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

SICP 孤読書会 - 2.4 抽象データの多重表現 (2.4.1 〜 2.4.3)

SICP

この節では、プログラムの内部実装が、異なる方法で表現されている可能性があるデータにどう対処するかを勉強する。

そこで必要となる

  • 汎用手続き(generic procedure)
  • 型タグ(type tag)
  • データ主導(data directed) プログラミング

についても述べる。


2.4.1 複素数の表現

汎用演算を使うプログラムとして、複素数の算術演算を実行するシステムの開発を考える。

複素数は2つの表現を持つことができる。

  • 直交座標形式(実部と虚部)
  • 極座標形式(絶対値と偏角)

複素数の加算(減算)では、実部と虚部による直交座標形式を使った考え方が適する

Real-part(z1 + z2) = Real-part(z1) + Real-part(z2)
Imaginary-part(z1 + z2) = Imaginary-part(z1) + Imaginary-part(z2)

複素数の乗算(除算)では、絶対値と偏角による極座標系式での表現を使った考え方が適する

Magnitude(z1・z2) = Magnitude(z1)・Magnitude(z2)
Angle(z1・z2) = Angle(z1)・Angle(z2)

複素数の演算に対して、4つの選択子と2つの構成子

  • 選択子
    • real-part
    • imag-part
    • magnitude
    • angle
  • 構成子
    • make-from-real-imag (実部と虚部で指定した複素数を返す)
    • make-from-mag-ang (絶対値と偏角で指定した複素数を返す)

が実装済みであると仮定すると抽象データを使った複素数の算術演算を実装することができる

(define (add-complex z1 z2)
  (make-from-real-imag (+ (real-part z1) (real-part z2))
                       (+ (imag-part z1) (imag-part z2))))

(define (sub-complex z1 z2)
  (make-from-real-imag (- (real-part z1) (real-part z2))
                       (- (imag-part z1) (imag-part z2))))

(define (mul-complex z1 z2)
  (make-from-mag-ang (* (magnitude z1) (magnitude z2))
                     (+ (angle z1) (angle z2))))

(define (div-complex z1 z2)
  (make-from-mag-ang (/ (magnitude z1) (magnitude z2))
                     (- (angle z1) (angle z2))))

最初に述べたように複素数は、直交座標形式、極座標系式のどちらでも表現することができる

直交座標形式で表現

(define (real-part z) (car z))
(define (imag-part z) (cdr z))
(define (magnitude z)
  (sqrt (+ (square (real-part z)) (square (imag-part z)))))
(define (angle z)
  (atan (imag-part z) (real-part z)))
(define (make-from-real-imag x y) (cons x y))
(define (make-from-mag-ang r a)
  (cons (* r (cos a)) (* r (sin a))))

z は複素数(直交座標形式で表現されている)

極座標形式で表現

(define (real-part z)
  (* (magnitude z) (cos (angle z))))
(define (imag-part z)
  (* (magnitude z) (sin (angle z))))
(define (magnitude z) (car z))
(define (angle z) (cdr z))
(define (make-from-real-imag x y)
  (cons (sqrt (+ (square x) (square y)))
        (atan y x)))
(define (make-from-mag-ang r a) (cons r a))

z は複素数(極座標で表現されている)

先に定義した複素数の算術演算(add-complex, sub-complex, mul-complex, div-complex)は どちらの複素数表現を利用しても問題なく動作する。

2.4.2 タグ付きデータ

複素数の具体的表現(直交座標系式、極座標系式)の決定を伸ばすことができれば、システム設計の柔軟性を最大に保つことができる。
最終的に両方の表現を使うと決定することもできる。

それぞれの複素数型タグ(type tag)をつけることで、両方の表現を1つのシステムに組み込むことが可能となる。

タグつきデータを操作するため、

  • attach-tag: タグ付きデータを作る手続き
  • type-tag: タグを取り出す手続き
  • contents: 実際の内容を取り出す手続き

を定義する

(define (attach-tag type-tag contents)
  (cons type-tag contents))

(define (type-tag datum)
  (if (pair? datum)
      (car datum)
      (error "Bad tagged datum -- TYPE-TAG" datum)))

(define (contents datum)
  (if (pair? datum)
      (cdr datum)
      (error "Bad tagged datum -- CONTENTS" datum)))

これらを使い、複素数が直交座標形式、極座標形式のどちらを持つか判定する定義

(define (rectangular? z)
  (eq? (type-tag z) 'rectangular))

(define (polar? z)
  (eq? (type-tag z) 'polar))

を書くことができる。

型タグを使った直交座標表現

(define (real-part-rectangular z) (car z))

(define (imag-part-rectangular z) (cdr z))

(define (magnitude-rectangular z)
  (sqrt (+ (square (real-part-rectangular z))
           (square (imag-part-rectangular z)))))

(define (angle-rectangular z)
  (atan (imag-part-rectangular z)
        (real-part-rectangular z)))

(define (make-from-real-imag-rectangular x y)
  (attach-tag 'rectangular (cons x y)))

(define (make-from-mag-ang-rectangular r a)
  (attach-tag 'rectangular
              (cons (* r (cos a)) (* r (sin a)))))

型タグを使った極座標表現

(define (real-part-polar z)
  (* (magnitude-polar z) (cos (angle-polar z))))

(define (imag-part-polar z)
  (* (magnitude-polar z) (sin (angle-polar z))))

(define (magnitude-polar z) (car z))

(define (angle-polar z) (cdr z))

(define (make-from-real-imag-polar x y)
  (attach-tag 'polar
               (cons (sqrt (+ (square x) (square y)))
                     (atan y x))))

(define (make-from-mag-ang-polar r a)
  (attach-tag 'polar (cons r a)))

2.4.1 で仮定した汎用手続き real-part, imag-part, magnitude, angle は タグを調べ、その型のデータを扱う手続きを呼ぶ手続きとして実装することができる。

(define (real-part z)
  (cond ((rectangular? z)
         (real-part-rectangular (contents z)))
        ((polar? z)
         (real-part-polar (contents z)))
        (else (error "Unknown type -- REAL-PART" z))))

(define (imag-part z)
  (cond ((rectangular? z)
         (imag-part-rectangular (contents z)))
        ((polar? z)
         (imag-part-polar (contents z)))
        (else (error "Unknown type -- IMAG-PART" z))))

(define (magnitude z)
  (cond ((rectangular? z)
         (magnitude-rectangular (contents z)))
        ((polar? z)
         (magnitude-polar (contents z)))
        (else (error "Unknown type -- MAGNITUDE" z))))

(define (angle z)
  (cond ((rectangular? z)
         (angle-rectangular (contents z)))
        ((polar? z)
         (angle-polar (contents z)))
        (else (error "Unknown type -- ANGLE" z))))

汎用演算子が polar 型 の数に演算するときは、タグを剥がし 極座標表現を扱うプログラムに渡す。
逆に汎用演算として複素数を構成するときは、極座標表現を使うプログラムで polar 型のタグを付ける。

データオブジェクトをレベルからレベルへ渡すとき、タグをつけ剥がしすることは重要な組織化戦略となる。
(2.5節で詳しく扱う)


2.4.3 データ主導プログラミングと加法性

データの型を調べ、適切な手続きを呼び出す一般的戦略は型による振り分け(dispatching on type)という。
システム設計で部品化を実現する強力な戦略となる。

2.4.2 節の振分け実装には2つの弱点がある

  • 汎用インターフェース手続き(real-part, imag-part, magnitude, angle) は異なる表現のすべてを知らなければならない
  • それぞれの表現はシステム全体でどの二つの手続きも同じ名前を持たない保証をしなければならない

汎用インターフェースの実装が加法的(additive)ではない。

システム設計を更に部品化する手段が必要。 データ主導プログラミング(data-directed programming)というプログラム技法が役に立つ。

データ主導プログラミングは、一方の軸に演算、他方の軸に型をとった二次元の表を扱っているとみなすことができる。

Polar Rectangular
real-part real-part-polar real-part-rectangular
imag-part imag-part-polar imag-part-rectangular
magnitude magnitude-polar magnitude-rectangular
angle angle-polar angle-rectangular

表の項目は各引数の型に対し、各演算が実装する手続きを表す。

表から演算名と引数の型の組合せを探し、作用させる正しい手続きを見つけ、 それを引数の内容に作用させる単一の手続きとしてインターフェースを実装する。

こうすることにより、新しい表現を追加する際、既存の手続きを変更する必要はなく、表に新しい項目を追加するだけとなる。 汎用インタフェースの実装が加法的となる。


問題 2.73 〜 2.76

SICP/ch2/2-73.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-74.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-75.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-76.txt at master · snufkon/SICP · GitHub

に解答を追加。


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

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

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