Serendip

Web Studio

問題4.21

λ式だけを使って再帰をしている問題のコードを見て、以前読んだYコンビネータの記事（Y Combinatorを直感的に理解。しようと試みる。 – 医者を志す妻を応援する夫の日記、Y コンビネータって何？ – IT戦記）を思い出した。
脚注にはY演算子（Y operator）と書かれていて、何か関係があるのかと思ったら、Yコンビネータの日本語訳は "不動点演算子" というらしい。
ずばり、この問題はYコンビネータの話らしい。こんなところで再会するとは。

a. Fibonacci 数を計算する手続き

((lambda (n)
         ((lambda (fib)
                  (fib fib n))
          (lambda (fb k)
                  (cond ((= k 0) 0)
                        ((= k 1) 1)
                        (else
                          (+ (fb fb (- k 1))
                             (fb fb (- k 2))))))))
 10)
gosh> 55

b. 与えられた数値が偶数かどうかを判定する手続き

(define (f x)
  ((lambda (even? odd?)
           (even? even? odd? x))
   (lambda (ev? od? n)
           (if (= n 0) #t (od? ev? od? (- n 1))))
   (lambda (ev? od? n)
           (if (= n 0) #f (ev? ev? od? (- n 1))))))

(f 42)
gosh> #t
(f 37)
gosh> #f

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る