もうひとつのTeXがチューリング完全であることの証明
この記事はTeX ＆ LaTeX Advent Calendar 2016の17日目の記事です． 2日目はYasuhide Minodaさんでした．18日目はVoDさんです．
はじめに
これまで，TeXがチューリング完全であるかを証明する様々な試みがあった．ここにいくつか挙げておこう．
私の知る限り，そのすべてがTeXの胃，すなわちプリミティブの実行までを使用している．しかし，TeXには胃の前に口，すなわちマクロの展開がある．ここで，気になるのは次の問題である．
この問いに答えるため，簡単なBrainf*ck処理系を作成してみた．それが，次である．
実用するためのプログラムでないため，使い方の説明は省略するが，sample.texの\edefの中にBrainf*ckコードがあり，それが\showによって正しく処理されていることがわかる．\edefの中ではTeXの胃が動かないことがわかっているので，TeXはマクロ展開のみでチューリング完全であることが示された．
この処理系実装には，いくつかの面白い点がある．今回の記事では，そのTeX言語テクニックを紹介していこう．
マクロ展開のみにすることによるメリット・デメリット
テクニックそのものの前に，TeX言語をマクロ展開のみに制限して使用することのメリットとデメリットをまとめておこう．
マクロ展開のみで望んだ結果が得られるマクロのことを，界隈では「完全展開可能な」マクロと呼ぶ．TeX内において，完全展開可能なマクロは制限なく使用することができる．というのも，TeXは文脈によって，完全展開可能であることを要求されるのだ．先のsample.texにおける\edefの中などがそれである．そのような状況でも使用可能なマクロは，他のマクロと組み合わせて使用することが容易である．
デメリットは，完全展開可能であるために，ほとんどの副作用が禁じられる*1点だ．これにより，次のことができなくなる．
- マクロ展開中のマクロ定義
- ラムダ計算のように，その場でマクロを定義できない
- 値の書き換えといった動作も禁止される
- 算術演算
これらの制限により，展開可能なマクロを実装することは困難である．
完全展開可能Brainf*ck処理系実装のためのテクニック
では，完全展開可能Brainf*ck処理系を実装するためのテクニックを見てみよう．
入出力・環境
まずはBrainf*ck処理系を実行していった時のテープなどの状態，すなわち環境をどう表現するかを見ていこう．まず，完全展開可能にする時点で，副作用が一切使えない．よって，直接テープを書き換えるといった実装はできない．ここでは，Brainf*ck処理系を環境を受け取り，環境を返すマクロとして作成することとした．もう少し詳しく説明すると，次のようになる．
Brainf*ck処理系における 環境 とは，(テープ, 入力, 出力, コード) である．テープとは，次節で示す数値を{と}で囲んだものの列である．テープには，読み取り位置という，特別な要素がひとつ存在する．入力と出力はともに文字列である．コードとは<，>，+，-，.，,，[，]から構成される列*2である．
Brainf*ck処理系における評価（→）とは，環境から環境への関数である．評価を複数回適用することを→*で表現する．
初期環境Iを(初期テープ, s, ε, c)とする．ここで初期テープとは，列のすべての要素が0の読み取り位置が左端のテープで，sは任意の文字列，cは任意のコードである．Eをコードが空列の環境とし，I→*Eであるとき，Eの出力を実行結果と呼ぶ．
ここで，本来は→の中身，すなわち評価規則を定義するべきだが，長くなるので省略する*3．評価規則は普通のBrainf*ckなので，定義自体は簡単なはずだ．
今回作成したBrainf*ck処理系とは，この関数→を完全展開可能なマクロとして実装したものにあたる．
数値の表現
ここで，前節で述べなかった数値の定義を示しておこう．当然，TeXの数値は完全展開可能な状況では使いづらいので，使いやすいように定義している．
- 空列εは数値である．
- 任意の数値nに対し,
onは数値である．
よくある自然数の定義法である．ここでは，succを「oを前置する」関数としている*4．
テープの表現
さて，ここで具体的にテープをどう実装したかを述べよう．テープに必要な要件は次である．
- 副作用なしで，読み取り位置を前後させた状態を構築できる
- 副作用なしで，読み取り位置の値を書き換えた状態を構築できる
あ，これ研究室ゼミでみたことある*5．Zipperだ！
Zipperとは，副作用なしで要素をたどり，書き換えるなどの操作ができることができる木やリストなどを実装するためのプログラミング技法である．先の要件を満たすリストはその典型である．例を挙げておこう．
リスト[1,2,3,4]に対し，読み取り位置が要素3の位置にあるとする場合，これを([2,1],[3,4])の組で表現する．読み取り位置を右にずらすときは，右側のリストの先頭を左側のリストの先頭に送る．すなわち([3,2,1],[4])のようになる．現在の読み取り位置の値を書き換えるには，右側のリストの先頭を置換えればよい．([3,2,1],[4])の先頭を42に書き換えると([3,2,1],[42])になる．
さて，これをTeXでどう実装するかである．左側のリストをl1，右側のリストをl2とする．これらは，単純に数値を{と}で囲んだものの列である．これに対し，リストZipperは\@febf@mem@startl1{}{}\curl2で表現される．リストZipperへの操作は，マクロとパターンマッチで実装される．なお，l1の後に不要な{}{}があるように思えるが，これには意味がある．パターンマッチの都合上，左側に最低でも2要素必要だったのだ．
入出力
ここまでで，テープに数値がどのように書き込まれるのかを確認した．ここで問題になるのが入出力である．入出力は文字列なので，文字から自然数への相互変換が必要になってくる．これは，事前に相互変換を行うためのテーブルのようなマクロを用意することとした．ソースコードも分離してあり，in.texが文字から自然数への，out.texが自然数から文字への変換を行うマクロになっている．それぞれの中身を一部見てみよう．
% in.texの一部 \expandafter\def\csname @febf@in@'\endcsname{ooooooooooooooooooooooooooooooooooooooo} \expandafter\def\csname @febf@in@(\endcsname{oooooooooooooooooooooooooooooooooooooooo} \expandafter\def\csname @febf@in@)\endcsname{ooooooooooooooooooooooooooooooooooooooooo} \expandafter\def\csname @febf@in@*\endcsname{oooooooooooooooooooooooooooooooooooooooooo} \expandafter\def\csname @febf@in@+\endcsname{ooooooooooooooooooooooooooooooooooooooooooo}
% out.texの一部 \expandafter\def\csname @febf@out@ooooooooooooooooooooooooooooooooooooooo\endcsname{'} \expandafter\def\csname @febf@out@oooooooooooooooooooooooooooooooooooooooo\endcsname{(} \expandafter\def\csname @febf@out@ooooooooooooooooooooooooooooooooooooooooo\endcsname{)} \expandafter\def\csname @febf@out@oooooooooooooooooooooooooooooooooooooooooo\endcsname{*} \expandafter\def\csname @febf@out@ooooooooooooooooooooooooooooooooooooooooooo\endcsname{+}
文字aから対応する自然数への変換は，\@febf@in@aというマクロで，自然数nから対応する文字への変換は\@febf@out@nというマクロで表現される．これらの変換は\csnameを用いて動的にマクロを呼び出すことによって解決される．
当然，%など，TeXの中で特別な役割を持つ文字を，この方法で変換することは難しい．今回のBrainf*ck処理系の目的は，あくまでチューリング完全性の確認であるから，使用できる文字の集合が小さくなることは許容できるとしている．許容できないという読者は，ぜひ改善してみてほしい．
評価
準備が終わり，あとはコードを評価する部分だけである．この部分は先にコードを示しておこう．
\def\@febf\@febf@mem@start#1\cur#2\inp#3\out#4\code#5{% \expandafter\ifx\csname @febf@#5\endcsname\relax \expandafter\@febf@mem \else \expandafter\@febf@normal \fi{#1}{#2}{#3}{#4}{#5}% }
評価→を表すマクロが，\@febfである．このマクロは引数として\@febf@mem@start#1\cur#2で示されるテープ，#3で入力，#4で出力，そして#5でコードの先頭1文字を取る．このマクロは，基本的に#5がどの文字かによって，どの評価規則を適用するかを決定しているだけである．
ただし，ここで[と]の対応を取る処理をさぼるため，TeXのカテゴリーコードを使った技法を使っている．実は今回の実装では，[と{，]と}を同等にしている．これは，[と]のカテゴリーコードという値を{や}と同一の値にすることで実現している．TeXにおいて，{と}は自動で対応が取られるのはよく知られているであろう．これが[と]にも適用されるのだ．
しかし，この方法を使う場合，TeXのパターンマッチ上，+と[+]など，「1文字」と「[+1文字+]」が区別できないという問題が生じる．幸い，Brainf*ckでは<>が意味のない命令列として使用できるので，この問題はチューリング完全性を確認する目的に対しては障害とならない．
実行結果の取得
評価→が得られたら，最後はそれを可能な限り初期環境に対して適用し，実行結果を得るだけである．しかし，ここでも工夫が必要になる．残念なことに，TeXのマクロ展開はスモールステップなので，可能な限りマクロを展開し続けるという行為もテクニックが必要になるのだ．今回の実装では，\romannumeralトリックと呼ばれる技法を使った．詳しい説明は，すでに公開された記事があるので，そちらを参照してほしい．
