Sample Solutions to Practice Problems on Midterm Study Guide

1. Explain what is meant by "covariance" and by "contravariance".  Under
   what circumstances is each principle valid?  Give an example of each.

   Covariance means that the codomain (return type) of a function can become
   more specific (smaller). Contravariance means the domain can become
   more general (larger).  The domain cannot become smaller and the codomain
   cannot become larger.  For example, a function of type string -> object
   can be replaced by a function of type object -> string but not vice versa.

2. What's the difference between the following two lines in Java. Will
   either compile and run?

    i. Object[] A = new String[10];
   ii. ArrayList<Object> B = new ArrayList<String>();


   The first line will compile but the second will not.  This is
   because arrays were allowed to be covariant in order to support
   polymorphism, which they shouldn't be, as it results in the
   following inconsistency:

     A[0] = "abc";
     A[1] = new Integer(2);

   This will compile but shouldn't.  Type variance is properly observed with
   generics.


3. Explain the difference between the following functions:

   a. let f(x,y) = x+y
   b. let g x y = x+y

   Give an example of the functions behaving differently

   Function f is not Curried but the function g is.  One can call
   g 1, which returns a function expecting another argument but one
   can only call f with both arguments in a pair, as in f(2,3).


4. Determine if the following function is tail-recursive and if not,
   write a tail-recursive version

     let rec fib n = if (n<3) then 1 else fib(n-1) + fib(n-2)

   This function is not tail recursive.  The following one is:

     let fib n =
       let rec fibiter n a b =  // this is tail recursive
         if (n<3) then b else fib (n-1) b (a+b)
       fibter n 1 1  // body of outer function


5. Is the following function tail-recursive?

     let rec forall predicate m =
       match m with
         | [] -> true
	 | a::b -> (predicate a) && forall predicate b

   It is, even though the && appears to be the last operation.  But it isn't:
   the && is shortcircuited: the recursive call is only made if (predicate a)
   returns true.


6. Rewrite the following to use the Option monad instead of raising exceptions

     let safediv a b =
       if b<>0 then a/b else raise(Exception "div by zero")

     let safediv a b =
       if b<>0 then Some(a/b) else None

6b. Write a function 'howmany' that takes a list and a predicate, and
    returns how many values x in the list are such that predicate(x) evaluates
    to true.

   let howmany m predicate =
     let rec iter m counter =  // this is also tail-recursive
       match m with
         | [] -> counter
	 | a::b when (predicate a) -> iter b (counter+1)
	 | _ -> iter b counter
     iter m 0

7. Determine the output of the following program and explain why:

     let x = 1
     let f y = x+y
     let g() =
       let x = 2
       printfn "f(1) is %d"  (f 1)

     F# will output 2 because it's statically scoped.
   
8. Show how to emulate dynamic scoping in a programming language that
   only allows static scoping

   Requires mutation:

   let mutable x = 1
   let f y = x+y
   let g() =
     let savex = x
     x <- 2
     printfn "f(1) is %d"  (f 1)  // prints 3
     x <- savex

   Dynamic scoping is simulated by temporarily replacing the value of a global


9. Determine the output of the following program:

     let make n =
       let mutable x = n
       fun y ->
         x <- x+y
	 x
	 
     let mutable a1 = make 0
     let mutable a2 = make 0
     a1 2  // 2
     a1 2  // 4
     a1 2  // 6
     a2 2  // 2


10. Concerning templates (generics), explain the differences between how
    they're implemented in C++ compared to Java.
     
    C++ templates are instantiated at compile time and carries zero
    runtime overhead. However, template code is not type-checked, which
    they are in Java.  Java uses "type erasure" to implement templates
    (generics) in which typenames are replaced by the Object superclass.


11. C++20 introduced "concepts", illustrated in

      template<typename T> requires std::totally_ordered<T>

    Explain whether the program will still compile if the "requires"
    clause is dropped.

    The requirement is checked against instantiations of T at compile time.
    But it will still compile: the joke is that "the requirement is optional."
    

12. Explain why advanced object oriented programming requires dynamic
    memory allocation.  Why is stack allocation not enough?

      Because the compiler doesn't know the exact type and
      therefore the size of the object.

    Explain what is meant by "dynamic dispatch" and "dynamic typing"

      Dynamic typing means that the exact type of objects is only known
      at runtime and is carried by the objects.  Dynamic dispatch means
      when a function a.f() is invoked, the dynamic type of a is used to
      determine which version of f to call.
    

13. What's the difference between "overloading" and "overriding"?
    Give an example of each.

    Both concern resolving functions that share the same name.
    Overloading happens at compile time while overriding happens at
    runtime using dynamic dispatch.

    struct A {
      virtual int f() { return 1; }
    };
    struct B {
      int f() override { return 2; }
    };
    
    int g(A x) { return 1; }
    int g(B x) { return 2; }

    int main() {
      A* n = new B(); // static type A, dynamic type B
      int x = n.f();  // returns 2 because of overriding (dynamic dispatch)
      x = g(n);   // returns 1 because of overloading (static type used)
    }


14. Give an example of a "pure virtual function" in the context of
    the shapes example in C++.

    class shape {
      virtual double area() = 0;
    };  // one cannot create an instance of such a class

15. Determine if the following C++ code contain any memory errors, and if so,
    what type of errors:

    int* px = new int(3);
    int* qx = new int(4);
    px = qx;
    delete px;
    delete qx;

    px = qx; causes a memory leak: the int(3) is still on the heap
    with no live pointer pointing to it.  There is also a double free
    at the end.  Both are runtime errors.

15b. Explain what is meant by the "first fit", "best fit" and "worst fit"
     memory allocation strategies.

     First fit finds the first block of memory large enough to satisfy the
     request while best fit finds the smallest block of memory large enough
     to satisfy the request.  Worst fit finds the largest block of memory
     that satisfies the request.

16. Explain what's meant by the "lifetime" of a value in memory.  When does
    lifetime end?

    The lifetime of a value is how long it's guaranteed to stay at the same
    location in memory.  Lifetime ends with mutation: either by being assigned
    to a different value or being popped from the stack or freed from the heap.
    It also ends following a "transfer of ownership" or "move".

16b. Give an example of a function returning a "dangling pointer".

    int* f() {
      int x = 1;
      return &x;  // the pointer will outlive the stack-allocated x.
    }

17. The following problem concerns the difference between pointers
    and references in C++.  Determine the output of the following code:

    int x = 1;
    int y = 2;
    int* px = &x;
    int& rx = x;
    px = px+1;
    rx = rx+1;
    cout << rx << " and " << *px << endl;  

  prints 2 and some arbitrary value, or segmentation fault. px was set
  to point to the memory location after that of x (&x), which is probably
  that of y, depending on where the compiler decides to allocate memory.
  rx always refers to x, it's effectively an alias for x.

18. Determine if the following will compile and explain why:

    unique_ptr<int> x = make_unique<int>(2);
    unique_ptr<int> y = make_unique<int>(3);
    x = y;

    It will not compile.  x=y will destroy the uniqueness of y.
    x = move(y) compiles and triggers move semantics.

19. Explain what happens during a "move assignment"  x = move(y) :

    1. if x was pointing to heap-allocated memory, it's freed
    2. x is set to point to what y was pointing to.
    3. y is set to point to nullptr.

20. What are the "Rule of Three", "Rule of Five" and the "Rule of Zero".

    The rule of three says if there is a custom destructor then there
    should also be a custom copy constructor and copy = operator.
    The rule of five adds the custom move constructor and move = operator.
    The rule of zero says that it's best to not to define any of the above:
    leave it to the defaults.  The rule of zero should be applied when
    using smart pointers such as std::unique_ptr.


21. Determine if the following program contain memory errors, and if so,
    what type:

    struct vec {
      int* a;
      int length;
      vec(int len) {
        a = new int[len];
        length=len;
      } // constructor
      ~vec() {
        if (a) delete[] a;
      }  // destructor
    };

    int main() {
      vec A(10);
      vec B(10);
      A = B;
    }

  This program will cause a double free at the end of main: the default copy
  = operator in A = B will create two copies of the pointer int* a, and the
  destructor of both structs will be called when they're popped from the
  stack.  This is why programs should either follow the rule of three, or
  the rule of zero by replacing int* a with unique_ptr<int[]> a;


22. Explain the difference between a shared_ptr and a weak_ptr.  When is
    a weak_ptr required?

    A weak_ptr is a downgraded shared_ptr that does not increase the
    reference counter when a shared_ptr is assigned to a weak_ptr.  weak_ptr
    is required to avoid cycles, which could lead to memory leaks, in
    pointer graphs.  multiple shared_ptr, unlike unique_ptr, can point to
    the same heap-allocated structure, which is only freed when the
    reference counter goes to zero.
    

22b. What is the effect of calling .lock() on a weak_ptr?

     Temporarily upgrades the weak_ptr to a shared_ptr to access the
     heap data.  Used only as a R-Value


23. Is a shared_ptr more efficient than a unique_ptr?  Why?

    No. There's more runtime overhead both in terms of memory for the
    counters and the need to coordinate between multiple shared pointers.


24. Explain what's happening in the following program. What is causing
    the unique pointers to lose their uniqueness?

    void no_raii() {
      int *x = new int(1);
      unique_ptr<int> px(x);
      unique_ptr<int> qx(x);
    }

    What's causing the loss of uniquess is violation of "RAII",
    Resource Acquisition is Initialization.  There is a gap between
    the acquistion of the heap data int(1), and the initialization of
    the unique_ptr qx, in which px was initialized with the same
    pointer, resulting in pointers that are "uniquely" not unique. It
    will also result in a double free.  This is why unique_ptr should
    always be created by make_unique, and not by its public
    constructor that takes a raw pointer.


25. The 'memcpy' function from the cstring library copies bytes from a source
    to a destination memory address.  Show how it can be used to compromise
    the uniqueness of unique pointers.

    unique_ptr<int> x = make_unique<int>(3);
    unique_ptr<int> y = make_unique<int>(8);
    memcpy(&x,&y,sizeof(unique_ptr<int>));

    By creating the raw pointers &x and &y we're able to use memcpy to
    copy the pointers, creating two identical "unique" pointers.  This
    will also cause a memory leak of the integer 3, and later a double free
    on the integer 8.  This is why raw pointers should never be mixed
    with smart pointers.