- Due: 11:00pm Thursday 12 November
- fork wellesleycs251 / cs251-funky and add bpw as admin
- Answers in
- Time estimates in
- Submission: commit and push your completed work to your Bitbucket fork.
- Relevant reading:
- All problems fall under the group collaboration policy. You may work in pairs or alone. You may discuss ideas with other groups, but your writing and code must be your own. If you work with a partner, you must work together as a pair on all parts of the problem rather than working on separate pieces.
This assignment explores evaluation orders other than familiar eager/strict evaluation.
1. Lambda Calculus Reductions [10 points]
Write your answers to the following in plain text in
lambda.txt or in
hg add the latter if you create it).
If typing answers in plain text (a
.txt file), please use the backslash character
\ in place of λ. For example, the example in part (a) below would be rewritten:
((\f. \x. f (f x)) (\y. y + 1)) 2
Feel free to use this notation in rich text too.
Show all reduction steps in two distinct reductions of the following impure lambda calculus term to normal form. Treat
+as you would expect.
((λf. λx. f (f x)) (λy. y + 1)) 2
Reduce the lambda calculus term (λx. λy. x y) (λx. x y) to the shortest form you can find by the lambda calculus reduction rules. Be careful to avoid variable capture. What happens if you do not avoid capture by renaming?
2. Stream Programming [30 points]
Recall that streams are infinite data structures where the production of “the rest” of the data structure is deferred until needed. In the following examples, we use the following types to represent streams, as defined in the
signature STREAM = sig datatype 'a scons = Scons of 'a * (unit -> 'a scons) type 'a t = unit -> 'a scons type 'a stream = 'a t (* another name for it *) ... end
We represent a stream as a thunk (a function that takes
() as its argument) that, when called, produces a pair of an element in the stream and another stream (a thunk representing the rest of the stream). We use a single-constructor datatype to allow a recursive type. You will complete the following functions in the
Write a function
stake : 'a stream -> int -> 'a list * 'a streamthat takes a stream and an int
nand returns a pair of the stream’s first
nvalues in order in a list and the rest of the stream. Build only one list, using only n cons operations, and requesting only
nelements (and no more) from the stream. In other words, do not use
rev(reverse) and do not expand the stream any farther than necessary. Given
nats, a stream of the natural numbers starting at 0:
- val take5 = stake nats 5; val take5 = ([0,1,2,3,4], fn) : int list * int stream
Write a stream
funny_numbersthat is like the stream of natural numbers
0,1,2,3,..., but every multiple of 5 is negated:
0,1,2,3,4,~5,6,7,8,9,~10,.... For example:
- val (result,_) = stake funny_numbers 12; val result = [0,1,2,3,4,~5,6,7,8,9,~10,11] : int list
Write a function
smap : ('a -> 'b) -> 'a stream -> 'b streamthat takes a mapping function
f : 'a -> 'band a stream, and creates a new result stream where every element is
fapplied to the corresponding element of the argument stream. Calling
smapshould not result in any expansion of streams.
- val (result,_) = stake (smap (fn x => x*2) funny_numbers) 12; val result = [0,2,4,6,8,~10,12,14,16,18,~20,22] : int list
Write a function
sfilter : ('a -> bool) -> 'a stream -> 'a streamthat takes a predicate function and a stream, and creates a new result stream that will contain only the elements of the original stream on which
sfiltershould not result in any expansion of streams.
- val (result,_) = stake (sfilter (fn x => x mod 2 = 0) funny_numbers) 12; val result = [0,2,4,6,8,~10,12,14,16,18,~20,22] : int list
Once you have everything else working: For full credit (i.e., to get the last 1 of several points), simplify your implementation to use exactly 1
valbinding, and 0 anonymous function definitions (
fn ... => ...). (Hint: partial application and currying.)
Write a function
scycle : 'a list -> 'b list -> ('a * 'b) streamthat takes two lists and produces a stream where each element is a pair of elements, one from each list, cycling through the elements of each list in order. Do not assume that the lists are the same length. Do assume that they are non-empty.
- val (result,_) = stake (scycle [1,2,3] ["a","b"]) 7; val result = [(1,"a"),(2,"b"),(3,"a"),(1,"b"),(2,"a"),(3,"b"),(1,"a")] : (int * string) list
There are a variety of solutions. The original stream construction work and each step of stream expansion on the resulting stream should all be O(1) (i.e., not proportional to the length of either of the lists). My solution is 5-6 lines and never uses integers or list lengths.
[OPTIONAL / 0 points] Lazy Language Integration
If you are interested in learning a bit more about lazy evaluation and language integration, see the last section of the notes on delayed evaluation and laziness, plus Chapter 15 of Programming in Standard ML and
3. Side Effects of Lazy Side Effects [10 points]
Our implementation of promises works well in the absence of side effects.
structure Promise :> PROMISE = struct datatype 'a promise = Thunk of unit -> 'a | Value of 'a type 'a t = 'a promise ref fun delay th = ref (Thunk th) fun force p = case !p of Value v => v | Thunk th => let val v = th () val _ = p := Value v in v end end
If we wish to support true “at most once” evaluation of promised thunks in the presence of side effects, we need to consider error cases. Consider the following contrived example using our promise implementation from class:
val calls = ref 0 val p = Promise.delay (fn () => let val c = !calls val _ = calls := c + 1 val _ = print ("This is call #" ^ Int.toString c ^ "\n") in 7 div c end) val x = (Promise.force p) handle e => 13 val y = x + Promise.force p + (!calls)
Mixing laziness and side effects makes it difficult to predict the order in which side effects occur. This is not such a problem in the simple example above, but a new problem does arise.
- What printed output will this code produce? Does this violate (at least the spirit of) our definition for promises?
- Improve the implementation of
Promiseto ensure that the thunk truly is called at most once. You will want to extend the implementation of the
'a Promise.tdatatype and the
Promise.forcefunction to handle the case where the thunk has been called but resulted in an exception. When promises in such state are forced again, the force operation should immediately raise the same exception that was raised the first time the promise was forced, without calling the thunk again. When your implementation is complete, it should cause this code example to bind
13and raise a divide-by-zero error instead of binding
y, and it should still work in all cases where promises worked previously. It will help to recall that exceptions are just contructors of the special datatype