これは Emacs Advent Calendar 2024 の16日目の記事です。一つ前の記事は macOS向けにユニバーサルバイナリーのEmacsを自前ビルドする話 です。
かんたんな自作言語のコンパイラをいろんな言語で書いてみるシリーズ 31番目の言語は Emacs Lisp です。
Emacs Lisp に移植することにより、「コンパイラ実装に入門したいんですけど、最低限の骨組みだけでいいから 1〜2週間くらいでパパッと完成させられて達成感が味わえるやつないですか？ 解説はいろいろ見つかるんだけど自分が読める言語で書かれたミニマルな参考実装がないんですよね。私 Emacs Lisp しか分からなくて……」と言われたときにポンと渡せるようになりました。
できたもの
Emacs Lisp はたまにちょっとしたものを書く程度ですので、Emacs Lisp のコードとしては拙いところがあるかと思います。ただ、高度なテクニックは出てこないのでその分入門者にも読みやすいものになっている……かもしれません（ものは言いよう）。
急いで書いて雑になっているところは後で直します……。
サイズ
$ LANG=C wc -l mrcl_{lexer,parser,codegen}.el lib/*.el
57 mrcl_lexer.el
269 mrcl_parser.el
257 mrcl_codegen.el
43 lib/json.el
60 lib/utils.el
686 total
コンパイラの主要な部分だけならこのくらい:
$ LANG=C wc -l mrcl_{lexer,parser,codegen}.el
57 mrcl_lexer.el
269 mrcl_parser.el
257 mrcl_codegen.el
583 total
動作の例
$ echo '
func add(a, b) {
return a + b;
}
func main() {
call add(1, 2);
}
' | emacs --script mrcl_lexer.el | emacs --script mrcl_parser.el | emacs --script mrcl_codegen.el
# ↓アセンブリが出力される
call main
exit
label add
push bp
mov bp sp
mov reg_a [bp:2]
push reg_a
mov reg_a [bp:3]
push reg_a
pop reg_b
pop reg_a
add reg_a reg_b
mov sp bp
pop bp
ret
mov sp bp
pop bp
ret
label main
push bp
mov bp sp
mov reg_a 2
push reg_a
mov reg_a 1
push reg_a
_cmt call~~add
call add
add sp 2
mov sp bp
pop bp
ret
(snip)
移植元
Ruby 版から移植しています。
自分がコンパイラ実装に入門するために作った素朴なトイ言語とその処理系です。
- コンパクト: コンパイラ部分は 1,000 行程度
- 無理して短く書くようなことはせず、読みやすさ優先で素直に書いてこのくらい
- pure Ruby / 標準ライブラリ以外のライブラリ不要
- ブラックボックスなしですべてを掌握できるように
- x86風の自作VM向け機械語にコンパイルする
- ライフゲームのために必要な機能だけ
- 変数宣言、代入、反復、条件分岐、関数定義
- 演算子:
+,*,==,!=のみ（優先順位は()で明示） - 型なし（値は符号付き整数のみ）
- 作ったときに書いた備忘記事
-
製作メモ
- 作ったときの全過程を書いています
- この通りにやれば誰でも同じものを作れる……のは確かだけど、いろいろ改善点が見えてきたので全体的に改訂したい
- 凝ったことはしていないので Ruby を知らない人でも雰囲気くらいは分かるんじゃないかと
-
本体には含めていない後付けの機能など
- 真偽値リテラル / break / if/else / 単項マイナス / パーサの別実装 / 簡単な静的型検査 / etc.
- これらは後から追加できます
-
他言語への移植
- 最低限の機能だけに絞ってコンパクトにしているので気軽に移植できます
- コンパイラ部分のみ
- Python, TypeScript, Julia, Dart, Haskell, Zig, V, R, Elixir など、2024-07-21 の時点では 29言語
-
セルフホスト版
- さらに育てていってセルフホスト（自作コンパイラで自作コンパイラをコンパイルする）もできました
ライフゲームをコンパイルしてVMで実行する
いつもはコンパイラ部分だけ移植しているのですが、Emacs にはなんとテキストを表示する機能がありますので、アセンブラと VM も移植し、コンパイルした機械語コードの実行まで Emacs 上でできるようにしてみました。
ターミナルで
$ ./compile_run.sh game_of_life.mrcl
のように実行すると Docker コンテナ内でライフゲームのプログラムをコンパイルした後 Emacs が起動し、次のような表示になります。
起動した時点ではステップ実行モードで待機した状態になっています。
s キーを押すと自動実行モードに切り替わり、勝手にプログラムの実行が進んでいきます。
表示を更新する処理は
(erase-buffer)
(insert "...表示する内容...")
を繰り返しているだけですが、これで十分期待した動作になってくれますね。
メモ
- vector の使い方にちょっと慣れた
- 今までちゃんと使う機会がなかった
- シリアライズのフォーマットは JSON。「そこはS式でしょ」と思うのが人情ではありますが、テストが JSON 前提になっている都合でいつもどおり JSON にしました。
- 標準入力から読み込むために
/dev/stdinを使っているので/dev/stdinが使えない環境では動かなさそう - Ubuntu 22.04 の Docker イメージを使っている都合で Emacs のバージョンは 27.1。ちょっと古いですね。Ubuntu 24.04 に上げたい。
この記事を読んだ人は（ひょっとしたら）こちらも読んでいます
「私 Bash しか分からなくて……」と言われたときでも大丈夫。