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