CSC123/252 Midterm Study Guide (Spring 2021)

                     With Practice Problems


   Topics of focus:

1. No direct questions on lambda calculus but you need to understand how
   lambda terms appear in scheme, perl, and to what extend can they be
   represented in C.

2. Functional programming in C/Perl.
   
   You need to be able to understand and analyze Scheme, C and Perl
   programs.  However, when I ask you to write code you can use any of
   these languages.  You'll be asked to follow certain restrictions in
   coding, as on the first two programming assignments.

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

   *Limitations to pure functional programming in C
   *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.

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, or with other uses of "static" 
   and "dynamic". 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 (mutation) 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.

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 static overloading.

    *The Visitor Design pattern.  Study the EXPRESSION TREE programs in C#.

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

8. Generics in C++, Java and C# and how they differ

   8b. Covariant and Contravariant types, especially in C#


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

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

2. The following function in C computes 2**n (2 to the nth power) in
   log(n) steps by binary factorization on n. 

int pw2(unsigned 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;
}

Rewrite the function in a purely functional style, without loops,
without destructive assignment and with a tail-recursive function
wrapped inside a larger function.


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 (no perl packages).
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?:


9a. 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.

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

9c. Would the visitor pattern still work without the ability to overload
    the visit function inside each visitor?

10. Compare the following implementations of polymorphic linked lists:

class list
{
   object head;
   list tail;
}

class list<A>
{
   A head;
   list<A> tail;
}

What are the advantages of using one form instead of another? 

11. Describe what will happen with the following C# segments of code, in terms
   of any compiler errors, or runtime errors, and EXPLAIN WHY

   // assume using System; and using System.Collections.Generic;

   a. object[] A = new string[10];
      A[0] = 1; // 1 is not a string but it's an object

   b. List<object> B = new List<string>(); // equivalent to ArrayList in java


12. Determine if the following program will compile and run, and EXPLAIN WHY.
using System;

interface I<T>
{
   int f(T other);
}

class A : I<A>
{
   protected int x = 2;
   public int f(A other) { return x-other.x; }
}

class B : A
{
   double y;
   public B(double z) {y=z;}
}

public class hardquestion
{
  public static void Main()
   { I<B> x = new B(2.5);
   }
}

12b.  What minimal changes (without changing main) should be made to 
get the program to work as intended.


13. Explain why the following java generic class won't compile:

class someclass<T>
{
   public T x;
   public static T y; 
}

Would the class compile in C#?  Why?