賢人鳥

分かった！ 分かった！ 分かった！

自己言及

ものまね鳥(M)は、自己言及する鳥なんだ！

Haskell では、型推論がジャマして、ものまね鳥を実現できない。

-- Mx = xx
m x = x x -- エラーになる

ヒバリ(L)も実現できない！

-- Lxy = x(yy)
l x y = x (y y) -- エラーになる

当然の帰結として、Haskell では再帰を使わないと賢人鳥(Y)を実現できない！

賢人鳥1

wikipediaの Y コンビネーターに書かれている最初の賢人鳥はこう。

(define Y
  (lambda (f)
    ((lambda (x) (f (lambda (y) ((x x) y))))
     (lambda (x) (f (lambda (y) ((x x) y)))))))

これは SLL だ！

;; Sxyz = xz(yz)
(define S (lambda (x) (lambda (y) (lambda (z) ((x z) (lambda (w) ((y z) w)))))))
;; Lxy = x(yy)
(define L (lambda (x) (lambda (y) (x (lambda (z) ((y y) z))))))
;; Y = SLL
(define Y ((S L) L))

賢人鳥2

wikipediaの Y コンビネーターに書かれている二番目の賢人鳥はこう。

(define Y
  ((lambda (x) (lambda (y) (y (lambda (z) (((x x) y) z)))))
   (lambda (x) (lambda (y) (y (lambda (z) (((x x) y) z)))))))

説明にあるように、これはチューリング鳥を使った UU。

;; Uxy = y(xxy)
(define U (lambda (x) (lambda (y) (y (lambda (z) (((x x) y) z))))))
;; Y = UU
(define Y (U U))

賢人鳥3

The Little Schemer に出てくる賢人鳥はこう。

(define Y
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f) (le (lambda (x) ((f f) x)))))))

これは BML だ！

;; Bxyz = x(yz)
(define B (lambda (x) (lambda (y) (lambda (z) (x (lambda (w) ((y z) w)))))))
;; Mx = xx
(define M (lambda (x) (x x)))
;; Lxy = x(yy)
(define L (lambda (x) (lambda (y) (x (lambda (z) ((y y) z))))))
;; Y = BML
(define Y ((B M) L))

面倒だけど、代入すれば、ちゃんと変形できる。

The Little Schemer (The MIT Press)