Contents:

• Sample Problems
  • Streams (Delayed Evaluation)
  • Promises (Delayed Evaluation)
  • ML Types and Type Inference
  • Higher-Order Programming
  • Parallelism (Manticore)
  • Concurrent ML
  • Dynamic Dispatch and Subtyping
  • Sample Problems Elsewhere
• Sample Solutions
  • Solutions: Streams (Delayed Evaluation)
  • Solutions: Promises (Delayed Evaluation)
  • Solutions: ML Types and Type Inference
  • Solutions: Higher-Order Programming
  • Solutions: Parallelism (Manticore)
  • Solutions: Concurrent ML
  • Solutions: Dynamic Dispatch and Subtyping

Sample Problems

These sample problems focus primarily on material from the second half of the course. Many good example problems for review of midterm concepts are available elsewhere.

Streams (Delayed Evaluation)

These problems practice programming with our standard stream type, a thunk that, when called, returns a pair of an element and the remaining stream.

datatype 'a scons = Scons of 'a * (unit -> 'a scons)
type 'a stream = unit -> 'a scons

Here are some examples of streams and stream-manipulating functions:

(* A stream of ones. *)
fun ones () = Scons (1,ones)
(* A stream of the natural numbers from 0. *)
val nats =
    let fun f x = Scons (x, fn () => f (x+1))
    in fn () => f 0 end

(* Count the stream elements until f returns true on one of them. *)
fun firstindex f stream =
    let fun help stream ans =
            let val Scons (v,s) = stream ()
            in 
                if f v then ans else help s (ans + 1)
            end
    in
        help stream 0
    end
    
(* Produce a new stream where every element is one greater than in s. *)
fun sinc s =
    fn () =>
        let
            val Scons (x, s') = s ()
        in
            Scons (x + 1, sinc s')
        end

Sample problems:

1. Write an ML function n_elems : 'a stream * int -> 'alist * 'a stream that takes a stream, s and an integer, n, and returns a pair of a list holding the first n elements of s, in order, and the stream that contains all remaining elements of s after the first n. Assume n is non-negative. Hint: recursion is useful, but you do not need a helper function.

2. Fill in the blanks below such that fillin will be bound to [3,4,5,6,7].

   fun f i = fn () => Scons (i, f (i + 1))
   val fillin = __________ (n_elems (f __________, _____________))

3. Write a stream sfact : int stream that produces the factorials starting from 1: 1, 2, 6, 24, 120, …
4. Write an ML function sfold : ('a * 'b -> 'b) -> 'b -> 'a stream -> int -> 'b * 'a stream that takes 4 arguments:
   1. A combiner function.
   2. An accumlator.
   3. A stream.
   4. A number of elements, n.

   and folds the combiner starting from the initial accumulator over the first n elements of the stream in order, returning the resulting accumulator and the stream of remaining elements after the first n.

   First implement sfold using n_elems. Then implement a second version without using any lists or list functions (thus barring n_elems or any equivalent code).

Promises (Delayed Evaluation)

Recall the signature of our promise implementation:

type 'a promise
(* Make a promise for a thunk. *)
val delay : (unit -> 'a) -> 'a promise
(* If promise not yet forced, call thunk and save.
   Return saved thunk result. *)
val force : 'a promise -> 'a

Sample problems:

1. Simulate the following code to answer these questions:

   1. What is printed by the following bindings?
   2. What are the values bound to a and b?

   val r = ref 0
   fun f y = !r + (print "world\n"; y)
   val x = delay (fn () => (print "hello\n"; f 3))
   val g = fn () => (print "hi\n"; r := !r + 1; f 4)
   val a = (force x) + g ()
   val b = g () + (force x)

ML Types and Type Inference

1. For each of the following function bindings:

   1. Perform type inference manually to determine the types of the binding.
   2. Explain the steps/facts used to determine this type.
   3. Explain some things that the type can tell us about what the function does (or does not) do with its arguments to produce its result.

   fun f1 f xs =
       case xs of
           [] => []
         | x::xs' => (f x)::(f1 f xs')
   fun f2 x = f2 x
   fun f3 x = f3 (f3 x)

2. For each of the following types, describe in detail what the type means, including how its pieces are related. Do you know a familiar function with this type?

   mystery  : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
   intrigue : ('a -> bool) -> 'a list -> 'a list

3. Assuming intrigue has the type above, what is the type of the binding riddle below:

   val riddle = intrigue (fn (len, xs) => len = List.length xs)

4. Recall that ML has a built-in data type for ordering:

   datatype order = LESS | EQUAL | GREATER

   What are the types of the following fun and val bindings?

   fun mapmerge compare transform elems1 elems2 =
       case (elems1, elems2) of
           ([], []) => []
         | (e1::rest1, e2::rest2) =>
             (case compare (e1, e2) of
                  LESS => (transform e1)::(mapmerge compare transform rest1 elems2)
                | _ => (transform e2)::(mapmerge compare transform elems1 rest2))
         | (elems1, []) => map transform elems1
         | ([], elems2) => map transform elems2
   fun absorder (x, y) =
       let
           val xabs = abs x
           val yabs = abs y
       in
           if xabs < yabs then LESS
           else if xabs = yabs then EQUAL
           else GREATER
       end
   val mm1 = mapmerge absorder (fn x => "+" ^ Int.toString x) [1,2,3]
   val mm2 = mm1 [4,5]
   val mm3 = mapmerge absorder (fn x => [x])
   val mm4 = mm3 [1,2,3] [4,5]
   (* Challenge: mm5 is trickier than you should expect for exam questions. *)
   val mm5 = mapmerge absorder

Higher-Order Programming

1. Implement a function partition : ('a -> pred) -> 'a list -> 'a list * 'a list that takes a predicate and an original list of elements and pair of lists where the elements of the original list have been split such that the first list contains the elements of the original list for which the predicate returns true (in their original order) and the second list contains the elements of the original list for which the predicate returns false.

   1. Write a recursive solution without using other higher-order functions.
   2. Write a filter-based solution without explicit recursion.
   3. Write a fold-based solution without explicit recursion.
   4. Describe the value that results from the call partition (fn x => (x mod 2) = 0), its type, how it could be used, and the name of function application concept involved in making this work.

Parallelism (Manticore)

1. Consider this naive recursive function to compute the nth number of the Fibonacci sequence:

   fun fib n =
       if n <= 1
       then 1
       else
           let
               val fibn_1 = fib (n-1)
               val fibn_2 = fib (n-2)
               val sum = fibn_1 + fibn_2
           in
               print (Int.toString n ^ "->" ^ Int.toString sum ^ "\n");
               sum
           end

   Answer the following questions:

   1. How many calls to fib are made during evaluation of the expression fib 3?

   2. For each of these scenarios:

      • Starting from the original code, suppose we rewrite val fibn_1 = ... using a Manticore parallel binding: pval fibn_1 = ..., but leave the other val bindings as they are.
      • Starting from the original code, suppose we rewrite val fibn_2 = ... using a Manticore parallel binding: pval fibn_2 = ..., but leave the other val bindings as they are.
      • Using both pval fibn_1 and pval fibn_2.

      Answer these questions:

      • What is printed? Assume that each call to print succeeds atomically, so there is no interleaving of the outputs printed by single print calls.
      • Including the main task in which the initial fib 3 call is made, how many tasks may run in total during the fib 3 computation?
      • Including the main task in which the initial fib 3 call is made, what is the maximum possible number of tasks are in progress (started, but not finished) at any one point in time?
      • Is there any benefit vs. the non-parallel version? Consider: Of the in-progress tasks, how many are doing useful work vs. simply waiting for another task to complete?

Concurrent ML

1. Recall that the Concurrent ML library includes the following functions:

   (* Create a new channel. *)
   channel : unit -> 'a chan
       
   (* Spawn a new thread running the given workload function. *)
   spawn : (unit -> unit) -> thread_id
           
   (* Send the given value on the given channel. *)
   send : 'a chan * 'a -> unit
       
   (* Receive a value on the given channel. *)
   recv : 'a chan -> 'a

   Consider the following Concurrent ML code:

       val input = channel ()
       val output = channel ()
       fun produce x bound =
           if bound < x
           then send (input, NONE)
           else (
               print ("IN (" ^ Real.toString x ^ ")\n");
               send (input, SOME x);
               produce (x + 1.0) bound
           )
       fun transform f =
           case recv input of
               SOME x => (send (output, SOME (x, f x)); transform f)
             | NONE => send (output, NONE)
       fun consume () =
           case recv output of
               SOME (x,y) => (print ("OUT (" ^ Real.toString x ^ ", " ^ Real.toString y ^ ")\n");
                              consume ())
             | NONE => print "Done.\n"
       val thread1 = spawn (fn () => produce 0.0 3.5)
       val thread2 = spawn (fn () => transform (fn x => x * 2.0))
       val thread3 = spawn consume

   1. Show a printed output that could be produced by running this code.
   2. Are there any other possible printed outputs of this code? If so, write another. If not, explain why not.

   3. Draw an arrow showing how to move a single print call to another position within the same function that currently contains it, such that the following output becomes possible:

      OUT (0.0, 0.0)
      IN (0.0)
      OUT (1.0, 2.0)
      IN (1.0)
      OUT (2.0, 4.0)
      IN (2.0)
      OUT (3.0, 6.0)
      IN (3.0)
      Done.

Dynamic Dispatch and Subtyping

1. Consider the following Java code:

   class A {
       int myNumber() { return 7; }
       boolean guess(int x) { return x == myNumber(); }
   }
   class B extends A {
       int myNumber() { return 251; }
       int myOtherNumber() { return super.myNumber(); }
       boolean otherGuess(int x) { return x == myOtherNumber(); }
   }

   Write the values stored in each of the result_ variables after running the following code using the above definitions:

   A aa = new A();
   A ab = new B ();
   B bb = new B();
       
   boolean resultAA = aa.guess(251);
   boolean resultAB = ab.guess(251);
   boolean resultBB = bb.guess(251);
   
   boolean resultBBother = bb.otherGuess(251);

2. Building from the definitions above…

   class C extends B {
       boolean otherIsLargerAndNot(int y) {
           return myNumber() < myOtherNumber() && y != myOtherNumber();
       }
   }
   class D {
       A[] fragile(B[] bs) {
           if (bs[0].otherGuess(7) {
               bs[0] = new B();
           }
           return bs;
       }
   }

   Tasks:

   1. Fill the blanks such that the following code type-checks, but throws an ArrayStoreException when run:

      ____[] array = new ____[1];
      array[0] = new ____();
      new D().fragile(array);

   2. Explain where in the accumulated code the ArrayStoreException is thrown and why. Fill in the blank in the following code so that it would type-check against your example above, but fail at run time if not for the ArrayStoreException raised above.

      array[0]._______________________(4);

Sample Problems Elsewhere

The UW CSE 341 exams have some relevant problems both for earlier topics (midterms) for some of our more recent topics (finals).

Midterms

The midterm exams from that course also have good problems for reviewing some of the older concepts that are coming back from our midterm exam for mastery grading on our final exam:

• Programming in ML, especially with higher-order functions
• ML signatures/structures
• Scope and evaluation semantics
• ML types

Finals

The final exams from that course have some good problems for some of our more recent topics, but not all problems are relevant.

Ignore problems that:

• Use Ruby
• Use Racket mutation (mcons/set-mcar!/set-mcdr!/set!), macros, or struct.
• Consider a “MUPL” interpreter.

There are many relevant problems on:

• Subtyping: The subtyping problems from these exams (usually around the last problem in those exams) are useful practice. They use the little “ML with mutable records and subtyping” language we saw in class. The ideas are generally relevant to subtyping issues we considered in Java as well.
• Streams / Delayed Evaluation: There are several good stream problems in these exams, but they are in Racket instead of ML. Seeing through the differences takes some minor translation work, but is pretty straightforward. We’ll port a couple of these problems to ML above.
• Static/Dynamic Typing: problems on type systems in this exam are good practice. Some of them focus on the soundness and completeness terms which we have defined (but have emphasized less in homework).

Sample Solutions

Solutions: Streams (Delayed Evaluation)

fun n_elems (s, n) =
    if n = 0
    then ([], s)
    else let
             val Scons (first_elem, s') = s()
             val (rest_elems, rest_stream) = n_elems (s', n-1)
         in
             (first_elem::rest_elems, rest_stream)
         end

fun f i - fn () => Scons (i, f (i + 1))
val fillin = #1 (n_elems (f 7, 4))

val sfact =
    let fun loop i fact = Scons (fact, fn () => loop (i+1) (i*fact))
    in fn () => loop 1 1 end
          
fun sfold1 combine acc stream n =
    let val (elems, rest) = n_elems (stream, n)
    in  (foldl combine acc elems, rest) end
    
fun sfold2 combine acc stream n =
    if n = 0
    then (acc, stream)
    else let val Scons (elem, rest) = stream ()
         in sfold combine (combine (elem, acc)) rest (n-1)

Solutions: Promises (Delayed Evaluation)

1. Printed output:

   hello
   world
   hi
   world
   hi
   world
   

   Bindings:

   val a = 8
   val b = 9

Solutions: ML Types and Type Inference

1. Type inference and explanations.

   Function:

   fun f1 f xs =
       case xs of
           [] => []
         | x::xs' => (f x)::(f1 f xs')

   • Type: f1 : ('a -> 'b) -> 'a list -> 'b list
   • Detailed description of constraints involved in inference:
     • xs is matched against a list pattern, so xs : 'a list
     • x appears in the element position and xs' appears in the list position of a cons pattern matched against xs, so:
       • x : 'a (the element type of the xs list type) and
       • xs' : 'a list (the same list type as xs).
     • f is applied to x, so f has a function type and its argument type must match the type of x. f : 'a -> 'b.
     • f1 is applied to two curried arguments f : 'a -> 'b and xs : 'a list, which agrees with the arguments types discovered for f and xs, so f1 has a function type ('a -> 'b) -> 'a list -> ____.
     • The body of f1 has two bracnhes:
       • one is the empty list, meaning it has some list type ____ list.
       • the other is a cons of the result of f onto the result of f1, so it also has a list type, and the element type must match the result type of f, that is b.

       So f1 : ('a -> 'b) -> 'a list -> 'b list.

   • Some things the type tells us about behavior:
     • The inferred type shows that the first argument is a function that is applied to elements of the second argument (list), and whose results appear as elements of the overall result list.
     • Since the type variables 'a remain in the final inferred type and were note replaced with concrete types, f1 cannot perform any operations on the elements of the argument list or result list itself, except via the first argument function.
     • We also know by the independence of 'a list and 'b list that f1 never mixes elements of these lists in the same context.

   Function:

   fun f2 x = f2 x

   • Type: f2 : 'a -> 'b
   • Inference:
     • f2 is applied to the argument of f2.
     • f2’s result is used as f2’s result.
     • There are no other constraints, so the argument and result types are completely unconstrained.
   • Some things the type tells us about behavior:
     • f2 never applied any operation to its argument other than making a recursive call, otherwise the argument type would be constrained further.
     • The result returned is completely unrelated to the argument, otherwise, their types would be related.
     • 'a -> 'b means we can call this function on any type of argument and use its result as any type we wish, and it’s just fine!
     • How are these things possible? This function is infinitely recursive. Every time it does return (i.e., never), the value it returns can be used as any type one pleases.

   Function:

   fun f3 x = f3 (f3 x)

   • Type: f3 : 'a -> 'a
   • Inference:
     • f3 is applied to the argument of f3.
     • f3 is applied to the result of f3, so its argument and result types must match.
     • There are no other constraints, so the argument/result type is unconstrained.
   • Some things the type tells us about behavior:
     • f2 never applied any operation to its argument other than making a recursive call, otherwise the argument type would be constrained further.
     • Whenever this function returns a value (it never does – infinite recursion), it can only possibly be the argument. When it returns a value (never), it’s acting a glorified identity function.
     • A type can look like it indicates a certain behavior (identify function has type 'a -> 'a), but may be infinitely recursive.

2. For each of the following types, describe in detail what the type means, including how its pieces are related. Do you know a familiar function with this type?

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

   • mystery applies its first argument to pairs of an element from its third argument (list) and the value of its second argument.
   • mystery and its first argument both also return values of the same type as mystery’s second argument.
   • This is a curried fold or other similar function.

   intrigue : ('a -> bool) -> 'a list -> 'a list

   • intrigue applies its first argument (a predicate function) to an element from its second argument (list).
   • Any elements of the result list can only possibly come from the argument list, since the 'a list type means the implementation of intrigue does not know anything about the list elements.
   • This is a curried filter or other similar function.

3. Note: the 'a in the type of riddle is independent of the 'a in the type of intrigue.

   riddle : (int * 'a list) -> (int * 'a list)

4. Types:

   val mapmerge : ('a * 'a -> order) -> ('a -> 'b) -> 'a list -> 'a list -> 'b list
   val absorder : int * int -> order
   val mm1 : int list -> string list
   val mm2 : string list
   val mm3 : int list -> int list -> int list list
   val mm4 : int list list

   The mm5 binding has a type that is trickier than what you should expect on this exam.

   While you might expect the type:

   val mm5 : (int -> 'a) -> int list -> int list -> 'a list

   This partial application, resulting in a value that should have a polymorphic type using at least one type variable, is subject to the value restriction. The ML compiler would report:

   Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)
   

   and give the (unusable) type:

   val mm5 : (int -> ?.X1) -> int list -> int list -> ?.X1 list

Solutions: Higher-Order Programming

1. Partition

   fun partition_rec pred xs =
       case xs of
           [] => ([], [])
         | x::xs' => let (* Calls pred once on each element in order. *)
                         val yes = pred x
                         val (yeses, nos) = partition_rec pred xs'
                     in
                         if yes then (x::yeses, nos) else (yeses, x::nos)
                     end
   
   (* Calls pred twice on every element. *)
   fun partition_filter pred xs =
       (filter pred xs, filter (fn x => not (pred x)) xs)
           
   (* Calls pred once on each element in order. *)
   fun partition_foldr pred xs =
       foldr (fn (x, (yes, no)) => if pred x then (x::yes, no) else (yes, x::no)) ([], []) xs
   
   (* Defined via partial application: *)
   fun partition_foldr_partial pred =
       foldr (fn (x, (yes, no)) => if pred x then (x::yes, no) else (yes, x::no)) ([], [])

Solutions: Parallelism (Manticore)

1. Answers:

   1. Evaluation of fib 3 involves 5 calls to fib:

               fib 3
              /     \
          fib 2     fib 1
         /     \
      fib 1   fib 0
      

   2. Using only pval fibn_1:

      • Prints one of several interleavings, such as:

        1->1
        0->1
        2->2
        1->1
        3->3
        

        or

        1->1
        1->1
        0->1
        2->2
        3->3
        

        Lines of output that are printed by a caller and callee (or an arbitrarily long call chain) happen in order. Otherwise, any other pairs of prints that occur in two different tasks can occur in either order.

      • Total tasks: 3
      • Most tasks in progress at one time: 3
      • Benefit vs non-parallel: yes. With idealized computational resources, this computation would run time O($n$) for fib n. More simply: all in-progress tasks can be doing useful work at the same time.

      Using only pval fibn_2:

      • Prints only one possibility:

        1->1
        0->1
        2->2
        1->1
        3->3
        

      • Total tasks: 3
      • Most tasks in progress at one time: 3
      • Benefit vs non-parallel: no. With idealized computational resources, this computation would still run in time O($2^n$) for fib n. More simply: all but one in-progress tasks are waiting for another task to complete. Critically: val fibn_1 = ... is evaluated to completion before starting evaluation of pval fibn_2. Evaluation of pval fibn_2 can run in parallel to computations that follow it, but the immediate next computation is val sum = fibn_1 + fibn_2, which depends on fibn_2, meaning it must wait for completion of fibn_2. The parallelism opportunity introduced by this pval is thus useless.

      Using both pval fibn_1 and pval fibn_2:

      • Prints: same as first scenario.
      • Total tasks: 5
      • Most tasks in progress at one time: 3
      • Benefit vs non-parallel: yes, as with the first scenario. However, note that, as with the scenario, there is no useful parallelism exposed by pval fibn_2, since evaluation of the sum binding must wait for it.

Solutions: Concurrent ML

1. Pipeline

   1. Output:

      IN (0.0)
      OUT (0.0, 0.0)
      IN (1.0)
      OUT (1.0, 2.0)
      IN (2.0)
      OUT (2.0, 4.0)
      IN (3.0)
      OUT (3.0, 6.0)
      Done.

   2. Another output:

      IN (0.0)
      IN (1.0)
      OUT (0.0, 0.0)
      IN (2.0)
      OUT (1.0, 2.0)
      IN (3.0)
      OUT (2.0, 4.0)
      OUT (3.0, 6.0)
      Done.

      Recall that send and recv are synchronous, meaning, they must await a coordinating recv or send before completing. In this pipeline:

      • the sends in thread1’s produce happen synchronously with the recvs in thread2’s transform;
      • each recv in thread2’s transform happens before the corresponding send in thread2’s transform; and
      • the sends in thread2’s transform happen synchronously with the recvs in thread3’s consume.

      Reasoning about when the IN and OUT lines can be printed relative to the above events, we can see that printing of IN (x+1.0) and OUT(x, ...) lines is concurrent, thus those pairs of lines could happen in either order, depending on thread scheduling. But this is the limit; it is not possible to see IN (x) before OUT (x-2.0, ...) or after OUT (x, ...).

      It turns out you may not be able to get the standard CML runtime implementation to produce this output from this code, due to how it schedules threads, but the general execution model we have defined allows it.

   3. The “backwards” output is possible by rewriting produce like this:

      fun produce x bound =
          if bound < x
          then send (input, NONE)
          else (
              (* OLD: print ("IN (" ^ Real.toString x ^ ")\n"); *)
              send (input, SOME x);
              (* NEW: *) print ("IN (" ^ Real.toString x ^ ")\n"); 
              produce (x + 1.0) bound
          )

      Now it’s possible for thread2’s transform to recv thread1’s message, then send it, allowing it to thread3 to recv it and print it, all before thread1 takes its next step (printing) after its send.

Solutions: Dynamic Dispatch and Subtyping

1. Results under dynamic dispatch:

   resultAA = false
   resultAB = true
   resultBB = true
   resultBBother = false

2. One way to break it:

   C[] array = new C[1];
   array[0] = new C();
   new D().fragile(array);
   array[0].otherIsLargerAndNot(4);

   Java’s covariant array subtyping rule allows passing a value of type C[] where B[] is expected as it allows C[] <: B[] because C <: B. Unfortunately, this allows fragile to store a B into an array of type C[] – that’s where the ArrayStoreException is raised. Otherwise, later operations on array, which the type system says has type C[] can fail where elements of array are not actually of type C.