CSE 428: Programming Language Concepts
Midterm #2 Solution

1. 1. fun flip(f,x,y) = f(y,x);
      ('a * 'b -> 'c) * 'b * 'a -> 'c
   2. fun flop(f,g,z) = f(g(z),z);
      ('a * 'b -> 'c) * ('b -> 'a) * 'b -> 'c

   3. fun reduce(f,a,nil) = a
         |reduce(f,a, (x::xs)) = f(x,reduce(f,a,xs));

      
      ('a * 'b -> 'b) * 'b * ('a list) -> 'b

   4. fun altnfold(f,g,0,x) = x + 0.0
         |altnfold(f,g,n,x) = f(g(altnfold(f,g,n-1,x)));

      
      ('a -> real) * (real -> 'a) * int * real -> real

2. 1. map(inc, [2,4,6]);

      [3,5,7]

   2. nfold(inc,5) 4;

      9

   3. filter(even, map(inc, [1,2,3,4]));

      [2,4]

   4. map(nfold(inc,2), [1,2,3,4]);

      [3,4,5,6]

3. 1. fun A x = false;

      Defines the empty set.

   2. fun B (f,g) = fn x => f(x) orelse g(x);

      Defines the union of sets f and g

   3. fun B (f,g) = fn x => f(x) andalso g(x);

      Defines the intersection of sets f and g

   4. fun D (x,f) = fn y => (x=y) orelse f(y);

      Defines the union of {x} and f

   5. fun E (f,g) = fn y => f(y) andalso (not (g(y)));

      Defines the difference (subtraction) of sets f-g

4. local
     fun f (dbIntConst(x),D) = true
        |f (## k, D) = (k<=D)
        |f (dbOp(e1,_,e2),D) = f(e1,D) andalso f(e2,D)
        |f (dbLet(e1,e2),D) = f(e1,D) andalso f(e2,D+1)
   in
     fun closed e = f(e, 0)
   end;
   

   For case two, either less than or less than or equal to was accepted. The difference comes from whether deBruijn indices start at 0 or 1.

5. 1. Incorrect, because the methods are unsynchronized, so there is the problem of interference (for instance two deposits could interfere so that one is lost)
   2. Incorrect: two account holders could be waiting for the balance to become >100. When this happen, both will make a withdrawal and the balance will go negative
   3. Correct. The fact that we use notify() here is not harmful because there is only one kind of condition on which the accountholdes might be suspended. Thus any supended process is "the correct one" to be woken up by a notification
   4. Correct
   5. Incorrect. Each account holder is a different object hence does not make sense to synchronize one of their methods (they would be associated to different locks and there would not be any mutual exclusion)