Lazy

MLton

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.

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.

signature LAZY =
   sig
      val lazy: (unit -> 'a) -> unit -> 'a
   end

This is easy to implement in 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