mrasu’s blog

読んだ物の内容など

算機プログラムの構造と解釈(2章)

「計算機プログラムの構造と解釈(SICP)」の2章です

必要なものを関数化して抽象レベルを上げます。

  1. 別型に共通インターフェースをつける、各型を区別できるようにする
  2. 各要素を区別できるようにする
  3. 型変換ができるようにする

とすれば、共通インターフェースを通して同一のもののように扱うことができるというところまで持っていけます。
オブジェクト指向ポリモフィズムです。

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

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


2章 データによる抽象の構築

2.1 データ抽象入門

2.1.1 有理数の演算

以下の手続きを仮定する

  1. (make-rat <n> <d>): 分子 <n> と分母<d>で仮定された有理数を返す
  2. (numer <x>): 有理数<x>の分子を返す
  3. (denom <x>): 有理数<x>の分母を返す

すると、以下の演算を定義できる
0. 加算
0. 減算
0. 乗算
0. 除算
0. 比較

また、対(pair)という合成データ要素が存在し、以下の手続きを定義されている。

  1. (cons <a> <b>): <a>と<b>をデータに持つpairを返す
  2. (car <x>): pair <x> の前半(cons における<a>部分) を返す
  3. (cdr <x>): pair <x> の後半(cons における<b>部分) を返す

これは、有理数を表すのに適したデータ形式である。
pairを基に先に仮定した3つの手続き(有理数を作成する。分子を返す。分母を返すの3つ)を実装する

  1. 有理数を作成する。
  2. 分子を返す。
  3. 分母を返す

また、デバッグ目的として有理数を表示する関数も定義する

2.1.2 抽象の壁

有理数の実装では、

  • consという事前に用意された、2つの値を保持するデータ
  • consを利用した有理数
  • ratを利用した演算利用できる有理数

という3層に分かれる。
どの層も1つ下の層のみを参照する。
これにより、実装の変更が容易になる。

2.1.3 データとは何か

データは

  1. 選択子(selector) (抽象データ。プログラムから利用される)
  2. 構成子(constructor) (具体的データ表現。選択子が内部的に使用する)
  3. データとして有効な条件

を持つものと定義できる

2.2 データ構造と閉方性

2.2.1 並びの表現

cons の短縮形がlist

(cons (1 cons (2 cons 3 (cons 4 ()))))

(list 1 2 3 4)

リストの内容を取得したいなら、cdrを繰り返せばよい。

  1. n番目を取得する
  2. 長さを取得する
  3. 連結(第1引数の最終要素と第2引数をつなげる)

写像をつくるなら、各項目を訪れてその項目に影響を与えればよい

2.2.2 階層構造

ツリー構造に対してもできる

  1. 長さ
  2. 写像(定数倍)
  3. map

2.2.3 公認インターフェース(conventional interfaces)としての並び

信号処理により、処理を切り離す。

  • フィルタ
  • 計算
  • 要素の取得
    1. 範囲
    2. ツリー

2.3 記号データ

2.3.1 クォート

クォート(')をつけると値が評価されない。
(価値がよくわからない)

微分

関数定義

  • variable? 変数かどうか
  • same-variable? 同じ変数か
  • sum? 和か
  • addend 加数
  • augend 被加数
  • make-sum 和を構成する
  • product? 積か
  • multiplier 乗数
  • multiplicand 被乗数
  • make-product 積を構成

集合

集合を定義する

  • 要素があるか
  • 追加
  • 交差

Huffman符号化木

  • 複合化

2.4 抽象データの多重表現

プログラム内で異なる方法で表現されているデータに対処するために、汎用手続(generic procedure)の話が本節

2.4.1 複素数の表現

複素数を直交座標と極座標で表現できるようにする

  • 加算
  • 減算
  • 積算
  • 除算

これらを、2つの方法で定義できる

  1. 直交座標を基にして複素数を表現する
  2. 極座標を基に表現する

2.4.2 タグつきデータ

両者を同時に実装する場合は

  1. どちらかを判断するためにタグをつける
  2. 各要素取得関数を外部から秘匿する
  3. 複素数作成用を定義する

これによって、既存の算術演算が直交座標・極座標の別を意識せずに動く

2.4.3 データ手動プログラミングと加法性

型タグによる振り分けには弱点がある

  1. 新しい表現を作成した場合は、既存の汎用手続き全てに分岐を追加する必要がある
  2. 名前の衝突を防ぐ必要がある

これでは大変なので、

  1. 呼び出す関数を型に依って変化するようにする
  2. 演算に外からアクセスできるようにする

これで、複素数に対する新しい表現が追加されても既存のものを修正する必要がなくなった。

2.5 汎用演算のシステム

2.5.1 汎用算術演算

有理数複素数(直交座標・極座標)の以下の演算を抽象化する

  1. 加算
  2. 減算
  3. 積算
  4. 除算

2.5.2 異なる型のデータ統合

各演算が抽象化できたので、強制型変換(coercion)によるデータ変換ができる