Posted at

SICP読書録 #19 2.1.3 データとは何か - 練習問題 2.6

hiroshi-manabe様の日本語訳を使わせてもらいます。

練習問題等はGaucheで実行。

前回はこちら


2.1.3 データとは何か

これまで、cons, car, cdrという手続きを用いることで、ペアという概念を利用してきた。しかし、ペアとは何だ?

2つのオブジェクトをconsでくっつけたら、carcdrでそれを取り出せる、ということさえ満たしていればそれはペアと言えるんじゃないか。だったら、次のように実装してもいい。


_.scm

(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

conscarは次のようにも定義できるのだそうだ。


_.scm

(define (cons x y)

(lambda (m) (m x y)))
(define (car z)
(z (lambda (p q) p)))

実際動かしてみると、うまくいく。


_.scm

gosh> (car (cons 10 20))

10

何でうまくいくのか?展開してみよう。


_.scm

> (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は次のように定義すればよい。


_.scm

(define (cdr z)

(z (lambda (p q) q)))

動かしてみよう。


_.scm

gosh> (cdr (cons 10 20))

20


練習問題 2.5

非負整数$a$と$b$のペアを$2^a3^b$の整数で表現できる。2と3は素数だから因数分解すればよいのだ。

作ってみよう。


_.scm

(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))


動かしてみよう。


_.scm

gosh> (car (cons 4 5))

4
gosh> (cdr (cons 4 5))
5


練習問題 2.6

先ほど、ペアというデータを手続きオブジェクトで表現してみせた。だったら数値というデータだって、手続きオブジェクトで表現できるんじゃないのか?

チャーチ数という表現方法を用いると、[数値0]と[1を足す演算]を次のように定義できるらしい。


_.scm

(define zero (lambda (f) (lambda (x) x)))

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

(add-1 zero)を展開してみよう。


_.scm

> (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))はどうか。


_.scm

> (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と名付けよう。


_.scm

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

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

これが正しい数値を表現できているのかを確かめるために、以下のように実行してみる。


_.scm

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

gosh> ((zero inc) 0)
0
gosh> ((one inc) 0)
1
gosh> ((two inc) 0)
2


チャーチ数に対する足し算を作ってみよう。

直感的に考えて、次のように実行できる。


_.scm

gosh> ((zero inc) ((one inc) 0))

1
gosh> ((one inc) ((one inc) 0))
2
gosh> ((one inc) ((two inc) 0))
3

一般化して、手続きaddを作ってみよう。


_.scm

(define (add a b)

(lambda (f) (lambda (x) ((a f) ((b f) x)))))

実行結果。


_.scm

(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