ELVM Compiler Infrastructureバックエンド作成のすゝめ

初編

「天はELVM Compiler Infrastructureの上にELVM Compiler Infrastructureを造れり」と言えり。されば天よりCコンパイラを生ずるには、……

というわけで,この記事では,(どこかに作者の資料があるかもしれないが)ELVM Compiler Infrastructureバックエンド作成法を解説する.

ELVM Compiler Infrastructureとは

ELVM Compiler Infrastructure(以下,本記事ではELVMと省略)とは

から構成されるCコンパイラ*1である.作者は@shinh氏.ELVMの詳細はここあたりを参照するとよいだろう.要は,Cプログラムを様々な他言語に変換できる.

何がうれしいのか

Turing完全性が云々……という話を置いておけば,純粋に変換でしかないので,普通のプログラミング言語ならあまりメリットはないだろう.しかし,これが難解プログラミング言語になると話が変わってくる.作者がLispインタプリタをPietで動かしたように,記述が困難な言語で大規模なプログラムを生成しやすくなるのだ.

さらに,ELVMの大きな特徴として,ELVMそのものがELVMでコンパイルできることが挙げられる.つまり,ELVMのバックエンドに追加されている言語でCコンパイラをお手軽に作ることができるようになるのだ.

話は変わり,近年,私のTLにおいて次の事象が観測された.

こんな話もあった.

時代がTeXでCコンパイラを求めていることは自明であった.しかし,ELVMバックエンドにはTeXがない.というわけで,ELVMのTeXバックエンドを作成し,それを用いてCコンパイラ(8cc.tex)を作成した.

8cc.texの話は別の機会に行うものとして,さっそくELVMバックエンドの作成方法を記していこう.

ELVMバックエンド作成

準備

まずは,バックエンドに追加する言語を決めて本家をfork.

バックエンドの作成

実際,バックエンドを作成する際に作成するファイルは少ない.foo言語のバックエンドを作るなら,targetディレクトリにfoo.cを作成するだけである.正直,既存の多言語での実装を読めばどのように実装すべきかはすぐにわかるのだが,次の点に注意して読むとよりわかりやすくなるだろう.

  • レジスタは全部で7つ.特に気にするべきなのはpcである.名前の通りプログラムカウンタで,実行のループのたびにインクリメントする必要がある
  • EIRは24bitマシンであることを想定している.普通の言語なら適宜マスクをかける必要があるだろう
    • で,私はこの部分でUINT_MAX + 1を使用するという初心者レベルの失態を犯していた.後世のために,このミスを告白しておく
  • メモリの初期値はModule構造体のdataに0番地から順に格納されている.ただし,dataに入っていない部分についても読み込んだ時に0が返ってくるようにしておく必要がある
  • 命令はdataとは別にModule構造体のtextで与えられる*2.これをバックエンドに追加する言語用に変換していく.
    • textの型はInstで,単方向リストになっている.メンバpcが同一のInst同士は,ひとつのグループとして扱う必要がある*3.これをバックエンドに追加する言語用に変換していく.ジャンプもこのグループ単位で行われる点に注意

さらに,EIRは命令セットが小さい.大まかな特徴をあげておこう.

  • 算術演算は加算(ADD)と減算(SUB)しかない.なお,乗算,除算,およびビット演算はビルトイン関数で実装済みである
  • ファイルIOはない.libcの実装を見ればわかるが,fopenしてもstdinが返ってくる
  • 標準入出力の命令は1文字読み込み(GETC)と1文字書き込み(PUTC)しかない

ビルドおよびテストの準備

ここまでで,foo.cの作成が終了したとする.あとは,これを本体に組み込んでテストを実行するだけである.

まずは,バックエンドを使えるようにするため,target/elc.cfoo.cのメインの関数のプロトタイプ宣言を記述しよう.次のようになるはずである.

/* ...(中略)... */
void target_bef(Module* module);
void target_bf(Module* module);
void target_unl(Module* module);
void target_foo(Module* module); /* <- ここが追加 */
typedef void (*target_func_t)(Module*);

次に,target_fooが呼べるように条件分岐を追加する.次のようになるはずだ.

static target_func_t get_target_func(const char* ext) {
  if (!strcmp(ext, "rb")) {
    return target_rb;
  } else if (!strcmp(ext, "py")) {
    return target_py;
  } else if (!strcmp(ext, "js")) {
    /* ...(中略)... */
  } else if (!strcmp(ext, "unl")) {
    return target_unl;
  } else if(!strcmp(ext, "foo")) { /* <-ここが追加 */
      return target_foo;           /* <-ここが追加 */
  } else {
    error("unknown flag: %s", ext);
  }
}

なお.関数の追加位置については,(作者に本来は確認すべきだが)末尾のほうが良いだろう.最初に追加されたUnlambdaは末尾に,次に追加されたVim scriptはEmacs Lispとの対比の目的でその脇に配置されたが,私がTeXを追加するときに,誤ってVim scriptの脇に配置してしまった*4*5

そして,追加したファイルをmakeできるようにする.Makefileに次のように追加する.

# ...(中略)...
# 末尾にfoo.cを追加
ELC_SRCS := elc.c util.c rb.c py.c ... unl.c foo.c
# ...(さらに中略)...
# 同じような記述が並んでいるところ(Targets)に次を追加
TARGET := foo
RUNNER := <<foo-runner>>
include target.mk

<<foo-runner>>には,コンパイル結果を動かすためのコマンドを記載しておく.1コマンドで動かない場合は,tools/foo.shを追加し,1コマンドで動くようにしておく.TeXではこれを用いている.

これで,makeが行えるようになった.追加した言語のテストはmake foomake elc-fooで行う.これがすべて通過すれば追加した部分は問題ないだろう.その後,make testすることによって,全言語のテストを行うことができる.make testは私の環境*6で時間がかかったので,お茶でも飲んで行く末を見守ると良いだろう.

テストまで通ったら,あとはREADME.mdのバックエンド一覧にfoo言語を追加し,言語数をインクリメントする.

終わりに

世界にELVMバックエンドが増えるといいな.

*1:現状は.フロントエンドが追加されればあるいは

*2:ハーバードアーキテクチャ

*3:Javaバックエンドでは同一のメソッドになるようになっている.

*4:さらに,README.mdとmakeなどの順序が異なってしまっている

*5:実は,その後に追加されたCommon LispTeXの脇に配置されてしまった.本当に申し訳ない

*6:Surface Pro 3上のHyper-Vで動くArch Linux(512MB memory)