アラン・チューリングという計算機科学者の考えた、 「チューリング・マシン」という仮想の計算機があります。 これは [０を書く]、[１を書く]、[右に進む]、[左に進む] と言った 非常に簡単な命令のみを実行できる想像上の計算機ですが、 我々の使っているパソコンでできるような計算は全て、 チューリングマシン用のプログラムとして書ける、ということが知られています。
…という前置きを付けてなんだか重々しい言語に見えてきたところで(^^;、 たぶんご存じの方も多いと思われる、わずか８文字の組み合わせで ありとあらゆるプログラムを表現する Brainfuck を弄ってみるとしましょう。
>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++
++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>
++++++++[<++++>-]<+.[-]++++++++++.
実行結果↓
Hello World!
処理系は The Brainfuck Archive のページから幾つか手に入ります。 Windows環境なら、compiled/win/BFI.exe が手っ取り早いかと。 The Brainf*ck Programming Language というページ(消滅？) には Erlangによる実装や、80文字×３行！ のソースで書かれたC版簡易インタプリタ（gcc/VC++/DigitalMarsC++では使えました） もありました。
…が、正直、たぶん各自自分でインタプリタを書いてしまうのが一番早いかも。
この言語は、一つの"配列"と、配列上の位置を表す一つの"ポインタ"から成ります。 "配列"の各要素は1バイトの整数で、最初は値は 0 です。 "ポインタ"は最初は配列の先頭を指しています。 この"ポインタ"を動かして"配列"を操作する命令を並べることで、 プログラムができあがります。命令は全部で８種類。
> ポインタを１進める< ポインタを１戻す+ ポインタの指す要素の値を１増やす- ポインタの指す要素の値を１減らす. ポインタの指す要素の値を外に出力, 外から値を入力して、
ポインタの指す場所へ入れる[ ポインタの指す要素の値が 0
だったら対応する次の ] までジャンプ] 対応する前の [ までジャンプもしＣ言語をご存じなら、要するに↓こういう意味です。
> ++ptr;< --ptr;+ ++(*ptr);- --(*ptr);. putchar(*ptr);, *ptr = getchar();[ while(*ptr) {] }配列のサイズは（厳密には無限である必要がありますが…） 特に決まってはいないようで、普通のプログラムを動かすに十分な程度は大きい、 と考えておくことにします。
この言語の全ての仕様は語り終わりました。 あとは色々書いて遊んでみましょう。
旅から無事帰還しましたので連載再開です。 まずは格好いいイディオムとかを意識せずに、適当に書いていくことにします。 最初の題材は、「hoge」と画面に表示するプログラム。 ASCIIコードで 68h 6Fh 67h 65h の４文字を表示すればいいわけなので、
++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++
++++++++.
+++++++.
--------.
--.
読みやすいように適当に改行を入れてあります。
hoge
配列の先頭要素を使って、+や-の連発で欲しい数字を作って出力するだけでした。
68h == 104 == 10*10 + 4 なので、最初に 'h' を作るところはループを使って短くできます。 配列の[0]にループカウンタ、[1]に表示する数を入れています。 じっくりにらむと最初の行が10*10の計算であることがわかるかと思います。
++++++++++[>++++++++++<-]>
++++.+++++++.--------.--.
hoge
これでもう皆さん、上記の Hello World は読めるようになりましたネ。
+[>,.<]
echo プログラム（入力をそのまま出力するプログラム） なぞはそこいらの言語よりよっぽど簡単に書けます。
メモリの [0] と [1] にある数値を足して、 結果を [0] に入れる処理を書いてみましょう。 まずは簡単版。[1]のデータを壊しつつ足し算を行います。 最初の行は入力(1 + 2)で最後の行は出力('3'が出るはず)なので、 実質は２行目のみです。
+>++><<
>[-<+>]<
++++++++++++++++++++++++++++++++++++++++++++++++.
やってることは、Cで書くと while( mem[1] ) { --mem[1]; ++mem[0]; }
です。
次に、[0] や [1] を壊さないで、結果を [2] に入れてみます。 [3] を作業領域として使用します。
+>++><<
[->>>+<<<]
>>>[-<+<<+>>>]<<
[->>+<<]
>>[-<+<+>>]<
++++++++++++++++++++++++++++++++++++++++++++++++.
というアルゴリズムです。
[0] * [1] を [2] に入れる。ただし、[0]は破壊・[3]を作業領域として使う。
++++>++><<
[-
>[->>+<<]
>>[-<+<+>>]
<<<
]>>
++++++++++++++++++++++++++++++++++++++++++++++++.
4*2、要するに '8' が出力される予定。やってることは、
while( mem[0] ) { --mem[0];
while( mem[1] ) --mem[1], ++mem[3];
while( mem[3] ) --mem[3], ++mem[2], ++mem[1];
}
これですね。あまり凝ったことを考えないならば、
ループは全部 while( mem[i] ) { --mem[i]; ... }
の形のものを使うようにすると簡単な気がします。
この言語自体の話を一瞬離れますが、
#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <map>
#include <boost/function.hpp>
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/if.hpp>
#include <boost/lambda/loops.hpp>
using namespace std;
using namespace boost;
using namespace boost::lambda;
int main(int, const char* argv[])
{
typedef vector<unsigned char> Memory;
typedef Memory::iterator Pointer;
cin.unsetf(ios_base::skipws);
// メモリ
Memory imem, dmem(65536);
// プログラム読み込み
ifstream fin(argv[1]);
if( fin )
copy( istream_iterator<char>(fin),
istream_iterator<char>(), back_inserter(imem) );
// ポインタ初期化
Pointer iptr_s=imem.begin(), dptr_s=dmem.begin();
int t_s;
// Bfの各命令に対応する関数の定義
map< char, function<void()> > action_for;
{
var_type<Pointer>::type iptr(var(iptr_s));
var_type<Pointer>::type dptr(var(dptr_s));
var_type<int>::type t(var(t_s));
action_for['>']= ++ dptr;
action_for['<']= -- dptr;
action_for['+']= ++*dptr;
action_for['-']= --*dptr;
action_for['.']= cout << *dptr;
action_for[',']= cin >> *dptr;
action_for['[']= if_( !*dptr )[
for_(t=1, t, ++iptr)[
if_( *iptr == '[' )[ ++t ],
if_( *iptr == ']' )[ --t ]
]];
action_for[']']= (iptr-=2, for_(t=-1, t, --iptr)[
if_( *iptr == '[' )[ ++t ],
if_( *iptr == ']' )[ --t ]
], ++iptr);
}
// 実行。無関係な文字はスキップする
while( iptr_s != imem.end() )
if( function<void()> f = action_for[ *iptr_s++ ] )
f();
}
たぶんこのページを見ている人の99.5%は Let's boost からのお客様なので、せっかくだから boost::lambda を無駄に使ってインタプリタを書いてみました。
「ポインタの指してるデータが 0 でないなら何か処理」は簡単。
前処理 [[-] 0でない場合の処理] 「こっちの値の方が大きければ」とか「データが0ならば」とかの場合は少し問題です。 前者については、とりあえず [ による0か否かの判定にもちこまなくてはならないので、 引き算のような処理をして 0 or not 0 に変形することが必要です。
+++++ # {0} = ?
>+++< # {1} = ?
>[ # while( {1} ) do
<[->>+>+<<<]> # {2:3} = !{0}
>>[-<<<+>>>]<< # {0} = !{3}
>[[-]<<->>]< # if({2}) then decr {0}
- # decr {1}
]< # end
++++++++++++++++++++++++++++++++++++++++++++++++.
えーと、この言語にはコメントなどという軟弱な機能はないので、
上の例の #... というのは、
実際のコードには存在しないものと考えて下さい。
もっとも、[<+.,->] を使わないように注意して"コメント"を書いてあるので、
多くのbf処理系ではそのまま実行できます。
コメント内の {n}はメモリのn番地のことを表し、 !{n} はメモリのn番地の値を取り出して計算につかったあと、 その番地は値0にクリアされる、ことを表している気分です。
真ん中の６行は、「{0}≧{1} なら 何か0以外の値、そうでなければ0」 を計算して {0} に置いておくようなアルゴリズムとなっています。 基本的には、足し算と同じ要領で、{0} から {1} を1ずつ引いていきます。 で、途中で{0}が0になったら{0}を減らすのはやめて、{1}だけを0まで減らす、と。 じっくり睨んで確かめて下さい。
これで「大小比較＆分岐」の準備ができました。
大小比較を実際につかったプログラムを書いてみました。 今度はこれまでのと違って結構なサイズになっています。 お第は、「大文字を小文字に変換しながら表示するecho」。
### init: ##################################
>>++++++++[->++++++++<]> # {3} = 0x40
>>>+++++++++[->++++++++++<]> # {7} = 0x5A ptr=7
### main: ##################################
[<<, # {5} = getchar()
## 00 00 00 40 00 *ch 00 5A 00 00 00
[->+<<+<<+>>>] # {2:4:6} = !{5}
<<<[->>>+<<<]>>> # {5} = !{2}
## 00 00 00 40 ch *ch ch 5A 00 00 00
>>[->+>>+<<<]> # {8:10} = !{7}
## 00 00 00 40 ch ch ch 00 *5A 00 5A
[ # while( {8} ) do
<<[->+>>+<<<]>> # {7:9} = !{6}
>[-<<<+>>>]< # {6} = !{9}
<[[-]<->]> # if({7}) then decr{6}
- # decr {8}
] # end
>>[-<<<+>>>]<<<<< # {7} = !{10}
## 00 00 00 40 ch *ch ans1 5A 00 00 00
## ans1 = 0 iff input le 5A
<<[-<+<<+>>>]< # {0:2} = !{3}
## 40 00 *40 00 ch ch ans1 5A 00 00 00
[ # while( {2} ) do
>>[-<+<<+>>>]<< # {1:3} = !{4}
<[->>>+<<<]> # {4} = !{1}
>[[-]>-<]< # if({3}) then decr{4}
- # decr {2}
] # end
<<[->>>+<<<]>>>>> # {3} = !{0}
## 00 00 00 40 ans2 *ch ans1 5A 00 00 00
## ans2 = 0 iff input le 40
# if(ans2) if(not ans1) {5} add 0x20
<[[-] # if( {4} ) then do
>++++++++++++++++++++++++++++++++ # {5} add 0x20
>[[-] # if( !{6} ) then do
<--------------------------------> # {5} sub 0x20
]<< # end
]>>[-]< # end; !{6}
## 00 00 00 40 00 *ch 00 5A 00 00 00
.>>] # putchar {5}
>>> 実行例 aiueo aiueo HoGe hoge Afajfa;loZjlbzzAaB afajfa;lozjlbzzaab
やっていることは要するに、入力が 0x41以上0x5A以下（大文字の範囲）だったら 32を足して小文字に変換、だけです。
比較計算のたびに値が0に壊されてしまうので毎回コピーを取っているせいで、 少し複雑に見えていますが、ループ内の３つのブロックの内最初の２つは、 前回紹介した大小比較そのものになっています。
ループの最後では、２段の条件判断をしています。 一個目は簡単な「0でなければ何か実行」のパターン、 二個目は「0なら何か実行」のパターン。ここでは、 「0なら32を足す」かわりに「まず32を足して、0でなければ32を引く」 と考えることで、簡単なパターンへ落としました。
上のプログラムにはまだかなり最適化の余地がありますが、 それは置いて置いて、とりあえず全部の命令を繋いでみると圧巻です。
>>++++++++[->++++++++<]>>>>+++++++++[->++++++++++<]>[<<,[->+<<+<<+>>>]<<<[
->>>+<<<]>>>>>[->+>>+<<<]>[<<[->+>>+<<<]>>>[-<<<+>>>]<<[[-]<->]>-]>>[-<<<+
>>>]<<<<<<<[-<+<<+>>>]<[>>[-<+<<+>>>]<<<[->>>+<<<]>>[[-]>-<]<-]<<[->>>+<<<
]>>>>><[[-]>++++++++++++++++++++++++++++++++>[[-]<------------------------
-------->]<<]>>[-]<.>>]
この完成形だけ人に見せると面白いかもしれません。^^;
ここで挙げたプログラムは、単にBrainfuckで書かれているから仕方ないというレベルでなく、遅いです。 もっと高速な小文字化echoが必要な方は、 私があとで改良したバージョン や、それよりも更に速い 花谷さんのバージョン を使ってみてください。
最後に幾つかWeb上の面白いサイトなどをご紹介。
++++++++++[>++++++++++<-]
>++++.+++++++.--------.--." を出力するようなものですね。
優勝者は49文字のbfプログラムでした。
…というわけで、Brainf*ckのお話はここらへんでお終いです。 流石に実用に使うことは絶対無いだろう言語ですし、 ソースの見た目はネタにしか見えないというかネタですが、 それでも基本的なパターンから順に積み上げていくと十分構造的なプログラムが書ける、 というのは面白いところですね。Bfは手続き型変言語の代表例ですが、 例えば関数型変言語の umlambda でこういったことをやってみると、 また別の構成があって楽しいものです。機会があれば皆さんもお試しあれ。
ではではー。
BFで書かれたBFインタプリタ。みじかっ。