Brainf**k講座(2) 数値入力と簡単なループ

はじめに

前回より始まりましたBrainf**k講座、実際のコードを通じて、少しずつできることを増やしていく予定です。

講座一覧

  1. Hello, BF!
    導入およびシンプルなループによる数値生成
  2. 数値入力と簡単なループ
    ,による入力と数値解釈、簡単なループの実例

実行環境

前回紹介していませんでしたが、Brainf**kを実行できる環境について。ちょっと組んでみたコードを動かしたくなった時に使えるものを紹介します。

  • ideone
    オンラインのIDE環境で、bffという処理系が使えます。この講座は基本的にこのbffに対応したものです。
  • Brainf**kインタープリタ
    あじさんという方が作られたブラウザ上で動くインタプリタです。細かい挙動の調整や、途中のセルの状態のダンプができたり、重宝しています。
    ※オプションで「バッファの型」を「4バイト符号付き整数」、「標準入力の終端」を「-1」と設定すると、bffと同じ挙動になります。

今回の話題

入力命令

今回は、最後の命令,の導入です。これでもう8種類全てが出そろいます。

  • , … 1文字入力し、その文字コードを現在のセルに保存する。
    ※入力がない場合は、特定の値 ( -1 や 0 ) が保存される。

「特定の値」というのは処理系によって変わります。この講座では、ideoneで使用されているbffという処理系に準じ、-1 を使うものとします。

※-1について
Brainf**kのセルは、他の言語の整数型と同じく、保持できる最大の数があり、そこから+で増やすとまた 0 に戻ります ( 逆に 0 から減らした場合は最大の数になります )。ただし、実行環境によってはできないものもあります。ideoneのbffという処理系では最大の数は$2^{32}-1$ですが、この数を便宜上-1としています。

数値の入力~1桁の場合

さて、それでは数値が入力から与えられるような問題があった場合、どのように対処すれば良いでしょうか。まずは簡単に、1桁の数値の時で考えます。

そうすると、文字としての“0”~“9”の入力を,で扱う場合、文字コード48~57としてセルに保存されますから、そこから48を引くことで数値が得られることになります。
入力時のセルをI、その右隣をTとすると、次のようなコードで、文字コード→数値変換ができ、Iのセルに変換した値が残ります。これは、前回のループをそのまま使っているものです。

I,>T++++++[T-<I-------->T]T

簡単なループ

それでは、入力値によって繰り返し回数の変わる、簡単なループの例を挙げてみます。

  • 入力値 ( 1桁 ) の分、“BF”を出力する ( 改行はしない )

これまでは、ループの回数はコード上の固定値でしたが、ここを入力由来の数値に置き換えれば良いです。次のような実装が考えられます。

コードに“memory layout”というコメントを記載していますが、これは各セルの位置関係 ( と役割 ) を表すものです。複雑なコードになってくると、こういった情報も載せておくと混乱が少なくなります。

閑話休題、このコードは次のような構成になっています。

  • 8行目は出力用の文字のコード生成 ( B,F両方に使う )
  • 10行目は入力された数字を数値に変換
  • 12行目はループによる出力

12行目のループで、各セルがどのように処理されているかを図解したのが次の図です。Iが8から始まった場合です。

f:id:ange1:20160702093103p:plain

今回は、出力用の文字コードを1セルで共有し、“B”(66)→“F”(70)に増やしてまた元に戻す、ということを繰り返しています。( 元に戻すことで、ループ毎に同じ挙動になる )
そして、Iが0になるまで2~4を繰り返すことで、入力された数字の回数分、“BF”が出力される、となります。

複数桁の数字の解釈

しかし、これでは1桁の数字しか対応できません。複数の、かつ不定長の桁数の数字に対応できなければ、実用としては厳しいでしょう。

そこで、入力の処理をループにして、複数桁の数字を解釈する方法を考えてみます。
数字は10進数で、上位の桁から入力されて来るわけなので、1桁増える毎にこれまで解釈された数値を10倍していけば、そしてそこに新たな桁分を加算していけば良いでしょう。Rubyで書くと次のような感じです。

a=0
while i=$<.getc
  a=a*10+(i.ord-48)
end

このような処理をBrainf**kで行う場合、入力文字を制御変数としたループを記述します。

ここでは、改行無し、EOF(入力値-1)まで数字が続く場合の例を挙げます。

I,+[
 (ループ内処理)
I,+]

基本的な骨組みは上のようになります。Iは入力文字コードを保存するセルです。ループ開始前と、各ループの最後に,で入力を行い、EOF(-1)かどうかを判定しています。EOFに達して-1が入力されると、直後の+によってセルの値が 0 になりますから、ループを終了するようになっています。

ここに、1桁の数字→数値変換、上位桁を10倍して新たな桁を足す処理を加えると、次のようになります。

* memory layout : WAIT
I,+[
 * convert *
 >T+++++++[-<I--------->T]
 * x10
 <<A[-<W++++++++++>A]
 * move back to A
 <W[->A+<W]
 * add the new digit
 >>I[-<A+>I]
I,+]

数字から数値の変換は、今度は-49 ( 7×7 ) になっていることに注意してください。これは,の入力値を+1した状態でループに入っているからです。

さて、ループ処理中の“x10”は前回出たループと同じです。ただ、Aから10倍した数字は一旦Wに保存されますから、結果をAに保持し続けることを考えると、また“move back to A”によってAに戻します。これはループによる1倍の掛け算に相当します。

そして今度、入力値IはAへの加算に使用します。これによって、ループを繰り返す毎に、これまで入力された桁分の数値がAに保存されるようになっています。

それでは、先ほどの「入力された数字の分だけ“BF”を出力する」を複数桁に対応させたバージョンです。数値の解釈部分 ( と、セルの位置関係 ) を変えただけになっていることが分かるかと思います。

今回のまとめ

  • ,は文字を入力し、その文字コードをセルに保存します
  • EOFに達した場合、,はEOFに対応した値 ( ideoneのbffでは-1 ) を保存します
  • 実行環境によりますが、セルの保持できる最大値から1増やすと0に戻り、0から1減らすと最大値になります。便宜上-1とはこの最大値のことを言います。
  • ,入力した文字コードから48を引くことで数値に変換できます。
  • 入力文字コードに+1してEOFを検出することで入力ループを作ることができます。

おわりに

これでもう既に、数値入力の処理ができるようになりました。みるみるBrainf**kの実力が上がっていくのが体感できることでしょう。次は、不定長の複数セルを活用するスライド型のループで、ループの幅を広げていきたいと思います。