きのこる庭

最終更新: 8/19 ( ~ 5.52 )

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

< ご注意 >
・難易度に関しては完全に個人の主観となります。
参考までに僕個人のスペックを記載しておくと、高校2年の数2Bまで終わってるくらいのレベル感です。アカデミックな数学はパッパラパーです。
・また、各Exerciseの難易度に関しては そのExerciseの所まで勉強した時点でのスキルセット・理解度を想定した難易度を書くようにしています( つまり、既に後の章も勉強して記述に慣れた状態での難易度ではないので、前の章の★3つと後の章の★3つのレベル感が大きく異なります )。

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

—

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

5.1 レジスタ計算機の設計
5.1 ★★★ (慣れると自然と書けるようになる。後の部分にも響くのでしっかりやること)
5.1.1 レジスタ計算機の記述言語
5.2 ★★ (本文の通り)
5.3 ★★★ (若干複雑だが、要素ごとに適宜抽象化・分解して考えると良い)
5.1.4 再帰を実装するためのスタックの使用
5.4 ★★★ (時間はかかるが難度は高くない。再帰はスタックを使用する)
5.5 ★★ (少々面倒だが制御器のフローを追うだけ)
5.6 ★ (5.5のfibonacci再帰の流れより自明)

5.2 レジスタ計算機シミュレータ

5.7 ★ (本文通りに手続きを定義してテストする)
5.2.2 アセンブラ
5.8 ★ (assocを使用する)
5.2.3 命令の実行手続きの生成
5.9 ★ (make-operation-expのaprocsを修正する)
5.10 ★★★ (インクリメント, デクリメントあたりが割と単純で良さそう)
5.11 (a) ★★ (afterfib-n-2 を変更)
(b) ★★ (問題文中の解答方針で)
(c) ★★★★ (レジスタ自体がスタックを持つように修正できる)
5.12 ★★★★★ (これまで学んだ事柄に対するな理解が必要)
5.13 ★★★ (make-new-machineの変更で完結)
5.2.4 計算機の性能の監視
5.14 ★ (単純な計測作業である)
5.15 ★ (make-new-machineに変更を加える)
5.16 ★ (トレース用のフラグを追加する)
5.17 ★★ (ラベル保持用の変数を追加する)
5.18 ★ (5.16とほぼ同様の実装)
5.19 ★★★ (labelが更新された際の初期化を忘れずに)

5.3 記憶の割当てとごみ厚め

5.3.1 ベクタとしてのメモリー
5.20 ★ (図5.14にならう)
5.21 (a) ★★★ (フィボナッチで勉強した再帰と同じ感じで)
(b) ★★★ (a,bともに仮変数を立ててnot pairを表現する)
5.22 ★★★★ (appendとappend!でポインタの扱いが異なる点に注目)
5.3.3 条件式, 代入および定義
5.23 ★★ (これまで通りの手順で)
5.24 ★★★★ (データの流れ方を把握していないと難しい)
5.25 ★★★★★ (4章の遅延評価器が参考になる)
5.26 (a) ★ (問題文通り)
(b) ★ (aが分かればたやすい)
5.27 ★ (単なる検証問題)
5.28 ★ (問題文通り)
5.29 ★★★ (どちらかというと数学の問題)
5.30 Pass

翻訳系

5.5.1 翻訳系の構造
5.31 ★ (問題5.32にも大きなヒントが書かれている)
5.32 (a) ★★★ (ecevalに非演算子の場合のブランチを切る)
(b) ★ (現実的に考えると自明)
5.5.5 翻訳したコードの例
5.33 ★★ (再帰と反復の違い)
5.34 ★★ (末尾再帰的)
5.35 Pass
5.36 ★★★★ (コンパイルの際に充てられていた処理を実行時に移す)
5.37 ★ (以前の節でも度々問題になった)
5.38-5.52 切り上げ

【概観】
・「レジスタ」という概念を取り上げ、より機械語に近い話に。
・デバッグして検証せよ というタイプの問題が多いので、これまで紙面などで検証してきた場合はかなりの苦行になる。
・本質的には 4章の Eval & Apply の循環の話の延長線上にある。4章をなんとなく理解しているだけだと5章の後半で死ぬ。
・4章のeval評価器に対して よりコンパイラという概念がハッキリと浮き出ているのが5章。プログラムがどのような順序で解釈され実行されているのかが理解できた。とりわけ、これまでの章でも末尾再帰や反復といった概念を定性的に理解してきたわけだけども、実際どのように環境がつくられたり保持されたりしているのかを定量的に理解できた。
・どこかのブログ記事で「5章はボーナスステージのように面白い」と書かれていたけど、これは4章の緻密な理解を前提とした話なので注意。特に4章は理解を促進するためにもしっかりデバッグできるようにしておいた方が良い。さもないと取り返しがつかなくなる(震え声)