CSC123 Midterm Exam Study Guide

  	           With Sample Solutions to Problems


   General area of questions:

1.   Lambda Calculus: 
   
     I will not ask you to do beta reduction or alpha conversion, but
     you should review what beta-reduction is (how it respects scoping).
     You need to understand the following principles, and not just
     vaguely - i.e., you should be able to related them to specific
     examples:

     Know that there are terms with no beta-normal form.  
     ((lambda (x) (x x)) (lambda (x) (x x)))

     Know the difference between "call-by-name" (outermost reduction) and
     "call-by-value" (innermost reduction).

     You should know what the "Church-Rosser" theorem says:
       (if A->B and A->C then B->D and C->D for some D, where '->' 
	represents beta-conversion).  

     You must understand the difference between static and dynamic
     scoping - in particular, why 'let' is statically scoped.  That is,
     what is let in lambda calc. form? 

     hint: (equal? (let ((x E) B)) ((lambda (x) B) E))

1.5 You should also understand how to define data structures in 
    lambda calculus, and how it relates to doing oop in scheme.

2.  Scheme basics - basic scheme syntax, cons, car, cdr, using quote
    ('), etc.    Define simple functions like length, member in
    scheme.  Know how to use let and define, including how to define
    functions within functions.  Study tail versus non-tail recursion.

3.  higher-order functions that take other functions as args and 
    possibly return functions.

5.  set! and object-orientation in Scheme.  This will be a MAJOR TOPIC
    on the test.  Study the handout, assignments, and examples I did in
    class.  You will be asked to write short programs using these techniques.

    Understand the difference between set! and let.  What's the difference
    between my and local in Perl?

6.  C# and OOP basics.  Be able to modify simple classes.  Understand the
    role of pointers in Java.  Understand the meaning of static, public,
    private, and protected.

7.  Inheritance in C# - understand the *purpose* as well as the mechanics
    of dynamic dispatch.  Know the consequences of the keywords "virtual",
    "override" and "new" with respect to inheritance.

8. Types and type casting.  How they differ in C/C++ and Java/C#

9.  In general, you will have to write scheme code and very simple C#/Java
    code (there'll be nothing exotic and you'll probably work off of
    some code that I will be providing).  However, you should be able to
    READ and understand arbitrary Java, C++, C# and C programs.  You
    need to appreciate that not everything is as it seems: e.g, A.B in 
    Java does not mean A.B in C++.


Sample questions  (solutions below - try them yourself first)
---

Given the definition  (define L '(0 2 4))

Explain what will be returned by the following expressions (L is defined
as above)

(cons (car L) (cdr L))
(cons 9 (cddr L)) 
(caar '((2 3) (4 5)))
(define (f x) (+ x 1))
(f (f (f (f (car L)))))
(if (null? L) 1 (cons 9 L))


Write scheme functions, one tail-recursive and one non-tail recursive,
that computes 2 to the nth power (don't use the built-in expt function).



Write a scheme function to return the reverse of a list of
i.e., (rev '(1 2 3)) --> (3 2 1)



Consider the following C program, where "cell" is a pointer to
a linked list node struct listcell { int head; listcell * tail };

cell fold(int (*f)(int,int), cell L, int ident)
{  if (L == NULL) return ident;
     else return (*f)(L->head,fold(f,L->tail,ident));
}

1. Explain what this function does.
2. Write the function in Scheme.



Write the following scheme expressions in lambda calculus form:

(begin A B)
(let ((x A)) B)

What is the difference between static and dynamic scoping?  I will
give you a program and you'll have to tell me how it'll behave under
these alternatives.  


Given the following class in C++, write the equivalent in Scheme (and C#).
scheme program must also be object oriented.  Also write code that would
be equivalent to the main function - that is, show how to create and use
the objects.

#include<iostream>
class pc
{
  private:
    String cpu; 
    double ghz;
    int megs;
    int gigs;
  public pc(String c, double g, int r, int d)  // constructor
    { cpu = c; ghz = g; megs = r; gigs = d; }
  public print()
    { cout << ghz << " ghz " + cpu + " cpu with " + ram;
      cout << "megs of memory and a " + gigs + "gig hard drive\n";
    }
  public void upgrade()  
    { megs = megs*2;  ghz = ghz + ghz/2; }
  public int fasterthan(pc * otherpc)  // in C++, int is same as boolean
    { return ghz > otherpc->ghz; } 
};  // class pc

int main()
{
   pc *newpc, *oldpc;
   oldpc = new pc("athlon",1.2,128,20);
   newpc = new pc("pentium4",2.0,256,40);
   oldpc->upgrade();
   if (newpc->fasterthan(oldpc)) cout << "newpc is faster\n";
     else cout << "newpc isn't very fast\n";
}

Does the expression "A.B" mean the same thing in C++ as it does in Java?
---


Determine the output of the following C# program and explain why:
(I suggest you run it!)

class superclass
{ private int x = 1;
  protected static int y = 1;
  public void f() 
   { Console.WriteLine("I'm the f in superclass\n"); }
  public virtual void g()
   { Console.WriteLine("I'm the g in superclass\n"); }
}

class subclass : superclass
{ public new int x = 1;
  public new void f()
   { Console.WriteLine("I'm the f in subclass\n"); }
  public override void g() 
   { x++;
     y++;
     Console.WriteLine("x is " + x + " and y is " + y); 
   }
}

public class goodquestion
{
  public static void Main(string[] args)
  {
     superclass A;  
     subclass B1;
     A = new subclass(); // A has different static and dynamic types
     B1 = new subclass();
     A.f();
     B1.f();
     B1 = (subclass)A; // why is this cast necessary, why is it valid?
     B1.f();
  }
}


---------------------------
Sample Solutions to above question:
---

Given the definition  (define L '(0 2 4))
Explain what will be returned by the following expressions (L is defined
as above)

(cons (car L) (cdr L))  : (0 2 4)
(cons 9 (cddr L))       : (9 4)
(caar '((2 3) (4 5)))   : 2
(define (f x) (+ x 1))  
(f (f (f (f (car L))))) : 4
(if (null? L) 1 (cons 9 L)) : (9 0 2 4)


Write scheme functions, one tail-recursive and one non-tail recursive,
that computes 2 to the nth power (don't use the built-in expt function).

; non-tail recursive:  (don't worry about negatives)
(define (power2 n) 
   (if (= n 0) 1 (2 * (power2 (- n 1)))))

; tail recursive - the real function is wrapped inside:
(define (powertwo n)
  (define (aux n ax)
     (if (= n 0) ax (aux (- n 1) (* 2 ax))))
 (aux n 1))

; if you insist on dealing with negative powers:
(define (powerdeux n)
  (if (< n 0) (/ 1.0 (powertwo (- 0 n))) (powertwo n)))


Write a scheme function to return the reverse of a list of
i.e., (rev '(1 2 3)) --> (3 2 1)

; I'll write it tail-recursively, which uses an accumulator list as a stack
(define (rev l ax)
  (if (null? l) ax (rev (cdr l) (cons (car l) ax))))

(rev '(1 2 3) '())  returns (3 2 1);
  


Consider the following C program, where "cell" is a pointer to
a linked list node struct listcell { int head; listcell * tail };

cell fold(int (*f)(int,int), cell L, int ident)
{  if (L == NULL) return ident;
     else return (*f)(L->head,fold(f,L->tail,ident));
}

1. Explain what this function does.

  repeatedly applies a (right-associative) operator f, with identity
id to a list l.  The identity is the element such that f(x,id) = x.

2. Write the function in Scheme.

(define (fold f l id)
  (if (null? l) id (f (car l) (fold f (cdr l) id))))


Write the following scheme expressions in lambda calculus form:

(begin A B)  :  (lambda x. B) A, where x is not free in B
   under call-by-value, A is evaled first, then B. x is a dummy param

(let ((x A)) B) : this one is really important to know:
   
   (lambda x.B) A   - here x may appear in B. let is a form of
"suspended" substitution.

What is the difference between static and dynamic scoping?  I will
give you a program and you'll have to tell me how it'll behave under
these alternatives.  

for the following program:
(let ((x 2))
   (let ((f (lambda (y) (+ y x))))
      (let ((x 4))
         (f 1))))

static (lexical) scoping returns 3, for x is looked up in f's defining
(static) environment.  under dynamic scoping, x will be looked up in the
calling environment, and the above expression will return 5.  Perl's "local"
variables are dynamically scoped.


Given the following class in C++, write the equivalent in Scheme (and C#).
scheme program must also be object oriented.  Also write code that would
be equivalent to the main function - that is, show how to create and use
the objects.

#include<iostream>
class pc
{
  private:
    String cpu; 
    double ghz;
    int megs;
    int gigs;
  public pc(String c, double g, int r, int d)  // constructor
    { cpu = c; ghz = g; megs = r; gigs = d; }
  public print()
    { cout << ghz << " ghz " + cpu + " cpu with " + ram;
      cout << "megs of memory and a " + gigs + "gig hard drive\n";
    }
  public void upgrade()  
    { megs = megs*2;  ghz = ghz + ghz/2; }
  public int fasterthan(pc * otherpc)  // in C++, int is same as boolean
    { return ghz > otherpc->ghz; } 
};  // class pc

int main()
{
   pc *newpc, *oldpc;
   oldpc = new pc("athlon",1.2,128,20);
   newpc = new pc("pentium4",2.0,256,40);
   oldpc->upgrade();
   if (newpc->fasterthan(oldpc)) cout << "newpc is faster\n";
     else cout << "newpc isn't very fast\n";
}

(define (buildpc cpu ghz megs gigs)
  (define print (lambda ()
     (being (display ghz) (display " ghz ") (display cpu) ; ...
      )))
  (define (upgrade) (begin (set! megs (* 2 megs))
			   (set! ghz (+ ghz (/ ghz 2)))))
  (define (getghz) ghz) ; accessor
  (define (fasterthan otherpc)
     (return (> ghz (otherpc 'getghz))))
  ; interface  - note the procs with no args are called in place:
  (lambda (method)
    (cond ((equal? method 'print) (print))
	  ((equal? method 'getghz) (getghz))
	  ((equal? method 'upgrade) (upgrade))
          ((equal? method 'fasterthan) fasterthan)
	  (#t 'error))))

(define newpc (buildpc "athlon",1.5,128.20));
(define oldpc (buildpc "pentium4",2.0,256,40));
(oldpc 'upgrade)
(if ((newpc 'fasterthan ) oldpc) "faster" "not faster")


Does the expression "A.B" mean the same thing in C++ as it does in Java?

No. A.B in C++ means A->B in Java.  there's an implicit * and dereference.

---


Determine the output of the following C# program and explain why:

I changed it a bit to make it more interesting

class superclass
{ private int x = 1;
  protected static int y = 1;
  public void f() 
   { Console.WriteLine("I'm the f in superclass\n"); }
  public virtual void g()
   { Console.WriteLine("I'm the g in superclass\n"); }
}

class subclass : superclass
{ public new int x = 1;
  public new void f()
   { Console.WriteLine("I'm the f in subclass\n"); }
  public override void g() 
   { x++;
     y++;
     Console.WriteLine("x is " + x + " and y is " + y); 
   }
}

public class goodquestion
{
  public static void Main()
  {
     superclass A;  
     subclass B1, B2;
     A = new subclass(); // A has different static and dynamic types
     B1 = new subclass();
     A.f();
     B1.f();
     B2 = (subclass)A; // why is this cast necessary, why is it valid?
     B2.f();
     B1.g();
     A.g();
     B1.g();
  }
}


//  output:
I'm the f in the superclass
I'm the f in the subclass
I'm the f in the subclass
x is 2 and y is 2;  // g in subclass is called because of "override"
x is 2 and y is 3;  // x is new instance, but y is static