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正規化 と呼ばれており、手法として実際に使われているそうです。 なるほど、やっぱりこういうのもありなんですね。