#008 遅延評価の実装 - λx. x K S K ＠はてな

OCaml で遅延（怠惰*1）評価を実装する方法があるが，毎回 lazy や Lazy.force を書かないといけないため非常に面倒である．たとえば，ML の授業などでは，

type 'a lazy_list = Nil | Cons of 'a * 'a lazy_list lazy_t

とすれば簡単，と教わるのではないだろうか．このとき，1::2::3::... のようなリストを定義するためには Cons(1, lazy(Cons(2, lazy(Cons(3,lazy ...))))) と記述する必要があり， lazy を毎回書くのが嫌になるかもしれない．だからといって

let cons x xs = Cons(x, lazy xs)

などとしてはいけない．OCaml では，ユーザの定義する全ての関数は正格関数となるため， cons が呼ばれた時点で xs が必ず評価されてしまい，それを後から lazy で遅延しても全く意味がない．また，if 文を再定義する際にも同様のことが言える． OCaml では，式 if b then t else e は， b の真偽値が確定した時点で t か e を評価するように非正格に定義されているが，これを

let cond b t e = if b then t else e

などと再定義してしまっては意味がない．なぜなら， cond が呼ばれた時点で， b の真偽値に関係なく t も e も評価されてしまうからだ．そこで，この記事では camlp4 を利用した（似非）遅延評価の実装方法を紹介する．なお，ここでは camlp4-3.09.2 を用いるものとする．

まず，下に示すプログラム pa_lazy.ml を用意する．簡単に言うと，このプログラムは次のような変換 T[ _ ] をしているだけである．

T[ x ] = Lazy.force x
T[λx.M ] = λx.T[ M ]
T[ M N ] = T[ M ] (lazy T[ N ])

つまり，その値が参照されない限り関数の引数の評価を行わないようなプログラムに翻訳される．その他，リストのコンストラクタなども遅延リスト用に変換している．

(* pa_lazy.ml *)
open Pcaml
let _loc = Token.dummy_loc
let lident_patt = Grammar.Entry.create Pcaml.gram "lident_patt"
and simple_expr = Grammar.Entry.create Pcaml.gram "simple_expr"
let _ =
  let rec fun_expr ps e = match ps with
      [] -> e
    | p::ps -> <:expr< fun [$p$ -> $fun_expr ps e$] >> in
  let rec eta_lazy n ps e =
    let v = "x"^string_of_int n in
    if n <= 0 then fun_expr (List.rev ps) e
    else eta_lazy (n-1) (<:patt<$lid:v$>>::ps) (<:expr<$e$ (Lazy.force $lid:v$)>>) in
  DELETE_RULE expr: SELF; SELF END; DELETE_RULE patt: SELF; SELF END;
  DELETE_RULE expr: SELF; "::"; SELF END; DELETE_RULE patt: SELF; "::"; SELF END;
  DELETE_RULE expr: "[";"]" END; DELETE_RULE patt: "[";"]" END;
  EXTEND
    str_item: LEVEL "top"
      [[ "let"; "lazy"; p = LIDENT; "="; e = simple_expr; "["; i = INT; "]" ->
           <:str_item< declare
             value $lid:p$ = lazy $eta_lazy (int_of_string i) [] e$;
           end >> ]];
    simple_expr:
      [[ v = LIDENT -> <:expr< $lid:v$ >> | e = expr LEVEL "simple" -> e ]];
    expr: LEVEL "simple"
      [[ v = LIDENT -> <:expr< Lazy.force $lid:v$ >>
       | "["; "]" -> <:expr< `nil >> ]];
    expr: LEVEL "apply"
      [ LEFTA [ e1 = expr; e2 = expr -> <:expr< $e1$ (lazy $e2$) >> ]];
    expr: AFTER "^"
      [ RIGHTA [ hd = SELF; "::"; tl = SELF ->
                   <:expr< `cons(lazy $hd$,lazy $tl$) >> ]];
    patt:
      [ RIGHTA [ hd = lident_patt; "::"; tl = lident_patt ->
                   <:patt< `cons($hd$,$tl$) >> ]];
    patt: LEVEL "simple" [[ "["; "]" -> <:patt< `nil >> ]];
    lident_patt:
      [[ v = LIDENT -> <:patt< $lid:v$ >> | "_" -> <:patt< _ >> ]];
    let_binding:
      [[ v = LIDENT; ps = LIST0 patt LEVEL "simple"; "="; e = expr ->
           (<:patt< $lid:v$ >>, <:expr< lazy $fun_expr ps e$ >>)
       | "_"; "="; e = expr -> (<:patt< _ >>, e) ]];
  END

これを，

ocamlc -pp "camlp4o pa_extend.cmo q_MLast.cmo" -I +camlp4 -c pa_lazy.ml

などとしてコンパイルする．これを利用することにより，以下の制限のもと全ての値の評価が遅延されるような OCaml のプログラムが導出できる（手抜きなので余計な制限が多いが気にしないように）．

既存の関数は let lazy （新しい関数名） = （元の関数名）[（引数の数）] で再定義．
中置演算子は再定義不可．
部分適用は禁止．
リストのコンストラクタは，:: と [] のみ．[1;2]などは不可．
関数定義の際の引数やリストパターンの引数は変数のみ．
式 let _ = ... の評価は遅延されない．
（その他にもいろいろあるかもしれないが省略）

例えば，一見 OCaml では止まらなさそうな以下の素数生成プログラム primes.ml も停止する．なお，非正格になっているかどうかの検証のため，敢えて if の代わりに上記の cond を使ってみた．

(* primes.ml *)
let lazy print_int = print_int[1]
let lazy print_char = print_char[1]
let lazy succ = succ[1]
let lazy pred = pred[1]
let lazy gt = (>)[2]
let lazy md = (mod)[2]

let cond b t e = if b then t else e
let rec from n = n::from (succ n)
let rec sieve p l = match l with
    x::xs -> cond (gt (md x p) 0) (x::sieve p xs) (sieve p xs)
let rec primes l = match l with x::xs -> x::primes (sieve x xs)
let rec print_n n l = match l with
    x::xs -> cond (gt n 0) (print_int x; print_char ' '; print_n (pred n) xs) ()
let _ = print_n 100 (primes (from 2))

コンパイル方法は以下の通り．

ocamlc -o primes.bin -pp "camlp4o ./pa_lazy.cmo" primes.ml

実際に，primes.bin を実行すると 100 個の素数が出力される．

*1:厳密には，遅延（delay）と怠惰（lazy）は異なるがこの記事ではどちらも「遅延」と呼ぶことにする．