fixedpoint.jp

2007/02/14

Y combinator on Scheme

型なし 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

参考にしたページ:

© 2006-2023 fixedpoint.jp