CSC 123 Midterm Study Guide.

Topics:

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

F# Programming

  Curried and Uncurried functions
  Tail Recursion
  Pattern Matching
  Monadic Error handling
  Mutable closures such as used in streams
  Comparison to OOP

Limitations of C in regard to functional and object-oriented programming.

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.

How Generics are implemented in C++, Java and C#/F#

// NOT ON TEST:
Memory allocation and deallocation stragegies.
Stack versus heap allocation.
First fit, best fit and worst fit, tradeoffs (lightly)

Different types and causes of memory errors (lightly)

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

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?

12b.    Explain what 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. Explain if the following compiles in Java:

    interface I {
      Object f();
    }
    class A implements I {
      public String f() { return "abc"; }
    }

15b. How about the following:

    class A<T> {
      T x;
      static T y;
    }

16. 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;

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

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


18. Concerning streams in F# such as the following (infinite odd numbers):

    let mutable x = 1
    let oddstream = fun () ->
      x <- x+2
      Some(x-2)
      
    Show how to define a stream modifier `limit` that would limit the
    stream to a certain number, i.e oddstream |> limit 10, should limit
    the stream to the first 10 odds.


18b. Show how to define a stream modifier take_while that would return
     values that satisfy a predicate, and None otherwise.
     

18c. (harder) Show how to define a stream modifier `filter` that takes
     a predicate and modifies a stream to only return values that satisfy
     the predicate.


19.  Explain why in (Gnu) C the K combinator cannot be defined as follows:

    typedef int (*intfun)(int);
    intfun K(int x) {
       int inner(int y) { return x; }
       return inner;
    }