Elixirで簡単な自作言語のコンパイラを書いた

これは Elixir Advent Calendar 2023 の11日目の記事です。一つ前の記事は asdf-elixir の default-mix-commands で Mix コマンドを自動で実行する、次の記事は 初心者によるElixir入門① #初心者 です。

簡単な自作言語のコンパイラをいろんな言語で書いてみるシリーズ 26番目の言語は Elixir です。

できたもの

サイズ

  $ wc -l *.ex lib/utils.ex
  445 mrcl_codegen.ex
   17 mrcl_compiler.ex
  132 mrcl_lexer.ex
  392 mrcl_parser.ex
   47 lib/utils.ex
 1033 合計

動作例

  $ echo '
  func add(a, b) {
    return a + b;
  }

  func main() {
    call add(1, 2);
  }
' | ./run.sh lex | ./run.sh parse | ./run.sh codegen

  # ↓ アセンブリが出力される

  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版）の説明用テンプレ＞

自分がコンパイラ実装に入門するために作った素朴なトイ言語 Mini Ruccola とその処理系です。簡単に概要を書くと下記のような感じ。

• 小規模: コンパイラ部分は 1,000 行程度
  • 無理して短く書くようなことはせず、読みやすさ優先で素直に書いてこのくらい
• pure Ruby
  • 標準ライブラリ以外のライブラリ不要。ブラックボックスなしですべてを掌握できるように。
• x86風の自作VM向けにコンパイルする
• ライフゲームのために必要な機能だけ
  • 変数宣言、代入、反復、条件分岐、関数
  • 演算子
    • +, *, ==, != のみ
    • 左結合（優先順位は ( ) で明示）
  • 型なし（値は符号付き整数のみ） ... B言語や BCPL に似てる？
• 作ったときに書いた備忘記事
  • RubyでオレオレVMとアセンブラとコード生成器を2週間で作ってライフゲームを動かした話
  • Rubyでかんたんな自作言語のコンパイラを作った
• 本体には含めていない後付けの機能など
  • 真偽値リテラル / break / if/else / 単項マイナス / パーサの別実装 / 静的型検査 / etc.
• セルフホスト版
  • 育てていってセルフホストまでできました
• 他言語への移植
  • コンパイラ部分のみ
  • Python, Java, PHP, TypeScript, Julia, Dart, OCaml, Haskell, Rust, Zig, V, Forth など、2023-12-10 の時点では 26言語
• 作り方は製作過程のメモに全部書いています。
  • この通りにやれば誰でも同じものが作れる、と言いたいところだけどいろいろ改善点が見えてきたので全体的に改訂したい……
  • 凝ったことはしていないので Ruby を知らない人でも雰囲気くらいは分かるんじゃないかと。

＜説明用テンプレおわり＞

メモ

Elixir に入門したての人がむりやり書いたという感じでこなれてないと思いますが、とにかく動いてはいます。

見た目は Ruby に似ているものの、パターンマッチが強力だったりして書き味は OCaml とか Haskell とかに近いと感じました。ただ、慣れすぎていて普段はあまり意識しませんが Ruby も Lisp の影響を受けているので「見た目だけ Ruby っぽいけど中身は全然違う」ともちょっと違うかなと。

素朴なコンパイラなので並行処理の出番はなく、ここに関しては「Elixir ならでは」なところには触れられませんでしたね。

• （Ruby に慣れているので）def ... do ... とか if ... do ... の do を書き忘れがち
• せっかくなので |> をもっと使ってみたかったけど、不慣れなためあまり使わずになんとかしてしまった。書き直せるところが結構ありそう。
• （今回書いた範囲では）型を強く意識しないと書けない、という感じではなかった
• 今回は Mix は使わず。 elixirc コマンドでコンパイルして elixir コマンドで実行するだけ。
• 今回はミュータブルな機能は使わず。OCaml, Haskell のときとだいたい同じ。

この記事を読んだ人は（ひょっとしたら）こちらも読んでいます