ex 2.6 チャーチ数

sicp 
;; sicp ex 2.6
(define zero (lambda (f) (lambda (x) x)))

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

(define one
  (lambda (f) (lambda (x) (f x))))

(define two
  (lambda (f) (lambda (x) (f (f x)))))

;; add
;; チャーチ数は、f を x に n 回適応する関数
;; (lambda (f) (lambda (x) <body>)) ..... (1)
;; の形になってる。
;; なので、
;; (define (add a b)
;;   (lambda (f)
;;     (lambda (x) ... )))
;; となるだろう。
;; チャーチ数 a
;; (lambda (f) (lambda (x) (f (f (f ... (f x))))))
;; に f を引数として (a f) わたすと
;; (lambda (x) (f (f (f ... (f x)))))
;; となる。
;;
;; これを g として 引数 x を渡して、(g x) とすると
;; (f (f (f ... (f x))))
;; となる。
;;
;; これを引数として (a f) に渡すと
;; ((lambda (x) (f (f (f ... (f x))))) (g x))
;; ((lambda (x) (f (f (f ... (f x))))) (f (f (f ... (f x)))))
;; (f (f (f ... (f (f (f (f ... (f x))))))))
;; となるので、これを上記 (1)式の <body> の部分に入れれば目的の値となるから
(define (add a b)
 (lambda (f)
   (lambda (x)
     ((a f) ((b f) x)))))

チャーチ数は初めてSICPを読んだときに面食らった覚えがあります。


今回はチャーチ数のすべてを理解できたとは言えないけど。
addの実装なんかはかなり推測的に行ったし。


でも、データは条件を満たすもの、で、その条件を手続きとして表現すると、
数という最下層のデータでも表現できる、ということがわかりました。


こういうことを知れるところが面白いんだよな。この本は。


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

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