CSC123 Midterm Exam Study Guide

                  With Practice Problems


   Topics of focus:

1. Some lambda calculus concepts (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/Perl.  You need to be able to understand and
   analyze both Scheme and Perl programs.  However, when I ask you to
   write code you can use either scheme or Perl.  If you're writing
   Perl code you'll be asked to follow certain restrictions (e.g., use
   lambda-closures instead of "package")

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

   Linked lists in scheme.
   Tail versus non-tail recursive programs.  ***
   Functions that are defined within another function.
   Higher-order functions that take other functions as args and 
   possibly return functions (map, fold, howmany, etc...).
   Study how this is done in Scheme, Perl, as well using C# DELEGATES.
   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. They're not directly related.
   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 scheme/perl bank account
   program and assignment.  Study the handout, assignments, and
   examples I did in class.  Also see the sample problems below.  This
   could be a point of emphasis on the exam.

6. Fundamental characteristics of inheritance and oop.  static versus
   dynamic dispatch, multiple inheritance issues, etc. 

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 
    when and where dynamic dispatch occurs.

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

10. The Visitor Design Pattern 

11. Polymorphism (possible).  Specifically the difference between
natural and non-natural polymorphism and how to implement them in C#
and other languages.  The use of generics (parametric types) in C#,
and how it is different from templates in C++.  Covariant and
contravariant types.

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,Perl,C,C++,C#).  

Study thoroughly.  This exam may be as important as the final.


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 perl 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

sub fib
{
   my $n = $_[0];
   my $tfib;  // don't combine this line with one below (because of recursion)
   $tfib = sub { my ($n,$a,$b) = @_;
                 if ($n<2) {$b} else {$tfib->($n-1,$b,$a+$b)}
               };
   $tfib->($n,1,1);  // calling 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/perl program:

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

sub fold
{
   my ($f,$identity,@L) = @_;
   if (@L==()) {$identity} 
    else {  my ($head,@tail) = @L;
            $f->($head,fold($f,$identity,@tail));
         }
}

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


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:

   my $x = 1;
   sub f 
    { $x }

   {  
      my $x = 2;
      print f();
   }

What would be result of changing my to local?


4.2 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/perl closure function that takes
   not 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 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.
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
    double gigs;    // memory
    double teras;   // hard drive capacity in terabytes
  public:
    pc(string c, double g, double r, double d)  // constructor
    { cpu = c; ghz = g; gigs = r; teras = d; }
    virtual void upgrade()  // increase memory and speed
    { gigs = gigs*2;  ghz = ghz + ghz/2; }
    virtual 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,1,0.5);
   newpc = new pc("i7",2.8,8,2.0);
   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.

7. (somewhat harder).  Implement in Perl/Scheme a subclass with some
additional properties:

class multicorepc : public pc
{
  private:
    int cores;  // number of cpu cores
  public:
    pc2(string c, double g, double r, double d, int e) : pc(c,g,r,d)
    { cores = e; }
    int fasterthan(pc *other)  // override superclass virtual method.
    { return ghz*cores > otherpc->ghz*otherpc->cores; }
};

---


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();



10a. Assume that in the visitor pattern, the visitee classes are
A, B, and C.  Write the interfaces for the abstract visitee and
the abstract visitor.


10b. Show how the *accept* function of the visitor pattern should be
implemented (write the function). 


11. Explain how templates in C++ are different from Generics in C#.  
    This is a technical question: it's not asking you to write an essay
    praising one language and making fun of another.  Simply point out
    the TECHNICAL difference.


12. What does "contravariant" type parameters mean?  Explain the circumstances
    under which a type parameter can be labeled contravariant (in). 

    I could also ask you something like:

    Explain what's WRONG with the following interface:

    interface badinterface<in A, out B>
    {
       void f(A x);
       void g(A x, B y);
    }