Qiita に書きました。
V言語でかんたんな自作言語のコンパイラを書いた
かんたんな自作言語のコンパイラをいろんな言語で書いてみるシリーズ 24番目の言語は V(V言語、vlang) です。
V を触り始めて1週間くらいの人が、理解は後回しにしてとにかく動くものを作るぞ、という方向性で書いたもの(そのくらいのノリで気軽に書けるコンパイラです)。
V のバージョンは 0.3.3(weekly.2023.14)。
できたもの
動かし方の例
$ echo ' func add(a, b) { return a + b; } func main() { call add(1, 2); } ' | bin/mrcl_lexer | bin/mrcl_parser | bin/mrcl_codegen # ↓アセンブリが出力される call main exit label add push bp cp sp bp cp [bp:2] reg_a push reg_a cp [bp:3] reg_a push reg_a pop reg_b pop reg_a add_ab cp bp sp pop bp ret label main push bp cp sp bp cp 2 reg_a push reg_a cp 1 reg_a push reg_a _cmt call~~add call add add_sp 2 cp bp sp pop bp ret (snip)
移植元
<自作言語処理系(Ruby版)の説明用テンプレ>
自分がコンパイラ実装に入門するために作った素朴なトイ言語 mini-ruccola とその処理系です。簡単に概要を書くと下記のような感じ。
- コンパクト: コンパイラ部分は 1,000 行程度
- 無理して短く書くようなことはせず、読みやすさ優先で素直に書いてこのくらい
- pure Ruby
- 標準ライブラリ以外のライブラリ不要。すべてを掌握できるように。
- x86風の自作VM向けにコンパイルする
- ライフゲームのために必要な機能だけ
- 変数の宣言・代入、反復、条件分岐、関数の定義・呼び出し
- 演算子:
+
,*
,==
,!=
のみ(優先順位は(
)
で明示) - 型なし(値は符号付き整数のみ) ... B言語や BCPL に似てる?
- 作ったときに書いた備忘記事
- 本体には含めていない後付けの機能など
- 真偽値リテラル / break / if/else / 単項マイナス / Racc などを使って書いたパーサの別実装 / etc.
- セルフホスト版
- さらに育てていくとセルフホストまでできます
- 作ったときの全過程を製作メモに書いています
- この通りにやれば誰でも作れる、と言いたいところだけどいろいろ改善点が見えてきたので全体的に改訂したい……
- 凝ったことはしていないので Ruby を知らない人でも雰囲気くらいは分かるんじゃないかと
<説明用テンプレおわり>
メモ
- 実質3, 4日くらいで移植完了
- ひっかかるところがほとんどなくて書くことがあまりない
- 参考にしたのはほぼこの2つのみ
- V Documentation
- ここを眺めれば基本的なところはだいたい分かる
- vlang リポジトリの vlib/ 以下
- 検索して使用例を見る
- V Documentation
- Go に似てる
- "V is very similar to Go. If you know Go, you already know ≈80% of V." (https://vlang.io/)と書かれている通り
- Go をよく知らないので詳しいことは書けませんが、見た目はたしかに似ていて、多値が返せたりする
- print が便利
- 構造体を print に渡すと中身を表示してくれる
- 文字列リテラルへの埋め込み
'...${x}...'
- mut にすれば
<<
で配列の末尾に要素を追加できる- ここだけ見た目がちょっと Ruby っぽい
- 今後 V言語を使う機会があったら今回作ったものから部品取りできる
この記事を読んだ人は(ひょっとしたら)こちらも読んでいます
Forth(Gforth)でかんたんな自作言語のコンパイラを書いた
Qiita に書きました。
DockerでLibreOffice Basicマクロを実行する(2022年版)
Qiita に書きました。
Ruccola VM Crystal版の速度改善 (2022-08)
fastvm/rclvm.cr の高速化の自分用メモ。
- オペコードを String のまま取り回す実装だった → これをシンボルや enum にするとどうなるか
def execute : Int32 | Nil insn = @mem.main[@pc] opcode = insn[0] case opcode when "exit" then return insn[1].as(Int32) when "cp" then cp() ; @pc += 1 when "lea" then lea() ; @pc += 1 when "add_ab" then add_ab() ; @pc += 1 # ...
修正前はこうなっていて、文字列比較してるとこで遅くなってそう。
- 使っている Crystal のバージョンが 1.0.0 のままだった → これを最新の 1.5.0 に上げるとどうなるか
計測
変更前 real 1m34.613s / user 1m44.672s / sys 0m2.679s real 1m34.598s / user 1m44.409s / sys 0m2.869s real 1m34.340s / user 1m44.597s / sys 0m2.555s opcode をシンボルに変更しただけ real 1m29.133s / user 1m36.528s / sys 0m2.152s real 1m28.814s / user 1m36.282s / sys 0m2.106s real 1m29.255s / user 1m36.347s / sys 0m2.400s opcode を enum に変更しただけ real 1m28.696s / user 1m35.704s / sys 0m2.447s real 1m29.589s / user 1m36.684s / sys 0m2.367s real 1m28.533s / user 1m35.828s / sys 0m2.244s Crystal のバージョン変更だけ(1.0.0 => 1.5.0) real 1m13.030s / user 1m21.938s / sys 0m2.984s real 1m12.881s / user 1m21.927s / sys 0m2.772s real 1m12.474s / user 1m21.444s / sys 0m2.840s Crystal 1.5.0 + enum real 1m8.694s / user 1m16.653s / sys 0m2.906s real 1m8.094s / user 1m15.968s / sys 0m2.952s real 1m8.741s / user 1m16.860s / sys 0m2.683s
メモ
- v1.5.0 に上げただけでけっこう速くなる
- 処理時間は 23% 減、速度は 1.30倍
- バージョンアップの寄与の方が大きいが、シンボル化・enum化でも多少速くなる
- 速度向上の優先度
- そんなに高くない。あまりがんばらずに速くできるならやってしまおうか、くらいの温度感。
- 可読性・保守性を損なわない方を優先
Crystal では String#to_sym
は使えないが、
オペコードの種類は限られているので自前で変換してやれば String からシンボルへの変換は可能。
opcode = case opcode_str when "exit" then :exit when "cp" then :cp when "lea" then :lea when "add_ab" then :add_ab # ... snip ... else raise # 不正なオペコード end
……という方法を思いついてないせいでシンボル化できないと思っていたか、 面倒そうなので後回しにしていたか(忘れたけどたぶん前者)。
シンボル (Symbol) - Crystal
https://ja.crystal-lang.org/reference/syntax_and_semantics/literals/symbol.html
シンボルはコンパイル時に解釈されるもので、動的に生成することはできません。シンボルを生成する唯一の方法はシンボルリテラルを使うことです。
- シンボルと enum どちらを使うか
- せっかく Crystal を使っているので、この場合は enum でいいんじゃないかなと
- 煩雑さはシンボルを使う場合でもあまり変わらない
(
String#to_sym
が使えないので)
列挙型 (Enum) - Crystal
https://ja.crystal-lang.org/reference/syntax_and_semantics/enum.html
最終的に Crystal 1.5.0 + enum 化によって
- 処理時間は 27.5% 減
- 速度は 1.38倍
になった。
コミット:
vm2gol v2 (63) sub_sp 命令を廃止 / panic
sub_sp 命令を廃止
VM命令 sub_sp
を廃止しました。
オペランドを負の値にすれば add_sp
で代用できるので。
これで VM のコードが5行減って、実装の量の面でも、仕様の面でも、またちょっとコンパクトになりました。
VM命令がいっぱいあると、入門者視点では「えー、こんなにいっぱい覚えないといけないの……」となりそうなので、少ない数で済ませられるならその方がいいかなと。
ちなみに sub_sp
を使っているのは変数宣言のときだけ。
--- a/vgcodegen.rb +++ b/vgcodegen.rb @@ -290,7 +290,7 @@ def gen_stmts(fn_arg_names, lvar_names, stmts) end def gen_var(fn_arg_names, lvar_names, stmt) - puts " sub_sp 1" + puts " add_sp -1" if stmt.size == 3 _, dest, expr = stmt
panic
たとえばコンパイラが完成するまでのこういう状態だったら、
# 例: vgcodegen.rb: _gen_expr_binary case operator when "+" then _gen_expr_add() else raise not_yet_impl("operator", operator) end
"not yet implemented" というメッセージも間違いではありませんでした。
まだ +
演算子しか実装していないが、これから *
や ==
などの場合の処理も実装していく予定である、という表明になっています(そのつもり)。
しかし、今は完成してだいぶ落ち着いている状況であり、 新たな演算子を追加する予定は今のところありません。
case operator when "+" then _gen_expr_add() when "*" then _gen_expr_mult() when "==" then _gen_expr_eq() when "!=" then _gen_expr_neq() else raise not_yet_impl("operator", operator) end
こうなってくると、 "not yet implemented" というメッセージと実装者(私)の意図とのずれが気になってきます。
というわけで、 not_yet_impl
を使っていた箇所は一律で panic
に置き換えました。
あわせて、パーサで使っていた ParseError
クラスをなくしました。
その他
rbenv local 2.7.6
sub_sp
をなくしたのでサイズはちょっと減りました。
$ wc -l vg*.rb common.rb 66 vgasm.rb 375 vgcodegen.rb 57 vglexer.rb 368 vgparser.rb 442 vgvm.rb 52 common.rb 1360 合計 # コメントを除いたサイズ: $ cat vg*.rb common.rb | grep -v '^ *#' | wc -l 1324