懶惰的評價

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)