vm2gol v2 製作メモ(34) 次世代の生死を決定


もうだんだんライフゲームそのもののコーディングに移ってきたので、

cp 33_adjust_index_2.vgt.json gol.vgt.json

として、以後はこの gol.vgt.json に対して修正を加えていきます。


座標補正ができて、その前に生存セルのカウントも作っていたので、 今回は生存セルの数によって次世代の生死を決定する部分を作ります。

Ruby のコードではこのように書いていました:

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

これをそのまま vgt コードに書き直すと

  // 現在のセルの生死
  ["var", "current"]
, ["call_set", "current"
             , ["vram_get", "w", "h", "x", "y"]
  ]

  // 次世代の生死
, ["var", "next_val"]

, ["case"
  , [["eq", "current", 0]
      ["case"
      , [["eq", "n", 3]
        , ["set", "next_val", 1]]
      , [["eq", 0, 0]
        , ["set", "next_val", 0]]
      ]
    ]
  , [["eq", 0, 0]
      ["case"
      , [["le", "n", 1]
        , ["set", "next_val", 0]]
      , [["ge", "n", 4]
        , ["set", "next_val", 0]]
      , [["eq", 0, 0]
        , ["set", "next_val", 1]]
      ]
    ]
  ]

こうなるんですが、まだ le とか ge を実装してないんですよね。

ここで実装してしまってもいいんですが、 今あるものでどうにかできないかと思って変形してみました。

生存カウントが取りうる値は 0〜8 なので、 「1以下」は「0, 1 のいずれか」 「4以上」は「4, 5, 6, 7, 8 のいずれか」 に変更できます。

こうすると eq だけでいけますね。

// case 文の部分だけ

["case"
, [["eq", "current", 0]
    // 現在の状態が死の場合
  , ["case"
    , [["eq", "n", 3]
      , ["set", "next_val", 1]]
    , [["eq", 0, 0]
      , ["set", "next_val", 0]]
    ]
  ]
, [["eq", 0, 0]
    // 現在の状態が生の場合
  , ["case"
    , [["eq", "n", 0]
      , ["set", "next_val", 0]]
    , [["eq", "n", 1]
      , ["set", "next_val", 0]]
    , [["eq", "n", 4]
      , ["set", "next_val", 0]]
    , [["eq", "n", 5]
      , ["set", "next_val", 0]]
    , [["eq", "n", 6]
      , ["set", "next_val", 0]]
    , [["eq", "n", 7]
      , ["set", "next_val", 0]]
    , [["eq", "n", 8]
      , ["set", "next_val", 0]]
    , [["eq", 0, 0] // 生存カウントが 2 または 3 の場合
      , ["set", "next_val", 1]]
    ]
  ]
]

うーん、 eq だけでなんとかなりますが、 なんだかやぼったいですね。 もうちょっとなんとかならないか……。

( とはいえ、これで正しく動きますし、後からでも修正できるので、 このまま先に進んでも良かったかなという気も。 )

条件をじっくり見てみます。 よく見ると、 「現在の状態が生の場合」 「現在の状態が死の場合」 の両方を合わせても、 次世代が生になるのは3通りしかないことに気づきます。

死 → 生: 生存セル数が 3 の場合だけ
生 → 生: 生存セル数が 2 または 3 の場合だけ

これ以外の場合、次世代は死です。

なるほど……。

現在の状態が生の場合、「0, 1, 4, 5, 6, 7, 8 だったら死、それ以外は生」 じゃなくて「2, 3 だったら生、それ以外は死」 とすると、

["case"
, [["eq", "current", 0]
    // 現在の状態が死の場合
  , ["case"
    , [["eq", "n", 3]
      , ["set", "next_val", 1]]
    , [["eq", 0, 0]
      , ["set", "next_val", 0]]
    ]
  ]
, [["eq", 0, 0]
    // 現在の状態が生の場合
  , ["case"
    , [["eq", "n", 2]
      , ["set", "next_val", 1]]
    , [["eq", "n", 3]
      , ["set", "next_val", 1]]
    , [["eq", 0, 0]
      , ["set", "next_val", 0]]
    ]
  ]
]

やぼったいのがだいぶ解消されました。

さらに、 next_val のデフォルト値を死にしてしまえば、 else 節も省けて 「生になるのが3通り、それ以外は死」を素直に表現したコードになる気がします。

  ["var", "next_val"]
, ["set", "next_val", 0]

, ["case"
  , [["eq", "current", 0]
      // 現在の状態が死の場合
    , ["case"
      , [["eq", "n", 3]
        , ["set", "next_val", 1]]
      ]
    ]
  , [["eq", 0, 0]
      // 現在の状態が生の場合
    , ["case"
      , [["eq", "n", 2]
        , ["set", "next_val", 1]]
      , [["eq", "n", 3]
        , ["set", "next_val", 1]]
      ]
    ]
  ]

いいんじゃないでしょうか。

gol.vgt.json に組み込んで動かします。

--- a/gol.vgt.json
+++ b/gol.vgt.json
@@ -113,6 +113,38 @@
     , ["set", "count", ["+", "count", "tmp"]]
 
     , ["_cmt", "★count_aliveの最後"]
+
+      // ----------------
+
+    , ["_cmt", "★次世代の生死決定の直前"]
+
+      // 注目しているセルの現世代の生死
+    , ["var", "current_val"]
+    , ["call_set", "current_val", ["vram_get", "w", "h", "x", "y"]]
+
+      // 注目しているセルの次世代の生死
+    , ["var", "next_val"]
+    , ["set", "next_val", 0]
+
+    , ["case"
+      , [["eq", "current_val", 0]
+        , ["case"
+          , [["eq", "count", 3]
+            , ["set", "next_val", 1]]
+          ]
+        ]
+      , [["eq", 0, 0]
+        , ["case"
+          , [["eq", "count", 2]
+            , ["set", "next_val", 1]]
+          , [["eq", "count", 3]
+            , ["set", "next_val", 1]]
+          ]
+        ]
+      ]
+
+    , ["_cmt", "★次世代の生死決定の直後"]
+
     ]
   ]

実行。

$ ./run.sh gol.vgt.json 
vgcg.rb:408:in `block in codegen_stmts': Not yet implemented ("stmt_head") ("case") (RuntimeError)
    from vgcg.rb:394:in `each'
    from vgcg.rb:394:in `codegen_stmts'
    from vgcg.rb:47:in `block in codegen_case'
    from vgcg.rb:29:in `each'
    from vgcg.rb:29:in `codegen_case'
    from vgcg.rb:373:in `block in codegen_func_def'
    from vgcg.rb:356:in `each'
    from vgcg.rb:356:in `codegen_func_def'
    from vgcg.rb:398:in `block in codegen_stmts'
    from vgcg.rb:394:in `each'
    from vgcg.rb:394:in `codegen_stmts'
    from vgcg.rb:423:in `codegen'
    from vgcg.rb:435:in `<main>'

case文が入れ子になっていて、 codegen_case() => codegen_stmts() => codegen_case() という流れで呼び出そうとして、 codegen_stmts() から codegen_case() が呼べなくてエラーになっています。

codegen_func_def() から持ってきて codegen_stmts() にコピー:

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -400,6 +400,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 "case"
+      alines += codegen_case(fn_arg_names, lvar_names, stmt_rest)
     when "while"
       alines += codegen_while(fn_arg_names, lvar_names, stmt_rest)
     when "_cmt"

雑にやってますがたぶん大丈夫だろう、という感覚はあります。


さて、実行できるようになったところでこれから動作確認をやっていくわけですが。

動かしてみると、次世代の生死決定の部分に辿り着くまでに 459 ステップかかりました。

================================
459: reg_a(0) reg_b(0) reg_c(0) zf(1)
---- memory (main) ----
      496   ["cp", "reg_a", "[bp-1]"]
      499   ["_cmt", "右下"]
      501   ["push", "[bp-5]"]
      503   ["push", "[bp-3]"]
      505   ["push", "[bp+2]"]
      507   ["_cmt", "call_set~~vram_get"]
      509   ["call", 41]
      511   ["add_sp", 3]
      513   ["cp", "reg_a", "[bp-6]"]
      516   ["set_reg_a", "[bp-1]"]
      518   ["set_reg_b", "[bp-6]"]
      520   ["add_ab"]
      521   ["cp", "reg_a", "[bp-1]"]
      524   ["_cmt", "★count_aliveの最後"]
pc => 526   ["_cmt", "★次世代の生死決定の直前"]
      528   ["sub_sp", 1]
      530   ["push", "[bp+5]"]
      532   ["push", "[bp+4]"]

...

さすがにこのくらいの規模になってくると エンターキー押しっぱなし方式は辛いので、 ステップ実行開始の位置を適宜修正しながら作業します。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -313,8 +313,8 @@ class Vm
       end
 
       dump_v2()
-      $stdin.gets if @step >= 0
-      sleep 0.01
+      $stdin.gets if @step >= 450
+      # sleep 0.01
     end
   end

sleep も外すと一瞬でたどり着きますね。現代のコンピュータはすごい……。


で、動作確認です。

中心のセルに注目して、そのセルの生死と 周囲の生存セルの数を変えて期待する動作になっているか確認していきます。

まずは注目するセル (2, 2) の現世代が死、周囲の生存セル数が 0 の場合。

      // 初期状態の設定
      // 設定なし → すべてのセルが死

    , ["call", "count_alive", "w", "h", 2, 2]

この場合は次世代も死ですね。

================================
516: reg_a(0) reg_b(1) reg_c(0) zf(0)
---- memory (main) ----
      674 ["label", "end_eq_12"]
      676   ["set_reg_b", 1]
      678   ["compare"]
      679   ["jump_eq", 692]
      681   ["jump", 699]
      683 ["label", "when_10_0"]
      685   ["cp", 1, "[bp-8]"]
      688   ["jump", 699]
      690 ["label", "when_10_1"]
      692   ["cp", 1, "[bp-8]"]
      695   ["jump", 699]
      697 ["label", "end_case_10"]
      699   ["jump", 703]
      701 ["label", "end_case_5"]
pc => 703   ["_cmt", "★次世代の生死決定の直後"]
      705   ["cp", "bp", "sp"]
      708   ["pop", "bp"]
      710   ["ret"]
      711 ["label", "main"]
      713   ["push", "bp"]
      715   ["cp", "sp", "bp"]
      718   ["sub_sp", 1]
      720   ["cp", 5, "[bp-1]"]
      723   ["sub_sp", 1]
      725   ["cp", 5, "[bp-2]"]
      728   ["sub_sp", 1]
      730   ["cp", 0, "[bp-3]"]
      733   ["sub_sp", 1]
---- memory (stack) ----
         21 0
         22 15
         23 10
         24 37
         25 542
         26 5
         27 5
         28 2
sp    => 29 0 ... next_val
         30 0 ... current_val
         31 0
         32 3
         33 1
         34 3
         35 1
         36 0 ... count
   bp => 37 47

next_val が 0 になっているので、OKです。


次は死から生になるパターンを見てみましょう。

(1, 1), (2, 1), (3,1) を生にしてみます。

      // 初期状態の設定
    , ["call", "vram_set", "w", 1, 1, 1]
    , ["call", "vram_set", "w", 2, 1, 1]
    , ["call", "vram_set", "w", 3, 1, 1]

    , ["call", "count_alive", "w", "h", 2, 2]
================================
586: reg_a(1) reg_b(1) reg_c(0) zf(1)
---- memory (main) ----
      674 ["label", "end_eq_12"]
      676   ["set_reg_b", 1]
      678   ["compare"]
      679   ["jump_eq", 692]
      681   ["jump", 699]
      683 ["label", "when_10_0"]
      685   ["cp", 1, "[bp-8]"]
      688   ["jump", 699]
      690 ["label", "when_10_1"]
      692   ["cp", 1, "[bp-8]"]
      695   ["jump", 699]
      697 ["label", "end_case_10"]
      699   ["jump", 703]
      701 ["label", "end_case_5"]
pc => 703   ["_cmt", "★次世代の生死決定の直後"]
      705   ["cp", "bp", "sp"]
      708   ["pop", "bp"]
      710   ["ret"]
      711 ["label", "main"]
      713   ["push", "bp"]
      715   ["cp", "sp", "bp"]
      718   ["sub_sp", 1]
      720   ["cp", 5, "[bp-1]"]
      723   ["sub_sp", 1]
      725   ["cp", 5, "[bp-2]"]
      728   ["sub_sp", 1]
      730   ["cp", 0, "[bp-3]"]
      733   ["sub_sp", 1]
---- memory (stack) ----
         21 0
         22 15
         23 10
         24 37
         25 542
         26 5
         27 5
         28 2
sp    => 29 1 ... next_val
         30 0
         31 0
         32 3
         33 1
         34 3
         35 1
         36 3
   bp => 37 47

生になりました!


生 → 死 のパターン

    // 初期状態の設定
    , ["call", "vram_set", "w", 2, 2, 1]

    , ["call", "count_alive", "w", "h", 2, 2]
================================
539: reg_a(0) reg_b(1) reg_c(0) zf(0)
---- memory (main) ----
      674 ["label", "end_eq_12"]
      676   ["set_reg_b", 1]
      678   ["compare"]
      679   ["jump_eq", 692]
      681   ["jump", 699]
      683 ["label", "when_10_0"]
      685   ["cp", 1, "[bp-8]"]
      688   ["jump", 699]
      690 ["label", "when_10_1"]
      692   ["cp", 1, "[bp-8]"]
      695   ["jump", 699]
      697 ["label", "end_case_10"]
      699   ["jump", 703]
      701 ["label", "end_case_5"]
pc => 703   ["_cmt", "★次世代の生死決定の直後"]
      705   ["cp", "bp", "sp"]
      708   ["pop", "bp"]
      710   ["ret"]
      711 ["label", "main"]
      713   ["push", "bp"]
      715   ["cp", "sp", "bp"]
      718   ["sub_sp", 1]
      720   ["cp", 5, "[bp-1]"]
      723   ["sub_sp", 1]
      725   ["cp", 5, "[bp-2]"]
      728   ["sub_sp", 1]
      730   ["cp", 0, "[bp-3]"]
      733   ["sub_sp", 1]
---- memory (stack) ----
         21 0
         22 15
         23 10
         24 37
         25 542
         26 5
         27 5
         28 2
sp    => 29 0 ... next_val
         30 0
         31 0
         32 3
         33 1
         34 3
         35 1
         36 0
   bp => 37 47

いい感じですね!


生 → 生 のパターン

      // 初期状態の設定
    , ["call", "vram_set", "w", 2, 2, 1]
    , ["call", "vram_set", "w", 1, 1, 1]
    , ["call", "vram_set", "w", 1, 2, 1]
    , ["call", "vram_set", "w", 1, 3, 1]

    , ["call", "count_alive", "w", "h", 2, 2]
================================
609: reg_a(1) reg_b(1) reg_c(0) zf(1)
---- memory (main) ----
      674 ["label", "end_eq_12"]
      676   ["set_reg_b", 1]
      678   ["compare"]
      679   ["jump_eq", 692]
      681   ["jump", 699]
      683 ["label", "when_10_0"]
      685   ["cp", 1, "[bp-8]"]
      688   ["jump", 699]
      690 ["label", "when_10_1"]
      692   ["cp", 1, "[bp-8]"]
      695   ["jump", 699]
      697 ["label", "end_case_10"]
      699   ["jump", 703]
      701 ["label", "end_case_5"]
pc => 703   ["_cmt", "★次世代の生死決定の直後"]
      705   ["cp", "bp", "sp"]
      708   ["pop", "bp"]
      710   ["ret"]
      711 ["label", "main"]
      713   ["push", "bp"]
      715   ["cp", "sp", "bp"]
      718   ["sub_sp", 1]
      720   ["cp", 5, "[bp-1]"]
      723   ["sub_sp", 1]
      725   ["cp", 5, "[bp-2]"]
      728   ["sub_sp", 1]
      730   ["cp", 0, "[bp-3]"]
      733   ["sub_sp", 1]
---- memory (stack) ----
         21 0
         22 15
         23 10
         24 37
         25 542
         26 5
         27 5
         28 2
sp    => 29 1 ... next_val
         30 0
         31 0
         32 3
         33 1
         34 3
         35 1
         36 3
   bp => 37 47

これもヨシ!

( ヨシ! とか言ってますが、実はバグがあって、確認ミスしています。 ここは気づかなかったふりをしていったん続けます。 ミスは起こるよということで…… 次の次の回(第36回) でバグが発覚して修正されます )


ひとまず代表的なパターンだけやってみましたが、 不安なので一通り確認しておきます。

とは書いたものの、め、めんどくさい……あ、普通に関数として抽出してしまえばいいのか。

--- a/gol.vgt.json
+++ b/gol.vgt.json
@@ -45,6 +45,32 @@
     ]
   ]
 
+, ["func", "calc_next_gen", ["current_val", "count"]
+  , [
+      // 注目しているセルの次世代の生死
+      ["var", "next_val"]
+    , ["set", "next_val", 0]
+
+    , ["case"
+      , [["eq", "current_val", 0]
+        , ["case"
+          , [["eq", "count", 3]
+            , ["set", "next_val", 1]]
+          ]
+        ]
+      , [["eq", 0, 0]
+        , ["case"
+          , [["eq", "count", 2]
+            , ["set", "next_val", 1]]
+          , [["eq", "count", 3]
+            , ["set", "next_val", 1]]
+          ]
+        ]
+      ]
+    , ["return", "next_val"]
+    ]
+  ]
+
 , ["func", "count_alive", ["w", "h", "x", "y"]
   , [
       ["var", "count"]
@@ -124,24 +150,7 @@
 
       // 注目しているセルの次世代の生死
     , ["var", "next_val"]
-    , ["set", "next_val", 0]
-
-    , ["case"
-      , [["eq", "current_val", 0]
-        , ["case"
-          , [["eq", "count", 3]
-            , ["set", "next_val", 1]]
-          ]
-        ]
-      , [["eq", 0, 0]
-        , ["case"
-          , [["eq", "count", 2]
-            , ["set", "next_val", 1]]
-          , [["eq", "count", 3]
-            , ["set", "next_val", 1]]
-          ]
-        ]
-      ]
+    , ["call_set", "next_val", ["calc_next_gen", "current_val", "count"]]
 
     , ["_cmt", "★次世代の生死決定の直後"]

ここまで来るともう普通の、いつもやってる高級言語リファクタリングですね。

テスト用の関数を用意して、 calc_next_gen() のテストだけ全パターンやってしまいます。

ちゃんとした言語で書いてたら 「ここまでしっかりテストしなくてもええやろ」って思ってしまうところですが、 怪しいコード生成器とアセンブラで作った機械語コードを うさんくさいVMの上で動かしているので まったく油断できません。

, ["func", "test_calc_next_gen", []
  , [
      ["var", "next_val"]

    , ["call_set", "next_val", ["calc_next_gen", 0, 0]]
    , ["_cmt", "★ 死-0 → 死になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 0, 1]]
    , ["_cmt", "★ 死-1 → 死になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 0, 2]]
    , ["_cmt", "★ 死-2 → 死になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 0, 3]]
    , ["_cmt", "★ 死-3 → 生になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 0, 4]]
    , ["_cmt", "★ 死-4 → 死になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 0, 5]]
    , ["_cmt", "★ 死-5 → 死になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 0, 6]]
    , ["_cmt", "★ 死-6 → 死になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 0, 7]]
    , ["_cmt", "★ 死-7 → 死になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 0, 8]]
    , ["_cmt", "★ 死-8 → 死になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 1, 0]]
    , ["_cmt", "★ 生-0 → 死になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 1, 1]]
    , ["_cmt", "★ 生-1 → 死になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 1, 2]]
    , ["_cmt", "★ 生-2 → 生になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 1, 3]]
    , ["_cmt", "★ 生-3 → 生になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 1, 4]]
    , ["_cmt", "★ 生-4 → 死になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 1, 5]]
    , ["_cmt", "★ 生-5 → 死になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 1, 6]]
    , ["_cmt", "★ 生-6 → 死になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 1, 7]]
    , ["_cmt", "★ 生-7 → 死になるはず"]

    , ["call_set", "next_val", ["calc_next_gen", 1, 8]]
    , ["_cmt", "★ 生-8 → 死になるはず"]
    ]
  ]

, ["func", "main", []
  , [
    // ...

    ["call", "test_calc_next_gen"]

    // ...

すべて確認した結果、問題なさそうでした!

確認が済んだので test_calc_next_gen() の呼び出し箇所をコメントアウトしておきます。

--- a/gol.vgt.json
+++ b/gol.vgt.json
@@ -230,11 +230,11 @@
     // , ["call_set", "tmp", ["adjust_index", 5, 1]]
     // , ["_cmt", "★ 座標補正の確認 補正なし: 1 になるべき"]
 
-      ["call", "test_calc_next_gen"]
+    //   ["call", "test_calc_next_gen"]
 
     // ----------------
 
-    , ["var", "w"] // 盤面の幅
+      ["var", "w"] // 盤面の幅
     , ["set", "w", 5]
     , ["var", "h"] // 盤面の高さ
     , ["set", "h", 5]

完成までもうちょっと!!