Reline.readmultiline ちょっと調べたメモ

Reline を使うと複数行編集ができるようなので、自分が使いそうな基本的な部分について調べてみました。

このリッチなのが標準で使えるの嬉しいですよね。ありがたや……。

RUBY_VERSION    #=> 3.0.0
Reline::VERSION #=> 0.2.5

最初の雛形

ブロックは必須。

require "reline"

PROMPT = "> "

loop do
  text =
    Reline.readmultiline(PROMPT) do |_|
      # このブロックについては後述
      true
    end

  # 編集が完了した複数行文字列を使った処理
  puts "text (#{text})"
end

これだけだとまだ複数行編集できないんですが、デバッグ用のログと履歴まわりを準備しておくと捗るので先にそっちを片付けます。

挙動確認のためのデバッグログ出力

デバッグ用の表示を同じターミナルに出力すると混ざって分かりにくいので、 ファイルに出力して別ターミナルで tail -F することに。

$log = File.open("debug.log", "a")

def debug(*args)
  $log.puts *args
  $log.flush
end

履歴の保存・復元

同じ入力を繰り返すのは面倒なので履歴まわりを用意しておきます。

Reline.readmultiline の第2引数 add_hist を true にすると Reline が履歴を覚えてくれて、カーソルキー上下や ctrl-n ctrl-p で履歴を辿れるようになります。

  text = Reline.readmultiline(PROMPT, true) do |input| ...

一度終了して次回実行したときに前回までの履歴が復元されてほしいので、シリアライズしてファイルに保存します。とりあえず JSON で適当に。

require "json"

HISTORY_FILE = "history"

def add_history(text)
  File.open(HISTORY_FILE, "a") { |f| f.puts JSON.generate(text) }
end

def load_history
  return unless File.exist?(HISTORY_FILE)

  File.read(HISTORY_FILE).each_line do |json|
    Reline::HISTORY << JSON.parse(json)
  end
end

Reline.readmultiline のブロック

  text =
    Reline.readmultiline(PROMPT, true) do |input|
      debug ""
      debug "-->> readmultiline block"
      debug input.inspect
      true
    end

こんな感じでデバッグ出力して動作を見てみると、 Enter キーが押されたタイミングでこのブロックが呼び出されているようだぞ、ということが確認できます。

11 Enter 22 Enter と入力したときのデバッグ出力:

-->> readmultiline block
"11\n"

-->> readmultiline block
"22\n"

このブロックは LineEditor#confirm_multiline_termination_proc にセットされ、

ed_newline
=> confirm_multiline_termination
=> @confirm_multiline_termination_proc

という流れで呼び出されるようです。 ed_newline という名前のメソッドから呼ばれているので、改行の入力がトリガーになっていると考えて良さそうな雰囲気です。

ブロックの呼び出しはこのようになっていて、

@confirm_multiline_termination_proc.(temp_buffer.join("\n") + "\n")

各行の末尾に LF の付いた文字列がブロックの引数に渡ってくることが分かります。


ブロックの評価値の扱いも見てみます。

class Reline::LineEditor
  # ...
  private def ed_newline(key)
    # ...
          if confirm_multiline_termination
            finish
          else
            key_newline(key)
          end

真だったら編集完了、偽だったら編集継続となるようです(見た感じでは)。


というわけで、

  1. 編集中の複数行文字列が引数としてブロックに渡ってくる
  2. 編集が完了しているかを判断し、完了している場合はブロックの評価値を真にする。途中だったら偽にする。

というあたりを踏まえて、ブロックの中身を修正します。 例として、末尾が ; になっていたら編集完了というルールにします。

  text =
    Reline.readmultiline(PROMPT, true) do |input|
      debug ""
      debug "--> readmultiline block"
      debug input.inspect

      finished = input.strip.end_with?(";")
      debug "finished (#{finished})"
      finished
    end

11 Enter ;22 Enter ; Enter と入力したときのデバッグ出力:

-->> readmultiline block
"11\n"
finished (false)       ... まだ編集の途中

-->> readmultiline block
"11\n;22\n"
finished (false)       ... まだ編集の途中

-->> readmultiline block
"11\n;22\n;\n"
finished (true)        ... 末尾が ; なので編集が完了したと判断

なるほど。基本的なことがやりたいだけであればこのくらい分かっていれば良さそうですね。

プロンプトをカスタマイズする

たとえば、最初の行とそれ以外で異なるプロンプトを表示したいといった場合、 Reline.prompt_proc に Proc オブジェクトをセットすることでカスタマイズできるようです。

PROMPT = "> "

Reline.prompt_proc =
  Proc.new do |lines|
    lines.each_with_index.map do |line, i|
      i == 0 ? PROMPT : "| "
    end
  end
$ ruby sample.rb 
> 11
| 22
| ;
text (11
22
;)
> 

この場合、Reline.prompt_proc で生成したプロンプト文字列が優先して使われ、Reline.readmultiline の第一引数で渡したプロンプト文字列は使われなくなるようです(表面的な挙動を見た感じでは)。

ただし、Reline.readmultiline の第一引数で渡したプロンプト文字列と長さが異なっていると履歴を移動した際にカーソル位置がずれるので、とりあえず同じ長さにしておくと良いようです。

まとめたもの

require "reline"
require "json"

HISTORY_FILE = "history"
PROMPT = "> "

$log = File.open("debug.log", "a")

def debug(*args)
  $log.puts *args
  $log.flush
end

def add_history(text)
  File.open(HISTORY_FILE, "a") { |f| f.puts JSON.generate(text) }
end

def load_history
  return unless File.exist?(HISTORY_FILE)

  File.read(HISTORY_FILE).each_line do |json|
    Reline::HISTORY << JSON.parse(json)
  end
end

def finished?(input)
  stripped = input.strip
  return true if stripped == "exit"
  return true if stripped.end_with?(";")

  false
end

Reline.prompt_proc =
  Proc.new do |lines|
    lines.each_with_index.map do |line, i|
      i == 0 ? PROMPT : "| "
    end
  end

load_history

loop do
  text =
    Reline.readmultiline(PROMPT, true) do |input|
      debug ""
      debug "-->> readmultiline block"
      debug input.inspect

      finished = finished?(input)
      debug "finished (#{finished})"
      finished
    end

  add_history text

  # 編集が完了した複数行文字列を使った処理
  puts "text (#{text})"

  break if text == "exit"
end

メモ

参考

関連

vm2gol v2 (57) 二項演算を左結合に変更



二項演算が右結合になっていたのを左結合に変えます。

例として 1 + 2 + 3 で見てみます。

変更前は

[:+,
  1,
  [:+, 2, 3]]

となるようにパースされていて、最終的に機械語になって実行されるときには

2 + 3
1 + {2 + 3 の結果}

という順番で実行されるようになっていました。

今回の変更により

[:+,
  [:+, 1, 2],
  3]

となるようにパースされ、

1 + 2
{1 + 2 の結果} + 3

という順番で実行されるようになります。


なぜ変更するかという話で言えば、 v3 を作っているときに右結合なのを忘れていて少しハマったのがきっかけです。 コードを書いている側としては、無意識のうちに他の一般的な言語と同じで左結合だろうと思っていたわけですね。自分で作ったのに。

すごく困るというわけではないですし、 「ライフゲームコンパイルできればよい」という観点で言えば正直どっちでも大差ありません。

どっちでもいいのですが、実装を大きく変えなければいけないわけでもないので、 だったらより良い(一般的で直感に反していない、自然な)形に変えておこう、という程度の動機です。

意図的に右結合にしていたということもなかったと思いますし、変えてしまっていいでしょう。


修正後の状態。

def binary_op?(t)
  ["+", "*", "==", "!="].include?(t.value)
end

def _parse_expr_factor
  t = peek()

  if t.type == :sym
    consume "("
    expr = parse_expr()
    consume ")"
    expr

  elsif t.type == :int || t.type == :ident
    $pos += 1

    case t.type
    when :int
      t.value.to_i
    else
      t.value
    end

  else
    raise ParseError
  end
end

def parse_expr
  expr = _parse_expr_factor()

  while binary_op?(peek())
    op =
      case peek().value
      when "+"  then "+"
      when "*"  then "*"
      when "==" then "eq"
      when "!=" then "neq"
      else
        raise ParseError, "must not happen"
      end
    $pos += 1

    expr_r = _parse_expr_factor()
    expr = [op.to_sym, expr, expr_r]
  end

  expr
end

という処理になりました。関数の引数や case 文の when 句のパースと似たパターンですね。

その他の修正

  • ラベルが見つからない場合はエラーにする (vgasm.rb)
    • 存在しない関数を呼び出すようなコードを書いた場合、 原因が分かりにくいエラーが VM での実行時に発生するようになっていて困ったので、 アセンブルの段階でエラーにしてしまうことに
  • VMコメントの整理
  • rename: codegen_〜 => gen_〜 (vgcg.rb)
    • メソッド名を短くしました。 gen_〜 でも分かるからいいかなと。

2021-10-05 追記

式の結合と優先順位については、現時点で

  • 左結合
  • 演算子の優先順位なし(括弧で明示)

という方式になっていますが、たまたま VTL という言語についての記事を読んでいて「おお、同じだ」と思いました。

VTL(Very Tiny Language)の作成

VTLでは,演算子の間に優先順位は存在せず,左から順番に演算が行われます.演算の順序を変えたい場合は括弧"()"をつけます.例えば,"2+3*4"の結果は"20"となり,"2+(3*4)"の結果は"14"となります.

vm2gol の方は「ライフゲームコンパイルするという目的に対して重要度の低い部分を排してできるだけ簡素にしたい」という動機により優先順位なしになっているわけですが、VTL の方はリソースの制約が背景にあっての選択のようです。



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

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

理解は後回しにしてとにかく動くものを作るぞ、という方向性で書いたもの。

できたもの

github.com

移植元

memo88.hatenablog.com

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

動かし方の例

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

  func main() {
    call add(1, 2);
  }
' | cargo run lex | cargo run parse | cargo run 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)

メモ

  • 理解は後回しにして、かっこ悪い書き方でもいいのでとにかく完成まで持って行く……といういつも通りの方針で、時間をかけすぎないように。理解は後でゆっくり。まずは手を動かして慣れる。
  • Tour of Rust
    • 情報量が多すぎずよく整理されていて、一番最初にこれを読めばよかった
  • 借用とかムーブとか
    • このくらいのプログラムを書いて動かせる程度には分かってきた、はず。 でもけっこう怪しい。
  • ライフタイム
    • まだよく分かっていなくて、コンパイルが通らなかったらライフタイムが絡まない書き方にして回避したりしている
  • 連結リストが難しそうだったので Vec<NodeId> で管理する方式にしてとりあえず回避
  • レキサの入力文字列は最初に Vec<char> にして使い回し
    • C版Zig版 のように単純なバイト列として扱ってもよかったが、 せっかくなので UTF-8 文字列として扱ってみた

TODO

気が向いたらあとで

  • List にノードID ではなくノードを直接持たせる
  • List のイテレータ対応

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

memo88.hatenablog.com

memo88.hatenablog.com

memo88.hatenablog.com

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行近く減らせました! 🙌

(まあ、元が冗長すぎたんですけどね)