Funky Functions
 Due: 11:00pm Thursday 12 November
 Files:
 fork wellesleycs251 / cs251funky and add bpw as admin
 Answers in
lambda.txt
orlambda.pdf
(hg add
it),stream.sml
, andsideeffects.sml
.  Time estimates in
time.txt
 Submission: commit and push your completed work to your Bitbucket fork.
 Relevant reading:
 SML References
 especially Delayed Evaluation and Laziness
 Robert Harper, Programming in Standard ML (PDF book)
 Tools:
 Collaboration:
 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 lambda.pdf
(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 STREAM
signature:
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 singleconstructor datatype to allow a recursive type. You will complete the following functions in the Stream
structure.

Write a function
stake : 'a stream > int > 'a list * 'a stream
that takes a stream and an intn
and returns a pair of the stream’s firstn
values in order in a list and the rest of the stream. Build only one list, using only n cons operations, and requesting onlyn
elements (and no more) from the stream. In other words, do not use@
(append) orrev
(reverse) and do not expand the stream any farther than necessary. Givennats
, 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_numbers
that is like the stream of natural numbers0,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 stream
that takes a mapping functionf : 'a > 'b
and a stream, and creates a new result stream where every element isf
applied to the corresponding element of the argument stream. Callingsmap
should 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 stream
that takes a predicate function and a stream, and creates a new result stream that will contain only the elements of the original stream on whichf
returnstrue
. Callingsfilter
should 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
fun
binding, 1val
binding, and 0 anonymous function definitions (fn ... => ...
). (Hint: partial application and currying.) 
Write a function
scycle : 'a list > 'b list > ('a * 'b) stream
that 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 nonempty. 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 56 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
lazy.sml
.
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
Promise
to ensure that the thunk truly is called at most once. You will want to extend the implementation of the'a Promise.t
datatype and thePromise.force
function 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 bindx
to13
and raise a dividebyzero error instead of bindingy
, 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 datatypeexn
.