Purely Functional Data Structures の遅延評価の記法

Purely Functional Data Structures の遅延評価の記法を紹介し、それと等価な OCaml のコードを説明します。

遅延評価

遅延評価(ここではメモ化付きの遅延評価を指します)は必要になるまで計算が遅延される、プログラムの評価戦略のことを意味しています。 遅延評価は概念的には thunk(サンク)、つまり評価したら初めて値を返す関数(逆に言えば、評価するまで計算を遅延できるということ)で表現できます。 書籍を理解するにはあまり関係ないため、そういうものだと思っていただければよいです。興味がある人は調べてみてください。

OCaml では lazy キーワードで遅延評価の生成と、パターンマッチ時の評価の強制ができます。 細かな syntax について Lazy patterns · yallop/ocaml-patterns Wiki を見てください。

$-記法

PFDS では遅延評価の記述が煩雑になるため、簡便に記述できるように独自の記法として $-記法 を導入しています。 $-記法によって遅延評価される式の型は τ susp で定義されます。 susp には特に意味はなくて、OCaml だと 'a Lazy.t で、Scala だと => A となります。

$e は e の評価を遅延することを意味します。(型は τ susp) OCaml では lazy eLazy.from_val eLazy.from_fun (fun () -> e) のいずれかを使います。 Lazy.from_val e は e が評価されてしまうので、それで問題無い時だけ使うように気を付けてください。 基本的には lazy e を使っておけばよいと思います。

次に $ 記号の影響範囲についてです。 $ 記号は可能な限り(lexical な意味で)右まで影響が伸びるように意味論が定義されています。 たとえば $calc a b c$(calc a b c) として解釈されます。 つまり、calc a b c 全体が遅延評価されるということです。

関数の引数で $-記法が使われた場合、たとえば fun force ($x) = x は x を即時評価することを意味します。 OCaml では let force (lazy x) = x と書けば同じ意味になります。 関数で引数を受け取った時に評価せず、別の計算に渡すには、書籍では fun plus (x, y) = $case (x, y) of ($m , $n) => m + n のように記述しています。 この式は $(case (x, y) of ($m, $n) => m + n) という意味である点に注意してください。 OCaml では以下のように書けます。

let plus x y =
  match x, y with
  | lazy m, lazy n -> lazy (m + n)

書籍中では、このパターンが頻出であるため fun lazy という syntax sugar が導入されています。 fun lazy f p = efun f x = $case x of p => force e(翻訳書まま) のように展開されます。 (おそらくここは誤植があって、展開結果は fun f x = $case x of $p => force e が正しいはずです。) この syntax sugar を OCaml で簡単に書く方法はないので、個別に頑張って書いていくしかないと思います。

以上、簡単にですが OCaml で PFDS の $-記法を使う方法を説明しました。

Comments

comments powered by Disqus