この記事は(も)Kogakuin Univ Advent Calendar 2019 - Adventar23日目です。
たくさん書いたので分割した。もう片方はコチラ

metarinです
今回はBrainf*ckの紹介をします

Brainf*ck is 何?

おそらく世界で最も単純な手続き型プログラミング言語です
正式名称は Brainfuck ですが、fワードが含まれるのでuをアスタリスクで置き変えています

命令の種類がとてつもなく少なく、なんと8種類しかありません
しかも、なんとこれでチューリング完全¹なんです！

言語仕様

普通の言語ならブログ記事1つにはとても収まらない言語仕様の解説も、命令が8種類しかないBrainf*ckならできちゃいます

命令	処理
+	現在のポインタが指す値に1加算
-	現在のポインタが指す値に1減算
>	現在のポインタを1進める
<	現在のポインタを1戻す
.	現在のポインタが指す値を出力
,	現在のポインタが指す値に1B標準入力から取得
[	現在のポインタが指す値が0でなければ実行、0ならば対応する]へ
]	現在のポインタが指す値が0でなければ対応する[へ、0ならば何もしない
他の文字	コメント

とても簡単ですね!

実行環境

読者のみなさんもこの言語の素晴しさに感動して、自分でも使ってみたいと思っているに違いありません！
しかし、この言語の素晴しさはいままで紹介したものだけではありません。
なんと命令が8種類しかないので簡単に処理系が自作できちゃうんです！

自分で作ってる時間がない忙しい人や、作例を見たい人向けに自分でC++で書いてみたものを貼っておきます
https://gist.github.com/metarin/189c20f64f4b6f16488a7cdcba862c3b

Hello, World!

実行環境も整備できたことですし、実際にプログラムを書いてみましょう!
最初のプログラムの代名詞ことHello, World!は以下のように実装できます

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++. 72 = 'H'
+++++++++++++++++++++++++++++. 101 = 'e'
+++++++. 108 = 'l'
. 'l'
+++. 111 = 'o'
-------------------------------------------------------------------. 44 = ','
------------. 32 = ' '
+++++++++++++++++++++++++++++++++++++++++++++++++++++++. 87 = 'W'
++++++++++++++++++++++++. 111 = 'o'
+++. 114 = 'r'
------. 108 = 'l'
--------. 100 = 'd'
-------------------------------------------------------------------. 33 = '!'

8種の文字以外の全ての文字はコメント扱いされるので//や#を書かなくてもコメントを書くことができます。すごい!
処理的には、+や-で出力したい文字のASCIIコードを作って.で出力しているだけです。

以下の5規則を覚えておくと、ASCIIコードをまあまあ快適に読み書きできるので、これからのBrainf*ckライフを快適なものにするためにも是非覚えましょう

• 0x0a = 改行(LF)
• 0x20 = 空白(SPC)
• 0x30 ~ 0x39 = 0~9
• 0x41 ~ 0x5a = A~Z
• 0x61 ~ 0x7a = a~z

ちなみにループを使うことでもっと短く書くことが出来ます

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

Brainf*ckで競プロ

AtCoderではなんとBrainf*ckを使って提出することが出来ます!
練習用にBrainf*ckでも解きやすい問題を2つピックアップしてきましたので、実際に解いてみましょう!

※ちなみに数値計算が必要な問題は下記2つの理由により難易度が高いことが多いです

• Brainf*ckでは入力を1Bずつ取るので2桁以上の数値が入力された際1桁ずつしか取れないので合算する必要があって大変

• AtCoderのBrainf*ck処理系はメモリセル1ブロックがchar型なのでオーバーフローを防ぐために多倍長整数を自分で実装する必要がある場合がある

• ABC013 A - A
  https://atcoder.jp/contests/abc013/tasks/abc013_1

  12/13日のKogakuin Univ Advent Calendarで紙幣が紹介してた問題です。

  入力と出力すべき値の対応を表にすると

  入力	入力(Hex)	出力	出力(Hex)
  A	0x41	1	0x31
  B	0x42	2	0x32
  C	0x43	3	0x33
  D	0x44	4	0x34
  E	0x45	5	0x35

  このように入力から 0x10=16 を引いたものを出力すればいいことが分かります。
  解答例はコチラ

  ちなみに、この頃のAtCoderのコンテストは改行を出力しないとWAになります。
  「当ってるはずなのに全部WAだ!NANDE!」という場合はだいたいこれなので気をつけて下さい。

• ABC141 A - Weather Prediction
  晴れ→雨→曇り→晴れ→… のように天気が規則的に変化する町の天気予報をする問題です。

  入力の1文字目をそれぞれ見てみると、S,C,R となりいずれも重複していないので、1文字取得するだけで明日の天気を予測できます。

  あとは分岐を書くだけなのですが、Brainf*ckにはif文がありません。
  しかし、ループの終了条件である(*p != 0)を利用することで、!=に限り比較的簡単に書くことができます。
  0番目のメモリが'S'でないことを確かめるには次のような手順を踏みます

  1. 0番目のメモリから、ASCIIコードで'S'にあたる0x53を引く
  2. 0番目のメモリにポインタを合わせた状態で、ループを始める
  3. 'S'でなかった場合はループの中の処理が実行される(この処理の最後は必ず0が入っているところにポインタが合うようにする)

  解答例はコチラ
  出力する文字をあらかじめメモリに置いておき分岐でその内容を書き変えるというアプローチを取っています。

まとめ

Brainf*ckは学習コストが非常に低いので、これを読んだあなたもすぐに始められます!
しかも、

• ポインタを完全理解できる
• 他の言語を使う際にも、メモリに何があるかを意識してプログラムを書くようになる

といった副次的な効果もあります!
みなさんも是非この機会にBrainf*ckerライフを始めましょう!