hiroshi-manabe様の日本語訳を使わせてもらいます。
練習問題等はGaucheで実行。
2.1.3 データとは何か
これまで、cons, car, cdrという手続きを用いることで、ペアという概念を利用してきた。しかし、ペアとは何だ？
2つのオブジェクトをconsでくっつけたら、carとcdrでそれを取り出せる、ということさえ満たしていればそれはペアと言えるんじゃないか。だったら、次のように実装してもいい。
(define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "Argument not 0 or 1: CONS" m))))
dispatch)
(define (car z) (z 0))
(define (cdr z) (z 1))
この方法だと、ペアを手続きdispatch（というか、xとyの値を含んだクロージャ）で表現している。
これは突飛な方法に思えるかもしれないが、手続きをオブジェクトとして扱うことで、複合データを表現できるのだ。このやり方をメッセージパッシングという。
練習問題 2.4
consとcarは次のようにも定義できるのだそうだ。
(define (cons x y)
(lambda (m) (m x y)))
(define (car z)
(z (lambda (p q) p)))
実際動かしてみると、うまくいく。
gosh> (car (cons 10 20))
10
何でうまくいくのか？展開してみよう。
> (car (cons 10 20))
> (car (lambda (m) (m 10 20))
> ((lambda (m) (m 10 20)) (lambda (p q) p))
> ((lambda (p q) p) 10 20)
> 10
なるほど。ならばcdrは次のように定義すればよい。
(define (cdr z)
(z (lambda (p q) q)))
動かしてみよう。
gosh> (cdr (cons 10 20))
20
練習問題 2.5
非負整数$a$と$b$のペアを$2^a3^b$の整数で表現できる。2と3は素数だから因数分解すればよいのだ。
作ってみよう。
(define (cons x y)
(* (expt 2 x) (expt 3 y)))
(define (car z)
(define (car-iter z x)
(if (= (remainder z 2) 0)
(car-iter (/ z 2) (+ x 1))
x))
(car-iter z 0))
(define (cdr z)
(define (cdr-iter z y)
(if (= (remainder z 3) 0)
(cdr-iter (/ z 3) (+ y 1))
y))
(cdr-iter z 0))
動かしてみよう。
gosh> (car (cons 4 5))
4
gosh> (cdr (cons 4 5))
5
練習問題 2.6
先ほど、ペアというデータを手続きオブジェクトで表現してみせた。だったら数値というデータだって、手続きオブジェクトで表現できるんじゃないのか？
チャーチ数という表現方法を用いると、[数値0]と[1を足す演算]を次のように定義できるらしい。
(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))
(add-1 zero)を展開してみよう。
> (add-1 zero)
> (add-1 (lambda (f) (lambda (x) x)))
> (lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) x)) f) x))))
> (lambda (f) (lambda (x) (f ((lambda (x) x) x))))
> (lambda (f) (lambda (x) (f x)))
さらに、(add-1 (add-1 zero))はどうか。
> (add-1 (add-1 zero))
> (add-1 (lambda (f) (lambda (x) (f x))
> (lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) (f x)) f) x))))
> (lambda (f) (lambda (x) (f ((lambda (x) (f x)) x))))
> (lambda (f) (lambda (x) (f (f x))))
というわけで、add-1を通すたびに手続きfの呼ばれる回数が増えていくという仕組みになっている。チャーチ数とは、fが呼ばれる回数によって数値を表すという表現方法のようだ。
得られた式をそれぞれ、one,twoと名付けよう。
(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x))))
これが正しい数値を表現できているのかを確かめるために、以下のように実行してみる。
(define (inc n) (+ n 1))
gosh> ((zero inc) 0)
0
gosh> ((one inc) 0)
1
gosh> ((two inc) 0)
2
チャーチ数に対する足し算を作ってみよう。
直感的に考えて、次のように実行できる。
gosh> ((zero inc) ((one inc) 0))
1
gosh> ((one inc) ((one inc) 0))
2
gosh> ((one inc) ((two inc) 0))
3
一般化して、手続きaddを作ってみよう。
(define (add a b)
(lambda (f) (lambda (x) ((a f) ((b f) x)))))
実行結果。
(define three (add one two))
(define four (add two two))
(define five (add (add two two) one))
gosh> ((three inc) 0)
3
gosh> ((four inc) 0)
4
gosh> ((five inc) 0)
5