最古のbrainfuck処理系と言語仕様【Brainf*ck Advent Calendar 2019 9日目】

プログラミング 難解プログラミング言語 brainfuck

この記事はBrainf*ck Advent Calendar 2019 - Adventarの9日目の記事です。

brainfuckは最も有名な難解プログラミング言語といえそうである。

brainfuckの人気を支えているのはその言語仕様の分かりやすさだろう。brainfuckはコンパイラを限界まで簡単にするために設計された言語であるから、他の難解言語と比較すると命令は非常に読みやすく理解しやすい。それどころか、覚えることの少なさを考慮すれば、実用性のある高級言語よりもさらに敷居が低いといえるのではないだろうか。

このように言語仕様の単純明快さが長所のbrainfuckだが、実は罠がある。それは処理系依存の動作が多数存在していることだ。とくに処理系の違いによってプログラムの内容に大きな変化が生まれそうなのが次の2つである:

  • セルの値の範囲(サイズはいくらか?負の数を扱えるか?)
  • ラップアラウンドの有無(例えばセルが8ビットのとき、値が255のセルで+を実行すると値が0に戻るか?)

例えば「1番目のセルの値が1でないとき、2番目のセルの値を1増やす」ようなプログラムを書くとき、次のように実装したくなる。

- [[-] > + <]

しかしラップアラウンドを行わない処理系において、このプログラムは1番目のセルの値が0であるとき正常に動作しない。つまり、可搬性がないということである。

私はこれらの可搬性の問題を知ったとき、そもそも自分が日本語版Wikipedia等に書かれたbrainfuckの言語仕様しか読んだことがなくて、その出典を知らないということに気がついた。 また、brainfuckについて書かれた日本語の記事の多くは、言語仕様の詳細や可搬性の問題への言及をWikipediaへの参照に止めている。

そこで自分なりにbrainfuckの言語仕様の出典を探して日本語でまとめてみようと考え、この記事を書くに至った。本記事の目標は、 brainfuck設計者であるUrban Müllerの処理系に示された言語仕様を把握する ことである。

Urban Müllerの処理系

brainfuckは、できるだけコンパイラが小さくなるチューリング完全のプログラミング言語としてUrban Müllerによって設計された1。Urban Müllerは1993年に最初のbrainfuckコンパイラ(296バイト)をAminet(パーソナルコンピューターAmiga関連のソフトウェアアーカイブ)にアップロードしたらしい2。
たいへん残念なことに私にはその最初の処理系を見つけることができなかったが、Urban Müllerが同じく1993年にアップロードした、2番目のバージョンと思われる処理系のアーカイブ(brainfuck-2.lha)はAminet - dev/lang/brainfuck-2.lhaからダウンロードすることができる(2019年12月現在)。この2番目の処理系からbrainfuckの言語仕様を読み解くのが本記事の趣旨だ。

brainfuck-2.lhaを解凍すると、readmeのほか以下のプログラムを得られる。

名前 説明
bfc brainfuckのコンパイラ (240バイト! )
bfc.asm コンパイラのソース
bfi brainfuckのインタプリタ
bfi.c インタプリタのソース (移植性がある)
src/ brainfuckのサンプルプログラム集
src/atoi.b サンプル: 標準入力から数値を読む
src/div10.b サンプル: ポインタの指す数値を10で割る
src/hello.b サンプル: Hello World!
src/mul10.b サンプル: ポインタの指す数値を10倍する
src/prime.b サンプル: 与えられた上限まで素数を計算する
src/varia.b サンプル: SWAPやDUPなど、プログラムの断片集

ちなみに先述した「最初の」brainfuck処理系についてreadmeで言及がなされている。

WHATS NEW
=========

Yes, I squeezed another ridiculous 56 bytes out of the compiler. They have
their price, though: The new compiler requires OS 2.0, operates on a byte
array instead of longwords, and generates executables that are always 64K
in size. Apart from that the language hasn't changed. Again:
***  OS 2.0 *required* for the compiler and the compiled programs  ***

コンパイラから56バイトを圧搾した旨が書かれていることから以前のコンパイラが296バイトであったことがわかり、これは英語版Wikipediaの記述と一致する。 その他、コンパイラの動作にAmiga OS 2.0が必要になったほか、配列要素のサイズがlongword(Amigaでは32ビット?)からbyteに変化したようだ。

readmeの言語仕様を読む

readmeにはbrainfuckの説明が以下のように書かれている。

THE LANGUAGE
============

The language 'brainfuck' knows the following commands:

 Cmd  Effect                                 Equivalent in C
 ---  ------                                 ---------------
 +    Increases element under pointer        array[p]++;
 -    Decrases element under pointer         array[p]--;
 >    Increases pointer                      p++;
 <    Decreases pointer                      p--;
 [    Starts loop, counter under pointer     while(array[p]) {
 ]    Indicates end of loop                  }
 .    Outputs ASCII code under pointer       putchar(array[p]);
 ,    Reads char and stores ASCII under ptr  array[p]=getchar();

All other characters are ignored. The 30000 array elements and p are being
initialized to zero at the beginning.  Now while this seems to be a pretty
useless language, it can be proven that it can compute every solvable
mathematical problem (if we ignore the array size limit and the executable
size limit).

読み取れる仕様を全て日本語化した。

  • brainfuckには次に示す8つの命令がある:
命令 効果 同等なC言語の文
+ ポインタの指す要素をインクリメントする array[p]++;
- ポインタの指す要素をデクリメントする array[p]--;
> ポインタをインクリメントする p++;
< ポインタをデクリメントする p--;
[ ポインタの指す値をカウンタとしてループを開始する while(array[p]) {
] ループの終わりを示す }
. ポインタの指すASCIIコードを出力する putchar(array[p]);
, 1文字読み込み、ポインタの指す位置にASCIIコードを代入する array[p]=getchar();
  • 上記以外の全ての文字は無視される
  • 配列の要素数は30000である
  • 最初、配列の要素およびポインタはゼロで初期化されている

この説明で未定義の事項として、以下の4つを挙げることができる。

  1. セルの値の範囲
    セル(配列の要素)の値の範囲は定義されていない。先述したとおり、おそらくUrban Müllerの最初のコンパイラと次のコンパイラでも実装が異なる。ただしASCIIコードの入出力を行う機能があるため、少なくとも0〜127を扱うことができるものとしてよさそうである。
  2. セルのオーバーフロー
    インクリメントやデクリメントの結果、セルがオーバーフローするときの動作は定義されていない。
  3. 配列外参照
    ポインタが配列の端より向こう側に移動したときの動作は定義されていない。
  4. EOF
    入力命令,がEOFをどのように扱うか定義されていない。

インタプリタを読む

Urban Müllerの処理系にはC言語で記述されたインタプリタのソースコードbfi.cが付属しているので、先ほど述べた4つの未定義の事項に対してインタプリタがどのように振る舞うのか確認することができる。

1. セルの値の範囲

セルの配列aが4行目で宣言されている。

char a[5000], f[5000], b, o, *s=f;

セルがchar型であることがわかる。
やっかいなことに、C言語の規格3によると、char型が符号付きであるかどうかは処理系に依存する4らしい。 残念ながら変数宣言部分からはセルの符号の有無について有益な情報は得られないようだ。unsignedかsignedがついていればよかったのだが。

2. セルのオーバーフロー

C言語では符号無しの計算ではオーバーフローが起こらないが、符号ありの計算のオーバーフローの動作は未定義である5。

したがってchar型が符号無しであるような処理系でコンパイルされたbfi.cはセルをラップアラウンドすることがわかる。一方、char型が符号付きであるような処理系についてラップアラウンドがあるかどうかはわからない6。

3. 配列外参照

ポインタが配列外に移動したときに対応するコードが39、40行目に書かれている。

if( p<0 || p>100)
  puts("RANGE ERROR"), exit(0);

ポインタが負の番地、または100より大きい番地を指したときインタプリタはRANGE ERRORを出力して正常終了する。

この0〜100という範囲は不思議なことに配列aの要素数である5000個よりも小さく、そもそも配列の要素数がreadmeに示された配列の要素数である30000個よりも小さい。

4. EOF

入力に対応するコードが19行目に書かれている。

case ',': a[p]=getchar();fflush(stdout); break;

getcharはそれ以上入力が存在しないときEOFを返す。マクロEOFは型がintで負の値をもつ整数定数式に展開する7ことが定められているが、具体的な値は規定されていない。

したがって、このインタプリタはEOFとしてint型の負数をchar型に変換した値を用いるが、その値はC言語の処理系依存である。

コンパイラを読む

アセンブリはよくわかりません。許してください。

サンプルプログラムを読む

処理系に付属している6つのサンプルプログラムのなかで、未定義の動作を踏んでいるものがないかどうか調べる。とくに、ポインタの指す数値がゼロのときに-命令が実行されることがあるかどうかを確認したい。

しかし他人が書いたbrainfuckのコードを全て読むのは苦行なので、インタプリタを自作して確認することにした。作成したインタプリタのコードの一部を掲載する。

array[ptr]++;
if (array[ptr] > CELL_MAX) {
    std::cerr << "'+' overflow (" << inst.line << ", " << inst.col << ")\n";
    array[ptr] = 0;
}

array[ptr]--;
if (array[ptr] < 0) {
    std::cerr << "'-' overflow (" << inst.line << ", " << inst.col << ")\n";
    array[ptr] = CELL_MAX;
}

if (array[ptr] == EOF) {
    std::cerr << "',' EOF (" << inst.line << ", " << inst.col << ")\n";
    std::exit(0);
}

このようにオーバーフローやEOFを検知することができる。 ここで先に結果を述べてしまうと、セルの値の範囲を0〜255として実行したところ、残念ながら(?)どのサンプルプログラムも未定義の操作を実行することはなかった。

atoi.b

==== ==== ====
cont digi num
==== ==== ====

+
[
 -                         cont=0
 >,
 ======SUB10======
 ----------

 [                         not 10
  <+>                      cont=1
  =====SUB38======
  ----------
  ----------
  ----------
  --------

  >
  =====MUL10=======
  [>+>+<<-]>>[<<+>>-]<     dup

  >>>+++++++++
  [
   <<<
   [>+>+<<-]>>[<<+>>-]<    dup
   [<<+>>-]
   >>-
  ]
  <<<[-]<
  ======RMOVE1======
  <
  [>+<-]
 ]
 <
]
>>[<<+>>-]<<
#

atoi.bは、改行を終端とする非負整数を入力に取り、cont(ソースコード中のコメント参照)に格納するプログラムである。

(\n判定のため)入力された値からいきなり10引いている部分が気になったが、入力が正しく([0-9]*\nの形で)与えられていて、入力された数値が範囲内に収まっている限り、このプログラムに未定義の動作は現れない。

div10.b

==== ==== ==== ==== ====
num  ten  tmp  bool div
==== ==== ==== ==== ====

>+++++++++<
[
 >>>+<<                bool= 1
 [>+>[-]<<-]           bool= ten==0
 >[<+>-]               ten = tmp
 >[<<++++++++++>>>+<-] if ten=0 ten=10  inc div
 <<-                   dec ten
 <-                    dec num
]
>>>>[<<<<+>>>>-]<<<<   copy div to num
>[-]<                  clear ten

div10.bは、numに格納されている値を10で割るプログラムである。小数点以下は切り捨てられる。

numが負でない限りこのプログラムに未定義の動作は現れない。

hello.b

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

特筆すべきことはない。

mul10.b

=====MUL10=======
[>+<-]>         ; move num one right ie num2=num
>>++++++++++    ; load 10 into fourth element
[
 <<[<+>>+<-]    ; add num2 to first and third element
 >[<+>-]>       ; num2=third element
 -              ; loop ten times
]
<<[-]<          ; clear num2
#

mul10.bはポインタの指す数値を10倍するプログラムである。

数値が負ではなく、かつ10倍した値がセルの値の範囲内に収まっているとき、このプログラムに未定義の動作は現れない。

prime.b

prime.bのコード(長いので折りたたみ)

===================================================================
======================== OUTPUT STRING ============================
===================================================================
>++++++++[<++++++++>-]<++++++++++++++++.[-]
>++++++++++[<++++++++++>-]<++++++++++++++.[-]
>++++++++++[<++++++++++>-]<+++++.[-]
>++++++++++[<++++++++++>-]<+++++++++.[-]
>++++++++++[<++++++++++>-]<+.[-]
>++++++++++[<++++++++++>-]<+++++++++++++++.[-]
>+++++[<+++++>-]<+++++++.[-]
>++++++++++[<++++++++++>-]<+++++++++++++++++.[-]
>++++++++++[<++++++++++>-]<++++++++++++.[-]
>+++++[<+++++>-]<+++++++.[-]
>++++++++++[<++++++++++>-]<++++++++++++++++.[-]
>++++++++++[<++++++++++>-]<+++++++++++.[-]
>+++++++[<+++++++>-]<+++++++++.[-]
>+++++[<+++++>-]<+++++++.[-]

===================================================================
======================== INPUT NUMBER  ============================
===================================================================
+                          cont=1
[
 -                         cont=0
 >,
 ======SUB10======
 ----------

 [                         not 10
  <+>                      cont=1
  =====SUB38======
  ----------
  ----------
  ----------
  --------

  >
  =====MUL10=======
  [>+>+<<-]>>[<<+>>-]<     dup

  >>>+++++++++
  [
   <<<
   [>+>+<<-]>>[<<+>>-]<    dup
   [<<+>>-]
   >>-
  ]
  <<<[-]<
  ======RMOVE1======
  <
  [>+<-]
 ]
 <
]
>>[<<+>>-]<<

===================================================================
======================= PROCESS NUMBER  ===========================
===================================================================

==== ==== ==== ====
numd numu teid teiu
==== ==== ==== ====

>+<-
[
 >+
 ======DUP======
 [>+>+<<-]>>[<<+>>-]<

 >+<--

 >>>>>>>>+<<<<<<<<   isprime=1

 [
  >+

  <-

  =====DUP3=====
  <[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<<<

  =====DUP2=====
  >[>>+>+<<<-]>>>[<<<+>>>-]<<< <


  >>>


  ====DIVIDES=======
  [>+>+<<-]>>[<<+>>-]<   DUP i=div

  <<
  [
    >>>>>+               bool=1
    <<<
    [>+>+<<-]>>[<<+>>-]< DUP
    [>>[-]<<-]           IF i THEN bool=0
    >>
    [                    IF i=0
      <<<<
      [>+>+<<-]>>[<<+>>-]< i=div
      >>>
      -                  bool=0
    ]
    <<<
    -                    DEC i
    <<
    -
  ]

  +>>[<<[-]>>-]<<
  >[-]<                  CLR div
  =====END DIVIDES====


  [>>>>>>[-]<<<<<<-]     if divides then isprime=0


  <<

  >>[-]>[-]<<<
 ]

 >>>>>>>>
 [
  -
  <<<<<<<[-]<<

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

  >>




  ===================================================================
  ======================== OUTPUT NUMBER  ===========================
  ===================================================================
  [>+<-]>

  [
   ======DUP======
   [>+>+<<-]>>[<<+>>-]<


   ======MOD10====
   >+++++++++<
   [
    >>>+<<              bool= 1
    [>+>[-]<<-]         bool= ten==0
    >[<+>-]             ten = tmp
    >[<<++++++++++>>-]  if ten=0 ten=10
    <<-                 dec ten
    <-                  dec num
   ]
   +++++++++            num=9
   >[<->-]<             dec num by ten

   =======RROT======
      [>+<-]
   <  [>+<-]
   <  [>+<-]
   >>>[<<<+>>>-]
   <

   =======DIV10========
   >+++++++++<
   [
    >>>+<<                bool= 1
    [>+>[-]<<-]           bool= ten==0
    >[<+>-]               ten = tmp
    >[<<++++++++++>>>+<-] if ten=0 ten=10  inc div
    <<-                   dec ten
    <-                    dec num
   ]
   >>>>[<<<<+>>>>-]<<<<   copy div to num
   >[-]<                  clear ten

   =======INC1=========
   <+>
  ]

  <
  [
   =======MOVER=========
   [>+<-]

   =======ADD48========
   +++++++[<+++++++>-]<->

   =======PUTC=======
   <.[-]>

   ======MOVEL2========
   >[<<+>>-]<

   <-
  ]

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

  ===================================================================
  =========================== END FOR ===============================
  ===================================================================


  >>>>>>>
 ]
 <<<<<<<<



 >[-]<
  [-]
 <<-
]

======LF========

++++++++++.[-]

prime.bは、atoi.bで入力された数値以下の素数をすべて求めてスペース区切りで出力するプログラムであり、サンプルプログラムの集大成といえる。さすがにこの規模のbrainfuckのソースコードは読みたくない。

255までの素数を出力させたが、未定義の動作は現れなかった。

varia.b

[
most of these require the the numbers to the right of the pointer to be 0

CLR  =   [-]
ADD  =   [<+>-]<
DUP  =   [>+>+<<-]>>[<<+>>-]
SWAP =   [>+<-]<[>+<-]>>[<<+>>-]<
MUL  =   >[-]>[-]<< <[>[>+>+<<-] >[<+>-] <-] >>>[<<<+>>>-]<<<
IF   =   >[-]<[>[-]+<-]> (your program here) <

]

varia.bには汎用的に使えるコードの断片が集められている。 どれも当たり障りのなさそうなコードだが、ここで[-]について考察しておきたい。

いままでセルの値が「負」ではないときに未定義の動作が現れない、という表現を何度か使ってきた。しかし負の値を許容するとこれらのプログラムは意図したとおりに動かない可能性があり、その中にはセルの値を0にするという目的の[-]も含まれている。

  • ラップアラウンドを行わない処理系では[-]がクラッシュするか、無限ループに陥る。
  • サイズの大きい(32ビットなどの)セルでは、[-]が終了するために極端に時間がかかることがある。

セルの値が0のときに-命令を実行しうるサンプルプログラムが存在しなかったことも踏まえると、Urban Müllerはセルが負の値をもつことを想定していない、と考えることができそうである。

まとめ

Urban Müllerの処理系を調べてわかったことをまとめる。

  • 各命令がC言語の文と対応付けて説明されている。
  • 8つの命令以外が無視されることがreadmeで明言されている。
  • 配列の要素数が30000個であることがreadmeで明言されている。しかし不思議なことに、インタプリタではそれが守られていない。
  • 配列の各要素およびポインタは0で初期化されることがreadmeで明言されている。
  • セルのサイズは定義されておらず、ただASCIIコードを扱うことができれば良い。実際、最初の処理系と2番目の処理系でも扱いが異なる。
  • セルが負数を扱えるかどうかは定義されていない。インタプリタの実装ではキーワードsignedやunsignedが使用されておらず、Urban Müllerの意図は感じられない。また、サンプルプログラムにおいて値が0のセルがデクリメントされることはない。
  • 配列外参照を行なったとき動作は定義されていないが、インタプリタで配列外参照を行うとエラーメッセージが出る。
  • EOFの扱いは定義されていない。

雑記

日本語版Wikipediaによると「Müllerが開発したコンパイラのサイズはわずか123バイト、インタプリタは98バイトであった」とのことである8。しかしながら出典が示されていない。そこで適当に「brainfuck 123 bytes」で検索してみたところサイズが一致するコンパイラとインタプリタのアーカイブをひとつ見つけたが9、開発者はUrban MüllerではなくJeffry Johnstonであった。断言はできないが、おそらく日本語版Wikipediaの記述が間違っているのだろう。

ほとんどの出典が示されていないだけでなく、日本語版Wikipediaのbrainfuckの記事は英語版と比べて驚くほど情報の量が少ないのであまり役に立たなかった。

brainfuckに関する情報源としてはbrainfuck - Esolangが最強だと思う。可搬性の問題、歴史、サンプルコードなど、brainfuckに関するあらゆる情報が詳しくまとめられている。もしまだ読んだことがないbrainfuckerがいれば、ぜひ一通り読んでみることをオススメしたい。

  1. “The Brainfuck Programming Language” http://www.muppetlabs.com/~breadbox/bf/ (参照 2019-10-4)「Brainfuck is the ungodly creation of Urban Müller, whose goal was apparently to create a Turing-complete language for which he could write the smallest compiler ever, for the Amiga OS 2.0.」↩

  2. 英語版Wikipediaの情報だが、出典が示されていなかった。"Brainfuck - Wikipedia" https://en.wikipedia.org/wiki/Brainfuck (参照 2019-10-4)「Müller’s original compiler was implemented in machine language and compiled to a binary with a size of 296 bytes. He uploaded the first Brainfuck compiler to Aminet in 1993.」↩

  3. JIS X 3010:2003「プログラム言語C」を参照した。↩

  4. JIS X 3010:2003「プログラム言語C」6.3.1.1「単なる char 型を符号付きとして扱うか否かは，処理系定義とする」↩

  5. JIS X 3010:2003「プログラム言語C」6.2.5「符号無しオペランドを含む計算は，決してオーバフローしない。すなわち，結果を符号無し整数型で表現できないときは，その型で表現しうる最大値より 1 だけ大きい数を法とする剰余を結果とする。」3.4.3「未定義の動作の例としては，整数演算のオーバフローに対する動作がある。」↩

  6. これは未定義の動作とも言い切れないような気がする。というのは、次のようなことを考えたからだ。『int型より小さい型は演算前にint型への暗黙の汎整数拡張が行われるという話がある。このとき、char型をint型に変換して行われた演算の結果をchar型に変換すると、定義された動作のみによってラップアラウンドが行われたことになるのではないか？』自信は全くないのでC言語の規格を調べて動作を理解したかったのだが、AdCに間に合わなくなりそうだった、本記事の趣旨はC言語の仕様を調べることではない、むずかしくてよくわからない、などの理由により諦めた。↩

  7. JIS X 3010:2003「プログラム言語C」7.19.1「EOFは，型が int で，負の値をもつ整数定数式に展開する。」↩

  8. “Brainfuck - Wikipedia” https://ja.wikipedia.org/wiki/Brainfuck (参照 2019-10-5)「実際、Müllerが開発したコンパイラのサイズはわずか123バイト、インタプリタは98バイトであった。」↩

  9. “Index of /brainfuck/compiled/msdos/jeff” http://esoteric.sange.fi/brainfuck/compiled/msdos/jeff/ (参照 2019-10-5)↩