二週間で簡単なインタープリタ言語を実装してみた (日記)

私は昔から言語処理系に興味があり、自分で言語を作ることを夢見てきました。 しかし、いざ言語を実装しようと思って言語処理系に関する本を読んでも何から手を付けていいか分からず、アセンブラもまともに読めないまま、数年が経ってしまいました。 大学時代は情報系ではなかったため、コンパイラの実験がある情報系の学科のカリキュラムを羨ましく思い、情報系の授業の教科書を手にとって見ても読む気が起きず、自分に作れるのは所詮、構文木をちょこっといじって変換するレベルのもの (例えばsjspなど) にとどまっていました。

そんな中、去年のRebuild.fmで、とても感銘を受けた回がありました。 LLVMのlinkerであるLLDを開発されているrui314さんの回です。 rebuild.fm セルフコンパイルできるC言語のコンパイラを実装するという話のなかで、インクリメンタルに開発する重要性について話をされています。

qiita.com

この回を聞いてやっと、コンパイラの書き方がわかった気がしました。 コンパイラに関する本を読んでも実装の進め方がわからなかったのは、コンパイルフェーズごとに章に分かれていたからで、正規言語の難しい話を読んでは本を投げ出していたのです。 Rebuild.fmのrui314さんのお話を聞いて、まず最初は小さい言語をとにかくパースからコード生成まで通して動くようにして、そこから徐々に文法を増やしていくというインクリメンタルなアプローチが有力なのだとやっとわかったのです。 ここで最初の言語は、関数もforループも演算子もない、とてもプリミティブな文法だけもつ言語から始めるのです。 コンパイラの教科書を読んでもさっぱりわからなかった実装の進め方が、ようやくわかった瞬間でした。

最近、まつもとゆきひろさんの『言語のしくみ』が出版されたこともあり、言語実装の熱が高まっているように感じます。 私は今年は言語実装の年にしようと思っていて、その第一歩としてインタープリタ言語を書いてみました。 まずやったことは、mrubyやLuaなどの実装を手元に引っ張ってきて、ctagsを打って数日読んでみました。

Luaのファイル構成は分かりやすいので読みやすいです。mrubyはmrbgems/mruby-compiler/coreやsrc/vm.cなどを中心に見ていきました。ざっくり雰囲気を掴むくらいの気持ちで読みました。 あとはひたすら実装を進めていきました。

つまり参考にしたものはmrubyとLuaです。 書籍としては以下の本を挙げておきます (もうちょっとやわらかいインタープリタ実装の本ある気がするけど知らないです)。

大学時代に買ったけど当時はあまり理解できず、最近開いてみてようやく理解し始めたコンパイラの本。 この本だけ読んでてもよく分からないけど、自分でVMを書いてみてから改めてこの本を読んでみたら、納得する部分がたくさんありました (特に関数のコード生成について)。 大学で使われている教科書で少し硬い。

情報系教科書シリーズ コンパイラ

Direct threadingなどmrubyで使われている技術がよく分かる本 (すみません、最初の方をちら見しただけでちゃんとは読んではないです…)。

まつもとゆきひろ 言語のしくみ

rui314先生をリスペクトしているので、私も日記形式でお送りしてみます。

1月3日

実家から戻り、インタープリタ言語を作る意識を高める。 ディレクトリを作り、yaccファイルを用意する。

1月7日

mrubyの構文木の実装を参考にして、ASTを全てnode*で実装することにする。

typedef struct node {
  struct node *car, *cdr;
} node;

とりあえずノードを追加するたびにmallocするような形で実装を進める。 文法は四則演算のみ。

1月8日

構文木のためのメモリープールを実装する。 ASTは全てnode*で表すことにしたので、この構造体のみ考えておけば良いのは楽。

四則演算のみの言語に対して、コード生成と実行器を実装する。 実装が簡単なスタックマシンで作る。

今ある文法は

• 式 (expression) が並んだものがprogram
• expressionは四則演算が使える
• リテラルは整数 (long) または浮動小数点数 (double)

enum OP_CODE {
  OP_ADD,
  OP_MINUS,
  OP_TIMES,
  OP_DIVIDE,
  OP_LOAD_LONG,
  OP_LOAD_DOUBLE,
  OP_PRINT_POP,
};

OP_PRINT_POPはちょっとダサい…

1月9日

コードが読みやすいようにいくつか変数名をリネーム。 変数を作り始めるが難しくて散歩に出かける。

夜、変数を実装。新たに追加した文法は

• 変数に代入できる
• 四則演算のなかで変数を使える
• printæ–‡

statement         : IDENTIFIER EQ expression
                    {
                      $$ = cons(nint(NODE_ASSIGN), cons($1, $3));
                    }
                  | PRINT expression
                    {
                      $$ = cons(nint(NODE_PRINT), $2);
                    }
                  ;

OP_PRINT_POPを削除してOP_ASSIGN, OP_PRINT, OP_LOAD_IDENTを追加。

 enum OP_CODE {
+  OP_ASSIGN,
+  OP_PRINT,
   OP_ADD,
   OP_MINUS,
   OP_TIMES,
   OP_DIVIDE,
   OP_LOAD_LONG,
   OP_LOAD_DOUBLE,
-  OP_PRINT_POP,
+  OP_LOAD_IDENT,
 };

OP_ASSIGNã‚„OP_LOAD_IDENTのoperandは、変数配列のindexが入っているので、実行器の雰囲気はこんな感じ。

+      case OP_ASSIGN:
+        e->variables[GET_ARG_A(e->codes[i])].value = e->stack[--e->stackidx];
+        break;
       case OP_ADD: BINARY_OP(+); break;
@@ -172,6 +214,9 @@ static void execute_codes(env* e) {
         break;
+      case OP_LOAD_IDENT:
+        e->stack[e->stackidx++] = e->variables[offset - GET_ARG_A(e->codes[i])].value;
+        break;

booleanリテラルを実装する。まだ演算はない。

1月11日

簡単なテストケースを書く。

foo = 3 * 4 / 5 + 6.7 * 7
bar = foo * 3.1 + foo / 7.2
print foo + bar

このスクリプトを実行すると207.281666667と表示される。 Python 2のコンソールで確かめながら実行結果を確かめる。

if文を実装する。Vim scriptに倣って、if … endifにする。 if文の実装に伴って、OP_JMP_NOTを作る。 各ステートメントの命令数をカウントしないといけないことに気が付き、codegen関数の返り値をvoidからuint16_tにする。

1月12日

else文を実装する。 無条件にジャンプするOP_JMPを作る。

if true
  a = 10
  print a
else
  b = 11
  print b
endif

このスクリプトは次のようなコードに変換されて実行される。

bool true
jmp_ifnot 5
long 10
let 0
load 0
print
jmp 4
long 11
let 1
load 1
print

for文の中にprogram counterã‚’incrementするところがあるので、jmp_ifnotのoperandが1少ないように見えるがこれで正しい。

elseif文を実装する。 構文木を構築するときに新しいif文にしてしまうことで、コード生成を触らなくても実装できてしまうことに気がつく。

デバッグしやすいように、構文木をLISPのような形式で表示できるようにする。

1月13日

while文を実装する。 これまでoperandはuint16_tだと思っていたが、これではジャンプ命令で負の値を指定できないという初歩的なミスに気がつく。 とりあえず暫定対処でOP_JMP_BACKを追加する。

>=, ==, <= など、数値の比較を行う演算子を実装する。

&&, || を実装する。これらは四則演算などの他の二項演算子とは異なり、右辺を評価しないことがある。 if文を作ったときに追加したOP_JMP_NOTは評価値をスタックからpopしてしまうため、仕方なしにOP_JMP_NOT_KEEPを作る。

if文とwhile文が実装されたので、なんとなく「言語らしさ」が出てきてかわいい。

1月14日

operandã‚’uint16_tからint16_tに変更し、OP_JMP_BACKを削除する。 少しリファクタリングする。

最近は仕事が忙しくて進められていない。

1月16日

組み込み関数min(), max()を実装する。 関数の引数のASTを組み立てていて、ようやくnode*の良さが分かってくる。 関数の実装はべた書きでスタックを直接操作していて危ない。 関数呼び出しのoperandには、何番目の関数かというindexと、引数の数を指定するようにする。 ユーザー定義の関数の実装を妄想する。

1月17日

単項演算子 +, - を実装する。 組み込み関数abs()を実装する。

1月18日

endifとendwhileをendにする。RubyやLuaっぽくてかわいい。

a = 10
while a >= 0
  print a
  if a > 5
    print 10
  else
    print 0
  end
  a = a - 1
end

ユーザー定義関数をとりあえずパースできるようにする。

+statement         : FUNC IDENTIFIER LPAREN fargs_opt RPAREN sep statements sep END
+                    {
+                      $$ = cons(nint(NODE_FUNCTION), cons($2, cons($4, $7)));
+                    }
+                  | RETURN expression
+                    {
+                      $$ = cons(nint(NODE_RETURN), $2);
+                    }

まだコード生成はどうすれば良いのかさっぱりわからない。

ファイルが大きくなってきたので分割する。

1月19日

simple virtual machineという意味でsvmと名付けていたが、support vector machineと紛らわしいので、minivmにrenameする。

ユーザー定義関数の実装に想いを馳せる。

1月21日

ユーザー定義関数のコード生成と実行器を実装する。 program counterã‚’save・unsaveするOP_SAVEPC, OP_UNSAVEPC、ローカル変数の領域を確保と解放を行うOP_ALLOC, OP_UNALLOCを実装する。 少し汚いけど、実行時には変数領域を逆さまに使うようにすると、確保した数を持たなくてよいので楽ということに気がつく。 関数の実行は、おおむね次のような流れになる。

• 引数を順番に評価してスタックに積む
• 現在のprogram counter (呼び出し前のpc) をスタックに積む
• 関数呼び出しを行う
• ローカル変数のための変数領域を確保
• popして呼び出し前のpcをローカル変数に入れる
• 引数をpopして後ろからローカル変数に入れていく
• 関数の中身を評価する
• return文で、ローカル変数の変数領域を解放し、呼び出し前のpcに戻す

しかし、関数の中からグローバル変数が見れないとか、再帰呼出しができない (関数自体はグローバル変数領域に確保されるが、関数の中身のコード生成時にローカル変数リストを見ているため) という問題に直面し、頭を抱える。昼寝する。

単項演算子 ! (not) を実装する。

1月22日

グローバル変数とローカル変数は全く性質が違うと悟る。 湯淺先生の本の関数のコード生成の節を読む。 ローカル変数に対するオペコード OP_LET_LOCAL, OP_LOAD_LOCAL_IDENT を追加し、グローバル変数とは区別するように実装し、ようやく関数の中からグローバル変数を参照したり、再帰呼び出しできるようになる。

a = 10
b = 20
func foo(x)
  b = 30
  return a * b + x
end

print foo(50)
print a
print b

このスクリプトが350, 10, 20と表示するようになる (昨日の時点ではグローバル変数領域を見れてなかったので、Undefined variable: aだった)。

フィボナッチ数を計算する (効率の悪い再帰呼び出しの) スクリプトが動き、とても興奮する。テストケースに追加する。

OP_UNALLOCとOP_UNSAVEPCを削除してOP_RETに統一する。ローカル変数領域を明け渡すとともに、program counterを呼び出し元に戻す。

break文とcontinue文を実装する。 continueは簡単なのでまあいいとして、break文のジャンプ先がわからずに小一時間悩む。 ワンパスで生成までやっているので、while文の中身を生成しているときは飛び先のpcが分からない。 仕方なく、while文の先頭にwhile文の最後まで飛ぶジャンプ命令を追加する。

スタックの一番上をコピーして積むOP_DUPを追加して、 &&, ||を作ったときに追加したOP_JMP_IF_KEEPとOP_JMP_NOT_KEEPを削除する。

パフォーマンス改善のために、即値を足したり引いたりするOP_IADDとOP_IMINUSを追加する。 足し算は可換なので即値が左のときも適用できるはずだけど後回し。

そこそこコードを書けるようになったので、軽くスクリプトを書いてみたり速度比較をしてみる。 以下のスクリプトが動く。

func fib(n)
  if n <= 1
    return 1
  end
  return fib(n - 1) + fib(n - 2)
end

n = 0
while n < 38
  print fib(n)
  n = n + 1
end

このスクリプトを9.05sで実行できた。 これと全く同じことを行うスクリプトはruby 2.1.9で9.10s, mruby 1.2.0で14.78s, Lua 5.2.4で12.83s, Python 2.7.12で26.30sかかった。 スクリプト言語としてそこそこの速度が出ている事がわかる。

なお、生成された中間コードは次のような感じになった。

long 3
let 0
jmp 20
ret 2
alloc 2
let_local 1
let_local 0
load_local 0
long 1
<=
jmp_ifnot 2
long 1
jmp -10
load_local 0
iminus 1
call 0 1
load_local 0
iminus 2
call 0 1
+
jmp -18
long 0
jmp -20
long 0
let 1
jmp 1
jmp 11
load 1
long 38
<
jmp_ifnot 7
load 1
call 0 1
print
load 1
iadd 1
let 1
jmp -11

こうやって改めて見てみると、やはり関数の最初にretがあったりwhile文の最初のjmpとかして意味不明かもしれない。 returnやbreakなど、生成時に本来飛びたいジャンプ先がわからずにこうなってしまった。 ワンパスで生成するのにこだわらなかったらもう少し素直なコードになるはずだけど、今回は深追いしないことにする。

これからやること

言語処理系としてやらないといけないことは、まだまだたくさんあります。 文字列や配列、辞書なども作りたいし、型とか関数引数の数のチェックなどをスキップしているので、誤った文法のスクリプトを流すと簡単にセグフォしてしまいます… 流石にそういうのは直したい。 構文エラー時のメッセージも雑すぎるのでなんとかしたいと思っています。 今の実装だとおそらくクロージャが作れないので、もう少しスコープをきちんと扱えるようになってから考えたいです。

それっぽく動くものはできたけど色々と気に入らない部分はあるので、今回の実装はいったん捨てて、また1から書いていくと思います。 参考程度にGitHubにリポジトリを置いておきます。

まとめ

二週間で初めてのインタープリタ言語を実装できたので、今年中にあと23個くらい言語処理系を書くと思います。 今回はスタックマシンで作りましたが、レジスタマシンのコード生成はどうすればいいのかよくわからないし、並行処理のコード生成とか検討もつきません。 LLVMバックエンドを使ってみたり、アセンブラを吐いてみたり、GCを実装してみたり、あるいはgoroutineスケジューラの実装も読んでみたりと、やりたい事が山積みです。 Scalaのwebアプリケーションを運用している以上はJVMについて詳しくなりたいという思いもあります。

その最初のステップとして、簡単なインタープリタ言語を実装してみました。 とりあえず最初の一歩を踏み出せてよかったです。 小さい構文から始めて、少しずつ構文を足していくというやり方は、言語処理系を作る上で有用だと思います。 よく考えてみればそりゃそうかという方法ですが、rui314さんのお話を始めて聞いたときは目から鱗が落ちる思いがしました。

ASTにmruby方式 (LISPのようにcar cdrで表す) を採用したことは、良い面と悪い面がありました。 メモリー管理は1つの構造体について集中しておけばいいので楽です。 関数の引数部分のように、まさにリスト構造になっている部分は配列にするよりも、consで表すほうが楽だと思います。 悪い面としては、コード生成時にcarやcdrが何を表しているのかよく分からなくなるという問題があります。 パーサーの対応する部分を見れば分かるのですが、生成部分のコードだけを見ていたら何も分かりません。 次に書く言語では、この方式は使わずに実装してみたいと思います。

言語実装の楽しみは、バグっていたら全く動かないし、きちんと実装できたら、その文法で書けるあらゆるコード、あらゆるアルゴリズムが動くようになるというところにあると思います。あるところまで書いたら可能性が一気に広がる楽しさというのは昔Tweetしたことがあります。 この思いは今でも変わっていません。

プログラミングってさ, 1書いても1の成果でないじゃん. 5まで, いや, 9まで書いても2の成果しか出ないじゃん. 10まで書いてやっと3の成果が, と思ったら, 100の成果に実ってさ, だから楽しいんだよね.

— いちにぃ (@itchyny) 2012å¹´3月4æ—¥

言語処理系の分野は広大で、いくらでも学ぶ楽しみが広がっています。 いくらやっても学ぶことがあり、しかも実装してみて動くとすごく楽しいというのは、プログラマの趣味としてはうってつけではないでしょうか (趣味レベルに作る程度だと、本業で研究されているレベルまではいくらやっても到達しないままかもしれませんが…)。 実装が公開されている言語もいくつもあり、素晴らしい教材がたくさん見つかります。 第一歩として、スタックマシンのインタープリタ言語を実装してみました。 レジスタマシンやネイティブコード生成、LLVMバックエンドなど、色々な方式を試しながら、言語処理系作りを楽しみたいと思います。