Crafting Interpreters（インタプリタの作り方）

引用

Nystrom, R. (2021). Crafting Interpreters. Genever Benning. Free official edition: https://craftinginterpreters.com/

章の要約

第1章：はじめに

序章は本書の約束を示す。Lox という一つの小さな言語のために完全なインタプリタを二つ作り、すべてのコード行を示して説明し、理論は他の本より控えめにする、というものである。Nystrom は「小さな言語」はいたるところにあり、言語を作ることは厳しいプログラミングの訓練になり、この分野は魔法使いだけのものではないと論じる。本書の仕掛け（挿入場所を正確に示すコード断片、余談、章末のチャレンジ、デザインノート）を説明し、Lex や Yacc を使わずすべて手で書く理由、そして一つ目のインタプリタを Java、二つ目を C で書く理由を述べる。

第2章：領域の地図

この章は言語処理系の作り方を概観し、プログラムが字句解析、構文解析、静的解析、中間表現、最適化、コード生成、仮想マシン、ランタイムを通る流れをたどる。続いて、ワンパスコンパイラ、木を辿るインタプリタ、トランスパイラ、実行時コンパイル（JIT）といった近道を紹介し、「コンパイラ」と「インタプリタ」の境界はあいまいなので本書は両方を扱うと述べる。

第3章：Lox 言語

実装する言語の非公式な紹介である。動的型付けでガベージコレクションを持ち、C 風の構文を持つスクリプト言語で、真偽値、数値、文字列、nil、一般的な演算子、変数、制御フロー、クロージャを伴う第一級関数、単一継承のクラスを備える。Lox がプロトタイプではなくクラスを採用する理由を説明する節がある。デザインノートは、式を中心に作られた言語と、式と文を区別する言語を比較する。

第4章：字句解析

第 II 部では Java による木を辿るインタプリタ jlox に取りかかる。この章はインタプリタの枠組み（ファイルの実行または REPL、エラー報告）を整え、ソースのテキストをトークンに変換する手書きのスキャナを作る。1 文字・2 文字の演算子、文字列と数値のリテラル、そして「最長一致」によるキーワードと識別子の区別を扱う。短い節で字句文法と正規言語を結びつけるが、オートマトンには深入りしない。

第5–6章：コードの表現、式の構文解析

第5章は文脈自由文法を導入して Lox の式の文法を書き、小さなメタプログラムで構文木のクラスを生成する。「表現問題（expression problem）」を論じ、ビジターパターンを導入して簡単な木の表示プログラムを書く。第6章は優先順位と結合規則によって曖昧さを解消し、式の再帰下降パーサを作り、パニックモードによる回復と同期を伴う構文エラーの報告を加える。

第7章：式の評価

インタプリタは式の木を評価するようになり、Lox の値を Java のオブジェクトで表す。この章は真偽の判定規則を定め、単項演算子と二項演算子を実装し、わかりやすく報告される実行時の型エラーを加える。デザインノートでは静的型付けと動的型付けを比較検討する。

第8–9章：文と状態、制御フロー

第8章は文、グローバル変数、代入、ブロックスコープを加え、入れ子とシャドーイングを扱える環境の連鎖で実装する。第9章はチューリングマシンとチューリング完全性に簡単に触れた後、if、短絡評価の and/or、while、そして while への脱糖によって実装する for を加える。

第10章：関数

ユーザー定義関数が登場する。引数の個数を検査する呼び出し式、ネイティブ関数 clock()、関数宣言と関数オブジェクト、（例外で Java のスタックを巻き戻して実装する）return、そして環境を捕捉する局所関数である。

第11章：解決と束縛

クロージャと変更可能な環境が組み合わさると微妙なバグが生じるため、この章では実行前に各変数参照がどのスコープを指すかを正確に計算する静的な解決パスを加える。これが本書における意味解析の入り口であり、同じパスでトップレベルのコードからの return などのエラーも報告する。

第12–13章：クラス、継承

第12章はクラス宣言、インスタンス、フィールド（get 式と set 式）、メソッド、this、初期化子を実装する。デザインノートはクラスとプロトタイプを比較する。第13章は単一継承と super 呼び出しを加えて jlox を完成させる。この部の導入では、jlox は 2 千行に満たない Java コードだと述べられている。

第14–15章：バイトコードのチャンク、仮想マシン

第 III 部では C で一から clox を作る。第14章は、AST を辿る方式（メモリの局所性が悪い）やネイティブコード（複雑で移植性がない）ではなくバイトコードを選ぶ理由を説明し、動的配列による命令のチャンク、逆アセンブラ、定数プール、行番号情報を作る。第15章は仮想マシンのディスパッチループと値スタックを書いて電卓として動かす。デザインノートはレジスタ型のバイトコードを論じる。

第16–17章：オンデマンドの字句解析、式のコンパイル

第16章は求められたときだけトークンを生成するスキャナを書き、トライ木のような状態機械でキーワードを認識する。第17章はバイトコードを直接出力するワンパスコンパイラを書く。用いるのは Pratt パーサで、各トークンの種類が前置と中置の解析関数および優先順位を持つ。

第18–19章：値の型、文字列

第18章は動的型付けの値を C のタグ付き共用体で表し、型検査と実行時エラーを伴って真偽値と nil を加える。第19章は共通のヘッダを持つヒープ上のオブジェクト（「構造体の継承」）を導入し、文字列と連結を実装し、解放できるようにすべてのオブジェクトのリストを保持する。デザインノートは文字列のエンコーディングを論じる。

第20章：ハッシュテーブル

一章をまるごと使ってハッシュテーブルを一から作る。バケットと負荷率、チェイン法とオープンアドレス法、FNV-1a ハッシュ関数、線形探査、サイズ変更、墓標（tombstone）による削除、そして clox がポインタで文字列を比較できるようにする文字列のインターン化である。

第21–23章：グローバル変数、ローカル変数、前後へのジャンプ

これらの章は、文とグローバル変数（ハッシュテーブルに格納）、コンパイル時に解決されスタックのスロットに置かれるブロックスコープのローカル変数、そしてバックパッチによって条件付き・無条件のジャンプにコンパイルされる制御フローを加える。デザインノートは goto をめぐる議論を振り返る。

第24–25章：呼び出しと関数、クロージャ

著者が「怪物」と呼ぶ第24章は、関数オブジェクト、コールフレーム、入れ子の関数のためのコンパイラのスタック、引数の束縛、実行時のスタックトレース、ネイティブ関数を加える。第25章は上位値（upvalue）によってクロージャを実装する。上位値は最初は「開いた」状態（スタックを指す）で、変数がスコープを抜けると「閉じられ」（ヒープに移され）る。

第26章：ガベージコレクション

仮想マシンにマーク・スイープ方式のガベージコレクタを加える。到達可能性とルートを定義し、灰色オブジェクトの作業リストを伴う三色抽象を用い、文字列表を弱参照として扱い、いつ回収するか（レイテンシとスループット、自己調整するヒープの閾値）を論じ、ストレステストモードで GC のバグを見つける方法を示す。

第27–29章：クラスとインスタンス、メソッドと初期化子、スーパークラス

オブジェクトモデルを三章かけて C で作り直す。クラスとインスタンスのオブジェクト、フィールド、メソッドと束縛メソッド、this、初期化子、そしてメソッド呼び出しを数倍速くする最適化された invoke 命令である。第29章はメソッドをサブクラスへ下方にコピーすることで継承を実装し、super 呼び出しを実装して仮想マシンを完成させる。

第30章：最適化

最終章は性能を測定し改善する。ベンチマークとプロファイリングを論じ、ハッシュテーブルの探査における剰余演算をビットマスクに置き換え、すべての値を 64 ビットに詰める NaN ボクシングを実装する。後者については全体で約 10% の向上が報告されている。最後に、コンパイラ最適化の教科書や形式的なプログラミング言語理論など、さらなる学習への提案で締めくくる。

付録 I–II：Lox の文法、生成された構文木クラス

付録は Lox の完全な文法を一か所にまとめ、第5章のメタプログラムが生成する Java の構文木クラスを掲載する。

主要概念

第1–3章：ようこそ

• 木を辿るインタプリタとバイトコード VM：本書が順に作る二つの実装方式で、単純さと速度を引き換えにする。
• Lox：クロージャとクラスを持つ、小さく動的型付けでガベージコレクションのある言語で、二度実装されることを前提に設計されている。

第4–6章：jlox の字句解析と構文解析

• トークンと字句（レキシーム）：レキシームは生の部分文字列であり、トークンはそれに種類、リテラル値、行番号を加えたもの。
• ビジターパターン：固定された構文木クラスの集合に、各クラスを編集せずに新しい操作を加える方法。
• パニックモードによる回復：構文エラーの後、文の境界と思われる位置までトークンを読み飛ばし、解析を続けてさらにエラーを報告できるようにすること。

第7–11章：評価、状態、関数

• 環境：名前から値への対応で、外側の環境へ連鎖させて入れ子のスコープを表す。
• 脱糖：便利な構文（for など）をより単純な構文（while）に変換して実装すること。
• クロージャ：宣言された時点の環境を保持する関数値。
• リゾルバ：実行前に各変数の使用をその宣言に結びつける静的なパス。

第12–13章：クラスと継承

• 束縛メソッド：アクセス元のインスタンスとひとまとめにしたメソッド値で、後で this が正しく働くようにする。
• スーパークラス呼び出し：super.method() は呼び出しを含むクラスのスーパークラスからメソッドを探す。

第14–19章：バイトコード、VM、値

• バイトコードのチャンク：定数と行番号を伴う、コンパクトで線形な命令の配列。
• Pratt パーサ：トークンの種類ごとの前置・中置関数の表に駆動される、優先順位上昇型のパーサ。
• タグ付き共用体：型のタグと、取りうるペイロードの共用体を並べて持つ C の構造体で、動的な値の表現に使う。

第20–25章：ハッシュテーブル、変数、呼び出し

• 墓標付きオープンアドレス法：項目をバケット配列に直接格納し、削除したスロットに印をつけて探査列を保つ方式。
• 文字列のインターン化：異なる文字列をそれぞれ一つだけ保持し、等価比較をポインタ比較にすること。
• 上位値：捕捉された変数への VM の間接参照で、変数がスタック上にある間は開いており、ヒープに移されると閉じる。

第26–30章：ガベージコレクション、オブジェクト、最適化

• 三色マーク・スイープ：白・灰・黒の集合で、オブジェクトが未訪問か、処理待ちか、追跡済みかを管理する。
• NaN ボクシング：数値以外の値を IEEE 754 の NaN の未使用ビットパターンに符号化し、すべての値を 64 ビットに収める手法。
• 最適化の前にプロファイル：推測ではなく、ベンチマークとプロファイラで実際のホットスポットを見つけること。

批判的分析

長所

• 各段階で完全かつ実行可能なコード。 二つのインタプリタのすべての行が本文に現れ、各断片は挿入すべきファイルと関数を示し、章の順序はどの章の後でもプログラムが動くように組まれている。読者は断片ではなく、動く実装を二つ手にして終える。
• 一つの言語の二つの実装。 Lox を二度作ることで、設計を直接対比できる。環境とスタックスロット、Java のガベージコレクタと自作のもの、AST を作る再帰下降パーサとワンパスの Pratt コンパイラである。第 III 部の各章の冒頭では、jlox が当然視していたものが何度も説明される。
• 構文解析を超えた工学的な深さ。 ハッシュテーブル、上位値を伴うクロージャ、ガベージコレクション、NaN ボクシングの章は、多くの入門的なコンパイラ教科書が省くランタイムの話題を、測定結果とトレードオフ（たとえば AST を離れる理由としてのキャッシュの局所性）を説明しながら扱う。
• チャレンジとデザインノート。 チャレンジは章の内容の先へと読者を押し出し（break、無名関数、BETA 式の継承、switch 文の追加）、暗黙のセミコロン、静的型付けと動的型付け、「新奇さの予算」といった話題のデザインノートは言語設計上の判断を持ち込む。

短所

• 意図的に理論が軽い。 正規言語、文法、構文解析は必要な範囲でしか導入されず、LL・LR の理論、パーサ生成器、型システム、形式意味論は扱われない。コンパイラの試験に備える学生には別の教科書が必要である。
• 動的でインタプリタ型の対象に限られる。 Lox には静的型がなく、clox は機械語ではなく独自のバイトコードにコンパイルするため、レジスタ割り当て、命令選択、静的型検査は扱われない。
• 二つの言語を前提とする。 第 II 部には実用的な Java が、第 III 部にはポインタや手動のメモリ管理を含む確かな C の力が必要であり、著者は必要なら先に C を学ぶよう明言している。
• 長く、少しずつ進む。 断片を一つずつ示す書き方のため本全体は長く、またコードは本番向けのスタイルではなく紙面での読みやすさを優先して書かれていると著者自身が断っている。

コースにおける位置づけ

このコースの書籍リストでは、Crafting Interpreters と Douglas Thain の Introduction to Compilers and Language Design が入門書の二冊であり、扱う範囲は異なる。Nystrom は動的言語のためにすべての段階を手で書き、ランタイムの実装（クロージャ、ガベージコレクション、バイトコード VM）を深く掘り下げる。一方 Thain は文法理論、Flex と Bison、静的型検査、そして X86 または ARM のアセンブリ生成を扱う。先に Nystrom を読めば言語が端から端までどう動くかを直感的につかめ、その後 Thain が Nystrom の省いた形式的な構文解析とネイティブコード生成を補う。

コース中のより本格的な本である Cooper と Torczon の Engineering a Compiler、Aho、Lam、Sethi、Ullman の Compilers: Principles, Techniques, and Tools は、一般にコンパイラ理論と最適化を包括的に扱う本とされている。Nystrom 自身も最終章で、コンパイル時最適化の次の一歩として Cooper と Torczon を勧めている。Pierce の Types and Programming Languages は、本書が意図的に避けている形式的な型理論を学ぶための本である。

本書の使い方

本書は、初めて言語処理系の実装に取り組むプログラマを対象としている。コンパイラの予備知識は不要だが、プログラミングには慣れている必要がある。第 II 部で使う Java はごく小さな部分集合だが、第 III 部は確かな C の力を前提とする。

本書が想定している使い方は、コード断片の設計意図どおり、章ごとにコードを打ち込み、各インタプリタを常に動く状態に保つことである。第 I 部（第1–3章）はすばやく読める。第 II 部（第4–13章）は字句解析、構文解析、評価、スコープ、クロージャを理解するための中心であり、解決を扱う第11章は短いが重要である。第 III 部（第14–30章）はより長く難しく、第24–26章（呼び出し、クロージャ、ガベージコレクション）が最も難しいが、取り組む価値がある。短い授業なら第 II 部で止めるか、第 III 部を第26章まで進めてオブジェクト指向の章と第30章を任意とするとよい。

各章で少なくともいくつかのチャレンジに取り組むこと。ただし後の章は手を加えていないインタプリタを前提とするので、コードのコピーで行う。デザインノートは言語設計の議論として単独でも読める。本書のウェブサイトで全文が公開されており、jlox と clox のソースコードは MIT ライセンスで公開されているので、自分の実装の確認に役立つ。

版と出典

本ガイドは Crafting Interpreters の無料ウェブ版 https://craftinginterpreters.com/（本文 © 2015–2020 Robert Nystrom、印刷版は 2021 年刊）に基づく。目次、各部の導入、第1章の全文、そして全 30 章の冒頭部分、すべての節見出し、チャレンジとデザインノートを参照し、14.1 節（なぜバイトコードか）と 30.3–30.4 節（NaN ボクシングと「次はどこへ」）は全文を読んでいる。二つの付録も含む。