How to Design Programs: An Introduction to Programming and Computing（プログラムの設計法：プログラミングと計算への入門）

引用

Felleisen, M., Findler, R. B., Flatt, M., & Krishnamurthi, S. (2018). How to Design Programs: An Introduction to Programming and Computing (2nd ed.). The MIT Press. Free official edition: https://htdp.org/

章の要約

プロローグ：プログラムの書き方

プロローグでは、読者はすぐに DrRacket でプログラミングを始める。数値、文字列、画像の演算を行い、続いて一つのプログラムをいくつかの版に育てながら、ロケットが着陸する小さなアニメーションを作る。最後の節（「Not!」）は、こうした素早く無計画なプログラミングがなぜスケールしないのかを説明し、本書の代案である体系的なプログラム設計への準備をする。

第1–2章：算術、関数とプログラム

第 I 部「固定サイズのデータ」は、数値、文字列、画像、真偽値の式と、値がどの種類のデータかを判定する述語から始まる。第2章は関数定義、置き換えによる計算、関数の合成、大域定数、そして本書で使う二種類の完全なプログラム、すなわちバッチプログラムと big-bang で作る対話的な「ワールド」プログラムを導入する。

第3章：プログラムの設計法

本書の中心となる章である。関数のための設計レシピを六つの段階で示す。データ定義、シグネチャと目的の記述とヘッダ、関数の例、テンプレート、定義、テストである。次にこのレシピをプログラム全体へと広げ、領域知識と check-expect によるテストの役割を強調し、仮想ペットを一貫した例としてワールドプログラムの設計法を示す。

第4–7章：区間、列挙、項目分け、構造の追加、項目分けと構造、まとめ

これらの章はレシピをより豊かなデータに広げる。第4章は条件式と、それに対応するデータ定義（列挙、区間、項目分け）を扱い、信号機のような有限状態のワールドで締めくくる。第5章は posn から始めて構造体を導入し、構造体型の定義、「データの全体像」、構造体を使った設計、グラフィカルなテキストエディタへと進む。第6章は項目分けと構造体を組み合わせ、入力の誤りを検査し、等価性の述語を論じる。第7章はこの部をまとめる。良いプログラマは試行錯誤で手直しするのではなく設計するのであり、レシピには手順の次元とデータの次元がある。

間奏 1：初級学生言語

最初の間奏は、教育用言語 BSL を正確に説明する。語彙、文法、意味、代数的な手順の列としての評価、エラーメッセージ、真偽式、定数と構造体の定義、テストである。

第8–10章：リスト、自己参照的なデータ定義による設計、リストの続き

第 II 部「任意の大きさのデータ」は '() と cons から作るリストを導入し、自己参照的なデータ定義から再帰関数が導かれ、関数のテンプレートがデータの形に従うことを示す。第9章は空でないリスト、再帰的データとしての自然数、入れ子になった「マトリョーシカ」の構造、ワールドプログラムの中のリストを加える。第10章はリストを生成する関数、リストの中の構造体、（ファイルから読む）リストのリスト、そしてグラフィカルなエディタの再設計を扱う。

第11–13章：合成による設計、プロジェクト：リスト、まとめ

第11章は、問題を補助関数に分解して合成する方法を教える。再帰する補助関数や一般化する補助関数も含む。第12章は大きめのプロジェクトを示す。辞書、iTunes のライブラリ、言葉遊び、ミミズのゲーム、簡易版テトリス、宇宙戦争ゲーム、有限状態機械である。まとめでは、自己参照に合わせてレシピを洗練させることと、必要なデータ定義とともに「ウィッシュリスト」を書くことを強調する。

間奏 2：クオートとアンクオート

短い間奏で、大きなデータを簡潔に書く記法としてクオート、準クオート、アンクオート、スプライスを導入し、あわせてシンボルを紹介する。

第14–15章：いたるところの類似、抽象の設計

第 III 部「抽象」は、第 II 部の多くの関数が似ていることに気づくところから始まる。第14章は似た関数やデータ定義を抽象化し、関数が値であることを示す。第15章は抽象のための設計レシピを示す。例からの抽象、シグネチャの一般化、変更箇所の一元化、テンプレートからの抽象である。

第16–18章：抽象の利用、名前のない関数、まとめ

第16章は map、filter、foldr などの既存の抽象の使い方を教え、local による局所定義とそれがもたらす表現力を導入し、例とプロジェクトで練習する。第17章は名前のない関数のための lambda を導入し、それを抽象化、仕様の記述、さらにはデータの表現にも用いる。まとめは、抽象を再利用可能なコードを作ることと使うことの両面として描く。

間奏 3：スコープと抽象

この間奏は、レキシカルスコープ、変数の束縛出現と被束縛出現を定義し、さらに二つの抽象の仕組み、すなわち中級学生言語の for ループとパターンマッチングを紹介する。

第19–20章：S 式の詩学、反復的な洗練

第 IV 部「絡み合ったデータ」は、互いに参照し合う複数の定義で記述されるデータを扱う。木、森、S 式であり、二分探索木のプロジェクトと関数の単純化の節を含む。第20章は反復的な洗練を明示的に導入し、何段階かの版を経て洗練されるコンピュータのファイルシステムのモデルを例とする。

第21–22章：インタプリタの洗練、プロジェクト：XML の商取引

第21章は反復的な洗練により、式、変数、関数からなる小さな言語のインタプリタ、すなわち DrRacket の対話領域の中核を設計する。第22章は XML を S 式として表し、XML の列挙をレンダリングし、ドメイン固有言語を論じ、XML データを読み込む。

第23–24章：同時処理、まとめ

第23章は二つの複雑な入力を受け取る関数の設計法を示し、三つの場合（一方の入力を原子的なデータとして扱う、両方を歩調を合わせて処理する、すべての組み合わせを二次元の表で扱う）を区別し、データベースのプロジェクトで締めくくる。まとめでは、設計レシピがあらゆる形の構造的データにスケールすると述べる。

間奏 4：数の性質

この間奏は、固定サイズの数の表現、オーバーフローとアンダーフロー、そして教育用言語が正確な数と不正確な数をどう区別するかを説明する。

第25–26章：標準的でない再帰、アルゴリズムの設計

第 V 部「生成的再帰」は、問題を新たに生成した部分問題に分割するような、データの構造に従わない再帰を導入する。第26章はそのようなアルゴリズムのために設計レシピを調整する。コーディングの段階に四つの新しい問いを加え、停止性の明示的な論証を求め、構造的再帰と生成的再帰を比較する。

第27–30章：主題の変奏、数学の例、バックトラックするアルゴリズム、まとめ

生成的再帰の例として、フラクタル、二分探索、構文解析の一端（第27章）、ニュートン法、数値積分、ガウスの消去法のプロジェクト（第28章）、そしてグラフの探索と n クイーン問題に関するバックトラックのプロジェクト（第29章）が挙げられる。まとめは、多くの計算機科学者がこうした関数をアルゴリズムと呼ぶこと、そしてそれがすべての入力で停止するとは限らないことを述べる。

間奏 5：計算のコスト

最後の間奏は、特定の入力で時間を測ってもわかることが少ない理由を説明し、抽象的な実行時間と「オーダー」の定義を導入して、それを用いてプログラムが述語とセレクタに頼る理由を論じる。

第31–34章：知識の喪失、アキュムレータ形式の関数の設計、累積のさらなる用途、まとめ

第 VI 部「アキュムレータ」は、構造的・生成的な関数が再帰の途中で知識を「忘れて」しまい、非効率や停止しない原因になることを示す。アキュムレータが必要であると見抜き、アキュムレータの記述を書き、関数をアキュムレータ形式に変換するためのレシピを示し、木、データの表現、マウスで操作するグラフィカルなエディタに適用する。

エピローグ：先へ進む

エピローグは計算とプログラム設計を振り返り、次の段階を提案する。将来の開発者や計算機科学者には Racket のような本格的な言語、クラスとオブジェクト、型を、それ以外のすべての人には自分の分野でこの設計プロセスを使うことを勧める。

主要概念

プロローグと第1–3章

• 設計レシピ：問題文からテスト済みの関数へと導く六つの段階（データ定義、シグネチャ・目的・ヘッダ、例、テンプレート、定義、テスト）。
• データ定義：現実世界の情報をプログラムの中でデータとしてどう表すかを、例とともに述べたもの。
• ワールドプログラム：big-bang、状態、描画関数、イベントハンドラで作る対話的なプログラム。

第4–7章と間奏 1

• 項目分け：互いに異なる場合を列挙するデータ定義で、テンプレートでは場合ごとに一つの節を持つ cond に対応する。
• 構造体型：コンストラクタ、セレクタ、述語を持つ、プログラマが定義する複合データ型。
• 代数的な計算モデル：DrRacket のステッパが示すように、BSL のプログラムを一歩ずつの置き換えで評価すること。

第8–13章

• 自己参照的なデータ定義：自分自身を参照する定義（リストなど）で、再帰関数を導く。
• テンプレートはデータに従う：関数のコードの形は、それが処理するデータ定義の形を映す。
• ウィッシュリスト：後で設計する補助関数を、シグネチャと目的とともに並べたリスト。

第14–18章と間奏 3

• 抽象：繰り返し現れるコードのパターンを、違いをパラメータにした一つの関数にくくり出すこと。
• 値としての関数：関数を渡したり返したりすること。map、filter、foldr、lambda の基礎である。
• レキシカルスコープ：変数の各出現が、プログラムのテキストを調べれば見つかる定義を指すという規則。

第19–24章

• 相互参照するデータ：互いを参照する複数のデータ定義で、定義ごとに一つのテンプレートを必要とする。
• 反復的な洗練：まず問題の単純化した版を解き、細部を一歩ずつ加えていくこと。

第25–30章と間奏 5

• 生成的再帰：データの構造ではなく、問題への洞察に基づいて新たに生成した部分問題に対して行う再帰。
• 停止性の論証：生成的再帰の関数がなぜいずれ停止するかの説明、あるいは停止しない入力についての警告。
• 抽象的な実行時間：特定の実行の時間を測るのではなく、ステップ数の増え方の次数でコストを測ること。

第31–34章

• アキュムレータ：走査の途中で集めた知識を運ぶ追加の引数。
• アキュムレータの記述：アキュムレータが表す知識の説明で、多くの場合、元の引数と現在の引数の違いを述べる。

批判的分析

長所

• 教えられる明示的な方法。 序文は六段階の設計レシピを、学生がインデックスカードに書き写せるものとして示し、各部はそれぞれの段階に的を絞った問いを加えていく。データ定義、例、テンプレートといった中間成果物があるので、行き詰まった学生や教員は、どこで問題が生じたかを正確に見ることができる。
• データに導かれる進み方。 各部は新しい種類のデータ（固定サイズ、任意の大きさ、絡み合ったもの）か、新しい設計原理（抽象、生成的再帰、アキュムレータ）を導入し、それに応じてレシピを拡張する。そのため本書の構成自体が、プログラムの構造はデータに従うということを教えている。
• 初心者のために作られた教育用言語と環境。 一連の教育用言語（BSL、BSL+、ISL、ISL+）は学習者の段階に合ったエラーメッセージを出し、DrRacket のステッパは評価を一歩ずつ見せる。画像を使った対話的なワールドプログラムは、すぐに目に見えるフィードバックを与える。
• 豊富な演習と繰り返し現れる題材。 オンライン版には番号付きの演習が 528 問あり、仮想ペット、テキストエディタ、グラフといった題材がいくつもの部に再登場する。序文はこれを、反復的な洗練を「裏口から」導入するものだと説明している。

短所

• 主流の言語ではない。 本書は Python、Java、C ではなく Racket に基づく教育用言語で設計を教える。序文はそれが意図的だと論じるが、特定の産業用言語が必要な学生は後で自力で移行しなければならず、エピローグはその段階を他の本に委ねている。
• 長さとペース。 六つの部、五つの間奏、500 問を超える演習からなる本書は長く、序文自身もクォーター制や高校の授業のために削る案を示している。手早い入門を求める読者には、前半の章が遅く感じられるかもしれない。
• 状態、オブジェクト、型の扱いが限られる。 代入、クラスとオブジェクト、静的型はおおむね先送りされ、エピローグで次の話題として挙げられるだけである。アキュムレータ形式のプログラミングは関数型で示され、命令型のループは範囲外と明言されている。
• 規範的な書き方。 小さな関数でもすべての段階を踏むよう求める姿勢は、プログラミング経験のある学生には重く感じられることがある。ただし著者たちは、その規律こそが要点だと論じている。

コースにおける位置づけ

この入門プログラミングの書籍リストで、How to Design Programs は特定の言語より方法に焦点を当てた入門書である。一般にプロジェクト中心の Python 入門とされる Matthes の Python Crash Course や、Python でプログラミングと計算を教える Downey の Think Python と Guttag の Introduction to Computation and Programming Using Python とは対照的である。プログラム設計、テスト、再帰の確かな基礎を身につけたい学生は、HtDP から始め、エピローグの勧めに従って Python の本に進み、レシピを主流の言語に移すとよい。

Abelson と Sussman の Structure and Interpretation of Computer Programs は同じ Lisp 系の伝統に属し、一般により数学的な要求が高い本とされる。HtDP の序文は自らを前代数の知識だけで読めるものと位置づけているので、その前段階として適している。Kernighan と Ritchie の The C Programming Language は低水準のプログラミングを扱い、最初の授業の後に読むのがよい。

本書の使い方

本書はプログラミング経験のない読者のために書かれている。著者たちは前代数の知識で十分だとしており、必要なソフトウェアは無料の DrRacket 環境だけである。序文は独学者と教員の両方に向けて書かれている。

独学者には、本書全体を最初から最後まで学び、すべての演習を解くか、少なくとも解き方がわかるようにすることが求められる。序文はさらに三つの短い道筋を示している。高校の授業では第 I 部と第 II 部を小さなゲームのプロジェクトとともに、大学のクォーター制の授業では第 I、II、III、V 部と間奏 1・3 を、大学のセメスター制の授業では第 I 部と第 II 部の後、第 VI 部のうち生成的再帰に依存しない部分、続いて間奏 5 と残りを扱う。どの道筋でも第3章（設計レシピ）は必須であり、第8–9章と第14–16章が再帰と抽象の土台となる。

ステッパを使って評価を理解し、定義の前に check-expect のテストを書き、白紙から始めるのではなく各データ定義のテンプレートに従うこと。行き詰まったら、序文が教員にインデックスカードで行うよう勧めているように、レシピのうち失敗した段階に戻るとよい。

版と出典

本ガイドは https://htdp.org/ にある無料のオンライン第2版（本文 © 2014 MIT Press、オンライン版の公開日 2026年5月28日、印刷版は MIT Press より 2018 年刊）に基づく。序文の全文（設計レシピ、教育用言語、各部の構成、推奨される授業の道筋、初版との違いを含む）、完全な目次、プロローグ、全六部それぞれの冒頭の節とまとめの章、五つの間奏すべての冒頭部分、エピローグ、そして第 I、IV、V 部の選んだ節を参照している。