1. なぜ言語処理系にC言語なのか

この章では、本書全体の地図を描きます。そもそも「言語処理系」とは何か、なぜその実装にC言語がよく使われるのか、そして本書をどう読み進めればよいのかを説明します。手を動かすための開発環境の準備にも触れます。

1.1 言語処理系とは何か

言語処理系（language processor）とは、プログラミング言語で書かれたソースコードを受け取り、それを実行したり、別の形式に変換したりするソフトウェアの総称です。代表的なものに次の二種類があります。

• インタプリタ（interpreter）：ソースコードを読みながら、その場で意味を解釈して実行する処理系。Rubyの標準実装やPythonの標準実装CPythonがこの方式です。
• コンパイラ（compiler）：ソースコードを、機械語や別の言語など、より低レベルな形式へ一括変換する処理系。CコンパイラのGCCやClangがこれにあたります。

どちらも内部では似た段階を踏みます。文字の並びを意味のある単位（トークン, token）に区切る字句解析（lexical analysis）、トークンの並びから文法構造を組み立てる構文解析（parsing）、そして組み立てた構造を実行または変換する段階です。構文解析の結果は普通、木構造の形にまとめられ、これを抽象構文木（abstract syntax tree, AST）と呼びます。たとえば 1 + 2 * 3 という式は、次のような木になります。

graph TD
    A["+"] --> B["1"]
    A --> C["*"]
    C --> D["2"]
    C --> E["3"]

掛け算が足し算より深い位置にあるのは、掛け算が先に計算されるからです。この木を根からたどって計算すれば 1 + 6 = 7 が得られます。本書の後半では、まさにこの「木を作って、たどって、計算する」処理をC言語で書けるようになることを目指します。言語処理系の全体像をより深く学びたい場合は、定番の教科書であるドラゴンブック^{[Alfred, 2006]}や、手を動かしながら学べるCrafting Interpreters^{[Robert, 2021]}が良い道案内になります。

1.2 なぜC言語なのか

世の中には便利な言語がたくさんあるのに、なぜいまさらCを学ぶのでしょうか。言語処理系という文脈では、いくつもの理由があります。

第一に、実物がCで書かれていることです。前述のCPythonやLua、Rubyの処理系MRIなど、広く使われている言語処理系の心臓部はCで書かれています。それらのソースコードを読んだり改造したりしたいなら、Cが読めることは大きな武器になります。

第二に、メモリの仕組みが見えることです。言語処理系は、値やASTといったデータを大量に作っては捨てます。どこにメモリが確保され、いつ解放されるのかを意識できることは、効率的な処理系を書くうえで欠かせません。Cはメモリを隠さない言語なので、この感覚が自然に身につきます。

第三に、速いことです。インタプリタの内側のループは、プログラムの実行中に何百万回も回ります。ここが遅いと処理系全体が遅くなります。Cは機械語に近い制御ができるため、速い処理系を書きやすいのです。インタプリタの速さがどこから来るのかは、Ertlらの研究^{[M., 2003]}でも詳しく分析されています。

1.3 本書の進め方

本書は三部構成です。第I部でCの基礎（コンパイルの流れ、型、ポインタ）を固め、第II部でデータを表現する道具（構造体、共用体、関数ポインタ、const、メモリ管理）を学び、第III部で処理系を速くする最適化を扱います。

各章は前の章を前提に進みます。とくにポインタ（4. ポインタとメモリ）は後のほとんどの章で使うので、飛ばさずに読んでください。巻末には用語集（A. 用語集）と、さらに学ぶための文献案内（B. さらに学ぶために）を用意しました。知らない言葉が出てきたら用語集を引いてください。

1.4 開発環境を用意する

C言語のプログラムを動かすには、コンパイラが必要です。代表的なものにGCCとClangがあります。多くのLinux環境やmacOSでは、どちらかが最初から入っているか、簡単に導入できます。

コンパイラが入っているかは、ターミナル（端末）で次のように打って確かめられます。

cc --version

cc は「Cコンパイラ」を指す慣習的な名前で、GCCやClangへの別名になっていることが多いです。バージョン情報が表示されれば準備完了です。表示されない場合は、Linuxなら build-essential（GCC一式）パッケージを、macOSなら「Command Line Tools」を導入してください。

簡単なプログラムをコンパイルして実行する流れは次のようになります。hello.c というファイルに書いて、

#include <stdio.h>

int main(void) {
    printf("こんにちは、言語処理系\n");
    return 0;
}

次のコマンドでコンパイルし、できた実行ファイルを動かします。

cc hello.c -o hello
./hello

-o hello は「hello という名前の実行ファイルを作れ」という指示です。./hello で実行すると、メッセージが表示されます。各行が何をしているのかは次の章で詳しく説明するので、いまは「こうやって動かすのだ」という流れだけつかめれば十分です。

第I部　C言語の足場を固める

言語処理系を書く前に、まずC言語そのものの足場を固めます。この部では、Cプログラムがどうやって動く形になるのか（コンパイルの流れ）、値を入れる「型」とは何か、そしてC言語を理解するうえで避けて通れない「ポインタ」を扱います。

ここで紹介する道具は、後の部で構文木や値を表現するときの土台になります。急がば回れ。まずはこの三つの章でCの世界の地面を踏み固めましょう。

2. C言語の基礎

この章では、C言語のプログラムが「文字の並び」から「動くもの」になるまでの流れと、どんなプログラムにも共通する基本部品（変数、式、制御構造、関数）を一通り押さえます。すでにCを少しかじったことがある人にとっては復習になりますが、後の章で使う言葉をそろえる意味でも目を通してください。

2.1 ソースコードから実行ファイルまで

Cのプログラムは、人間が読めるソースコードとして書かれます。これはそのままでは動きません。コンピュータが実行できるのは、CPUが直接理解する機械語（machine code）だけだからです。ソースコードを機械語に翻訳する道具がコンパイラです。

実は、cc hello.c -o hello という一つのコマンドの裏で、いくつかの段階が順に実行されています。

graph LR
    A[ソースコード<br>hello.c] --> B[プリプロセス]
    B --> C[コンパイル]
    C --> D[アセンブル]
    D --> E[リンク]
    E --> F[実行ファイル<br>hello]

• プリプロセス（preprocess）：#include や #define といった、# で始まる命令を処理します。#include <stdio.h> は「stdio.h というファイルの中身をここに貼り付けよ」という意味で、printf などの機能を使えるようにします。#define で定義するマクロ（macro）は、コンパイル前にテキストを置き換える仕組みです。
• コンパイル（compile）：プリプロセス済みのCコードを、CPUごとのアセンブリ言語に翻訳します。
• アセンブル（assemble）：アセンブリ言語を機械語に翻訳し、オブジェクトファイルを作ります。
• リンク（link）：複数のオブジェクトファイルや、printf のような既製の部品（ライブラリ）をつなぎ合わせ、一つの実行ファイルにまとめます。

ふだんは一つのコマンドにまとまっているので意識する必要はありませんが、「ヘッダファイルを include し忘れた」「関数の定義が見つからない（リンクエラー）」といった失敗の原因を理解するには、この段階分けを知っておくと役に立ちます。各段階の詳細は^{[Brian, 1988]}の付録や^{[Robert, 2020]}で丁寧に解説されています。

2.2 main関数とプログラムの入り口

すべてのCプログラムは、main という名前の関数から実行が始まります。

#include <stdio.h>

int main(void) {
    printf("計算を始めます\n");
    return 0;
}

int main(void) を分解してみましょう。先頭の int は、この関数が整数（integer）を返すことを示します。main が返す整数は終了コードと呼ばれ、0 は「正常終了」を、それ以外は「何らかの異常」を意味する慣習です。括弧の中の void（ボイド、「空」の意）は「引数を受け取らない」という意味です。{ から } までが関数の中身で、上から順に実行されます。return 0; でこの値を呼び出し元（OS）に返してプログラムは終わります。

printf は文字列を画面に表示する関数です。末尾の \n は改行を表す特殊な書き方で、これがないと次の出力と同じ行にくっついてしまいます。

2.3 変数とデータ型

変数（variable）は、値に名前を付けて覚えておく入れ物です。Cでは、変数を使う前にその型（type）を宣言しなければなりません。型とは「その入れ物に何を入れるか」を表すもので、たとえば整数なら int、小数なら double です。

int count = 0;        // 整数の変数 count を 0 で初期化
double pi = 3.14159;  // 小数の変数 pi
char grade = 'A';     // 1文字を表す変数（'A' は文字定数）

// から行末まではコメントで、コンパイラに無視されます。複数行のコメントは /* ... */ でも書けます。

変数に最初の値を与えることを初期化（initialization）と呼びます。初期化していない変数の中身は不定（何が入っているかわからない）で、これはバグの温床です。宣言と同時に初期化する習慣をつけましょう。型については次章3. 基本型でさらに詳しく扱います。

2.4 式と演算子

式（expression）は、計算して値を生み出す断片です。1 + 2 も count * 3 も式です。Cの主な算術演算子は次のとおりです。

注意したいのは / です。整数同士の割り算は小数点以下が切り捨てられ、7 / 2 は 3 になります。3.5 がほしければ 7.0 / 2 のように、どちらかを小数にする必要があります。この「型によって演算の意味が変わる」性質は、言語処理系で割り算を実装するときに必ず向き合う問題です。

比較演算子（== 等しい、!= 等しくない、<、>、<=、>=）は、条件が成り立てば 1、成り立たなければ 0 という値を返します。Cには本来「真偽」専用の型がなく、0を偽、0以外を真として扱う点を覚えておいてください。

2.5 条件分岐とくり返し

プログラムを「上から順に実行する」だけでなく、条件によって枝分かれさせたり、くり返したりするのが制御構造（control flow）です。

条件分岐は if と else で書きます。

if (n % 2 == 0) {
    printf("偶数です\n");
} else {
    printf("奇数です\n");
}

くり返しは while や for を使います。次は1から10までの合計を求める例です。

int sum = 0;
for (int i = 1; i <= 10; i++) {
    sum += i;   // sum = sum + i と同じ
}
printf("合計は %d です\n", sum);

for (初期化; 継続条件; 更新) の三つの部分を見てみましょう。まず int i = 1 でカウンタを用意し、i <= 10 が成り立つ間くり返し、各回の最後に i++（i を1増やす）を実行します。sum += i は sum = sum + i の短い書き方です。printf の中の %d は「ここに整数を10進数で埋め込め」という指示で、後ろの sum の値に置き換わります。

くり返しは言語処理系にとって特別に重要です。なぜなら、インタプリタの本体は「次の命令を取り出して実行する」ことの巨大なくり返しだからです。このループの効率が処理系全体の速度を左右します（12. コンパイラの中身と処理系を速くする技法で詳しく扱います）。

2.6 関数

関数（function）は、ひとまとまりの処理に名前を付けて、何度でも呼び出せるようにする仕組みです。main も関数の一つでした。自分で関数を定義してみましょう。

#include <stdio.h>

// 二つの整数を受け取り、大きいほうを返す関数
int max(int a, int b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

int main(void) {
    int result = max(3, 8);
    printf("大きいほうは %d\n", result);  // 8 と表示される
    return 0;
}

int max(int a, int b) の読み方は、main のときと同じです。返り値の型が int、名前が max、そして括弧の中の int a, int b が引数（argument）、つまり呼び出し時に渡される値の受け皿です。max(3, 8) と呼ぶと、a に 3、b に 8 が入り、return で返された値が result に代入されます。

関数を使うと、複雑な処理を小さな部品に分けて考えられます。言語処理系のような大きなプログラムでは、「字句解析をする関数」「構文解析をする関数」「式を評価する関数」のように役割ごとに関数を分けるのが定石です。良い関数分割は、プログラムを読みやすく、直しやすくします^{[Brian, 1988]}。

2.7 この章のまとめ

• Cのソースコードは、プリプロセス・コンパイル・アセンブル・リンクを経て実行ファイルになる。
• プログラムは main 関数から始まる。
• 変数は型を持ち、使う前に宣言・初期化する。
• 式は値を生み、/ は整数だと切り捨てになるなど型に注意がいる。
• if／for／while で処理の流れを制御する。
• 処理は関数に分けて名前を付ける。

次章では、この「型」という考え方をさらに詳しく扱います。

3. 基本型

前章で「変数には型がある」と述べました。型はC言語の根幹であり、言語処理系を書くときには「処理系自身を実装するための型」と「処理系が扱う言語の型」の二つを同時に考えることになります。この章では、Cが持つ基本型の正体を見ていきます。型に別名を付ける typedef は、構造体や共用体を学んだ後の章（8. 型に別名を付ける typedef）で扱います。

3.1 ビットの解釈の仕方としての型

コンピュータのメモリに入っているのは、突き詰めれば 0 と 1 の並び、すなわちビット（bit）の列だけです。同じビット列でも、それを「整数」と思って読むか「小数」と思って読むかで、意味はまったく変わります。型とは、そのビット列をどう解釈し、どれだけの幅（バイト数）を占め、どんな演算ができるかを決める情報です。

たとえば32個のビット列 01000001... は、整数として読めばある数値ですが、文字として読めば 'A' かもしれません。型がこの解釈を確定させます。だからこそCは、変数を宣言するときに型を要求するのです。この「ビットの解釈」という見方は、後で共用体（6. 同じ場所を使い分ける共用体）を理解するときの土台になります。

graph TD
    A["メモリ上のビット列<br>01000001 00000000 ..."] --> B["int として解釈 → 65"]
    A --> C["char として解釈 → 'A'"]
    A --> D["float として解釈 → 別の値"]

3.2 整数型と、その幅

Cの整数型は一種類ではありません。表せる値の範囲（＝占めるビット数）によって、いくつかの型があります。

ここで「おおよそ」と書いたのには理由があります。Cの規格は、各型の正確なバイト数を固定していません^{[ISO/IEC, 2018]}。「int は short 以上、long は int 以上」といった大小関係は決まっていますが、具体的な幅は環境（CPUやコンパイラ）に委ねられています。手元の環境での実際の幅は sizeof 演算子で調べられます。

#include <stdio.h>

int main(void) {
    printf("int は %zu バイト\n", sizeof(int));
    printf("long は %zu バイト\n", sizeof(long));
    return 0;
}

sizeof(型) はその型が占めるバイト数を返します。printf の %zu は sizeof が返す型（size_t という符号なし整数型）を表示するための書式です。

3.3 符号の有無と固定幅整数型

整数型には、負の数を表せる符号付き（signed）と、負の数は表せないかわりに同じビット数でより大きな正の数まで表せる符号なし（unsigned）の区別があります。unsigned int のように unsigned を付けると符号なしになります。バイト列の長さ（バイナリのサイズ）や文字コードなど、負にならない量を扱うときは符号なしが自然です。

幅が環境依存だと困る場面のために、Cは幅を名前で固定した整数型を用意しています。<stdint.h> を include すると使えます。

#include <stdint.h>

int32_t  token_id;   // ちょうど32ビットの符号付き整数
uint8_t  byte;       // ちょうど8ビットの符号なし整数（バイト1個）
int64_t  big_value;  // ちょうど64ビットの符号付き整数

int32_t なら、どの環境でも必ず32ビットです。言語処理系では「バイトコードの1命令を uint8_t で表す」「整数値を int64_t で持つ」のように、幅をきっちり決めたい場面が多く、これらの型が活躍します^{[Robert, 2021]}。

3.4 浮動小数点型と文字

小数を扱うには浮動小数点型を使います。float（単精度、約4バイト）と double（倍精度、約8バイト）があり、精度が必要なら double を使うのが無難です。浮動小数点数は「だいたいの値」を表すもので、0.1 + 0.2 がちょうど 0.3 にならないなど、誤差が出ます。言語処理系で小数リテラルを実装するときは、この誤差の存在を前提に設計します。

文字は前章で触れたとおり char で表します。Cの世界では、char は実は小さな整数でもあります。'A' は文字コード（多くの環境ではASCIIの65）という整数として扱われ、'A' + 1 は 'B' の文字コードになります。字句解析で「この文字は数字か？」を c >= '0' && c <= '9' のように判定できるのは、文字が整数だからです。

3.5 暗黙の型変換と明示の型変換

異なる型の値が混ざった式では、型の変換（conversion）が起こります。Cはしばしば自動で変換します。これを暗黙の型変換（implicit conversion）と呼びます。たとえば int と double を足すと、int のほうが double に変換されてから計算されます。

自分の意思で変換するときは、キャスト（cast）と呼ぶ書き方を使います。

int   a = 7;
int   b = 2;
double result = (double)a / b;   // a を double に変換してから割る → 3.5

(double)a が「a を double として扱え」という明示の変換です。これがないと a / b は整数の割り算になって 3 に切り捨てられ、その後 double にしても 3.0 のままです。前章で触れた / の落とし穴は、こうしたキャストで回避できます。

3.6 この章のまとめ

• 型とは「ビット列をどう解釈し、どれだけの幅を取り、何ができるか」を決める情報。
• 整数型の幅は環境依存。移植性が要るなら int32_t などの固定幅整数型を使う。
• 符号なし整数の回り込みや、整数除算の切り捨てに注意する。
• 型変換には暗黙のものと明示（キャスト）のものがある。警告を活用する。

次章では、C言語最大の山場であるポインタに挑みます。型の話がここでも土台になります。

4. ポインタとメモリ

ポインタはC言語でいちばん難しいと言われる概念です。しかし言語処理系を書くなら避けて通れません。構文木のノードをつなぐのも、文字列を扱うのも、関数を値として渡すのも、すべてポインタが土台になります。この章では、メモリのモデルから始めて、ポインタを「こわくない道具」にしていきます。

4.1 メモリは巨大な番地付きの棚である

ポインタを理解する第一歩は、メモリ（memory）のイメージを持つことです。コンピュータのメモリは、1バイトずつ区切られた巨大な棚だと考えてください。それぞれの区画には番地（address、アドレス）という通し番号が振られています。0番地、1番地、2番地……と続く、ロッカーの番号のようなものです。

変数を宣言すると、その型に応じた区画がメモリ上に確保されます。int x = 42; と書くと、どこかの番地に4バイト分の場所が取られ、そこに 42 が書き込まれます。

graph LR
    subgraph メモリ
    A["番地 1000<br>42"]
    B["番地 1004<br>..."]
    C["番地 1008<br>..."]
    end
    X["変数 x"] -.指している.-> A

ポインタとは、この「番地」を値として持つ変数です。普通の変数が「数値そのもの」を持つのに対し、ポインタは「値がどこにあるか（番地）」を持ちます。住所を書いたメモのようなものだと考えるとよいでしょう。メモには家そのものは入っていませんが、それをたどれば家にたどり着けます。

4.2 アドレス演算子と間接参照演算子

ポインタを扱う基本の道具は二つです。アドレス演算子 & と、間接参照演算子 * です。

#include <stdio.h>

int main(void) {
    int x = 42;
    int *p = &x;     // p は「x の番地」を持つポインタ

    printf("x の値   : %d\n", x);    // 42
    printf("x の番地 : %p\n", (void *)p);  // 例: 0x7ffd...
    printf("p の指す先: %d\n", *p);  // 42（p をたどって読む）

    *p = 100;        // p の指す先（＝x）に 100 を書く
    printf("x の値   : %d\n", x);    // 100 に変わっている

    return 0;
}

一つずつ読み解きましょう。int *p は「p は int を指すポインタだ」という宣言です。型の int に * を付けると「それを指すポインタ型」になります。&x は「x の番地」を取り出す式で、これを p に入れています。

*p は「p が指す先の値」を表します。これを間接参照（dereference）と呼びます。*p は読み出しにも書き込みにも使えて、*p = 100; と書くと p が指す場所（つまり x）に 100 が書き込まれます。p 自身は番地を持ったままで、その指す先を通して x を書き換えているのです。

4.3 なぜポインタが必要なのか

「値そのものを使えばいいのに、なぜわざわざ番地を介すのか」と思うかもしれません。言語処理系づくりの観点から、ポインタが要る理由は大きく三つあります。

第一に、関数に変更を持ち帰らせるためです。Cでは、関数に値を渡すとそのコピーが渡されます（値渡し）。だから関数の中で引数を書き換えても、呼び出し元の変数は変わりません。呼び出し元の変数そのものを書き換えてほしいときは、その番地（ポインタ）を渡します。

void increment(int *n) {
    *n = *n + 1;     // 指す先を書き換える
}

int main(void) {
    int count = 5;
    increment(&count);   // count の番地を渡す
    // count はここで 6 になっている
    return 0;
}

第二に、大きなデータを安く渡すためです。構文木のノードのように大きな構造体を関数に渡すたびにコピーしていては、時間もメモリも無駄になります。番地（多くの環境で8バイト）だけを渡せば、中身はコピーせず共有できます。

第三に、データ構造を組み立てるためです。木やリストのように「あるノードが別のノードを指す」構造は、ポインタなしには作れません。これは後の章で構文木を作るときの核心になります^{[Andrew, 1998]}。

4.4 ヌルポインタ

ポインタは「どこも指していない」状態を表せます。それがヌルポインタ（null pointer）で、NULL という名前で書きます（<stddef.h> などで定義されています）。

int *p = NULL;     // いまは何も指していない

if (p != NULL) {
    printf("%d\n", *p);   // 指す先があるときだけ読む
}

ヌルポインタは「まだ値がない」「探したが見つからなかった」といった状況を表すのに使います。たとえば「シンボルテーブルから変数を探したが未定義だった」ときに NULL を返す、という設計はよくあります。

4.5 配列とポインタの関係

配列（array）は、同じ型の値をメモリ上に連続して並べたものです。

int nums[5] = {10, 20, 30, 40, 50};
printf("%d\n", nums[2]);   // 30（添字は 0 から数える）

nums[2] の [2] が添字（index）で、先頭を 0 として数えます。だから3番目の要素は nums[2] です。

Cでは配列とポインタが深く結びついています。配列の名前は、多くの場面で先頭要素の番地として振る舞います。そのため nums[i] は、内部的には「先頭の番地から i 個分ずらした場所をたどる」という計算になっています。この「番地をずらす」計算をポインタ演算（pointer arithmetic）と呼びます。

int *p = nums;       // 配列名は先頭の番地。p は nums[0] を指す
printf("%d\n", *p);       // 10
printf("%d\n", *(p + 2)); // 30 … nums[2] と同じ意味

p + 2 は「2バイト先」ではなく「int 2個分先」を指します。ポインタ演算は型の幅を考慮してくれるのです。この性質は、字句解析で文字列を1文字ずつ読み進めるときなどに自然に使われます。

4.6 文字列と char 配列

Cには専用の「文字列型」がありません。文字列は char の配列として表され、末尾に '\0'（ヌル文字、値が0の文字）を置いて「ここで終わり」を示します。

char word[] = "let";   // 'l' 'e' 't' '\0' の4バイトが並ぶ

"let" と書くと文字3個に見えますが、終端の '\0' を含めてメモリ上は4バイトです。文字列を扱う関数（strlen で長さを測る、strcmp で比較する、など）は、この '\0' を目印に文字列の終わりを判断します。言語処理系の字句解析では、ソースコードをこの「char の並び」として受け取り、先頭からポインタで読み進めていきます。

4.7 言語処理系でトークンを読み進める

ここまでの道具を組み合わせると、字句解析の最初の一歩が書けます。次の関数は、文字列の中の空白を読み飛ばし、最初の非空白文字を指すポインタを返します。

#include <stdio.h>

// p が指す位置から空白を飛ばし、次の文字の位置を返す
const char *skip_spaces(const char *p) {
    while (*p == ' ' || *p == '\t') {
        p++;            // ポインタを1文字進める
    }
    return p;
}

int main(void) {
    const char *src = "   1 + 2";
    const char *p = skip_spaces(src);
    printf("最初の文字は '%c'\n", *p);   // '1'
    return 0;
}

while (*p == ' ' || ...) は「p が指す文字が空白である間」くり返す、という意味です。p++ でポインタを1文字進め、空白でない文字に出会ったらループを抜けます。最後に、その位置を指すポインタを返します。ソースコード全体を先頭から終端までこうやって舐めていくのが、字句解析の骨組みです^{[Robert, 2021]}。const という見慣れない語が付いていますが、これは「指す先を書き換えない」という約束で、専用の章（9. constという書き換えないための約束）で詳しく扱います。

4.8 この章のまとめ

• メモリは番地付きの棚であり、ポインタはその番地を値として持つ。
• & で番地を取り、* で指す先をたどる（間接参照）。
• ポインタは「関数に変更を持ち帰らせる」「大きなデータを安く渡す」「データ構造を組む」ために要る。
• どこも指さないポインタは NULL。たどる前に確認する。
• 配列とポインタは地続きで、添字アクセスはポインタ演算で説明できる。範囲外アクセスに注意。
• 文字列は '\0' 終端の char 配列。字句解析はこれをポインタで読み進める。

ポインタを手にしたことで、次の部では複雑なデータ構造（構文木や値の表現）を組み立てられるようになります。

第II部　データを形にする

言語処理系の仕事の半分は「データの表現」です。トークン、構文木（AST）、実行時の値、シンボルテーブル、どれもメモリ上のデータ構造として表現しなければなりません。

この部では、複数の値をまとめる構造体（struct）、同じ場所を複数の解釈で使い分ける共用体（union）、関数そのものをデータとして扱う関数ポインタ、変更しないことを宣言する const、そして必要なときにメモリを確保する動的メモリ管理を学びます。これらを組み合わせると、構文木のような複雑なデータ構造がきれいに書けるようになります。

5. 複数の値をひとまとめにする構造体

言語処理系では、「いくつかの値がセットで意味を持つ」場面が無数にあります。トークンは「種類」と「位置」と「文字列」をセットで持ちますし、構文木のノードは「演算子」と「左の子」と「右の子」をセットで持ちます。こうした「関連する値の束」を表すのが構造体（struct）です。この章では構造体を学び、それを使って構文木の骨組みを作るところまで進みます。

5.1 なぜ構造体が要るのか

たとえばトークンを表すのに、種類・行番号・文字列という三つの情報を別々の変数で持つとどうなるでしょう。

int   token_kind;
int   token_line;
char *token_text;

トークンが100個あれば、これらを100組ばらばらに管理することになります。「3番目のトークン」の三つの情報がどれとどれなのかを取り違えれば、すぐにバグです。関連する値は、一つの箱にまとめて名前を付けたほうがよい。それが構造体です。

struct Token {
    int   kind;   // トークンの種類
    int   line;   // 何行目にあったか
    char *text;   // 元の文字列
};

struct Token { ... }; で「Token という名前の構造体型」を定義しています。中の kind、line、text をメンバ（member）と呼びます。これで「トークン1個分」を表す新しい型ができました。末尾のセミコロンを忘れやすいので注意してください。

5.2 構造体の宣言と初期化とメンバアクセス

定義した構造体型は、ふつうの型と同じように変数を作れます。

struct Token t;          // Token 型の変数 t
t.kind = 1;              // メンバに代入（ドットでアクセス）
t.line = 3;
t.text = "let";

printf("種類=%d 行=%d 文字列=%s\n", t.kind, t.line, t.text);

メンバには .（ドット）でアクセスします。t.kind は「t の kind メンバ」という意味です。宣言と同時にまとめて初期化することもできます。

struct Token t = { .kind = 1, .line = 3, .text = "let" };

.kind = 1 のようにメンバ名を指定する初期化（指示付き初期化子）は、どのメンバに何を入れているかが一目でわかるのでおすすめです。指定しなかったメンバは 0（ポインタなら NULL）で埋められます。

5.3 typedefと組み合わせて短く書く

ここまで見てきたように、struct Token のように毎回 struct を書くのは少し冗長です。typedef キーワード（詳しくは後の章（8. 型に別名を付ける typedef）で扱います）を使うと、すっきりします。

typedef struct Token {
    int   kind;
    int   line;
    char *text;
} Token;          // これで「Token」だけで使える

Token t;          // struct Token t; と書かなくてよい

typedef struct Token { ... } Token; は、構造体の定義と別名付けを同時に行う書き方です。以後は Token と書くだけで済みます。本書では、これ以降この書き方を標準とします。多くの実際の言語処理系も、この typedef struct のスタイルを採用しています^{[Robert, 2021]}。

5.4 ポインタ経由でメンバを取り出すアロー演算子

構造体は大きくなりがちなので、関数に渡すときは前章で学んだとおりポインタで渡すのが定石です。コピーを避けられますし、関数から中身を書き換えることもできます。

ポインタ経由でメンバにアクセスするときは、専用のアロー演算子 -> を使います。

void print_token(const Token *t) {
    // (*t).kind と書く代わりに t->kind と書ける
    printf("種類=%d 行=%d\n", t->kind, t->line);
}

int main(void) {
    Token t = { .kind = 1, .line = 3, .text = "let" };
    print_token(&t);     // 番地を渡す
    return 0;
}

t->kind は (*t).kind、すなわち「t が指す構造体の kind メンバ」と同じ意味です。ポインタをたどってからメンバを取り出す操作はあまりに頻出するので、-> という短い記法が用意されているのです。構造体を扱うコードでは、. よりむしろ -> を見かけることのほうが多いでしょう。

5.5 自分自身を指す構造体で木をつくる

構造体の真価は、メンバに「自分と同じ型へのポインタ」を持てることで発揮されます。これにより、木やリストのような再帰的なデータ構造が作れます。言語処理系の核心である構文木（AST）を、いよいよ表現してみましょう。

二項演算（左 演算子 右）のノードを考えます。たとえば 1 + 2 なら、+ のノードが左に 1、右に 2 をぶら下げます。「左」と「右」もまたノードなので、メンバの型は「ノードへのポインタ」になります。

typedef struct Node {
    int op;              // 演算子の種類（'+' '-' など。今は文字コードで表す）
    int value;           // 葉（数値）のときの値
    struct Node *left;   // 左の子ノードへのポインタ
    struct Node *right;  // 右の子ノードへのポインタ
} Node;

ここで left と right の型が struct Node *、つまり「Node を指すポインタ」になっている点が肝心です。構造体の中で、まだ定義の途中である自分自身を「ポインタ」としてなら参照できるのです（本体をそのまま入れることはできません。大きさが無限になってしまうからです）。typedef 後の Node ではなく struct Node と書いているのも、定義の途中だからです。

数値の葉ノードと、演算ノードを作る関数を用意します。

#include <stdlib.h>

// 数値（葉）ノードを作る
Node *new_number(int value) {
    Node *n = malloc(sizeof(Node));   // ノード1個分のメモリを確保
    n->op = 0;                        // 0 は「葉」を表すことにする
    n->value = value;
    n->left = NULL;
    n->right = NULL;
    return n;
}

// 二項演算ノードを作る
Node *new_binary(int op, Node *left, Node *right) {
    Node *n = malloc(sizeof(Node));
    n->op = op;
    n->value = 0;
    n->left = left;
    n->right = right;
    return n;
}

malloc（メモリ確保）という新顔が出てきました。これはプログラムの実行中に必要なだけメモリを借りる関数で、専用の章（10. 動的メモリ管理）で詳しく扱います。いまは「ノード1個分の場所を借りて、その番地を返してくれる」とだけ理解すれば十分です。sizeof(Node) で必要なバイト数を渡しています。

これらを使えば 1 + 2 * 3 の構文木が組み立てられます。

// 1 + (2 * 3) を表す木を作る
Node *tree = new_binary('+',
                 new_number(1),
                 new_binary('*', new_number(2), new_number(3)));

関数の呼び出しが入れ子になっているのが、そのまま木の形に対応しています。+ ノードの右の子が * ノードになっている様子が、コードからも読み取れます。

5.6 木をたどって計算する

構文木ができたら、それを根からたどって計算できます。木のような再帰的データは、再帰関数（自分自身を呼び出す関数）で処理するのが自然です。

int eval(const Node *n) {
    if (n->op == 0) {        // 葉なら、その値を返す
        return n->value;
    }
    int l = eval(n->left);   // 左の子を計算（再帰）
    int r = eval(n->right);  // 右の子を計算（再帰）
    switch (n->op) {
        case '+': return l + r;
        case '-': return l - r;
        case '*': return l * r;
        case '/': return l / r;
    }
    return 0;   // ここには来ない想定
}

eval は「ノードを受け取り、その部分木を計算した値を返す」関数です。葉（op == 0）ならその値をそのまま返し、そうでなければ左右の子をそれぞれ eval で計算してから、演算子に応じて組み合わせます。switch 文は、n->op の値ごとに処理を振り分ける制御構造で、たくさんの if を並べるより読みやすくなります。各 case の後の値が一致したところが実行されます。

eval(tree) を呼べば、さきほど作った 1 + 2 * 3 の木から 7 が得られます。これがインタプリタの中核、すなわち「木をたどって意味を計算する」処理（木構造インタプリタ / tree-walking interpreter）の最小形です^{[Robert, 2021]}。構造体とポインタと再帰だけで、もう小さなインタプリタの心臓ができてしまいました。

5.7 この章のまとめ

• 構造体は、関連する複数の値（メンバ）を一つの型にまとめる。
• メンバには .（本体）または ->（ポインタ経由）でアクセスする。
• typedef struct で struct を省ける書き方が定番。
• メンバに「自分自身へのポインタ」を持たせると、木やリストが作れる。
• 構文木は構造体で表し、再帰関数でたどって計算できる。これが木構造インタプリタの核。

次章では、ノードの種類によって持つべき情報が違う、という問題をきれいに解く共用体を学びます。

6. 同じ場所を使い分ける共用体

前章の構文木ノードには、少しもったいない点がありました。数値の葉ノードは value しか使わず left／right は無駄になり、演算ノードは逆に value を使いません。種類によって必要なメンバが違うこの状況を、きれいに表すのが共用体（union）です。共用体は言語処理系で「値」や「ノード」を表現するときの定番道具で、この章はその使いこなしを扱います。

6.1 メンバが場所を共有する共用体

構造体は、すべてのメンバがそれぞれ別の場所を占めました。共用体は、すべてのメンバが同じ場所を共有します。

union Number {
    int    as_int;      // 整数として見たときの値
    double as_double;   // 小数として見たときの値
};

見た目は構造体（struct）とそっくりで、struct を union に変えただけです。しかし意味はまったく違います。union Number のサイズは、as_int（4バイト）と as_double（8バイト）の合計ではなく、いちばん大きいメンバに合わせた8バイトです。as_int と as_double は、その同じ8バイトを重ねて使います。

graph TD
    subgraph struct["struct（別々の場所）"]
    S1["as_int<br>4バイト"]
    S2["as_double<br>8バイト"]
    end
    subgraph union["union（同じ場所を共有）"]
    U1["as_int / as_double<br>同じ8バイト"]
    end

これは3. 基本型で述べた「型とはビットの解釈の仕方」という話と直結します。共用体は、同じビット列を、どのメンバの型として解釈するかを選べる仕組みなのです。

union Number n;
n.as_int = 65;
printf("%d\n", n.as_int);   // 65

6.2 書いたのと違うメンバを読むと

共用体には、知らずに使うと痛い目を見る性質があります。あるメンバに書き込んだあと、別のメンバから読むと、結果は意味をなしません。

union Number n;
n.as_double = 3.14;
printf("%d\n", n.as_int);   // 3 ではなく、ビットを int と誤解した謎の値

as_double として書いた 3.14 のビット列を、as_int として読み解いてしまうので、出てくるのはでたらめな整数です。共用体は「いま、どのメンバとして使っているか」を自分で覚えておかなければならないのです。共用体自身はそれを記録してくれません。

6.3 種類の印を添えるタグ付き共用体

解決策はシンプルです。共用体と一緒に、「いまどの種類か」を表すタグ（tag）を構造体に同居させます。これをタグ付き共用体（tagged union）と呼びます。言語処理系で「いろいろな種類の値」を一つの型で表すときの、ほぼ標準的なやり方です。

実行時の値が「整数」か「小数」か「真偽値」のいずれかを取る言語を考えましょう。

typedef enum {
    VAL_INT,
    VAL_DOUBLE,
    VAL_BOOL,
} ValueType;

typedef struct {
    ValueType type;          // タグ：いまどの種類か
    union {
        int64_t as_int;      // type == VAL_INT のとき有効
        double  as_double;   // type == VAL_DOUBLE のとき有効
        int     as_bool;     // type == VAL_BOOL のとき有効
    } u;                     // 種類ごとの中身（場所を共有）
} Value;

新顔の enum（列挙型 / enumeration）は、名前付きの整数定数をまとめて定義する仕組みです。ここでは VAL_INT が 0、VAL_DOUBLE が 1、VAL_BOOL が 2 という整数に自動で割り当てられます。数字を直接書くより、VAL_INT という名前で書いたほうが意図が明確で、間違いも減ります。これがタグの正体です。

構造体 Value は、タグ type と、種類ごとの中身を入れる共用体 u の二つを持ちます。「type を見れば、u のどのメンバが有効かがわかる」という約束で運用します。int64_t は3. 基本型で学んだ固定幅整数型です。

6.4 タグ付き共用体を安全に使う

タグ付き共用体は、「作るときにタグも一緒に立てる」「使うときはタグを見てから対応するメンバを読む」という二つの規律で安全に使えます。値を作る関数を用意しましょう。

Value make_int(int64_t x) {
    Value v;
    v.type = VAL_INT;       // タグを立て、
    v.u.as_int = x;         // 対応するメンバに書く
    return v;
}

Value make_double(double x) {
    Value v;
    v.type = VAL_DOUBLE;
    v.u.as_double = x;
    return v;
}

Value make_bool(int b) {
    Value v;
    v.type = VAL_BOOL;
    v.u.as_bool = b;
    return v;
}

タグの設定とメンバへの書き込みを必ずセットで行うのがコツです。これらの関数を窓口にすれば、「タグだけ立てて中身を入れ忘れる」事故を防げます。

使う側では、タグで分岐してから読みます。値を画面に表示する関数を書いてみます。

#include <stdio.h>
#include <stdbool.h>   // bool 型を使うため

void print_value(Value v) {
    switch (v.type) {
        case VAL_INT:
            printf("%lld\n", (long long)v.u.as_int);
            break;
        case VAL_DOUBLE:
            printf("%g\n", v.u.as_double);
            break;
        case VAL_BOOL:
            printf("%s\n", v.u.as_bool ? "true" : "false");
            break;
    }
}

switch (v.type) でタグを調べ、その種類に対応するメンバだけを読んでいます。VAL_INT の枝では as_int しか触りません。こうすれば「書いたのと違うメンバを読む」事故は起きません。各 case の末尾の break は「ここで switch を抜ける」という意味で、これを忘れると次の case まで実行が流れ落ちてしまうので注意してください。

6.5 なぜタグ付き共用体が言語処理系に効くのか

タグ付き共用体は、言語処理系のあらゆる場所に現れます。代表的なのは次の二つです。

ひとつは、いま見た実行時の値（runtime value）の表現です。動的に型が決まる言語では、変数に入る値が整数か文字列かオブジェクトか、実行してみないとわかりません。一つの Value 型でそれらすべてを表すために、タグ付き共用体がうってつけなのです^{[Robert, 2021]}。

もうひとつは、構文木ノードの表現です。前章の Node は数値ノードと演算ノードを同じ構造体で表し、未使用のメンバが無駄になっていました。タグ付き共用体を使えば、ノードの種類ごとに必要なメンバだけを持たせ、メモリの無駄をなくせます。

typedef enum { ND_NUM, ND_BINARY } NodeKind;

typedef struct Node {
    NodeKind kind;
    union {
        int64_t value;                  // ND_NUM のとき
        struct {                        // ND_BINARY のとき
            int op;
            struct Node *left;
            struct Node *right;
        } binary;
    } u;
} Node;

数値ノードは u.value だけを、演算ノードは u.binary 一式だけを使います。共用体のおかげで、両者は同じ場所を共有し、ノード1個のサイズは「いちばん大きい種類」に抑えられます。コンパイラの教科書でも、構文木をこの形（種類タグ＋共用体）で表す例が数多く紹介されています^{[Andrew, 1998]}。

6.6 値を使ってインタプリタを育てる

前章のインタプリタは整数しか返せませんでした。Value を返すようにすれば、整数と小数が混ざった計算もできます。考え方の要点だけ示します。

Value eval(const Node *n) {
    if (n->kind == ND_NUM) {
        return make_int(n->u.value);
    }
    Value l = eval(n->u.binary.left);
    Value r = eval(n->u.binary.right);
    // ここで l と r のタグを見て、整数同士なら整数演算、
    // 片方でも小数なら小数演算、と振り分ける（前章 basics.md の型変換の話が効いてくる）
    if (l.type == VAL_INT && r.type == VAL_INT) {
        switch (n->u.binary.op) {
            case '+': return make_int(l.u.as_int + r.u.as_int);
            /* 他の演算子も同様 */
        }
    }
    /* 小数が絡む場合の処理は省略 */
    return make_int(0);
}

左右の子のタグを見て、整数同士か、小数が絡むかを判断し、適切な演算を選びます。これはまさに、動的型付き言語のインタプリタが実行時に行っている判断そのものです。「タグを見て分岐する」というこのパターンが、処理系のあちこちで繰り返されることになります。

6.7 この章のまとめ

• 共用体はすべてのメンバが同じメモリを共有し、サイズは最大メンバに合わせる。
• 「書いたのと違うメンバを読む」と結果は無意味。共用体は単独では危険。
• タグ（多くは enum）を添えたタグ付き共用体にすれば安全に使い分けられる。
• 作るときにタグを立て、使うときはタグで分岐してから読む、という規律を守る。
• 実行時の値と構文木ノードの表現は、どちらもタグ付き共用体の代表的な使いどころ。

次章では、関数そのものをデータとして扱う関数ポインタに進みます。タグで分岐するかわりに「関数の表」を引く、という別の設計が見えてきます。

7. 処理を値として持ち運ぶ関数ポインタ

これまで、ポインタは「データのありか」を指していました。実は、ポインタは関数のありかも指せます。それが関数ポインタ（function pointer）です。関数を値として変数に入れたり、引数で渡したり、表に並べたりできるようになります。言語処理系では、この道具が「組み込み関数の登録」や「命令ディスパッチ」といった場面で働きます。

7.1 関数もメモリ上にある

4. ポインタとメモリで「変数はメモリ上のどこかに置かれ、番地を持つ」と学びました。実は関数も同じです。コンパイルされた関数の機械語は、メモリ上のどこかに置かれ、先頭の番地を持っています。関数ポインタとは、その「関数の先頭番地」を持つポインタです。番地さえあれば、そこにジャンプして実行できます。これが関数を値として扱える理由です。

まず、ポインタに入れたい関数たちを用意します。どれも「int を二つ受け取り int を返す」同じ形にそろえておきます。

int add(int a, int b) { return a + b; }
int sub(int a, int b) { return a - b; }
int mul(int a, int b) { return a * b; }

7.2 関数ポインタの宣言の読み方

関数ポインタの宣言は、Cの文法の中でもとっつきにくい部類です。落ち着いて読み解きましょう。

int (*fp)(int, int);

これは「fp は、int を二つ受け取り int を返す関数を指すポインタである」という宣言です。内側から読むのがコツです。(*fp) で「fp はポインタ」、その後ろの (int, int) で「指す先は2引数の関数」、先頭の int で「その関数は int を返す」となります。(*fp) の括弧は必須で、外すと意味が変わってしまいます（int *fp(int, int) は「int * を返す関数の宣言」になってしまう）。

この長い型は、typedef（詳しくは8. 型に別名を付ける typedef）で別名を付けると一気に読みやすくなります。

// 「int を二つ受け取り int を返す関数」へのポインタ型に BinOp という名前を付ける
typedef int (*BinOp)(int, int);

BinOp op = add;     // 関数 add の番地を入れる（& は省略できる）
int r = op(3, 4);   // op を通して add を呼ぶ → 7

関数名 add は、それ自体が「関数の番地」として振る舞います（配列名が先頭要素の番地になったのと同じ感覚です）。だから op = add; で番地を代入でき、op(3, 4) と書けば、op が指す関数（いまは add）が呼ばれます。typedef のおかげで、関数ポインタが普通の変数のように扱えています。

7.3 表を引いて処理を選ぶディスパッチテーブル

関数ポインタの代表的な使い道が、ディスパッチテーブル（dispatch table）です。「種類」と「処理」を表（配列）で対応づけておき、種類で表を引いて対応する関数を呼ぶ、という手法です。

前章までのインタプリタでは、演算子ごとの処理を switch で振り分けていました。これを関数ポインタの表に置き換えてみましょう。まず、演算子の文字を 0〜3 の番号に対応させ、その番号で表を引きます。

typedef int (*BinOp)(int, int);

// 番号 → 処理 の対応表
BinOp op_table[4] = {
    add,   // 0 番: 加算
    sub,   // 1 番: 減算
    mul,   // 2 番: 乗算
    div_,  // 3 番: 除算（div は標準ライブラリと名前が衝突するので別名に）
};

int apply(int op_index, int a, int b) {
    return op_table[op_index](a, b);   // 表を引いて、得た関数を呼ぶ
}

op_table[op_index] で関数ポインタを取り出し、その直後に (a, b) を付けて呼び出しています。switch のように分岐を書き並べる必要がなく、表に一行足すだけで演算子を増やせます。種類が増えても表に追記するだけでよく、この拡張のしやすさが、ディスパッチテーブルの利点です。インタプリタの命令実行ループをこの方式で組むのは、古くから知られた効率化の定番でもあります^{[James, 1973]}。

switch 方式とディスパッチテーブル方式は、どちらが絶対に優れるというものではありません。

最後の行が要点です。次に見る「組み込み関数の登録」のように実行中に処理を足したい場面では、switch では手が出ません。関数ポインタの表なら、実行中に中身を差し替えられます。

7.4 組み込み関数を登録する

多くの言語には、print や len のような組み込み関数（built-in function）が用意されています。言語処理系の中では、これらを「名前」と「実体（C言語の関数）」の対応として持っておき、ユーザーのプログラムがその名前を呼んだら対応するC関数を実行します。この対応づけに、関数ポインタが使えます。

#include <stdio.h>
#include <string.h>

typedef Value (*Builtin)(Value arg);   // 組み込み関数の形（Value は union.md の型）

typedef struct {
    const char *name;   // 言語側から見た名前
    Builtin fn;         // 対応する C 関数
} BuiltinEntry;

// 実体となる C 関数たち
Value builtin_print(Value arg) {
    print_value(arg);          // union.md で作った表示関数を使う
    return make_int(0);
}

Value builtin_abs(Value arg) {
    int64_t x = arg.u.as_int;
    return make_int(x < 0 ? -x : x);
}

// 名前 → 関数 の登録表
BuiltinEntry builtins[] = {
    { "print", builtin_print },
    { "abs",   builtin_abs   },
};

// 名前で表を引いて呼び出す
Value call_builtin(const char *name, Value arg) {
    for (int i = 0; i < 2; i++) {
        if (strcmp(builtins[i].name, name) == 0) {
            return builtins[i].fn(arg);   // 見つけた関数を呼ぶ
        }
    }
    printf("未定義の関数: %s\n", name);
    return make_int(0);
}

BuiltinEntry は「名前」と「関数ポインタ」を組にした構造体です（5. 複数の値をひとまとめにする構造体の応用です）。その配列 builtins[] が登録表になります。call_builtin は、与えられた名前を strcmp（文字列の比較。等しければ 0 を返す）で表と突き合わせ、一致した行の fn を呼び出します。

この設計の良いところは、組み込み関数を足す作業が「表に一行加える」だけで済むことです。新しい関数 builtin_sqrt を書いて { "sqrt", builtin_sqrt } を表に並べれば、もう言語の中から sqrt が呼べます。インタプリタの本体には一切手を入れません。関数ポインタが「処理を値として持ち運べる」からこそ、こうした拡張可能な設計が書けます^{[Robert, 2021]}。

7.5 標準ライブラリでの関数ポインタ

関数ポインタは、特殊な道具ではありません。C標準ライブラリにも、関数ポインタを受け取る関数があります。代表が qsort です。

#include <stdlib.h>

int compare_int(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y);   // x>y なら正、x<y なら負、等しければ 0
}

int nums[] = {3, 1, 4, 1, 5, 9, 2, 6};
qsort(nums, 8, sizeof(int), compare_int);   // compare_int の流儀で並べ替え

qsort は「どう並べ替えるか」を知りません。並べ替えの基準を、compare_int という関数ポインタで外から受け取るのです。だから同じ qsort で、昇順にも降順にも、構造体の特定メンバ順にも並べ替えられます。「処理の一部を呼び出し側から渡す」というこの考え方はコールバック（callback）と呼ばれ、関数ポインタの最も普遍的な用途です。言語処理系でも、構文木の各ノードに対して任意の処理を適用する「ビジター」のような場面で同じ発想が使えます。

7.6 この章のまとめ

• 関数もメモリ上にあり、その番地を持つのが関数ポインタ。
• 宣言 int (*fp)(int, int) は内側から読む。typedef で別名を付けると扱いやすい。
• ディスパッチテーブルは「種類→処理」を表で引く手法。実行中に処理を差し替えられるのが強み。
• 組み込み関数は「名前→関数ポインタ」の表で登録すると、拡張が一行で済む。
• qsort のように、処理の一部を関数ポインタで外から渡す手法をコールバックと呼ぶ。

次章では、これまで何度か顔を出してきた typedef（型に別名を付ける機能）を改めてまとめます。

8. 型に別名を付ける typedef

基本型（3. 基本型）、ポインタ（4. ポインタとメモリ）、構造体（5. 複数の値をひとまとめにする構造体）、共用体（6. 同じ場所を使い分ける共用体）を学んだところで、typedef を改めて取り上げます。typedef は既存の型に別名（alias）を付ける機能で、言語処理系づくりで特に効いてきます。

8.1 typedef の基本

typedef int64_t Value;   // 「Value」は int64_t の別名になる

Value x = 100;           // int64_t x = 100; と同じ意味

なぜ別名が役立つのでしょうか。第一に、意図が名前で伝わるからです。int64_t result と書くより Value result（処理系が扱う値だ）と書くほうが、コードを読む人に役割が伝わります。

第二に、後から変えやすいことです。いま値を int64_t で表していても、将来「小数も扱いたい」と思うかもしれません。コード中のあちこちに int64_t と直書きしていると全部を直す羽目になりますが、typedef int64_t Value; の一行だけにまとめておけば、その一行を typedef double Value; に変えるだけで済みます。この「一箇所で型を切り替えられる」性質は、設計を試行錯誤する言語処理系づくりと相性が良いのです^{[Andrew, 1998]}。

8.2 構造体や共用体、関数ポインタとの組み合わせ

typedef の本当の威力は、構造体（5. 複数の値をひとまとめにする構造体）や共用体（6. 同じ場所を使い分ける共用体）、関数ポインタ（7. 処理を値として持ち運ぶ関数ポインタ）のような、書くと長くなる型に短い名前を付けられる点にあります。これらの章で typedef struct や typedef union のパターンが登場しましたが、改めて整理します。

// 構造体に別名を付ける（struct.md で使ったパターン）
typedef struct Token {
    int   kind;
    int   line;
    char *text;
} Token;

Token t;   // struct Token t; と書かずに済む

// 関数ポインタ型に分かりやすい名前を付ける
typedef int (*BinaryOp)(int, int);

BinaryOp ops[] = { add, sub, mul };   // int (*ops[])(int, int) と書くより明快

8.3 この章のまとめ

• typedef は既存の型に別名を付け、意図を伝え、後からの差し替えを容易にする。
• 構造体・共用体・関数ポインタのような複雑な型に短い名前を付けるのに特に有効。
• 別名を作るだけで新しい型ではないため、コンパイラは型の取り違えを検出しない。

次章では、これまで何度か顔を出してきた const（「書き換えない」という約束）を扱います。

9. constという書き換えないための約束

これまでの章で、const char *p のような書き方が何度か登場しました。const（コンスト、「定数の」の意）は「この値は書き換えない」とコンパイラに宣言するキーワードです。一見すると地味ですが、const を使いこなすと、バグを未然に防ぎ、コードの意図を明確にし、ときには最適化の助けにもなります。言語処理系のように大きく長持ちするプログラムでは、この「約束」が効いてきます。

9.1 コンパイラに守らせる「約束」としてのconst

C言語では、変数は基本的にいつでも書き換えられます。const を付けると、その変数は初期化のあと書き換えられなくなります。

const int MAX_DEPTH = 1000;   // 再帰の最大の深さ
MAX_DEPTH = 2000;             // ← コンパイルエラー：const を書き換えようとした

MAX_DEPTH を書き換えようとすると、コンパイラがエラーで止めてくれます。これは単なる制限ではなく、安全装置です。「この値は途中で変わらないはずだ」という設計者の意図を、コンパイラが機械的にチェックしてくれるのです。人間の注意力に頼るより、はるかに確実です^{[Robert, 2020]}。

const は、プログラムのあちこちに散らばる「変えてはいけない値」に意図を込めるのに向いています。マクロ（#define）でも定数は作れますが、const は型を持つぶん、型チェックの恩恵を受けられます。

9.2 ポインタのどこが定数なのか

const がいちばん混乱を呼ぶのは、ポインタと組み合わさったときです。ポインタには「指す先」と「ポインタ自身」という二つの書き換え対象があり、const がどちらに掛かるかで意味が変わります。

int a = 1, b = 2;

const int *p = &a;   // (1) 指す先が const：*p は書き換え不可、p は変更可
int *const q = &a;   // (2) ポインタ自身が const：*q は書き換え可、q は変更不可
const int *const r = &a;  // (3) 両方 const

それぞれ何ができて何ができないかを表にします。

見分け方のコツは、「const のすぐ右にあるものが守られる」と読むことです。const int *p は const の右が int（指す先）なので指す先が守られ、int *const q は const の右が *（ポインタ自身）なのでポインタが守られます。言語処理系でいちばんよく使うのは (1) の const int *、すなわち「指す先は読むだけ」のパターンです。

9.3 壊さないという宣言としての関数引数のconst

const がもっとも役立つのは、関数の引数です。前の章で何度か const Node * や const char * を引数に使ってきました。これは関数の利用者への約束です。すなわち「この関数は、渡されたデータを読むだけで、書き換えません」という宣言です。

// この関数はトークンを表示するだけで、中身を変えない
void print_token(const Token *t) {
    printf("種類=%d 行=%d\n", t->kind, t->line);
    // t->kind = 0;  ← もし書こうとすればコンパイルエラーになる
}

const Token *t と書いておくと、うっかり関数の中で t->kind を書き換えるコードを書いても、コンパイラが止めてくれます。これには三つの利点があります。

第一に、バグを防ぐこと。「表示するだけのつもりが、誤って書き換えていた」という事故を、コンパイル時に発見できます。第二に、意図が伝わること。関数の宣言を見ただけで、「ああ、これは読むだけの関数だ」と利用者にわかります。ドキュメントを読まなくても、型が語ってくれるのです。第三に、後で述べる最適化の助けになることがあります。

言語処理系のように関数が何百個もあるプログラムでは、「この関数はデータを壊すのか、壊さないのか」が型から読み取れることの価値は計り知れません。const を付けられる引数には積極的に付けるのが、規模の大きなCプログラムでの良い習慣です^{[Brian, 1988]}。

9.4 constの伝播と、無理に外すごまかし

const には「伝わっていく」性質があります。const Node * を受け取った関数が、その left メンバ（これも Node *）を別の関数に渡すなら、その関数も const を尊重しなければ筋が通りません。だから const 対応の関数は、芋づる式に他の関数へ const を要求します。最初は面倒に感じますが、これは「読むだけの処理」と「書き換える処理」が型のうえできれいに分かれていく、健全な圧力です。

一方で、const を無理やり外すキャスト（3. 基本型で学んだ型変換）も書けてしまいます。

const int *p = &a;
int *q = (int *)p;   // const を外す。書けるが、原則やってはいけない
*q = 99;             // 未定義動作になりうる危険な操作

これは「約束を破る」行為です。元が本当に書き換え可能な変数を指していればたまたま動くこともありますが、本物の定数（書き換え不可能なメモリに置かれた値）を指していた場合、何が起きるか保証されません（未定義動作）。const を外すキャストは、よほどの理由がない限り避けてください。const は破るためでなく、守るためにあります。

9.5 constとリテラル文字列

const が関わる身近な落とし穴に、文字列リテラルがあります。"hello" のようにソースに直接書いた文字列は、書き換えできない領域に置かれることがあります。

char *s = "hello";
s[0] = 'H';   // 危険：未定義動作。クラッシュすることもある

const char *t = "hello";   // こう書けば、書き換えようとした時点でコンパイルエラー

文字列リテラルを指すポインタは const char * で受けるのが安全です。こうしておけば、誤って書き換えようとしたときにコンパイラが教えてくれます。4. ポインタとメモリの skip_spaces で引数を const char * にしていたのも、まさにこの理由からです。「ソースコードの文字列は読むだけ」という意図を表していたのです。言語処理系では入力ソースを大量に読みますが、入力を書き換えることはまずないので、const char * が基本になります。

9.6 この章のまとめ

• const は「この値は書き換えない」という約束をコンパイラに守らせる安全装置。
• ポインタでは「指す先が const」か「ポインタ自身が const」かで意味が変わる。const のすぐ右が守られる。
• 読むだけの関数引数には const を付けると、バグを防ぎ、意図が伝わり、最適化の助けにもなる。
• const は伝播する。キャストで無理に外すのは未定義動作を招くので避ける。
• 文字列リテラルは const char * で受けるのが安全。入力ソースの扱いに直結する。

ここまでで、データを安全に表現する道具がそろいました。次章では、それらのデータを置く場所（実行中に確保するメモリの管理）を扱います。

10. 動的メモリ管理

言語処理系は、実行してみるまで「どれだけのデータを扱うか」がわかりません。ソースコードが10行か10万行か、構文木のノードが100個か100万個か、コンパイル時には決められません。こうした「実行時に必要量が決まるメモリ」を扱うのが動的メモリ管理（dynamic memory management）です。5. 複数の値をひとまとめにする構造体で malloc をちらりと使いましたが、この章でその正体と作法をきちんと学びます。

10.1 スタックとヒープ

Cのプログラムが使うメモリには、性質の違う二つの領域があります。スタック（stack）とヒープ（heap）です。

スタックは、関数の呼び出しに伴って自動で管理される領域です。関数の中で int x; や Token t; のように宣言した普通の変数（局所変数 / ローカル変数）は、ここに置かれます。関数が呼ばれると領域が確保され、関数を抜けると自動で解放されます。何も意識しなくてよいかわりに、寿命は関数の中だけ、大きさもコンパイル時に決まっている必要があります。（正確に言うと、C の規格が決めているのは「寿命」の規則だけで、スタックという置き場所は典型的な実装の姿です。最適化によって局所変数がレジスタに置かれたり、メモリ上に現れないこともあります。でも、考え方のモデルとしてはスタックで十分です。）

ヒープは、プログラマが明示的に「借りて」「返す」領域です。実行時に好きな大きさを確保でき、確保したメモリは自分で返すまで生き続けます。関数を抜けても消えません。構文木のように「関数を抜けたあとも使い続けたいデータ」「実行時までサイズが決まらないデータ」は、ヒープに置きます。

graph TD
    subgraph stack["スタック（自動管理）"]
    S["局所変数<br>関数を抜けると消える"]
    end
    subgraph heap["ヒープ（手動管理）"]
    H["malloc で確保<br>free するまで残る"]
    end

5. 複数の値をひとまとめにする構造体で構文木のノードを malloc で作ったのは、まさにこの理由です。ノードを作る関数 new_number を抜けたあともノードは生き続けてほしいので、スタックではなくヒープに置く必要があったのです。もし局所変数として Node n; を作って &n を返したら、関数を抜けた瞬間にその領域は無効になり、壊れたポインタ（ダングリングポインタ / dangling pointer）が残ってしまいます。

10.2 mallocとfreeによる借用と返却

ヒープを使う基本の道具が、<stdlib.h> の malloc と free です。

#include <stdlib.h>

int *p = malloc(sizeof(int) * 100);   // int 100 個分のメモリを借りる
if (p == NULL) {                       // 借りられたか必ず確認する
    /* メモリ不足。ここでエラー処理 */
}
p[0] = 42;                             // 配列のように使える
/* ... 使う ... */
free(p);                               // 使い終わったら返す
p = NULL;                              // 返したあとは NULL を入れておくと安全

malloc(バイト数) は、指定したバイト数のメモリを確保し、その先頭の番地を返します。必要なバイト数は sizeof(型) * 個数 で計算するのが定石です。確保に失敗すると（メモリが足りないなど）NULL が返るので、使う前に必ず確認します。

free(p) は、借りていたメモリを返します。返したあとの p は無効な番地を指したままなので、p = NULL; を入れておくと、間違って使ったときに早く気づけます。

10.3 三つの定番トラブル

動的メモリ管理には、よく知られた落とし穴があります。言語処理系のように malloc／free を多用するプログラムでは、これらが現実の悩みになります。

メモリリーク（memory leak）は、借りたメモリを返し忘れ、使われないメモリが溜まっていく問題です。1回や2回なら害はありませんが、インタプリタのように長時間動き続けるプログラムでは、少しずつメモリを食いつぶし、やがて動かなくなります。5. 複数の値をひとまとめにする構造体で「木を作りっぱなしにしている」と注意したのは、このリークのことでした。

ダングリングポインタ（dangling pointer）は、free 済みの、あるいはすでに無効になったメモリを指し続けるポインタです。これを使うと、別の用途に再利用されたメモリを読み書きしてしまい、原因の追いにくいバグになります。

二重解放（double free）は、同じメモリを2回 free してしまう間違いです。ヒープの管理情報が壊れ、プログラムが異常終了したり、深刻な脆弱性になったりします。

char *p = malloc(10);
free(p);
free(p);   // ← 二重解放。p を NULL にしておけば free(NULL) は安全なので防げる

free(NULL) は「何もしない」と決められているので、free のあとに p = NULL; を入れておけば、うっかり二度 free しても安全です。小さな習慣ですが、効果は大きいです。

10.4 構文木をきちんと解放する

5. 複数の値をひとまとめにする構造体で作りっぱなしにしていた構文木を、最後まで面倒を見て解放してみましょう。木は再帰的なデータなので、解放もまた再帰で書くのが自然です。子を先に解放してから、自分を解放するのがポイントです。

void free_node(Node *n) {
    if (n == NULL) {
        return;
    }
    if (n->kind == ND_BINARY) {     // 演算ノードなら、まず子を解放
        free_node(n->u.binary.left);
        free_node(n->u.binary.right);
    }
    free(n);                        // 最後に自分を解放
}

順序が大切です。先に free(n) してしまうと、n->u.binary.left を読むときには n がもう無効で、ダングリングポインタの間接参照になってしまいます。だから「子を片付けてから自分を片付ける」。木全体は、根に対して free_node(tree) を一度呼べば、再帰的にすべてのノードが解放されます。malloc で組み立てた木を、free で対称的にたたむわけです。

10.5 なぜ言語処理系はメモリ管理が難しいのか

ここまでは「借りたら返す」という素朴なやり方でした。しかし、本格的な言語処理系では、これだけでは済まなくなります。理由は、値の寿命が複雑に絡み合うからです。

たとえば、ある変数に入れた配列を、別の変数にも代入し、関数にも渡したとします。この配列は、いくつの場所から参照されているのでしょうか。どこからも参照されなくなった瞬間はいつでしょうか。手作業で free のタイミングを正しく決めるのは、現実のプログラムでは非常に難しいのです。

そこで、多くの言語はガベージコレクション（garbage collection, GC）（「もう誰からも参照されていないメモリを自動で見つけて回収する仕組み」）を備えています。GC は言語処理系自身が提供する機能で、ユーザーは free を書かなくてよくなります。RubyもPythonもJavaScriptも、内部にGCを持っています。GC の作り方そのものは本書の範囲を超えますが、「なぜ多くの言語が malloc／free をユーザーから隠し、GCを採用したのか」は、ここまで学んだ手動メモリ管理の難しさから実感できるはずです。GCの設計に踏み込みたい場合は、コンパイラの教科書^{[Andrew, 1998]}やCrafting Interpreters^{[Robert, 2021]}の後半が良い入り口になります。

10.6 アリーナ

手動管理とGCの中間にある、実装が簡単で言語処理系と相性の良い手法を一つ紹介します。アリーナ（arena、領域確保）です。

アイデアは単純です。ノードを1個ずつ malloc するのではなく、大きなメモリを一度にどんと借りておき、そこから少しずつ切り出して使う。そして、もう全部いらなくなったら、大きなメモリごと一度に返す。個々のノードを free する必要がなくなります。

typedef struct {
    char  *buffer;   // 大きく確保した領域
    size_t capacity; // その大きさ
    size_t used;     // どこまで使ったか
} Arena;

void *arena_alloc(Arena *a, size_t size) {
    void *p = a->buffer + a->used;   // 次の空き位置
    a->used += size;                 // 使った分だけ進める
    return p;                        // （実際には容量チェックや整列が要る）
}

構文木のように「作っている間はぜんぶ必要だが、処理が終わればまとめて捨てる」データは、アリーナと非常に相性が良いのです。1個ずつ free する手間も、解放順序を間違える危険もなくなり、しかも malloc を何度も呼ぶより速くなります。多くの実用的なコンパイラが、構文木やその場限りのデータにアリーナを使っています^{[Steven, 1997]}。「いつ解放するか」を個々のノードではなく「フェーズ全体」の単位で考える、という発想の転換が鍵です。

10.7 この章のまとめ

• メモリにはスタック（自動管理・関数の寿命）とヒープ（手動管理・自分で返すまで残る）がある。
• 関数より長生きさせたいデータはヒープへ。局所変数の番地を外へ返してはいけない。
• malloc で借り、free で返す。1対1で対応させ、free 後は NULL を入れる。
• メモリリーク・ダングリングポインタ・二重解放に注意。サニタイザで検出する。
• 構文木は再帰で「子→自分」の順に解放する。
• 寿命管理が難しくなるとGCが要る。簡単な処理系ではアリーナや「あえて解放しない」も有効。

ここまでで、データを表現し、置き、片付ける道具がそろいました。次の部では、こうして組んだ処理系を速くする話に進みます。

第III部　速くする

言語処理系は「正しく動く」だけでは不十分なことがあります。インタプリタが遅ければ、その上で動くプログラムも遅くなります。この部では、プログラムを速くするための考え方を二段階に分けて学びます。

まず最適化の基礎として、計測の大切さ、コンパイラがやってくれる最適化、そしてプログラマが気をつけるべき点を扱います。続いて発展編として、言語処理系に特有の速くする技法（ディスパッチの工夫や静的解析）に踏み込みます。「推測するな、計測せよ」を合言葉に進みましょう。

11. 最適化の基礎

ここまでで、小さな言語処理系を組み立てる道具がそろいました。動くものができたら、次に気になるのが「速さ」です。インタプリタが遅ければ、その上で動くすべてのプログラムが遅くなります。しかし最適化は、やみくもに手を出すと、コードを複雑にするばかりで速くもなりません。罠が多い分野です。この章では、最適化に向き合う前の心構えと、土台となる基礎を学びます。

11.1 早すぎる最適化は諸悪の根源

最適化の話は、ある有名な戒めから始めるのが筋です。ドナルド・クヌースは1974年の論文で、こう書きました。「早すぎる最適化は諸悪の根源である（premature optimization is the root of all evil）」^{[Donald, 1974]}。

これは「最適化するな」という意味ではありません。クヌースが言いたかったのは、プログラムのどこが本当に遅いのかを確かめないまま、勘で細かい高速化に走るな、ということです。経験則として、プログラムの実行時間の大半は、コード全体のごく一部に集中します。残りの大部分をいくら磨いても、全体の速度はほとんど変わりません。それどころか、読みにくく直しにくいコードが残るだけです。

だから最適化の第一歩は、コードを書き換えることではありません。どこが遅いのかを知ることです。

11.2 プロファイラとタイマー

「どこが遅いか」を客観的に知る道具がプロファイラ（profiler）です。プロファイラは、プログラムを実行しながら「どの関数に、どれだけの時間が使われたか」を記録してくれます。Linuxなら perf、GCC/Clang と組み合わせる gprof などがあります。

# gprof を使う例：プロファイル情報付きでコンパイルして実行
cc -pg -O2 interp.c -o interp
./interp program.txt      # 実行すると gmon.out が作られる
gprof interp gmon.out     # 結果を表示。どの関数が重いかがわかる

perf はコンパイルオプションを追加しなくてもサンプリングできる、Linuxカーネル付属のプロファイラです。

# perf を使う例（Linux のみ）：コンパイル時の変更が不要で手軽に計測できる
cc -O2 -g interp.c -o interp     # -g でシンボル名を付けると結果が読みやすい
perf record ./interp program.txt # 実行しながらプロファイルデータを記録する（perf.data が作られる）
perf report                      # 結果を表示。どの関数が重いかがわかる

プロファイラを使うと、たいてい予想が裏切られます。「ここが重いはずだ」と思っていた関数が実は誤差で、まったくノーマークだった関数が時間の大半を食っていた、というのはよくある話です。だからこそ「推測するな、計測せよ」なのです。

もっと手軽に、特定の処理にかかった時間を測るだけなら、<time.h> のタイマーで十分なこともあります。

#include <time.h>
#include <stdio.h>

clock_t start = clock();          // 開始時刻
run_interpreter(program);         // 測りたい処理
clock_t end = clock();            // 終了時刻

double sec = (double)(end - start) / CLOCKS_PER_SEC;
printf("実行時間: %.3f 秒\n", sec);

clock() はプログラムが使ったCPU時間を返します。前後の差を CLOCKS_PER_SEC で割れば秒に直せます。改善の前後でこの数字を比べれば、「手を入れて本当に速くなったか」を確かめられます。最適化したつもりで遅くなっていた、という事態を防ぐためにも、計測は欠かせません。なお、計測値は実行のたびに揺れます（他のプログラムや CPU の状態の影響を受けるため）。一回の計測で判断せず、何回か実行して傾向を見ること、そして比べたい差が揺れより大きいことを確かめるのが、計測の基本作法です。

11.3 コンパイラの最適化フラグ

自分でコードを書き換える前に、まず使うべき強力な味方がいます。コンパイラ自身の最適化機能です。GCCやClangは、-O（オーは「Optimize」の頭文字）というフラグを付けると、生成する機械語を自動で速くしてくれます。

-O2 を付けるだけで、同じソースコードが何倍も速くなることがあります。コンパイラは、人間がやると間違えやすい細かな高速化を、正しさを保ったまま大量に適用してくれるからです。自分でコードをいじって高速化する前に、まず -O2 を付けて計測する。これが最適化の正しい出発点です。

cc -O2 interp.c -o interp     # まずはこれで計測する

コンパイラが具体的に何をしているのかは、次章12. コンパイラの中身と処理系を速くする技法で代表的な変換を紹介します。原理を体系的に学びたいなら、コンパイラ最適化の専門書^{[Steven, 1997]}が定番です。

11.4 アルゴリズムとデータ構造がいちばん効く

細かなコードの書き換えより、はるかに大きな差を生むのが、アルゴリズムとデータ構造の選択です。

例で考えましょう。言語処理系では「変数名から、その変数の情報を引く」操作（シンボルテーブルの検索）が頻繁に起こります。これを、変数を配列に並べて毎回先頭から探す方式（線形探索）で実装したとします。変数が n 個あれば、1回の検索に平均 n/2 回の比較が要ります。変数が増えるほど、検索は比例して遅くなります。

これをハッシュテーブル（hash table）（名前から「だいたいの置き場所」を一発で計算できるデータ構造）に変えると、変数が何個あっても1回の検索がほぼ一定時間で済みます。変数が1万個あるプログラムでは、この違いは劇的です。どんなに -O3 を付けて線形探索を磨いても、ハッシュテーブルに変えたときの差には遠く及びません。

xychart
    title "検索回数とデータ量の関係（イメージ）"
    x-axis ["10", "100", "1000", "10000"]
    y-axis "1回あたりの比較回数" 0 --> 5000
    line [5, 50, 500, 5000]
    line [1, 1, 1, 1]

上の線が線形探索（データ量に比例して増える）、下のほぼ平らな線がハッシュテーブル（データ量によらずほぼ一定）のイメージです。最適化で最初に見直すべきは、細かいコードではなく、使っているアルゴリズムとデータ構造なのです。この「処理量がデータ量とともにどう増えるか」という見方は計算量（computational complexity）と呼ばれ、最適化を考えるうえでの共通言語になります。

11.5 くり返しの内側を軽くする

2. C言語の基礎で「インタプリタの本体は巨大なくり返しだ」と述べました。最適化の効果は、何度も実行される場所ほど大きいという原則があります。1回しか走らない初期化処理を10倍速くしても全体は変わりませんが、100万回回るループの内側を2倍速くすれば、全体が見違えます。

たとえば6. 同じ場所を使い分ける共用体で見た eval のような評価ループは、プログラムの実行中ずっと回り続けます。ここで毎回、無駄な計算をしていないか（たとえば、ループの中で変わらない値を毎回計算し直していないか）を見直す価値は高いのです。次の二つを比べてみましょう。

// 改善前：ループの中で毎回 strlen(name) を計算している
for (int i = 0; i < count; i++) {
    if (strncmp(table[i], name, strlen(name)) == 0) { /* ... */ }
}

// 改善後：変わらない長さを外に出す（ループ不変式の移動）
size_t len = strlen(name);
for (int i = 0; i < count; i++) {
    if (strncmp(table[i], name, len) == 0) { /* ... */ }
}

name の長さはループ中で変わらないのに、改善前は毎回 strlen で測り直しています。これをループの外に出すだけで、回る回数だけ無駄が減ります。このように「ループの中で値が変わらない計算を外に出す」変換をループ不変式の移動（loop-invariant code motion）と呼びます。実は、これは -O2 のコンパイラがしばしば自動でやってくれる変換でもあります。だからこそ「まずコンパイラに任せる」が効くのです。次章で、こうしたコンパイラの自動変換を体系的に見ていきます。

11.6 この章のまとめ

• 「早すぎる最適化は諸悪の根源」。勘ではなく計測に基づいて最適化する。
• プロファイラやタイマーで「どこが本当に遅いか」を確かめてから手を入れる。
• 自分でいじる前に、まずコンパイラの -O2 を試して計測する。
• 細かいコードより、アルゴリズムとデータ構造の選択（計算量）がはるかに効く。
• 効果は「何度も実行される場所」ほど大きい。インタプリタの内側ループに注目する。

次章では、コンパイラが内部で行っている代表的な最適化と、言語処理系を速くするための一歩進んだ技法に踏み込みます。

12. コンパイラの中身と処理系を速くする技法

前章では「まず計測、それからコンパイラに任せる」という心構えを学びました。この章では一歩進んで、コンパイラが内部で何をやっているのかを代表的な変換を通してのぞき、さらに言語処理系そのものを速くするための技法に踏み込みます。前章の基礎を踏まえたうえで読んでください。

12.1 コンパイラが行う代表的な最適化

-O2 を付けたとき、コンパイラはソースコードの「意味」を変えずに、機械語を速くする変換を多数適用します。代表的なものをいくつか、具体例で見ていきます。これらを知っておくと、「自分で書くべきこと」と「コンパイラに任せてよいこと」の線引きができるようになります。

定数畳み込み（constant folding）は、コンパイル時に計算できる式を、あらかじめ計算してしまう変換です。

int x = 60 * 60 * 24;   // 書いた人は意味（1日の秒数）を明示したい
// コンパイラは 86400 を直接埋め込む。実行時の掛け算は消える

60 * 60 * 24 は実行するまでもなく 86400 だとわかります。コンパイラはこれを計算済みの値に置き換えるので、わざわざ自分で 86400 と書いて意味をわかりにくくする必要はありません。意味の伝わる書き方をして、計算はコンパイラに任せる。これが定数畳み込みの教訓です。

共通部分式の除去（common subexpression elimination）は、同じ計算が何度も現れるとき、一度だけ計算して使い回す変換です。

// 書いたコード
int a = (x + y) * 2;
int b = (x + y) * 3;
// コンパイラは (x + y) を一度だけ計算し、両方で使い回す

関数のインライン展開（inlining）は、小さな関数の呼び出しを、その中身で置き換える変換です。関数呼び出しには、引数を渡したり戻り先を覚えたりする手間（オーバーヘッド）がかかります。中身が数行の関数なら、呼び出すより本体を直接埋め込んだほうが速いことがあります。eval から呼ばれる小さなヘルパ関数などは、コンパイラがインライン展開してくれることが多いのです。

ここに挙げたのは一部にすぎず、前章で触れたループ不変式の移動や、ループの展開、レジスタ割り当てなど、コンパイラは何十種類もの最適化を組み合わせます。その全体像はコンパイラの専門書^{[Steven, 1997]}やドラゴンブック^{[Alfred, 2006]}で体系的に学べます。これらの大半は人間が手で書く必要がありません。コンパイラに任せ、人間は読みやすさとアルゴリズムに集中する。これが賢い分業です。

12.2 インタプリタのディスパッチを速くする

ここからは、言語処理系に特有の最適化です。前章で「インタプリタの内側ループが速度を決める」と述べました。その内側ループの中心にあるのが、ディスパッチ（dispatch）、すなわち「次に実行すべき命令を選んで、その処理に飛ぶ」操作です。バイトコードインタプリタ（構文木ではなく、命令の列を順に実行する方式）を例に考えます。

もっとも素直な書き方は、大きな switch 文でループを回すものです。

// 命令の列 code を先頭から実行する（簡略版）
for (;;) {
    uint8_t op = *ip++;        // 次の命令を取り出し、ポインタを進める
    switch (op) {
        case OP_ADD:  /* 加算の処理 */  break;
        case OP_SUB:  /* 減算の処理 */  break;
        case OP_PUSH: /* 値を積む処理 */ break;
        /* ... 命令の数だけ case が並ぶ ... */
    }
}

これは正しく動きますし、出発点として申し分ありません。しかし命令を1個実行するたびに、ループの先頭へ戻り、switch の分岐判定をやり直します。この「ループ末尾から先頭への戻り」と「switch の分岐」が、CPUにとっては予測しづらく、性能の足かせになることが知られています。CPUは次に進む先を先読み（分岐予測 / branch prediction）して高速に動きますが、switch ディスパッチはこの先読みを外しやすいのです。

これを改善する古典的な技法が、7. 処理を値として持ち運ぶ関数ポインタで触れたスレッデッドコード（threaded code）です^{[James, 1973]}。アイデアは、「各命令の処理の末尾で、switch に戻らず、次の命令の処理へ直接ジャンプする」というものです。

// computed goto を使ったスレッデッドコード（GCC/Clang の拡張機能）
static void *table[] = { &&do_add, &&do_sub, &&do_push, /* ... */ };
#define DISPATCH() goto *table[*ip++]   // 次の命令へ直接飛ぶ

DISPATCH();                 // 最初の命令へ
do_add:  /* 加算の処理 */  DISPATCH();   // 処理の最後で、次の命令へ直接ジャンプ
do_sub:  /* 減算の処理 */  DISPATCH();
do_push: /* 値を積む処理 */ DISPATCH();

各命令の処理の末尾にディスパッチを置くことで、命令ごとに別々のジャンプ地点ができ、CPUの分岐予測が当たりやすくなります。Ertlらの研究^{[M., 2003]}は、こうした技法がインタプリタの性能をどれだけ左右するかを詳しく分析しており、ディスパッチの設計がインタプリタ速度の中心的な要因であることを示しています。goto * という見慣れない記法はGCC/Clangの拡張機能で標準Cではありませんが、高速なインタプリタの実装では広く使われています^{[Robert, 2021]}。

12.3 静的解析で実行前に手を打つ

もう一つの発展的な方向が、静的解析（static analysis）、すなわちプログラムを実行する前に、その性質を調べて最適化に活かす技法です。前章で見たコンパイラの最適化も、その多くは静的解析に支えられています。

たとえば「この変数の値は、ここから先で二度と使われない」とわかれば、その変数を保持するためのメモリやレジスタを別の用途に回せます（生存解析 / liveness analysis）。あるいは「この計算結果は、どこに行っても必ず正の数だ」とわかれば、負数のチェックを省けます。こうした「実行しなくてもわかる事実」を集めて、無駄を削るわけです。

静的解析の理論的な土台として有名なのが、抽象解釈（abstract interpretation）です。これは、プログラムを「実際の値」ではなく「値の性質（符号、範囲、型など）」のレベルで「実行」してみることで、起こりうる挙動を安全に見積もる枠組みです。1977年にクザンらが定式化しました^{[Patrick, 1977]}。たとえば「変数 x は常に 0 以上 100 以下だ」とわかれば、配列の範囲チェックを省ける、といった最適化につながります。

graph LR
    A[ソースプログラム] --> B[静的解析<br>実行せずに性質を調べる]
    B --> C{わかった事実}
    C --> D["この変数はもう使われない<br>→ 領域を再利用"]
    C --> E["この値は常に正<br>→ チェックを省略"]
    C --> F["この計算は定数<br>→ 事前に計算"]

言語処理系を作る側にとって、静的解析は「自分の処理系を賢くする」ための道具です。最初は何もせず素直に実行する処理系で十分ですが、性能を追い求める段階になると、こうした解析が効いてきます。理論はやや高度ですが、ドラゴンブック^{[Alfred, 2006]}やコンパイラ実装の教科書^{[Andrew, 1998]}が橋渡しをしてくれます。

12.4 最適化をどこで止めるか

最適化には終わりがありません。やろうと思えばいくらでも手を入れられます。だからこそ、どこで止めるかを決めることが大切です。

判断の基準は二つあります。ひとつは目標です。「このプログラムが1秒以内に終わればよい」という目標があるなら、それを達成した時点で最適化は終わりです。目標がないまま「もっと速く」を追うと、労力に見合わない細かな改善に延々と時間を溶かすことになります。

もうひとつは費用対効果です。最適化はたいていコードを複雑にし、読みにくく、直しにくくします。得られる速度向上が、その複雑さに見合うかを天秤にかけます。前章で見たように、効果は「何度も実行される場所」に集中するので、ホットスポット（実行時間の大半を占めるごく一部）だけを最適化し、残りは読みやすさを優先するのが王道です。これはクヌースの論文^{[Donald, 1974]}が半世紀前に説いたことそのものであり、いまも変わらない最適化の知恵です。

12.5 この章のまとめ

• コンパイラは定数畳み込み、共通部分式の除去、インライン展開など多くの最適化を自動で行う。人間はその大半を手書きしなくてよい。
• インタプリタの速度はディスパッチが左右する。switch 方式をスレッデッドコードに変える古典的技法がある。
• 静的解析（抽象解釈など）は、実行前にプログラムの性質を調べ、最適化やバグ検出に活かす。
• 最適化には目標と費用対効果という止めどきがある。ホットスポットに集中し、計測と正しさの確認を必ずセットにする。

これで本書の本編は終わりです。型からポインタ、構造体や共用体や関数ポインタ、メモリ管理、そして最適化まで、簡単な言語処理系を作るのに必要なC言語の道具がそろいました。巻末の用語集（A. 用語集）と文献案内（B. さらに学ぶために）も活用し、ぜひ自分の手で処理系を育ててみてください。

A. 用語集

本書に登場した主な用語を、五十音順ではなく「学ぶ順序」に近い形でまとめます。 知らない言葉に出会ったら、ここに戻ってきてください。 各語の詳しい説明は、本文の対応する章にあります。

A.1 C言語の基礎にまつわる用語

コンパイラ（compiler）

人間が読めるソースコードを、CPUが実行できる機械語などへ翻訳する道具。GCCやClangが代表例。詳しくは2. C言語の基礎。

機械語（machine code）

CPUが直接理解できる、0と1で表された命令の列。ソースコードはコンパイルされてこの形になる。

プリプロセス（preprocess）

コンパイルの前段階で、#include や #define といった # で始まる命令を処理すること。

マクロ（macro）

#define で定義する、コンパイル前のテキスト置き換えの仕組み。

規格（standard）

「正しいCプログラムとは何か」を定めた取り決め。C99・C11・C17などの版がある^{[ISO/IEC, 2018]}。

式（expression）

計算して値を生み出すコードの断片。1 + 2 など。

制御構造（control flow）

if・for・while など、処理の流れを分岐させたりくり返したりする仕組み。

関数（function）

ひとまとまりの処理に名前を付け、引数を受け取って値を返す部品。詳しくは2. C言語の基礎。

A.2 型にまつわる用語

型（type）

ビット列をどう解釈し、どれだけの幅を占め、何ができるかを決める情報。詳しくは3. 基本型。

固定幅整数型（fixed-width integer type）

int32_t や uint8_t のように、どの環境でも幅が一定の整数型。<stdint.h> で使える。

符号付き／符号なし（signed / unsigned）

負の数を表せるのが符号付き、0以上だけを表すかわりに正の範囲が広いのが符号なし。

移植性（portability）

別の環境（CPUやOS）に移しても正しく動く性質。int の幅が環境依存なことなどが関わる。

キャスト（cast）

(double)x のように、値の型を明示的に変換する操作。

typedef

既存の型に別名を付ける機能。意図を伝え、後からの型差し替えを容易にする。詳しくは3. 基本型。

列挙型（enum / enumeration）

名前付きの整数定数をまとめて定義する仕組み。タグ付き共用体のタグによく使う。

A.3 ポインタとメモリにまつわる用語

メモリ（memory）／番地（address）

データを置く、番地（通し番号）の付いた領域。詳しくは4. ポインタとメモリ。

ポインタ（pointer）

値そのものではなく、値のある「番地」を持つ変数。

間接参照（dereference）

*p のように、ポインタが指す先の値を読み書きすること。

ヌルポインタ（null pointer）

どこも指していないことを表すポインタ。NULL と書く。たどると異常終了する。

配列（array）／添字（index）

同じ型の値をメモリ上に連続して並べたものと、その何番目かを指す番号（0から数える）。

ポインタ演算（pointer arithmetic）

p + 1 のように、番地を型の幅ぶんずらす計算。配列アクセスの正体。

バッファオーバーフロー（buffer overflow）

配列の範囲外を読み書きしてしまう不具合。深刻なバグや脆弱性の原因。

スタック（stack）／ヒープ（heap）

関数の寿命で自動管理される領域がスタック、自分で借りて返す領域がヒープ。詳しくは10. 動的メモリ管理。

malloc / free

ヒープからメモリを借りる関数と、返す関数。1対1で対応させる。

メモリリーク（memory leak）

借りたメモリを返し忘れ、使われないメモリが溜まっていく不具合。

ダングリングポインタ（dangling pointer）

すでに無効になった（解放済みなどの）メモリを指し続けるポインタ。

二重解放（double free）

同じメモリを2回 free してしまう間違い。ヒープを壊す。

ガベージコレクション（garbage collection, GC）

もう誰からも参照されないメモリを自動で回収する仕組み。多くの言語が内蔵する。

アリーナ（arena）

大きなメモリを一度に確保してそこから切り出し、最後にまとめて返す手法。構文木と相性が良い。

A.4 データ構造とふるまいにまつわる用語

構造体（struct）／メンバ（member）

関連する複数の値を一つにまとめた型と、その中の各値。詳しくは5. 複数の値をひとまとめにする構造体。

共用体（union）

すべてのメンバが同じメモリを共有する型。サイズは最大メンバに合わせる。詳しくは6. 同じ場所を使い分ける共用体。

タグ付き共用体（tagged union）

「いまどの種類か」を表すタグと共用体を組にしたもの。値や構文木の表現の定番。

関数ポインタ（function pointer）

関数の番地を持つポインタ。関数を値として持ち運べる。詳しくは7. 処理を値として持ち運ぶ関数ポインタ。

ディスパッチテーブル（dispatch table）

「種類→処理」を表（配列）で対応づけ、種類で引いて関数を呼ぶ手法。

コールバック（callback）

処理の一部を関数ポインタで外から渡す手法。qsort の比較関数などが例。

const

「この値は書き換えない」という約束をコンパイラに守らせるキーワード。詳しくは9. constという書き換えないための約束。

未定義動作（undefined behavior）

規格が結果を保証しない操作。const を破る、範囲外アクセスなどが該当し、何が起きてもおかしくない。

A.5 言語処理系と最適化にまつわる用語

言語処理系（language processor）

ソースコードを実行・変換するソフトウェアの総称。インタプリタとコンパイラがある。詳しくは1. なぜ言語処理系にC言語なのか。

字句解析（lexical analysis）／構文解析（parsing）

文字列を意味のある単位（トークン）に区切る処理と、その並びから文法構造を組み立てる処理。

抽象構文木（abstract syntax tree, AST）

構文解析の結果を木構造で表したもの。本書では構造体とポインタで表現した。

木構造インタプリタ（tree-walking interpreter）

構文木を根からたどって意味を計算する方式のインタプリタ。詳しくは5. 複数の値をひとまとめにする構造体。

プロファイラ（profiler）

プログラムのどこに時間が使われたかを計測する道具。最適化の出発点。詳しくは11. 最適化の基礎。

計算量（computational complexity）

処理量がデータ量とともにどう増えるかを表す尺度。アルゴリズム選択の指標。

ディスパッチ（dispatch）

次に実行する命令を選んでその処理へ飛ぶ操作。インタプリタ速度の中心。詳しくは12. コンパイラの中身と処理系を速くする技法。

スレッデッドコード（threaded code）

各命令の処理の末尾から次の命令へ直接ジャンプし、ディスパッチを速くする技法^{[James, 1973]}。

静的解析（static analysis）／抽象解釈（abstract interpretation）

実行前にプログラムの性質を調べる技法と、その理論的土台の一つ^{[Patrick, 1977]}。

B. さらに学ぶために

本書は「簡単な言語処理系を作るのに必要なC言語の知識」を速習することに絞りました。ここから先へ進むための道案内として、信頼できる文献を分野別に紹介します。どれも本書の各章で引用したもので、次の一歩にふさわしい定番です。

B.1 C言語そのものを深める

C言語をきちんと学び直したいなら、まず原典です。カーニハンとリッチーの『The C Programming Language』第2版^{[Brian, 1988]}は、C言語の設計者自身による古典で、簡潔ながら本質を突いています。本書で駆け足に扱った文法や標準ライブラリを、腰を据えて学べます。

より現代的で実務的な入門としては、シーコードの『Effective C』^{[Robert, 2020]}が優れています。未定義動作の避け方、安全なメモリ管理、文字列の扱いなど、本書で「注意」として触れた落とし穴を、最新の規格に沿って丁寧に解説しています。本書を読んで「Cの危うさ」が気になった人に特におすすめです。

言語仕様の厳密な根拠が必要になったら、C言語の国際標準規格そのもの^{[ISO/IEC, 2018]}にあたります。読み物ではありませんが、「この動作は本当に保証されているのか」を確かめる最終的なよりどころです。

B.2 言語処理系の作り方を学ぶ

本書の題材だった言語処理系づくりを本格的に学ぶなら、ニストロムの『Crafting Interpreters』^{[Robert, 2021]}が最良の出発点です。木構造インタプリタとバイトコードインタプリタの両方を、実際に動くコードを書きながら一冊で作り上げます。後半はまさにCで書かれており、本書で学んだ構造体、共用体、関数ポインタ、メモリ管理、スレッデッドコードが、生きた文脈で次々に登場します。Web版が無料で公開されているのも魅力です。

理論的な土台までしっかり押さえたいなら、定番の教科書へ進みます。アホらの『Compilers: Principles, Techniques, and Tools』^{[Alfred, 2006]}（通称「ドラゴンブック」）は、字句解析、構文解析、意味解析、最適化を体系的に網羅した、この分野の金字塔です。アペルの『Modern Compiler Implementation in C』^{[Andrew, 1998]}は、その名のとおりC言語での実装に重きを置いており、本書からの橋渡しとして読みやすいでしょう。

B.3 最適化を深める

最適化の理論と実装を専門的に学ぶなら、マクニックの『Advanced Compiler Design and Implementation』^{[Steven, 1997]}が定番です。本書の発展編で名前だけ挙げた数々の最適化（共通部分式の除去、生存解析、レジスタ割り当てなど）が、アルゴリズムのレベルで詳しく解説されています。

最適化に取り組む際の心構えとしては、クヌースの古典的論文「Structured Programming with go to Statements」^{[Donald, 1974]}を一度読む価値があります。「早すぎる最適化は諸悪の根源」という有名な一節の、本来の文脈を知ることができます。半世紀前の論文ですが、その知恵はいまも色あせていません。

インタプリタの高速化という、本書がもっとも力を入れた話題をさらに追うなら、二つの文献が役立ちます。ベルの「Threaded code」^{[James, 1973]}は、スレッデッドコードの原典です。そしてエルトルとグレッグの「The structure and performance of efficient interpreters」^{[M., 2003]}は、ディスパッチの設計がインタプリタ性能をどれだけ左右するかを、現代的な計測で明らかにした重要な論文です。本書の発展編で述べたことの実証的な裏づけが得られます。

B.4 静的解析の理論へ

最適化やバグ検出の土台にある静的解析を理論から学びたいなら、クザンらの「Abstract interpretation」^{[Patrick, 1977]}が出発点です。抽象解釈という枠組みを最初に定式化した論文で、やや高度ですが、現代の多くの解析ツールの根っこにある考え方を知ることができます。いきなり原典が難しければ、まずドラゴンブック^{[Alfred, 2006]}のデータフロー解析の章で素地を作ってから挑むとよいでしょう。

B.5 学びを進めるための姿勢

最後に、本書が一貫して勧めてきた姿勢をもう一度。手を動かすこと、そして警告とエラーから学ぶことです。文献を読むのと並行して、小さな電卓言語のインタプリタを実際に書き、壊し、直してみてください。本書で学んだ道具が、紙の上の知識から「自分の手になじんだ道具」へ変わるのは、その瞬間です。あなたの最初の言語処理系が、ここから始まります。