Go TemplateでCコンパイラを実装する【ELVM】

# TL; DR

- ELVM のバックエンドにGo `text/template`（以下「Go Template」、処理系は[Gomplate](https://docs.gomplate.ca/)）を追加
- C言語(8cc) -> ELVM IR -> Go Template にコンパイル
- 8ccの8cc実装をコンパイルすればGo Templateで8ccコンパイラがつくれる！（セルフホスト）

https://github.com/shinh/elvm

# はじめに

~~ご存じの通り~~ Go Templateはチューリング完全[^turing]なので、任意の処理を実装可能です。
といっても brainf\*ck だけでは華が無いので、今回は **C言語のソースコードをGo Template上で実行します**。

# 過去の ~~ネタ~~ 記事

Go Templateでプログラミングをする方法については過去の記事をご覧ください。

https://qiita.com/Syuparn/items/4157d13c39b95185acfd

https://qiita.com/Syuparn/items/2072207ec0565a80d2b2

# ELVMとは？

ELVMは、以下の仕組みで言語を別言語に変換するコンパイラ（トランスパイラ？）[^trans]です。名前の通り、Esolang版のLLVM的なものです。

```
言語Aのソースコード -> フロントエンド -> IR(中間言語) -> バックエンド -> 言語Bのソースコード
```

製作者のshinhさんご本人の解説記事

http://shinh.skr.jp/slide/elvm/000.html

https://shinh.hatenablog.com/entry/2016/12/22/005706

本記事では、Go Templateを生成するバックエンドを実装することでC言語 (8cc) をGo Templateに変換します。8cc自身で書かれた8ccコンパイラをGo Templateに変換することで、題名の通り「Go TemplateでC言語コンパイラを実装」できます。
~~フルスクラッチ実装を期待された方はすみません...~~

（先日本家にマージいただいたので、晴れて公式（？）に採用されました :tada:）

https://github.com/shinh/elvm/pull/127

# 実装方法
## 処理系選定

`text/template` パッケージはGoのアプリケーションに組み込んで使う想定のものですが、ELVM的にはコマンドで呼び出せるものが便利です。
そこで、Go TemplateをAWKのようにCLIで実行できる 「Gomplate」を使用しました。

https://docs.gomplate.ca/

```bash
$ gomplate -i 'Hello, {{"world!"}}'
Hello, world!
```

~~一応拙作の [tmplscript](https://github.com/Syuparn/tmplscript) も要件を満たしますが、Starが多い安定したものを使いたかったので...~~

注意点として、Gomplateは [Sprig](http://masterminds.github.io/sprig/)が使えません！互換性のある関数があるため表現力にそこまで差はありませんが、手癖で書くと未定義エラーが頻発します。

## 命令の実装

ELVM IR(中間言語のバイトコード)をGo Templateへ変換します。
バックエンドのコード生成処理はC言語で実装されており、すでに50言語以上実装があるので他を参考に進めていきます。

例：Go言語

https://github.com/shinh/elvm/blob/master/target/go.c

生成物は、基本的に以下の形式の実装になっています。

```go:生成物（Goバックエンドの例）
package main
import "os"

func main() {
	// レジスタ用変数の初期化

	// メモリ用変数（スライス）の初期化
	// IO用バッファ変数の初期化

	for {
		// pc(プログラムカウンタ)の番地に対応した命令を呼び出し
		switch pc {
		case 0:
			// 命令
		case 1:
			// 命令
		// ...
		}
	}
}
```

Gomplateの生成物も上記の実装を踏襲しています。

https://github.com/shinh/elvm/blob/master/target/gomplate.c

以下、Go Template特有のハマったところを紹介します。

### メモリ管理

メモリは `{番地: 値}` 形式のmapで表現しています。スライスで実装したほうがシンプルですが、 長さ `2^24` のint64スライスを扱う必要があるので速度的に諦めました[^mem]。

```gomplate:初期化
{{- /* 例：mem[0] = 1, mem[10] = 2 */ -}
{{- $mem :=  coll.Dict 0 1 10 2 -}}
```

```gomplate:LOAD命令
{{- /* 例：123番地の値をレジスタaに読み込み */ -}
{{- /* coll.Has, coll.Indexは文字列キーしか受け取れないのでprintで型変換 */ -}
{{- if coll.Has $mem (print 123) -}}
  {{- $a = $mem | coll.Index (print 123) -}}
{{- else -}}
  {{- $a = 0 -}}
{{- end -}}
```

```gomplate:STORE命令
{{- /* 例：レジスタaの値を123番地に格納 */ -}
{{- /* Gomplateにはmapを破壊的変更する関数が無いため、変更済みmapをマージで新規作成 */ -}
{{- $mem = $mem | coll.Merge (dict 123 $a) -}}
```

`coll.Has`, `coll.Index` が文字列キーしか受け取れないので要注意です（しかもmapのキーがint `123`でも `"123"` でマッチできる）。

### 無限ループが無い

Go Templateのrange文はmap, sliceをループすることしかできないため、有限回で終わってしまいます[^loop]。テンプレートの再帰を使えば無限ループ可能ですが、こちらは実装上の制約で10万回で止まってしまいます。

そこで、range文と再帰を組み合わせて、現実的な範囲ではループが途切れないように ~~ごり押し~~ しました。

```gomplate:力こそパワー
{{- define "Step" -}}
  {{- /* 引数を取り出し変数初期化 */ -}}

  {{- range math.Seq 100 -}}
  {{- range math.Seq 100 -}}
  {{- range math.Seq 100 -}}
  {{- range math.Seq 100 -}}
  {{- range math.Seq 100 -}}
  {{- range math.Seq 100 -}}
    {{- if false -}}
    {{- else if (eq $pc 0) -}}
      {{- /* 命令 */ -}}
    {{- else if (eq $pc 1) -}}
      {{- /* ... */ -}}
    {{- end -}}
    {{- $pc = (math.Add $pc 1) -}}
  {{- end -}}
  {{- end -}}
  {{- end -}}
  {{- end -}}
  {{- end -}}
  {{- end -}}

  {{- /* ローカル変数を引数に渡して再帰 */ -}}
  {{- $args := coll.Dict "in" $in "out" $out "cursor" $cursor "mem" $mem "a" $a "b" $b "c" $c   "d" $d "bp" $bp "sp" $sp "pc" $pc -}}
  {{- tmpl.Exec "Step" $args -}}
{{- end -}}
```

rangeは長さ1兆の1重ループにすることもできますが、メモリを食いすぎてクラッシュする（※`math.Seq` はスライスを生成する）ため、長さ100の6重ループにしました。

### EXITでプログラムを終了

`EXIT` 命令を実行すると即座に `os.Exit(0)` する必要がありますが、Gomplateにこのような関数はありません[^exit]。
そこで、上記の無限ループに「`EXIT` を評価したらbreak」という処理を追加します。

```gomplate:EXITの追加
{{- define "Step" -}}
  {{- /* 引数を取り出し変数初期化 */ -}}

  {{- range math.Seq 100 -}}
  {{- /* ...以下rangeのネスト */ -}}
    {{- if false -}}
    {{- else if (eq $pc 0) -}}
      {{- /* 命令 */ -}}
    {{- else if (eq $pc 1) -}}
      {{- /* 命令がEXITの場合 */ -}}
	  {{- $exited = true -}}
    {{- end -}}
    {{- $pc = (math.Add $pc 1) -}}
    {{- if $exited -}}
	  {{- break -}}
	{{- end -}}
  {{- end -}}
  {{- /* ...以下endのネスト */ -}}

  {{- /* EXITしていたら再帰しない */ -}}
  {{- if not $exited -}}
    {{- $args := coll.Dict   "in" $in   "out" $out   "cursor" $cursor   "mem" $mem   "a" $a   "b" $b   "c" $c   "d" $d   "bp" $bp   "sp" $sp   "pc" $pc   -}}
    {{- tmpl.Exec "Step" $args -}}
  {{- end -}}
{{- end -}}
```

### レジスタを24bitに切り詰める

8ccのレジスタは24bit (`uint24`)なので、`int64` を切り詰める必要があります。残念ながらGomplateにビット演算は無いため、余りを使って素朴に実装しました。余りに `2^24` を足してからまた余りを取っているのは、結果を必ず正にするためです。

```gotemplate:ADD命令
{{- /* d = ((d + 2^24) % 2^24 + 2^24) % 2^24 */ -}
{{- $d = (math.Rem (math.Add (math.Rem (math.Add $d 16777215) 16777216) 16777216) 16777216) -}}
```

### IO
#### in

Gomplateは、外部入力を `datasource` として受け取ることができます。今回は `stdin` を `datasource` にすることで `GETC` 命令を実装しました。

https://docs.gomplate.ca/datasources/

```makefile:Makefile
TARGET := gomplate
# 生成ファイルを `gomplate --datasource data=stdin: -f hoge.gomplate` の形式で実行
RUNNER := gomplate --datasource data=stdin: -f
```

datasourceはURLの形式で書くため、スキーム `stdin:` のみ指定しています。

Template内部では、`datasource` 関数の戻り値として読み込めます。

```gomplate:GETC命令
{- /* $in にstdinを文字列で格納 */ -}
{- /* 初期化時に読み込むとstdinを使わないプログラムでハングするため、最初にGETCが呼ばれたタイミングで取得 */ -}
{{- if (eq $in "") -}}
  {{- $in = (datasource \"data\") -}}
{{- end -}}
{{- /* GETCは一文字ずつ読み込むため、現在のカーソルが指すバイトのみ取得 */ -}
{{- if (lt $cursor (len $in)) -}}
  {{- /* stringをcoll.Indexするとbyteが取れる（Goと同じ）ので、そのままint型のレジスタへ代入 */ -}}
  {{- $a = $in | coll.Index $cursor -}}
  {{- $cursor = math.Add $cursor 1 -}}
{{- else -}}
  {{- $a = 0 -}}
{{- end -}}
```

#### out
~~「入力と違って、出力の関数はないのでは？」と思った貴方。Go Templateプログラミング沼へようこそ。~~

Go Templateの **本来の用途**、変数を直接 `{{ $hoge }}` とすれば結果がレンダリングされるのでした。

`PUTC` 命令で出力用バッファ変数に追記し、`EXIT` 命令でプログラムを終了する際にバッファ全体をレンダリングしています。

```gotemplate:PUTC命令の処理
{{- $out = printf "%s%c" $out (math.Rem 42 256) -}}
```

```gotemplate:EXIT命令の処理
{{- /* EXITが２回以上呼ばれても */ -}
{{- if not $exited -}}{{$out}}{{- end -}}
{{- $exited = true -}}
```

# 動かしてみる！

というわけで、いよいよGomplateでC言語をコンパイルするときがやってきました。

## コンパイラの概要

コンパイラは以下のように動作します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239887/2adc0b68-3f1c-4aed-0400-18ee1c2c8357.png)

まずコンパイラのフロントエンドがCのソースコードからELVM IRを生成します。次に、バックエンドがIRから今回のターゲット言語であるGomplateを生成します。
ちなみに、**フロントエンド自体もGomplate製です**。ELVMの8ccフロントエンド自体も8ccで書かれているため、自身をコンパイルすることでGomplate製のフロントエンドが手に入るという寸法です[^backend]。**ブートストラップ最強。**

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239887/57e01b63-6ea6-f142-89e8-e74c657b5e4b.png)

## ビルドする

使用したGomplateは最新版(プレリリース) `v4.0.0-pre-2` です。3系だと動かないので要注意。

Makefileでターゲット言語へのコンパイルと動作テストが行えます。このサンプルコードに8ccのコンパイラも含まれている[^8cc]ので、以下を実行するだけで8ccフロントエンドのGomplate実装が手に入ります。

```bash
$ make gomplate
```

生成されたGomplateソースコードは**驚異の6MB**です。

```bash
$ ll out/8cc.c.eir.gomplate
-rwxr-xr-x 1 syuparn syuparn 6335625 Apr  2 21:41 out/8cc.c.eir.gomplate*
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239887/b82094b9-1fd3-8422-12f5-aeff233db6d7.png)

続いて、この巨大なフロントエンド実装で以下のソースコードをELVM IRへコンパイルします。

```c:out/8cc.in.c
int putchar(int x);

int main() {
  putchar('X');
  return 0;
}
```

```bash:いざコンパイル！
cat out/8cc.in.c | gomplate --datasource data=stdin: -f out/8cc.c.eir.gomplate > out/compiled.eir
```

~~ご想像の通りめちゃくちゃ遅いので、8コア32GBのPCでもコンパイルに1時間かかります~~ :innocent:
しかし、確かにELVM IRができています。

```eir:out/compiled.eir
        .text
main:
        #{push:main}
        mov D, SP
        add D, -1
        store BP, D
        mov SP, D
        mov BP, SP
        .file 1 "-"
        .loc 1 5 0
        .loc 1 4 0
        mov A, 88
        mov D, SP
        add D, -1
        store A, D
        mov SP, D
        putc A
        add SP, 1
        .loc 1 5 0
        mov A, 0
        mov B, A
        #{pop:main}
        exit
        #{pop:main}
        exit
```

続いて、バックエンドでターゲットのGomplateにコンパイルします。

```bash
$ ./out/elc -gomplate out/compiled.eir > out/compiled.gomplate
```

できたものがこちら。

```gotemplate:out/compiled.gomplate
{{- define "Step" -}}
 {{- $in := $ | coll.Index "in" -}}
 {{- $out := $ | coll.Index "out" -}}
 {{- $cursor := $ | coll.Index "cursor" -}}
 {{- $mem := $ | coll.Index "mem" -}}
 {{- $a := $ | coll.Index "a" -}}
 {{- $b := $ | coll.Index "b" -}}
 {{- $c := $ | coll.Index "c" -}}
 {{- $d := $ | coll.Index "d" -}}
 {{- $bp := $ | coll.Index "bp" -}}
 {{- $sp := $ | coll.Index "sp" -}}
 {{- $pc := $ | coll.Index "pc" -}}
 {{- $exited := false -}}

 {{- range math.Seq 100 -}}
 {{- range math.Seq 100 -}}
 {{- range math.Seq 100 -}}
 {{- range math.Seq 100 -}}
 {{- range math.Seq 100 -}}
 {{- range math.Seq 100 -}}
  {{- if false -}}
 {{- else if (eq $pc 0) -}}
  {{- $pc = math.Sub 1 1 -}}
 {{- else if (eq $pc 1) -}}
  {{- $d = $sp -}}
  {{- $d = (math.Rem (math.Add (math.Rem (math.Add $d 16777215) 16777216) 16777216) 16777216) -}}
  {{- $mem = $mem | coll.Merge (dict $d $bp) -}}
  {{- $sp = $d -}}
  {{- $bp = $sp -}}
  {{- $a = 88 -}}
  {{- $d = $sp -}}
  {{- $d = (math.Rem (math.Add (math.Rem (math.Add $d 16777215) 16777216) 16777216) 16777216) -}}
  {{- $mem = $mem | coll.Merge (dict $d $a) -}}
  {{- $sp = $d -}}
  {{- $out = printf "%s%c" $out (math.Rem $a 256) -}}
  {{- $sp = (math.Rem (math.Add (math.Rem (math.Add $sp 1) 16777216) 16777216) 16777216) -}}
  {{- $a = 0 -}}
  {{- $b = $a -}}
  {{- if not $exited -}}{{$out}}{{- end -}}
  {{- $exited = true -}}
  {{- if not $exited -}}{{$out}}{{- end -}}
  {{- $exited = true -}}
  {{- end -}}
  {{- $pc = (math.Add $pc 1) -}}
 {{- if $exited -}}{{- break -}}{{- end -}}{{- end -}}
 {{- if $exited -}}{{- break -}}{{- end -}}{{- end -}}
 {{- if $exited -}}{{- break -}}{{- end -}}{{- end -}}
 {{- if $exited -}}{{- break -}}{{- end -}}{{- end -}}
 {{- if $exited -}}{{- break -}}{{- end -}}{{- end -}}
 {{- if $exited -}}{{- break -}}{{- end -}}{{- end -}}

 {{- if not $exited -}}
  {{- $args := coll.Dict   "in" $in   "out" $out   "cursor" $cursor   "mem" $mem   "a" $a   "b" $b   "c" $c   "d" $d   "bp" $bp   "sp" $sp   "pc" $pc   -}}
  {{- tmpl.Exec "Step" $args -}}
 {{- end -}}
{{- end -}}

{{- $in := "" -}}
{{- $out := "" -}}
{{- $cursor := 0 -}}
{{- $a := 0 -}}
{{- $b := 0 -}}
{{- $c := 0 -}}
{{- $d := 0 -}}
{{- $bp := 0 -}}
{{- $sp := 0 -}}
{{- $pc := 0 -}}
{{- $mem :=  coll.Dict 0 1 -}}
{{- $args := coll.Dict "in" $in "out" $out "cursor" $cursor "mem" $mem "a" $a "b" $b "c" $c "d" $d "bp" $bp "sp" $sp "pc" $pc -}}
{{- tmpl.Exec "Step" $args -}}
```

これをGomplateで実行すると...「`X`」が表示されました！コンパイル成功です :tada:

```bash
$ gomplate --datasource data=stdin: -f out/compiled.gomplate
X
```

これで、**C言語のソースコードを書くだけでELVMでGo Templateへ移植できるようになりました**。
~~もうただのテンプレートエンジンとは呼ばせません。~~ 思うがまま、好きなものを実装してください。

# おわりに

以上、ELVMでGo Template実装を追加した紹介でした。ELVMは本当にロマンあふれるコンパイラなので、他のesolangバックエンド実装も読んでいきたいと思います。また、元ネタ（？）のLLVMにも挑戦したいです。

[^turing]: 厳密には、テンプレート再帰が100,000回しかできないため無限ループは作れません。実用性（？）を考えると、再帰を可能な限りfor文に置き換える最適化が必要です。
[^trans]: この場合、トランスパイルとコンパイルどちらが適切な表現なのでしょうか...？
[^loop]: 厳密にはチャネルを使って無限ループを生成可能ですが、標準関数/Gomplateではチャネルを生成できません。
[^exit]: `test.Fail` は即座に終了しますが `os.Exit(1)` のため条件を満たしません。
[^mem]: スライス自体は128MBしかありませんが、Gomplateに破壊的変更の関数が無いため更新するたびスライス複製が必要になってしまいます...
[^8cc]: ややこしいですが、「C言語で書かれた8ccコンパイラ実装のソースコード」をELVMでコンパイルしGomplateソースコード（=Gomplate製の8ccコンパイラ）を生成しています。
[^backend]: バックエンドは現状8cc製ではないためブートストラップすることはできませんが、8ccに移植すれば完全Gomplate製のELVMも作れるはずです。