読者です 読者をやめる 読者になる 読者になる

SICP 孤読書会 - 2.1 データ抽象入門 (2.1.1 〜 2.1.4)

データ抽象(data abstraction)は、合成データオブジェクトの使い方を、それが基本的データによりどう作られたかの細部から隔離する技法。

データ抽象の基本的な考えは、プログラムを合成データオブジェクトを使うように構成し、「抽象データ」を操作するようにすること。

  • プログラムはデータを、当面の仕事を実行するのに必要でないデータについては何も仮定しないよう使うべき。
  • データ表現は、データを使うプログラムから独立に定義すべき。


2.1.1 例: 有理数の算術演算

有理数を使った算術演算を元にデータ抽象について考える。

有理数の足し算、引き算、掛け算、割り算と2つの有理数が等しいかをテストをしたい。

分子と分母から有理数を作る方法、有理数から分子や分母を取り出す(選択する)方法があると仮定して始める。

  • (make-rat n d): 分子が整数 n, 分母が整数 d の有理数を返す。
  • (numer x): 有理数 x の分子を返す。
  • (denor x): 有理数 x の分母を返す。

make-rat, numer, denor の実装により有理数がどう表現されているかはまだ話していない。
それでもこの3つの手続きがあれば、

有理数の足し算、引き算、掛け算、割り算と2つの有理数が等しいかをテストをしたい。

を手続きとして表すことができる。

(define (add-rat x y)
  (make-rat (+ (* (number x) (denom y))
               (* (number y) (denom x)))
            (* (denom x) (denom y))))

(define (sub-rat x y)
  (make-rat (- (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

(define (mul-rat x y)
  (make-rat (* (numer x) (numer y))
            (* (denom x) (denom y))))

(define (div-rat x y)
  (make-rat (* (numer x) (denom y))
            (* (denom x) (numer y))))

(define (equal-rat? x y)
  (= (* (numer x) (denom y))
     (* (numer y) (denom x))))

データ抽象の具体的な実装をするために、基本的手続き cons で構成される対(pair)という合成構造を利用する。

(define x (cons 1 2))
(car x)   ; 1
(cdr x)   ; 2

car, cdr の基本的手続きを使って対からデータを取り出すことが出来る。
対で構成するデータオブジェクトをリスト構造(list structured)データという。

有理数の表現

対(cons)を使って有理数を表現することができる。

構成子(constructors)

(define (make-rat n d) (cons n d))

選択子(selectors)

(define (numer x) (car x))
(define (denom x) (cdr x))

これにより、インタフェースとして先に実装していた add-rat, sub-rat, mul-rat, div-rat, equal-rat? を利用し、有理数演算を実行できるようになる。


問題 2.1

SICP/ch2/2-1.scm at master · snufkon/SICP · GitHub

に解答。


2.1.2 抽象の壁

2.1.1 の有理数の例には、複数のレイヤーが存在する。

=================== 有理数を扱うプログラム ========================

====================== add-rat sub-rat ...  ===================

===================== make-rat numer denom ====================

======================= cons car cdr ==========================

水平の線がシステムの異なる「レベル」を隔離する抽象の壁(abstraction barrier)
各レベルの手続きは、抽象の壁を定義し、異なるレベルを接続するインターフェースとなる。

抽象の壁により、

  • それぞれのレベルでは、データ抽象を使う(上位)のプログラムを、データ抽象を実装する(下位)のプログラムから分けている。
  • プログラムの維持、修正が容易になる。


問題 2.2, 2.3

SICP/ch2/2-2.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-3.scm at master · snufkon/SICP · GitHub

に解答を追加。


2.1.3 データとは何か

データは「選択子構成子と、これらの手続きを有効な表現とするために満たすべき条件とで定義される」
(厳密に定義するのは難しいけど。)

有理数の場合、

選択子: numer, denom
構成子: make-rat
条件: 任意の整数 n と任意の零でない整数 d について、x が (make-rat n d) なら

(numer x) / (denom x) = n / d

を満たす。

対の場合、

選択子: car, cdr 構成子: cons 条件: 任意のオブジェクト x と y について z が (cons x y) なら (car z) は x であり、(cdr z) は y である。


問題 2.4 〜 2.6

SICP/ch2/2-4.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-5.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-6.scm at master · snufkon/SICP · GitHub

に解答を追加。

2.6 が難しかった。


2.1.4 拡張問題: 区間算術演算

スルーしました。


SICP 孤読書会のメインページはこちら

計算機プログラムの構造と解釈

計算機プログラムの構造と解釈