• Due: 11:00pm Thursday 12 November
  • Files:
    • fork wellesleycs251 / cs251-funky and add bpw as admin
    • Answers in lambda.txt or lambda.pdf (hg add it), stream.sml, and side-effects.sml.
    • Time estimates in time.txt
  • Submission: commit and push your completed work to your Bitbucket fork.
  • Relevant reading:
  • 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.

  1. 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

  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 single-constructor datatype to allow a recursive type. You will complete the following functions in the Stream structure.

  1. Write a function stake : 'a stream -> int -> 'a list * 'a stream that takes a stream and an int n and returns a pair of the stream’s first n values in order in a list and the rest of the stream. Build only one list, using only n cons operations, and requesting only n elements (and no more) from the stream. In other words, do not use @ (append) or 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

  2. Write a stream funny_numbers that 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

  3. Write a function smap : ('a -> 'b) -> 'a stream -> 'b stream that takes a mapping function f : 'a -> 'b and a stream, and creates a new result stream where every element is f applied to the corresponding element of the argument stream. Calling smap 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

  4. 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 which f returns true. Calling sfilter 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, 1 val binding, and 0 anonymous function definitions (fn ... => ...). (Hint: partial application and currying.)

  5. 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 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.

  6. [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.

  1. What printed output will this code produce? Does this violate (at least the spirit of) our definition for promises?
  2. 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 the Promise.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 bind x to 13 and 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 exn.