あざらしとペンギンの問題

主に漫画、数値計算、幾何計算、TCS、一鰭旅、水族館、鰭脚類のことを書きます。

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)と呼ばれています。

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

数学的な定義

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

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

それを言うための準備として、LとRのみによって定まる、入力および出力を「翻訳」する関数の組を与えてやる必要があります。なぜなら、Lが受け入れる入力がRにおいて正しい形式であること、また、Lの出力に関しても同様であることは、ここで言う意味での計算の本質ではないにもかかわらず、一般的には成り立たないからです。言い換えれば、Rは部分関数であるということです。他方、暗黙の仮定として、Lは文字列から文字列への全域関数であるとします。一般的なプログラム言語(のほとんど)はそれを満たしています。

入力の翻訳関数 T_{L \to R} は、文字列から文字列への写像であって、その結果がRにおいて受け入れられる形式のものであること、加えて、Lにおいて常に正しい計算結果を返す(つまり停止する)ようなプログラムが存在することを言います。

出力の翻訳関数 T_{\mathrm{out}: L \to R} は、文字列から文字列への写像であって、 Rにおいて受け入れられる形式の文字列を受け取り、加えて、Lにおいて常に正しい計算結果を返す(つまり停止する)ようなプログラムが存在することを言います。入力がそれ以外の場合は何を返しても構いませんが、計算の停止性は保証される必要があります。

ここまで来て、規則Rがチューリング完全であることを言う準備ができました。

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

ここでひとつ気づくことがあります。実は、 T_{\mathrm{out}: L \to R} は省くことができます。なぜなら、その計算を  P_L にサブルーチンとして含めることができるからです。 T_{\mathrm{out}: L \to R} が停止することは本質的に重要です。そうでないと、 T_{\mathrm{out}: L \to R} だけでチューリング完全性を言えてしまうことがあるからです。

というわけで、改めて言うと、

規則Rがチューリング完全であるとは、入力の翻訳関数 T_{L \to R} が存在して、Lによって書かれたすべてのプログラム P_L に対して、Rで書かれた手続き P_R が存在して、すべての文字列 x について P_R(T_{L \to R}(x)) = 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*3 という言語です。

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

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

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

言語仕様については

Brainfuck - Wikipedia

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

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

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

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

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

それでは作ってみよう

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

bfi.plt · GitHub

このバッチファイル群は gnuplot 4.4 で動作しますが、5.0 でも動作確認しています。*4それらは以下の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:名前がアレなため brainf*ck などと書かれることもあります。

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