Lazy
====

In a lazy (or non-strict) language, the arguments to a function are
not evaluated before calling the function.  Instead, the arguments are
suspended and only evaluated by the function if needed.

<:StandardML:Standard ML> is an eager (or strict) language, not a lazy
language.  However, it is easy to delay evaluation of an expression in
SML by creating a _thunk_, which is a nullary function.  In SML, a
thunk is written `fn () => e`.  Another essential feature of laziness
is _memoization_, meaning that once a suspended argument is evaluated,
subsequent references look up the value.  We can express this in SML
with a function that maps a thunk to a memoized thunk.

[source,sml]
----
signature LAZY =
   sig
      val lazy: (unit -> 'a) -> unit -> 'a
   end
----

This is easy to implement in SML.

[source,sml]
----
structure Lazy: LAZY =
   struct
      fun lazy (th: unit -> 'a): unit -> 'a =
         let
            datatype 'a lazy_result = Unevaluated of (unit -> 'a)
                                    | Evaluated of 'a
                                    | Failed of exn

            val r = ref (Unevaluated th)
         in
            fn () =>
               case !r of
                   Unevaluated th => let
                                       val a  = th ()
                                           handle x => (r := Failed x; raise x)
                                       val () =         r := Evaluated a
                                     in
                                       a
                                     end
                 | Evaluated a => a
                 | Failed x    => raise x
         end
   end
----
