Brainfuckインタープリタ

【プチコン/mkII 両対応】※mkIIのホームメニューには非対応 2012年12月9日 公開


 これはプチコンで動作する難解言語「Brainfuck」のインタープリタです。言語の仕様についてはWikipediaなどを参照してください。また、下記のメニューのBrainfuck入門にも各命令の使い方を記しているのでご覧になってください。
 このプログラムはインタープリタとして動作する最小限の機能のみ搭載し可読性を重視したものとなっています。各命令の実装方法の参考になれば幸いです。これをベースにして自分が使いやすいインタープリタを作るのがベターかもしれません。プチコン上でお手軽にBrainfuckのコーディングを楽しみたい人はPetit Brainfuckの方がおすすめです。

 このページでは前半でこのシンプルなプログラム「Brainfuckインタープリタ」について書いており、後半ではBrainfuckのインタープリタの作り方とBrainfuckそのものについて解説していきます。(たぶん、後半がメインかも)



《 プログラムリスト 》

CLS:CLEAR
MAX=30000:DIM P(MAX)
L=LEN(MEM$)-1
FOR I=0TO L
P$=MID$(MEM$,I,1)
 IF P$==">"THEN C=C+1:IF C>=MAX THEN C=0
 IF P$=="<"THEN C=C-1:IF C<0 THEN C=MAX-1
 IF P$=="+"THEN P(C)=P(C)+1:IF P(C)>255 THEN P(C)=0
 IF P$=="-"THEN P(C)=P(C)-1:IF P(C)<0 THEN P(C)=255
 IF P$=="."THEN ?CHR$(P(C));
 IF P$==","THEN GOSUB @GETCHAR
 IF P$=="["THEN GOSUB @WHILE
 IF P$=="]"THEN GOSUB @WEND
NEXT
END

@GETCHAR
K$=INKEY$()
IF K$==""THEN @GETCHAR
P(C)=ASC(K$):RETURN

@WHILE
IF P(C) THEN RETURN
N=0
FOR J=I TO L
 P$=MID$(MEM$,J,1)
 IF P$=="]" THEN N=N-1
 IF P$=="[" THEN N=N+1
 IF N==0 THEN I=J:J=L
NEXT
RETURN

@WEND
IF P(C)==0 THEN RETURN
N=0
FOR J=I TO 0STEP -1
 P$=MID$(MEM$,J,1)
 IF P$=="]" THEN N=N-1
 IF P$=="[" THEN N=N+1
 IF N==0 THEN I=J:J=0
NEXT
RETURN
QRコード(ファイル名:OCHABRFK)
QRコード

《 使用方法 》

 実行前にMEM$にBrainfuckのソースコードを入れておいてください。このプログラム単体では編集はできないためPETIT EDITORなどを使って編集するとよいでしょう。実行モードで MEM$="++++++++[>++++++++<-]>+." のようにしてMEM$に直接代入してもOKですが、その場合は最大26文字までのコードしか実行できません。
 実行すると出力結果を表示して終了します。出力命令 " . " を用いて適切な出力を行わない場合は画面上には何も表示されません。

《 改造について 》

 このプログラムは冒頭に書いているようにインタープリタとして必要最低限の機能しか実装していません。そのため必要に応じて様々な機能を追加すると良いでしょう。
 考えられる機能は、現在Brainfuckのソースコードのどの部分を実行しているのかを視覚的に分かりやすくしたりとか、実行速度を変えられるようにしたりとか、現在操作しているポインタの値を分かりやすく表示するとかがあります。
 それらの機能はすでにPetit Brainfuckに搭載されていますのでそれを参考にすると良いかも知れません。(1画面のリストサイズに抑えているためプログラムリストの可読性は著しく低いけど)

《 インタープリタの作り方 》

 ここではBrainfuckのインタープリタの作り方について書いていきます。
 インタープリタを作るのに必要なのは構文解析ですが、Brainfuckはすべての命令が1文字で表現されしかも引数もないので構文解析は非常に簡単です。具体的に書くと単純にコードをMID$で1文字ずつ抽出すればそれが命令になるわけですからね。したがって、行うべきことは各命令を実行する処理を実装するだけですが、まず、命令の実装の前に配列変数を確保しておきます。これはBrainfuckではポインタ操作用に十分な量の配列が必要なためです。

 実装するのが簡単な命令は、"+"、" - "、" > "、" < "の4つでしょう。

 最初にポインタの値のインクリメントとデクリメントを行う "+" と " - " について書きます、Brainfuckではポインタの値は0〜255(byte型の整数)となっているためインクリメントを行う場合は255を越えた時に0にしてデクリメントを行う場合には0より小さくなった場合には255にする必要があります。(つまり、256=0で、-1=255ということ)
 次にポインタ操作をする " > "と" < " について書きます。ポインタを1進める" > " によって操作するポインタを進めていくと定義している配列の上限を超える場合があります。この場合にどのような処理を行うかはBrainfuckでは定義されてないためインタープリタに依存する形になります。
 ここでは、ポインタの値と同じく数値が循環するように設定することにしましょう。配列の定義数を変数MAXとした場合には確保される配列は0〜MAX-1であるためMAX-1を越えたら0にする必要があります。同様に" < " では0を下回った場合にもエラーが出てしまうため0より小さくなった場合にはMAX-1になるようにする必要があります。

 次に入出力の命令について書いていきます。
 出力を行う " . " はBrainfuckではそのキャラコードを表示するように定義されているためBASICではCHR$関数を使ってPRINT命令で表示すればいいので簡単です。1文字ずつ表示する場合には横に並んでいた方が分かりやすいのでLOCATEで指定するか、PRINT命令の最後に" ; " を付けて結合処理を行うと良いでしょう。
 入力を行う " , " はポインタに1バイト(0〜255)の値を入力する命令ですが、どのように行うかはBrainfuckでは定義されていません。ここでは入力がお手軽なINKEY$を使って処理を行いましょう。難しいことは何もなくキー入力があるまでずっと待つだけです。

 このようにBrainfuckの命令はシンプルで分かりやすいため実装は非常に楽なのですが、ループ命令である " [ " と " ] " だけは実装の難易度は少しだけ高くなっています。
 これは一般的な構造化命令に対応したBASICならば WHILEWEND 、C言語ならばwhile(){} に相当するものです。条件を満たしている間のみループ内が実行され条件を満たさなくなったらループから脱出(最初から条件を満たしてないときはスキップ)されるのです。

 仕様上は入れ子(多重ループ)もサポートしているのですが、その最も簡単な実装方法を書いていきます。
 まずは下記のような2重ループで記されたコードがあるとします。

命令1
[
命令2
[
命令3
]
命令4
]
命令5
A
B
C
D

 この場合にもしも多重ループに対応していない場合はAからCにジャンプする可能性があります。
 では、どのような動作をするのが正しいのでしょうか。これは一般的なプログラミング言語を習得済みの人ならば一目瞭然ですが、それをコーディングするためには具体的に言葉で説明できる必要があります。(言葉でなくてもフローチャートで説明できれば十分だけど)
 Aの時点で命令を満たしている(=ポインタが指す値は0以外)場合は命令2が実行され、条件を満たしてない(=ポインタが指す値は0)場合はDの後の命令5が実行されます。Bの時点で命令を満たしている場合は命令3が実行され、条件を満たしてない場合はCの後の命令4が実行されます。
 また、Cの時点で命令を満たしている場合はBの後の命令3が再び実行され、条件を満たしてない場合はループを抜けて命令4が実行されます。Dの時点で条件を満たしている場合はAの後の命令2が再び実行され、条件を満たしてない場合はループを抜けて命令5が実行されます。

 このように言葉で書くと非常にややこしく感じるかもしれませんが、それをコーディングする場合にはすごくシンプルに表現が可能です。実は " [ " と " ] " の数は等しくなっているのです。別の言い方をすればネストをカウントしていきネストがゼロの状態でループを抜けるというわけです。
  " [ " はAの時点で条件を満たしてない場合は順番にリストの後の方を見ていくと " [ " はA、Bの2つ、" ] " はC、Dの2つであるためDの後に抜けることはすぐに分かります。これがDだとその逆になり、リスト先頭に向かってカウントするだけです。

 あとはこれをプチコンのsmile basicでコーディングするだけですが、 " [ " を実行する場合に条件を満たしている時はループ内が実行されるのでそのままRETURNで問題ないし、条件を満たしてない時はネストをカウントする必要があるのですがネストを変数Nとした場合には " [ " が現れたらNをインクリメント(N=N+1)して " ] " が現れたらデクリメント(N=N-1)をすればいいです。Nの値がゼロになった場所が次に実行する場所になります。
 " ] " を実行する場合は条件を満たしてない時はループを抜けるためそのままRETURNで問題ないし、そうでない場合は同様にインクリメントとデクリメントを行えばよいです。
 これによって何重ループになっても対応できます。これで問題はないのですが、速度を重視するならば " [ " の位置をスタックに入れておいてそれを取り出せば高速になります。

 以上のようにBrainfuckのインタープリタを作るのは非常に簡単です。インタープリタを作るよりもBrainfuckのコードを書く方が難しいと言われているくらいです(笑)
 とはいえ、これはごく基本的な部分だけであり、快適に使用するためにはどのようなUIにしていくかというものを考える必要があります。これはBrainfuckでは命令を実装するよりも難しいかもしれません。まともに使うならば上記の改造点で記しているようなものは最低限欲しいところでしょう。

《 はじめてでも分かる Brainfuck入門 》

 プログラミング言語「Brainfuck」は難解プログラミング言語の1つです。難解プログラミング言語は意図的に読解が困難になるように設計されたプログラミング言語であるため実用性を目指したものではありません。
 しかし、Brainfuckはシンプルでありながらパズルのような考え方が必要になるためなかなか奥が深いです。

 「Brainfuck」は以下の8つの命令のみで構成されています。

現在のポインタが指す値を1増やす(インクリメントする)
現在のポインタが指す値を1減らす(デクリメントする)
ポインタを1つ進める(インクリメントする)
ポインタを1つ戻す(デクリメントする)
ポインタが指す値(そのキャラコードの文字)を出力する
1バイト入力し、現在のポインタに代入する(キャラコードの値が現在のポインタに入る)
現在のポインタが指す値が0であれば対応する ] の直後へジャンプする
現在のポインタが指す値が0でなければ対応する [ の直後へジャンプする

 Brainfuckでは開始時にすべてのポインタの値は0に初期化されポインタ0を指しています。
 次に各命令の簡単な使い方を書いていきます。

+++ポインタ0に3の値を入れる
--ポインタ0に-2の値を入れる(バイト型整数なので-2は254になる)
>>>++ポインタ3に2の値を入れる
>>+<<-ポインタ2に1の値を入れた後にポインタ0に-1の値を入れる
,++.ポインタ0に1バイトの値を入力した後に2加えてその値を出力する
 (「A」を入力したら「C」と表示する)
[++++]+ポインタ0に1の値を入れる
 ("["を実行した時点ではポインタ0の値は0なのですぐに"]"にジャンプするため最後の"+"しか実行されない)
+[----]ポインタ0の値は減り続ける(無限ループ)
 ("["を実行した時点ではポインタ0の値は1なのでループ内を実行するけど"]"を実行の時点でポインタが0の値を示すことがないためループが終了することはない)

 これだけでは何のことやらよく分からないですね(笑)
 そういうわけで次にサンプルコードをいくつか用意したのでそれを見てどのような動作をするのかを学んでください。
 私自身がBrainfuck初心者であるため高度なサンプルは用意できませんでした。ネット上にはBrainfuckのコードはたくさんあるのでより高度な使い方を知りたい人はWeb検索をしてください←って丸投げかいっ(笑)

《 サンプルコード 》

 プログラミングを覚えるには実際に入力して自分の目で動作を確認したり改造するのが一番ということでBrainfuckのサンプルコードを用意しました。
 各サンプルにはどのような原理で動作しているのかという解説も付け加えましたので理解をするのは容易でしょう。

サンプル1 (66文字)
++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++
+.
(プチコンの画面サイズに合わせて32文字ごとに改行している)

 アルファベット「A」を出力するコードです。ポインタ0においてインクリメントを65回行い(=ポインタ0の示す値を65にする)最後にその値を出力しています。(キャラコード65つまり、41Hとなる「A」を表示)

サンプル2 (24文字)
++++++++[>++++++++<-]>+.

 アルファベット「A」を出力するコードの短縮版です。ポインタ0にインクリメントを8回行い(=ポインタ0が示す値を8にする)それをカウンタ代わりに(8回の)ループをして1回のループでインクリメントを8回(合計8×8回のインクリメント)を行い最後にもう1回インクリメントすることで合計65回のインクリメントを行っています。
 これは65=8×8+1であるためです。65=10×6+5(最初に10回インクリメントを行いループ内で6回インクリメントを行いループを抜けて5回インクリメントを行う)でも同じように書くことができますが、a+b+cの値が最小となるa×b+cの形で表現することで最も短く書くことができます。

サンプル3 (119文字)
+++++++++[>++++++++>+++++++++++>
+++++<<<-]>.>++.+++++++..+++.>-.
------------.<++++++++.--------.
+++.------.--------.>+.
(プチコンの画面サイズに合わせて32文字ごとに改行している)

 「Hello, world!」を出力するコードです。サンプル2を応用したものとなっています。
 まずはインクリメントを9回行いポインタ0の値を9にしてそれをループのカウンタ代わりにして、ポインタ1、2、3の値をそれぞれ72(=8x9)、99(=11x9)、45(=5x9)にしています。
 すでにポインタ1には72の値が入っているのでそれを出力すれば「H」になります。
 ポインタ2の値は2回インクリメントすると101になるためそれを出力すると「e」になります。さらに7回インクリメントすると108になるためそれを出力すると「l」になります。さらに同じものもう1回出力しています。さらに3回インクリメントすると111になるためそれを出力すると「o」になります。
 ポインタ3には45の値が入っているのでそれを1回デクリメントすると44になるため出力すると「,」になります。さらに12回デクリメントすると32になるためそれを出力すると「 」(スペース)になります。
 ポインタ2の値は現在111であるためそれを8回インクリメントすると119になりそれを出力すると「w」になります。それを8回デクリメントすると111になりそれを出力すると「o」になります。そこから3回インクリメントすると114になりそれを出力すると「r」になります。6回デクリメントすると108になりそれを出力すると「l」になります。8回デクリメントすると100になりそれを出力すると「d」になります。
 ポインタ3の値は現在32であるため1回インクリメントすると33になりそれを出力すると「!」になります。
 以上、出力された文字を順番に見ていくと「Hello, world!」になります。
 このように複数の文字を表示する場合にはキャラコードがある程度近いものをピックアップしてその概算値をあらじめループによって生成しておくことが短縮への鍵となります。

サンプル4 (26文字)
+++++[>+>+<<-]>>[<<+>>-]<<

 ポインタ0の値をポインタ1にコピーするコードです。
 最初の "[" の前に適当な数の "+" や "-" を置いてポインタ0の初期値を決めてください(このサンプルでは5にしている)
 まずは、ポインタ0の値をカウンタとして使用してポインタ1ポインタ2に移動します。(ポインタ1、2はループでインクリメントを繰り返すことによってポインタ0の初期値と同じになるけどポインタ0はループでデクリメントを繰り返すことによって値は0になる)
 そして、ポインタ2の値をカウンタ代わりにポインタ0に値を移動します。このサンプルが実行されるとポインタ0、1、2の値はそれぞれ5、5、0となりポインタ0の値がポインタ1にコピーされていることが分かります。

 サンプル2〜4を見て分かるようにBrainfuckではループ命令 "[" 、"]" の間に "-" をはさんで上手くループから脱出させることによって様々な処理が可能になります。(要するに特定の1つのポインタの値を破壊する(=0にする)ことで指定した回数でループを抜けることが可能になる)
 指定のポインタの値を0にする(初期化する)ならば" [-] "とすれば良いです。

"-" を挟まないループとしては "[>]" や "[<]" があります。

サンプル5 (27文字)
+>+>+>+>+>>+>+>+<<<<<<<<[>]

 これはポインタ0からポインタ7のうちポインタ5以外は値を1としてポインタを0に戻した状態で "[>]" を使ってその値が0のポインタの位置で停止させるというものです。
  "[>]" や "[<]" によって値が0のポインタを見つけ出すことが可能になります。(すべてのポインタの値は初期値が0であるためこのサンプル5において "[>]" を "[<]" に変えた場合は末尾のポインタで停止する)

サンプル6 (38文字)
++++++++[>++++++++>+++<<-]>>++[
<+.>-]
(プチコンの画面サイズに合わせて32文字ごとに改行している)

 「A」〜「Z」の26文字を出力するコードです。
 あらかじめポインタ1に64(「A」のキャラコード-1)、ポインタ2に26(文字数)の値を入れておきます。ポインタ2の値をカウンタ代わりにしてループを行い1回のループごとにポインタ1の値をインクリメントしていけば65を始点としたインクリメントを行う26回のループ(FOR I=64 TO 89 〜 NEXT のような感じ)となります。そのループ内で出力命令を実行すれば「A」から順番に26文字分表示されるということです。
 なぜ、「A」のキャラコードである65ではなくマイナス1となる64という値を最初にポインタ1に入れておくかというと FOR 〜 NEXT のループではNEXTが実行された時点でカウンタとなる変数の値がインクリメントするのに対してBrainfuckではインクリメントを行う命令を実行した時点でインクリメントが行われるため出力命令を実行する直前にインクリメントしておけば64+1で65から開始したのと同じになるからです。こうすることで、65よりも64を生成するコードの方が1文字少なくて済むためコードが1文字分短縮できるわけです。

サンプル7 (94文字)
,>,>++++++++[<------<------>>-]<
<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[
<<[>>>+<<<-]>>>[<<+<+>>>-]<-]<
(プチコンの画面サイズに合わせて32文字ごとに改行している)

 入力命令と多重ループを使ったサンプルでキーボードから入力した2つの数字の乗算を行うコードとなっています。(Petit Brainfuckで動作させる場合は、入力命令と多重ループはオプションとなっているので対応するようにしておいてください)

 まずは、入力時に「1」のキーを押してポインタに1の値が入るようにしなくてはなりません。「1」のキャラコードは49(テンキーの数字の値はキャラコードから48をマイナスしたもの)なのでポインタ0、1に入力した後で48回デクリメントをしています。
 ポインタ0の値をポインタ3にコピーを行い(=ポインタ0の値をカウンタにしてポインタ2、ポインタ3に移動した後にポインタ3の値をポインタ0に移動)、「ポインタ1の値をポインタ4に移動した後にポインタ4の値をポインタ1、2に移動」というものをポインタ3の値の回数だけ繰り返しています。

 サンプル4の所でも書いたようにBrainfuckはループカウンタの代わりにしたポインタの値は破壊されてしまうためそれを再利用する必要がある場合にはあらかじめその値を別のポインタに移しておく必要があります。そして、その移しておいた値を再び元に戻せば多重ループ中のカウンタとして再び使用することが可能になります。

 このコードを実行して、「4」「2」の値を入力するとポインタ0、1、2の値はそれぞれ4、2、8となっており、「4×2=8」が実行されたことが分かると思います。Petit Brainfuckなどの操作しているポインタの位置にカーソル表示するインタープリタを使用している場合にはカーソルが答えの位置に来るようになっており、答えが分かりやすくなっていると思います。
 出力命令に対応させて「4×2=8」のように表示を行うコードはこれよりもさらに難易度が高くなります。(解が2桁になる場合には除算を用いて10の位と1の位に分ける必要があるため)

《 ASCIIコード表 》

 Brainfuckで出力する文字のコード表を記しておきます。
 プチコンでは、キャラコード0〜255(16進数で0〜FF)の文字が使用できますが、ASCIIコードとして世界標準で定められているものは7ビット(10進数で0〜127、16進数で0〜7F)のみです。ただし、プチコンでは0〜31(16進数で0〜1F)の制御文字は使用できず、独自のキャラが割り振られています。128〜255(80〜FF)は機種依存文字であるためそれを出力するBrainfuckのコードを書いても他の環境(プチコン以外)では正常に出力されない可能性があります。(半角カナは国内の規格で定められているため問題ないけどそれ以外はプチコン独自のキャラや配置になっているものが大半)


コード

コード

コード

コード

コード

コード
10進数
16進数
10進数
16進数
10進数
16進数
10進数
16進数
10進数
16進数
10進数
16進数
スペース
32
20
48
30
64
40
80
50
96
60
112
70
33
21
49
31
65
41
81
51
97
61
113
71
34
22
50
32
66
42
82
52
98
62
114
72
35
23
51
33
67
43
83
53
99
63
115
73
36
24
52
34
68
44
84
54
100
64
116
74
37
25
53
35
69
45
85
55
101
65
117
75
38
26
54
36
70
46
86
56
102
66
118
76
39
27
55
37
71
47
87
57
103
67
119
77
40
28
56
38
72
48
88
58
104
68
120
78
41
29
57
39
73
49
89
59
105
69
121
79
42
2A
58
3A
74
4A
90
5A
106
6A
122
7A
43
2B
59
3B
75
4B
91
5B
107
6B
123
7B
44
2C
60
3C
76
4C
92
5C
108
6C
124
7C
45
2D
61
3D
77
4D
93
5D
109
6D
125
7D
46
2E
62
3E
78
4E
94
5E
110
6E
126
7E
47
2F
63
3F
79
4F
_
95
5F
111
6F
127
7F

《 注意 》
アスキーコード92(16進数では5C)は本来ならば「\(バックスラッシュ)が割り当てられているけど国内規格では「¥」が割り当てられておりプチコンでもそうなっている関係上、それを記載した。
アスキーコード127(16進数では7F)は本来ならばDEL(デリート)が割り当てられているけどプチコンでは独自に「\」が割り当てられているためそれを記載した。しかし、これは国際的に定められているアスキーコード表としては正しくないことを留意して欲しい。


RETURN/RETURN *MAIN

inserted by FC2 system