01 / 読書ガイド
読書ガイド
引用
Abelson, H., & Sussman, G. J., with Sussman, J. (1996). Structure and Interpretation of Computer Programs (2nd ed.). MIT Press. Free official edition: https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/index.html
章の要約
本書は五つの章からなり、各章は複雑さを制御する一つの手段、すなわち手続き、データ、状態とストリーム、新しい言語、機械を中心に据える。著者は Scheme を付随的に教える。Lisp の方言には構文がほとんどなく、数日で習得できるというのがその理由である。初版の序文は、目標を、言語の構文や巧妙なアルゴリズムではなく、大規模システムの知的な複雑さを制御する技法を教えることだと述べている。
第1章：手続きによる抽象の構築
1.1 節は式、名前付けと環境、組み合わせの評価、複合手続き、置換モデル、条件式、ニュートン法による平方根、ブラックボックス抽象としての手続きを紹介する。1.2 節は手続きが生み出すプロセスを調べる。線形再帰と反復、木構造再帰、増加の位数、べき乗、最大公約数、素数判定である。1.3 節は高階手続きによって水準を上げる。引数としての手続き、lambda、一般的な方法としての手続き（不動点、ニュートン法）、返り値としての手続きを扱う。
第2章：データによる抽象の構築
第2章は手続きから複合データへ進む。2.1 節は有理数の算術、抽象化の壁、「データとは何か」という問い、区間算術の演習を通じてデータ抽象を展開する。2.2 節は列、階層構造とクロージャ性、標準的インタフェースとしての列、そして図形言語を扱う。2.3 節は記号データ、すなわち引用、記号微分、集合、ハフマン符号化木を導入する。2.4 節と 2.5 節は複数表現、タグ付きデータ、データ主導プログラミング、汎用演算を論じ、記号代数で締めくくる。
第3章：モジュール性、オブジェクト、状態
この章はプログラムの組織化の二つの方法、すなわち時間とともに変化するオブジェクトを中心にする方法と、情報の流れ（ストリーム）を中心にする方法を対比する。3.1 節は代入と局所状態を導入し、その利点と代償を比べる。3.2 節は置換モデルに代えて評価の環境モデルを示す。3.3 節は可変データ（リスト、キュー、表）、ディジタル回路のシミュレータ、制約の伝播をモデル化する。3.4 節は並行性とその制御機構を扱う。3.5 節は遅延リストとしてのストリーム、無限ストリーム、遅延評価を展開し、関数型プログラムとオブジェクトのモジュール性を比べる。
第4章：メタ言語的抽象
この章の前提は、評価器も単なる別のプログラムだということである。4.1 節はメタ循環評価器を作る。評価の中核、式の表現、プログラムとしての実行、構文解析と実行の分離を扱う。4.2 節はそれを遅延評価のインタプリタに変形し、正規順序と作用的順序を対比する。4.3 節は amb と探索による非決定性計算を加える。4.4 節は論理プログラミングの質問システムで、それが数理論理学なのかという問いと実装を含む。
第5章：レジスタマシンによる計算
最終章は、メタ循環評価器が実行環境から受け継いでいる制御の仕組みを説明する。5.1 節はレジスタマシンを設計し、再帰のためにスタックを使う。5.2 節はレジスタマシンのシミュレータを作る。5.3 節はベクタとしてのメモリとガベージコレクションを扱う。5.4 節は末尾再帰を含む明示制御評価器を示す。5.5 節は Scheme からレジスタマシンのコードへのコンパイラを説明する。
主要概念
第1章：手続きとプロセス
- 置換モデル：手続きの適用がどう評価されるかを推論する方法。
- 再帰的プロセスと反復的プロセス：再帰的な手続きがどちらも生み出し得ること。空間と時間の増え方が異なる。
- 高階手続き：手続きを受け取る、または返す手続き。
第2章：データ抽象
- 抽象化の壁：データ型の使用とその表現を分けるインタフェース。
- クロージャ性：結果に対して再び適用できるデータの組み合わせ方。
- データ主導プログラミング：型タグで振り分け、既存のコードを変えずに新しい表現を加えられるようにする。
第3章：状態とストリーム
- 局所状態と代入：変化するオブジェクトと、それによる置換モデルの破綻。
- 環境モデル：フレームと束縛による、代入を伴う評価の説明。
- ストリーム：遅延リスト。列を全体として扱えるようにする。
第4章：評価器
- メタ循環評価器：ある言語で書かれた、その言語自身のインタプリタ。
- 遅延評価と
amb：式が評価される時点を変える評価器の変種。 - 質問システム：パターンマッチングと単一化による計算モデル。
第5章：機械
- レジスタマシン：レジスタとスタックを持つ、段階的に動作する機械。
- 明示制御評価器とコンパイラ：機械の水準で表した評価器とそのコンパイル。
批判的分析
長所
- 明快で一貫した主題。 本書は抽象化、標準的インタフェース、新しい言語による複雑さの制御を軸に全体を組み立て、各章は一つの言語またはモデルを拡張していく。
- 少ない要素で深さを出す。 Scheme の構文がごく少ないため、環境、ストリーム、評価器、コンパイルといった考え方に紙幅を割ける。読者は評価器、質問システム、コンパイラを読むだけでなく自ら実装する。
- 丁寧な改訂。 第2版は主要なシステム（汎用算術、インタプリタ、レジスタマシンのシミュレータ、コンパイラ）を設計し直し、IEEE 標準に従うどの Scheme でも動くようにコードを書き直し、並行性と非決定性の節を加えた。
- 演習と付属資料。 本文には多数の演習があり、書籍サイトには本のコード、MIT の課題例、教員用マニュアル、Scheme の実装が用意されている。
- オープンなライセンス。 全文がクリエイティブ・コモンズ表示-継承 4.0 のもとで無料公開され、目次からリンクをたどれる。
短所
- 初心者には難しい。 初版の序文は、本書を MIT の入門科目であり、電気工学・計算機科学専攻の共通必修科目の四分の一にあたると説明している。第3〜5章は進みが速く、大学1年次の数学の素養と演習に割く時間が必要である。
- 1学期では終わらない。 第2版の序文は全体を1学期では扱えないとしており、著者自身も論理プログラミング（4.4）、シミュレータの実装（5.2）、コンパイラの大部分（5.5）を省くことが多い。
- Scheme が中心。 一般的な業界言語は教えず、レジスタマシンの部分も実在の命令セットではなく本書独自のレジスタマシン言語を用いる。
- 版が古い。 第2版は 1996 年の刊行で、正誤表の最終更新は 1999 年である。
コースにおける位置づけ
入門プログラミングの書棚の中で、要求が高く考え方を重視する側にある。『How to Design Programs』も無料で Lisp 系の言語を使うが、初心者のための段階的な設計手順を築くので最初のコースに向く。SICP は二巡目として、またはすでにプログラミングができる読者に向く。『Think Python』と『Python Crash Course』は一つの人気言語への平易で実用的な入門書であり、『Introduction to Computation and Programming Using Python』は Python による計算的問題解決の講義、『The C Programming Language』は低水準言語の短い古典である。SICP が教えるのは言語というよりプログラムの捉え方であり、一般的な言語も必要なときは他の本が良い併読書になる。
本書の使い方
大学1年次の数学の素養があり、演習に時間を割ける意欲的な読者に向く。Scheme（書籍サイトに MIT Scheme などが挙がっている）をインストールし、本のコードを実行する。
実用的な進め方：
- 中核： 第1章と第2章の全体、続いて 3.1〜3.3 節と 3.5 節（状態、環境モデル、ストリーム）、4.1 節と 4.2 節（メタ循環評価器と遅延評価器）。
- 選択： 3.4 節（並行性）、4.3 節（
amb）、4.4 節（論理プログラミング）、および第5章全体。著者自身も選択的に扱っている。再帰を機械の水準で理解したければ、まず 5.1 節と 5.4 節を読む。 - 演習： 各節で演習を解いてから先へ進む。特に第2章のデータ抽象の演習と第4章のインタプリタの演習である。
理論を先に減らしたければ、より平易な Scheme による入門書から始め、後で第1章に戻るとよい。
版と出典
本ガイドは第2版（MIT Press、1996年）に基づき、MIT Press の公式 SICP サイトの HTML 版を参照している。同サイトは、全文がクリエイティブ・コモンズ表示-継承 4.0 でライセンスされていると明記している。内容は、序文と前書き、完全な目次、五つの章の導入と節の構成、および付属サイトによる補助資料の説明に基づく。