脳ざらし紀行

_ [ネット] Fの不動点

ラムダ式fを受けとったら、ラムダ式を返す次のようなプロシージャFを定義します。

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

とりあえず簡単な例で計算してみましょう。Fに常に5を返すラムダ式を渡して、返ってきたラムダ式に3を渡してみましょう。

((F (lambda (n) 5)) 3) 

いくらになるでしょうか。

;; => (* 3 (f (- 3 1))) => 15

15になりました。そして、次のようなプロシージャ fを考えます。

(define f
  (lambda (s)
    (F (lambda (x) ((s s) x)))))

fはラムダ式を受けとるようなラムダ式sを受けとって、ラムダ式を生成した後、それをFに渡します。

さて、次のような単純なプロシージャhを考えます。

(define h
  (lambda (x)
    (lambda (y)
      5)))

hは受けとったものを無視して、常に5を返すラムダ式を返します。ここで次のようなものを計算してみます。

((f h) 3) 

いくらになるでしょうか。

;; => ((F (lambda (x) ((h h) x))) 3) 
;; h は何を受けとっても5を返すラムダ式を返すので
;; => ((F (lambda (x) 5)) 3) => 15

15になりました。さて上の例でhの代わりに、fを入れてみたら何が起こるでしょう。

((f f) 10) ;; => ?

説明のためにちょっと書き換えてみましょう。

((lambda (x) ((f f) x)) 10)

これが ((f f) 10) と同じなのはすぐ分かりますね。さて、

((lambda (x) ((f f) x)) 10)
;; => ((f f) 10)
;; => ((F (lambda (x) ((f f) x))) 10) うむ?!

待って下さい。元と同じ、(lambda (x) ((f f) x)) が出てきました。少し長いので、hogeとでも書き直しておきましょう

(define hoge 
 (lambda (x) ((f f) x)))

ここで、Fはラムダ式を受けとってラムダ式を返す写像だったことを思い出して下さい。上のことからも分かるように、すべての nについて

(hoge n) == ((F hoge) n）

が成り立ちます。つまり、hogeは写像 Fの不動点なのです。ところで私たちは Fの不動点をすでに知っています。そう、階乗ですね。確かめてみましょう。

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

(fact 10) ;; => 3628800
((F fact) 10) ;; => 3628800

なるほど、階乗関数は Fの不動点のようです。さて、hogeも Fの不動点でした。ということは先ほどの答えはもう分かりますね。

((f f) 10) 
;; => ((lambda (x) ((f f) x)) 10)
;; => (hoge 10)
;; => 3628800

はい拍手。

_ [ネット] Yオペレータ

上の例ではfの定義の中にFが最初から入っていました。ならば、Fを受けとって、Fの不動点である (lambda (x) ((f f) x)) を返すプロシージャYを定義しましょう。

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

((Y F) 10) ;; => 3628800

Yは上のFに限らずすべてのFに対して、不動点を返します。

YF = F(YF)

Yオペレータと呼ぶそうです。

_ [ネット] プログラム言語とその他のメモ。

昨日の、自己言及の論理と計算(PDF)の最後に不動点の話が載っていて、どうしても分からなくて、検索したら上のサイトの「不動点オペレータについて」がヒットした。このページを元にして上の文章を書いてみました。

YF = F(YF) はMITのSchemeのページのシンボルにも使われているそうです。