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

[hiroshi-manabe様の日本語訳](https://github.com/hiroshi-manabe/sicp-pdf)を使わせてもらいます。
練習問題等は[Gauche](http://practical-scheme.net/gauche/index-j.html)で実行。

[前回はこちら](https://qiita.com/shuetsu@github/items/007be822b806ed798377)

## 2.1.3 データとは何か

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

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

``` _.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

`cons`と`car`は次のようにも定義できるのだそうだ。

``` _.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
```