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 クエリの実行を待つ時間みたいになっており、仕事の質として非常によろしくない。転職を考えないとまずいレベル。
      • 「この半年何をしていましたか?」「Hive のクエリ書いてましたね……」
    • イテレーションが長過ぎる。イテレーションを速く回したい

方針

  • 用途をプロトタイピング、開発中の検証、自動テストに限定する
    • 完全なクローンである必要はない
    • サイズの大きなデータを扱う必要はない。 小さなデータだけを想定する。
  • ひとまず非公開
    • ひとまず自分用
    • 人に読まれる前提で書かないといけないとなると、やはり追加のコストがばかにならないので……
    • 自分が必要な機能だけを作る
    • 公開については自分で使えるようになってから考える
  • 汚くてよい
    • ある程度機能の揃った RDB を作るのは今回が初めてなので、どうせ大したものは作れない。初回から良いものを作るのは無理。
      • と思うことにしてハードルを下げる
    • 1年後にきれいなものができるより1ヶ月後に動くものが使える方が嬉しい。minimum viable product を目指す。
    • 個人が仕事以外の時間で作るものなので大したリソースは捻出できない。その範囲でなんとかする。
    • 仕事でこんなの書いたらどやされる、という感じの出来上がりになっております
  • UDF をそのまま動かすのは大変そうなので簡易に済ます。ここは諦める。

手間をかけずに済ませたいので、自分が慣れているもの、枯れているものを使う方向で。

  • HiveQLパーサ
    • Ruby + Racc
      • JRuby でもそのまま動く?
    • AST(S式)に変換
  • エンジン
    • Java
    • ASTを受け取って実行
      • 素朴に木の末端から evaluate していく方式で今のところ何とかなっている
  • HDFS

メモ

↓ここらへんを先にやっておいてよかった、というか、やってなかったらそもそも 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
  • [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


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 にブランチ名を変えました。



*1:ドメインロジックではドメインに即したオブジェクトに変換して使うべき、という観点からはその都度変換した方がよいと思いますが、ここは難しく考えなくていいんじゃないかな……。

素朴な自作言語のコンパイラをKotlinに移植した


かんたんな自作言語のコンパイラをいろんな言語で書いてみるシリーズ 12回目は Kotlin です。

やっつけなので汚いです。ライフゲームコンパイルが通ったのでヨシ、というレベルのものです。

github.com

移植元

memo88.hatenablog.com

ベースになっているバージョン: tag:51 のあたり

メモ


今回の実験は配列変数の宣言。 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 合計