Module System

Lazy evaluation

Standard ML doesn’t have built-in support for lazy evaluation. Some implementations, notably SML/NJ, have nonstandard lazy evaluation primitives, but programs that use those primitives won’t be portable. Lazy suspensions can also be implemented in a portable manner, using Standard ML’s module system.

First we define an interface, or signature, for manipulating lazy suspensions:

signature LAZY =
sig
  type 'a lazy
  
  val pure : 'a -> 'a lazy
  val delay : ('a -> 'b) -> 'a -> 'b lazy
  val force : 'a lazy -> 'a
  
  exception Diverge
  
  val fix : ('a lazy -> 'a) -> 'a
end

This signature indicates that:

The type constructor of lazy suspensions is abstract - its internal representation is hidden from (and irrelevant to) users.
There are two ways to create a suspension: by directly wrapping its final result, and by delaying a function application.
The only thing we can do with a suspension is force it. When a delayed suspension is forced for the first time, its result is memoized, so that the next time the result won’t have to be recomputed.
We can create self-referential values, where the self-reference goes through a suspension. This way we can create, for example, a logically infinite stream containing the same repeated element, as in the following Haskell snippet:

-- Haskell, not Standard ML!
xs :: [Int]
xs = 1 : xs

After defining the interface, we have to provide an actual implementation, also known as module or structure:

structure Lazy :> LAZY =
struct
  datatype 'a state
    = Pure of 'a
    | Except of exn
    | Delay of unit -> 'a
  
  type 'a lazy = 'a state ref
  
  fun pure x = ref (Pure x)
  fun delay f x = ref (Delay (fn _ => f x))
  fun compute f = Pure (f ()) handle e => Except e
  fun force r =
    case !r of
        Pure x => x
      | Except e => raise e
      | Delay f => (r := compute f; force r)
  
  exception Diverge
  
  fun fix f =
    let val r = ref (Except Diverge)
    in r := compute (fn _ => f r); force r end
end

This structure indicates that a suspension is internally represented as a mutable cell, whose internal state is one of the following:

Pure x, if the suspension was already forced, and its final result is x.
Except e, if the suspension was already forced, and an exception was thrown in the process.
Delay f, if the suspension wasn’t forced yet, and its final result can be obtained by evaluating f ().

Furthermore, because we used opaque ascription (:>), the internal representation of the type of suspensions is hidden outside of the module.

Here’s our new type of lazy suspensions in action:

infixr 5 :::
datatype 'a stream = NIL | ::: of 'a * 'a stream Lazy.lazy

(* An infinite stream of 1s, as in the Haskell example above *)
val xs = Lazy.fix (fn xs => 1 ::: xs)

(* Haskell's Data.List.unfoldr *)
fun unfoldr f x =
  case f x of
      NONE => NIL
    | SOME (x, y) => x ::: Lazy.delay (unfoldr f) y

(* Haskell's Prelude.iterate *)
fun iterate f x = x ::: Lazy.delay (iterate f o f) x

(* Two dummy suspensions *)
val foo = Lazy.pure 0
val bar = Lazy.pure 1

(* Illegal, foo and bar have type `int Lazy.lazy`,
 * whose internal representation as a mutable cell is hidden *)
val _ = (foo := !bar)