vm2gol v2 （58） _debug でブレークポイントを指定できるようにした

vm2gol-v2

今回はブレークポイントを指定できるようにしたのと、後はリファクタリングです。

_debug でブレークポイントを指定

これまで、プログラムの特定の箇所の動作を観察してデバッグしたい場合次のような手順を踏んでいました。

  • まず適当に実行（最初からステップ実行するなど）して、調べたい場所が何ステップ目あたりかを調べる
  • vgvm.rb を直接書き換え、どのステップまでスキップするか指定する
  • 実行するとそのステップまでスキップされるので、そこからステップ実行する

参考: （30） 生存カウント / VRAM から値を取得 / ステップ数を表示

スキップできなかった状態に比べればこれでもかなりの進歩だったわけですが、 さらに便利になるようにブレークポイントを指定できるようにしました。

ステップ実行を始めたい箇所に _debug(); と書いて実行すると、

func main() {
  var a = 1;
  var b = 10;
  set a = a + 2;
  _debug();      // ここからステップ実行開始
  set a = a + b;
}

指定した箇所までダンプ表示がスキップされ、 次の図のように _debug 命令の箇所で止まります。

あとはこれまで通り Enter キーを押してステップ実行すればOK。

f:id:sonota88:20210504065415p:plain

これ、ほんとにちょっとした修正で済むのでたいへんお買い得です。もっと早くやっておけばよかった。

以下の VM の修正を見ての通り、 _debug 命令が来たら Vm#debug を true にして、 Vm#debug が true になっていたらステップ実行する、それだけ。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -135,6 +135,7 @@ class Vm
     @bp = stack_size - 1 # base pointer
 
     @step = 0
+    @debug = false
   end
 
   def test?
@@ -178,6 +179,7 @@ class Vm
     when "set_vram"  then set_vram()  ; @pc += 1
     when "get_vram"  then get_vram()  ; @pc += 1
     when "_cmt"      then               @pc += 1
+    when "_debug"    then _debug()    ; @pc += 1
     else
       raise "Unknown opcode (#{opcode})"
     end
@@ -199,7 +201,7 @@ class Vm
       return if do_exit
 
       unless test?
-        if ENV.key?("STEP")
+        if ENV.key?("STEP") || @debug
           dump()
           $stdin.gets
           # $stdin.gets if @step >= 600
@@ -432,6 +434,10 @@ class Vm
       raise not_yet_impl("arg2", arg2)
     end
   end
+
+  def _debug
+    @debug = true
+  end
 end
 
 if $PROGRAM_NAME == __FILE__

ほとんどそのまま受け渡すだけなのでコンパイラ部分も少しの修正でOK。

to_fn_arg_disp, to_lvar_disp

lvar_addr = to_lvar_addr(lvar_names, lvar_name)
puts "  cp 0 #{lvar_addr}"

のように使っていたやつです。

この lvar_addr には [bp:-2] のような文字列が入るわけですが、これって「アドレス」なんだっけ？   値をセットする宛先だからアドレスと呼んでもダメじゃなさそうだけど…… 詳しくいえば「宛先アドレスの bp 相対間接参照表現」みたいになるんでしょうか……。

みたいな感じでモヤモヤしていて気になっていました。

そこで、モヤモヤしなくて済むような名前と処理内容に変えました。

[bp:-2] のような文字列を返すのではなく、 displacement の値 -2 だけを返すようにすれば、次のように書けます。

  disp = to_lvar_disp(lvar_names, lvar_name)
  puts "cp 0 [bp:#{disp}]"

displacement という、呼び方が定まっているものを返しているわけですから、返り値を受ける変数名も素直に disp とすればよいと（略しているのは置いといて）。

そもそもは何度も同じような処理を繰り返していて煩雑だから共通化していたわけですが、こういう場合は DRY であることよりも意味が明確でモヤモヤしない方が嬉しいです。

また、修正前は

  • displacement を求める
  • 文字列（間接参照表現）を組み立てる

という2つの処理を行っていたのが、責務も単純になり、その面でも良かったのかなと。

その他の修正

他に気になっていた部分のリファクタリング。

  • メソッドの並び順の修正
  • その他細かいの
    • parse_args まわりを簡素化

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

Ruby

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） 二項演算を左結合に変更

vm2gol-v2

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

例として 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に移植した

vm2gol-v2

かんたんな自作言語のコンパイラをいろんな言語で書いてみるシリーズ 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の読み書きを組み込み関数化

vm2gol-v2

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}"

だいぶさっぱりしました。

その他