型なし lambda calculus の Y combinator には多くのバリエーションがあります。Scheme のような call-by-value で評価が行われるシステムで動作するバリエーションのうち、よく知られている2つが Wikipedia の Y Combinator の頁に記載されています。それぞれ関数として定義すると以下のようになります:
(define Z
(lambda (f)
((lambda (x) (f (lambda (y) ((x x) y))))
(lambda (x) (f (lambda (y) ((x x) y)))))))(define T
((lambda (x) (lambda (y) (y (lambda (z) (((x x) y) z)))))
(lambda (x) (lambda (y) (y (lambda (z) (((x x) y) z)))))))
上のいずれかを使えば、再帰的定義によって別の関数を定義できます; 例えば
(define fact
(lambda (f)
(lambda (n)
(if (= n 0)
1
(* n (f (- n 1)))))))
((T fact) 5) ; => 120
((T fact) 10) ; => 3628800階乗よりもっと計算にコストがかかる関数を定義してみます。Ackermann 関数は急激に発散することで知られている2変数の帰納的関数です。2変数関数も次のように2回の適用を利用する形に翻訳すれば Z や T をそのまま利用できます。
(define ackermann
(lambda (f)
(lambda (m)
(lambda (n)
(cond ((= 0 m) (+ n 1))
((= 0 n) ((f (- m 1)) 1))
(else ((f (- m 1)) ((f m) (- n 1)))))))))
(((Z ackermann) 2) 10) ; => 23 immediately
(((Z ackermann) 3) 7) ; => 1021 after a while
(((Z ackermann) 4) 4) ; => 2^(2^65536)-3 in the next world参考にしたページ: