2007年01月07日
Lambda Calculus Simulator
Y澤先生の課題。

「Schemeでラムダ計算シミュレーターを作ってチャーチ数で階乗を計算」
処理系はSigSchemeを使いました。以下の3つのルールに従って単純に実装するだけ。行数的には100行ちょっとですね。call-by-nameなのでeval一発という訳には行かないので面倒という所がポイントです。Haskellでやるのは...卑怯ですね。
; t(term) ::= x (variable) ; | (lambda (x) t) (abstraction) ; | t t (applicatoin) ; ; v(value) ::= (lambda (x) t) (abstraction value) ; (SUBST-1) [x -> s] x := s ; (SUBST-2) [x -> s] y := y ; (SUBST-3) [x -> s](lambda (y) t1) := (lambda (y) [x -> s]t1) ; (SUBST-4) [x -> s](t1 t2) := [x -> s]t1 [x -> s]t2 ; (E-APP1) ; t1 -> t'1 ; ----------------- ; t1 t2 -> t'1 t2 ; ; (E-APP2) ; t2 -> t'2 ; ----------------- ; v1 t2 -> v1 t'2 ; ; (E-APPABS) ; (lambda (x) t1) v2 -> [x |-> v2] t1
参考図書としてTAPLを参照しました。ただ、ここに載っているLambda計算のシミュレーターはclosureの中まではbeta変換を施さないので少し注意が必要でした。TAPLに載っているshift操作を忠実に実装するのは面倒だったので、再帰的にsubstituteする中で、被置き換え対象のシンボルと同じシンボルを持つclosureが出てきたらsubstitutionを辞めるという戦略にしました。
出来上がったものの実行コードは以下の様になります。
(define (print-church n) (print (((eval n '()) (lambda (x) (+ x 1))) 0))) (define zero '(lambda (s) (lambda (z) z))) (define four '(lambda (s) (lambda (z) (s (s (s (s z))))))) (define (succ num) `((lambda (n) (lambda (s) (lambda (z) (s ((n s) z))))) ,num)) (print-church (eval-lambda (succ zero))) (print-church (eval-lambda (ifact four)))
実行結果は以下の様になります。
[kzk@pfidev1]~/u-tokyo/3-fuyu/lambda% gosh church.scm (lambda (s) (lambda (z) (s z))) 1 (lambda (f) (lambda (z) (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f z)))))))))))))))))))))))))) 24
実行速度を比べているとやはりgoshは速いですね。一度SigSchemeを高速化しようとしてCodeFestでGC時のキャッシュミスを減らそうと頑張ってみたのですが、これと同じ結果になってしまいました。
Guileはインタプリタの割に速いのですが、あれはどこがどう速いのか未だに分かってません。メモリ管理が優秀なのかな。
P.S.
TAPLはSimply Typed Lambda Calculusまでしか読みこなせていない...。
P.S.
higeponさんがSigSchemeテストコードを活用して下さっているようです。
- by
- at 23:52

comments
Guile が速い理由(予想):
-Compiler 型で結構最適化をかけるから→このλ計算機みたいに小さい code を繰り返し実行する program で特に顕著なはず
-Copying GC (だったはず)なので、memory が潤沢な環境では連続して確保した object が memory 上で連続するので参照局所性大→sigscheme で fragmentation がひどくなるような確保 pattern で特に顕著なはず
-heap の初期 size が大きいかも
というわけで検証よろしく(ぇ