CSC123 Midterm Exam Study Guide

             With Practice Problems AND Sample Solutions


   Topics of focus:

1. I won't ask you about the mechanics about alpha/beta conversion.  However,
   you need to understand how the lambda calculus relates to programming.
   That is, how the usual programming language constructs (booleans, ifelse)
   can be represented as lambda terms.

   You also need to understand how to define data structures as lambda 
   terms, and how this relates to oop in Scheme/Perl.

2. Basic Scheme programming.  I may ask you to write simple scheme
   functions such as length of a list. You also need to understand 
   tail-recursion and how to write such functions in Scheme.  Also look at
   how to define a function within a function.

3.  higher-order functions that take other functions as args and 
    possibly return functions.  You may be asked to write code fragments
    with the choice of scheme or perl.  Be very careful with Perl syntax.

4. Closures and objects.  How assignment (set!) affects the nature of
   programming.  For this topic, if I ask you to write code you can
   do it in either scheme or Perl.  This will be a MAJOR TOPIC on the
   test. Study the handout, assignments, and examples I did in
   class.  Also see the sample problem below.

6. Fundamental characteristic of inheritance.  It's not enough to simply
   memorize the slogan "every instance of a subclass contains an instance
   of the superclass".  You need to understand the impact of this
   principle on how programs can be written.  For example, how to model
   inheritance in Scheme/Perl/C.  How to model multiple-inheritance in
   Java/C#.  

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#

For the problems that require you to write code, there'll be nothing
exotic and you'll probably work off of some code that I will be
providing.  You should be able to READ and understand arbitrary code
in any of the languages we've visited (Scheme,Perl,C,C++,C#).  

Study thoroughly and early, but don't get paranoid and emotional.


Practice Problems  (solutions will be posted later - try them yourself first)
---

1.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)) 
(car (car '((2 3) (4 5))))
(define (f x) (+ x 1))
(f (f (f (f (car L)))))


2. 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).



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


4. 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));
}

  a. Explain what this function does.
  b. Write the function in Scheme.



5. write the following scheme expressions in lambda calculus form:

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


6. Explain the difference between let and set! in Scheme


7. What is the difference between static and dynamic scoping?  Why
   is static scoping almost always used?

   Determine and explain the output of the following program:

   my $x = 2;
   sub f { $x+1; }
   { my $x = 3;
     print f();
   }

   What would happen if both occurences of "my" were replaced by "local".



8. Given the following class in C++, write the equivalent in Scheme or Perl.
You must use the closure method for implementing objects.
Also write code that would be equivalent to the main function - 
that is, show how to create and use the objects.

using namespace std;
#include<iostream>
#include<string>
class pc
{
  private:
    String cpu;  // cpu type
    double ghz;  // cpu speed
    int megs;    // memory
    int gigs;    // hard drive
  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("pentium3",1.0,256,20);
   newpc = new pc("pentium4",3.2,512,80);
   oldpc->upgrade();
   if (newpc->fasterthan(oldpc)) cout << "newpc is faster\n";
     else cout << "newpc isn't very fast\n";
}

*** Note that A->B is equivalent to A.B in C#/Java.
---


9. Determine the output of the following C# program and explain why:
(I suggest you run it to see if you're right!)

using System;

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();
     A.g();
     B1.f();
     B1 = (subclass)A; // why is this cast necessary?  why is it valid?
     B1.f();
  }
}