｢3.3.3 表の表現｣ということで、set-car!/set-cdr!を内部的に使いながら、テーブルの要素を追加・更新・削除できるようなデータ構造を構築していきます。 問題3-24では、｢キーに該当する要素｣を見つけるときに、equal?で厳密にチェックするのではなく、何ら…

キューに関する問題です。先頭・最後尾の対や前後の対を指し示すポインタを操作する練習でもあります。 問題3-21では、例文に掲載されている手続きで作成したキューを、視覚的にわかりやすく印字するためのメソッドを定義します。front-queueをそのまま使っ…

｢3.2 評価の環境モデル｣の節では、手続きがどのように評価されていくのかということについての新しい見方が提示されています。2〜3日かけて何度もじっくり読んでみました。置換えモデルは、カッコの中身を展開していって、元の手続きへ収束していくようなイ…

｢3.3 可変データでのモデル化｣の節に入りました。 問題3-12で、append!の動きを確認します。 (define (append! x y) (set-cdr! (last-pair x) y) x) (define (last-pair x) (if (null? (cdr x)) x (last-pair (cdr x)))) (define x (list 'a 'b)) (define y …

対が指す場所が等しいのか、データを指している対は同一なのか否か、ということに対する考察を深めていく部分です。 問題3-15は、set-to-wow!の効果を説明せよとのことです。 (define (set-to-wow! x) (set-car! (car x) 'wow) x) (define x (list 'a 'b)) (…

｢3.1.3 代入を取り入れた代価｣では、関数型プログラミングと命令型プログラミングの違いや、｢同一｣｢変化｣など重要なキーワードについて語られていて、非常に示唆に富んだ節だと感じました。本書の後続の部分で何かにつまずいたら、ここに戻ってこようとも思…

｢3.1.2 代入を取り入れた利点｣ということで、代入や局所変数という概念を使うことによる利点が述べられています。例えば、ランダムな値を引き出す手続きとして、(random x)のように何らかの引数を指定するのか、(rand)のようにrand手続きの中の局所変数を繰…

第三章に入りました。最初は代入に関する練習問題です。 問題3-1のアキュムレータ手続きです。 (define (make-accumulator init) (let ((sum init)) (lambda (x) (begin (set! sum (+ sum x)) sum)))) (define A (make-accumulator 5)) (A 10) ;=>15 (A 10) …

問題2-92以降については、問題文は読んでみたものの、コードを書いたとしてもそれが正しいかを検証するための数学的な知識が自分には足りていないと思ったので、今回は解くのをあきらめました。これでひとまず第二章は終了です。 かなり前から使っていたよう…

｢2.5.3 例：記号代数｣に入りました。多項式の算術演算を扱えるパッケージを定義します。polynominal型の構成要素は、一つの不定元と、各次数に関連づけられている係数の組み合わせのリストです。 本書に書いてあるパッケージ手続きを愚直に書いた上で、問題2…

一元多項式の除算を定義します。問題文を読みながら、商と剰余を求めるための数式を紙に書いて、何となく流れはわかりました。しかし、それを実装する段階で、商と剰余のリストをどのように返していいのかわからず、ウェブで模範解答を探したところ、ここに…

｢整数->有理数->実数->複素数｣というように、各型を拡大解釈するための順序が存在する場合、型のレベルを一段上げるための手続きraiseを定義してやれば、強制型変換ロジックを汎用化することができます。この中で、｢実数｣に関しては、これまで扱ってこなかっ…

raiseを使ってapply-genericを改善します。これによって、get-coercion/put-coercionやt1->t2のような型変換のベタ書きを排除することができます。まずは、オブジェクトツリーの各要素に自身のレベルを表す値を返すような手続きを追加しました。 ;(define (t…

型を単純化するdrop手続きを定義します。この問題に関しては、結構手間取った割には、まだまだ完全な解答を導きだせておらず、またこれまでのequ?やraiseの実装方法に重大な誤りがあったことを発見しました。 まずは、dropのインターフェイスを定義します。 …

複数の異なるデータ型を演算できるように機能追加していきます。まずは、Louis Reasonerの仮説が正しいかどうかを確認していきます。 (define (scheme-number->scheme-number n) n) (define (complex->complex z) z) (put-coercion 'scheme-number 'scheme-n…

昨日の続きです。まずは問題2-78。汎用演算のサンプルコードのままだと、単純な整数の数値を一つ作るためには、(make-scheme-number 3)みたいなことをやってscheme-numberのタグをつけなければなりません。この面倒臭さを解消するための問題です。タグつけの…

｢2-5 汎用演算のシステム｣の節に入りました。ここから先の問題に取り組むためには、本書に掲載されているコードを書かなければならず、それに結構時間がかかってしまいました。しかし、書いてみることで、今までの自分の理解不足を補えたという利点もありま…

put-get-genと問題2-74は時間をしっかりと作ってから取り組んでみようと思ってますので、次のメッセージパッシングの問題に進みます。 演算や型の定義をputを使って登録しつつ、getを用いて適用していくというやりかたではなく、型ごとに、その型で使われる…

いよいよ｢2.4 抽象データの多重表現｣の節に入りました。いかにソフトウェアを設計/実装すべきかということに対する多くのヒントを得られそうな予感がしています。 早速、問題2-73の記号微分を行なうプログラムの改修に取り組みました。しかし、putやgetは自…

Huffman符号化木に関する問題を解いています。可変長の符号をどのように定義して、decode/encodeをどのような処理で表現するのか、という点に面白味を感じました。以下は、本書に掲載されていた、Huffman木を作成する手続きと、decodeの手続きです。 (define…

まずは、Huffman符号化木を生成するための手続きを書きます。以下は、本書に掲載されていた例文で、記号とその重み付けの組み合わせリストから、Huffman-treeの葉の要素の並びを生成するロジックです。 (define (adjoin-set x set) (cond ((null? set) (list…

Huffman-treeを構成している記号が任意の数の場合、そこから生成される符号の大きさにどのような分布が見られるかを調べます。(問題2-71) (define 5-symbols '((a 1) (b 2) (c 4) (d 8) (e 16))) (encode '(a) (generate-huffman-tree 5-symbols)) ;=>(0 0 0…

集合に関する問題です。問題2-59のunion-setは以下のように実装しました。intersection-setにおけるelement-of-set?の使い方をちょっと変えるだけで表現することができます。 (define (union-set set1 set2) (cond ((null? set1) set2) ((null? set2) set1) …

集合を扱う問題の続きです。こんどは、集合を構成しているリストが順序付けらていたら、処理をどれだけ効率化することができるかを調べます。例題として、element-of-set?とintersection-setは以下のように表現されていました。 (define (element-of-set? x …

集合の要素を二進木で表現した場合に関する問題です。木の節の要素よりも値が小さければ左側へ、大きければ右側へという規則を設けることによって、木全体が釣り合っていれば、探索処理を対数的に効率化することができます。それらを表すための各手続きは、…

DBは、今日取り組んだような集合を扱うためのソフトウェアだと捉えると、どのような手続きでそれを表現できるか、ということを実験的に実装するのが問題2-66です。例題では、テーブルに収められているレコードのキーが、ただのリストとして管理されている場…

微分記号に関する問題の続きです。前回のエントリーの最後で、複数の要素を同じ括弧内で足し合わせられるようにするためには、ドット末尾記法を使えば良いんじゃないかと書きましたが、これは大きな勘違いでした。つまり、make-sumをする時に、a2が一つか複…

記号微分に関する問題です。quoteを使った記号表現だけで微分計算をやってしまうという点に面白味を感じました。まずは、本書に出てきた例文をコピペします。 (define (=number? exp num) (and (number? exp) (= exp num))) (define (variable? x) (symbol? …

約二ヶ月間、SICPから離れてしまいましたが、今日から徐々に再開していきたいと思います。手始めに第一章から第三章までを流し読みしました。二章の後半から三章にかけての部分は、今回初めて触れる内容でしたが、非常に面白そうな感触を受けることができ、…