技術も腕力もないけどコンパイラを自作してみた

概要

LispをCへ変換するコンパイラ(トランスパイラということもありますが以下コンパイラと呼びます)を Go で実装してみました。

成果物については PLC で公開しています。

この記事では特に整数のみを扱うLispコンパイラを実装して、フィボナッチ数を計算できるようになるまでの過程をまとめました。

免責 Goで作ってみたのですが本編ではまったくGoが出てきません。

はじめに

簡単なコンパイラを作るのは難しくない

TCFM #10 52:10

コンパイラを自作するなんて難度高そうだけど、そんなに難しくないというならひょっとしたらできるんじゃないか。

とはいえ、C言語自体詳しくないのにそのコンパイラを作るというのはさすがに無謀すぎる。

もっと難易度の低そうな言語はないか。

そこでLisp。

カッコだらけだけど、パースするのは簡単にできる。

さらに、最低限必要な要素も

• atom
• eq
• car
• cdr
• cons
• if
• quote
• lambda
• define

これさえあればいい。たった9つ。全容を把握できているって素晴らしい。
これだけだとデバッグで困るので、printとprognを追加することにしよう。

さて、次は出力形式をきめる。

8ccだとアセンブリを吐いてるけど、Human Resource Machineで遊んだ程度の知識しかないので やめておいたほうがよさそうだ。

アセンブリより優しそうな候補として、LLVM IRを考えてみる。実行結果を逐一保存していくのは面倒だけど、structureもあるしよさそう。

試しにprintを実装してみるとできた。これはいけるかもしれない。

念の為、より優しいCの出力についても試してみる。

やってみると圧倒的に便利で、コード量がLLVM IR出力の半分以下になった。腕力がそんなにあるわけじゃないから、
ひとまずC出力で実装しきって、IR出力については発展課題(ここではやらない)ということにしよう。

実装してみる

まず手でコンパイルしてみて実装方針に問題がないか、イメージしきれていない箇所の洗い出しを行った上で、コンパイラの実装に落とし込んでいきます。

printを例にとってみると、入力のLispコードが

(print 1 2 3)

なら、出力となるCコードは

#include<stdio.h>

int main(void) {
	printf("%d %d %d\n", 1, 2, 3);
}

となります。この中で4行目以外はすべてテンプレ出力で問題ないのでとくに考えることはありません。
print実装の肝としても、引数に合わせて書式指定などを整えてあげるだけなので、ささっと実装できます。

これだけだと明らかに機能不足なので、なにか処理をした上でprintするようなものを作ってみます。

例えば、1+2の結果をprintするとすると、

(print (+ 1 2) (+ 3 4 5))

これをコンパイルした場合、テンプレ部分を除いたコードは、

int plus_0 = 1 + 2;
int plus_1 = 3 + 4 + 5;
printf("%d %d\n", plus_0, plus_1);

となるように実装します。計算の結果を逐一保存して、保存した結果をprintに渡します。
ついでに+を実装していて、引数をすべて評価して + で連結するだけで実装しています。

こうするとmain関数に大量の変数が宣言されることになり、メモリも確保されっぱなしになります。
本来ならばGCを実装するところだろうけれど、これも発展課題としてとっておくことにします。

ここまででprintの実装は一段落したので、prognの実装に進みます。

けど、引数を順に評価するだけなので特に難しいことはなく、最後の評価値を返値となるとなるようにして終わりとします。

せっかく複数の処理を流せるようになったので、次はdefineを定義して変数を取り扱ってみることにします。

(progn
  (define a 1)
  (print a))

int a = 1;
printf("%d\n", a);

現状では整数のみを取り扱うことにしているので、整数変数を定義するようになっていれば問題ありません。
その裏側、コンパイラの内部処理で、変数の宣言チェックが行えるように記録しておきます。

変数定義ができるようになったので、関数定義もできるよう lambda の実装に移ります。
まず、defineとの組み合わせを考える前に lambda の即時実行を実装してみます。

(print ((lambda (x) (+ x 1)) 2))

int lambda_0(int *args) {
	int x = args[0];
	int add_0 = x + 1;
	return add_0;
}

int main(void) {
	int lambda_0_args[] = {2};
	printf("%d\n", lambda_0(lambda_0_args));
}

lambdaを使ったら順次関数として定義していくことにします。引数については個数を考慮したくないので、
配列で受け取ることにして、関数内で適宜変数に再割当てします。関数呼び出しをしている箇所では、
事前に引数を配列にまとめて保持しておくようにします。

lambdaができたのでdefineと組み合わせて関数定義を実装してみます。
といっても、lambdaで定義した関数を関数ポインタに代入するだけでそれっぽくなります。

(define add1 (lambda (x) (+ x 1)))

int (*add1)(int*);
int lambda_0(int *args) {
	int x = args[0];
	int add_0 = x + 1;
	return add_0;
}

int main(void) {
	add1 = lambda_0;
}

次は、条件分岐をできるようにしたいので eq や if を実装してみます。eq でやることは + と似ていて、+ の代わりに && で連結するだけです。

(eq 1 2 3)

bool eq_0 = 1==2 && 1==3;

この eq を使って if の実装にとりかかります。

(if (eq 1 2) 10 20)

int if_0;
int eq_0 = 1==2;
if (eq_0) {
	if_0 = 10;
} else {
	if_0 = 20;
}

適当にCのifに変換するだけでもそれっぽく動いてくれます。ここに、+ と同様に - を追加してあげるとフィボナッチ数を再帰で計算することができます。

実際にやってみると、

(progn
	(define fib (lambda (n)
		(if (eq n 0)
			0
			(if (eq n 1)
				1
				(+ (fib (- n 1)) (fib (- n 2)))))))
	(print (fib 10)))

#include<stdio.h>

int (*fib)(int*);
int lambda_1(int *args){
  int n = args[0];
  int if_1;
  int eq_2 = n == 0;
  if (eq_2) {
    if_1 = 0;
  } else {
    int if_3;
    int eq_4 = n == 1;
    if (eq_4) {
      if_3 = 1;
    } else {
      int minus_5 = n;
      minus_5 -= 1;
      int fib_args_6[] = {
        minus_5
      };
      int minus_7 = n;
      minus_7 -= 2;
      int fib_args_8[] = {
        minus_7
      };
      int plus_9 = 0;
      plus_9 += fib(fib_args_6);
      plus_9 += fib(fib_args_8);
      if_3 = plus_9;
    }
    if_1 = if_3;
  }

  return if_1;
}

int main(void) {
  fib = lambda_1;
  int fib_args_2[] = {
    10
  };
  printf("%d\n" , fib(fib_args_2));
}

こんな感じの冗長なコードが生成されますが、実際に動かしてみるとちゃんと計算してくれます。

まとめ

lispをCに愚直に変換するコンパイラ(トランスパイラ)を作ってみました。

ここまでの過程で実装したものは

から取得できます。

とにかく動くことを目標にして、実装難度がなるべく低くなるように設計して実装してみると、
つまづくところもほとんどなくフィボナッチ数の計算などもできるところまで実装できました。

数少ないつまづきポイントをまとめてみると、

• if
  • 初期実装ではifを関数として実装して、引数すべてを評価してから返り値を決めるというポカをしてました。
• 再帰関数
  • undefinedチェックを行っていましたが、defineの代入タイミングとlambdaの定義タイミングが前後してエラーを吐くというお約束も経験しました。

今回実装したのは整数のみを扱うLispで、Lispなのにリスト処理をちゃんとできない出来損ないでした。
次回はリスト処理を行えるようにデータ構造の見直しを行い、evalのlispコードをコンパイルしてランタイムでevalが動かせるコンパイラの実装を行います。

では、ご拝読ありがとうございました。

おまけ

ここでは、残りのatom, quote, car, cdr, consについて触れていきます。

なぜ本編で扱わなかったのかというと、この記事で実装してみたlambdaでは返り値をintと決め打ちしているように、
cdrやconsと併用できないという致命的な設計ミスがあったためです。

とはいえ、全くやらずに次の目標に向かうのもモヤモヤするので、ここで触れるようなふわっとした実装をしました。

atomについては、引数をコンパイル時に評価してみて整数かどうかで0か1で初期化するとしました。

quoteでは、引数を整数と整数リストのみと限定して実装しました。
整数なら

(quote 1)

int quote_0 = 1;

整数リストなら整数配列に変換します。

(quote (1 2 3))

int quote_0[] = {1,2,3};

carについては、quoteで整数リストを整数配列に変換したように、内部的には整数配列の最初の値を返すという実装をしました。

cdrは、引数で渡された整数リストに対して、2番目以降の要素を新しく定義した配列に入れるという実装をしました。

consについても、新しい配列を作って要素を入れ込むというものを作りました。
入れ子リストなどは次の段階で取り組むことにして、ここでは一次元の整数リストのみを扱うことにしました。

以上がこの記事で扱ったコンパイラでの実装となります。