CSC123 Midterm Exam Study Guide

                  With Practice Problems


   Topics of focus:

1. Some lambda calculus concept (call by name/value, church-rosser) may
   appear on the exam, but this will not be an emphasis.  However, you
   need to understand how beta-reduction relates to set! and closure.
   That is, how closures changes the idea of a "function" to enable
   state and objects

2. Usage of Scheme/Ruby.  You need to be able to understand and
analyze both Scheme and Ruby programs.  However, when I ask you to
write code you can use either scheme or ruby.  However, when writing
Ruby code you'll be asked to follow certain restrictions (e.g., use
lambda-closures instead of "class")

   Don't forget to study the following mechanisms and concepts:

   Linked lists in scheme/ruby.
   Tail versus non-tail recursive programs
   Functions that are defined within another function

2.  Higher-order functions that take other functions as args and 
    possibly return functions (map, fold, howmany, etc...) 
    You may be asked to write code fragments.

3. The difference between static (lexical) and dynamic scoping of
   variables.  Do not confuse this topic with static vs dynamic
   dispatch with respect to inheritance.  
   EVERY YEAR THERE ARE PEOPLE WHO GET THESE TWO CONCEPTS CONFUSED. SO
   PLEASE REMEMBER TO STUDY THIS DIFFERENCE.  NO MERCY POINTS!

4. Closures and objects.  How assignment (set!) affects the nature of
   programming.  What is a closure (read the handout on "modularity,
   objects and state").  Study the ruby/scheme bank account
   assignment.  This will be a MAJOR TOPIC on the test.  Study the
   handout, assignments, and examples I did in class.  Also see the
   sample problems below.

6. Fundamental characteristics of inheritance and oop.  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/Ruby/C, which do not have the built-in support
   for oop compared to C++/Java/C#. 

7. C# delegates

8.  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.  Understand the 
    difference between interface and superclass.

9. Types and type casting, including how they differ in C/C++ and Java/C#

10. The Observer Design Pattern. 

11. Other topics to be determined, 
    depending on how much was covered before the exam.

For the problems that require you to write C# 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,Ruby,C,C++,C#).  

Study thoroughly.  This may be the most important written exam of
the semester.


Practice Problems  (Sample solutions to be posted)
---

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 or ruby functions, one tail-recursive and one non-tail
recursive (that is, recursive but not tail-recursive), that computes 2
to the nth power (don't use the built-in expt function).  For the
tail-recursive function, define it inside another function that sets
the intial parameter of the interior function.  hint: (I probably
won't give such a hint on the exam however):

Here's how you'd do it for the tail-recursive fibonacci function:

(define (fib n)
    (define (tfib n a b) (if (< n 2) b (tfib (- n 1) b (+ a b))))
  (tfib n 1 1)) ; body of outer function calls the inner function

another hint: here's how you'd write it non-tail recursively in C 

int powerof2(int n)
{ if (n<1) return 1; else return 2*powerof2(n-1); }
// why is this not tail-recursive?



3. Consider the following Scheme program:

(define (fold f identity L)
  ( if (null? L) identity (f (car L) (fold f identity (cdr L)))))

Explain what this function does.  Give an example of how to call it 
and what result you can expect.

3b.  Explain how the above function differs from the one below (besides being
     written in a different language - we're not concerned with syntactic
     differences).

def cdr(m) 
  m[1..m.length-1]
end

def Reduce(f,i,m)
  if m.length<1 then return i end
  return Reduce(f, f[i,m[0]], cdr(m))
end
  
  

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

   Determine the output of the following program and explain why:

def G(y)
  x = 1  # local var within g
  lambda {|y| x+y}  
end  

def F()
  x = 2  
  g = G(1) 
  g[4]
end
print "scoping test: ", F(), "\n"


4b. I may also ask a question like the following:

  Suppose you're shown a new language that has C-style syntax

   int x = 1;
   void f() { print(x); }
   int main()
   { int x = 2;
     f();
   }
  
  Explain how you would use this program to determine if the language
  uses static or dynamic scoping.


5. What is a closure?  Write a scheme/ruby closure function that takes
   no arguments, but which returns 2 the first time it's called, 4 the
   second time it's called, 8 the third time, 16 the fourth time, and so
   on.  That is, 
     print f()    # prints 2
     print f()    # prints 4, etc..

6. Given the following class in C++, write the equivalent in Scheme or Ruby.
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.
hint: you'll need to create a function to return the ghz value, because 
"private" in C++/Java/C# only gives class-level protection. 

using namespace std;
#include<iostream>
#include<string>
class pc   // objects that represent personal computers
{
  private:
    String cpu;  // cpu type
    double ghz;  // cpu speed
    int megs;    // memory
    int gigs;    // hard drive capacity
  public pc(string c, double g, int r, int d)  // constructor
    { cpu = c; ghz = g; megs = r; gigs = d; }
  public void upgrade()  // increase memory and speed
    { 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("pentium4",2.0,512,120);
   newpc = new pc("core2 quad",2.8,4096,1000);
   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.
---


8. 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()  // static override
   { Console.WriteLine("I'm the f in subclass\n"); }
  public override void g()  // dynamic override
   { 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(); 
     B1 = new subclass();
     A.f();   
     A.g();   
     B1.f();  
     B1 = (subclass)A;
     B1.f();  
  }
}

8.2 can you write code to call the superclass.g() function?:

9.  Consider the following inheritance structure in C# and code that
    tries to use it:

  interface I     
  { void f(); }

  class S {}

  class A : S,I 
   { public void f() {Console.WriteLine("A.f"); } 
   }
  class B : S,I 
   { public void f() {Console.WriteLine("B.f"); } 
   }

  ...
Given:

      I u = new B();
      S v = new A();
      A n = new A();

  For each case below, determine and explain if it's valid, 
  causes a compile-time error, or a runtime error.  Consider each 
  case independently.


    1.  v = n;

    2.  n = (A) new B();
    
    3.  n = (A) u;      

    4.  v.f();

    5.  ((A)v).f();

    6.  ((I)v).f();


10. In the Obeserver pattern there are observers and observees.  Which
    classes are the "update" functions located in?  Why are there different
    update functions in these classes?  Explain when update is called.