懒惰的评价

Created: November-22, 2018

标准 ML 没有内置的懒惰评估支持。某些实现，特别是 SML / NJ，具有非标准的惰性求值原语，但使用这些原语的程序将不可移植。惰性悬架也可以使用标准 ML 的模块系统以便携方式实现。

首先，我们定义一个接口或签名来操作延迟挂起：

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

此签名表明：

延迟挂起的类型构造函数是抽象的 - 它的内部表示是对用户隐藏的（与之无关）。
有两种方法可以创建暂停：通过直接包装其最终结果，以及延迟函数应用程序。
我们可以用悬架做的唯一一件事就是强迫它。当第一次强制延迟暂停时，其结果被记忆，以便下次不必重新计算结果。
我们可以创建自我引用的值，其中自引用经历暂停。这样我们就可以创建一个包含相同重复元素的逻辑无限流，如下面的 Haskell 片段所示：

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

在定义接口之后，我们必须提供一个实际的实现，也称为模块或结构：

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

此结构表明暂停在内部表示为可变单元格，其内部状态为以下之一：

Pure x，如果暂停已被迫，其最终结果是 x。
Except e，如果暂停已经被迫，并且在此过程中抛出异常。
Delay f，如果暂停还没有强制，最终结果可以通过评估 f () 获得。

此外，因为我们使用了不透明的归属 （:>），所以悬浮类型的内部表示隐藏在模块之外。

这是我们的新型懒惰悬架：

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)