再帰的な無名関数

Scheme Math

次の関数は再帰的な関数だ。

(define fact
  (lambda (n)
    (if (= n 0)
        1
        (* n (fact (- n 1))))))

この関数は内部で自分自身を呼び出しているので、普通の方法では無名関数として定義できない。

こういう場合、不動点オペレータというものを使うと以下のようにしてfactを定義することができる。（fact関数の中で直接factという名前を使っていない所がポイント）

(define fact
  (let ((Y (lambda (F)
             ((lambda (s) (F (lambda (x) ((s s) x))))
              (lambda (s) (F (lambda (x) ((s s) x))))))))
    (Y (lambda (f)
         (lambda (n)
           (if (= n 0)
               1
               (* n (f (- n 1)))))))))

ここで天下り的に出てきたYをなんとか導出してみたいと思って数日間考えていたのだが、ようやく方法が分かった。ほとんどは最後に挙げた参考URLに書いてあることの焼き直し。

まず、こういう関数を考えてみる。

(define fact-maker
  (lambda (s)
    (lambda (n)
      (if (= n 0)
          1
          (* n ((s s) (- n 1)))))))

すると以下のような変形ができるので、

;; #0
(fact-maker fact-maker)

;; #1
((lambda (s)
   (lambda (n)
     (if (= n 0)
         1
         (* n ((s s) (- n 1))))))
 fact-maker)

;; #2
(let ((s fact-maker))
  (lambda (n)
    (if (= n 0)
        1
        (* n ((s s) (- n 1))))))

;; #3
(lambda (n)
  (if (= n 0)
      1
      (* n ((fact-maker fact-maker) (- n 1)))))

(fact-maker fact-maker)はfactに等しい。

次に、fact-makerを変形していく。

;; #0
(define fact-maker
  (lambda (s)
    (lambda (n)
      (if (= n 0)
          1
          (* n ((s s) (- n 1)))))))

;; #1
(define fact-maker
  (lambda (s)
    (let ((f (lambda (x) ((s s) x))))
      (lambda (n)
        (if (= n 0)
            1
            (* n (f (- n 1))))))))

; ここで以下のように定義すると関数呼び出しが停止しない
; (define fact-maker
;   (lambda (s)
;     (let ((f (s s)))
;       (lambda (n)
;         (if (= n 0)
;             1
;             (* n (f (- n 1))))))))

;; #2
(define fact-maker
  (lambda (s)
    ((lambda (f)
       (lambda (n)
         (if (= n 0)
             1
             (* n (f (- n 1))))))
     (lambda (x) ((s s) x)))))

;; #3
(define fact-maker
  (lambda (s)
    (F (lambda (x) ((s s) x)))))

(define F
  (lambda (f)
    (lambda (n)
      (if (= n 0)
          1
          (* n (f (- n 1)))))))

これを使うと、(fact-maker fact-maker)は以下のような式に展開される。

((lambda (s)
   (F (lambda (x) ((s s) x))))
 (lambda (s)
   (F (lambda (x) ((s s) x)))))

ここからFを抽象してYが得られる。

(define Y
  (lambda (F)
    ((lambda (s)
       (F (lambda (x) ((s s) x))))
     (lambda (s)
       (F (lambda (x) ((s s) x)))))))

以上のことをまとめると、

(Y F) == (fact-maker fact-maker) == fact

となる。

不動点

一般に、f(x)=xとなるようなxのことを関数fの不動点と呼ぶ。

今回の場合、(F fact)はfactと等しいので、factは関数Fの不動点になっている。

Yには任意のラムダ式Fに対して

F(YF) = YF

という関係がある。このときYFは関数Fの不動点になっているので、YはFの不動点を作り出す操作、つまり不動点オペレータとなる。

参考URL