TL; DR
- ELVM のバックエンドにGo
text/template（以下「Go Template」、処理系はGomplate）を追加 - C言語(8cc) -> ELVM IR -> Go Template にコンパイル
- 8ccの8cc実装をコンパイルすればGo Templateで8ccコンパイラがつくれる！（セルフホスト）
はじめに
ご存じの通り Go Templateはチューリング完全1なので、任意の処理を実装可能です。
といっても brainf*ck だけでは華が無いので、今回は C言語のソースコードをGo Template上で実行します。
過去の ネタ 記事
Go Templateでプログラミングをする方法については過去の記事をご覧ください。
ELVMとは？
ELVMは、以下の仕組みで言語を別言語に変換するコンパイラ（トランスパイラ？）2です。名前の通り、Esolang版のLLVM的なものです。
言語Aのソースコード -> フロントエンド -> IR(中間言語) -> バックエンド -> 言語Bのソースコード
製作者のshinhさんご本人の解説記事
本記事では、Go Templateを生成するバックエンドを実装することでC言語 (8cc) をGo Templateに変換します。8cc自身で書かれた8ccコンパイラをGo Templateに変換することで、題名の通り「Go TemplateでC言語コンパイラを実装」できます。
フルスクラッチ実装を期待された方はすみません...
（先日本家にマージいただいたので、晴れて公式（？）に採用されました 
）
実装方法
処理系選定
text/template パッケージはGoのアプリケーションに組み込んで使う想定のものですが、ELVM的にはコマンドで呼び出せるものが便利です。
そこで、Go TemplateをAWKのようにCLIで実行できる 「Gomplate」を使用しました。
$ gomplate -i 'Hello, {{"world!"}}'
Hello, world!
一応拙作の tmplscript も要件を満たしますが、Starが多い安定したものを使いたかったので...
注意点として、Gomplateは Sprigが使えません！互換性のある関数があるため表現力にそこまで差はありませんが、手癖で書くと未定義エラーが頻発します。
命令の実装
ELVM IR(中間言語のバイトコード)をGo Templateへ変換します。
バックエンドのコード生成処理はC言語で実装されており、すでに50言語以上実装があるので他を参考に進めていきます。
例：Go言語
生成物は、基本的に以下の形式の実装になっています。
package main
import "os"
func main() {
// レジスタ用変数の初期化
// メモリ用変数（スライス）の初期化
// IO用バッファ変数の初期化
for {
// pc(プログラムカウンタ)の番地に対応した命令を呼び出し
switch pc {
case 0:
// 命令
case 1:
// 命令
// ...
}
}
}
Gomplateの生成物も上記の実装を踏襲しています。
以下、Go Template特有のハマったところを紹介します。
メモリ管理
メモリは {番地: 値} 形式のmapで表現しています。スライスで実装したほうがシンプルですが、 長さ 2^24 のint64スライスを扱う必要があるので速度的に諦めました3。
{{- /* 例：mem[0] = 1, mem[10] = 2 */ -}
{{- $mem := coll.Dict 0 1 10 2 -}}
{{- /* 例：123番地の値をレジスタaに読み込み */ -}
{{- /* coll.Has, coll.Indexは文字列キーしか受け取れないのでprintで型変換 */ -}
{{- if coll.Has $mem (print 123) -}}
{{- $a = $mem | coll.Index (print 123) -}}
{{- else -}}
{{- $a = 0 -}}
{{- end -}}
{{- /* 例：レジスタ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をループすることしかできないため、有限回で終わってしまいます4。テンプレートの再帰を使えば無限ループ可能ですが、こちらは実装上の制約で10万回で止まってしまいます。
そこで、range文と再帰を組み合わせて、現実的な範囲ではループが途切れないように ごり押し しました。
{{- 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にこのような関数はありません5。
そこで、上記の無限ループに「EXIT を評価したらbreak」という処理を追加します。
{{- 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 を足してからまた余りを取っているのは、結果を必ず正にするためです。
{{- /* 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 命令を実装しました。
TARGET := gomplate
# 生成ファイルを `gomplate --datasource data=stdin: -f hoge.gomplate` の形式で実行
RUNNER := gomplate --datasource data=stdin: -f
datasourceはURLの形式で書くため、スキーム stdin: のみ指定しています。
Template内部では、datasource 関数の戻り値として読み込めます。
{- /* $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 命令でプログラムを終了する際にバッファ全体をレンダリングしています。
{{- $out = printf "%s%c" $out (math.Rem 42 256) -}}
{{- /* EXITが２回以上呼ばれても */ -}
{{- if not $exited -}}{{$out}}{{- end -}}
{{- $exited = true -}}
動かしてみる！
というわけで、いよいよGomplateでC言語をコンパイルするときがやってきました。
コンパイラの概要
コンパイラは以下のように動作します。
まずコンパイラのフロントエンドがCのソースコードからELVM IRを生成します。次に、バックエンドがIRから今回のターゲット言語であるGomplateを生成します。
ちなみに、フロントエンド自体もGomplate製です。ELVMの8ccフロントエンド自体も8ccで書かれているため、自身をコンパイルすることでGomplate製のフロントエンドが手に入るという寸法です6。ブートストラップ最強。
ビルドする
使用したGomplateは最新版(プレリリース) v4.0.0-pre-2 です。3系だと動かないので要注意。
Makefileでターゲット言語へのコンパイルと動作テストが行えます。このサンプルコードに8ccのコンパイラも含まれている7ので、以下を実行するだけで8ccフロントエンドのGomplate実装が手に入ります。
$ make gomplate
生成されたGomplateソースコードは驚異の6MBです。
$ ll out/8cc.c.eir.gomplate
-rwxr-xr-x 1 syuparn syuparn 6335625 Apr 2 21:41 out/8cc.c.eir.gomplate*
続いて、この巨大なフロントエンド実装で以下のソースコードをELVM IRへコンパイルします。
int putchar(int x);
int main() {
putchar('X');
return 0;
}
cat out/8cc.in.c | gomplate --datasource data=stdin: -f out/8cc.c.eir.gomplate > out/compiled.eir
ご想像の通りめちゃくちゃ遅いので、8コア32GBのPCでもコンパイルに1時間かかります 
しかし、確かにELVM IRができています。
.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にコンパイルします。
$ ./out/elc -gomplate out/compiled.eir > 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」が表示されました！コンパイル成功です
$ gomplate --datasource data=stdin: -f out/compiled.gomplate
X
これで、C言語のソースコードを書くだけでELVMでGo Templateへ移植できるようになりました。
もうただのテンプレートエンジンとは呼ばせません。 思うがまま、好きなものを実装してください。
おわりに
以上、ELVMでGo Template実装を追加した紹介でした。ELVMは本当にロマンあふれるコンパイラなので、他のesolangバックエンド実装も読んでいきたいと思います。また、元ネタ（？）のLLVMにも挑戦したいです。
-
厳密には、テンプレート再帰が100,000回しかできないため無限ループは作れません。実用性（？）を考えると、再帰を可能な限りfor文に置き換える最適化が必要です。 ↩
-
この場合、トランスパイルとコンパイルどちらが適切な表現なのでしょうか...？ ↩
-
スライス自体は128MBしかありませんが、Gomplateに破壊的変更の関数が無いため更新するたびスライス複製が必要になってしまいます... ↩
-
厳密にはチャネルを使って無限ループを生成可能ですが、標準関数/Gomplateではチャネルを生成できません。 ↩
-
test.Failは即座に終了しますがos.Exit(1)のため条件を満たしません。 ↩ -
バックエンドは現状8cc製ではないためブートストラップすることはできませんが、8ccに移植すれば完全Gomplate製のELVMも作れるはずです。 ↩
-
ややこしいですが、「C言語で書かれた8ccコンパイラ実装のソースコード」をELVMでコンパイルしGomplateソースコード（=Gomplate製の8ccコンパイラ）を生成しています。 ↩