code Closures as data structures, delayed evaluation and laziness with promises and streams

Contents

Tasks

1. Representing Maps by Functions (map.sml, 20 points)

MAP and FUNMAP signatures are provided and documented in map.sig. Maps are data structures that represent a mapping keys to values. You previously implemented an Env structure that implements maps as association lists, with some additional operations. In this task you will implement a map data structure using only function closures.

  1. Implement a FunMap structure in map.sml, ascribing the FUNMAP signature, which also supports defining a map from a given function. Your implement should represent maps purely as function closures. The ideas to implement these are quite similar to those for the SET ADTs we (partly) implemented in class. A map-representing function returns an option when called on a key: NONE if the given key is unbound in the map represented by that function, SOME v if the given key is bound to value v in the map represented by that function. Implement all bindings described in FUNMAP.

    Test your implementation to make sure it functions as expected on a range of cases. Some starter ideas are included in test-map.sml:

    val m0 = FunMap.empty;
val lookup_x_m0 = FunMap.lookup "x" m0;
val m1 = FunMap.bind ("x", 7) m0;
val lookup_x_m1 = FunMap.lookup "x" m1;
val m2 = FunMap.bind ("y", 8) m1;
val lookup_x_m2 = FunMap.lookup "x" m2;
val lookup_y_m2 = FunMap.lookup "y" m2;
val lookup_x_unbind_x_m2 = FunMap.lookup "x" (FunMap.unbind "x" m2);
val lookup_73_halves = FunMap.lookup 73 (FunMap.define (fn n => SOME (n div 2)));
val lookup_x_make_shadow = FunMap.lookup "x" (FunMap.make [("y", 4),("x", 5),("x",2)];

  2. One of the bindings in the MAP signature could be implemented externally by clients without knowing the concrete type of maps.

    • Which one? Re-implement it as a new function binding (with the same name and type) outside of the FunMap structure.

    • Does implementing this function as a primitive operation within the abstract data type (i.e., within the structure) confer any advantages versus writing a generic version outside? (Assume the external version is also provided by the library: in other words, “saving clients the trouble of writing it” is irrelevant to this question.)

  3. Consider the trade-offs between list representations, function representations, and at least one other (hypothetical) representation for sets and for maps. Examples of other representations include hash tables, heaps, tries, etc. You do not need to implement your extra representation. Answer the following questions in comments in map.sml:

    1. What distinguishes function-representable but non-list-representable sets and maps from list-representable sets and maps? Give examples and explain the fundamental distinction that separates sets/maps that can be represented with, e.g., lists and those that cannot (but can be represented by functions).
    2. What is the fundamental operation over collections that is not possible to implement for function representations of general sets and maps? (Operations like toString and toList are impossible because of this limitation.)
    3. Which representation (lists or functions) is more space-efficient for use cases where insertion of duplicate set elements or binding of duplicate map keys (shadowing) is common? How much does your answer depend on implementation choices vs. fundamental limits of the representation?

  4. For the last couple points on this problem, convert map.sml to include zero uses of the fn ... => .. syntax. Use exactly one fun binding per binding in FUNMAP. (Hint: exploit currying and partial application.)

2. Stream Programming (stream.sml, 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 this 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 stream.sml (mostly 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

    Define funny_numbers outside of the Stream structure.

  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.

3. Side Effects of Lazy Side Effects (side-effects.sml, 15 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.

Submission

Submit: The course staff will collect your work directly from your hosted repository. To submit your work:

  1. Make sure you have committed your latest changes.

    $ git add ...
$ git commit ...

  2. Run the command cs251 sign to sign your work and respond to any assignment survey questions.

    $ cs251 sign

  3. Push your signature and your latest local commits to the hosted repository.

    $ git push

Confirm: All local changes have been submitted if the output of git status shows both:

  • Your branch is up to date with 'origin/master', meaning all local commits have been pushed
  • nothing to commit, meaning all local changes have been committed

Resubmit: If you realize you need to change something later, just repeat this process.