SICP 2 Building Abstractions with Data - プログラミング再入門

第１章では手続きの作り方、性質、抽象化・一般化の方法を学びましたが、この章はデータ構造の話な模様。

ノート

例えば有理数を扱う場合、分子・分母のペアを一塊のデータとして扱えるとプログラムがすっきり書ける。複合データが内部的にどう表現されていてそれをどう扱うのかと言う部分と、複合データをひと纏まりに捉えてどう計算を行うのかを扱う部分とが分離出来る。データ抽象化と呼ぶ。
ax+byを計算する手続きが、a、b、x、yの表現に依存せずにプログラムが書けるべき。
特別なデータ構造を使わずに手続きを使っても複合データは作れる。これでますます手続きとデータの区別がつかなくなって来る。
この時点ではsymbolic expressionsが具体的に何を表しているのかは分からない。シンボルで表現された数式？
最後にgeneric operations（総称関数）の紹介で、データの表現方法に応じて同じプログラムが異なる演算を行う仕組みを取り上げる。しかも元のプログラムを変更せずに新しいデータ型へ対応出来る様にする必要がある。

2.1 Introduction to Data Abstraction

データ抽象化への導入。
データ抽象化は、データがどの様に構成されているかとそのデータがひと塊としてどの様に使われるかを分離する。
抽象化されたデータにアクセスする為にselectorとconstructorと呼ばれる手続きを用意する。

2.1.1 Example: Arithmetic Operations for Rational Numbers

例：有理数の算術演算

We are using here a powerful strategy of synthesis: wishful thinking.

「希望的観測」を以て当たる。
make-rat、numer、denomの実装を知らなくても、これらが用意されていると言う仮定でプログラムを組む事は出来る。実行は出来ないけど。

Pairs

ペア。
cons cellとかdotted pairと呼ばれるもの。
例を実行してみる。

> (define x (cons 1 2))
> x
(1 . 2)
> (car x)
1
> (cdr x)
2
> (define y (cons 3 4))
> (define z (cons x y))
> z
((1 . 2) 3 . 4)
> (car (car z))
1
> (car (cdr z))
3
>

Data objects constructed from pairs are called list-structured data.

リスト構造。あるいは単にリスト。

Representing rational numbers

有理数を表現する。存在しているペアを変更するのではなく毎回の計算で新しいratを作っている。関数型っぽい。
実行してみる。

> (define one-half (make-rat 1 2))
> (print-rat one-half)

1/2
> (define one-third (make-rat 1 3))
> (print-rat (add-rat one-half one-third))

5/6
> (print-rat (mul-rat one-half one-third))

1/6
> (print-rat (add-rat one-third one-third))

6/9
>

print-ratの最初にnewlineがあるので空行が出来る。
次に、約分するmake-ratの実装。

> (define one-third (make-rat 1 3))
> (print-rat (add-rat one-third one-third))

2/3
>

前回、6/9と表示されていた物が約分されて2/3と表示されている。
データの表現方法は変わってはいないもののデータの作り方を変えた。でも演算の為の関数等は一切変える必要は無い。

Exercise 2.1

符号も考慮する。
numeratorとdenominatorを掛けて、負であれば負、正であれば正。それぞれのnumeratorとdenominatorは絶対値にして、結果の符号をnumeratorにのみ掛ける。

(define (make-rat n d)
  (let ((sign (if (< (* n d) 0) -1 1))
        (g (gcd n d)))
    (cons (* sign (/ (abs n) g)) (/ (abs d) g))))

実行してみる。

> (print-rat (make-rat 2 10))

1/5
> (print-rat (make-rat -2 10))

-1/5
> (print-rat (make-rat 2 -10))

-1/5
> (print-rat (make-rat -2 -10))

1/5
>