gnuplot で brainfuck のインタープリタを作った話

gnuplot とは関数のグラフや実験データをプロットするためのフリーソフトウェアの一つです。例えば,次のようなグラフを描くことができます。

f:id:azapen6:20151203213927p:plain

さて,gnuplot には作業を自動化するためにバッチファイルを読み込んで実行する機能があります。例えば,上のグラフを表示するには,

plot [-5:5] sin(x)
replot cos(x)

という内容を sincos.plt*1 というファイルに書いて,gnuplot 上で

> load "sincos.plt"

というコマンドを入力します。

gnuplot の説明はここまでにして,今回のテーマは gnuplot のバッチファイルで理論上あらゆる計算が実現できるということです。gnuplot のバージョンは 4.4 とします。*2

チューリング完全

まず,あらゆる計算が実現できるということを定めます。

ここでは,計算とは,入力から定められた規則を定められた手続きに従って適用することで出力を構成することを言います。規則というのは,例えば,C言語,BASIC,FortranLISPHaskellJavaPythonRuby といったプログラム言語であり,手続きとはそれらの言語で書かれたプログラムのことです。

今,規則Rによってあらゆる計算が実現できるということを,次のように定めます:

上に挙げたいずれか一つの言語について,その言語で書かれた任意のプログラム(ただし入力を受け取って出力を返すもの。停止しなくてもよい。)を,規則Rを用いた手続きで同じことができるように書き換えられる。

もし上のいずれか一つについて書き換えができるならば,その他すべてについても(自明とは限らない)書き換えができることが知られています。というのも上の言語は相互に書き換えが可能だからです。その意味であらゆる計算が実現できると言うのです。

逆に,規則Rを用いて書かれた手続きのすべてを上のどの言語にも書き換えられることも言えるはずです。なぜなら,規則Rを適用するプログラム(ここでいう gnuplot)は何らかのプログラム言語で書かれているからです。

その意味であらゆる計算が実現できるような規則Rは,最も普遍的なプログラム言語のクラスに属していると考えられます。そのクラスに属するすべての言語は,他の言語と相互に書き換えが可能であり,例えば,C言語と相互に書き換えが可能です。そのような規則はチューリング完全(Turing complete)であると言われます。チューリング完全な規則で記述される手続きを計算と同一視するというのは一種の教義であり,チャーチ・チューリングの提唱(Church-Turing thesis)と呼ばれています。*3

今回のテーマをこの言葉で書き換えるならば,gnuplot のバッチファイルはチューリング完全であるということになります。

数学的な定義

用語の定義として,アルファベット \Sigma とは特別な記号 \bot を含まない有限集合であり,アルファベット \Sigma 上の文字列とは, \Sigma の要素を有限の個数(0個の場合もあり)並べたものを言います。計算機では \Sigma \{ 0, 1 \} を使うことが多いと思いますが,ラテン文字の集合や,ひらがなの集合であっても構いません。意味があるのは有限集合であるという部分だけです。以後,アルファベットは何らかのものに固定されているとして,特に明示せずに「文字列」という言葉を使います。

プログラム言語Lがチューリング完全(上に挙げたような言語のどれかひとつ)であるとき,規則Rがチューリング完全であるとは,RからLへの書き換えが常に実行できることを言います。

それを言うための準備として,LとRのみによって定まる,入力および出力を「翻訳」する関数の組を与えてやる必要があります。なぜなら,Lが受け入れる入力がRにおいて正しい形式であること,またその逆が言えるとは限らないからです。それはここでの計算の本質とは関係ない部分ですが,無視できない問題です。

入力の翻訳関数 T_{L \to R} とは,任意の文字列をRにおいて受け入れられる形式の文字列に写す関数であって,それを計算して必ず停止するプログラムをLによって書くことができるものを言います。

出力の翻訳関数 T_{out} とは,(規則Rの適用によって得られた)文字列を文字列に写す(部分)関数であって,それを計算して必ず停止するプログラムをLによって書くことができるものを言います。

ここまで来て,チューリング完全性を定義する準備ができました。

規則Rがチューリング完全であるとは,チューリング完全なプログラム言語Lを任意にひとつ選んだとき,RとLのみによって決まる翻訳関数の組 T_{L \to R}T_{out} が存在して,Lによって書かれる任意のプログラム P_L に対して,Rで書かれた手続き P_R が存在して,すべての文字列 x について P_R(T_{L \to R}(x)) = T_{out}(P_L(x)) となることを言います。

チューリング完全性において避けられない問題として,計算が一般に停止しないこと,それを判定することが原理的に不可能であるということがあります。つまり,ある  x について  P_L(x) および  P_R(x) の値が確定しない場合が必ず生じます。しかし, P_L(x) が停止しないからといって, P_R(x) が停止しない,あるいはその逆は,必ずしも成り立つとは言えません。

これはなかなか面倒な問題ですが,後に証明に使うインタープリタ方式では,ある入力に対してP_L(x) が停止しないことと, P_R(x) が停止しないことが同値になるようにできます。よって,停止しない場合は元のアルファベットにない特別な記号 \bot を用いて P_R(x) = P_L(x) = \bot とします。

証明方法

規則Rのチューリング完全性を証明するには,上にも書いたように,それを用いてあるプログラム言語Lのすべてのプログラムを書き換えられることを示せばいいということになります。

具体的な方法としては,LのインタープリタをRを用いて作ればいいのです。プログラム言語Lのインタープリタ I_L とは,Lで書かれたプログラム P_L と入力 x を受け取って,それを実行して得られる出力 P_L(x) を返すプログラムであるとします。すなわち,I_L(P_L, x) = P_L(x) です。もしRによってLのインタープリタ I_{L|R} が書けるならば,P_R(x) = I_{L|R}(P_L, x) = P_L(x) より,Rがチューリング完全であることが言えます。

要するに,gnuplot のバッチファイルでいずれかのチューリング完全な言語のインタープリタを作れば,gnuplot のバッチファイルがチューリング完全であるということになります。

brainfuck

とは言うものの,一般的なプログラム言語に対してインタープリタを作ることはあまり簡単ではありません。そこで登場するのが brainfuck*4 という言語です。

brainfuck の特長は何と言っても,チューリング完全であり,かつコンパイラインタープリタが簡単に書けることです。その代わりにプログラムを書くことが非常に難しいという犠牲を払っています。例えば,Hello world プログラムは次のようになります。

+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.
------------.<++++++++.--------.+++.------.--------.>+.

な… 何を言ってるのか わからねーと思うが

言語仕様については

Brainfuck - Wikipedia

を参照。Web上で実行できるインタープリタ

BrainFuckインタープリタ:いで庵

にあります。また,Ideone.com で実行可能な言語にも含まれています。

Online Compiler and IDE >> C/C++, Java, PHP, Python, Perl and 70+ other compilers and interpreters - Ideone.com

ともかく gnuplot のバッチファイルで brainfuckインタープリタを作ればよいという方針が定まりました。

それでは作ってみよう

というわけで作りました。

bfi.plt · GitHub

このバッチファイル群は gnuplot 4.4 で動作しますが,5.0 でも動作確認しています。*5それらは以下の3つのファイルから成り立っています。

bfi.plt: gnuplot 上でロードするファイル
bfi_init.plt: 関数の定義および変数の初期化
bfi_run.plt: インタープリタの本体部

起動するには,カレントディレクトリに上3つのファイルを置いて,変数 program に brainfuck のプログラムを,input に入力のビット列を指定し,bfi.plt をロードします。入力を読まない場合は input は不要です。

それでは先に出した Hello world プログラムを実行してみましょう。

コマンド:

> program = "\
+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.\
------------.<++++++++.--------.+++.------.--------.>+."
> load "bfi.plt"
Hello, world!

(1行目の最後のバックスラッシュ \ は行を継続する記号で,program には \ を除いた一続きの文字列が入ります。)

出た!

別のプログラムでも試してみよう,ということで

Brainfuck -サンプルコードを使って処理の流れを見てみよう。

からFizzBuzzのプログラムを拝借します。

++++++[->++++>>+>+>-<<<<<]>[<++++>>+++>++++>>+++>+++++>+++++>>>>>>++>>++<
<<<<<<<<<<<<<-]<++++>+++>-->+++>->>--->++>>>+++++[->++>++<<]<<<<<<<<<<[->
-[>>>>>>>]>[<+++>.>.>>>>..>>>+<]<<<<<-[>>>>]>[<+++++>.>.>..>>>+<]>>>>+<-[
<<<]<[[-<<+>>]>>>+>+<<<<<<[->>+>+>-<<<<]<]>>[[-]<]>[>>>[>.<<.<<<]<[.<<<<]
>]>.<<<<<<<<<<<]

これを実行すると

> program = "\
++++++[->++++>>+>+>-<<<<<]>[<++++>>+++>++++>>+++>+++++>+++++>>>>>>++>>++<\
<<<<<<<<<<<<<-]<++++>+++>-->+++>->>--->++>>>+++++[->++>++<<]<<<<<<<<<<[->\
-[>>>>>>>]>[<+++>.>.>>>>..>>>+<]<<<<<-[>>>>]>[<+++++>.>.>..>>>+<]>>>>+<-[\
<<<]<[[-<<+>>]>>>+>+<<<<<<[->>+>+>-<<<<]<]>>[[-]<]>[>>>[>.<<.<<<]<[.<<<<]\
>]>.<<<<<<<<<<<]"
> load "bfi.plt"
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
...

出た!!

同じサイトの素数を表示するサンプルコードは,Web上のインタープリタで実行してみたところ間違っているようだったので,ここでは試しません。

とりあえず gnuplot のバッチファイルでちゃんと計算ができるということが分かって頂けたでしょうか。厳密に言うとこのバッチファイルは停止しない限り出力を画面に出さないのですが,出力文字列 ostr を出力と同一視すれば, brainfuck のあらゆるプログラムを実行できることになる,はず。

まとめ

今回は gnuplot のバッチファイルであらゆる計算が実現できることを示しました。そのために brainfuck というプログラム言語(?)のインタープリタgnuplot のバッチファイルで作りました。実は次の記事で他の人が gnuplot のバッチファイルで brainfuckインタープリタを作っていたのですが,

gnuplotで遊ぼう 〜 階乗, フィボナッチ数, Brainfuck処理系まで - プログラムモグモグ

それに書かれていたものは外部プログラムに頼っていて,求めていたものではないと思いました。そこで自分でインタープリタを書いてみたという話でした。

*1:拡張子は特に決まったものはありませんが,この記事では .plt とします。

*2:gnuplot 4.4 は2015年現在では既に古いバージョンです。最近のバージョンではループ処理が普通にできるようになっているため,それなりのプログラムが簡単に書けるようになっています。

*3:理論の世界では,チャーチ・チューリングの提唱に従わない計算モデルは多々あります。

*4:名前がアレなため brainf*ck などと書かれることもあります。

*5:gnuplot のバッチファイルには一般に後方互換性がありません。