何か得するかもしれないBrainf*ck入門

はじめに

Brainf*ckはWikipdiaでは難読プログラムとされている言語で
卑語を含むので一般的に「u」は「*」で伏せられている
一見ネタ言語のようであるが面白い特徴を持つ

• コンパイラだと123バイト,インタプリタだと98バイトとかなり軽量
• チューリング完全
• 予約語を8語しか持たない

この簡便な記述を受けて,
頭がぴょんぴょんした人が作った「ごちうさ」
おれたちにできない事を平然とやってのけるッ人が作った「ジョジョ言語」
永続的な狂気に冒されたプレイヤーが作った「Nyauko」
など様々な派生言語が生まれている(というより予約語が変わっただけですが)

また個人的には多くのC言語勉強者を挫折に導いた「ポインタ」についての概念が
理解しやすくなるのではないかと考えているので「ポインタ」がわからない人にはおすすめしたい

言語仕様について

プログラム実行時にはメモリを指すポインタのようなものが用意されており
それを左右に動かしたり指している値を増やしたり減らしたりしてプログラムを組む
メモリ,ポインタは起動時にすべて0になる

予約語について

予約語	説明
+	ポインタの指すメモリの値を1増やす
-	ポインタの指すメモリの値を1増やす
>	ポインタを右に1つずらす
<	ポインタを左に1つずらす
[	ポインタの指すメモリの値が0だったら次の「]」に進む
]	ポインタの指すメモリの値が0でなければ前の「[」に戻る
,	標準入力から1バイト読み込み
.	ポインタの指すメモリの値を出力

その他の文字は全てコメントである

Hello World!

適当版

simple_hello.bf

++++++++++ ++++++++++ ++++++++++ ++++++++++
++++++++++ ++++++++++ ++++++++++ ++.        #H
++++++++++ ++++++++++ +++++++++.            #e
+++++++.                                    #l
.                                           #l
+++.                                        #o
---------- ---------- ---------- ----------
---------- ---------- -------.              #camma
---------- --.                              #_
++++++++++ ++++++++++ ++++++++++ ++++++++++
++++++++++ ++++++++++ ++++++++++ ++++++++++
+++++++.                                    #w
--------.                                   #o
+++.                                        #r
------.                                     #l
--------.                                   #d
---------- ---------- ---------- ----------
---------- ---------- -------.              #!

解説

文字を出力するには対応する文字コードに値を調整しないといけません
"Hello, world!"に対応するASCIIのは"72,101,108,108,111,44,32,119,111,114,108,100,33"なので
値を前の文字の差分の分足し引きしているだけです

まとも版

helloworld.bf

+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+
++.>-.------------.<++++++++.--------.+++.------.--------.>+.

うまく複数のメモリやループを使いこなせばこのように最適化できます
(解説については話のメインでないので省略します)

基本的な操作について

説明の都合上
初期のメモリを{0},その右となりを{1},その先{2},{3}...
と表記する
以下のプログラム群は保存場所がまちまちなので適宜あわせてください
また標準入力の値は文字コードの値を前提としてやってますので注意してください
例:'0'= 48(0x30)

こちらの方のアルゴリズムが素晴らしく書けていましたので結果的にそのアルゴリズムの解説となっています

移動

move.bf

,
[>+<-]
>.<

{1}に1足して{0}から1引くことを{0}が0になるまでループする
ちょうど{0}から{1}に1ずつ動かすイメージ

コピー

copy.bf

,
[>+>+<<-]
[+>>-<<]
.
>.<

{1}と{2}に{0}を移し
{2}を{0}に移す
移す動作をすると値が消滅してしまうので{2}にコピーを取っている

if文その1

if1.bf

,
[+>]<

上のプログラムはif文の一例で
if({0})({0}+=1)をしてます
ループの初めに0かどうかをみたい対象に合わせて,ループの最後にわざと使用していないメモリを指した状態で終われば0かどうかを調べる1回ループになります

if文その2

if2.bf

,
[>+>+<<-]
>>[[-]<+>]<<
[+>-<]
.

上のプログラムもif({0})({0}+=1)をしてます
{0}を{1},{2}に移動し{2}が0でなければループ内に入り{2}を0にする,ループの最後で{2}をみれば1回のみの実行となります
最後に{1}を{0}に戻せば完了です

足し算

add.bf

,
>,<
[>+<-]
>.<

移動と同じです
{1}が0の時は0を足すことになるなので移動と同じになります

引き算

sub.bf

,
>,<
>[<->-]<
.

足し算の時とほとんど同じです
両者を引くことで被減算数が0になる地点でループから抜けます

定数倍

k_mul.bf

,
[>+++<-]
>.<

3倍するプログラムです
移動する際にN回足せばN倍になります

掛け算

mul.bf

,
>,<
[->>+<<]
>[-<
>>[->+>+<<]<<       #1
>>>>[-<<+>>]<<<<    #2-1
>>>[-<<<+>>>]<<<    #2-2
>]<
.

まず{0}を{2}に移動
その状態で{1}が0になるまで以下のループ
1. {1}を1つ減らす
2. {2}を{3},{4}にコピー後片方を{0}に足し合わせ,もう片方を{2}に戻す

{2}の値はもともと最初の{0}の値なので,最初の{0}の値を{1}回足し合わせることにより表現できる

割り算

dev.bf

,
>,<

# {3}=1
>>>+<<<

# while {3} do  ### main_loop ###
>>>[<<<

#################### section1 ###

#  copy from {0} to {4}
[->>>>+>+<<<<<]
>>>>>[-<<<<<+>>>>>]<<<<<
#  copy from {1} to {5}
>[->>>>+>+<<<<<]<
>>>>>>[-<<<<<+>>>>>]<<<<<<

#################### section2 ###

#   while {4} do
>>>>[<<<<
#  copy from {5} to {6}
>>>>>[->+>+<<]<<<<<
>>>>>>>[-<<+>>]<<<<<<<
#     if !{6} then
#       {5}-=1
#     end
>>>>>>[[-]<->]<<<<<<
#     {4}-=1
>>>>-<<<<
#   end
>>>>]<<<<

#################### section3 ###

#   {4}=1
>>>>+<<<<

#################### section4 ###

#   copy from {5} to {6}
>>>>>[->+>+<<]<<<<<
>>>>>>>[-<<+>>]<<<<<<<

#   if !{6} then
#     {4}-=1
#   end
>>>>>>[[-]<<->>]<<<<<<

#################### section5 ###

#   if !{5} then
#     {3}-=1
#   end
>>>>>[[-]<<->>]<<<<<
#################### section6 ###
#   if !{4} then
>>>>[[-]<<<<
#     {2}+=1
>>+<<
#     copy from {1} to {6}
>[->>>>>+>+<<<<<<]<
>>>>>>>[-<<<<<<+>>>>>>]<<<<<<<
#     {0}   sub !{6}
>>>>>>[-<<<<<<->>>>>>]<<<<<<
#   end
>>>>]<<<<

# end ########## main_loop end ###
>>>]<<<

# !{1}
>[-]<
# {1} add !{0}
# {0} add !{2}
[->+<]
>>[-<<+>>]<<

まず初めに{3}を1にして,これが0になるまでループする部分(main_loop)に入ります

• section1では{0}を{4}(a=>buf_a),{1}を{5}(b=>buf_b)にコピーします
• section2では{4}(buf_a)と{5}(buf_b)のどちらが大きいかを比較します 具体的には{4}(buf_a)を1ずつ引きながらループしている間{5}(buf_b)も0より大きければ引きます つまり「buf_a>=buf_b」なら「buf_b==0」,「buf_a<buf_b」なら「buf_b-=buf_a」になっています
• section3ではbuf_aを1にしています,section6でさらに引くかの判定を行うためです
• section4ではsection2でbuf_bが正であればbuf_b(被除算数)の方が大きいことを意味しますのでbuf_aを0にしてsection6を行わないようにします
• section5では上が成り立つとこれ以上ループの必要がないのでループフラグの{3}を0にします
• section6では{0}(a)から{1}(b)を引き,商{2}(count)を1増やしますsection4を通ったかで決まります

ループを抜けたら{1}に余り{0}, {0}に商{2}を入れて完成