懶惰的評價

標準 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)