vm2gol v2 製作メモ(30) 生存カウント / VRAM から値を取得 / ステップ数を表示


$stdin.gets を無効化

前回二重ループですべてのセルを生存に変えていくというのをやりましたが、 ループがぐるぐる回るため何度も同じ処理を繰り返すようになり、 Enter キーを押しっぱなしにしないといけなくなってきました。

これはかったるいです。なんとかしましょう。

(かったるいですが、たったこれだけのことをやるのでも こんなにいっぱい命令を処理しているんだなあ……と実感できるので これはこれでよい体験だと思います )

Enter キーで 1ステップごとに進めるのをやめて、 勝手に動くようにしてみましょうか。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -285,7 +285,7 @@ class Vm
       end
 
       dump_v2()
-      $stdin.gets
+      # $stdin.gets
     end
   end

完全に削除せずにコメントアウトにしておきました。

これで前回の 29_loop_xy.vgt.json を動かすと一瞬ですべてのセルが生存になり、 おおっ、すごい! となるのですが、一方で、一瞬でババッと動いて終わってしまうので、少し寂しさがあります。 というか速すぎて何が起こってるか全然分からない……。

sleep を入れてみましょうか。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -286,6 +286,7 @@ class Vm
 
       dump_v2()
       # $stdin.gets
+      sleep 0.01
     end
   end

うーむ。まあこれで進めてみましょう。

vram_get()

ライフゲームの話に戻ります。

次にどこから手を付けるかちょっと悩むところですが、 あるセルの周囲にある 8個のセルを調べ、 何個が生きているかを調べる関数 count_alive() を作りましょうか。

Ruby で書いたものでいうとここです:

      xl = (x == 0     ) ? $w - 1 : x - 1
      xr = (x == $w - 1) ? 0      : x + 1
      yt = (y == 0     ) ? $h - 1 : y - 1
      yb = (y == $h - 1) ? 0      : y + 1

      n = 0
      n += $grid[yt][xl]
      n += $grid[y ][xl]
      n += $grid[yb][xl]
      n += $grid[yt][x ]
      n += $grid[yb][x ]
      n += $grid[yt][xr]
      n += $grid[y ][xr]
      n += $grid[yb][xr]

まずは端っこの方は無視して、盤面の中心でカウントが正しく動くことを確認しようと思います。 中心のセル(座標でいうと (2, 2) )に着目しているとして、たとえば

.....
.@...
.....
.....
.....

という状態であれば生存数 1、

.....
.@@@.
.@.@.
.@@@.
.....

だったら 8 、が得られることを目指します。


そのためには VRAM から値を読み取る vram_get() が必要で……まだなかったですね。今回はこれを作ります。

  • vram_set() をコピーしてちょっと修正して vram_get() を用意。
  • count_alive() 関数を作って main() から呼び出す。 まずは適当なセルの値を取得して、ローカル変数 tmp にセットするだけ。
// 30_count_alive.vgt.json

["stmts"

, ["func", "vram_set", ["w", "x", "y", "val"]
  , [
      ["var", "yw"]
    , ["set", "yw", ["*", "y", "w"]]

    , ["var", "vi"] // vram index
    , ["set", "vi", ["+", "yw", "x"]]

    , ["set", "vram[vi]", "val"]
    ]
  ]

, ["func", "vram_get", ["w", "x", "y"]
  , [
      ["var", "yw"]
    , ["set", "yw", ["*", "y", "w"]]

    , ["var", "vi"] // vram index
    , ["set", "vi", ["+", "yw", "x"]]

    , ["return", "vram[vi]"]
    ]
  ]

, ["func", "count_alive", ["w", "x", "y"]
  , [
      ["var", "count"]
    , ["set", "count", 0]

    , ["var", "tmp"]
    , ["call_set", "tmp", ["vram_get", "w", "x", "y"]]
    ]
  ]

, ["func", "main", []
  , [
      ["var", "w"] // 盤面の幅
    , ["set", "w", 5]
    , ["var", "h"] // 盤面の高さ
    , ["set", "h", 5]

    , ["var", "x"]
    , ["set", "x", 0]

    , ["var", "y"]
    , ["set", "y", 0]

    , ["call", "count_alive", "w", 1, 1]
    ]
  ]

]

実行。

================================
reg_a(6) reg_b(1) reg_c(0) zf(0)
---- memory (main) ----
      58   ["set_reg_a", "[bp-1]"]
      60   ["set_reg_b", "[bp+3]"]
      62   ["add_ab"]
      63   ["cp", "reg_a", "[bp-2]"]
      66   ["set_reg_a", "vram[vi]"]
      68   ["cp", "bp", "sp"]
      71   ["pop", "bp"]
      73   ["ret"]
      74 ["label", "count_alive"]
      76   ["push", "bp"]
      78   ["cp", "sp", "bp"]
      81   ["sub_sp", 1]
      83   ["cp", 0, "[bp-1]"]
      86   ["sub_sp", 1]
pc => 88   ["push", "y"]
      90   ["push", "x"]
      92   ["push", "w"]
      94   ["call", 41]
      96   ["add_sp", 3]
      98   ["cp", "reg_a", "[bp-2]"]
      101   ["cp", "bp", "sp"]
      104   ["pop", "bp"]
      106   ["ret"]
      107 ["label", "main"]
      109   ["push", "bp"]
      111   ["cp", "sp", "bp"]
      114   ["sub_sp", 1]
      116   ["cp", 5, "[bp-1]"]
---- memory (stack) ----
         28 0
         29 0
         30 0
         31 0
         32 0
         33 0
         34 0
         35 6
sp    => 36 5
         37 0
   bp => 38 47
         39 154
         40 5
         41 1
         42 1
         43 0
         44 0
---- memory (vram) ----
..... .....
.@... .....
..... .....
..... .....
..... .....
vgvm.rb:227:in `block in start': Not yet implemented ("push") ("y") (RuntimeError)
    from vgvm.rb:150:in `loop'
    from vgvm.rb:150:in `start'
    from vgvm.rb:445:in `<main>'

↓このようになっていて、関数の引数が解決されずにそのまま VM に渡っています。またこのパターンですね。

pc => 88   ["push", "y"]
      90   ["push", "x"]
      92   ["push", "w"]

修正します。 codegen_call_set() の引数に fn_arg_names を追加して 参照を解決してあげます。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -215,14 +215,29 @@ def codegen_call(lvar_names, stmt_rest)
   alines
 end
 
-def codegen_call_set(lvar_names, stmt_rest)
+def codegen_call_set(fn_arg_names, lvar_names, stmt_rest)
   alines = []
 
   lvar_name, fn_temp = stmt_rest
   fn_name, *fn_args = fn_temp
+
   fn_args.reverse.each {|fn_arg|
-    alines << "  push #{fn_arg}"
+    case fn_arg
+    when Integer
+      alines << "  push #{fn_arg}"
+    when String
+      case
+      when fn_arg_names.include?(fn_arg)
+        fn_arg_addr = to_fn_arg_addr(fn_arg_names, fn_arg)
+        alines << "  push #{fn_arg_addr}"
+      else
+        raise not_yet_impl(fn_arg)
+      end
+    else
+      raise not_yet_impl(fn_arg)
+    end
   }
+
   alines << "  call #{fn_name}"
   alines << "  add_sp #{fn_args.size}"
 
@@ -297,7 +312,7 @@ def codegen_func_def(rest)
     when "call"
       alines += codegen_call(lvar_names, stmt_rest)
     when "call_set"
-      alines += codegen_call_set(lvar_names, stmt_rest)
+      alines += codegen_call_set(fn_arg_names, lvar_names, stmt_rest)
     when "var"
       lvar_names << stmt_rest[0]
       alines << "  sub_sp 1"

何度もやってきたので慣れたものですね。

実行。

$ ./run.sh 30_count_alive.vgt.json

(略)

      74 ["label", "count_alive"]
      76   ["push", "bp"]
      78   ["cp", "sp", "bp"]
      81   ["sub_sp", 1]
      83   ["cp", 0, "[bp-1]"]
      86   ["sub_sp", 1]
pc => 88   ["push", "[bp+4]"]

(略)

vgvm.rb:227:in `block in start': Not yet implemented ("push") ("[bp+4]") (RuntimeError)
    from vgvm.rb:150:in `loop'
    from vgvm.rb:150:in `start'
    from vgvm.rb:445:in `<main>'

今度は VM です。 関数の引数の push ってまだやってなかったんですね。

修正します。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -223,6 +223,9 @@ class Vm
             when /^\[bp\-(\d+)\]$/
               stack_addr = @bp - $1.to_i
               @mem.stack[stack_addr]
+            when /^\[bp\+(\d+)\]$/
+              stack_addr = @bp + $1.to_i
+              @mem.stack[stack_addr]
             else
               raise not_yet_impl("push", arg)
             end

実行。

$ ./run.sh 30_count_alive.vgt.json 

(略)

      39 ["label", "vram_get"]
      41   ["push", "bp"]
      43   ["cp", "sp", "bp"]
      46   ["sub_sp", 1]
      48   ["set_reg_a", "[bp+4]"]
      50   ["set_reg_b", "[bp+2]"]
      52   ["mult_ab"]
      53   ["cp", "reg_a", "[bp-1]"]
      56   ["sub_sp", 1]
      58   ["set_reg_a", "[bp-1]"]
      60   ["set_reg_b", "[bp+3]"]
      62   ["add_ab"]
      63   ["cp", "reg_a", "[bp-2]"]
pc => 66   ["set_reg_a", "vram[vi]"]

(略)

vgvm.rb:408:in `set_reg_a': Not yet implemented ("val") ("vram[vi]") (RuntimeError)
    from vgvm.rb:162:in `block in start'
    from vgvm.rb:150:in `loop'
    from vgvm.rb:150:in `start'
    from vgvm.rb:448:in `<main>'

えーっと…… vi というのはローカル変数の名前なので、 機械語コードにこれが登場してるのはおかしい、というやつ。

, ["return", "vram[vi]"]

ここです。 return 文のとこを修正します。

ちょっと長めになったので codegen_return() にメソッド抽出しました。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -289,6 +289,35 @@ def codegen_set(fn_arg_names, lvar_names, rest)
   alines
 end
 
+def codegen_return(lvar_names, stmt_rest)
+  alines = []
+
+  retval = stmt_rest[0]
+
+  case retval
+  when Integer
+    alines << "  set_reg_a #{retval}"
+  when String
+    case retval
+    when /^vram\[([a-z0-9_]+)\]$/
+      var_name = $1
+      case
+      when lvar_names.include?(var_name)
+        lvar_addr = to_lvar_addr(lvar_names, var_name)
+        alines << "  get_vram #{lvar_addr} reg_a"
+      else
+        raise not_yet_impl("retval", retval)
+      end
+    else
+      raise not_yet_impl("retval", retval)
+    end
+  else
+    raise not_yet_impl("retval", retval)
+  end
+
+  alines
+end
+
 def codegen_func_def(rest)
   alines = []
 
@@ -321,8 +350,7 @@ def codegen_func_def(rest)
     when "eq"
       alines += codegen_exp(fn_arg_names, lvar_names, stmt)
     when "return"
-      val = stmt_rest[0]
-      alines << "  set_reg_a #{val}"
+      alines += codegen_return(lvar_names, stmt_rest)
     when "case"
       alines += codegen_case(stmt_rest)
     when "while"

実行。

$ ./run.sh 30_count_alive.vgt.json 

(略)

      39 ["label", "vram_get"]
      41   ["push", "bp"]
      43   ["cp", "sp", "bp"]
      46   ["sub_sp", 1]
      48   ["set_reg_a", "[bp+4]"]
      50   ["set_reg_b", "[bp+2]"]
      52   ["mult_ab"]
      53   ["cp", "reg_a", "[bp-1]"]
      56   ["sub_sp", 1]
      58   ["set_reg_a", "[bp-1]"]
      60   ["set_reg_b", "[bp+3]"]
      62   ["add_ab"]
      63   ["cp", "reg_a", "[bp-2]"]
pc => 66   ["get_vram", "[bp-2]", "reg_a"]
      69   ["cp", "bp", "sp"]
      72   ["pop", "bp"]
      74   ["ret"]

(略)

vgvm.rb:279:in `[]': no implicit conversion of String into Integer (TypeError)
    from vgvm.rb:279:in `block in start'
    from vgvm.rb:150:in `loop'
    from vgvm.rb:150:in `start'
    from vgvm.rb:448:in `<main>'

さっき修正した return の部分ですが、今度は VMget_vram の方を修正します。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -276,7 +276,23 @@ class Vm
         arg1 = @mem.main[@pc + 1]
         arg2 = @mem.main[@pc + 2]
 
-        val = @mem.vram[arg1]
+        vram_addr =
+          case arg1
+          when Integer
+            arg1
+          when String
+            case arg1
+            when /^\[bp\-(\d+)\]$/
+              stack_addr = $1.to_i
+              @mem.stack[stack_addr]
+            else
+              raise not_yet_impl("arg1", arg1)
+            end
+          else
+            raise not_yet_impl("arg1", arg1)
+          end
+
+        val = @mem.vram[vram_addr]
 
         case arg2
         when "reg_a"

これでエラーが出なくなりました!

出なくなりましたが、ババッと動いて終了してしまうので やっぱり何が起こってるのかよく分からん…… というか何してたんだっけ…… あ、生存カウントでした。

コメントアウトしたばかりですが $stdin.gets をコメントインして結果確認しましょうか。うーむ。

================================
reg_a(0) reg_b(1) reg_c(0) zf(0)
---- memory (main) ----
      69   ["cp", "bp", "sp"]
      72   ["pop", "bp"]
      74   ["ret"]
      75 ["label", "count_alive"]
      77   ["push", "bp"]
      79   ["cp", "sp", "bp"]
      82   ["sub_sp", 1]
      84   ["cp", 0, "[bp-1]"]
      87   ["sub_sp", 1]
      89   ["push", "[bp+4]"]
      91   ["push", "[bp+3]"]
      93   ["push", "[bp+2]"]
      95   ["call", 41]
pc => 97   ["add_sp", 3]  # vram_get() から戻った直後
      99   ["cp", "reg_a", "[bp-2]"]
      102   ["cp", "bp", "sp"]
      105   ["pop", "bp"]
      107   ["ret"]
      108 ["label", "main"]

(略)

---- memory (vram) ----
..... .....
..... .....
..... .....
..... .....
..... .....

実行途中の様子。 vram_get() から戻ってきた直後です。

VRAM の (1, 1) のセルが死亡状態、 reg_a が 0 になっており、期待する結果になっているようです。 見た目の変化がないのでそこはかとなく不安ではありますが。


今度は (1, 1) のセルを生存状態にして、同じ箇所で reg_a が 1 になることを確認。

// 30_count_alive.vgt.json

+    , ["call", "vram_set", "w", 1, 1, 1] // この行を追加。 (1, 1) のセルを生存状態にする。
     , ["call", "count_alive", "w", 1, 1]

実行します。

================================
reg_a(0) reg_b(1) reg_c(0) zf(0)
---- memory (main) ----
      69   ["cp", "bp", "sp"]
      72   ["pop", "bp"]
      74   ["ret"]
      75 ["label", "count_alive"]
      77   ["push", "bp"]
      79   ["cp", "sp", "bp"]
      82   ["sub_sp", 1]
      84   ["cp", 0, "[bp-1]"]
      87   ["sub_sp", 1]
      89   ["push", "[bp+4]"]
      91   ["push", "[bp+3]"]
      93   ["push", "[bp+2]"]
      95   ["call", 41]               # vram_get() の呼び出し
pc => 97   ["add_sp", 3]              # vram_get() から戻った直後
      99   ["cp", "reg_a", "[bp-2]"]
      102   ["cp", "bp", "sp"]
      105   ["pop", "bp"]
      107   ["ret"]
      108 ["label", "main"]
      110   ["push", "bp"]
      112   ["cp", "sp", "bp"]
      115   ["sub_sp", 1]
      117   ["cp", 5, "[bp-1]"]
      120   ["sub_sp", 1]
      122   ["cp", 5, "[bp-2]"]
      125   ["sub_sp", 1]
      127   ["cp", 0, "[bp-3]"]
---- memory (stack) ----
         25 0
         26 0
         27 0
         28 0
         29 6
         30 5
         31 38
         32 97
sp    => 33 5
         34 1
         35 1
         36 5
         37 0
   bp => 38 47
         39 155
         40 5
         41 1
---- memory (vram) ----
..... .....
.@... .....
..... .....
..... .....
..... .....

あれ、 reg_avram_get() の返り値)が 1 になるはずなのに……おかしい……。

(何回も動かして調べる)

分かりました。さっき修正した get_vram の修正がミスっていたようです。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -283,7 +283,7 @@ class Vm
           when String
             case arg1
             when /^\[bp\-(\d+)\]$/
-              stack_addr = $1.to_i
+              stack_addr = @bp - $1.to_i
               @mem.stack[stack_addr]
             else
               raise not_yet_impl("arg1", arg1)

再度実行すると、ちゃんと reg_a に 1 が入りました!

ステップ数を表示

さて、さっき「何回も動かして調べる」と書きました。

何をしてたかというと、

  • (1) 実行しつつメインメモリとにらめっこして、目的の箇所を探す (辿り着くまで Enter キーで進める)
  • (2) 目的の箇所で止めて状態を確認する
  • (3) おかしかったら、 Ctrl+C で止めて、VM のコードを修正して、 (1) に戻る

みたいなことを繰り返していました。

ここらへんから、デバッグがだんだんしんどくなってきます。 @pc がメインメモリの中で行ったり来たりするので 「目的の箇所を探す」がまず大変。 集中力が必要だし、見間違えて通り過ぎると「あぁ〜また最初から実行しないと……」 となります。

そこで、何か工夫しようということで、ステップ数を表示することにしました。 これならすぐできそう。

目的の箇所が何ステップ目かが分かれば、 2回目以降はステップ数を見ながら、たとえば 「120ステップのところまで進めて確認すればいいな」 という感じで作業できて、これだけでもだいぶ楽になります。

修正します。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -132,6 +132,8 @@ class Vm
     @sp = stack_size - 1
     # ベースポインタ
     @bp = stack_size - 1
+
+    @step = 0
   end
 
   def set_sp(addr)
@@ -148,6 +150,8 @@ class Vm
     $stdin.gets
 
     loop do
+      @step += 1
+
       # operator
       op = @mem.main[@pc]
 
@@ -371,7 +375,7 @@ class Vm
   def dump_v2
     puts <<-EOB
 ================================
-#{ dump_reg() } zf(#{ @zf })
+#{ @step }: #{ dump_reg() } zf(#{ @zf })
 ---- memory (main) ----
 #{ @mem.dump_main(@pc) }
 ---- memory (stack) ----

これで実行すると下記のようになり、 さっきのデバッグで見ていた箇所は 62 ステップ目だな、というように分かるわけです。 これは改善ですね!

================================
62: reg_a(1) reg_b(1) reg_c(0) zf(0)
---- memory (main) ----
      69   ["cp", "bp", "sp"]
      72   ["pop", "bp"]
      74   ["ret"]
      75 ["label", "count_alive"]
      77   ["push", "bp"]
      79   ["cp", "sp", "bp"]
      82   ["sub_sp", 1]
      84   ["cp", 0, "[bp-1]"]
      87   ["sub_sp", 1]
      89   ["push", "[bp+4]"]
      91   ["push", "[bp+3]"]
      93   ["push", "[bp+2]"]
      95   ["call", 41]
pc => 97   ["add_sp", 3]
      99   ["cp", "reg_a", "[bp-2]"]
      102   ["cp", "bp", "sp"]
      105   ["pop", "bp"]
      107   ["ret"]
      108 ["label", "main"]
      ...

さらに、こうすれば

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -311,7 +311,7 @@ class Vm
       end
 
       dump_v2()
-      $stdin.gets
+      $stdin.gets >= 62
       sleep 0.01
     end
   end

調べたいところまで早送りして、それ以降はステップ実行、 なんてこともできます!


VRAM からセルの生死の情報が取得できるようになったので、 生存カウントの続きに戻りましょう!

vm2gol v2 製作メモ(29) 盤面のスキャン / 組み込みの neq


盤面の初期化ができたので続きをやります。

えーと続きというのは何かというと…… とりあえずループを回して盤面のセルを1個ずつスキャンする処理が必要なので、 それをやりましょう。

Ruby のコードでいうとこの部分。

(0...$h).each do |y|
  (0...$w).each do |x|
    # x, y を使った処理
  end
end

一度にあれこれやると大変そうなので、 前回のブリンカーの初期化を改造して、 まずは「メインの盤面のセルを全部 1(生存)にするだけ」 をやってみましょう。

1行だけでやってみる

いや、さらにステップを小さくしましょう。 まずは y を 0 に固定にして x だけ 0 から w-1 まで変化させるところからやってみます。 これなら単に一重の while ループ書くだけですね。

// 29_loop_x.vgt.json

["stmts"
, ["func", "vram_set", ["w", "x", "y", "val"]
  , [
      ["var", "yw"]
    , ["set", "yw", ["*", "y", "w"]]

    , ["var", "vi"] // vram index
    , ["set", "vi", ["+", "yw", "x"]]

    , ["set", "vram[vi]", "val"]
    ]
  ]

, ["func", "main", []
  , [
      ["var", "w"] // 盤面の幅
    , ["set", "w", 5]

    , ["var", "x"]
    , ["set", "x", 0]

    , ["while", ["neq", "x", "w"], [
        ["call", "vram_set", "w", "x", 0, 1]
      , ["set", "x", ["+", "x", 1]]
      ]]
    ]
  ]
]

実行します。

$ ./run.sh 29_loop_x.vgt.json 
vgcg.rb:132:in `codegen_exp': Not yet implemented ("right") ("w") (RuntimeError)
        from vgcg.rb:78:in `codegen_while'
        from vgcg.rb:294:in `block in codegen_func_def'
        from vgcg.rb:274:in `each'
        from vgcg.rb:274:in `codegen_func_def'
        from vgcg.rb:315:in `block in codegen_stmts'
        from vgcg.rb:311:in `each'
        from vgcg.rb:311:in `codegen_stmts'
        from vgcg.rb:334:in `codegen'
        from vgcg.rb:346:in `<main>'

これは……あ、 codegen_exp の右項の処理がローカル変数に未対応ですね。 対応させましょう。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -128,6 +128,8 @@ def codegen_exp(fn_arg_names, lvar_names, exp)
       case
       when fn_arg_names.include?(args[1])
         to_fn_arg_addr(fn_arg_names, args[1])
+      when lvar_names.include?(args[1])
+        to_lvar_addr(lvar_names, args[1])
       else
         raise not_yet_impl("right", args[1])
       end

実行。

$ ./run.sh 29_loop_x.vgt.json 
vgcg.rb:168:in `codegen_exp': Not yet implemented ("operator") ("neq") (RuntimeError)
        from vgcg.rb:78:in `codegen_while'
        from vgcg.rb:296:in `block in codegen_func_def'
        from vgcg.rb:276:in `each'
        from vgcg.rb:276:in `codegen_func_def'
        from vgcg.rb:317:in `block in codegen_stmts'
        from vgcg.rb:313:in `each'
        from vgcg.rb:313:in `codegen_stmts'
        from vgcg.rb:336:in `codegen'
        from vgcg.rb:348:in `<main>'

なるほど、以前 eq は作っていました (※ 第23回) が、 neq は未実装でした。 実装しましょう。


eq とだいたい同じ。 "neq" は "not equal" の略です。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -164,6 +164,24 @@ def codegen_exp(fn_arg_names, lvar_names, exp)
     alines << "  set_reg_a 1"
 
     alines << "label end_eq_#{label_id}"
+  when "neq"
+    $label_id += 1
+    label_id = $label_id
+
+    alines << "  set_reg_a #{left}"
+    alines << "  set_reg_b #{right}"
+    alines << "  compare"
+    alines << "  jump_eq then_#{label_id}"
+
+    # else
+    alines << "  set_reg_a 1"
+    alines << "  jump end_neq_#{label_id}"
+
+    # then
+    alines << "label then_#{label_id}"
+    alines << "  set_reg_a 0"
+
+    alines << "label end_neq_#{label_id}"
   else
     raise not_yet_impl("operator", operator)
   end

eq の部分をコピペして、 ラベルを修正して、 評価結果(set_reg_a にセットする値)の真偽を逆にしただけ。 たぶんこれでいいはず……。

実行。

$ ./run.sh 29_loop_x.vgt.json 
vgcg.rb:339:in `block in codegen_stmts': Not yet implemented ("stmt_head") ("call") (RuntimeError)
        from vgcg.rb:331:in `each'
        from vgcg.rb:331:in `codegen_stmts'
        from vgcg.rb:91:in `codegen_while'
        from vgcg.rb:314:in `block in codegen_func_def'
        from vgcg.rb:294:in `each'
        from vgcg.rb:294:in `codegen_func_def'
        from vgcg.rb:335:in `block in codegen_stmts'
        from vgcg.rb:331:in `each'
        from vgcg.rb:331:in `codegen_stmts'
        from vgcg.rb:354:in `codegen'
        from vgcg.rb:366:in `<main>'

なるほど、 codegen_while()codegen_stmts() と呼び出しているのですが、 codegen_stmts() が call文に対応していません。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -333,6 +333,8 @@ def codegen_stmts(fn_arg_names, lvar_names, rest)
     case stmt_head
     when "func"
       alines += codegen_func_def(stmt_rest)
+    when "call"
+      alines += codegen_call(lvar_names, stmt_rest)
     when "set"
       alines += codegen_set(fn_arg_names, lvar_names, stmt_rest)
     else

codegen_func_def() からコピペ……。 前回ちょっと書いたように codegen_stmts()codgen_func_def() の内容が重複してます。 リファクタリングできそうですが、前回書いた通り放置して、 ベタに codegen_stmts() を call文に対応させます。

ともかくこれで動くようになりました! VRAM のメイン領域の y=0 の行のセルが左から順に生存になっていき、 右端のセルまで全部生存になったところで while ループを抜けて プログラムが終了します。

---- memory (vram) ----
@@@@@ .....
..... .....
..... .....
..... .....
..... .....

exit

二重ループですべてのセルを生存にする

では二重ループですべてのセルを生存にしてみましょう! はたして二重ループはちゃんと動くでしょうか?

// 29_loop_xy.vgt.json

["stmts"
, ["func", "vram_set", ["w", "x", "y", "val"]
  , [
      ["var", "yw"]
    , ["set", "yw", ["*", "y", "w"]]

    , ["var", "vi"] // vram index
    , ["set", "vi", ["+", "yw", "x"]]

    , ["set", "vram[vi]", "val"]
    ]
  ]

, ["func", "main", []
  , [
      ["var", "w"] // 盤面の幅
    , ["set", "w", 5]
    , ["var", "h"] // 盤面の高さ
    , ["set", "h", 5]

    , ["var", "x"]
    , ["set", "x", 0]

    , ["var", "y"]
    , ["set", "y", 0]

    , ["while", ["neq", "y", "h"], [
        ["set", "x", 0]

      , ["while", ["neq", "x", "w"], [
          ["call", "vram_set", "w", "x", "y", 1]
        , ["set", "x", ["+", "x", 1]]
        ]]

        , ["set", "y", ["+", "y", 1]]

      ]]
    ]
  ]
]

実行。

$ ./run.sh 29_loop_xy.vgt.json 
vgcg.rb:341:in `block in codegen_stmts': Not yet implemented ("stmt_head") ("while") (RuntimeError)
        from vgcg.rb:331:in `each'
        from vgcg.rb:331:in `codegen_stmts'
        from vgcg.rb:91:in `codegen_while'
        from vgcg.rb:314:in `block in codegen_func_def'
        from vgcg.rb:294:in `each'
        from vgcg.rb:294:in `codegen_func_def'
        from vgcg.rb:335:in `block in codegen_stmts'
        from vgcg.rb:331:in `each'
        from vgcg.rb:331:in `codegen_stmts'
        from vgcg.rb:356:in `codegen'
        from vgcg.rb:368:in `<main>'

これも同じパターン。 codegen_while()codegen_stmts() と呼びだされて、 codegen_stmts() が while文に対応してません。

同じように codegen_func_def() からのコピペで修正します。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -337,6 +337,8 @@ def codegen_stmts(fn_arg_names, lvar_names, rest)
       alines += codegen_call(lvar_names, stmt_rest)
     when "set"
       alines += codegen_set(fn_arg_names, lvar_names, stmt_rest)
+    when "while"
+      alines += codegen_while(fn_arg_names, lvar_names, stmt_rest)
     else
       raise not_yet_impl("stmt_head", stmt_head)
     end

動くようになりました!! 下記のようにローカル変数 w, h, x, y が割り当てられていて、 x, y が指しているセルが生存に変わっていく様子が観察できます!

---- memory (stack) ----
         35 7
         36 5
         37 47
         38 135
         39 5
         40 2
         41 1
         42 1
sp    => 43 1 ... y
         44 3 ... x
         45 5 ... h
         46 5 ... w
   bp => 47 49
         48 2
         49 0
---- memory (vram) ----
@@@@@ .....
@@@.. .....
..... .....
..... .....
..... .....

そのまま Enter キーを押しっぱなしにしていると、 下記のようにすべてのセルが生存になったところでプログラムが終了しました!

---- memory (stack) ----
         41 4
         42 1
         43 5
         44 5
         45 5
         46 5
         47 49
         48 2
sp bp => 49 0
---- memory (vram) ----
@@@@@ .....
@@@@@ .....
@@@@@ .....
@@@@@ .....
@@@@@ .....

exit

やぼうのじつげんに またいっぽ ちかづいたぞ!

vm2gol v2 製作メモ(28) リファクタリング / ダンプ表示の改良


リファクタリングします!

参照の解決処理をメソッド抽出

前回雑にコピペで追加しまくった

fn_arg_pos = fn_arg_names.index(args[1]) + 2
"[bp+#{fn_arg_pos}]"

この部分を抽出してメソッド化しようと思います。 2行だけとはいえ、さすがに何度も同じことをやっていてどうも煩雑なので。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -8,6 +8,11 @@ require './common'
 
 $label_id = 0
 
+def to_fn_arg_addr(fn_arg_names, fn_arg_name)
+  index = fn_arg_names.index(fn_arg_name)
+  "[bp+#{index + 2}]"
+end
+
 def codegen_case(when_blocks)
   alines = []
   $label_id += 1
@@ -103,8 +108,7 @@ def codegen_exp(fn_arg_names, lvar_names, exp)
         lvar_pos = lvar_names.index(args[0]) + 1
         "[bp-#{lvar_pos}]"
       when fn_arg_names.include?(args[0])
-        fn_arg_pos = fn_arg_names.index(args[0]) + 2
-        "[bp+#{fn_arg_pos}]"
+        to_fn_arg_addr(fn_arg_names, args[0])
       else
         raise not_yet_impl("left", args[0])
       end
@@ -119,8 +123,7 @@ def codegen_exp(fn_arg_names, lvar_names, exp)
     when String
       case
       when fn_arg_names.include?(args[1])
-        fn_arg_pos = fn_arg_names.index(args[1]) + 2
-        "[bp+#{fn_arg_pos}]"
+        to_fn_arg_addr(fn_arg_names, args[1])
       else
         raise not_yet_impl("right", args[1])
       end
@@ -175,8 +178,7 @@ def codegen_set(fn_arg_names, lvar_names, rest)
       alines += codegen_exp(fn_arg_names, lvar_names, exp)
       "reg_a"
     when fn_arg_names.include?(rest[1])
-      fn_arg_pos = fn_arg_names.index(rest[1]) + 2
-      "[bp+#{fn_arg_pos}]"
+      to_fn_arg_addr(fn_arg_names, rest[1])
     when /^vram\[(.+)\]$/ =~ rest[1]
       vram_addr = $1
       alines << "  get_vram #{vram_addr} reg_a"

適当に to_fn_arg_addr というメソッド名にしたものの、 このメソッドで行っていることは参照の解決なので resolve_〜 という名前の方が良かったかなあ? とか考えたりしつつ……。

まあこれで進めましょう。


ローカル変数の解決の方も同様に共通化します。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -13,6 +13,11 @@ def to_fn_arg_addr(fn_arg_names, fn_arg_name)
   "[bp+#{index + 2}]"
 end
 
+def to_lvar_addr(lvar_names, lvar_name)
+  index = lvar_names.index(lvar_name)
+  "[bp-#{index + 1}]"
+end
+
 def codegen_case(when_blocks)
   alines = []
   $label_id += 1
@@ -105,8 +110,7 @@ def codegen_exp(fn_arg_names, lvar_names, exp)
     when String
       case
       when lvar_names.include?(args[0])
-        lvar_pos = lvar_names.index(args[0]) + 1
-        "[bp-#{lvar_pos}]"
+        to_lvar_addr(lvar_names, args[0])
       when fn_arg_names.include?(args[0])
         to_fn_arg_addr(fn_arg_names, args[0])
       else
@@ -194,14 +198,14 @@ def codegen_set(fn_arg_names, lvar_names, rest)
     when /^\d+$/ =~ vram_addr
       alines << "  set_vram #{vram_addr} #{src_val}"
     when lvar_names.include?(vram_addr)
-      lvar_pos = lvar_names.index(vram_addr) + 1
-      alines << "  set_vram [bp-#{lvar_pos}] #{src_val}"
+      lvar_addr = to_lvar_addr(lvar_names, vram_addr)
+      alines << "  set_vram #{lvar_addr} #{src_val}"
     else
       raise not_yet_impl("vram_addr", vram_addr)
     end
   else
-    lvar_pos = lvar_names.index(dest) + 1
-    alines << "  cp #{src_val} [bp-#{lvar_pos}]"
+    lvar_addr = to_lvar_addr(lvar_names, dest)
+    alines << "  cp #{src_val} #{lvar_addr}"
   end
 
   alines
@@ -236,8 +240,8 @@ def codegen_func_def(rest)
         when String
           case
           when lvar_names.include?(fn_arg)
-            lvar_pos = lvar_names.index(fn_arg) + 1
-            alines << "  push [bp-#{lvar_pos}]"
+            lvar_addr = to_lvar_addr(lvar_names, fn_arg)
+            alines << "  push #{lvar_addr}"
           else
             raise not_yet_impl(fn_arg)
           end
@@ -256,8 +260,8 @@ def codegen_func_def(rest)
       alines << "  call #{fn_name}"
       alines << "  add_sp #{fn_args.size}"
 
-      lvar_pos = lvar_names.index(lvar_name) + 1
-      alines << "  cp reg_a [bp-#{lvar_pos}]"
+      lvar_addr = to_lvar_addr(lvar_names, lvar_name)
+      alines << "  cp reg_a #{lvar_addr}"
     when "var"
       lvar_names << stmt_rest[0]
       alines << "  sub_sp 1"

コード量の変化はあまりないものの、 DRY になり、ちょっとだけすっきりした……気がします。


あと目に付くのは、前回も修正しまくったこういうやつですね。

    case args[0]
    when Integer
      args[0]
    when String
      case
      when lvar_names.include?(args[0])
        to_lvar_addr(lvar_names, args[0])
      when fn_arg_names.include?(args[0])
        to_fn_arg_addr(fn_arg_names, args[0])
      else
        raise not_yet_impl("left", args[0])
      end
    else
      raise not_yet_impl("left", args[0])
    end

これも同じようなパターンが何度も出てくるので、 共通化したくなるのが人情ではありますが……

  • 似ているように見えて微妙に違っているので意外と手間がかかるかも?
    • 通化できるか調べる手間
      • 「早すぎる共通化」ではないか?
      • 抽象化に漏れはないか?
    • 抽出できる形に整える手間
  • テストコードで守られていない

といったあたりを考慮して、ここはぐっとこらえて、やめておきました。 下手なことしてバグを入れて時間をロスするのもつまらないですしね。

ひとまず寝かせておいて、 どうしてもやりたかったら完成した後でやってもいいでしょう。


似たようなところで言えば codegen_func_def()codegen_stmts() の内容が被っているのも気にはなっているんですが、 同様の理由で放置しています ( v1 のときは適当なところで共通化していたのですが、 v2 ではなんかタイミングを逃してしまいました…… )。

ダンプ表示の改良

この段階でもう一つ改良しておきます。

ライフゲームの実装に入り、 メインメモリのダンプ表示の行数が増え、 ダンプ表示全体が 1画面に収まらなくなってきました。

これは困るので、対処しましょう。 これからどんどん長くなっていくので、 そろそろ対策しておかないとこの後めんどくさいのです。

pc を基準にして、その前後の部分だけを表示するようにします。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -12,6 +12,8 @@ end
 class Memory
   attr_accessor :main, :stack, :vram
 
+  MAIN_DUMP_WIDTH = 30
+
   def initialize(stack_size)
     @main = []
 
@@ -34,7 +36,12 @@ class Memory
       addr += 1 + num_args
     end
 
-    vmcmds.map{ |vmcmd|
+    vmcmds
+    .select {|vmcmd|
+      pc - MAIN_DUMP_WIDTH <= vmcmd[:addr] &&
+      vmcmd[:addr] <= pc + MAIN_DUMP_WIDTH
+    }
+    .map {|vmcmd|
       head =
         if vmcmd[:addr] == pc
           "pc =>"

幅は適当に決めました。


それから、若干先回り気味ですが、スタック領域の方もついでに修正しておきます。

これまでは関数呼び出しのネストが浅かったので特に問題ありませんでしたが、 これからネストが深くなってくるとアドレスが大きい方 (sp 〜 スタックの底までの範囲)が伸びてきて、 これまた 1画面に収まらなくなるためです。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -80,6 +80,7 @@ class Memory
     @stack.each_with_index do |x, i|
       addr = i
       next if addr < sp - 8
+      next if addr > sp + 8
       head =
         case addr
         when sp

前回のブリンカーの初期化だけのプログラムを動かして確認します。

================================
reg_a(7) reg_b(2) reg_c(0) zf(0)
---- memory (main) ----
      07   ["cp", "sp", "bp"]
      10   ["sub_sp", 1]
      12   ["set_reg_a", "[bp+4]"]
      14   ["set_reg_b", "[bp+2]"]
      16   ["mult_ab"]
      17   ["cp", "reg_a", "[bp-1]"]
      20   ["sub_sp", 1]
      22   ["set_reg_a", "[bp-1]"]
      24   ["set_reg_b", "[bp+3]"]
      26   ["add_ab"]
      27   ["cp", "reg_a", "[bp-2]"]
      30   ["set_vram", "[bp-2]", "[bp+5]"]
      33   ["cp", "bp", "sp"]
pc => 36   ["pop", "bp"]
      38   ["ret"]
      39 ["label", "main"]
      41   ["push", "bp"]
      43   ["cp", "sp", "bp"]
      46   ["sub_sp", 1]
      48   ["cp", 5, "[bp-1]"]
      51   ["push", 1]
      53   ["push", 1]
      55   ["push", 2]
      57   ["push", "[bp-1]"]
      59   ["call", 5]
      61   ["add_sp", 4]
      63   ["push", 1]
      65   ["push", 2]
---- memory (stack) ----
         32 0
         33 0
         34 0
         35 0
         36 0
         37 0
         38 7
         39 5
sp bp => 40 47
         41 61
         42 5
         43 2
         44 1
         45 1
         46 5
         47 49
         48 2
---- memory (vram) ----
..... .....
..@.. .....
..... .....
..... .....
..... .....

1画面に収まるようになりました!

call, call_set のメソッド抽出

あと1箇所、ちょっとしたメソッド抽出もついでにやっておきます。

codegen_func_def() が長くなってきたので、 callcall_set の部分をメソッドに抽出しておきます。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -169,6 +169,32 @@ def codegen_exp(fn_arg_names, lvar_names, exp)
   alines
 end
 
+def codegen_call(lvar_names, stmt_rest)
+  alines = []
+
+  fn_name, *fn_args = stmt_rest
+  fn_args.reverse.each {|fn_arg|
+    case fn_arg
+    when Integer
+      alines << "  push #{fn_arg}"
+    when String
+      case
+      when lvar_names.include?(fn_arg)
+        lvar_addr = to_lvar_addr(lvar_names, fn_arg)
+        alines << "  push #{lvar_addr}"
+      else
+        raise not_yet_impl(fn_arg)
+      end
+    else
+      raise not_yet_impl(fn_arg)
+    end
+  }
+  alines << "  call #{fn_name}"
+  alines << "  add_sp #{fn_args.size}"
+
+  alines
+end
+
 def codegen_set(fn_arg_names, lvar_names, rest)
   alines = []
   dest = rest[0]
@@ -232,25 +258,7 @@ def codegen_func_def(rest)
     stmt_head, *stmt_rest = stmt
     case stmt_head
     when "call"
-      fn_name, *fn_args = stmt_rest
-      fn_args.reverse.each {|fn_arg|
-        case fn_arg
-        when Integer
-          alines << "  push #{fn_arg}"
-        when String
-          case
-          when lvar_names.include?(fn_arg)
-            lvar_addr = to_lvar_addr(lvar_names, fn_arg)
-            alines << "  push #{lvar_addr}"
-          else
-            raise not_yet_impl(fn_arg)
-          end
-        else
-          raise not_yet_impl(fn_arg)
-        end
-      }
-      alines << "  call #{fn_name}"
-      alines << "  add_sp #{fn_args.size}"
+      alines += codegen_call(lvar_names, stmt_rest)
     when "call_set"
       lvar_name, fn_temp = stmt_rest
       fn_name, *fn_args = fn_temp
--- a/vgcg.rb
+++ b/vgcg.rb
@@ -195,6 +195,23 @@ def codegen_call(lvar_names, stmt_rest)
   alines
 end
 
+def codegen_call_set(lvar_names, stmt_rest)
+  alines = []
+
+  lvar_name, fn_temp = stmt_rest
+  fn_name, *fn_args = fn_temp
+  fn_args.reverse.each {|fn_arg|
+    alines << "  push #{fn_arg}"
+  }
+  alines << "  call #{fn_name}"
+  alines << "  add_sp #{fn_args.size}"
+
+  lvar_addr = to_lvar_addr(lvar_names, lvar_name)
+  alines << "  cp reg_a #{lvar_addr}"
+
+  alines
+end
+
 def codegen_set(fn_arg_names, lvar_names, rest)
   alines = []
   dest = rest[0]
@@ -260,16 +277,7 @@ def codegen_func_def(rest)
     when "call"
       alines += codegen_call(lvar_names, stmt_rest)
     when "call_set"
-      lvar_name, fn_temp = stmt_rest
-      fn_name, *fn_args = fn_temp
-      fn_args.reverse.each {|fn_arg|
-        alines << "  push #{fn_arg}"
-      }
-      alines << "  call #{fn_name}"
-      alines << "  add_sp #{fn_args.size}"
-
-      lvar_addr = to_lvar_addr(lvar_names, lvar_name)
-      alines << "  cp reg_a #{lvar_addr}"
+      alines += codegen_call_set(lvar_names, stmt_rest)
     when "var"
       lvar_names << stmt_rest[0]
       alines << "  sub_sp 1"

ではライフゲームに戻りましょう!

vm2gol v2 製作メモ(27) ライフゲームの実装開始 / 組み込みの掛け算


なんだかライフゲーム詐欺みたいになってきましたが 今度こそほんとにライフゲームに突入できる……はず……。

というか突入しましょう!

やるぞぉ……!


はい、やります。

vgtコードです。 最終的にはグライダーを動かしたいのですが、 まずは確認が簡単そうなブリンカーから始めましょうか。

// 27_blinker.vgt.json

["stmts"
, ["func", "vram_set", ["w", "x", "y", "val"]
  , [
      ["var", "yw"]
    , ["set", "yw", ["*", "y", "w"]]

    , ["var", "vi"] // vram index
    , ["set", "vi", ["+", "yw", "x"]]

    , ["set", "vram[vi]", "val"]
    ]
  ]

, ["func", "main", []
  , [
      ["var", "w"] // 盤面の幅
    , ["set", "w", 5]

      // VRAM の初期化(ブリンカー)
    , ["call", "vram_set", "w", 2, 1, 1]
    , ["call", "vram_set", "w", 2, 2, 1]
    , ["call", "vram_set", "w", 2, 3, 1]
    ]
  ]
]

まずは初期化の部分ということで、 main 関数とは別に、座標を指定して状態をセットする vram_set 関数を用意し、 座標 (2, 1) (2, 2) (2, 3) の 3つのセルを生存状態にします。 VM の初期化時に VRAM の内容を 0 で初期化しているので、 これ以外のセルはすべて死亡状態です。

こういう状態に初期化したい:

.....
..@..
..@..
..@..
.....

さて、適当に書きましたが、とりあえず動かしてみましょうか。 どうなるでしょうか?

$ ./run.sh 27_blinker.vgt.json 
vgcg.rb:106:in `codegen_exp': Not yet implemented ("left") ("y") (RuntimeError)
        from vgcg.rb:154:in `codegen_set'
        from vgcg.rb:221:in `block in codegen_func_def'
        from vgcg.rb:196:in `each'
        from vgcg.rb:196:in `codegen_func_def'
        from vgcg.rb:251:in `block in codegen_stmts'
        from vgcg.rb:247:in `each'
        from vgcg.rb:247:in `codegen_stmts'
        from vgcg.rb:270:in `codegen'
        from vgcg.rb:282:in `<main>'

vgcg.rb の該当箇所を見てみると下記のようになっています。

def codegen_exp(lvar_names, exp)

  # ...

  left =
    case args[0]
    when Integer
      args[0]
    when String
      case
      when lvar_names.include?(args[0])
        lvar_pos = lvar_names.index(args[0]) + 1
        "[bp-#{lvar_pos}]"
      else
        raise not_yet_impl("left", args[0])
      end
    else
      # ...

ローカル変数には対応済ですが、関数の引数には未対応だったようです。 対応しましょう。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -65,7 +65,7 @@ def codegen_while(fn_arg_names, lvar_names, rest)
   alines << "label while_#{label_id}"
 
   # 条件の評価 ... 結果が reg_a に入る
-  alines += codegen_exp(lvar_names, cond_exp)
+  alines += codegen_exp(fn_arg_names, lvar_names, cond_exp)
   # 比較対象の値(真)をセット
   alines << "  set_reg_b 1"
   alines << "  compare"
@@ -89,7 +89,7 @@ def codegen_while(fn_arg_names, lvar_names, rest)
   alines
 end
 
-def codegen_exp(lvar_names, exp)
+def codegen_exp(fn_arg_names, lvar_names, exp)
   alines = []
   operator, *args = exp
 
@@ -102,6 +102,9 @@ def codegen_exp(lvar_names, exp)
       when lvar_names.include?(args[0])
         lvar_pos = lvar_names.index(args[0]) + 1
         "[bp-#{lvar_pos}]"
+      when fn_arg_names.include?(args[0])
+        fn_arg_pos = fn_arg_names.index(args[0]) + 2
+        "[bp+#{fn_arg_pos}]"
       else
         raise not_yet_impl("left", args[0])
       end
@@ -151,7 +154,7 @@ def codegen_set(fn_arg_names, lvar_names, rest)
       rest[1]
     when rest[1].is_a?(Array)
       exp = rest[1]
-      alines += codegen_exp(lvar_names, exp)
+      alines += codegen_exp(fn_arg_names, lvar_names, exp)
       "reg_a"
     when fn_arg_names.include?(rest[1])
       fn_arg_pos = fn_arg_names.index(rest[1]) + 2
@@ -220,7 +223,7 @@ def codegen_func_def(rest)
     when "set"
       alines += codegen_set(fn_arg_names, lvar_names, stmt_rest)
     when "eq"
-      alines += codegen_exp(lvar_names, stmt)
+      alines += codegen_exp(fn_arg_names, lvar_names, stmt)
     when "return"
       val = stmt_rest[0]
       alines << "  set_reg_a #{val}"

再度実行。

$ ./run.sh 27_blinker.vgt.json 
vgcg.rb:141:in `codegen_exp': Not yet implemented ("operator") ("*") (RuntimeError)
    from vgcg.rb:157:in `codegen_set'
    from vgcg.rb:224:in `block in codegen_func_def'
    from vgcg.rb:199:in `each'
    from vgcg.rb:199:in `codegen_func_def'
    from vgcg.rb:254:in `block in codegen_stmts'
    from vgcg.rb:250:in `each'
    from vgcg.rb:250:in `codegen_stmts'
    from vgcg.rb:273:in `codegen'
    from vgcg.rb:285:in `<main>'

おっと、掛け算がまだなかったですね。 足し算と同じ感じで追加しましょう。

まず VM に命令を追加してから、それに合わせてコード生成器を修正する、 という順番が正攻法な気がしますが、 そんなに難しいことやってないのでコード生成器から先にやってしまっても大丈夫でしょう。

エラーメッセージにしたがってコード生成器を掛け算に対応させます。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -119,6 +119,10 @@ def codegen_exp(fn_arg_names, lvar_names, exp)
     alines << "  set_reg_a #{left}"
     alines << "  set_reg_b #{right}"
     alines << "  add_ab"
+  when "*"
+    alines << "  set_reg_a #{left}"
+    alines << "  set_reg_b #{right}"
+    alines << "  mult_ab"
   when "eq"
     $label_id += 1
     label_id = $label_id

足し算とほぼ同じですね。 reg_areg_b に値をセットし、 mult_ab 命令を実行すると結果が reg_a に入るようにします。 "mult" は "multiply" の略です。

実行するとこんどは VMmult_ab 命令などない! と怒られるので、 命令を追加します。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -173,6 +173,9 @@ class Vm
       when "add_ac"
         add_ac()
         @pc += pc_delta
+      when "mult_ab"
+        mult_ab()
+        @pc += pc_delta
       when "add_sp"
         set_sp(@sp + @mem.main[@pc + 1])
         @pc += pc_delta
@@ -294,7 +297,7 @@ class Vm
       2
     when "set_reg_a", "set_reg_b", "label", "call", "push", "pop", "add_sp", "sub_sp", "jump_eq", "jump"
       1
-    when "ret", "exit", "add_ab", "compare"
+    when "ret", "exit", "add_ab", "compare", "mult_ab"
       0
     else
       raise "Invalid operator (#{operator})"
@@ -346,6 +349,10 @@ class Vm
     @reg_a = @reg_a + @reg_c
   end
 
+  def mult_ab
+    @reg_a = @reg_a * @reg_b
+  end
+
   def set_reg_a(val)
     @reg_a =
       case val

こちらも足し算のコードをコピペしてちょこっと変えるだけですね。 動かしてみます。

$ ./run.sh 27_blinker.vgt.json 
(略)
================================
reg_a(0) reg_b(0) reg_c(0) zf(0)
---- memory (main) ----
      00   ["call", 41]
      02   ["exit"]
      03 ["label", "vram_set"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["sub_sp", 1]
      12   ["set_reg_a", "[bp+4]"]
      14   ["set_reg_b", "w"]
      16   ["mult_ab"]
      17   ["cp", "reg_a", "[bp-1]"]
      20   ["sub_sp", 1]
      22   ["set_reg_a", "[bp-1]"]
      24   ["set_reg_b", "x"]
      26   ["add_ab"]
      27   ["cp", "reg_a", "[bp-2]"]
      30   ["set_vram", "vi", "[bp+5]"]
      33   ["cp", "bp", "sp"]
      36   ["pop", "bp"]
      38   ["ret"]
      39 ["label", "main"]
      41   ["push", "bp"]
      43   ["cp", "sp", "bp"]
      46   ["sub_sp", 1]
      48   ["cp", 5, "[bp-1]"]
      51   ["push", 1]
      53   ["push", 1]
      55   ["push", 2]
pc => 57   ["push", "w"]
      59   ["call", 5]
      61   ["add_sp", 4]
      63   ["push", 1]
      65   ["push", 2]
      67   ["push", 2]
      69   ["push", "w"]
      71   ["call", 5]
      73   ["add_sp", 4]
      75   ["push", 1]
      77   ["push", 3]
      79   ["push", 2]
      81   ["push", "w"]
      83   ["call", 5]
      85   ["add_sp", 4]
      87   ["cp", "bp", "sp"]
      90   ["pop", "bp"]
      92   ["ret"]
---- memory (stack) ----
         35 0
         36 0
         37 0
         38 0
         39 0
         40 0
         41 0
         42 0
sp    => 43 2
         44 1
         45 1
         46 5
   bp => 47 49
         48 2
         49 0
---- memory (vram) ----
..... .....
..... .....
..... .....
..... .....
..... .....

vgvm.rb:214:in `block in start': Not yet implemented ("push") ("w") (RuntimeError)
    from vgvm.rb:142:in `loop'
    from vgvm.rb:142:in `start'
    from vgvm.rb:389:in `<main>'

機械語コードに w が出てくるのはおかしいので、 コード生成器がおかしいはず。 w の参照が解決できてないのでは。

      39 ["label", "main"]
      41   ["push", "bp"]
      43   ["cp", "sp", "bp"]
      46   ["sub_sp", 1]
      48   ["cp", 5, "[bp-1]"]
      51   ["push", 1]
      53   ["push", 1]
      55   ["push", 2]
pc => 57   ["push", "w"]
      59   ["call", 5]

main() が始まって、 vram_set() の呼び出しの前に引数を スタックに push するとこがおかしいようだ、と当たりを付けて調べてみると……。

ここですね。 やはり、参照の解決をしていないようです。

def codegen_func_def(rest)

  # ...

    case stmt_head
    when "call"
      fn_name, *fn_args = stmt_rest
      fn_args.reverse.each {|fn_arg|
        alines << "  push #{fn_arg}" # ←ここ
      }
      alines << "  call #{fn_name}"
      alines << "  add_sp #{fn_args.size}"
    when "call_set"

修正します。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -206,7 +206,20 @@ def codegen_func_def(rest)
     when "call"
       fn_name, *fn_args = stmt_rest
       fn_args.reverse.each {|fn_arg|
-        alines << "  push #{fn_arg}"
+        case fn_arg
+        when Integer
+          alines << "  push #{fn_arg}"
+        when String
+          case
+          when lvar_names.include?(fn_arg)
+            lvar_pos = lvar_names.index(fn_arg) + 1
+            alines << "  push [bp-#{lvar_pos}]"
+          else
+            raise not_yet_impl(fn_arg)
+          end
+        else
+          raise not_yet_impl(fn_arg)
+        end
       }
       alines << "  call #{fn_name}"
       alines << "  add_sp #{fn_args.size}"

動かします。

$ ./run.sh 27_blinker.vgt.json
(略)
================================
reg_a(0) reg_b(0) reg_c(0) zf(0)
---- memory (main) ----
      00   ["call", 41]
      02   ["exit"]
      03 ["label", "vram_set"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["sub_sp", 1]
      12   ["set_reg_a", "[bp+4]"]
      14   ["set_reg_b", "w"]
      16   ["mult_ab"]
      17   ["cp", "reg_a", "[bp-1]"]
      20   ["sub_sp", 1]
      22   ["set_reg_a", "[bp-1]"]
      24   ["set_reg_b", "x"]
      26   ["add_ab"]
      27   ["cp", "reg_a", "[bp-2]"]
      30   ["set_vram", "vi", "[bp+5]"]
      33   ["cp", "bp", "sp"]
      36   ["pop", "bp"]
      38   ["ret"]
      39 ["label", "main"]
      41   ["push", "bp"]
      43   ["cp", "sp", "bp"]
      46   ["sub_sp", 1]
      48   ["cp", 5, "[bp-1]"]
      51   ["push", 1]
      53   ["push", 1]
      55   ["push", 2]
pc => 57   ["push", "[bp-1]"]
      59   ["call", 5]
      61   ["add_sp", 4]
      63   ["push", 1]
      65   ["push", 2]
      67   ["push", 2]
      69   ["push", "[bp-1]"]
      71   ["call", 5]
      73   ["add_sp", 4]
      75   ["push", 1]
      77   ["push", 3]
      79   ["push", 2]
      81   ["push", "[bp-1]"]
      83   ["call", 5]
      85   ["add_sp", 4]
      87   ["cp", "bp", "sp"]
      90   ["pop", "bp"]
      92   ["ret"]
---- memory (stack) ----
         35 0
         36 0
         37 0
         38 0
         39 0
         40 0
         41 0
         42 0
sp    => 43 2
         44 1
         45 1
         46 5
   bp => 47 49
         48 2
         49 0
---- memory (vram) ----
..... .....
..... .....
..... .....
..... .....
..... .....

vgvm.rb:214:in `block in start': Not yet implemented ("push") ("[bp-1]") (RuntimeError)
    from vgvm.rb:142:in `loop'
    from vgvm.rb:142:in `start'
    from vgvm.rb:389:in `<main>'

たぶんこれも push 命令で参照の解決が未実装ですねー。

今までサボッていたツケが回ってきた、と見ることもできますが、 YAGNI でやってるので今が実装のタイミングなのだ、と見ることもできるので、 大丈夫だと思います。 たぶん。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -208,8 +208,16 @@ class Vm
           case arg
           when Integer
             arg
-          when "bp"
-            @bp
+          when String
+            case arg
+            when "bp"
+              @bp
+            when /^\[bp\-(\d+)\]$/
+              stack_addr = @bp - $1.to_i
+              @mem.stack[stack_addr]
+            else
+              raise not_yet_impl("push", arg)
+            end
           else
             raise not_yet_impl("push", arg)
           end

お次はこう:

vgvm.rb:373:in `set_reg_a': Not yet implemented ("val") ("[bp+4]") (RuntimeError)
    from vgvm.rb:154:in `block in start'
    from vgvm.rb:142:in `loop'
    from vgvm.rb:142:in `start'
    from vgvm.rb:397:in `<main>'

修正しまーす。

# Vm#set_reg_a()

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -369,6 +369,9 @@ class Vm
       when /^\[bp-(\d+)\]$/
         stack_addr = @bp - $1.to_i
         @mem.stack[stack_addr]
+      when /^\[bp\+(\d+)\]$/
+        stack_addr = @bp + $1.to_i
+        @mem.stack[stack_addr]
       else
         raise not_yet_impl("val", val)
       end

またこれ:

      03 ["label", "vram_set"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["sub_sp", 1]
      12   ["set_reg_a", "[bp+4]"]
      14   ["set_reg_b", "w"] ← まだ "w" が残ってる
pc => 16   ["mult_ab"]

vgvm.rb:361:in `*': String can't be coerced into Fixnum (TypeError)
    from vgvm.rb:361:in `mult_ab'
    from vgvm.rb:177:in `block in start'
    from vgvm.rb:142:in `loop'
    from vgvm.rb:142:in `start'
    from vgvm.rb:400:in `<main>'

次から次に出てきますね……ガンガンやっつけていきましょう。 codegen_exp() の右辺で参照の解決が未実装でした。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -112,7 +112,21 @@ def codegen_exp(fn_arg_names, lvar_names, exp)
       raise not_yet_impl("left", args[0])
     end
 
-  right = args[1]
+  right =
+    case args[1]
+    when Integer
+      args[1]
+    when String
+      case
+      when fn_arg_names.include?(args[1])
+        fn_arg_pos = fn_arg_names.index(args[1]) + 2
+        "[bp+#{fn_arg_pos}]"
+      else
+        raise not_yet_impl("right", args[1])
+      end
+    else
+      raise not_yet_impl("right", args[1])
+    end
 
   case operator
   when "+"

またなんか似た感じの:

================================
reg_a(1) reg_b("[bp+2]") reg_c(0) zf(0)
---- memory (main) ----
      00   ["call", 41]
      02   ["exit"]
      03 ["label", "vram_set"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["sub_sp", 1]
      12   ["set_reg_a", "[bp+4]"]
      14   ["set_reg_b", "[bp+2]"]
pc => 16   ["mult_ab"]

vgvm.rb:361:in `*': String can't be coerced into Fixnum (TypeError)
    from vgvm.rb:361:in `mult_ab'
    from vgvm.rb:177:in `block in start'
    from vgvm.rb:142:in `loop'
    from vgvm.rb:142:in `start'
    from vgvm.rb:400:in `<main>'

w[bp+2] になりましたが、 こんどは reg_b[bp+2] という文字列がそのまま入っていてダメです。

見てみるとこうなっていて、

  def start
    # ...
      case op
      # ...
      when "set_reg_a"
        val = @mem.main[@pc + 1]
        set_reg_a(val)
        @pc += pc_delta
      when "set_reg_b"
        n = @mem.main[@pc + 1]
        @reg_b = n
        @pc += pc_delta

# ...

  def set_reg_a(val)
    @reg_a =
      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
        @mem.stack[stack_addr]
      else
        raise not_yet_impl("val", val)
      end
  end

set_reg_a 命令では対応済なので、 set_reg_b でも同じようにすればいいでしょう。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -154,8 +154,8 @@ class Vm
         set_reg_a(val)
         @pc += pc_delta
       when "set_reg_b"
-        n = @mem.main[@pc + 1]
-        @reg_b = n
+        val = @mem.main[@pc + 1]
+        set_reg_b(val)
         @pc += pc_delta
       when "set_reg_c"
         n = @mem.main[@pc + 1]
@@ -377,6 +377,22 @@ class Vm
       end
   end
 
+  def set_reg_b(val)
+    @reg_b =
+      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
+        @mem.stack[stack_addr]
+      else
+        raise not_yet_impl("val", val)
+      end
+  end
+
   def compare
     @zf = (@reg_a == @reg_b) ? 1 : 0
   end

お次は?

---- memory (main) ----
      00   ["call", 41]
      02   ["exit"]
      03 ["label", "vram_set"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["sub_sp", 1]
      12   ["set_reg_a", "[bp+4]"]
      14   ["set_reg_b", "[bp+2]"]
      16   ["mult_ab"]
      17   ["cp", "reg_a", "[bp-1]"]
      20   ["sub_sp", 1]
      22   ["set_reg_a", "[bp-1]"]
      24   ["set_reg_b", "[bp+3]"]
      26   ["add_ab"]
      27   ["cp", "reg_a", "[bp-2]"]
pc => 30   ["set_vram", "vi", "[bp+5]"]
      33   ["cp", "bp", "sp"]
      36   ["pop", "bp"]
      38   ["ret"]

vgvm.rb:241:in `[]=': no implicit conversion of String into Integer (TypeError)
    from vgvm.rb:241:in `block in start'
    from vgvm.rb:142:in `loop'
    from vgvm.rb:142:in `start'
    from vgvm.rb:416:in `<main>'

vi は変数名なので機械語コードに出現しているのがおかしい、 というパターンですね。 つまり参照が未解決……。

codegen_set() を修正します。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -188,7 +188,15 @@ def codegen_set(fn_arg_names, lvar_names, rest)
   case dest
   when /^vram\[(.+)\]$/
     vram_addr = $1
-    alines << "  set_vram #{vram_addr} #{src_val}"
+    case
+    when /^\d+$/ =~ vram_addr
+      alines << "  set_vram #{vram_addr} #{src_val}"
+    when lvar_names.include?(vram_addr)
+      lvar_pos = lvar_names.index(vram_addr) + 1
+      alines << "  set_vram [bp-#{lvar_pos}] #{src_val}"
+    else
+      raise not_yet_impl("vram_addr", vram_addr)
+    end
   else
     lvar_pos = lvar_names.index(dest) + 1
     alines << "  cp #{src_val} [bp-#{lvar_pos}]"

どうでしょうか?

---- memory (main) ----
      00   ["call", 41]
      02   ["exit"]
      03 ["label", "vram_set"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["sub_sp", 1]
      12   ["set_reg_a", "[bp+4]"]
      14   ["set_reg_b", "[bp+2]"]
      16   ["mult_ab"]
      17   ["cp", "reg_a", "[bp-1]"]
      20   ["sub_sp", 1]
      22   ["set_reg_a", "[bp-1]"]
      24   ["set_reg_b", "[bp+3]"]
      26   ["add_ab"]
      27   ["cp", "reg_a", "[bp-2]"]
pc => 30   ["set_vram", "[bp-2]", "[bp+5]"]

vgvm.rb:241:in `[]=': no implicit conversion of String into Integer (TypeError)
    from vgvm.rb:241:in `block in start'
    from vgvm.rb:142:in `loop'
    from vgvm.rb:142:in `start'
    from vgvm.rb:416:in `<main>'

vi[bp-2] に置き換わりましたが、まだダメか〜。

修正するぞ〜。

# set_vram

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -238,7 +238,27 @@ class Vm
         arg1 = @mem.main[@pc + 1]
         arg2 = @mem.main[@pc + 2]
 
-        @mem.vram[arg1] = arg2
+        src_val =
+          case arg2
+          when Integer
+            arg2
+          when /^\[bp\+(\d+)\]$/
+            stack_addr = @bp + $1.to_i
+            @mem.stack[stack_addr]
+          else
+            raise not_yet_impl("set_vram", arg2)
+          end
+
+        case arg1
+        when Integer
+          @mem.vram[arg1] = src_val
+        when /^\[bp-(\d+)\]$/
+          stack_addr = @bp - $1.to_i
+          vram_addr = @mem.stack[stack_addr]
+          @mem.vram[vram_addr] = src_val
+        else
+          raise not_yet_impl("set_vram", arg1)
+        end
 
         @pc += pc_delta
       when "get_vram"

どうだ!?

$ ./run.sh 27_blinker.vgt.json 
(略)

================================
reg_a(17) reg_b(2) reg_c(0) zf(0)
---- memory (main) ----
      00   ["call", 41]
pc => 02   ["exit"]
      03 ["label", "vram_set"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["sub_sp", 1]
      12   ["set_reg_a", "[bp+4]"]
      14   ["set_reg_b", "[bp+2]"]
      16   ["mult_ab"]
      17   ["cp", "reg_a", "[bp-1]"]
      20   ["sub_sp", 1]
      22   ["set_reg_a", "[bp-1]"]
      24   ["set_reg_b", "[bp+3]"]
      26   ["add_ab"]
      27   ["cp", "reg_a", "[bp-2]"]
      30   ["set_vram", "[bp-2]", "[bp+5]"]
      33   ["cp", "bp", "sp"]
      36   ["pop", "bp"]
      38   ["ret"]
      39 ["label", "main"]
      41   ["push", "bp"]
      43   ["cp", "sp", "bp"]
      46   ["sub_sp", 1]
      48   ["cp", 5, "[bp-1]"]
      51   ["push", 1]
      53   ["push", 1]
      55   ["push", 2]
      57   ["push", "[bp-1]"]
      59   ["call", 5]
      61   ["add_sp", 4]
      63   ["push", 1]
      65   ["push", 2]
      67   ["push", 2]
      69   ["push", "[bp-1]"]
      71   ["call", 5]
      73   ["add_sp", 4]
      75   ["push", 1]
      77   ["push", 3]
      79   ["push", 2]
      81   ["push", "[bp-1]"]
      83   ["call", 5]
      85   ["add_sp", 4]
      87   ["cp", "bp", "sp"]
      90   ["pop", "bp"]
      92   ["ret"]
---- memory (stack) ----
         41 85
         42 5
         43 2
         44 3
         45 1
         46 5
         47 49
         48 2
sp bp => 49 0
---- memory (vram) ----
..... .....
..@.. .....
..@.. .....
..@.. .....
..... .....

exit

やった〜動いた〜!!

(上に貼ったのは終了時の状態です)

Enter キーを連打してプログラムの実行を進めると、 3つのセルが順番に生存状態になっていくのが VRAM のダンプ表示で確認できました!!!!

グラフィックが動くと、 これまでとは違う種類の手応えがあっていいですね……!!

楽しくなってきた!!


とりあえず動くところまで持って行きたかったので ほぼコピペみたいな感じで参照を解決する部分のコードを書き散らかしてしまいました。

似たような処理がこれだけ多く出現すると さすがにリファクタリングしたくなってきますので、 次回はリファクタリングにしましょう。

あと、ダンプ表示が長くなってきて1画面に収まらなくなってきたので、 そこもどうにかしましょう。

vm2gol v2 製作メモ(26) 配列とVRAM その2 / ダンプ表示の改良


さて、前回やっつけで VRAM を用意しましたが、 今回は VRAM の仕様というか使い方みたいなものを簡単に書いておきます。

あわせて、前回お手軽に inspect で済ませていたダンプ表示を いい感じに修正します。


ライフゲームの盤面のサイズは 縦5 x 横5 = 25 セルとします。

前回 Ruby のコードで書いたように、 次世代の盤面を一時的に置くバッファ領域として 5x5=25 の領域がもう一つ必要です。 これについては、VRAM のサイズを 50 にして、 後ろの方の 25個を使うことにします。

これに関しても、 vram_main, vram_buf のように 2つに分ける方式をちょっと考えた気がしますが、 とりあえず1個のままで進めました。 2つに分けた場合は、VM命令を増やすか、 または VM命令の引数で制御できるように 修正しないといけなくなり、うーんそれはちょっと…… とか、そんなことを考えてたような気がします(忘れました)。


スタック領域のように1行1アドレスの形にすると 表示スペースを取りすぎるので、ダンプではコンパクトに表示させます。 0 か 1 しか入らないし、2次元の表示になってほしいので、

---- memory (vram) ----
..... .....
@.@.. ..@..
.@@.. @.@..
.@... .@@..
..... .....

このように表示されるようにします。 左側がメイン領域、右側がバッファ領域。 . が死んでいるセル、 @ が生きているセルです。


各領域の左上を原点として、 右向きが x 軸、下向きが y 軸とします。

xy座標を VRAM のアドレスに変換するには、 メイン領域の場合は

y * 5 + x

で、バッファ領域の場合はこれにオフセットとして 25 を足してやればよいでしょう。

たとえば原点 (0, 0) にアクセスしたい場合は

メイン領域:        0 * 5 + 0 => 0
バッファ領域: 25 + 0 * 5 + 0 => 25

で、座標 (2, 3) にアクセスしたい場合は

メイン領域:        3 * 5 + 2 => 17
バッファ領域: 25 + 3 * 5 + 2 => 42

という計算で VRAM 用のアドレスに変換できます。

下記はダンプ表示での位置とアドレスの対応関係を図にしたものです。

 0  1  2  3  4 | 25 26 27 28 29
 5  6  7  8  9 | 30 31 32 33 34
10 11 12 13 14 | 35 36 37 38 39
15 16 17 18 19 | 40 41 42 43 44
20 21 22 23 24 | 45 46 47 48 49

では VRAM のダンプ表示部分を修正しましょう。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -18,7 +18,7 @@ class Memory
     # スタック領域
     @stack = Array.new(stack_size, 0)
 
-    @vram = Array.new(10, 0)
+    @vram = Array.new(50, 0)
   end
 
   def dump_main(pc)
@@ -91,8 +91,18 @@ class Memory
     lines.join("\n")
   end
 
+  def format_cols(cols)
+    cols.map{|col| col == 1 ? "@" : "." }.join("")
+  end
+
   def dump_vram
-    @vram.inspect
+    rows = @vram.each_slice(5).to_a
+    main = rows[0..4]
+    buf = rows[5..9]
+
+    (0..4).map {|li| # line index
+      format_cols(main[li]) + " " + format_cols(buf[li])
+    }.join("\n")
   end
 end
 

死亡セルが . 、生存セルが @ となるようにしてみました。

./run.sh 25_vram_set_get.vgt.json を実行すると、 VRAM のダンプ表示のアドレス 0 の箇所が . から @ に変わって また . に戻り、 次に アドレス 1 の箇所が . から @ に変わる、 という挙動が確認できます。

良さそうですね。

vm2gol v2 製作メモ(25) 配列とVRAM / set_vram, get_vram


関数まわりと条件分岐とかが一応できて、入れ子の式も回避方法が決まり…… たぶんまだ足りないところがボロボロ出てくると思いますが、 ライフゲーム作りながら直していきましょう。


まずはライフゲームのロジックの確認のため Ruby で書いてみます。

# coding: utf-8

$w = 8
$h = 6
$grid = []
$buf = []

# init
(0...$h).each {|y|
  $grid[y] = []
  $buf[y] = []
}

(0...$h).each {|y|
  (0...$w).each {|x|
    puts "#{x} #{y}"
    $grid[y][x] = 0
    $buf[y][x] = 0
  }
}

def dump
  (0...$h).each {|y|
    puts $grid[y].map {|v|
      v == 0 ? " " : "@"
    }.join("")
  }
  puts "--------"
end

$grid[0][0] = 1
$grid[0][1] = 1
$grid[0][2] = 1
$grid[1][2] = 1
$grid[2][1] = 1


loop do
  (0...$h).each {|y|
    (0...$w).each {|x|
      xl = (x == 0) ? $w - 1 : x - 1
      xr = (x == $w - 1) ? 0 : x + 1
      yt = (y == 0) ? $h - 1 : y - 1
      yb = (y == $h - 1) ? 0 : y + 1

      n = 0
      n += $grid[yt][xl]
      n += $grid[y ][xl]
      n += $grid[yb][xl]
      n += $grid[yt][x ]
      n += $grid[yb][x ]
      n += $grid[yt][xr]
      n += $grid[y ][xr]
      n += $grid[yb][xr]

      if $grid[y][x] == 0
        if n == 3
          $buf[y][x] = 1
        else
          $buf[y][x] = 0 # 死んだまま
        end
      else
        if n <= 1
          $buf[y][x] = 0
        elsif n >= 4
          $buf[y][x] = 0
        else
          $buf[y][x] = 1
        end
      end
    }
  }

  (0...$h).each {|y|
    (0...$w).each {|x|
      $grid[y][x] = $buf[y][x]
    }
  }

  dump
  sleep 0.1
end

あんまり凝らないようにしてベタに書いてみました。 こんなもんでいいでしょう。 これを vgt のコードに書き換えていきます。


と、これを眺めていると大事なものがまだ用意できていないことに気づきますね? (またこのパターンか〜)

そう、配列です。 これもまじめにやろうとするとヒープ領域を用意して…… となる気がするんですが、ちょっと面倒そうです。

それと、未解決というか決めていなかった問題としてもうひとつ、 画面への出力をどうするかというのがあります。 難しいことはせずに単に端末にプリントするだけでいいでしょ、 程度にぼんやり考えてましたが、さて。 ていうかプリント? コンピュータにおけるプリントとは?

どうしようかなと悩みましたが、 メインメモリ、スタック領域とは別に配列専用の領域を用意して VRAM と兼用することにしました。

ここでもまた我々は初心者なので(難しいことはしてはいけない云々)、というわけです。 締め切りも迫ってるし難しいことやってる余裕はないのです…… とにかくライフゲームが動けばそれでええんや!(とまた言い聞かせる)


※ 「VRAM といったら普通こういうものだ」という知識がないので、 VRAM と呼んではいますがなんか間違ってるかもしれません。 配列と兼用なのも強引な気はしています。自覚はあるのです……。 あとで調べるのです……あとで……。


はい、では VRAM兼配列を用意しましょう。

サイズは固定で、まずは試しということで小さい領域を用意します (あとで大きくします)。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -10,13 +10,15 @@ module TermColor
 end
 
 class Memory
-  attr_accessor :main, :stack
+  attr_accessor :main, :stack, :vram
 
   def initialize(stack_size)
     @main = []
 
     # スタック領域
     @stack = Array.new(stack_size, 0)
+
+    @vram = Array.new(10, 0)
   end
 
   def dump_main(pc)

で、0 はじまりのインデックス (VRAMのアドレス)を指定して値のセットと値の取得ができるようにしましょう。

この2つの VM命令を追加します:

set_vram {VRAMのアドレス} {セットする値}
get_vram {VRAMのアドレス} {取得した値の格納先}

修正します。

VM命令 set_vram を追加:

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -209,6 +209,13 @@ class Vm
         end
         set_sp(@sp + 1)
         @pc += pc_delta
+      when "set_vram"
+        arg1 = @mem.main[@pc + 1]
+        arg2 = @mem.main[@pc + 2]
+
+        @mem.vram[arg1] = arg2
+
+        @pc += pc_delta
       else
         raise "Unknown operator (#{op})"
       end
@@ -255,7 +262,7 @@ class Vm
 
   def self.num_args_for(operator)
     case operator
-    when "cp"
+    when "cp", "set_vram"
       2
     when "set_reg_a", "set_reg_b", "label", "call", "push", "pop", "add_sp", "sub_sp", "jump_eq", "jump"
       1

VM命令 get_vram を追加:

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -216,6 +216,20 @@ class Vm
         @mem.vram[arg1] = arg2
 
         @pc += pc_delta
+      when "get_vram"
+        arg1 = @mem.main[@pc + 1]
+        arg2 = @mem.main[@pc + 2]
+
+        val = @mem.vram[arg1]
+
+        case arg2
+        when "reg_a"
+          @reg_a = val
+        else
+          raise not_yet_impl("arg2", arg2)
+        end
+
+        @pc += pc_delta
       else
         raise "Unknown operator (#{op})"
       end
@@ -262,7 +276,7 @@ class Vm
 
   def self.num_args_for(operator)
     case operator
-    when "cp", "set_vram"
+    when "cp", "set_vram", "get_vram"
       2
     when "set_reg_a", "set_reg_b", "label", "call", "push", "pop", "add_sp", "sub_sp", "jump_eq", "jump"
       1

( ※ get_vram で取得した値をどこに格納するか分岐するように書いていますが、結局 reg_a 以外にセットすることはありませんでした。 )

メインメモリやスタック領域と同じく、 ただの Ruby の配列なので文字列でもオブジェクトでも何でも入れ放題ですが、 ライフゲームのセルごとの生死を入れておくだけなので 数字の 0 または 1 だけを入れるように決めておきます。 0 が死、 1 が生とします。

それから、このままだと中で何が起こってるかが分からないので ダンプ表示に VRAM のダンプを追加します。 まだサイズが小さいですし、まずはお手軽に inspect しとけばいいでしょう。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -90,6 +90,10 @@ class Memory
     end
     lines.join("\n")
   end
+
+  def dump_vram
+    @vram.inspect
+  end
 end
 
 class Vm
@@ -303,6 +307,8 @@ class Vm
 #{ @mem.dump_main(@pc) }
 ---- memory (stack) ----
 #{ @mem.dump_stack(@sp, @bp) }
+---- memory (vram) ----
+#{ @mem.dump_vram() }
     EOB
   end
 

はい。では vgt のコードを書いて動作確認です。 コード生成器の方を修正してないのでまだ動きませんが、 まずはイメージということで。

// 25_vram_set_get.vgt.json

["stmts"
, ["func", "main", []
  , [
      ["var", "x"]

    , ["set", "vram[0]", 1]
    , ["set", "x", "vram[0]"]

    , ["set", "vram[0]", 0]
    , ["set", "x", "vram[0]"]

    , ["set", "vram[1]", 1]
    , ["set", "x", "vram[1]"]
    ]
  ]
]

コード生成器のレイヤーでは、 set を拡張する形で対応させることにします。

( ここらへんになってくると 「そういえば set文ってどうしてたっけ……これちゃんと動くのかな?」 みたいに、なんというか制御しきれてない部分が出てきて、 ちょっと楽しいですね? )

修正します。

codegen_set() で VRAM からの値の取得と、VRAM への値のセットができるようにします。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -156,12 +156,22 @@ def codegen_set(fn_arg_names, lvar_names, rest)
     when fn_arg_names.include?(rest[1])
       fn_arg_pos = fn_arg_names.index(rest[1]) + 2
       "[bp+#{fn_arg_pos}]"
+    when /^vram\[(.+)\]$/ =~ rest[1]
+      vram_addr = $1
+      alines << "  get_vram #{vram_addr} reg_a"
+      "reg_a"
     else
       raise not_yet_impl("set src_val", rest)
     end
 
+  case lvar_name
+  when /^vram\[(.+)\]$/
+    vram_addr = $1
+    alines << "  set_vram #{vram_addr} #{src_val}"
+  else
   lvar_pos = lvar_names.index(lvar_name) + 1
   alines << "  cp #{src_val} [bp-#{lvar_pos}]"
+  end
 
   alines
 end

差分を見やすくするためにインデントを元のままにしています。 この後別コミットでインデントだけ修正しました。

あと、 lvar_name という変数名が実態にそぐわなくなったため dest という名前にリネームしておきました。


では動かしましょう!

================================
reg_a(1) reg_b(0) reg_c(0) zf(0)
---- memory (main) ----
      00   ["call", 5]
      02   ["exit"]
      03 ["label", "main"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["sub_sp", 1]
      12   ["set_vram", 0, 1]
      15   ["get_vram", 0, "reg_a"]
      18   ["cp", "reg_a", "[bp-1]"]
pc => 21   ["set_vram", 0, 0]
      24   ["get_vram", 0, "reg_a"]
      27   ["cp", "reg_a", "[bp-1]"]
      30   ["set_vram", 1, 1]
      33   ["get_vram", 1, "reg_a"]
      36   ["cp", "reg_a", "[bp-1]"]
      39   ["cp", "bp", "sp"]
      42   ["pop", "bp"]
      44   ["ret"]
---- memory (stack) ----
         38 0
         39 0
         40 0
         41 0
         42 0
         43 0
         44 0
         45 0
sp    => 46 1 ... vram[0] から取り出した値がローカル変数 x にコピーされた
   bp => 47 49
         48 2
         49 0
---- memory (vram) ----
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

vram[0] に 1 がセットされ、 その値が reg_a を経由してローカル変数 x にコピーされた直後です。

続きを動かすと、 vram[0] を 0 に戻し、同様に vram[1] に 1 をセットして……というのが確認できます。 良さそうですね!

vm2gol v2 製作メモ(24) 入れ子の式


関数まわりが整備でき、条件分岐ができ、反復処理もできるようになりました。 プログラムを作るのに必要な道具が揃ってきたのでもうそろそろ ライフゲームが書けてしまうのでは!?

……と言いたいところですが、ここで問題が出てきました。


これまで ["+", "a", 1] とか ["eq", 1, 2] のような 単純な式ばかり扱ってきましたが、 ライフゲームのような実際のプログラムを書くとなると、 たとえば

while i < width * height do
  ...
end

とか

if a < 10 && b < 20
  ...
end

みたいに、もう少し複雑な条件式がカジュアルに出現します。

また、 while文や if文の条件の部分以外でも

x = (a * b) - (c * d)

こういう代入も普通ですよね?

vgtコードで書くとこう:

["set"
, "x"
, [
    "-"
  , ["*", "a", "b"]
  , ["*", "c", "d"]
  ]
]

このような入れ子の式は、これまで適当にやってきた「結果を reg_a に入れる方式」 ではうまく計算できません。

たとえば (a * b) - (c * d) の場合、

  • (1) a * b を評価して結果を reg_a に入れる
  • (2) c * d を評価して結果を reg_a に入れる
  • (3) (1) の結果 - (2) の結果reg_a に入れる

という順番で処理すると、 (2) の時点で (1) の結果が上書きされてしまうからです。


Lecture Notes>(6) コード生成1>式のコンパイル
https://chibash.github.io/lecture/os/lang106.html

ところがこのままでは、a - b == c + 1 のような式をコンパイルできない。 c + 1 を実行している間、レジスタ %edx の中に保存された a - b の結果が壊されてしまうからだ。

そうそう、これですよ。

ではどうするかってんで、いくつかの方法を検討しました。


(1) 使っていないレジスタに評価結果を退避させる

  • レジスタの数は有限なので、入れ子の数がレジスタの数で制限されてしまう。
  • また、どの結果がどのレジスタに入っているのか管理しないといけない。
    • さらっと管理と書いたけど、結構めんどくさそうでは?
  • これだけのためにレジスタを追加するのもなー

(2) 途中の評価結果を自動で確保したローカル変数に入れていく。

  • できなくはなさそうだがちょっと手間がかかりそう
  • ちょっとで済む?

(3) 逆ポーランド記法の処理のように、スタックを利用する

  • これもできなくはなさそうだが……
  • スタックを使った処理は知識としてはうっすら知っていて、 ちょっとだけ使ったこともあるけど不安
    • 10年以上前に BibTeX の書式をカスタマイズしたときと PostScript をいじったとき
  • 処理するプログラムの方はまともに作ったことがないので不安

(2)、(3) のスタックを使う方式の場合は、できなくはなさそうなんですが

  • 実装ミスってスタックの状態がおかしくなると辛くなくなるのでは?
  • 後で苦しむのでは?
  • そうならないようにちゃんと実装できる?

というところが不安です……。

そうならないように調べたり試行錯誤してる時間ある? → そんな時間はない(平日は時間がない!!!!)


(4) スタックに固定サイズで領域を確保しておく方式

Lecture Notes>(6) コード生成1>式のコンパイル
https://chibash.github.io/lecture/os/lang106.html

この解説ページは v1 を作っていたときに参考にさせてもらいました。

そこで + のような2オペランドの演算をおこなうときには、左側の式を計算してから右側の式の計算に移る間に、レジスタ %edx の内容をメモリに退避することにする。 退避先として、スタック・フレームを使う。このためスタック・フレームを大きめにとることにする。 (略)

退避先は、式の入れ子の段数だけ必要で、最後に割り当てた退避先から順に不要になることを考えると、スタックを使って管理すればよいことがわかる。そこでスタック・フレームには必ず 32 words(個数はマクロ SAVEDAREA_SIZE で指定)余分に取って、ここを退避領域として使うことにする。固定長なので、式の入れ子の深さが 32 を越えるとコンパイルできなくなるが、今回は無視する。

  • スタック領域が無駄に伸びるとダンプ表示が見にくくなりそう……うーむ

これらを検討して、どうにかしようとしたわけですが……

どうにかしたかったんですよ。 これできるとかっこよくていいじゃないですか。 やりたかったのですが。

この時点で 2週間の期限まであと残り 4,5 日というタイミングだったので、 泣く泣く諦めることにしました。

それでどうしたかというと、

途中の計算結果を明示的にローカル変数に格納する

です。つまり、入れ子の式は使わないことにして、

y * 5 + x == 25

が計算したかったら、

[
  "eq"
, ["+"
    ["*", "y", 5]
  , "x"
  ]
]

じゃなくて、

  ["var", "tmp1"]
, ["set", "tmp1", ["*", "y", 5]]
, ["var", "tmp2"]
, ["set", "tmp2", ["+", "tmp1", "x"]]
, ["eq", "tmp2", 25]]

まあ、このような vgtコードを手で書くわけです……。

負けた感がありますが、 ここで不確実性を取り込むと期限内に完走できなくなる可能性が出てきて、そっちの方が嫌です。

とにかくライフゲームを動かすことが最優先の目的です。 一応回避はできると分かってしまったので、 ダサくても確実なやり方でとにかく逃げ切るべきと判断しました。 この入れ子問題はゴールした後でゆっくり考えればよいと。

いやー仕方ないなー締め切りがなー。 締め切りさえなければなー。


結果的には、入れ子の式を大量に書く必要があって 手で書くと手間がばかにならない……ということにはならなかったので (ライフゲーム自体がそんなに大きなプログラムではないので)、 これはそんなに悪い判断ではなかったんじゃないかなーと思います。

むしろ、ちょっとこだわりすぎた気もして、 無駄に悩まずにさっさと手で書く方式に切り替えていれば、 3, 4日早く完成していたかもしれません。

(ただ、あれこれ考えて試行錯誤すること自体も目的ではありますし、 良い経験だった気がします。 なんとか期限内にはゴールできたので、結果オーライということで……)

v1 ではどうだったか

というわけで、 v2 ではそこらへんの試行錯誤を逐一なぞることはしませんが、 v1 では実際どうだったかというと

  • まず適当に作る(それぞれの評価結果を reg_a に入れる)
  • それっぽく動いたので進める
  • 忘れた頃に正しく動かないケースが発生
  • 何が問題なのか調べる
  • 入れ子の場合におかしくなると分かる
  • うーむ
  • gccコンパイル結果を見てみたり
  • とりあえず適当にレジスタに退避してみる
  • やっぱ適当じゃダメだな……
  • 考えても確信が持てないので調べる
  • 検討するもお手軽にはいかなさそう……(そうでもない?

というのを、while の実装と並行してやっていてグズグズになり、 ここまででも結構時間をロストしていたわけです。

たしかこれで 3,4日くらい悩んでいて、昼休みにもいろいろ調べたりしていました。 どうにかすればできるんだろうけど、そのやり方を理解する時間と、 これ実装を複雑にせずに実現できる? シンプルで簡単な実装ができるか、試している時間は……と考えて、 厳しそうだと判断した気がします。


それと、考えすぎだったということでいえば。

単純な値だけならいいですが、 これってちゃんとやろうとすると

x = (a * 2) + foo(a - 1)

こんなふうに関数が入ってきたらどうなるのか? とか、けっこうややこしい気がするんですよね……。

そこらへんまで考えて 「これはちゃんとやらないといけないな」 みたいな気分になり、あれこれ検討したわけですが、 今になって思えば、 これについてもとりこし苦労だったと思います。

「関数が入ってきたときだけ手動で展開」 という対応でも十分だったんじゃないかと。

, ["call_set", "tmp", ["foo", ...]]
, ["set", "x", ["+", ["*", "a", 2], "tmp"]]

みたいな。


それから、(4) の固定サイズ退避領域の方式はダンプ表示の都合で却下しましたが、 これも今になって考えてみると、 必要な分だけの固定サイズにする作りでも良かった気がしますね。 たとえば 2個とか 3個とか。 それだったらダンプ表示の問題も許容範囲内だったかも。

vm2gol のコード生成器は汎用目的ではなくライフゲーム専用のものですし、 すべてのケースに対応しようとしてある程度十分なサイズを確保しておかないと…… という心配は無用だったと思います。


まあそんなわけで、回避できると分かったので先に進みます。 入れ子の問題はゴールした後の宿題、お楽しみということで……。

おまけ: v1 の完成後に知った・読んだもの

スタックマシン方式

低レイヤを知りたい人のためのCコンパイラ作成入門>スタックマシン
https://www.sigbus.info/compilerbook#%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF%E3%83%9E%E3%82%B7%E3%83%B3

v1 を作った後で読みました。 「スタックマシン」の節に答えが載ってますね。 v2 が終わったらこれで作ってみる予定。

スタックマシンではこの式に限らず、複数の途中結果を持つどのような式でも計算することができます。 スタックマシンを使うと、どのような部分式も、 それを実行した結果として1つの要素をスタックに結果として残すという約束を守っている限り、 上記の方法でうまくコンパイルできるのです。

ローカル変数を自動的に補う方式

このギャップを埋めるために、 計算の途中結果もすべて変数として定義するのがK正規化という変換です (ちなみにK正規化という名前は、ML Kitというコンパイラに由来します)。

速攻MinCamlコンパイラ概説>K正規化(kNormal.ml)
http://esumii.github.io/min-caml/tutorial-mincaml-9.htm

これも v1 を作り終わった後、割と最近読んだ解説。 MinCaml だと K正規化 と呼ばれており、手法として実際に使われているそうです。 なるほど、やっぱりこういうのもありなんですね。