CSC123/252 Midterm Study Guide (Fall 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
   C++, C# and F#.  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. Closures and objects.  How destructive assignment (mutation) affects 
   programming.  What is a closure? Study the python/c++ bank account
   programs and assignment.  Study the handout, assignments, and
   examples I did in class.   Also see the sample problems below.

4. Fundamental characteristics and requirements of OOP.  
   The "three D's" of OOP: their advantages and disadvantages.

5.  Inheritance in C++ and 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).

6. Covariance and Contravariance in C# and in Java.  Understand the problem
   of allowing arrays to be covariant.

7. Generics/Templates in C++, Java and C#, how they differ in their
   implementation, advantages and disadvantages. (not just syntax).
   This is the only topic we studied where C# differs significantly 
   from Java.

   7b. "concept" in C++20

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

9. Functional programming
   
   Functional programming in C and its limits
   Basic F# syntax, mechanics
   Using lambda expressions in F#
   Curried functions in F#
   PATTERN MATCHING in F#- how to use it and what are its advantages.
   Tail versus non-tail recursive programs. 

10. Monadic error handling in F# using options and results.  You will not
   be allowed to call get.  Must learn how to use map/bind.

------------------------

OTHER GUIDELINES:

  You will be asked to write small fragments of code in C, C++, C#, and F#.
  For C++ (for now) it will mostly involve lambda terms.
  You will also need to be able to read programs in Python and Java.
  For some problems, you may be given a choice of language to write the
  solution in (among those that we've studied).
  Study your own notes, my sample programs and documents, especially the
  ones that I wrote myself. Study past programming assignments.  I will
  provide sample solutions to some of them.  Doing the assignments is
  an excellent way to study for my exams.  Concerning topics, items that
  I have addressed repeatedly have a better chance of appearing on the exam.
  Items that I only mentioned once have a lower chance of appearing.
  When asked to explain a concept such as dynamic dispatch, it's best 
  to give an example.


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

Note: some of these problems are on the harder side but they will allow
you to be well prepared for the exam (study hard but don't panic).
---

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

   object[] A = new string[10];
   List<object> B = new List<string>();

   where List refers to System.Collections.Generic.List, which has
   methods such as .Add and .Get.

1b. Why are arrays allowed to be covariant in Java and in C#?

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 or F#) 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 C program

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 F#, which are statically
   scoped.

5. What is a closure?  Write a C++ or F# 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 "overriding" compared to "overloading"

  7c. what is the disadvantage of overriding compared to overloading
   

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

9e. The following template function is constrained by a modern "concept"
    
template<typename T> requires std::totally_ordered<T> 
bool sorted(vector<T> V)
  for(int i=1;i<V.size();i++) if (V[i-1] > V[i]) return 0;
  return 1;
}

When is the required concept checked?

Will this, and any code that calls it, compile if the "requires" 
clause is removed?

10. C++ templates can abstract over more than just typenames. You can
have an int N in a template, for example.  Why isn't this allowed in C#
or in Java? why not allow something like class A<type T,int N>?

11. java.util.function.Function<A,B> is an interface that requires
the following function to be defined:

   B apply(A x);

When Function is used as a type, it often occurs in the form

   Function<? super A, ? extends B> f;  // declares a function f

? super A means A or a superclass of A, and ? extends B means B or a 
subclass of B.

Can we aslo write  Function<? extends A, ? super B>   ???


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

13. Consider the following C# program:

interface number {}

class integer : number {
  public int x;
  public integer(int a) {x=a;}
}
class rational : number {
  public int n, d;  // numerator and denominator
  public rational(int a,int b) { n=a; d=b; }
}
class real : number {
  public double r;
  public real(double a) { r=a; }
}
public class greatquestion {
  number times(integer A, integer B) => new integer(A.x*B.x);
  number times(integer A, rational B) => new rational(A.x*B.n, B.d);
  number times(integer A, real B) => new real((double)A.x * B.r);
  number times(rational A,rational B) => new rational(A.n*B.n,A.d*B.d);
  number times(rational A,real B) => new real((double)A.n*B.r/(double)A.d);
  number times(real A, real B) => new real(A.r*B.r);
  number times(number A, number B) => times(B,A);

  number product(number[] N) { // find product of an array of numbers
     number ax = new integer(1);
     foreach(var n in N) ax = times(ax,n);
     return ax;
  }//product
}

What will be the result of calling the product function on any array of
numbers?  Which version of `times` will the function call?
Why doesn't this program work as intended?  Give clear, concise answers.


13b. Rewrite this program in F# and make it work as intended.

I will give you the type definition and the product function. You just
need to write `times`

type Number = Integer of int | Rational of int*int | Real of float;;

// write times here
let product (N:Number []) = 
  let mutable ax = Integer(1)
  for n in N do ax <- times ax n
  ax


14. Write a function in F# that computes the multiplicative inverse of 
a Number (1/number).  It should return an value of type option<Number>:
Either Some(n) where n is a Number, or None if the inverse doesn't exist:

The inverse of Integer(n) is Rational(1,n) if n is not zero ( n<>0 )
The inverse of Rationa(n,d) is Rational(d,n) if n is not zero
The inverse of Real(r) is Real(1.0/r) if r<>0.0
Otherwise, the inverse doesn't exist.


14b. Write a function (divide a b) that computes Number a divided by Number b
by multiplying a with the inverse of b.  divide must also return an option
since the inverse of b may not exist.

You may only use pattern matching or the monadic combinators `map` and `bind`.
Under no circumstances are you allowed to call `get`.

14c.  Rewrite the times function so that both numbers being mutiplied
are of type option<Number> and the return type is also option<Number>.
times should return Some(number) only if both arguments are Some(number)s.
If either argument is None, return None.

Same requirements as before but you can also call map2, but no calls to "get".

14d. Explain why it's generally not good practice to call get on an Option