Qiita に書きました。
vm2gol v2 (56) VRAMの読み書きを組み込み関数化
- 目次ページに戻る / 前 / 次
- 前回からの差分をまとめて見る
VRAM の読み書きは、配列アクセスのような見た目で書けるようにしていました。
set vram[0] = 1; set vram_value = vram[0];
これをどうコンパイルしていたか。
レキサでは vram[0]
をまるごと1つのトークン、1つの識別子として切り出していました。
まじめにやるなら vram
, [
, 0
, ]
のように4つのトークンに分けるところだと思うんですが、それを1つのトークンにまとめていてちょっとズルい雰囲気がありますね。最初はどうやればよいか分かっていなくて手探りでしたし、簡単に済ませるためにこれはこれで良かったとは思いますが。
後段のコード生成処理では識別子が vram[...]
のパターンになっているか判別して、
マッチしていたら ...
の部分を取り出し、
その部分がローカル変数だったら……というややこしいことをしていました。
VRAM まわりだけ例外扱いになっていて、それで実装が無駄に膨らんでいて野暮ったい。
移植するときもコード生成器の VRAM まわりの部分書くのめんどくさいんですよね。
というわけで今回 vram[...]
記法をまともにサポートする……のではなく、 vram[...]
記法を廃止し、組み込み関数にしてしまいました。
上記の例でいうと次のように書き方が変わります。
call set_vram(0, 1); call_set vram_value = get_vram(0);
変更後のコードで呼び出している get_vram
, set_vram
という関数はどこにあるのか?
これはコード生成時に固定のコードを出力して、それを呼び出すようにしています。
def codegen_builtin_set_vram puts "" puts "label set_vram" puts " push bp" puts " cp sp bp" puts " set_vram [bp:2] [bp:3]" # vram_addr value puts " cp bp sp" puts " pop bp" puts " ret" end def codegen_builtin_get_vram puts "" puts "label get_vram" puts " push bp" puts " cp sp bp" puts " get_vram [bp:2] reg_a" # vram_addr dest puts " cp bp sp" puts " pop bp" puts " ret" end def codegen(tree) puts " call main" puts " exit" head, *top_stmts = tree codegen_top_stmts(top_stmts) codegen_builtin_set_vram() codegen_builtin_get_vram() end
呼び出し規約に従ってさえいれば、アセンブリで書かれていても呼び出し側からは普通の関数と同じインターフェイスで使えるので、これでいいわけですね。
先行して v3 で試してみて、悪くなかったので v2 にフィードバックしました。
たとえばC言語なんかで普通にプログラムを作る場合、標準ライブラリが別のオブジェクトファイルとして存在していて、自分の書いたプログラム(のオブジェクトファイル)とリンカでくっつける……みたいな流れですよね。たしか。
それを踏まえて「標準ライブラリの処理をどこに記述し、どこで自分の作ったプログラムとくっつけるか」という視点で考えてみると、 今回の修正では標準ライブラリが(アセンブリコードの形で)コード生成器の中に埋め込まれ、コード生成器が(アセンブリコードを結合することで)リンク相当の処理をする形になったわけですね。 ふむ……。
リンカごっこもそのうちやってみたい。
VRAM のアクセスも通常の関数を処理するルートに乗せたことで 特別扱いしていた部分をなくすことができました。
--- a/vglexer.rb +++ b/vglexer.rb @@ -33,7 +33,7 @@ def tokenize(src) str = $1 tokens << Token.new(:sym, str) pos += str.size - when /\A([a-z_][a-z0-9_\[\]]*)/ + when /\A([a-z_][a-z0-9_]*)/ str = $1 tokens << Token.new(:ident, str) pos += str.size
--- a/vgcg.rb +++ b/vgcg.rb @@ -204,15 +204,6 @@ def codegen_expr(fn_arg_names, lvar_names, expr) when lvar_names.include?(expr) cp_src = to_lvar_addr(lvar_names, expr) puts " cp #{cp_src} reg_a" - when _match_vram_ref(expr) - var_name = _match_vram_ref(expr) - case - when lvar_names.include?(var_name) - vram_addr = to_lvar_addr(lvar_names, var_name) - puts " get_vram #{vram_addr} reg_a" - else - raise not_yet_impl("rest", rest) - end else raise not_yet_impl("expr", expr) end @@ -245,20 +236,6 @@ def codegen_call_set(fn_arg_names, lvar_names, stmt_rest) puts " cp reg_a #{lvar_addr}" end -def _match_vram_addr(str) - md = /^vram\[(\d+)\]$/.match(str) - return nil if md.nil? - - md[1] -end - -def _match_vram_ref(str) - md = /^vram\[([a-z_][a-z0-9_]*)\]$/.match(str) - return nil if md.nil? - - md[1] -end - def codegen_set(fn_arg_names, lvar_names, rest) dest = rest[0] expr = rest[1] @@ -267,18 +244,6 @@ def codegen_set(fn_arg_names, lvar_names, rest) src_val = "reg_a" case - when _match_vram_addr(dest) - vram_addr = _match_vram_addr(dest) - puts " set_vram #{vram_addr} #{src_val}" - when _match_vram_ref(dest) - vram_addr = _match_vram_ref(dest) - case - when lvar_names.include?(vram_addr) - lvar_addr = to_lvar_addr(lvar_names, vram_addr) - puts " set_vram #{lvar_addr} #{src_val}" - else - raise not_yet_impl("dest", dest) - end when lvar_names.include?(dest) lvar_addr = to_lvar_addr(lvar_names, dest) puts " cp #{src_val} #{lvar_addr}"
だいぶさっぱりしました。
その他
- 細かいリファクタリング、リネームなど
hive-modoki: かんたんな Apache Hive のクローンを作っていた話
2021-06-08 追記
Hive を使うお仕事から離れることになったため、 hive-modoki は開発中止となりました。 転職先が見つかるとかで開発終わるパターンは織り込み済で、半分は作る事自体が目的ということにして保険かけてたので、まあ、大丈夫。
パーサやクエリエンジン部分は何か別の所で再利用できるといいですね。
概要
- Apache Hive のしょぼいクローン
動機
- Hive テスト 自動化 メモ
にいろいろ書いたように工夫はしていたが、それでも限界がある
- 結局 Hive が遅いのがボトルネック
- 遅いのをなんとかしたい
方針
- 用途をプロトタイピング、開発中の検証、自動テストに限定する
- 完全なクローンである必要はない
- サイズの大きなデータを扱う必要はない。 小さなデータだけを想定する。
- ひとまず非公開
- ひとまず自分用
- 人に読まれる前提で書かないといけないとなると、やはり追加のコストがばかにならないので……
- 自分が必要な機能だけを作る
- 公開については自分で使えるようになってから考える
- 汚くてよい
- ある程度機能の揃った RDB を作るのは今回が初めてなので、どうせ大したものは作れない。初回から良いものを作るのは無理。
- と思うことにしてハードルを下げる
- 1年後にきれいなものができるより1ヶ月後に動くものが使える方が嬉しい。minimum viable product を目指す。
- 個人が仕事以外の時間で作るものなので大したリソースは捻出できない。その範囲でなんとかする。
- 仕事でこんなの書いたらどやされる、という感じの出来上がりになっております
- ある程度機能の揃った RDB を作るのは今回が初めてなので、どうせ大したものは作れない。初回から良いものを作るのは無理。
- UDF をそのまま動かすのは大変そうなので簡易に済ます。ここは諦める。
手間をかけずに済ませたいので、自分が慣れているもの、枯れているものを使う方向で。
- HiveQLパーサ
- エンジン
- Java
- ASTを受け取って実行
- 素朴に木の末端から evaluate していく方式で今のところ何とかなっている
- HDFS
- HDFS の代わりにローカルのファイルシステムを使う
- ファイルのフォーマット: array table
メモ
↓ここらへんを先にやっておいてよかった、というか、やってなかったらそもそも Hive のクローンを作ろうと考えなかったと思います。
TODO
まず各機能の最低限の部分を作り、後から必要な部分を肉付けしていく感じで。
select
- [v] select ... from ...
- [v] order by
- [v] where
- [v] join
- [v] left outer, inner
- expression
- [v] 関数呼び出し
- [v] case
- [v] group by
- [v] サブクエリ
- [v] union all
- [v] CTE(with句)
- [v] cast
- [v] from句なしの select
- builtin functions
- [v] coalesce
- [v] array / named_struct
- [v] date_format / unix_timestamp / from_unixtime
- window functions
- [v] row_number
- [v] UDF
- [v] macro
- 演算子
- [v] between
型
- [v] int / tinyint / bigint / smallint
- [△] decimal
- [v] string
- [v] bool
- [v] timestamp
- [v] array / struct
その他
- [v] create table
- [v] insert
- [v] insert ... values ...
- [v] select + insert
- [v] dynamic patition
- [v] use
- [v] show tables / show databases
- alter table
- [] drop partition
- [v] CLI interface / 対話的実行
- [v] スプレッドシート(fods ファイル)の内容をロード
- [v] JsonSerDe(ロードのみ)
関連
↓これらを先にやっておいたのがよかった。これらをやっていなかったら、そもそも自分で作れるかもと考えなかったはず。
進捗
2021
3/11 from句なしの select
3/13 macro / timestamp
3/25 対話的実行
4/10 array / struct
4/22 CTE + select + insert
4/24
array, struct の型まわりのハリボテだった部分を実装。 JSON のパースに Gson を使っていて int が double としてパースされていたのが、 型の情報を見て int に変換できるようになった。
select t1.id, t2.id from t1 inner join t2 on t2.id = t1.xs[0].a
のような array/struct の値を使った join もできるようになってる。
4/25
- 組み込み関数を追加:
coalesce
- use: DB が存在しない場合はエラーにする
- create table の際にディレクトリも作成
- Print
(#{num_rows} rows)
(beeline-modoki) select 'fdsa' as foo;
- 二項演算子を追加:
<>
,-
4/26
- funcall を expr に含める
- create database if not exists ...
- insert: カラム数の一致をチェック
- insert ... values で null を書けるようにした
- feat: binary op
*
- feat: unary op:
-
,is not null
- add jar (haribote)
4/27
- feat: binary op:
<
,<=
,>
,>=
- feat: builtin functions: array, named_struct
- feat: dynamic partition (select + insert)
4/28
- スプレッドシート(fods ファイル)の内容をロード
- これを使うだけなので簡単: JRubyでLibreOffice Calcのfodsファイルを読み書きするサンプル 2021
4/29
- feat: between
4/30
- feat: JsonSerDe(ロードのみ)
- feat: smallint
5/1
- fodsファイルからデータを抽出
- → JsonSerDe で一時テーブルにロード
- → select+insert(+dynamic patition) で目的テーブルに移し替え
が通して動くようになった。
5/2
- create文の stored as / location / tblproperties のパース
- とりあえずパースだけ。まだ使っていない。
- create temporary function ... のパース
- 同じくパースだけ
- クエリの実行に失敗したら AST をファイルにダンプして、 JUnit のテストからそのファイルを読んで実行できるようにしてみた。 失敗したときにすぐに IDE のデバッガで調べられて便利。
5/16
- tinyint と int を比較するときの暗黙の型変換とか、単項演算子
-
がまだだったとか、細かいところをちまちまと実装
vm2gol v2 (55) VM命令 set_reg_a, set_reg_b の廃止など
- 目次ページに戻る / 前 / 次
- 前回からの差分をまとめて見る
VM命令 set_reg_a, set_reg_b の廃止
cp
命令で書き換えられるため不要になっています。
「set_reg_a
, set_reg_b
を使って書いた方が意図も明確で可読性も高い」みたいなメリットも大してないので、廃止しました。
書き換えの例:
- set_reg_a 42 + cp 42 reg_a
一番最初の頃に追加した命令なので、名残惜しい感じがしなくもないですけどね……。
codegen_call_set() で codegen_call() を流用
移植していたときにコードの重複に気付きつつも後回しにしていた部分。
codegen_call_set()
から codegen_call()
を呼び出す形にしました。
--- a/vgcg.rb +++ b/vgcg.rb @@ -249,21 +249,10 @@ def codegen_call(fn_arg_names, lvar_names, stmt_rest) puts " add_sp #{fn_args.size}" end -# TODO codegen_call を流用できそう def codegen_call_set(fn_arg_names, lvar_names, stmt_rest) lvar_name, fn_temp = stmt_rest - fn_name, *fn_args = fn_temp - fn_args.reverse.each do |fn_arg| - codegen_expr( - fn_arg_names, lvar_names, fn_arg - ) - puts " push reg_a" - end - - codegen_vm_comment("call_set #{fn_name}") - puts " call #{fn_name}" - puts " add_sp #{fn_args.size}" + codegen_call(fn_arg_names, lvar_names, fn_temp) lvar_addr = to_lvar_addr(lvar_names, lvar_name) puts " cp reg_a #{lvar_addr}"
その他の修正
- コメントの整理・フォーマット・変数名リネーム
- テスト失敗時に diff が大量に出る問題への対策
- Rubocop まわりのメンテナンス(放置気味)
命令廃止とフォーマット修正が効いて 84行減り、1500行を切りました。 よしよし。
$ wc -l common.rb vg*.rb 41 common.rb 63 vgasm.rb 398 vgcg.rb 58 vglexer.rb 454 vgparser.rb 449 vgvm.rb 1463 合計
vm2gol v2 (54) コード生成器の冗長すぎる部分を整理
- 目次ページに戻る / 前 / 次
- 前回からの差分をまとめて見る
気にはなっていたけど後回しにしていたアレです。
今 v3 を作っているのですが、たしか 関数呼び出しの引数や return文で任意の式を書きたくなったとかで いじっていて、コード生成器の冗長すぎる箇所をうまいこと整理できると分かりました。
良さそうだったので v2 にもフィードバックしておきます。
rename: codegen_expr() => _codegen_expr_binary()
codegen_expr() で行っているのは現状では 二項演算のみなので、名前と処理内容が乖離しています。 まずはこの乖離を解消しました。
diff は省略して変更後の _codegen_expr_binary() を貼っておきます。
def _codegen_expr_binary(fn_arg_names, lvar_names, expr) operator, *args = expr arg_l = args[0] arg_r = args[1] _codegen_expr_push(fn_arg_names, lvar_names, arg_l) _codegen_expr_push(fn_arg_names, lvar_names, arg_r) case operator when "+" _codegen_expr_add() when "*" _codegen_expr_mult() when "eq" _codegen_expr_eq() when "neq" _codegen_expr_neq() else raise not_yet_impl("operator", operator) end end
reg_a への転送とスタックへの push を分離(_codegen_expr_push)
_codegen_expr_push()
というメソッドがあります。
さっきリネームした _codegen_expr_binary()
から呼び出されていて、
二項演算を行う前に引数を評価して結果をスタックに push する、ということをやっています。
呼び出し元はこう:
def _codegen_expr_binary(...) # ... _codegen_expr_push(fn_arg_names, lvar_names, arg_l) _codegen_expr_push(fn_arg_names, lvar_names, arg_r)
_codegen_expr_push()
では結果を reg_a
に転送するところまでで止めて、
スタックへ push するのは呼び出し側で行うようにします。
呼び出し側がこうなるように:
def _codegen_expr_binary(...) # ... _codegen_expr_push(fn_arg_names, lvar_names, arg_l) puts " push reg_a" _codegen_expr_push(fn_arg_names, lvar_names, arg_r) puts " push reg_a"
--- a/vgcg.rb +++ b/vgcg.rb @@ -117,27 +117,25 @@ def codegen_while(fn_arg_names, lvar_names, rest) end def _codegen_expr_push(fn_arg_names, lvar_names, val) - push_arg = case val when Integer - val + puts " cp #{val} reg_a" when String case when fn_arg_names.include?(val) - to_fn_arg_addr(fn_arg_names, val) + cp_src = to_fn_arg_addr(fn_arg_names, val) + puts " cp #{cp_src} reg_a" when lvar_names.include?(val) - to_lvar_addr(lvar_names, val) + cp_src = to_lvar_addr(lvar_names, val) + puts " cp #{cp_src} reg_a" else raise not_yet_impl("val", val) end when Array _codegen_expr_binary(fn_arg_names, lvar_names, val) #=> 結果が reg_a に入る - "reg_a" else raise not_yet_impl("val", val) end - - puts " push #{push_arg}" end def _codegen_expr_add
出力されるアセンブリコードが次のように変化します。 1命令だったところが2命令に増えて非効率になりますが、命令実行後の結果は変わりませんし、 コード生成処理がより良くなる方が嬉しいので気にせずやってしまいます。
- push [bp+3] + cp [bp+3] reg_a + push reg_a
あらためて codegen_expr() を作成
def codegen_expr(fn_arg_names, lvar_names, expr) case expr when Integer puts " cp #{expr} reg_a" when String case when fn_arg_names.include?(expr) cp_src = to_fn_arg_addr(fn_arg_names, expr) puts " cp #{cp_src} reg_a" when lvar_names.include?(expr) cp_src = to_lvar_addr(lvar_names, expr) puts " cp #{cp_src} reg_a" else raise not_yet_impl("expr", expr) end when Array _codegen_expr_binary(fn_arg_names, lvar_names, expr) else raise not_yet_impl("expr", expr) end end
修正前は codegen_expr() が二項演算しか受け付けていなかったのが、 それに加えて、整数、関数の引数、ローカル変数も式として扱うようになりました。
たとえば
while ({式}) { // ... }
という文があったとして、これまでは {式}
の部分に x == 1
のような二項演算しか書けないようになっていたのが、次のような文が書けるようになるイメージです。
while (1) { ... } // 整数 while (is_foo) { ... } // 関数の引数・ローカル変数
では codegen_expr() を使って置き換えていきます。
_codegen_expr_push()
まずは _codegen_expr_push() が置き換えられます。 あらためて見ても分かるように、この段階では codegen_expr() とまったく同じ内容になっているので、置き換えて OK。
--- a/vgcg.rb +++ b/vgcg.rb @@ -116,28 +116,6 @@ def codegen_while(fn_arg_names, lvar_names, rest) puts "" end -def _codegen_expr_push(fn_arg_names, lvar_names, val) - case val - when Integer - puts " cp #{val} reg_a" - when String - case - when fn_arg_names.include?(val) - cp_src = to_fn_arg_addr(fn_arg_names, val) - puts " cp #{cp_src} reg_a" - when lvar_names.include?(val) - cp_src = to_lvar_addr(lvar_names, val) - puts " cp #{cp_src} reg_a" - else - raise not_yet_impl("val", val) - end - when Array - _codegen_expr_binary(fn_arg_names, lvar_names, val) - else - raise not_yet_impl("val", val) - end -end - def _codegen_expr_add puts " pop reg_b" puts " pop reg_a" @@ -206,9 +184,9 @@ def _codegen_expr_binary(fn_arg_names, lvar_names, expr) arg_l = args[0] arg_r = args[1] - _codegen_expr_push(fn_arg_names, lvar_names, arg_l) + codegen_expr(fn_arg_names, lvar_names, arg_l) puts " push reg_a" - _codegen_expr_push(fn_arg_names, lvar_names, arg_r) + codegen_expr(fn_arg_names, lvar_names, arg_r) puts " push reg_a" case operator
_codegen_expr_push() はこの2箇所でしか使われていないため、用済みになりました。
_codegen_call_push_fn_arg() を置き換え
_codegen_expr_push() と同じ要領で。
--- a/vgcg.rb +++ b/vgcg.rb @@ -225,34 +225,14 @@ def codegen_expr(fn_arg_names, lvar_names, expr) end end -def _codegen_call_push_fn_arg(fn_arg_names, lvar_names, fn_arg) - push_arg = - case fn_arg - when Integer - fn_arg - when String - case - when fn_arg_names.include?(fn_arg) - to_fn_arg_addr(fn_arg_names, fn_arg) - when lvar_names.include?(fn_arg) - to_lvar_addr(lvar_names, fn_arg) - else - raise not_yet_impl(fn_arg) - end - else - raise not_yet_impl(fn_arg) - end - - puts " push #{push_arg}" -end - def codegen_call(fn_arg_names, lvar_names, stmt_rest) fn_name, *fn_args = stmt_rest fn_args.reverse.each do |fn_arg| - _codegen_call_push_fn_arg( + codegen_expr( fn_arg_names, lvar_names, fn_arg ) + puts " push reg_a" end codegen_vm_comment("call #{fn_name}") @@ -265,9 +245,10 @@ def codegen_call_set(fn_arg_names, lvar_names, stmt_rest) fn_name, *fn_args = fn_temp fn_args.reverse.each do |fn_arg| - _codegen_call_push_fn_arg( + codegen_expr( fn_arg_names, lvar_names, fn_arg ) + puts " push reg_a" end codegen_vm_comment("call_set #{fn_name}")
_codegen_call_push_fn_arg() は codegen_expr() と完全に同じではないため、 この修正によって、関数呼び出しの引数に二項演算を置けるようになります。
修正前: call foo_func(1 + 2); //=> コンパイルエラー 修正後: call foo_func(1 + 2); //=> コンパイルエラーにならない
挙動が変わってしまいますが、この変化は特に問題ないですし、記述力が高まるのでよしとします。
codegen_set() のセットする値のコード生成処理の部分
他にも置き換えられる箇所がないかと見ていきます。 codegen_set() でセットする値のコード生成を行っている部分も置き換えられそう。
var x = vram[{ローカル変数}];
のような文を書けるようにするために
codegen_set() には vram[{ローカル変数}]
の部分のコード生成処理があるのですが、
今の codegn_expr() ではこれはできません。
というわけで codegen_expr() で vram[{ローカル変数}]
も扱えるようにします。
一応問題ないか具体例で考えてみましょうか。
// 二項演算の左右の項に vram[{ローカル変数}] が来ても問題ないか? // ... 問題なさそう while (vram[vi] == x) { ... } // 関数の引数でも問題ないか? // ... 問題なさそう call foo_func(vram[vi] + 1);
たぶん大丈夫。
まずは codegen_expr() で
vram[{ローカル変数}]
も扱えるようにします。
codegen_set() からコピペして codegen_expr() を修正し、 codegen_set() からは codegen_expr() を呼び出すように修正。
--- a/vgcg.rb +++ b/vgcg.rb @@ -215,6 +215,15 @@ def codegen_expr(fn_arg_names, lvar_names, expr) when lvar_names.include?(expr) cp_src = to_lvar_addr(lvar_names, expr) puts " cp #{cp_src} reg_a" + when _match_vram_ref(expr) + var_name = _match_vram_ref(expr) + case + when lvar_names.include?(var_name) + vram_addr = to_lvar_addr(lvar_names, var_name) + puts " get_vram #{vram_addr} reg_a" + else + raise not_yet_impl("rest", rest) + end else raise not_yet_impl("expr", expr) end @@ -277,39 +286,8 @@ def codegen_set(fn_arg_names, lvar_names, rest) dest = rest[0] expr = rest[1] - src_val = - case expr - when Integer - expr - when Array - _codegen_expr_binary(fn_arg_names, lvar_names, expr) - "reg_a" - when String - case - when fn_arg_names.include?(expr) - to_fn_arg_addr(fn_arg_names, expr) - when lvar_names.include?(expr) - to_lvar_addr(lvar_names, expr) - when _match_vram_addr(expr) - vram_addr = _match_vram_addr(expr) - puts " get_vram #{vram_addr} reg_a" - "reg_a" - when _match_vram_ref(expr) - var_name = _match_vram_ref(expr) - case - when lvar_names.include?(var_name) - lvar_addr = to_lvar_addr(lvar_names, var_name) - puts " get_vram #{ lvar_addr } reg_a" - else - raise not_yet_impl("rest", rest) - end - "reg_a" - else - raise not_yet_impl("rest", rest) - end - else - raise not_yet_impl("set src_val", rest) - end + codegen_expr(fn_arg_names, lvar_names, expr) + src_val = "reg_a" case when _match_vram_addr(dest)
codegen_set() の鬱陶しかった部分がすっきり!
reg_a
への値のセットと push reg_a
が分かれる都合で VM の修正も必要でした。
set_vram {VRAMのアドレス} reg_a
のパターンです。
--- a/vgvm.rb +++ b/vgvm.rb @@ -448,6 +448,8 @@ class Vm case arg2 when Integer arg2 + when "reg_a" + @reg_a when /^ind:/ stack_addr = calc_indirect_addr(arg2) @mem.stack[stack_addr]
codegen_return()
あとは codegen_return() も置き換えられます。 なんかパズルみたいで楽しい。
--- a/vgcg.rb +++ b/vgcg.rb @@ -312,30 +312,7 @@ end def codegen_return(lvar_names, stmt_rest) retval = stmt_rest[0] - - case retval - when Integer - puts " cp #{retval} reg_a" - when String - case - when _match_vram_ref(retval) - var_name = _match_vram_ref(retval) - case - when lvar_names.include?(var_name) - lvar_addr = to_lvar_addr(lvar_names, var_name) - puts " get_vram #{lvar_addr} reg_a" - else - raise not_yet_impl("retval", retval) - end - when lvar_names.include?(retval) - lvar_addr = to_lvar_addr(lvar_names, retval) - puts " cp #{lvar_addr} reg_a" - else - raise not_yet_impl("retval", retval) - end - else - raise not_yet_impl("retval", retval) - end + codegen_expr([], lvar_names, retval); end def codegen_vm_comment(comment)
これもすっきり。うーむ、もっと早くやってればよかった……。
while, case の条件式
while (ここ) { ... } case { (ここ) { ... } }
これらは現状では二項演算のみ受け付けるようになっていますが、 ここもついでに codegen_expr() に置き換えてしまいます。
while (do_break) { ... }
みたいなことができると嬉しいと思いますし、 二項演算だけに限定する理由もあんまりないと思いますし。
--- a/vgcg.rb +++ b/vgcg.rb @@ -48,7 +48,7 @@ def codegen_case(fn_arg_names, lvar_names, when_blocks) when "eq" # 式の結果が reg_a に入る puts " # -->> expr" - _codegen_expr_binary(fn_arg_names, lvar_names, cond) + codegen_expr(fn_arg_names, lvar_names, cond) puts " # <<-- expr" # 式の結果と比較するための値を reg_b に入れる @@ -94,7 +94,7 @@ def codegen_while(fn_arg_names, lvar_names, rest) puts "label #{label_begin}" # 条件の評価 ... 結果が reg_a に入る - _codegen_expr_binary(fn_arg_names, lvar_names, cond_expr) + codegen_expr(fn_arg_names, lvar_names, cond_expr) # 比較対象の値(真)をセット puts " set_reg_b 1" puts " compare"
ここまでの修正により、 _codegen_expr_binary()
の呼び出し元が
codegen_expr()
だけになりました。
codegen_case() の不要な分岐を削除
codegen_expr()
でさまざまな式を統一的に扱えるようになったため、演算子を見て振り分ける処理が不要になりました。
eq
以外をあえてエラーにする理由も特にないですし、行数も減ってすっきりさせられるので削除します。
--- a/vgcg.rb +++ b/vgcg.rb @@ -40,12 +40,9 @@ def codegen_case(fn_arg_names, lvar_names, when_blocks) when_blocks.each do |when_block| when_idx += 1 cond, *rest = when_block - cond_head, *cond_rest = cond puts " # when_#{label_id}_#{when_idx}: #{cond.inspect}" - case cond_head - when "eq" # 式の結果が reg_a に入る puts " # -->> expr" codegen_expr(fn_arg_names, lvar_names, cond) @@ -67,10 +64,6 @@ def codegen_case(fn_arg_names, lvar_names, when_blocks) # 偽の場合ここにジャンプ puts "label #{label_end_when_head}_#{when_idx}" - - else - raise not_yet_impl("cond_head", cond_head) - end end puts "label #{label_end}"
コードの量はどのくらい減ったか
[before] 41 common.rb 65 vgasm.rb 478 vgcg.rb 58 vglexer.rb 454 vgparser.rb 512 vgvm.rb 1608 合計 [after] 64 vgasm.rb 408 vgcg.rb 58 vglexer.rb 454 vgparser.rb 514 vgvm.rb 41 common.rb 1539 合計
70行近く減らせました! 🙌
(まあ、元が冗長すぎたんですけどね)
vm2gol v2 (53) 間接メモリ参照のフォーマットの改良 / alinesへの蓄積をやめる
- 目次ページに戻る / 前 / 次
- 前回からの差分をまとめて見る
間接メモリ参照のフォーマットの改良
機械語での間接メモリ参照はこれまでアセンブリでとまったく同じ
[bp-2]
, [bp+3]
のようなフォーマットにしていて、
VM では /^\[bp-(\d+)\]$/
のような正規表現を使うことで
間接メモリ参照であることを判定したり
bp からの相対位置(displacement)を取り出したりしていました。
しかし、この VM は 一応なんらかの CPU のシミュレータのつもりですから (オレオレのかなりいい加減なものとはいえ……) 、 正規表現とか高級なことはなるべくさせないようにしたい。
そこで今回、以下のようにちょっとだけ機械が読みやすそうな表現に変えました。
(before) [bp-2] [bp+3] (after) ind:bp:-2 ind:bp:3
見ての通りです。 ind は indirection の略。
この変換はアセンブラで行います。
--- a/vgasm.rb +++ b/vgasm.rb @@ -31,6 +31,15 @@ def create_label_addr_map(alines) map end +def to_machine_code_operand(arg) + case arg + when /^\[bp\-(\d+)\]$/ then "ind:bp:-#{$1}" + when /^\[bp\+(\d+)\]$/ then "ind:bp:#{$1}" + when /^-?\d+$/ then arg.to_i + else arg + end +end + src = File.read(ARGV[0]) alines = parse(src) @@ -49,9 +58,7 @@ alines.each do |aline| label_name = rest[0] insn << label_addr_map[label_name] else - insn += rest.map {|arg| - (/^-?\d+$/ =~ arg) ? arg.to_i : arg - } + insn += rest.map {|arg| to_machine_code_operand(arg) } end puts JSON.generate(insn)
影が薄かったアセンブラちゃんの仕事を増やせてよかったですね(?)。
base の部分には bp
しか来ないので決め打ちにしています。
VM 側の修正はこんな感じ:
--- a/vgvm.rb +++ b/vgvm.rb @@ -268,6 +268,20 @@ class Vm DUMP end + def calc_indirect_addr(str) + _, base_str, disp_str = str.split(":") + + base = + case base_str + when "bp" + @bp + else + raise not_yet_impl("base_str", base_str) + end + + base + disp_str.to_i + end + def add_ab @reg_a = @reg_a + @reg_b end @@ -283,11 +297,8 @@ class Vm case val when Integer val - when /^\[bp-(\d+)\]$/ - stack_addr = @bp - $1.to_i - @mem.stack[stack_addr] - when /^\[bp\+(\d+)\]$/ - stack_addr = @bp + $1.to_i + when /^ind:/ + stack_addr = calc_indirect_addr(val) @mem.stack[stack_addr] else raise not_yet_impl("val", val)
先頭だけ見ればよいので ^ind:
と簡素な正規表現で判定できるようになり、
calc_indirect_addr()
でも単に split(":")
で済むようになりました。
また、 displacement の正負も統一的に表現できるようになったこともあり、今回あわせて分岐も減らしています。
case 式の都合に合わせるため正規表現は残していますが、
なくそうと思えばいつでもなくせる状態になってます
(たとえば 〜.start_with?("ind:")
に書き直すとかで)
ので、まあこれでええでしょということにします。
(追記 2021-02-06) アセンブリでのフォーマットも変更
パースがしやすいのと、 数値の正負によって挙動を切り替える煩雑さがなくなってすっきりするため、 機械語と同様にアセンブリでのフォーマットもコロンで区切る形に変えることにしました。
素人の浅知恵かもしれませんが、これではダメだということになったらまたそのとき考えましょう。
(before) [bp-2] [bp+3] (after) [bp:-2] [bp:3]
これにより、機械語への変換処理も次のように簡素に。
# vgasm.rb def to_machine_code_operand(arg) case arg when /^\[(.+)\]$/ then "ind:#{$1}" when /^-?\d+$/ then arg.to_i else arg end end
コード生成の簡素化(alines への蓄積をやめる)
def codegen(tree) - alines = [] - - alines << " call main" - alines << " exit" + puts " call main" + puts " exit" head, *rest = tree # assert head == "stmts" - alines += codegen_top_stmts(rest) + codegen_top_stmts(rest) - - alines end
各メソッドの先頭で配列 alines を用意していた部分と alines を返却していた部分がなくなり、 アセンブリコードを alines に蓄積するのをやめてその場で出力するようにしました。
副作用がない方がテストとかしやすいかなと思って修正前のような書き方をしていたのですが、 コード生成処理に関しては結局メソッド単位のテストは書いていませんし、 その場で出力する方式に変えても特に問題ない ( 第49回 で問題ないようにした ) ので、簡単で分かりやすい書き方に変えることにしました。
移植版の方で何度か試して悪くなさそうだったので Ruby版にフィードバックした形。
その他の修正
rbenv local 2.6.6
- Ruby 3.0 がリリースされたので2つ前のバージョンということで 2.6 に上げました (これまでは 2.5 で作ってました)
- Ruby の警告に従って修正:
IO#lines
=>#each_line
IO#lines is deprecated; use #each_line instead
- vgparser.rb: インデントの修正のみ
- 前回の後始末
- dump_exe.rb を削除
- 第8回 のときに書いたものだが、結局その後ほとんど使わなかったのと、 今回の修正で不要になったので。
vm2gol v2 (52) リファクタリング: 字句解析処理を別ファイルに分離
- 目次ページに戻る / 前 / 次
- 前回からの差分をまとめて見る
vgparser.rb
で行っていた字句解析処理を vglexer.rb
に分離します。
そうしなければいけない強い理由はあまりなくて、その方が他言語への移植がスムーズだった経験から、Ruby版にもフィードバックしておくか……というくらいのノリです。 あとは、個々のモジュールが小さくなっている方が威圧感がなくていいかなとか。
ファイル分割にあわせて、字句解析の結果であるトークン列をシリアライズして一度ファイルに出力する形にします。
整数値については、これまで字句解析の際に文字列から整数に変換して Token.new
に渡していましたが、最終的に文字列にシリアライズするのならわざわざ 文字列 → 整数 → 文字列 のように変換しなくても、文字列のまま受け渡してしまえばいいかなと。
*1
というわけで、まずはメインの修正の準備として文字列のまま渡すように修正。
--- a/vgparser.rb +++ b/vgparser.rb @@ -49,7 +49,7 @@ def tokenize(src) when /\A(-?[0-9]+)/ str = $1 - tokens << Token.new(:int, str.to_i) + tokens << Token.new(:int, str) pos += str.size when /\A(==|!=|[(){}=;+*,])/
これにより、Token#value
の型が String に統一され、静的型の言語への移植も(ちょっとだけ)やりやすくなります。
文字列から整数への変換はパーサで行うことになります。 微妙に DRY じゃないですが、まあいいか。
--- a/vgparser.rb +++ b/vgparser.rb @@ -131,7 +131,7 @@ class Parser t.value elsif t.type == :int @pos += 1 - t.value + t.value.to_i else raise ParseError end @@ -289,7 +289,14 @@ class Parser if t_left.type == :int || t_left.type == :ident @pos += 1 - expr_l = t_left.value + expr_l = + case t_left.type + when :int + t_left.value.to_i + else + t_left.value + end + parse_expr_right(expr_l) else
これで準備ができました。字句解析処理を vglexer.rb
に移動します……が、diff は大きいので略。
vglexer.rb
だけを動かして出力(シリアライズされたトークン列)を見るとこんな感じ:
$ ruby vglexer.rb gol.vg.txt | head kw:func ident:to_vi sym:( ident:w sym:, ident:x sym:, ident:y sym:, ident:offset
行ごとに記号と値をコロンで区切って並べるだけ。
あとは、 Parser クラスを解消して、トップレベルにメソッドが並ぶだけのスタイルにしました。簡単で分かりやすくする方向で考えるとクラスなくてもいいかなと。
テストコードの方もあわせて修正。すでに他のテストでやっているように ruby 〜.rb
の形でコマンドを実行して結果を読む方式に。
# test_vgparser.rb def _parse(src) File.open(VG_FILE, "wb") { |f| f.print src } _system %( ruby #{PROJECT_DIR}/vglexer.rb #{VG_FILE} > #{TOKENS_FILE} ) _system %( ruby #{PROJECT_DIR}/vgparser.rb #{TOKENS_FILE} > #{TREE_FILE} ) json = File.read(TREE_FILE) JSON.parse(json) end
その他の修正
- 変数名をより適切なものに変更
- words => insn, insns
- op, operator => opcode
- typo の修正
あと master
から main
にブランチ名を変えました。
素朴な自作言語のコンパイラをKotlinに移植した
かんたんな自作言語のコンパイラをいろんな言語で書いてみるシリーズ 12回目は Kotlin です。
やっつけなので汚いです。ライフゲームのコンパイルが通ったのでヨシ、というレベルのものです。
移植元
ベースになっているバージョン: tag:51 のあたり
メモ
- Java版 からコピーしてきて修正してできあがり。3日くらい。
- Kotlin は仕事で少しだけ使って、あと少し前に 「標準入力を読んで行ごとに処理」 と 「四則演算と剰余のみのexprコマンドをKotlinで作ってみた」 を書いたくらいのほぼ初心者
- Java と Scala の中間みたいな印象
今回の実験は配列変数の宣言。 trial ブランチで試してみました。
確認用のコードです。今回の実験ではとりあえずこれだけコンパイルできれば OK。
// declare_array.vg.txt func main() { var xs[22]; }
AST がこんな感じ。お試しなので適当。
$ ( \ > cat declare_array.vg.txt \ > | ./run.sh tokenize \ > | ./run.sh parse \ > ) 2>/dev/null [ "top_stmts", [ "func", "main", [ ], [ [ "var_array", "xs", 22 ] ] ] ]
アセンブリコードがこんな感じ。
$ ( \ > cat declare_array.vg.txt \ > | ./run.sh tokenize \ > | ./run.sh parse \ > | ./run.sh codegen \ > ) 2>/dev/null call main exit label main push bp cp sp bp # 関数の処理本体 sub_sp 22 # ... 配列のサイズ分の領域をスタック上に確保する cp bp sp pop bp ret
これだけだったら少し修正するだけで済みました。
次のようなコードはまだ正しく動くようにコンパイルできません。
func main() { var xs[22]; var a = 11; }
配列がスタック上で占有している幅を考慮しないといけないのに、それをまだやってないからです。 これをやろうとするとたぶんあちこち修正しないといけなくなるので、それはまた今度ということで。
vm2gol v2 (51) 機械語コードのフォーマットを固定長風に変更
- 目次ページに戻る / 前 / 次
- 前回からの差分をまとめて見る
これまで機械語コードのフォーマットはこのような YAML ファイルにしていました。 (以下便宜的に「可変長風」と呼びます)
--- - call - 1029 - exit - label - vram_set - push - bp ...
これを変更して、1行あたり1命令となるようにして、行ごとに JSON.parse
でパースできるようにしました。
(以下便宜的に「固定長風」と呼びます)
["call", 1029] ["exit"] ["label", "vram_set"] ["push", "bp"] ...
どの命令でもメモリ上で占める幅が 1 になったため Vm.num_args_for
も不要になってすっきりしました。
また、YAML への依存がなくなり JSON への依存に一本化できました。 Ruby でやる分には何でもいいのですが、他の言語に移植するときに若干めんどくさかったので。これでちょっと簡単になるはず。
その他の変更
メモ
元の YAML のように 1命令が複数の行(可変)となるようにしていたのは、機械語といってもバイナリではなくテキストにした上にさらに固定長風にしてしまうとさすがに簡略化しすぎで勉強にならないのではないか、みたいなことを考えていたからでした。たしか。
しかし、今になってみると別にこだわるところではなかったように思えます。こだわる必要がないのであれば簡単な方がよい、というわけで変えてしまうことにしました。
あとは 1行1命令にするとアセンブリコードとの違いがさらに小さくなってアセンブラが仕事してない感じになってしまうけどこれでいいの? ということが気になっていたのですが、そこも気にしないことにしました。
全体で 50行弱減って今このくらいの行数。
14 common.rb 58 vgasm.rb 555 vgcg.rb 509 vgparser.rb 513 vgvm.rb 1649 合計