CSC123/252 Midterm Study Guide (Spring 2024)

                     With Practice Problems


   Topics of focus:

1. No direct questions on lambda calculus but you must understand the
   scoping rules of lambda calculus (concerning free and bound
   variables), and essential properties like the Church-Rosser theorem
   and the uniqueness of normal forms. Be able to use lambda terms in
   Python, C++ and C#. Understand to what extend they can be
   represented in C.  Identifying free variables is crucial.  Many
   interesting topics only arise because of what's done with free
   variables.  For example, without free variables, there's no issue
   of static versus dynamic scoping.  Without free variables, there
   are no closures, and without mutation of free variables, most
   functions remain stateless.

2. The difference between static (lexical) and dynamic scoping of
   variables.  Do not confuse this topic with dynamic typing, dynamic
   dispatch and dynamic memory allocation.
   EVERY YEAR THERE ARE PEOPLE WHO GET THESE CONCEPTS CONFUSED. SO
   PLEASE REMEMBER TO STUDY THIS DIFFERENCE.  NO MERCY POINTS!
   Static vs dynamic scoping is an important topic to study carefully.

3. Functional programming
   
   You need to be able to understand and analyze Scheme, Python, C,
   C++ and C# programs.  You may have to write short segments of code
   in C, C++, C# and maybe Python or Javascript (you may be given a
   choice between these languages for certain problems).

   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 C as well as Python

4. Closures and objects.  How destructive assignment (mutation) affects 
   programming.  What is a closure (read the handout on "modularity,
   objects and state").  Study the scheme/python bank account
   program and assignment.  Study the handout, assignments, and
   examples I did in class.   Also see the sample problems below.

5. Fundamental characteristics and requirements of OOP.  
   The "three D's" of OOP: they're advantages and disadvantages.

6.  Inheritance in C++, C# - understand the *purpose* as well as the
    mechanics of dynamic dispatch.  Know the consequences of the
    keywords "virtual" and "override" with respect to inheritance.
    Understand when and where dynamic dispatch occurs, and the
    difference between dynamic dispatch (overriding) and static
    overloading.  What are C# "extension methods" and what are their
    limitations?

    Study the different versions of the expression tree program, especially
    the "csc17" version and the oop/functional hybrid version (with match).

7. Type safety and type casting, compile-time versus runtime type safety,
   including how they differ in C/C++ and Java/C#

8. Error handling using option monad as defined for C# programming assignment.
   You may be asked to write small pieces of code using this monad, similar
   to problems on the programming assignment.  I may provide you with a
   signature (or partial source code of the implementation of option).

9. Covariance and Contravariance in C# and in Java, but mostly in C#.

10. Generics/Templates in C++, Java and C#, how they differ in their
   implementation, advantages and disadvantages. (not just syntax).

   10b. "concept" in C++20



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

1. What's the difference between the following two lines in C#:

    var x = 1;
    dynamic x = 1;  (hint: it relates to item 7 above).
   (If I don't remember to cover this topic, it won't be on the exam)

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 C) 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/C program

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

int fold(int (*f)(int,int), int identity, list L) {
  if (isnil(L)) return identity; else return f(car(L),fold(f,identity,cdr(L)));
}
//assume list defines a linked list struct, car(L) returns the first item
//contained in the list and cdr(L) returns pointer to rest of list, and
//isnil(L) determines if L is an empty list.

  a. Explain what this function does (give an example of how it works)


  b. Is this function tail-recursive?


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

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

  Suppose you're shown a new language that has C-style syntax, but is not C
  (MAIN is in all captials!)

   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.

   4b. An even harder question would be:

   In Perl, the keyword `local` declares dynamically scoped variables,
   and the following program will print 2. (changing "local" to "my"
   will switch to static scoping and print 1)

   local $x = 1;
   sub f { $x }   # lambda ().return x
   sub g {  
      local $x = 2;
      print f();
   }
   g();

   **Show how to emulate this program in C or in Python, which are statically
   scoped.

5. What is a closure?  Write a Python/Javascript/C++ 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. Determine the output of the following C++ program

#include<iostream>
int main() {
  using namespace std;
  int x = 0;
  auto f = [&x](int y) mutable { x += y; };
  auto g = [x](int y) mutable { x += y; return x; };
  auto h = [x]() mutable { x = 1-x;  return x; };
  
  f(1);
  cout << "x is now " << x << endl;
  
  cout << g(1) << endl;
  cout << g(1) << endl;
  cout << "and x is now " << x << endl;
  
  cout << h() << endl;
  cout << h() << endl;
  cout << h() << endl;  
  cout << "the final value of x is " << x << endl;
  return 0;
}//main


7. Explain why object oriented programming requires dynamic type information.

  7b. what is the advantage of "overloading" versus "overriding"
   
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. Explain what, if anything, is wrong with the following Java class, and WHY:
    MUST EXPAIN WHY.

class bigobject<T> {
  T x;
  static T y;
  T[] A;
  bigobject(int n) { A = new T[n]; }
}

9b. Explain what, if anything, is wrong if exactly the same class is compiled
    in C#.

9c. Explain how template classes/functions in C++ carry no runtime overhead
    in terms of speed/memory (how is zero-overhead abstraction achieved).

9d. Determine the result of compiling the following C++ template, what (if
    any) errors would be emitted by the compiler, and why?

template<typename T>
class C {
public:
  T x;
  bool f() { return x.is_my_favorite_name_for_a_variable(); }
};


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.

12c.
    What's the difference between (A*)p and dynamic_cast<A*>(p) in C++

13. Explain what, if anything, is wrong with the following C# interface:

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

14. This question concerns the option monad and you may consult the source code 
    for the monad for this problem.
  
    C# contains a Stack<T> class that works as follows:
  
      using System.Collections.Generic;
      ...
      // in main:
      Stack<int> S = new Stack<int>();
      S.Push(1);
      int x = S.Pop();
      System.Console.WriteLine( S.Peek() );

  This code fragment compiles but will throw an System.InvalidOperationException
  because after the one is poped, there is no value to peek (peek looks at
  the top value without removing it).  Both .Pop and .Peek could throw this
  exception.  You are to write an "object adaptor" for this stack class,
  Safestack<T>, with versions of push, pop that return Nothing (None) 
  instead of throwing exceptions.

14b. (This one's a bit hard, but it's good practice)

     Write a function that takes an instance of Safestack<T> and a function
     of type Func<T,T,Option<T>> that pops the top two value from the stack, 
     applies the function, and pushes the result back on the stack, if 
     there is one.  It should also return the value computed by the function.

     Option<T> apply_op<T>(Safestack<T> stack, Func<T,T,Option<T>> fun)

     For example, if the top two values on the stack of integers are 1 and 3
     (2 on top) a call to 

       apply_op<int>(stack, (x,y)=>Option<int>.Make(x-y)) 
 
     will pop the 3, then 1 from the stack, push 2 (3-1) on the stack,
     and return Some(2).   

     However, if there were fewer than two values on the stack, or if
     the function fun returned None, then the function should still try to
     pop the stack twice (make the stack empty) and return None.

     You many only call push, pop and peek on the Safestack.  

     Your code may not crash.