三流プログラマの戯言

プログラミング初心者が気になったことを書き綴るだけ。主にc#

brainfuck 入門:言語仕様編

今回の主軸

今回は、 brainfuck の言語仕様と環境依存の挙動について解説します。

目次

brainfuck とは

Hello World.

言葉で説明するよりも、コードを見てもらったほうが早いのではないかと思います。
下に示すのはプログラミングでよく最初に書かれる Hello World. と出力するプログラムです。

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

概要

brainfuckプログラミング言語の一つで、コンパイラおよびインタプリタのサイズが小さくなるように設計されています。
よく勘違いされますが、人がプログラミングしにくいように作られた言語ではありません。
また、fuck という単語は良くないということで、 brainf*ckbrainfxxk などといった表記がされることがあります。この記事では特別な場合を除き brainfuck で統一しています。

予約語

brainfuck には以下の8個の予約語のみが与えられ、それ以外の文字はすべてコメントとして扱われます。

+-><[],.

また、それぞれの命令の内容は以下の通りとなっています。

予約語 命令内容 Cの相当コード
+ 現在の値をインクリメント *ptr++;
- 現在の値をデクリメント *ptr--;
> ポインタをインクリメント ptr++;
< ポインタをインクリメント ptr--;
[ 現在の値が 0 なら対応する ] に移動 while(*ptr){
] 現在の値が 1 なら対応する [ に移動 }
, 入力を1文字受け取り現在の値をその文字コードにする *ptr = getchar();
. 現在の値を文字コードとする文字を出力する putchar(*ptr);

メモリ仕様

brainfuck には変数というものは存在しておらず代わりに最低 30000 byte0 で初期化されたのメモリを有しており、 そのメモリの位置を指し示すポインタを移動させることにより任意のメモリにアクセスできるようになっています。

未定義動作

brainfuck には未定義動作がいくつか存在します。そのうち重要なものを紹介します。

  • 最大値に対するインクリメント
  • 最小値に対するデクリメント
  • メモリ領域外アクセス

これらの動作は一般的に動作が実行環境ごとに設定されていることが多いです。

実行環境による裁量

上記の未定義動作以外にも実行環境による裁量で変化しているものもあります。 以下にそのいくつかを紹介します。

  • 値の最小値
  • 値の最大値
  • EOF(入力の末端)

今回の記事に用いる実行環境

今回の記事で用いる環境は AtCoder という競技プログラミングを行うサービルで使われいてる実行環境に準拠します。
AtCoder での環境は以下の通りです。

  • 値は byte 型 ( 0 ~ 255 )
  • 0 に対するインクリメントは 255
  • 255 に対するインクリメントは 0
  • EOF-1 ( = 255 )
  • 対応する ] のない [ はエラー
  • 対応する [ のない ] はジャンプ時に先頭に戻る
  • メモリは 9999 byte ( ※言語仕様を満たしません )
  • メモリの領域外アクセスはエラー

※メモリの byte 数は言語アップデートにより 30000 以上になりました。実際のサイズは確認していませんが、メモリオーバーすることはないと思って問題だけの数があります。

この記事で登場するコード例では、 [] との対応はすべて取っており、メモリも仕様も 9999 を超えることがないように作成されています。

実行環境例

brainfuck のコードは実際に動かしてみるとわかりやすいです。こちらのサイトで簡単に実行できるので気になるコードは実際に動かして試してみてもいいかもしれません。
オンラインBrainf*ckデバッガ

問題例

次回

次回は基本構文の話しようと思います。
文字出力の話しました。
brainfuck 入門:ループ文と定数生成と文字出力 - 三流プログラマの戯言

記事一覧

brainfuck 入門:リンクまとめ - 三流プログラマの戯言