SICP 2.1.3 What Is Meant by Data? - プログラミング再入門

ノート

Dataとは何を表しているのか。

In general, we can think of data as defined by some collection of selectors and constructors, together with specified conditions that these procedures must fulfill in order to be a valid representation.

データとはひと組のセレクタとコンストラクタ、それからデータが正しい状態である為にそれらが満たすべき条件によって定義される、と考える事が出来る。

抽象度の高いデータ構造にとどまらず、cons、car、cdrについてもインターフェースの条件さえ満たせば変数等のデータオブジェクトを使わずに実現可能。

ここではconsの内部でdispatchと言う関数を定義して、ペアを作っている様に見せかけて実はクロージャを返している。carはこの0にこのクロージャを適用し、cdrは1に適用する。このクロージャは引数が0だった時に最初のxを、1だった時にyを返す事でcons、car、cdrを実現している。

実際にドットペアであろうがクロージャであろうが、同じインターフェースで同じ挙動を示すものは同じデータみなせる。

This may seem a curiosity now, but procedural representations of data will play a central role in our programming repertoire. This style of programming is often called message passing,

ここで言っているmessage passingが具体的にどんな定義なのかは分からないが、オブジェクト（ここではconsが返したクロージャ）に対してcarやcdrと言うメッセージを送っていると解釈している様に思う。これはpairと言うクラスのメソッドを直接呼び出しているのとは異なり、メッセージを受け取った側がそれに対する挙動を決めていると解釈している気がする。

Exercise 2.4

クロージャを使った別のcons、car、cdrの実装。
今回はconsで無名の関数（ここではこれをAとする）を作る。この関数は引数として与えられた関数mにconsの引数xとyを渡す。つまりmは二つの引数を取る関数。
この無名関数（A）に渡す関数mとして第１引数を返す関数を渡せばconsに渡したxが返る事になる。これがcarの定義。
cdrの定義は同様に

(define (cdr z)
  (z (lambda (p q) q)))

実行してみる。

> (define p (cons 'abc 'def))
> (car p)
abc
> (cdr p)
def
>

Exercise 2.5

非負の二つの整数に対しては2^a×3^bを計算する事でひとつの整数で表現可能。
２と３は互いに素なので

２を何回掛けても３の倍数にはならず、
逆に３を何回掛けても２の倍数にはならない。

2^a×3^bは必ず2がa個と3がb個の掛け算に素因数分解出来る。なのでひとつの整数にしてしまってもaとbは分離可能。

consは2^a×3^bを返す。
carは元の値を素因数分解した時の2の個数。すなわち２で何回割れるか。
cdrは同様に３で何回割れるか。

(define (cons a b)
  (* (expt 2 a) (expt 3 b)))
(define (car p)
  (define (iter rest pow)
    (if (zero? (remainder rest 2))
        (iter (/ rest 2) (+ pow 1))
        pow))
  (iter p 0))
(define (cdr p)
  (define (iter rest pow)
    (if (zero? (remainder rest 3))
        (iter (/ rest 3) (+ pow 1))
        pow))
  (iter p 0))

動作確認。

> (cons 5 9)
629856
> (car (cons 5 9))
5
> (cdr (cons 5 9))
9
> (cons 2 3)
108
> (car (cons 2 3))
2
> (cdr (cons 2 3))
3
>

Exercise 2.6

チャーチ数。ラムダ演算で表した自然数。定義はWeb上の色々な所にあるが、Wikipediaによると：
0 := λf x. x
1 := λf x. f x
2 := λf x. f (f x)
3 := λf x. f (f (f x))
関数の適用回数を数として扱う模様。ここで言う関数とは上記の定義に出て来るfで、xに適用する関数。チャーチ数nとは数とは言っても実は関数で、xにfをn回適用する関数を意味している。チャーチ数nは関数fに適用すると、引数xにfをn回適用する関数を返す。なので具体的な値にするにはまずチャーチ数にfを適用してxにfをn回適用する関数に変換してから、xに適用すると言う２段階の評価となる。
xは単位元的な存在なのか。xを出発点にfをn回適用するのだから。例えばxとして0を、fとして引数に１を加えるincを用いると、いわゆる普通の自然数になる。

zeroを考えると、「引数xにfを0回適用する関数」なので

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

add-1は定義から考えると、チャーチ数nを受け取りfの適用回数を１回増やす関数。考え方はチャーチ数nを評価した後に更にfをもう１回適用する。

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

まずチャーチ数nを評価する。すなわちnをfに適用してxの関数（xにfをn回適用する）に変換
その関数をxに適用
その結果に更にfをもう１回適用

と言う手順を行う関数を返す。

問題はzeroやadd-1を使わずにoneの定義を考える事。
定義からoneを考えると、fを受け取って、引数xにfを１回適用する関数を返すのだから

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

となる筈。
(add-1 zero)を展開すると：(lambda (f) (lambda (x) (f ( (zero f) x)))))
(zero f)の部分は：(lambda (x) x)
更に( (zero f) x)を展開すると：x
と言う事は(f ( (zero f) x))を展開すると：(f x)
最初に戻って(add-1 zero)を展開すると：(lambda (f) (lambda (x) (f x)))
合っていそうか。

定義からtwoを考えると

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

(add-1 one)を展開して考える。
(add-1 one)を展開すると：(lambda (f) (lambda (x) (f *1
( (one f) x)は：(f x)
(f ( (one f) x))は：(f (f x))
(add-1 one)は：(lambda (f) (lambda (x) (f (f x))))
合っていそう。

最後の問題はadd-1を繰り返し適用する以外の方法で足し算（m + n）をする関数を定義する事。add-1の時と同様に考えれば良さそう。最後の「fをもう１回適用」の部分を「fをもうm回適用」に変える。つまりxに対してfをn回適用して、更にm回適用する事で、都合m+n回適用する事になる。

チャーチ数nをfに適用して、fをn回適用する関数に変換する
その関数を引数xに適用する
その結果にfをm回適用する関数を適用する

ここで「fをm回適用する関数」は(m f)で得られるので、纏めると

(define (+ m n) (lambda (f) (lambda (x) ((m f) ((n f) x)))))

Wikipedianに記載されているPLUSの定義を確かめる。

PLUS := λm n f x. m f (n f x)

ピリオドまでが引数、以降は左結合なので( (m f) (n f x))、(n f x)の部分は( (n f) x)と解釈されるので合っていそう。

ここで動作確認を行う為にxとして0を、fとしてincを使う事でチャーチ数を自然数に変換するeval-churchを定義。

(define (eval-church c)
  (define (inc x) (+ 1 x))
  ((c inc) 0))

まずは動作確認。

> (eval-church zero)
0
> (eval-church one)
1
> (eval-church two)
2
>

演算子+をadd-churchとして定義して評価してみる。

> (eval-church (add-church one two))
3
>

一応イケてそう。

*1:one f) x))))) (one f)の部分は：(lambda (x) (f x