SICP

SICP を読んでみる #79 第二章 p.110-117

本日も復習の続き。

2.5 汎用演算のシステム
異なる種類の引数に対して汎用な演算を定義する。

ユーザーに対しては add や sub といった共通の手続きが提供されていて、内部は加法的に拡張が可能になる。

2.5.1 汎用算術演算
put, get, apply-generic を駆使して汎用算術演算システムを構築していく。

2.5.2 異る型のデータの統合
異なる型のデータ間で演算をおこなう方法の考察。

型の組み合わせ毎に関数を用意していく方法→うまくいくが煩わしい

強制型変換
ある型のオブジェクトを他の型のオブジェクトとみなして演算をおこなう

型の階層構造
ある型を別の型に変換できなくても、両者を第三の型に変換することで演算が可能になる場合もある。このような問題に対応するために、型の間の関係を利用する。

階層構造の不適切さ
型変換の上下が一意に決まるならいいが、そうでない場合も多々ある。

ここまでで復習おわり。明日から問題に戻ります。

SICP

SICP を読んでみる #78 第二章 p.99-110

今やっている部分がちょっと時間をかけすぎて全体像がボヤッとしてきてしまったのでページを戻りながら復習していきます。

2.4 抽象データの多重表現

データ抽象を用いることでデータの表現、演算、有理数を扱うプログラムといったレイヤ毎に分離し、複雑さを制御することができる。

ただし、この方法は十分ではない。

・同じものを別の形式を用いて表す
・異なる設計選択のものを共存できるようにする
・部品を加法的に用いて大きいシステムを組み立てる

ようなことを実現するための手法が必要。

→汎用手続きを構成する

・データをどう処理すればいいのか判断可能な、型タグを持つデータオブジェクトを用意する
・データ主導プログラミング

2.4.1 複素数の表現
複素数は複数の方法であらわすことができる

・直交座標形式
・極座標形式

別々の表現形式で作成されているライブラリを元に議論を進める。
各表現形式について real-part, imag-part, magnitude, angle という四つの選択子が実装されている。

この時点で、どちらの表現形式でも add-complex, sub-complex, mul-comples, div-complex は正常に動作することが保証される。

2.4.2 タグつきデータ
複数の表現形式を一まとめに扱う場合、それぞれを区別する必要がある。そのために、データにタグ付けをおこなう。
タグを管理するために attach-tag, type-tag, contents を定義する。

つけられたタグを元にどの手続きを使用してデータの処理をおこなうか振り分けるための、窓口になる関数を用意する。

2.4.3 データ主導プログラミングと加法性
型による振り分け:データの型を調べて適切な手続きを呼ぶ一般的戦略

2.4.2のような振り分け実装には幾つか弱点がある

・汎用インターフェース手続きは異なるすべての表現を知らなければいけない
・システム全体でどの手続きも同じ名前を持たないという保証をしなければいけない

→加法的ではない

システム設計を更に部品化する手段→データ主導プログラミング

型と演算を表にし、型から必要な演算を参照できるようする

put/get 手続きを用いてテーブルへの登録とテーブルからの参照ができると仮定して、実際の手続きと対応内容をひとまとまりにしたパッケージを定義する。

apply-generic は演算の名前と引数の型から必要な手続きを探し、作用させる。

※前述のパッケージで、put 時に引数の型をリストで渡していたり apply-generic の type-tags 変数で引数の型タグをリストとして取得しているのは、後から add や sub のような複数の引数を渡す演算に対応するため。

メッセージパッシング

今日の復習はここまで。明日は 2.5 汎用演算のシステムから。

SICP

SICP を読んでみる #77 第二章 p.117

問題解答

問2.83

  (put 'raise 'scheme-number
       (lambda (x)
         (let ((op (get-coercioin 'scheme-number 'rational)))
           (op v))))

こういうのを各パッケージに実装していく感じ?

→解答をみると、パッケージに含めないで機能を実装していた。これでいいのんか?

SICP

SICP を読んでみる #76 第二章 p.117

問題解答

問2.81
a. apply-generic 内で proc が見つかった時点で処理は終了するが、引数の型同士の演算が定義されていない場合に apply-generic が再帰的に呼ばれるようになってしまい処理がおわらない。

b. 同じ型の引数の強制型変換って、意味を感じられないような。。。?そもそも a. で無限ループすることが分かっているので意味がないどころかダメってことで FA?

c.ちょっと手抜き感はあるけど。

(define (apply-generic op . args)
  (let ((type-tags (map type-tags args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (if (= (length args) 2)
              (let ((type1 (car type-tags))
                    (type2 (cadr type-tags))
                    (a1 (car args))
                    (a2 (cadr args)))
                (let ((t1->t2 (get-coercioin type1 type2))
                      (t2->t1 (get-coercioin type2 type1)))
                  (cond (eq? type1 type2)
                        (apply proc (map contents args))
                        (t1->t2
                         (apply-generic op (t1->t2 a1) a2))
                        (t2->t1
                         (apply-generic op (t2->t1 a2)))
                        (else
                         (error "No method for these types"
                                (list op type-tags))))))
              (error "No method for these types"
                     (list op type-tags)))))))
SICP

SICP を読んでみる #74 第二章 pp.113-115

問2.80 は 2.79 と同じなのでパス。

本文

2.5.2 異なるデータの統合
整数と複素数の加算のように、異なる型間で演算をおこなう方法を定義する。
一つの方法は、型の組み合わせ毎に手続きを設計する方法。→非常に煩わしい。

強制型変換
型の組み合わせ毎に手続きを定義するのではなく、ある型を別の型に変換する方法を用意して、型変換を試みるようにする

SICP

SICP を読んでみる #73 第二章 p.113

大いにハマった問2.77も済んで、やっと前に進めます。

問題解答

問 2.78

(define (attach-tag type-tag contents)
  (if (eq? type-tag 'scheme-number)
      contents
      (cons type-tag contents)))

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

(define (contents datum)
  (cond ((number? datum) datum)
        ((pair? datum) (cdr datum))
        (else (error "Bad tagged datum -- CONTENTS" datum))))

この方法は場当たり的な感じがしてちょっと嫌な感じがするかな。

問 2.79
equ? の大元を定義。

(define (equ? x y) (apply-generic 'div x y))

install-scheme-number-package に追加

  (put 'equ? '(scheme-number scheme-number)
       (eq? x y))

install-rational-package に追加

  (define (equ? x y)
    (if (not (eq? (numer x) (numer x)))
        #f
        (if (not (eq? (denom x) (denom x)))
            #f
            #t)))
  (put 'equ? '(rational rational)
       (lambda (x y) (equ? x y)))

※先人の知恵と比較したら、±の判別が甘かった

  (define (equ?-rat x y)
    (or (and (= (numer x) (numer y)) (= (denom x) (denom y)))
        (and (= (numer x) (- (numer y))) (= (denom x) (- (denom y))))))

install-rectangular-package に追加

  (define (equ? x y)
    (if (not (eq? (magnitude x) (magnitude y)))
        #f
        (if (not (eq? (angle x) (angle y)))
            #f
            #t)))
  (put 'equ? '(rectangular rectangular)
       (lambda (x y) (equ? x y)))

install-complex-package に追加

  (define (equ? x y)
    (if (not (eq? (real-part x) (real-part y)))
        #f
        (if (not (eq? (imag-part x) (imag-part y)))
            #f
            #t)))
  (put 'equ? '(complex complex)
       (lambda (x y) (equ? x y)))

以上。自分の解答では if をネストしているのがダサい。 and や or を使うべし。

SICP

SICP を読んでみる #72 第二章 p.113

問題解答以前にコードの動作確認ができなくてハマっている問題 2.77。今日こそは片をつけたいものです。
やっぱり、こうなったときにデバッガが無いのは辛いですね、、、

問題解答

問 2.77
さんざん悩んだ挙句、解決。

(define op-table (make-hash-table 'equal?))

(define (put op type item)
    (if (not (hash-table-exists? op-table op))
        (hash-table-put! op-table op (make-hash-table 'equal?)))
    (let ((type-table (hash-table-get op-table op)))
      (hash-table-put! type-table type item)))

(define (get op type)
    (if (not (hash-table-exists? op-table op))
        (hash-table-put! op-table op (make-hash-table 'equal?)))
    (let ((type-table (hash-table-get op-table op)))
      (hash-table-get type-table type)))

値の比較に、デフォルトの eq? を使っていたのがダメだったようです。

gosh> (equal? '(complex) '(complex))
#t
gosh> (eq? '(complex) '(complex))
#f

これはわからないです、、、ぐぬぬぬ。

その他にも typo でハマったりしたものの、やっと動作確認ができました。長かった、、、、、

そしてやっと本題。

(magnitude z) の評価される順番。

(define (magnitude z) (apply-generic 'magnitude z))

で apply-generic が呼ばれる。

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (error
           "No method for these types -- APPLY-GENERIC"
           (list op type-tags))))))

z は (complex rectangular 3.4) なので、type-tags は (complex)。
proc は complex package で定義した

    (put 'magnitude '(complex) magnitude)

で、最初に呼び出されたのと同じ magnitude が抽出される。
二度目の magnutude への引数(apply-generic への引数も同じ)は (map contents args) でタグを一つ剥がされたものなので (rectangular 3 . 4)。

apply-generic では type-tags が (rectangular)、 proc が rectangular package で定義された magnitude。
グローバルで定義されている magnitude との区別がわかりにくいので、便宜上 rectangular.magnitude としておく。

apply-generic で (rectangular.magnitude (3 . 4)) が呼ばれて無事に 5 が返ってくる。

よって、 apply-generic が呼ばれるのは 2 回。

SICP

SICP を読んでみる #71 第二章 p.113

昨日に引き続き問題 2.77 を解いていきます。

問題解答

問2.77
必要なプログラムを全部用意して、図 2.24 の z を用意するところまでは動作確認完了。
次は。。。ということで magnitude の動作確認をしようとしてエラー。どうやら Gauche 標準で用意されている magnitude が呼ばれて、期待したものが呼ばれていないっぽい。→2.4 にあった apply-generic まわりの定義をしていなかったのが原因。

。。。。そして、結局今日はうまく magnitude が実行できないところでハマって時間切れ。
やっぱり、わかってるからってヒョイヒョイ飛ばしてしまうと詰まった時に手戻りが辛いですね、、、、反省。

SICP

SICP を読んでみる #70 第二章 p.113

仕事の締切やらその後の溜まったタスクの消化やら集中力が続かないやら(これがほとんど)で気づけば一週間ぶりの SICP です。ここで途切れないように粛々と続けていきます。

今やっているあたりはプログラムを書いていれば当たり前な内容なので、問題をこなすためにモロモロの準備をするのが結構ダルいというのもあって微妙に乗り気になれないのがテンション低めな原因です。かと言って、問題をこなしたらこなしたでいろいろ発見があるので飛ばすわけにはいかないんですね。

問題解答

問 2.77
いい加減 put/get が手元のないとどうしようもないので先人の知恵を借りよう。。。。とおもったらひげぽんさんの記事につきあたる。同じ所まで同じ教科書で勉強してみてわかるけど、この人すごいな、、、、数倍のスピードで数倍以上の習得度があるorz。これだけの差をガツンと目の前に突きつけられると凹む。→記事を最後まで読んだら、問題2.74 をやるのに3時間くらいって書いてありました。成果とかかった時間がわかるとすごくいい目安になります。

この問題がおわったら、これまでのふりかえりともあわせてここまでのひげぽんさんの記事と自分の理解した内容を突き合わせよう。

ひげぽんさんの作った put/get はこちら。

(define op-table (make-hash-table))

(define (put op type item)
    (if (not (hash-table-exists? op-table op))
        (hash-table-put! op-table op (make-hash-table)))
    (let ((type-table (hash-table-get op-table op)))
      (hash-table-put! type-table type item)))

(define (get op type)
    (if (not (hash-table-exists? op-table op))
        (hash-table-put! op-table op (make-hash-table)))
    (let ((type-table (hash-table-get op-table op)))
      (hash-table-get type-table type)))

get って、op がなかったら結局 type を取得する時にエラーになるから

(define (get op type)
    (let ((type-table (hash-table-get op-table op)))
      (hash-table-get type-table type)))

これでも同じなんじゃないだろうか?

とにかく、これで put/get が手に入ったので問題にとりかかります。

(put 'real-part '(complex) real-part)

これが get されたときの挙動を確認。”‘(complex)” の部分がよくわからない。
そもそも complex がどこで定義されていたっけ? →単に (complex) というリストを作っているだけだった。このレベルで忘れているとは、、、、

そもそも (make-complex-from-real-imag 3 4) が正常に動かない。調べると op-table に ‘make-from-real-imag は登録されているものの、その先が空っぽいんだけど何故!?

ちょっと時間がかかりすぎたので今日はここまで。明日再チャレンジ。