Sample Code for this Chapter

As we saw earlier, a datatype declaration is used to introduce a new type whose elements are generated by a given set of value constructors.  The value constructors may be used to create values of the type (by applying them to values of suitable type), and to decompose values of the type (by using them in patterns).  Value constructors, like all other functions in ML, are evaluated eagerly, meaning that the arguments to the constructor are evaluated before the constructor is applied.  For example, to attach an element to the front of a list, we first determine the value of the element and the value of the list before building a new list with that element as head and that list as tail.  This policy is based on the intuitively appealing idea of a list as a kind of value that we manipulate by using the list constructors as functions and as patterns.

An alternative is to view a data structure as being perpetually in the process of creation, rather than as a result of a completed computation.  According to this view a list may be thought of as a "partial", or "suspended", computation that, when provoked, computes just far enough to determine whether the end of the list has been reached, or , if not, to produce the next element of the list together with a suspended computation to compute the remainder of the list.  An added benefit of this viewpoint is that it is then possible to define infinite lists (better known as streams) that continually generate the next element, without ever reaching the end of the list.   This view of data structures as being in the process of creation conflicts with the eager evaluation strategy just described since under the eager approach all expressions are fully evaluated before they are used, whereas we would like to evaluate them only as much as absolutely necessary to allow the overall computation to proceed.  This is called, appropriately enough, lazy evaluation.

Standard ML does not support lazy evaluation as a primitive notion; it can be implemented "by hand" using methods that are described later in these notes.   However, Standard ML of New Jersey (from version 110.5) does provide for lazy evaluation through an extension of the datatype and val rec declaration forms.  We will illustrate these mechanisms by defining a type 'a stream of streams of values of type 'a.  Based on the discussion above you might imagine that a stream is just an infinite list, but it is important to keep the two concepts separate.  Lists are eager types whose values are generated by finitely-many applications of :: to the empty list, nil.   Streams are lazy types whose values are determined by suspended computations that generate the next element of the stream (and another computation to generate the remainder).  The two concepts are, and ought to be kept separate since they serve different purposes and require different modes of reasoning.

First off, the lazy evaluation mechanisms of SML/NJ must be enabled by evaluating the following declarations:

Compiler.Control.Lazy.enabled := true;
open Lazy;

We may then define a type of streams as follows:

datatype lazy 'a stream = Cons of 'a * 'a stream

The keyword "lazy" indicates that values of type 'a stream are suspended computations that, when evaluated, yield a value of the form Cons (x, c), where x is a value of type 'a, and c is another value of type 'a stream, i.e., another computation of such a value.

How might a value of type 'a stream be created?  Since the description of values of this type we've just given is clearly "circular", we must employ a recursive value binding to create one.  Here's a definition of the infinite stream of 1's as a value of type int stream:

val rec lazy ones = Cons (1, ones)

The keyword "lazy" indicates that we are defining a value of a lazy type, which means that it must be kept as an incomplete computation, rather than fully evaluated at the time the binding is created.  What computation is bound to ones?   It's the computation that, when evaluated, yields Cons (1, ones), a stream whose head element is 1 and whose tail is the very same computation again.  Thus if we evaluate the tail of ones we will, once again, obtain the same value, and so on ad infinitum.

How can we take apart values of stream type?  By pattern matching, of course!   For example, we may evaluate the binding

val Cons (h, t) = ones

to extract the head and tail of the stream ones.  To perform the pattern match we must first force the evaluation of ones to obtain Cons (1, ones), then pattern match to bind h to 1 and t to ones.  Had the pattern been "deeper", further evaluation would be forced, as in the following binding:

val Cons (h, (Cons (h', t')) = ones

To evaluate this binding, we evaluate ones to Cons (1, ones), binding h to 1 in the process, then evaluate ones again to Cons (1, ones), binding h' to 1 and t' to ones.   The general rule is pattern matching forces evaluation of partial computations up to the depth required by the pattern.

We may define functions to extract the head and tail of a stream as follows:

fun shd (Cons (h, _)) = h

fun stl (Cons (_, s)) = s

Both of these functions force the computation of the stream when applied so that they may extract the head and tail elements.  In the case of the head element it is clear that the stream computation must be forced in order to determine its value, but a moment's thought reveals that it is not strictly necessary to force the computation of a stream to extract it's tail!  Why is that?  Since the tail of a stream is itself a stream, it may be thought of as a suspended computation.  But which suspended computation is it?  According to the definition just given, it is the suspended stream computation extracted from the second component of the value of the given stream.  But another definition is possible: it is the suspended computation that, when forced, yields the second component of the result of forcing the stream computation.   Here's a definition:

fun lazy lstl (Cons (_, s)) = s

Here the keyword "lazy" indicates that an application of lstl to a stream does not immediately perform pattern matching (hence forcing the argument), but rather merely sets up a delayed stream computation that, when forced, forces the argument and extracts the tail of the stream.

The behavior of the two forms of tail function can be distinguished as follows:

val rec lazy s = (print "."; Cons (1, s));
val s' = stl s;                               (* prints "." *)
val Cons _ = s';                              (* silent *)

val rec lazy s = (print "."; Cons (1, s));
val s'' = lstl s;                             (* silent *)
val Cons _ = s'';                             (* prints "." *)

Notice that since stl immediately forces it's argument, the "." is printed when it is applied, whereas it is printed only when the result of applying lstl to an argument is itself forced by another pattern match.

It is extremely important that you understand the difference between these two definitions!  To check your understanding, let's define a function smap that applies a function to every element of a stream, yielding another stream.  The type of smap should be ('a -> 'b) -> 'a stream -> 'b stream.   The thing to keep in mind is that the application of smap to a function and a stream should set up (but not compute) another stream that, when forced, forces the argument stream to obtain the head element, applies the given function to it, and yields this as the head of the result.  Here's the code:

fun smap f =
        fun lazy loop (Cons (x, s)) = Cons (f x, loop s)

Notice that we have "staged" the computation so that the partial application of smap to a function yields a function that loops over a given stream, applying the given function to each element.  This loop is a "lazy" function to ensure that an application of loop to a stream merely sets up a stream computation, rather than forcing the evaluation of its argument at the time that the loop is applied.  This ensures that we are as lazy as possible about evaluating streams.   Had we dropped the keyword "lazy" from the definition of the loop, then an application of smap to a function and a stream would immediately force the computation of the head element of the stream, rather than merely set up a future computation of the same result.  This would be a bit over-eager in the case that the result of applying smap were never used in a subsequent computation.  Which solution is "right"?  It all depends on what you're doing, but as a rule of thumb, it is best to be as lazy as possible when dealing with lazy types.

To illustrate the use of smap, here's a definition of the infinite stream of natural numbers:

val one_plus = smap (fn n => n+1)
val rec lazy nats = Cons (0, one_plus nats)

It is worthwhile contemplating how and why this definition works.

Now let's define a function sfilter of type ('a -> bool) -> 'a stream -> 'a stream that filters out all elements of a stream that do not satisfy a given predicate.  Here's the code:

fun sfilter pred =
        fun lazy loop (Cons (x, s)) =
            if pred x then Cons (x, loop s) else loop s

We can use filter to define a function sieve that, when applied to a stream of numbers, retains only those numbers that are not divisible by a preceding number in the stream:

fun m mod n = m - n * (m div n)
fun divides m n = n mod m = 0
fun lazy sieve (Cons (x, s)) = Cons (x, sfilter (not o (divides x)) s)

We may now define the infinite stream of primes by applying sieve to the natural numbers greater than or equal to 2:

val nats2 = stl (stl nats)          (* might as well be eager *)
val primes = sieve nats2

To inspect the values of a stream it is often useful to use the following function that "takes" n>=0 elements from a stream and builds a list of those n values:

fun take 0 _ = nil
  | take n (Cons (x, s)) = x :: take (n-1) s

In addition to supporting demand-driven computation the lazy evaluation primitives of SML/NJ also support memoization of the results of a computation.  The idea is that a delayed computation is performed at most once.  If it is never forced by pattern matching, then the delayed computation is never performed at all.   If it is ever forced, then the result of forcing that computation is stored in a memo pad so that if it is forced again, the previous result is returned immediately,without repeating the work that was done previously.  Here's an example to illustrate the effects of memoization:

val rec lazy s = Cons ((print "."; 1), s)
val Cons (h, _) = s;                       (* prints ".", binds h to 1 *)
val Cons (h, _) = s;                       (* silent, binds h to 1 *)

Replace "print ".";1" by a time-consuming operation yielding 1 as result, and you will see that the second time we force s the result is returned instantly, taking advantage of the effort expended on the time-consuming operation induced by the first force of s.

Sample Code for this Chapter