1+1を計算したいだけなのに、関数型プログラミング言語を一つ書くことになった
著者は算術式を二分木に変換するデータ構造の課題を出され、ついでに評価器を書き、数日後にはクロージャ、ガベージコレクション、カスタムメモリアロケータ、REPL、FFIを備えるまでになった。全文でCコードを示しながら段階的に解説する。
日本語
コピー
1+1 を計算したかっただけなのに、関数型プログラミング言語をひとつ書くことになった
渡されたデータ構造の課題は、算術式を二分木に変換するというものだった。 当然のように、ついでに評価器も書くことにした。 数日後には、C でクロージャ、ガベージコレクタ、独自のメモリアロケータ、REPL、FFI、その他もろもろを実装していた。 graphLang
あのデータ構造の課題
問題はこうだ： 二分木を使って 1 + 1 + 1 を 3 に評価せよ。 どうやってここまで来たか？ まず 1+1+1 の木を作る。
(+)
/ \
(+) (1)
/ \演算子が根ノードになり、2 つのオペランドがその子になる。 次にこの木を評価する。 まず根ノードの左オペランドを評価する。これもまた + 式なので、外側の + を実行する前に、まずこれを 1 つの値に畳まなければならない。
(+)
/ \そしてもう一度評価する。
(3) <--- that's our result今やったことは、これと等価だ。
(+ (+ 1 1) 1)
|
v
(+ 2 1)
|
vただし注意してほしい。評価器がこれをやるには、+ が何を意味するかを知っていなければならない。 表現方法のひとつは、各演算を式の型の分岐にすることだ：
Expr ::= Add Expr Expr
| Sub Expr Expr
| Mul Expr Expr
| Div Expr Exprだが、これらの分岐は結局何を表している？ 評価器は本当に Add と Sub を区別する必要があるのか？ そこで和型を実装し始めた。この構造を見てほしい：
Add: Expr x Expr → Expr
Sub: Expr x Expr → Expr
Mul: Expr x Expr → Exprどれも 2 つの式を受け取り、1 つの式を返す。 ならば評価器は、演算が Add だろうと Sub だろうと Mul だろうと Div だろうと、気にする理由があるのか？ どうやらない。 すると式はこう書ける：
Expr ::= Func Expr Expr評価器は関数が何をするかを知る必要はない。ただ関数をどう適用するかだけを知っていればいい。
変数を足せる。変更は小さい
ちょっと足すだけのはずだ、全く問題ない。変数といっても、ハッシュテーブルを 1 回引いて Expr を取り出すだけ。 おっと待て。C には組み込みのハッシュテーブルがない。 hmmm.（´-`）.｡oO( … )
ならハッシュテーブルを実装しよう。小さな変更だ！m9(・∀・) で……どう動く？実装したことはない。 原始人のように Google して、この神記事を見つけた。 How to implement a hash table (in C) そこで Expr を少し変えた：
Expr ::= Func Expr Expr
| Val 見ての通り！これで変数ができ、評価したら関数に渡せる。(+ 1 1) のように。
実際に C で実装する
よし、この方針で C のコードを書こう。十分簡単に見える。タグ付き共用体にすぎない。
typedef enum {
LITERAL,
VAR,
FUNC,
} NodeType;
struct Node {
struct Node *left;
struct Node *right;
union {
int literal;
char *var;
char *func;
} data;
NodeType type;
現時点でのそれぞれのサイズ（64 ビットシステムを仮定）は：
+------------------------+----------+
| Field | Size |
+------------------------+----------+
| Left Pointer | 8 bytes |
| Right Pointer | 8 bytes |
| Data | 8 bytes |
| Type | 4 bytes |
| Padding | 4 bytes |
+------------------------+----------+
| Total | 32 bytes |32 バイトは大したことないように見えるが、どう使われるかを考えなければならない。1+1 を計算するには 3 つのノードが要る。
- 演算子用に 1 つ
- オペランド用に 2 つ
つまり 32 x 3 = 96 バイト、1+1 を計算するだけで。 だが問題はここだ。私のシステムでは、ノードを malloc() するとメタデータが付いてきて、16 バイトのメモリを食う！ するとノードあたりの総コストは 32（ノードサイズ）+ 16（malloc ヘッダ）= 48 バイト！ だから (+) 1 つ分の 3 ノードには 144 バイト必要だ！ しかも、細かい断片的な小さなアロケーションを大量に行うことになる。 もっと良いノードの割り当て方法を探さなければ。 明らかに独自のアロケータが要る。 そこで何が使えるか調べ、これまた原始人のようにして、最終的に自分で Arena Allocator を書くことにした。
Arena Allocator
Arena allocator の考え方は単純だ。最初に大きなメモリの塊を取り、そこに自分で割り当てていき、最後に塊ごと一気に解放する。 だから私の arena allocator はこうなる：
#define SIZE 1024ノードを割り当てるときは、これを使って先頭位置を記録するだけだ。
int top = 0;ノードを 1 つ割り当てるには、これをそのまま返す。
&arena[top++];アロケータを書き上げ、ノードを割り当てる C 関数を定義した：
Node *allocNode();うまくいった！あとは実際にこれらの関数を呼ぶだけだ。 そこで気づいた。
変数と関数を同じ環境に置ける！つまり関数自体も値になれる（°◇°）
前に作ったハッシュテーブルを覚えているか？そろそろアップグレードする時だ。
Env テーブルを構築する
Env テーブルには 2 つ、変数と関数を入れる。 だが関数とは何か？ 評価器にとっては、片側で引数を食べ、もう片側で結果を吐き出す、ただのものだ。
(func node)
/ \最初の考えは、C 関数を直接指させることだった。十分簡単に見える。 だがここで大きな問題がある：ユーザーはどうやって自分の関数を書くのか？ もうひとつ問題がある。 ユーザーが我々の言語でコードを入力しても、それが魔法のようにネイティブの C 関数ポインタになるわけではない。構築できるのは AST（ノードの木）だけだ。 関数が単なる C ポインタなら、それらは即座に不透明な値になってしまう。 関数が別の関数を返したらどうする？その関数をグラフに戻し、後で評価できる必要がある。だが C の関数ポインタは評価器が走査できるものではない。 だから評価器に「おい、俺は関数だが、俺のコードは C ポインタではなくこの木だ」と伝えるノード型が要る。 関数本体を木として保持し、評価器がそれを多段階で評価できるようにする必要がある。我々の目的にとって、これがクロージャの表現だ。 クロージャはブラックボックスな C 関数ではなく、我々のグラフの中の実在するノードだ。片側に引数を、もう片側に操作の木（関数本体）を保持する。
(closure)
/ \
(parameter) (body)
/ \（厳密には、クロージャには環境もある。だがローカル変数の話はまだしていない。）
関数を本当のノードにすれば、それを渡し回し、他の関数から返し、好きな時に一歩ずつ評価できる！
今や、ユーザーは自分で関数を定義できる。C のコードには一切触れずに！！！
では、それを実際に C で実装しよう。何が必要か？ 変数も関数も値である以上、環境は名前をノードに対応付ける必要がある。 そこで env entry はこう書ける。
typedef struct EnvEntry {
char *key;
Node *val;
struct EnvEntry *next;
これでハッシュテーブルが名前（key）を Node *、つまり値にマッピングする。
だが val の正体は何か？
Val は Node だ！ ただし現状の Node はクロージャもネイティブ関数も知らない。
ならば、以前の node 定義にそれらを追加すればいい。
struct Node {
struct Node *left;
struct Node *right;
union {
int literal;
char *var;
int index;
char *call;
struct Node *closure;
struct Node *nativeFunc;
} data;
NodeType type;
nativeFuncs は C 関数を表すノード、closures はノードで構成されるユーザー定義関数だ。 ネイティブ関数 = 不透明な C 実装 クロージャ = 言語レベルのグラフ表現 部品は揃った：
- メモリアロケータ
- 変数、C 関数、ユーザー定義関数を保持する環境テーブル
- プログラムをたどって関数を適用する評価器
最初のプログラムを動かそう！！
まだ lexer/parser がないので、AST を手で組み立てる。 テスト用のプログラムといえば、フィボナッチ数列に勝るものはない！ そこでプログラムを書いた。入力は fib(5)。 そして…… クラッシュした
メモリアロケータを改良する
なぜか？ なぜなら fib(5) が 13k 個のノードを生成するからだ。こちらのアロケータは全部で 1024 個しか持たない！ 「話は単純だ。このメモリを realloc して容量を増やし、動的配列にすればいい」と思うかもしれない。 問題はまさにそこにある。すべてのノードがこのメモリブロックの内部で互いを指している。 より大きな容量で realloc すると、ブロックは新しいアドレスに移動しうる。 ポインタがすべて無効になり、即 segfault だ！ どう解決する？
アロケータを一つ大きくするのではなく、複数のブロックを連結する！
確保済みのブロックを連結リストにつなげばいい。あるブロックの領域を使い切ったら、新しいブロックを確保して指す。データを移動する必要はない。
これが chunk allocator だ。各ブロックが chunk で、メモリを保持し、next ポインタで連結リストのようにつなぐ。
typedef struct Chunk {
Node nodes[CHUNK_SIZE];
struct Chunk *next;
最初の chunk と、現在割り当て中の chunk を記録しておけばいい。
揃ったもの：
- Chunk Memory Allocator（新規）
- 変数、c 関数、ユーザー定義関数を同時に保持する Environment テーブル
- env を引いて式を簡約しながらプログラムを再帰的にたどる Evaluator
最初のプログラムをもう一度動かす
そして…… 成功した！ 結果は 5！ 3+2 は 5 だ。 だが何かがおかしい。メモリを 1.32 mb 使っている。 おかしい。fib(5) は複雑な操作でもない。 そこで fib(10) も動かしてみた。 40 mb を食った！！ これはさすがにおかしい。 だから測ることにした。ベンチマークを走らせた。
RAM (GB) vs fib(n)
12.29 GB ┤
11.34 GB ┤ ╭───
10.40 GB ┤ ╭──────╯
9.45 GB ┤ ╭─────╯
8.51 GB ┤ ╭───╯
7.56 GB ┤ ╭╯
6.62 GB ┤ ╭╯
5.67 GB ┤ ╭╯
4.73 GB ┤ ╭─╯
3.78 GB ┤ ╭╯
2.84 GB ┤ ╭╯
1.89 GB ┤ ╭╯
0.95 GB ┤ ╭╯
0.00 GB ┼─────╯
-----------------------------------Fib(40) は OOM で落ちるまでに、実際に 12+ GB を食った。 なぜか？ およそ 13 億個のノードを生成するからだ。 1 ノード 48 バイトで、計算すると約 62.4 GB 分のノードを割り当てている。 問題は…… ノードを割り当て続けているのに、使い終わったノードを一度も解放していないことだ。 これを解決するために、ガベージコレクタを書く羽目になった。
ガベージコレクタを作る
ガベージを回収するとは何か？ 簡単に言えば、プログラムからもう到達できなくなったノードを消すことだ。 1+1+1 を評価するとき、evaluator はこう動く。
- ast を構築する
(+)
/ \
(1) (+)
/ \- 左辺を評価する。左辺はすでにリテラルなので飛ばし、右辺へ移る。
- 右辺は関数なので、まずそれを評価する。そしてこの木を書き換える。
(+)
/ \だが、あの二つの 1 はどうなる？
allocator に残ったままだ！ プログラムが終わるまで解放されない！ ガベージコレクタに必要なのは、根から出発して、まだ到達できるノードをすべてマークすることだ。 ノードがリテラルに簡約されると、その元の子ノードにはこのノードを通じて到達できなくなる！ そこで、リテラルに簡約された時点で子ノードを両方とも null にすればいい。そうすればガベージコレクタがグラフのこの部分から古いノードへ辿り着くことは永遠にない。 これがマークフェーズだ。ガベージコレクタは根から出発し、到達できるノードをすべてマークする。 マークが終わったら、ガベージコレクタにすべての chunk を走査させ、マークされていないノードを調べ、freeList という連結リストに加える。 こうすれば新しいノードが必要なとき、新たに割り当てずにこれらのノードを再利用できる。 freeList が空のときにだけ、現在の chunk から新しいノードを割り当てる。 それ以外は先頭をポップして、そのメモリをそのまま再利用する。 これでノードを効率よく回収できる！！
gc を加えてもう一度ベンチマークを走らせる：
RAM w/ GC (MB) vs fib(n)
1.7200 MB ┼
1.5886 MB ┤ ╭───
1.4571 MB ┤ ╭────╯
1.3257 MB ┤ ╭─────╯
1.1942 MB ┤ ╭────╯
1.0628 MB ┤ ╭─╯
0.9314 MB ┤ ╭╯
0.7999 MB ┤ ╭─╯
0.6685 MB ┤ ╭╯
0.5371 MB ┤ ╭─╯
0.4056 MB ┤ ╭╯
0.2742 MB ┤ ╭╯
0.1427 MB ┤ ╭───╯
0.0113 MB ┼─╯
-----------------------------------これを見てほしい！ fib(40) でメモリ使用量が 12 GB から 1.7 MB に落ちた。 ありえない。 だが話はまだ終わらない。
fib 40 の評価に 6 分かかった
なぜか？ 今書いたマーク・アンド・スイープのガベージコレクタは stop-the-world だ。 そして走らせているアルゴリズム自体が指数関数的だ。 メモリの問題は解決した。 だが今度は性能の問題が生まれた。 どちらも解決できる。
- 並列ガベージコレクタを実装できる
- fib 自体の評価方法にも手を入れられる
続きで扱うこと
この記事はすでに長くなりすぎたので、いくつかのパートに分けることにした。
- TCO とより良い評価方法で速度問題を解決する方法
- lexer/parser の実装
- FFI の実装……
- REPL の実装
- ポインタのデリファレンスからの切り替え……
- お粗末なラッパーを C に持ち込んだ話
- lambda 関数の実装
- ローカル変数の追加
- Cheney コピー GC の土台づくり
現時点でできたこと
- 式の型は代数データ型にできると気づいた
- 本当のバリアントとはデータの種類、つまり関数・変数・リテラルだと気づいた
- 変数と関数は別物ではなく、どちらもただのデータだと気づいた
- グラフ評価器を実装し、評価後にそのノードをその場で書き換えるようにした
- 独自のハッシュテーブルで環境テーブルを実装した
- ノードを確保するための独自 chunk アロケータを実装した
- ゴミをずっと抱え込んでいたことに気づいて、マーク&スイープ GC を実装した
要するに、グラフ簡約エンジンを作った。
待って。じゃあ 1+1 は計算できるのか
できる……というか、今はできる。 graphLang の流儀では、1+1 は確かに 2 になる！(´･ω･`) とにかく、ここで触れていない話が山ほどあって、それは全部 repo にある。