■

shinhさんのBrainstuck(id:shinichiro_h:20070714#1184371977)でBrainf*ckを実装する方法を思いついたのだが、書く時間がない。

以下アイデア

必要なBFのセルは1ステップ実行するごとに最大で一個しか増えないので、1ステップ実行するごとにスタック上のBFのセルを全部積みなおして、最後に一個だけ新しいセルを追加する。

すなわち、nステップ後のスタックは(スタックは右に伸びるとする)

BF junk C0 C1 ... Cn

ここで、BFは実行するBFのコード、junkはもう使わないごみ領域、C0が0番目のセル、…、Cnがn番目のセル。

各々のセルはスタックの5エントリを消費して、内容は

C=(clock, value, cursor, pc, end)

ここで、左にある要素ほどスタックの深いところにある。

nステップ後のスタックにおいては、
value はこのセルの現在値。cursor はカーソルがこのセルの位置にあれば1、なければ0。end は常に0。
pc と clock は Cn 以外はゴミで、Cn.pc は次に実行するコードの深さを指す。Cn.clock は n*5。

で、うまくコードを書いてやればn+1ステップ後のスタック

BF junk C0 C1 ... Cn C'0 C'1 ... C'n C'n+1

の形にできてインタープリタが完成する。このコピーの途中で「+-<>」の4命令は実行できる(最初に命令で分岐して、個別に更新しながらコピーを実行)。新しい C'n+1.pc は Cn.pc + n*5 + 5 - 1 にしないといけないのだが、これの計算に C'i.pc の領域をうまく使おう。

残った繰り返し命令がめんどくさいのだが、「通常実行モード」「]を探してる途中」「[を探してる途中」で分けるしかないはず。

実装できるはずなのだが、こいつはめんどうだ。