きのこる庭

最終更新: 8/10 ( ~ 4.79 )

せっかくだからざっくりでも難易度書いていった方が 後から勉強する人が勉強しやすそうなので 今後問題解くと同時に難易度も書き残していくことにする。

< ご注意 >
・難易度に関しては完全に個人の主観となります。
参考までに僕個人のスペックを記載しておくと、高校2年の数2Bまで終わってるくらいのレベル感です。アカデミックな数学はパッパラパーです。
ただ、4章の難易度をつける上で明記しておくべき点として、C言語で簡単なコンパイラ・インタプリタを実装したことがあります(「再帰下降構文解析」などのメンタルモデルをイメージとしてぼんやり持っているため、もしかしたらコンパイラ・インタプリタ周りを学んでいるのと学んでいないのとで若干体感難易度に差が出てくるかもしれないです)。なお、コンパイラ・インタプリタの実装に関して参考にした文献は以下の通りです。

・また、各Exerciseの難易度に関しては そのExerciseの所まで勉強した時点でのスキルセット・理解度を想定した難易度を書くようにしています( つまり、既に後の章も勉強して記述に慣れた状態での難易度ではないので、前の章の★3つと後の章の★3つのレベル感が大きく異なります )。

第1章 難易度リスト
第2章 難易度リスト
第3章 難易度リスト
第4章 難易度リスト
第5章 難易度リスト

—

5.1 レジスタ計算機での計算

4.1.1 評価器の中核
　4.1 ★ (letを使う)
4.1.2 式の表現
　4.2 (a) ★ (ヒントの通りに考える)
　　　(b) ★★ (主に選択子・構成子を変更する)
　4.3 ★★★ (2.73(a)が参考になる)
　4.4 ★★★ (「左から右に評価」という条件を忘れずに)
　4.5 ★★★ (expand-clausesを修正)
　4.6 ★★★ (先にlambdaからの導出をつくると楽かも)
　4.7 ★★★★ (body部分にて条件分岐を行う。この辺りから曖昧な理解だと困難に)
　4.8 ★★★★ (make-begin を使用して listで定義と実行を組む)
　4.9 ★★★ (ifを活用)
　4.10 ★★★ (好きな形に構文を設計しなおす)
4.1.3 評価器のデータ構造
　4.11 ★★ (影響範囲を洗い出しておくこと)
　4.12 ★★ (絶対出ると思った。scanを共通化できる)
　4.13 ★★ (最初の要素はset-car!とset-cdr!を活用して削除)
4.1.4 評価器をプログラムとして走らせる
　4.14 ★★★ (脚注18でreadの返す値を確認。evalがそれをいかに解釈するかが鍵)
4.1.5 プログラムとしてのデータ
　4.15 ★★ (問題に書かれた手順通り)
4.1.6 内部定義
　4.16 (a) ★ (問題文通りにやるだけ)
　　　 (b) ★★★ (イテレーションが必要になる)
　　　 (c) ★★ (どちらでも良いが効率に違いがある)
　4.17 ★★★ (let を使わない形式に書き換える)
　4.18 ★★★ (a, b周りの解釈プロセスを実際に追って考えると良い)
　4.19 ★★ (脚注26が参考になる。手続きと変数を区別して考えると自然)
　4.20 (a) ★★ (これまで出てきた導出タイプの問題とさほど違いが無い)
　　　 (b) ★ (letの内部での再帰定義に着目する)
　4.21 (a) ★★ (factはエントリポイント、ftはイテレーションと考えるとfibをつくるのも簡単。こちらの記事が参考になった)
　　　 (b) ★ (a問題を理解していれば簡単)
4.1.7 構文解析を実行から分離する
　4.22 ★(analyzeのみ変更。letがlambdaからの導出と考えると…)
　4.23 ★★ (本文を見ると概ね理解できる)
　4.24 ★★★★ (debug用の環境を整えていないとちょっと面倒かも)

4.2 Schemeの変形—遅延評価

4.2.1 正規順序と作用的順序
　4.25 ★ (想像に容易い)
　4.26 ★★ (「構文」と「手続き」の違い。高階関数が鍵)
4.2.2 遅延評価の解釈系
　4.27 ★ (作用的順序, 正規順序における出力の違いを考える)
　4.28 ★ (thunkに関わる)
　4.29 ★ (いつもの木構造再帰)
　4.30 (a) ★
　　　 (b) ★
　　　 (c) ★ (基本手続きの扱い方が鍵)
　　　 (d) ★★★ (遅延評価の観点で議論ができる)
　4.31 Skipped
4.2.3 遅延評価リストとしてのストリーム
　4.32 ★ (遅延タイミングを考える)
　4.33 ★★ (クォート式の場合の評価を加える)
　4.34 ★★★★ (無限ストリームの印字をどう工夫するか)

4.3 Schemeの変形—非決定性計算

4.3.1 ambと探索
　4.35 ★ (an-integer-starting-fromと大体つくりは同じ)
　4.36 ★ (k がどんどん探索に入ってしまうのが問題なので…)
　4.37 ★ (特に迷う事無く解けると思う)
4.3.2 非決定性プログラムの例
　4.38 ★ (実際にコードサンプルが無ければ頭で考えても問題なさそう)
　4.39 ★ (解に関しては関数プログラミングの原点に立ち返ると良い)
　4.40 ★★(解くとわかるけど、答えが構造的には割と汚くて抽象化したくなる)
　4.41 ★★★ (順列の生成には permutations基本手続きが使える。あとはfilter)
　4.42 ★★★ (排他的論理和を実装する必要がある)
　4.43 ★★★★ (「誰がどのヨットの持ち主か」「誰の父が誰の娘か」を分離して考える)
　4.44 ★ (余裕で解けるが、回答は拡張性が無いし良いプログラムとは言えない)
　4.45 ★ (なお、一般的なコンパイラはこの曖昧さを禁止しているし、すべきである)
　4.46 ★ (想像に容易い)
　4.47 ★★ (解析のパターンが出尽くした後どうなるか)
　4.48 ★ (名詞句の例を参考に)
　4.49 ★★ (ambを使用する)
4.3.3 amb評価器の実装
　4.50 ★★★ (list-refとrandom-integerを使用。実装がちょっと面倒)
　4.51 ★ (analyze-assignmentをベースにすると楽)
　4.52 ★★★★ (これまでの手続きの構成を参考にする)
　4.53 ★ (想像に容易い)
　4.54 ★ (pred-valueを使用する)

4.4 論理型プログラミング

4.4.1 推論的情報探索
　4.55 ★ (4.4.1本文を参考に。さらっと解ける)
　4.56 ★★ (notの使い方に注意)
　4.57 ★★ (can-do-job条件をお忘れなく)
　4.58 ★★ (プログラムより論理の組み立てに注力した方が良い)
　4.59 ★ (特に悩む所は無い)
　4.60 ★★★★ (何かしらの「重み付け」を実装するという発想.コード自体は難しくない)
　4.61 ★ (特に迷う点は無い)
　4.62 ★ (問題文通りに)
　4.63 ★ (問題文通りに)
4.4.3 論理型プログラミングは数学的論理か
　4.64 ★ (notに関する問題で紹介されたフレームの未束縛問題が鍵)
　4.65 ★ (重複)
　4.66 ★ (重複部をフィルタリングする機構が必要)
　4.67 ★★★★★ (評価の履歴を保持する機構を実装する必要がある)
　4.68 ★★★ (移動する要素を一時的に保持する機構を作成する)
　4.69 ★★ (son-of が使える)
4.4.4 質問システムの実装
　4.70 ★ (ones無限ストリームは 1, 1, 1, … となる。つまり…)
　4.71 ★ (無限ループになる質問をつくればよい)
　4.72 ★ (3章でやった対の無限ストリームの特徴を思い出す)
　4.73 ★ (4.71と同様)
　4.74 ★★
　4.75 ★★★★
　4.76 Pass
　4.77 Pass
　4.78 Pass
　4.79 Pass

【概観】
・章全体を通して処理系の実装的な話。
・フレームへの変数の束縛・各フレームにおける評価を意識した構成になっている印象。
・問題自体は一部の難しいものを除いて これまでの章よりも比較的容易に解けるものが多かった。
・とはいえ、本文の解説を完全に理解できたかどうかと問われると微妙。
・処理系の全容を定性的には理解できた(評価器ごとの字句解析、構文解析 等々)。
・これまでの章ではDrRacketでも 処理系を変えたりライブラリを参照したりでなんとかデバッグできていたが、4章あたりからはデバッグが困難になっており、所々デバッグのできない状態での進捗があったため理解度としては若干ふわふわしている感が否めない。
・抽象度が相当高くなっているため、具体的な実装からコツコツ攻めようとすると頭のメモリが枯渇する。幸いSICPの構成が インタフェースとなる手続きを先に出してその後詳細をつかんでいくような仕組みになってくれてはいる。
・amb、不完全性計算、推論系の話は面白かった。現実世界における実利性が非常に高い分野である反面、効率性等の現実的な制約との戦いがあるため探求しがいのある分野だと思う。