Final Exam Review Problems
Contents:
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:
- 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 firstn
elements ofs
, in order, and the stream that contains all remaining elements ofs
after the firstn
. Assumen
is non-negative. Hint: recursion is useful, but you do not need a helper function. -
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 __________, _____________))
- Write a stream
sfact : int stream
that produces the factorials starting from 1: 1, 2, 6, 24, 120, … - Write an ML function
sfold : ('a * 'b -> 'b) -> 'b -> 'a stream -> int -> 'b * 'a stream
that takes 4 arguments:- A combiner function.
- An accumlator.
- A stream.
- 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 firstn
.First implement
sfold
usingn_elems
. Then implement a second version without using any lists or list functions (thus barringn_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:
-
Simulate the following code to answer these questions:
- What is printed by the following bindings?
- What are the values bound to
a
andb
?
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
-
For each of the following function bindings:
- Perform type inference manually to determine the types of the binding.
- Explain the steps/facts used to determine this type.
- 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)
-
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
-
Assuming
intrigue
has the type above, what is the type of the bindingriddle
below:val riddle = intrigue (fn (len, xs) => len = List.length xs)
-
Recall that ML has a built-in data type for ordering:
datatype order = LESS | EQUAL | GREATER
What are the types of the following
fun
andval
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
-
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.- Write a recursive solution without using other higher-order functions.
- Write a
filter
-based solution without explicit recursion. - Write a
fold
-based solution without explicit recursion. - 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)
-
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:
- How many calls to
fib
are made during evaluation of the expressionfib 3
? -
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 otherval
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 otherval
bindings as they are. - Using both
pval fibn_1
andpval 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 singleprint
calls. - Including the main task in which the initial
fib 3
call is made, how many tasks may run in total during thefib 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?
- Starting from the original code, suppose we rewrite
- How many calls to
Concurrent ML
-
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
- Show a printed output that could be produced by running this code.
- Are there any other possible printed outputs of this code? If so, write another. If not, explain why not.
-
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
-
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);
-
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:
-
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);
-
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 theArrayStoreException
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, orstruct
. - 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)
-
Printed output:
hello world hi world hi world
Bindings:
val a = 8 val b = 9
Solutions: ML Types and Type Inference
-
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, soxs : 'a list
x
appears in the element position andxs'
appears in the list position of a cons pattern matched againstxs
, so:x : 'a
(the element type of thexs
list type) andxs' : 'a list
(the same list type asxs
).
f
is applied tox
, sof
has a function type and its argument type must match the type ofx
.f : 'a -> 'b
.f1
is applied to two curried argumentsf : 'a -> 'b
andxs : 'a list
, which agrees with the arguments types discovered forf
andxs
, sof1
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 off1
, so it also has a list type, and the element type must match the result type off
, that isb
.
So
f1 : ('a -> 'b) -> 'a list -> 'b list
. - one is the empty list, meaning it has some list type
- 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
thatf1
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 off2
.f2
’s result is used asf2
’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 off3
.f3
is applied to the result off3
, 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.
- Type:
-
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 asmystery
’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 ofintrigue
does not know anything about the list elements. - This is a curried
filter
or other similar function.
-
Note: the
'a
in the type ofriddle
is independent of the'a
in the type ofintrigue
.riddle : (int * 'a list) -> (int * 'a list)
-
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
-
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)
-
Answers:
-
Evaluation of
fib 3
involves 5 calls tofib
:fib 3 / \ fib 2 fib 1 / \ fib 1 fib 0
-
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 ofpval fibn_2
. Evaluation ofpval fibn_2
can run in parallel to computations that follow it, but the immediate next computation isval sum = fibn_1 + fibn_2
, which depends onfibn_2
, meaning it must wait for completion offibn_2
. The parallelism opportunity introduced by thispval
is thus useless.
Using both
pval fibn_1
andpval 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 thesum
binding must wait for it.
-
-
Solutions: Concurrent ML
-
Pipeline
-
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.
-
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
andrecv
are synchronous, meaning, they must await a coordinatingrecv
orsend
before completing. In this pipeline:- the
send
s inthread1
’sproduce
happen synchronously with therecv
s inthread2
’stransform
; - each
recv
inthread2
’stransform
happens before the correspondingsend
inthread2
’stransform
; and - the
send
s inthread2
’stransform
happen synchronously with therecv
s inthread3
’sconsume.
Reasoning about when the
IN
andOUT
lines can be printed relative to the above events, we can see that printing ofIN (x+1.0)
andOUT(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 seeIN (x)
beforeOUT (x-2.0, ...)
or afterOUT (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.
- the
-
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
’stransform
torecv
thread1
’s message, thensend
it, allowing it tothread3
torecv
it and print it, all beforethread1
takes its next step (printing) after itssend
.
-
Solutions: Dynamic Dispatch and Subtyping
-
Results under dynamic dispatch:
resultAA = false resultAB = true resultBB = true resultBBother = false
-
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[]
whereB[]
is expected as it allowsC[] <: B[]
becauseC <: B
. Unfortunately, this allowsfragile
to store aB
into an array of typeC[]
– that’s where theArrayStoreException
is raised. Otherwise, later operations onarray
, which the type system says has typeC[]
can fail where elements ofarray
are not actually of typeC
.