Lambda Calculus Simulator

Y澤先生の課題。

「Schemeでラムダ計算シミュレーターを作ってチャーチ数で階乗を計算」

処理系はSigSchemeを使いました。以下の3つのルールに従って単純に実装するだけ。行数的には100行ちょっとですね。call-by-nameなのでeval一発という訳には行かないので面倒という所がポイントです。Haskellでやるのは…卑怯ですね。
[code]
; 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
[/code]
参考図書としてTAPLを参照しました。ただ、ここに載っているLambda計算のシミュレーターはclosureの中まではbeta変換を施さないので少し注意が必要でした。TAPLに載っているshift操作を忠実に実装するのは面倒だったので、再帰的にsubstituteする中で、被置き換え対象のシンボルと同じシンボルを持つclosureが出てきたらsubstitutionを辞めるという戦略にしました。
出来上がったものの実行コードは以下の様になります。
[code]
(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)))
[/code]
実行結果は以下の様になります。
[code]
[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
[/code]
実行速度を比べているとやはりgoshは速いですね。一度SigSchemeを高速化しようとしてCodeFestでGC時のキャッシュミスを減らそうと頑張ってみたのですが、これと同じ結果になってしまいました。
Guileはインタプリタの割に速いのですが、あれはどこがどう速いのか未だに分かってません。メモリ管理が優秀なのかな。
P.S.
TAPLはSimply Typed Lambda Calculusまでしか読みこなせていない…。
P.S.
higeponさんがSigSchemeテストコードを活用して下さっているようです。

Similar Posts:

• n日前より古いファイルを消す
• 連続系演習第２回
• 上京