VBA抜きのExcelでBrainfuckの種明かし
完成品はこちら VBA抜きのExcelでBrainfuckインタプリタを作った - うなてっくろぐ
全体的な考え方
例えばBrainfuckの場合、命令ポインタ、データ配列とポインタ、入出力ストリームをまとめて一つの状態と考えると、プログラムの実行は「今の状態と次の命令を見て次の状態を決定する」の繰り返しと考えることができます。命令を見て影響する部分だけ変更できればいいのですが、VBAなしでは特定のセルを動的に書き換えることができません。
そこでシート上の一行をひとつの状態と考え、状態の各要素に「今の命令を実行した後の状態を計算する」という式が入っています。
それぞれの命令が影響する要素をまとめるとこのようになります。
| 命令 | 影響する要素 | 列見出し |
|---|---|---|
| > | データポインタ | p |
| +- | データ配列 | [n] |
| , | データ配列と入力 | p, in |
| . | 出力 | out |
| [] | 命令ポインタ | ip |
命令ポインタ(ip)
ここでは「条件分岐した」状態を作らないといけないので、一つ前の状態を元に判定することになります。
さて、括弧の対応を一つの式で探すのは困難なので、左側にもう一つテーブルを用意しました。まずsp列で[]の深さを数え、end列で「ブロック開始以降で同じ深さになる＝ブロックを抜ける位置」を調べています。
これを使って、
- '['かつポインタの指す値が0、ブロックをスキップする場合
- 「今」に対応するブロック脱出位置をOFFSETで取得
- ']'かつポインタの指す値が0以外、対応する開始位置に戻る場合
- 「今」を脱出位置リストからMATCHで検索＝ブロック開始位置
ということをしています。
データポインタ(p)
命令が'>'なら+1、'<'なら-1するだけですね。
ポインタの指す値を取得するのにOFFSETを使ったところ循環参照だと言われてしまったので、HLOOKUPで見出しから検索しています。OFFSETやINDIRECTといった関数は再計算の際に特殊な扱いをされるらしく、その辺を多用していると時々勘違いされるのだとか。まあ循環参照ではないにせよ計算量増えるのはよくないですね。
参考 http://officetanaka.net/excel/excel2007/051.htm
入力(in)
今何文字目を読み取るかというポインタにしてしまったので、一つ前の命令が','なら+1しています。
出力(out)
命令が'.'なら、*pに入っている文字コードをCHAR関数で文字にして末尾に追加します。
最初はその行で生成された一文字だけを出力して、あとで連結できないかと思ったのですが、セル範囲を渡して文字列連結してくれるような関数が見つからなかったのであきらめました。
ちなみにシート上部のOutputセルは命令ポインタが最後の命令を指す行を探して、その行のoutを取得しています。
データ配列([n])
まず最初にデータポインタが自分を指しているかを確認した上で、'+'なら+1、'-'なら-1しています。8bit符号なしではありません。
','の場合はその行のinが読み取るべき文字を指しているはずなので、Inputのin文字目を取得してCODE関数で文字コードにしています。
