TeX で Brainfuck

TeX というプログラミング言語があります。配列とループがないのが特徴です。配列とループがなくて困ることはあまりありませんが、その数少ない困る場面が、プログラミング言語 Brainfuck の実装でしょう。Wikipedia の記事を読む限り、バイト型の配列とそれを指し示すポインタ、それに while ループさえあれば、Brainfuck は簡単に実装できそうです。

しかし、ないものはないので、別の手段を考えます。ぱっと思いつく配列の実現手段は TeX のレジスタです。レジスタには、ある種のトークンやトークン列を一時的に保存できます。ちなみにトークンというのは TeX の入力の最小単位で、文字や整数のほか、グループ（{...} でくくられたもの）やコントロールシーケンス（\foo のようないわゆる TeX コマンド）も 1つのトークンです。

レジスタにはいろいろな種類があるのですが、個々のレジスタには「種類 + 番号」のような名前が付いています。たとえば整数用のレジスタなら、\count0、 \count1、 \count2、... といった具合です。この整数値を格納できるタイプのレジスタを使えば、番号をインデックスに見立てることで、バイト型の配列的なものが実現できますね。ただ、このインデックスの値をプログラムで足したり引いたりするには、やはりレジスタに収めるしかありません。インデックスは整数なので、整数用のレジスタが余分に 1個必要です。\count0 レジスタを割り当てましょう。

%% init
\countdef\pointer=0
\def\init#1{%
 \count0=0
 \loop \advance\count0 by 1 \global\count\count0=0 \ifnum\count0<#1 \repeat
 \global\pointer=1}

\init{255} とすることで、長さ 255 の配列がゼロに初期化されます。

あとは Brainfuck の仕様に従って処理を実装します。\run{...} で Brainfuck のプログラムが実行されるようにしましょう。

%% run bf program
\long\def\run#1{%
 \init{255}
 \apply#1!\relax}

%% applying each bf command
\def\apply#1{%
 \let\next=\apply
 \if#1>\increment\else
 \if#1<\decrement\else
 \if#1+\incrementp\else
 \if#1-\decrementp\else
 \if#1.\putbyte\else
 \if#1,\getbyte\else
 \if#1!\let\next=\relax\else
   \dowhile{#1}\let\next=\apply
 \fi\fi\fi\fi\fi\fi\fi
 \next}

\apply は、トークンを 1つ取り込み、その種類に応じてインデックスを動かしたり整数レジスタの値を増減したりします。これをトークンがなくなるまで繰り返します。

繰り返し処理がややトリッキーに見えるかもしれませんが、ループのための便利な構文もないし、末尾最適化もしてくれないので、自分で末尾再帰するように書くしかないからです。まあ、なんのことはなくて、次の処理を \next に \let して \next を最後に置けばいいのですが、たとえば再帰するつもりで各 \if 文の中に \apply や \relax を直接置いてしまうと、メモリがうまって止まります。TeXのコマンドは実行時に評価されるわけではなく、定義に書いてあるトークンの列に置き換えられるだけなので、 \apply の素の定義がばらばらばらっと無限に繰り返し展開されてしまうからです。実は TeX の動作というのは、徹頭徹尾「トークンを置き換える」だけであり、この置き換えのルールやタイミングをうまく与えることが TeX プログラミングにほかなりません。

\dowhile 以外の各処理を実装しましょう。入出力がやや面倒ですが、ほかは素直に書けます。

\def\increment{%
 \global\advance\pointer by 1}
\def\decrement{%
 \global\advance\pointer by -1}
\def\incrementp{%
 \global\advance\count\pointer by 1}
\def\decrementp{%
 \global\advance\count\pointer by -1}
\def\putbyte{%
 \ifnum\count\pointer<256
   \char\count\pointer\fi}
\def\getbyte{%
 \read 16 to \getchar
 \ifx\end\getchar\else
   \global\count\pointer=\getchar\fi}

残るは \dowhile ですが、これだけは正直てこずりました。前述のように TeX はトークンを次々に置き換えていくだけなので、簡単には前に戻れない。整数レジスタを使って対応する閉じ括弧 ] を探すことは簡単にできますが、そこまでのトークンをどこかに保持しておいて \apply の引数として渡すといった処理ができない。週末、子供と科学博物館にいったりレゴでアンモナイトを作ったりしてあげている間、ずっと考えてました。



で、最終的に思いついたのが、 [ と ] の \catcode を変更して TeX の字句解析をだます方法。 TeX は対応する {...} で囲まれた部分を 1つのトークンとして読み込むのですが、 Brainfuck の [...] を TeX のグループであるかのように読み込んでしまえば、対応する括弧で囲まれた部分を取り出すという問題そのものが消滅する！

\catcode`\[=1
\catcode`\]=2

%% [ and ] (while loop)
\newif\ifinnerloop

\def\dowhile#1{%
 \ifnum\count\pointer=0 \relax\else
   \loop {\apply#1!}%
     \ifnum\count\pointer=0 \innerloopfalse\else\innerlooptrue\fi
     \ifinnerloop
   \repeat
 \fi}

そんなわけで、たぶん Brainfuck っぽいものができました。とりあえず Wikipedia にあった Hello World! はうごく。

\run{
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.
<<+++++++++++++++.>.+++.------.--------.>+.>.
}

=> Hello'World!Ω

入れ子の括弧も大丈夫。以下は、今回おおいに参考にさせていただいた k.inaba さんのページから、掛け算の例。

\run{
++++>++><<
[-
  >[->>+<<]
  >>[-<+<+>>]
  <<<
]>>
++++++++++++++++++++++++++++++++++++++++++++++++.
}

=> 8

---

FAQ

・「むしろ TeX が brainfucking です。」

クヌース先生に言ってください。しかし、もしかするとあなたが brainfucking だと思っているのは、 TeX ではなく LaTeX のスタイルのほうではないでしょうか。あれは実際、brainfucking です。ドキュメントの見た目を制御するときにワケワカなのと、プログラミングがワケワカなのは、違う話です。スタイルとか気にしないで素の TeX プログラミングをするだけなら楽しいですよ。

・「Hello World! に ' とか Ω とかゴミが出てるけど？」

TeX のデフォルトのテキストフォント cmr10 で、それぞれASCIIコードの 32 と 10 に割り当てられているグリフ（を再現したもの）です。

・「入力のある Brainfuck プログラムから抜けられない」

\end と入力して、? とプロンプトが出たらリターンを押してください。運がよければエラーは出るものの dvi が生成されます。エラーは if 文が閉じてないとかそういうたぐいで、このエラーなしに再帰的なマクロを途中で抜ける方法を私は知りません。

・「The Brainfuck Archive のコードに動かないのがある」

そうですね。

実は 1つごまかしているところがあります。この実装は、 [...] の内側にコマンドが 1つしかない場合に対応していません。たとえば [-] と - を区別できないのです。これは [...] を TeX のグループとして読み込んでいることによる制限です。とはいえ、[-] としたい場面で [<>-] などと書くことにすれば、この制限を回避して等価なコードが記述できます。動作しない Brainfuck プログラムも、そんなふうに改修すれば動くかもしれません。

あと、制限としてはもうひとつ、配列の最大長が 255 です。これは TeX のレジスタが 256 個しかないからです（LuaTeX のような最近の実装を使えば 65535 とかまでいける）。上記のサイトのサンプルはかなり大がかりなものも多いので、この制限にひっかかって動かないものがけっこうありそう。

さらに言い訳が続きますが、上記のサイトのコード例で計算をする系のものには、出力結果を ASCII にしてないものがあるようです。そういうのは DVI や PDF にしたときに文字化けします。