Brainfuckとは < > + - , . [ ] の8命令だけからなるプログラミング言語です。チューリング完全なので、頑張ればどんなプログラムでも書けるハズですが、なにしろ8命令しか無いので書くのはとても大変です。一方、コンパイラやインタプリタを書くのはとても簡単です。
何となく、LinuxをカーネルレベルでBrainfuckに対応させてみます。つまり、Brainf*ckのソースを記述したファイルを読み込むと、それを実行した結果が読み出されるようにカーネルを改変してみます。
といってもパッチ書いたりCでカーネルモジュール書いたりはしません。
カーネルを弄るのに使うのは、カーネルデバッグ用言語SystemTap。（←詳しくはキーワードリンク参照）
本来はデバッグ用ですが、ライブにカーネルの動作を書き換えるという、まともじゃない使い方もできてしまうのです。
(ちなみに、ゆの in SystemTap - ゆの対応カーネルですよ！ - Okiraku Programming と同じ手法です。)
以下はFedora 9で試しました（ubuntu等でも出来るはず）。
なお、SystemTap自身は安全に使えるよう様々なリミッターがかかっていますが、今回それを外しています。
場合によってはカーネルがお亡くなりになったりする可能性があります。壊しては困る環境では実行しないこと。
動かし方
以下の方法であらかじめSystemTapとカーネルデバッグ情報をインストールしておきます。
# yum install kernel-devel systemtap # debuginfo-install kernel
先にbrainfuck用のスクリプトを用意しておきます。ファイル名は「〜.bf」としてください（拡張子固定）。
何でも良いですが、ソース／出力が長過ぎる(1000byte以上)のはちょっとまずいので、HelloWolrd
>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++. [-]>++++++++[<++++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<. +++.------.--------.[-]>++++++++[<++++>-]<+.[-]++++++++++.
とかFizzBuzz
++++++[->++++> >+>+>-<<<<<]>[<++++> >+++>++++> >+++>+ ++++>+++++> > > > > >++> >++<<<<<<<<<<<<<<-]<++++>+++ >-->+++>-> >--->++> > >+++++[->++>++<<]<<<<<<<<<<[->- [> > > > > > >]>[<+++>.>.> > > >..> > >+<]<<<<<-[> > > >]>[<+ ++++>.>.>..> > >+<]> > > >+<-[<<<]<[[-<<+> >]> > >+>+<<<<< <[-> >+>+>-<<<<]<]>>[[-]<]>[> > >[>.<<.<<<]<[.<<<<]>]>.<<<< <<<<<<<]
あたりなら良いでしょう。
なお入力を受け取るスクリプトは、入力文字列をスクリプトの後ろに「 : 」で区切って書いておく必要があります。例えば
+[,.] :Hello,World!
とかです。
ちなみにQuineを動かそうとしても、出力が変わらないのでよく分からないと思います。
こんなもんが本当に動くプログラムなのか？と疑問な方は、色んな人が（もっとまともな方法で）Brainfuck インタプリタやコンパイラを作っていますから、適当に検索して試してみると良いかもです。
さて、今回使うSystemTapなインタプリタを実行しましょう。
本エントリの末尾のスクリプトを「brainfuck.stp」というファイルに保存し、rootで
# chmod 755 brainfuck.stp # ./brainfuck.stp
として実行します。実行すると、Pass 1: ... という表示が出てきます。しばらくして "Pass 5: starting run."と出たら準備完了です。
別ウィンドウにコンソールを開き、用意したBrainf*ckのソースファイルをcatで読んでみましょう。catじゃなくてもlessでもemacsでも大丈夫です。（tacだと特殊な読み方をするためダメなようですが。）
すると、ソースの代わりに実行結果が読み出されているはずです。
% cat hello.bf Hello World!
brainfuck.stpを実行していた端末で Ctrl-C を叩くと元に戻ります。
% cat hello.bf >+++++++++[<++ .....
(なおあまりに重いソースを実行すると、しばらくマシンが固まったようになります。無限ループしても多分1分くらいでSystemTapの安全機構(MAXACTIONS)が働いて強制停止するはずですが、回復しなくなったら諦めて強制リブート…orz)
動作原理
このSystemTapスクリプトを実行すると、システムコールを監視し、名前の末尾が".bf"のファイルをopenシステムコールで開いた際、開いたプロセスとファイルディスクリプタを記憶します（probe syscall.open.return の部分。.returnはシステムコールから復帰する時を表します）。
そのプロセスがそのディスクリプタに対してreadシステムコールを呼び出すと、readから復帰する瞬間にファイルから読み込んだ内容をBrainfuckソースと見なして実行します(probe syscall.read.return の部分)。そして、実行結果でreadに渡されたバッファ($buf。bufはカーネル内の第2引数の変数名です)を上書きします。なおユーザが渡したバッファ長を超えないようにしています。そして、readシステムコールの返り値（長さ）もその大きさに書き換えます。
readするたびにバッファの中身を評価するので、まとめて全体をreadしないと動きません（1byteずつ読まれたりすると実行結果を返す領域もないですし）。
Brainf*ckインタプリタの部分（function eval_bf）は一命令ずつインタプリタ方式で実行しているだけです。
メモリはSystemTapには配列が無いので連想配列で実現しています。
出力は文字列として一文字ずつconcatしています（遅そう）。
ただし、入力を受け取るのは大変なので、スクリプトの後ろに「 : 」で区切って書くことにしています。
当該ディスクリプタをcloseするとbrainf*ck実行対象から外します。(probe syscall.closeの部分)（もしそのディスクリプタをdup2で閉じたら呼ばれないってこと？ あな恐ろしや…）
スクリプト中の %{ 〜 %} の部分は Embedded Cで、SystemTapスクリプトのみではできなかった部分を実装しています。
具体的には、バッファへの上書きや、ASCIIコードと文字の相互変換を実装しています。
後者くらいは標準であっても良い気がするのですが。。。
制限について
stapコマンド（SystemTap実行コマンド）のオプションとして -g -DMAXACTION=99999999 -DMAXSTRINGLEN=1024 -DSTP_NO_OVERLOAD を指定していますが、これはSystemTapの安全措置を緩めるものです。Brainf*ckは実行ステップがかなり掛かるので、こうしないと動きません。
スクリプト
#/bin/sh //usr/bin/stap -vg -DMAXACTION=99999999 -DMAXSTRINGLEN=1024 -DSTP_NO_OVERLOAD $0 ; exit global target_fd probe syscall.open.return { if ($return<0) next # error filename = user_string($filename) len = strlen(filename) ext = substr(filename, len-3,len-1) if (ext == ".bf") { printf("%s(%d) - opening brainf*ck : %d %s\n", execname(), pid(), $return, filename) target_fd[pid(),$return] = 1 } } probe syscall.close { if (!target_fd[pid(), fd]) next printf("%s(%d) - script closed : %d\n", execname(), pid(), fd) delete target_fd[pid(),fd] } probe syscall.read.return { if ($return <= 0) next if (!target_fd[pid(), $fd]) next script = user_string_n($buf, $return) if (strlen(script) < $return) { printf("** failed to load script : %d/%d bytes\n", strlen(script), $return) next } printf("** script loaded : %d bytes\n", $return) result = eval_bf(script) len = strlen(result) $return = $count<len?$count:len if (overwrite($buf, $return, result)) printf("%s(%d) - overwrite read : %d -> %dbyte\n", execname(), pid(), $fd, $return) else printf("%s(%d) - overwrite failed! : %d -> %dbyte\n", execname(), pid(), $fd, $return) } function overwrite:long(buf:long, size:long, result:string) %{ void *buf = (void*)(long)THIS->buf; THIS->__retvalue = 0; if (access_ok(VERIFY_WRITE,buf,THIS->size)) { memcpy(buf, (void*)(long)THIS->result, THIS->size); THIS->__retvalue = 1; } %} function ord:long(c:string) %{ THIS->__retvalue = THIS->c[0]; %} function chr:string(c:long) %{ THIS->__retvalue[0] = THIS->c; THIS->__retvalue[1] = 0; %} global mem[1000000] global stack function eval_bf:string(script:string) { script = tokenize(script, ":") input = tokenize("", ":") len = strlen(script) pos = 0 # inst pointer ptr = 0 # memory pointer inp = 0 # input ptr sp = 0 # stack pointer for [] loop output = "" # output string while (pos < len) { inst = substr(script, pos++, 1) # printf("inst:%d/%d -> %s\t", pos-1, len, inst) if (inst == ">") ptr++ else if (inst == "<") ptr-- else if (inst == "+") {mem[ptr]++ if(mem[ptr] == 256) mem[ptr] = 0} else if (inst == "-") {mem[ptr]-- if(mem[ptr] == -1) mem[ptr] = 255} else if (inst == ".") output .= chr(mem[ptr]) else if (inst == ",") mem[ptr] = ord(substr(input,inp++,1)) else if (inst == "[") { if (mem[ptr]) { stack[sp++] = pos-1; # push [ position # printf("sp:%d -> %d ", sp-1, stack[sp-1]) } else { # jump to corresponding ] skip_lv = 0 while(pos < len && skip_lv >= 0) { inst = substr(script, pos++, 1) if (inst == "[") skip_lv++ if (inst == "]") skip_lv-- } } } else if (inst == "]") { # printf("sp:%d -> %d ", sp-1, stack[sp-1]) if (sp < 0) { printf("invalid ] at pos %d\n", pos) break } pos = stack[--sp] # pop [ position } # printf("mem:%d -> %d\n", ptr, mem[ptr]) } delete mem delete stack return output; }
