brainfuck 入門:言語仕様編
今回の主軸
今回は、 brainfuck
の言語仕様と環境依存の挙動について解説します。
目次
brainfuck
とは
Hello World.
言葉で説明するよりも、コードを見てもらったほうが早いのではないかと思います。
下に示すのはプログラミングでよく最初に書かれる Hello World.
と出力するプログラムです。
++++++++++[->++++++++++>+++>++++++++++++>+++++>+++++++<<<<<] >>>>>++.<<<<+.+++++++..+++.>++.>-.<<.+++.------.--------.>>>----.
概要
brainfuck
はプログラミング言語の一つで、コンパイラおよびインタプリタのサイズが小さくなるように設計されています。
よく勘違いされますが、人がプログラミングしにくいように作られた言語ではありません。
また、fuck
という単語は良くないということで、
brainf*ck
や brainfxxk
などといった表記がされることがあります。この記事では特別な場合を除き brainfuck
で統一しています。
予約語
brainfuck
には以下の8個の予約語のみが与えられ、それ以外の文字はすべてコメントとして扱われます。
+-><[],.
また、それぞれの命令の内容は以下の通りとなっています。
予約語 | 命令内容 | Cの相当コード |
---|---|---|
+ |
現在の値をインクリメント | *ptr++; |
- |
現在の値をデクリメント | *ptr--; |
> |
ポインタをインクリメント | ptr++; |
< |
ポインタをインクリメント | ptr--; |
[ |
現在の値が 0 なら対応する ] に移動 |
while(*ptr){ |
] |
現在の値が 1 なら対応する [ に移動 |
} |
, |
入力を1文字受け取り現在の値をその文字コードにする | *ptr = getchar(); |
. |
現在の値を文字コードとする文字を出力する | putchar(*ptr); |
メモリ仕様
brainfuck
には変数というものは存在しておらず代わりに最低 30000 byte
の 0
で初期化されたのメモリを有しており、
そのメモリの位置を指し示すポインタを移動させることにより任意のメモリにアクセスできるようになっています。
未定義動作
brainfuck
には未定義動作がいくつか存在します。そのうち重要なものを紹介します。
- 最大値に対するインクリメント
- 最小値に対するデクリメント
- メモリ領域外アクセス
これらの動作は一般的に動作が実行環境ごとに設定されていることが多いです。
実行環境による裁量
上記の未定義動作以外にも実行環境による裁量で変化しているものもあります。 以下にそのいくつかを紹介します。
- 値の最小値
- 値の最大値
EOF
(入力の末端)
今回の記事に用いる実行環境
今回の記事で用いる環境は AtCoder という競技プログラミングを行うサービルで使われいてる実行環境に準拠します。
AtCoder での環境は以下の通りです。
- 値は
byte
型 (0 ~ 255
) 0
に対するインクリメントは255
255
に対するインクリメントは0
EOF
は-1
(= 255
)- 対応する
]
のない[
はエラー - 対応する
[
のない]
はジャンプ時に先頭に戻る メモリは9999 byte
( ※言語仕様を満たしません )- メモリの領域外アクセスはエラー
※メモリの byte
数は言語アップデートにより 30000
以上になりました。実際のサイズは確認していませんが、メモリオーバーすることはないと思って問題だけの数があります。
この記事で登場するコード例では、
[
と ]
との対応はすべて取っており、メモリも仕様も 9999
を超えることがないように作成されています。
実行環境例
brainfuck
のコードは実際に動かしてみるとわかりやすいです。こちらのサイトで簡単に実行できるので気になるコードは実際に動かして試してみてもいいかもしれません。
オンラインBrainf*ckデバッガ
問題例
いろはちゃんコンテスト Day1 A - 一問目
言わずと知れたbrainfuck
向けの問題です。ABC 085 A - Already 2018
BACの中で最もbrainfuck
向けの問題です。
次回
次回は基本構文の話しようと思います。
文字出力の話しました。
brainfuck 入門:ループ文と定数生成と文字出力 - 三流プログラマの戯言