CSC 123 Midterm Study Guide.

Topics:

Basic definitions of call-by-value versus call-by-name
Type soundness
Static versus dynamic type checking / type inference
Static versus dynamic scoping, relationship to lambda calculus

F# Programming

  Curried and Uncurried functions
  Tail Recursion
  Pattern Matching
  Monadic Error handling
  Comparison to OOP

OOP Essentials: the "three D's": dynamic memory allocation, typing,
and dispatch.  C/C++/Java support for advanced OOP.

Templates and Generics.  Covariance and Contravariance.

Memory allocation and deallocation stragegies.
Stack versus heap allocation.
First fit, best fit and worst fit, tradeoffs.
Data structures used in memory allocation (doubly linked list and
binary search tree).

Different types and causes of memory errors

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

Practice Problems (Sample Solutions in Separate File)

--

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

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

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

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)

5. Is the following function tail-recursive?

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

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")

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.


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)
   
8. Show how to emulate dynamic scoping in a programming language that
   only allows static scoping


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
     a1 2
     a1 2
     a2 2

10. Concerning templates (generics), explain the differences between how
    they're implemented in C++ compared to Java.

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.

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

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

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

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

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;

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

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

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

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;

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;

19. Explain what happens during a "move assignment":

    x = move(y);

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

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

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

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

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

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

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

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.