CSC123/252 Exam1 Study Guide (Fall 2020)

                     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 pure lambda calculus relates to set! and closures.
   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 other functions.
   Higher-order functions that take other functions as arguments and 
   possibly return functions (map, fold, howmany, etc...).
   Study how this is done in Scheme, Perl, as well as C#.
   You may be asked to write code fragments (with a choice of language).

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!
   Static vs dynamic scoping is a major topic to study carefully.

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 (as well as video lectures for Perl).  
   Also see the sample problems below.

5. Fundamental characteristics of inheritance and oop.  static versus
   dynamic dispatch, multiple inheritance issues, etc. What is "bless"?

   -- the extent of the following topics depends on what can be covered
   -- before teh exam

6.  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, and the difference between
    dynamic dispatch (overriding) and overloading.

7. (possible) Type safety and type casting, including how they differ in C/C++ and Java/C#


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

1. What is the purpose of "bless" in Perl?

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) // this will compute 2**n in log(n) steps
{ if (n<1) return 1; 
  else 
    {
       int half = powerof2(n/2);  // 2**n = 2**(n/2) * 2**(n/2)
       if (n%2==0) return half*half;
       else return 2*half*half; // if n is odd, multiply by additional 2
    }
} 
// why is this not tail-recursive?

Here's how you'd do it in C without recursion at all, also in log(n) steps
int pw2(int n)
{
  int ax = 1;  // accumulator
  factor = 2;  // start with 2**1 = 2
  while (n>0)
  {
     if (n%2==1) ax *= factor;
     n = n/2; // shift over next bit
     factor = factor * factor; // only need 2**2, 2**4, 2**8, 2**16, etc...
  }
  return ax;
}


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.


4.3 Even harder variant of scoping question: show how to emulate dynamic 
    scoping using static scoping (in any language)

5. What is a closure?  Write a scheme/perl 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 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. 

#include<iostream>
#include<string>
using namespace std;

class pc   // objects that represent personal computers
{
  private:
    string cpu;  // cpu type
    double ghz;  // cpu speed
    double gigs;    // memory in gigabytes
    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("i7",2.0,1,0.5);
   newpc = new pc("core i9",3.8,16,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.


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 h(string x) { Console.WriteLine("x is a string!");}
  public static void h(object x) { Console.WriteLine("x is an object!"); }

  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();  
     object x = "abcd";
     h(x);
  }
}

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