Excelの数式でチューリングマシンを実装（循環参照版）
このブログエントリは．Spreadsheets/Excel Advent Calendar 2019の17日目です． 1日遅れました，すみません．昨日は胃腸炎で倒れていたので許してください...
なお，この記事は完全にネタなのであしからず．
さて，Excelの数式だけ（VBAは使わない）でどこまでのことが可能なのでしょうか．
そこで，「Excelの数式がチューリング完全ということを示せば，数式だけでなんでもできるのでは？」と考えました．
チューリング完全というのは，要するに普通のプログラミング言語と同等の計算の表現力があるということです．
余談ですが，スーパーマリオメーカーはチューリング完全というのが示されましたね．
これが現代の科学力……！ 「スーパーマリオメーカーはチューリング完全」はなぜたった1年半で証明されたのか (1/2) - ねとらぼ
既存の資源
チューリングマシンが実装できれば，チューリング完全というのを示せるはず... と考えて，Wikipediaの定義を元にチューリングマシンを実装してみることにしました．
チューリングマシンとは，記号列が書かれた長いテープの上を，状態を持つ読み取りヘッドが左右に動きながら記号を読み取り，読み取った記号とマシンの状態によって (1)テープに書き込む記号， (2)ヘッドの動く方向，(3)その後のマシンの状態の3つが決まるというものです．
ググってみると，既にやっている人がいました．
上記の方法では，シートの1つの行を1ステップの計算の状態として使用しています． A列がヘッドの位置のインデックス，B列がマシンの状態，C列以降がテープ上の記号列を表しています． 1行下の数式でその上の行の数式を参照して，次の状態を算出しています．
これでもいいんですが，膨大な数の数式を入れなければならないのでとても重いです． ファイルのサイズが15MBになっていました．
循環参照
なので，循環参照を使って1つの数式だけで完結するようにしました．
こちらが計算シートと，
設定シートです．
やっていることは単純で，さきほど1行ごとに出していたチューリングマシンの状態やテープの情報を，1つの文字列にして結合して1セルに収まるようにしただけです． あとは，RunFlagがブランクになるとリセットされるようにIF関数を入れています．
使い方は，
- Excelの設定で循環参照の再計算の上限を1回にする
- RunFlag (B4セル) を，一度ブランクにして，その後「r」など文字列を入れる．（これでリセットされます）
- F9を押して再計算すると，チューリングマシンが1ステップ進みます．
- ずーーっっとF9を押し続けていると（1分位？），やがて「DONE! ...」となって計算終了です．（エラーのときはエラー値になります）
これは先ほどのリンク先の指数の計算を移植したものです．
1の個数が数値を表しており，入力が_111_111_で3^3を表しています．（他にも例えば_11_1111_なら2^4）
入力が_111_111_のときの出力は，1が27個続いたものになっており，確かに3^3=27が計算されています．
Excelの数式をDRYに書きたい
上記のやつを作ったときに思ったのですが，Excelの数式を1セルにまとめて書こうと思うとどうしても繰り返しが出てきてしまいます． Excelの数式には変数とか，let束縛とか無いから... （そういうときは複数セルに分けるべしというのが公式の見解だと思いますが）
でもそれだと辛い，DRYに書きたい， ということで簡易的にlet束縛みたいな前処理をするスクリプトをJavaScriptで書いてみました．
function replaceAll(target, search, replacement) {
return target.replace(new RegExp(escapeRegExp(search), 'g'), replacement);
}
function escapeRegExp(str) {
return str.replace(/[.*+?^${}()|[\]\\]/g, "\\$&");
}
function parse(code) {
const varAssoc = {};
const substituteVars = val => {
Object.keys(varAssoc).forEach(key =>
val = replaceAll(val, key, "(" + varAssoc[key]+ ")")
);
return val;
};
let returnLine;
code.split("\n").forEach(line => {
if(line.trim() === "") { return; }
const letIdx = line.indexOf("let ");
if(letIdx !== -1) {
const eqIdx = line.indexOf("=");
const varName = line.substring(letIdx + 4, eqIdx).trim();
const varVal = line.substring(eqIdx + 1).trim();
varAssoc[varName] = substituteVars(varVal);
} else {
returnLine = substituteVars(line);
}
});
return returnLine;
}
function p(code) { console.log(parse(code)); }
p(`
let _raw_ = IF(Current = "", setting!InitialData, Current)
let _state_ = LEFT(_raw_, 1)
let _pos_ = VALUE(MID(_raw_, 3, 3)) + 7
let _readchar_ = MID(_raw_, _pos_, 1)
let _writechar_ = VLOOKUP(_state_ & "-" & _readchar_, setting!TransitionTable, 4, FALSE)
let _movedir_ = VLOOKUP(_state_ & "-" & _readchar_, setting!TransitionTable, 5, FALSE)
let _nextpostext_ = TEXT(_pos_ + VLOOKUP(_movedir_, directions!Direction, 2, FALSE) - 7, "000")
let _nextstate_ = VLOOKUP(_state_ & "-" & _readchar_, setting!TransitionTable, 6, FALSE)
let _nextdata_ = _nextstate_ & ";" & _nextpostext_ & ";" & MID(_raw_, 7, _pos_ - 7) & _writechar_ & MID(_raw_, _pos_ + 1, 10000)
=IF(RunFlag="", "", IF(LEFT(Current, 5)="DONE!", Current, IF(_nextstate_ = setting!FinalState, "DONE!" & _nextdata_, _nextdata_)))`);
vscodeで実行するなり，ChromeのDevToolsのコンソールに貼り付けるなりして動かせます．
関数pにlet束縛入り数式を渡すと，変数を数式で置換した結果の数式をconsole.logで出力します．
やっていることは至極単純で，let 変数名 = 数式で変数名と置換後の数式を定義して，その後の数式内に変数名が現れたら単純に置換しているだけです．
（なので変数名の付け方を気をつけないと，変数名の一部だけ置換されておかしなことになります．）
そして，最後の1行の数式（の中の変数名を置換したもの）を結果として出力しています．
ただし，これで何も考えずに巨大な数式を書くとExcelの数式の長さの制限（8,192 文字）を超えてしまうので注意が必要です． なので使い勝手が微妙です．
brainf*ck
チューリングマシンはこれでできたのですが，「もっとプログラミング言語的なことをしたいな」ということで， チューリング完全なプログラミング言語としては最も実装が簡単と言われるbrainf*ckを実装してみようと思い立ちました．
しかし，既にやっている人がいました． orz
下記リンク先のbrainfck実装一覧の中に，Brainf--- interpreter in Excel sheet というのがあり，
それがまさにbrainfckを循環参照をつかって実装しています．
（軽くググっただけでも，日本語圏でも既にやっている人がいました（こっちは循環参照では無いようです）． ExcelでBrainfuck処理系 - プログラムモグモグ， VBA抜きのExcelでBrainfuckインタプリタを作った - うなてっくろぐ）
あと手を付けられるところといえば，複数セルを使っているのを1つにまとめて 使いやすくするとか（保守性は悪くなるけど），などと思いつつ，結局できていません．
まとめ
循環参照の数式のデバッグは大変．
胃腸炎も大変．
