$ \DeclareMathOperator{\arccosh}{arccosh} \DeclareMathOperator{\arcsinh}{arcsinh} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\rot}{rot} \DeclareMathOperator{\grad}{grad} \DeclareMathOperator{\diver}{div} $

Brainfuckインタプリタ

難解プログラミング言語、Brainfuck のインタプリタを Java で実装してみました。
Brainfuck とはなんぞや?という人は、Brainfuck - Wikipedia などをご覧ください。
一番下に簡単な言語仕様とサンプルコードを載せておきます。

1BF インタプリタ

2言語仕様

ある長さ[1]の byte 型配列と、現在その配列のどの位置を指しているのかを示す「ポインタ」があり、それらを以下の8つの命令を用いて操作していきます。 初期状態では、配列の各要素はすべて 0 で埋められており、ポインタは配列の一番最初(一番左)を指しています。
命令
意味
<ポインタの位置を一つ左にずらします
>ポインタの位置を一つ右にずらします
+ポインタが現在指している位置の要素を一つだけ増やします
ただし、現在指している要素が 255(=0xff) だった場合には 0 にします
-ポインタが現在指している位置の要素を一つだけ減らします
ただし、現在指している要素が 0 だった場合には 255(=0xff) にします
.ポインタが現在指している値をアスキーコードとする文字を出力します
,標準入力から値を取得し、ポインタが現在指している位置に書き込みます
[ポインタが現在指している値が 0 ならば、対応する ']' の直後までジャンプします
]対応する前の '[' までジャンプします
これら 8 個の命令が書かれたコードを先頭から呼んでいき、コードの終端まで到達したら終了します。
ちなみに上のアプレットではこの 8 種類の文字以外の文字は無視しています。

[1]この配列の長さが無限の時には、チューリングマシンと同等の計算能力を持つことができるので、その前提の上では例えば C言語で表現できるプログラムはすべて Brainfuck でも表現できます!

3Hello world

これだけだとちょっと寂しいので、「Hello world」と出力するプログラムの書き方を解説してみます。

3.1「H」を表示させるプログラム

いきなり「Hello world」などと (空白を含めて) 11 文字も出力させるなんて難しすぎる! のでまずは一文字目の「H」を表示させて終了する Brainfuck プログラムを作ってみましょう。

3.1.1安直に…

「H」の文字コードは 72 なので、72 回「+」を実行して出力すれば OK です。
++++++++++++++++++++
++++++++++++++++++++
++++++++++++++++++++
++++++++++++.

3.1.2ループを使って短く

しかしこれだとちょっと長いですね…。
他の言語では大抵、同じ命令を何回も実行したい場合には for 文などを使って実現するのではないでしょうか。
そこで「[」や「]」を使えばもっと短いコードにならないか考えてみます。
p[0]++ を n 回実行
while(p[0] != 0){
	p[1]++ を m 回実行
	p[0]--
}
p[1]++ を l 回実行
p[1] を出力
といった処理になるでしょうか。 なお、
\begin{equation} n \times m + l = 72 \end{equation}
(1)
です。
これを Brainfuck コードに書き下してみると、次のようになると思います。
+ ... + (n個)
[
	> + ... + (m個)
	<-
]
> + ... + (l個)
.
すると全コード長は、
\begin{equation} n + m + l + 7 \end{equation}
(2)
なので、 $nm+l=72$ を満たすもののうち、これを最小にする組み合わせは、例えば、
\begin{equation} (n, m, l) = (8, 9, 0) \end{equation}
(3)
とかでしょうか?
結局、以上の議論から導かれるコードは、
++++++++[>+++++++++<-]>.
となります。

3.2Hello world を表示させる!

ループを使って書いてみると、こんな感じになりました。
++++++++[>+++++++++<-]>. # H
<+++++[>++++++<-]>-.     # e
+++++++..                # ll
+++.                     # o
>+++++[>++++++<-]>++.    # (space)
<<++++++++.              # w
--------.                # o
+++.                     # r
------.                  # l
--------.                # d
118文字でした。 あなたはこれより短いコードを書けるでしょうか?