Serendip

Web Studio

問題2.6

各数の定義は引数として与えられた手続き f をn回作用させる手続きを返す。

(define zero (lambda (f) (lambda (x) x)))
(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))
(define three (lambda (f) (lambda (x) (f (f (f x))))))

add-1 は引数として与えられた手続き f を1回多く作用させる。

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

数字表示用手続き

(define (inc n)
  (+ n 1))

(define (to-s z)
  ((z inc) 0))

zero では f は1度も作用させられない。

(to-s zero)
((zero inc) 0)
(((lambda (f) (lambda (x) x)) inc) 0)
((lambda (x) x) 0)
0

(to-s one)
((one inc) 0)
(((lambda (f) (lambda (x) (f x))) inc) 0)
((lambda (x) (inc x)) 0)
(inc 0)
1

(to-s two)
((two inc) 0)
(((lambda (f) (lambda (x) (f (f x)))) inc) 0)
((lambda (x) (inc (inc x))) 0)
(inc (inc 0))
(inc 1)
2

(to-s three)
((three inc) 0)
(((lambda (f) (lambda (x) (f (f (f x))))) inc) 0)
((lambda (x) (inc (inc (inc x)))) 0)
(inc (inc (inc 0)))
(inc (inc 1))
(inc 2)
3

(to-s (add-1 two))
(to-s (lambda (f) (lambda (x) (f ((two f) x)))))
((lambda (x) (inc ((two inc) x))) 0)
(inc ((two inc) 0))
(inc (((lambda (f) (lambda (x) (f (f x)))) inc) 0))
(inc ((lambda (x) (inc (inc x))) 0))
(inc (inc (inc 0)))
(inc (inc 1))
(inc 2)
3

加算手続き add の定義

(define (add a b)
  (lambda (f) (lambda (x) ((a f) ((b f) x)))))

(to-s (add one two))
gosh> 3
(to-s (add three two))
gosh> 5
(to-s (add three three))
gosh> 6
(to-s (add zero three))
gosh> 3

参考サイト

以下のサイトを参考にした。
SICPを読む(39) 問題 2.6 Church数 – ボクノス
404 Blog Not Found:TuringとChurchの狭間で

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

posted with amazlet at 08.11.07

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

Amazon.co.jp で詳細を見る