読者です 読者をやめる 読者になる 読者になる

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

主に漫画、数値計算、幾何計算、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 のバッチファイルはチューリング完全であるということになります。

証明方法

規則Rのチューリング完全性を証明するには、上にも書いたように、それを用いてあるプログラム言語Lのすべてのプログラムを書き換えられることを示せばいいということになります。数学的には、プログラム言語Lがチューリング完全であるとき、規則Rがチューリング完全であるとは、Lによって書かれたすべてのプログラム P_L について、Rで書かれた手続き P_R が存在して、すべての x に対して P_R(x) = P_L(x) となると言えます。停止しない場合は P_R(x) = P_L(x) = \bot とします。*3

具体的な方法としては、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 で実行可能な言語にも含まれています。

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 でも動作確認しています。*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:正確にはLとRを入れ替えても同じことが言える必要があるのですが、Rが計算機上で実行される以上はLを用いて書けるので省略しています。

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

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