moratorium

処理系は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テストコードを活用して下さっているようです。