Excelのチューリング完全性を検証するためにPietインタプリタを実装しようとして挫折するまでの軌跡
はじめに
最近,Excelがチューリング完全になったという公式のお達しがあった.
Excel formulas, the world’s most popular programming language, is now Turing-complete. Go check it out! https://t.co/qkw3Bmt1gp
— Satya Nadella (@satyanadella) 2021年2月9日
チューリング完全になったということは,レイトレーシングや科学技術計算,言語処理系まで実装できるはずである.本記事では,Excelのチューリング完全性を悪用利用してそこそこ大きめのコード,具体的にはPiet処理系を実装しようとして挫折した流れを記録しようと思う.
Excelのチューリング完全性を支えるLAMBDAについて
詳しくは公式の説明を参照してほしい.簡単に言うと,
LAMBDA(n, n + 1)
のようにLAMBDA(引数1, 引数2, … , 引数n, 式)
の形でlambda抽象を導入できる.今回調べた限り,LAMBDAは次の性質を持つ.
- lambda抽象の状態でセルに配置できない(#CALC!エラーになる).
- lambda抽象自体はオブジェクトとして引き回せる.
- 要は
=LAMBDA(n, n(2))(LAMBDA(k, k+1))
のような記述が許容される.
- 要は
- なぜか計算によっては遅延評価される.
=LAMBDA(n, 3)(1/0)
はエラーにならずに3
と評価された.
Piet処理系を実装しようとして挫折した流れ
挫折した状態のコードは下記にある.
ここでは,これができるに至った経緯を示す.
対象の選定
今回,Excelのチューリング完全性を利用するにあたり,まずはExcelの性質をできる限り利用していこうと考えた.Excelの性質で特筆すべきなのはやはり二次元のデータ構造をナチュラルに扱えることであろう.つまり,実装するものもその性質があることが望ましい.そう,Piet処理系ならそれを満たせる.
Pietとは
Pietはプログラムが抽象画にみえるプログラミング言語である(公式を翻訳).画像上にあるプログラムポインタが,隣り合うふたつの画素の色差を元に計算を実行する.有名なのはこのHelloWorldだろう(DM's Esoteric Programming Languages - Piet Samples).
具体的な計算方法は公式を参照してほしい.ここでは,Pietが次の要素で構成されていることがわかっていればよい.
- プログラム
- 20色で構成された画像.上下左右につながった同色の画素はColour Blocksとよばれる一つの塊として扱われる.
- Program Pointer
- プログラムの実行位置.
- Direction PointerとCodel Chooser
- Program Pointerが次にどの方向へ移動するか.当然,計算中に書き換わる.
- 標準入力
- 数値,もしくは文字を読み取る対象.
- 標準出力
- 数値,もしくは文字を書き出す対象.
- スタック
- 計算の途中結果を書き出せる唯一の対象.
Pietを構成する各要素のExcel上での表現
プログラム
実はここが一番厄介.というのも,作る前からColour Blocks(と隣接)をExcelで直接計算するのは困難だと考えていた.そこで,画像を前処理して「自身が所属するColour Blocksへの参照」と「Colour Blocksの各情報」に分離することを考えた.具体的には,下記の画像のようにした.
上にある画像が「自身が所属するColour Blocksへの参照」である.各Colour Blocksの情報が載っているセルへの参照が文字列で記載されている.
下の表が「Colour Blocksの各情報」である.Colour Blocksの色,Direction PointerとCodel Chooserの値に対応した次のとび先(正確にはその計算に必要なセル参照を示す文字列),Colour Blocksの面積(命令によってこれを参照する場合がある)を事前に計算してある.ここにある情報を利用して,上にある画像に条件付き書式を設定して色付けしている.
Program Pointer
画像のどの位置にあればいいかが分かればいいので,セルへの参照で問題ない.
Direction PointerとCodel Chooser
取る値が決まっているので,とりあえず数値型とした.
標準入力
「標準入力として扱う行の先頭のセル参照」と「読み取るべき相対位置」で実現することにした.事前に文字と数値のパースが済んだ状態にできるのでうれしい.
標準出力
本当は標準入力と対になるように配列にしたかったが,あまりにも組み込み関数が足りないので文字列で妥協した.
スタック
Excelにまともなデータ構造を期待することはできない.しかし,配列で実装しようにも組み込み関数が足りないし,そもそも計算中に破壊的更新はできない.ここで役立つのがLAMBDAである.みんな学部のころに習ったであろうcons, car, cdrのlambdaによる表現がそのまま使えるのである.つまり,スタックの実装は下記で問題ない.
cons = LAMBDA(x,y, LAMBDA(m, m(x, y))) car = LAMBDA(z, z(LAMBDA(p,q, p))) cdr = LAMBDA(z, z(LAMBDA(p,q, q)))
PietインタプリタのLAMBDAによる構成
ここまで出来上がれば,インタプリタの構成は簡単である.メインループは下記の構成でよい.
mainloop = LAMBDA(pp,dp,cc,err,in,inp,out,stack, if(err >= 8, out, LET( ch, INDIRECT(pp), cl, OFFSET(INDIRECT(pp), 0, 1), nh, INDIRECT(OFFSET(INDIRECT(OFFSET(INDIRECT(pp), 0, 2 + dp * 2 + cc)), dy(dp), dx(dp))), nl, OFFSET(INDIRECT(OFFSET(INDIRECT(OFFSET(INDIRECT(pp), 0, 2 + dp * 2 + cc)), dy(dp), dx(dp))), 0, 1), IF(nh = -1, error, IF(OR(ch = 6, nh = 6), nop, switch(10 * hdiff(ch, nh) + ldiff(cl, nl), 1, push, 2, pop, 10, add, 11, subtract, 12, multiply, 20, divide, 21, modulo, 22, notpiet, 30, greater, 31, pointer, 32, switchpiet, 40, duplicate, 41, roll, 42, inn, 50, inc, 51, outn, 52, outc )))(pp,OFFSET(INDIRECT(OFFSET(INDIRECT(pp), 0, 2 + dp * 2 + cc)), dy(dp), dx(dp)),dp,cc,err,in,inp,out,stack) ) ))
要はProgram Pointerから実行すべき命令(error, nop, push, add, … , outc)を選択するだけである.各命令は次に実行すべき形のmainloopを呼び出す.例えば,足し算(add)は下記のようになる.
add = LAMBDA(pp,npp,dp,cc,err,in,inp,out,stack, IF(OR(car(stack) = "!!!error!!!", car(cdr(stack)) = "!!!error!!!"), mainloop(npp, dp, cc, 0, in, inp, out, stack), mainloop(npp, dp, cc, 0, in, inp, out, cons(car(stack) + car(cdr(stack)), cdr(cdr(stack)))) ) )
あとは,mainloopを適切な初期値で呼び出せば動くはずである.
ことの顛末
とりあえず,一番面倒なroll以外が実装できたところで動作確認してみた.結果,#NUM!エラーが返ってきた. Excelになぜかついているデバッガも雑にしか情報を返してこないので役に立たない. LETで適当に変数導入しているのが悪いのかと思い書き換えるも効果なし(正確には,ちょっと計算が進んでいたが最後までたどり着かない).
悶々として1日過ごしてMS公式ページを見ると,下記の注釈があることに気が付いた.
If you call a LAMBDA function from within itself and the call is circular, Excel returns a #NUM! error.
MSは停止性問題を肯定的に解決したどうやら関数呼び出しのネストが深すぎると#NUM!エラーにするらしい.ほとんど末尾呼び出しなんだから最適化してくれてもいいだろうとは思ったが,そうもいかないらしい.つまり,今回の実装方法ではリソースが足りないのでHello Worldすら実行できなかったのである.
私はここで諦めた.
まとめ
Excelは確かにチューリング完全になったかもしれませんが,現実の計算機では制限が強いので大きな計算はできません.いかがでしたか?