BFのすゝめ

この記事は Misoca+弥生 Advent Calendar 2019 の8日目です。

はじめに

生きてると処理系を書きたくなることありますよね。私はあります。

今回は衝動の赴くまま、今回は Brainf*** を作ることにしました。

正規式名称にfから始まる4文字ワードが含まれているので、* で伏字しています。あまり書いてて気持ち良いものではないので、以降この文章ではBFと呼びます。

みなさん。BF作りましょう。

BFとは

シンプルな仕様で、使うのが難しいプログラミング言語です。

BFの特徴は、

  • 8つの命令しかない
  • メモリが、リニアな30000バイトの空間を持つ

くらいしょうか。

(チューリング完全という特徴もあるのですが、説明すると長くなるのでここでは書きません)

この記事を書くためにBFの仕様を調べていて、 The Brainfuck Programming Language を読んで知ったのですが、最初に作られたのは Amiga OS2.0 用の実装だったんですね。...Amiga...この記事を読む人は知ってるかな...。

今回作るBFの仕様

最初に仕様が世にでてからもうだいぶ立ちます。 Brainfuck - Wikipedia によれば登場時期は1993年だそうなので、26年前ですね(...だいぶ前だな)。

それくらい前から仕様が存在しているので、実装は世の中にあまた存在しています。すでに他の実装をご存知の方も多いことでしょうし、自作されたことがある方もいることでしょう。

世に出ている実装には元の仕様から機能拡張されているものもありますが、今回は単純かつ小さめな仕様・実装でいきます。 基本は The Brainfuck Programming Language の仕様に従いますが、メモリサイズなど独自なところもあります(仕様で定義されていないところも含みます)。

仕様

基本設計

メモリ

  • メモリは、次の二つを持ちます
    • instructions メモリ
    • data メモリ
  • 二つのメモリはどちらも64KBのサイズとします
  • instructions メモリは起動時にプログラムを格納します
    • プログラムのサイズが64KB未満の場合は0で初期化します
  • data メモリは起動時に、すべて0で初期化します

レジスタ

レジスタとして以下を持ちます。

  • instruction pointer
    • 実行中の命令の位置を保持します
    • 16bit
  • data pointer
    • 命令実行中のメモリの読み書き位置を保持します
    • 16bit
  • bracket depth
    • [ ]のネストの深さを保持します(詳細は後述)
    • 16bit

命令セット

The Brainfuck Programming Language に書かれている命令だけを実装します。 それ以外の文字はすべて無視します。 各命令がASCIIコードの1文字となります。マルチバイト文字は考慮しません。

>    Increment the pointer.
<    Decrement the pointer.
+    Increment the byte at the pointer.
-    Decrement the byte at the pointer.
.    Output the byte at the pointer.
,    Input a byte and store it in the byte at the pointer.
[    Jump forward past the matching ] if the byte at the pointer is zero.
]    Jump backward to the matching [ unless the byte at the pointer is zero.

上記説明の pointer は、今回作るBFにおける data pointer にあたります。

実装

実装は https://github.com/ryotarokawakami/bf に置きました。cloneするなどして自由にご確認ください。

C言語で実装しているので、実行のためにはビルドが必要です。

(macbookで開発していたので、他の環境だとmakefileを書き換えないとダメかもしれません)

ファイルのロード

https://github.com/ryotarokawakami/bf/blob/master/src/utils.h を見ればわかりますが、ファイルのロード、ロードしたデータの削除は utils で提供しています。BFのインタプリタではファイルは扱いません。メモリ上にある命令列だけを対象に処理をします。

命令の実行

実装は https://github.com/ryotarokawakami/bf/blob/master/src/vm.c#L40 のあたりになります。

CPUのエミュレーションを実装するときにインタプリタの形式を採用すると同じような実装になります。1命令ずつ読み込んで実行する流れが見えると思います。 (読み込んだ値が 0 の場合は命令がないと解釈して処理を終えるようループの条件を作っているので、 HALT命令が実装されていると言えばされていますね)

[] はちょっとだけ面倒な仕様になっているので、ちょっとだけ面倒な実装になっています。

[]

仕様では、

[    Jump forward past the matching ] if the byte at the pointer is zero.
]    Jump backward to the matching [ unless the byte at the pointer is zero.

と書かれているので、対応する括弧を探す必要があります。 たとえば、

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

のようにプログラムがあるとき、最初の [ の括弧に対応する ] は、プログラムの一番右側に現れる ] であって、その2つ前にある ] ではないということです。

レジスタbracket depth を持たせたのは、対応する括弧を探しやすくするためです。 [ が見つかると bracket depth を +1、] が見つかると bracket depth を -1 するようにしています。 ジャンプする場合は https://github.com/ryotarokawakami/bf/blob/master/src/vm.c#L77https://github.com/ryotarokawakami/bf/blob/master/src/vm.c#L96 で処理します。 それぞれが 20 行に満たない処理なので、読めばすぐにわかると思います。シンプル。

ビルド

トップディレクトリで make してください。 bf という実行ファイルがトップディレクトリに作成されるはずです。

macbookで開発していたので他の環境ではビルドを試していませんが、もしビルドに失敗するとしても makefile を少し変更するだけでビルドできるようになると思います。 オプションに -std=c11 をつけてますが c99 でもビルドできると思います。

サンプルの実行

さて、 ビルドして bf という実行ファイルが作れたでしょうか。

サンプルとして samples/hello.bf を入れたので実行してみましょう。

./bf samples/hello.bf

どうでしょうか。実行結果はこんな感じになったでしょうか。

Hello, World!

BFのプログラムはなにしろ難解になるので、わかりやすさ優先で書いてみましたがいかがでしょうか。何をしているか理解できるでしょうか。

理解できない人がいるかもしれないので、最初の1行だけ解説してみます。

[ H: 72]

行頭の [ H: 72] の部分は、単なるコメントです。

BF のインタプリタは初期化時に data pointer を0 にします。data[0] は 0 です。そのため [ ] の中は処理されず、 instruction pointer は ] の後まで飛びます。 突然 data[0] が出てきたようにみえるかもしれませんが、基本設計のところで書いた data メモリ の0番地を data[0] と表記しているだけです。

] の直後のスペース

続いて、] の直後には (半角スペース) があります。 これは命令ではないので、無視されます。

++++++++++

この時点で data pointerは 0 を指しています。そのため、+ を一つ処理すると data[0] の値が+1されます。 + は10個あるので、すべて処理すると data[0] の値は10となります。

[

この時点ではまだ data pointer は 0 です。bracket depth も 0 です。 data[0] の値が 10 なので [ では対応する ] に飛びません。[ を処理するときに bracket depth を+1して 1 にします。

>+++++++<-]

> で data pointer が +1 されます。 続く +++++++ で data[1] の値が 7 になります。

さらに < で data pointer が-1され、 - で data[0] の値が-1されます。

そして ] で対応する [ に飛ぶかどうかを判定します。

大丈夫でしょうか。理解が追いついているでしょうか。

つまりここまでの ++++++++++[>+++++++<-] という処理は、

  1. data[0] を10にする
  2. ループに入る
  3. data[1] を7にする
  4. data[0] を9にする
  5. data[1] を14にする
  6. data[0] を8にする
  7. ...
  8. data[1] を70にする
  9. data[0] を0にする
  10. ループを出る

という動きになり、 7を10回足す 、つまり 7 × 10 の計算をしているのと同じことになります。 7 × 10 の掛け算をするだけで22命令使うなんてかわいいやつですね。

>++.>

ループから出たとき、 data pointer は 0 を指しています。

> で data pointer を +1 します。 ++ で data[1] を +2 するので、 この時点で data[1] は 72 となります。 . で data[1] をputchar() します。72 は ASCII コードH です。 > で data pointer を +1 します。ここで data pointer は 2 となります。 data[2] は初期値のまま 0 です。 改行コードは命令にない文字なので無視されます。

これで1行分の解説は終わりです。

おわりに

いかがでしたでしょうか。8命令という単純な仕様でいろいろプログラミングができてしまうなんて、BF 楽しくないですか?私は実装していてすごく楽しかったです。

この記事の冒頭でも書きましたが、BFは26年も前から存在する仕様で、実装も世の中にあまたあります。 実装者はみんな、仕様が単純かつ短時間で書けるプログラミングのお題として楽しんでいたのではないかなと思ってます。

BFのプログラムも多くの人が公開しています。 HelloWorldをはじめ、実に様々なプログラムが存在します。 個人的にお気に入りのコードが マンデルブロ集合の印字 です。 いやスゴイですね。プログラムしようという発想も実行結果も実にカッコイイです。 プログラムの内容は安定の難解さですが、読み解きたい気持ちが湧き上がってきますね(読み解いたとは言っていない)。

世のプログラマの多くが楽しんできた BF 、みなさんも年末年始のお休みあたりに楽しんでみてはいかがでしょうか。たぶん2時間もあれば実装できると思います。

最後になりますが、私が実装した BF でマンデルブロ集合のプログラム実行結果と、比較のために WegGLで作成したマンデルブロ集合 の画像を貼っておきます。

次回、 Misoca+弥生 Advent Calendar 2019 の9日目は mai_goto さんです。お楽しみに!


BFの実行結果とWebGLでの描画との比較

BFの実行結果

f:id:ryotaway:20191208000605p:plain:w400

WebGLで描画した結果

f:id:ryotaway:20191203010226p:plain:w400