先月末は旅行に行ったり、その旅行の間に滞った仕事をさばいたり月末締切のモロモロをやっつけたりで全く手がつけられなかったです。いくら忙しくても何とか時間を取ってちょっとづつでも進められるようにしないといけないですね。ということで三週間ぶりに気を取り直して再開。

三週間ぶりだとさすがにどこまで何をやったか忘れてしまっているので復習からやらないとです。学生時代、夏休みとか平気で二か月くらい勉強しない期間があったんですが、今思うと恐ろしいです。二か月も何もしなかったら全部綺麗に忘れちゃいますよね、、、、

本文

2.5.3 記号代数から。

SICP の文章、久しぶりに読むと全然頭に入ってこないです(汗。過去のメモを見つつ整理。

2.5.3 記号代数の続き。

本文

多項式の演算を要素毎に分解して考える。

加算 : 同じ次数の項の組み合わせ
(5x^2+3x+7) + 3x → 5x^2 + ((3+3)x) + 7 → 5x^2 + (6x) + 7

乗算 :
(5x^2+3x+7) × 3x → (5x^2)×3x + 3x×3x + 7×3x → 6x^3 + 9x^2 + 21x

一通り実装がおわって汎用算術演算システムへの組み込みがおわると add/mul を用いて多項式演算を自動的に扱うことができるようになる。
これはちょっと感動。

問2.86 はちょっと気力切れでパス。ぐぬぬ。

本文

2.5.3 例:記号代数
多項式の算術演算をするシステムの設計をおこなう

不定元:変数のこと

話を簡単にするために一元多項式を扱う→(y^2+1)*x^3+(2y)*x+1 も一元多項式の組み合わせということでいいのかな?

今回は 5x^2+3x+7 と 5y^2+3y+7 は別のものとして扱う(構文形式として扱う)

復習もおわったので問題に戻ります

問題解答

問2.84
問題を前にして考えるものの、どうにも手が動かないので先人の知恵を借りて学習することに。”二つの型のいずれが塔の中で高いかをテストする”というのがイマイチ思い浮かばない。

Python ならリストに入れてインデックスで調べるとか、辞書に入れて優先順位をつけたタグで調べるとかできるんだけど。
そもそも、 Gauche 標準機能だとリスト中で指定した値が格納されているインデックスを取るっていう直接の方法が無いのか。
先人の知恵を見ても、自分で作っている。

;塔の順序リスト
(define tag-tower '(scheme-number rational real complex))

;指定したタグのインデックスを返却
(define (index tag)
  (let ((order (member tag tag-tower)))
    (if (eq? #f order)
      (error "No match type -- HIGHER~INDEX?" tag)
        (- (length tag-tower) (length order)))))

“等しい”っていうのが場合によって異なるから定義できないってことなのかな?
レベルの高いタグを返す本体はこんな感じ。

(define (higher? x y)
  (let ((idxx (index x))
        (idxy (index y)))
    (if (< idxx idxy)
        x
        y)))

apply-generic はこんな感じになるのかな(コードは書いたけど実行はしていない)

(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)))
                (if (eq? type1 type2)
                    (apply proc (map contents args))
                    (if (eq? (higher? type1 type2) type1)
                        (apply-generic op a1 (raise a2))
                        (apply-generic op (raise a1) a2))))
              (error "No method for these types"
                     (list op type-tags)))))))

問2.85
こんな感じで project を各パッケージ毎に定義して、drop を定義するのかな。

(define (complex->scheme-number x)
	(make-scheme-number (real-part (contents x))))

(put 'project 'complex complex->scheme-number)

(define (project x)
  (apply-generic 'project x))

(define (drop x)
  (let ((p (project x)))
    (let ((r (raise p)))
      (if (eq x r)
          p
          x))))

本日も復習の続き。

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

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

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

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

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

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

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

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

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

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

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 汎用演算のシステムから。

問題解答

問2.83

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

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

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

問題解答

問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)))))))

本文

型の階層構造
型に階層構造を取り入れ、演算が可能になるまで型の変換をおこなって上位レベルに移動していく。
同様に、必要に応じて最簡な表現まで降ろすこともできる。