prime's diary

そすうの日々を垂れ流しちゃうやつだよ

メタプログラミング可能なBrainf*ck派生言語BFmeta 【Brainf*ck Advent Calendar 2019 3日目】

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

adventar.org

2日目はみみねこさんによる

mmnkblog.hatenablog.com

でした。4日目はmatsu7874さんによる「RustでBrainfuckインタプリタを実装した話を書けるだろうか?」の予定です。

今回はBrainf*ckの素直な派生言語で、かつメタプログラミングが可能な自作言語、BFmetaの紹介をします。

Brainf*ck派生言語の惨状

Brainf*ckは言語仕様が単純で、コンパイラインタプリタが作りやすいという特徴があります。 そのため、巷にはBrainf*ckの仕様をちょっといじった派生言語がいっぱいあります。

特に多いのが8種類の命令を別の文字列に置き換えただけの派生言語で、Ook!ジョジョ言語などがあります。 しかし、これらの言語は単なる文字列の置き換えに過ぎないため、ソースコードの見栄えが異なる以上の違いはなく、プログラミングする上ではあまり面白くないです。

ほかにも、命令の追加でプログラミングの難易度を下げた言語もあり、ビット演算命令を追加するなどしたBrainCrashが代表的な例です。 しかし、普通に命令を追加しただけでは多少プログラミングが簡単になるだけであまり面白くありません。 また、命令数を増やした分Brainf*ckのシンプルさから来る美しさが失われてしまいます。

かくして、ほとんどのBrainf*ck派生言語はプログラミング言語としてはちっともおもしろくないわけで、その惨状にひどくうなされた私は、夜しか眠れない日々が続きました。

なんとかBrainf*ckの美しさを継承しつつ、本質的な差異をもつ言語が作れないか考えた結果、ついに生み出されたのが、Brainf*ckでメタプログラミング*1を可能にする派生言語、BFmetaです。

BFmeta言語仕様

命令数はBrainf*ckと同じ8種類です。(プログラムの停止を表すヌル文字を9種類目と見ることもできるでしょう) しかし、Brainf*ckとBFmetaの最も大きな違いはプログラム空間とデータ空間が統合されていることです。これにより柔軟なメタプログラミングが可能になります。

まず、8bit(1Byte)*2符号なし整数*3の双方向に無限長*4の配列が用意され*5、0番地からプログラムのソースコードが順に格納され、配列のそれ以外の領域は0で初期化される。 データポインタとプログラムポインタという二つのポインタがあり、どちらも最初は0番地を指している。

命令の意味は次の通り、オリジナルのBrainf*ckとほとんど変更されていません。 プログラムポインタは毎ステップの最後に1進められ、プログラムポインタの指す値が次の9種類の文字のいずれかのASCIIコードに等しい場合、それに対応する処理が行われます。 それ以外の場合、何も行わず(単にプログラムポインタを1進めて)そのステップを終了します。

  • + データポインタの指す値を1増やす
  • - データポインタの指す値を1減らす
  • > データポインタの値を1増やす
  • < データポインタの値を1減らす
  • . データポインタの指す値を標準出力に出力する
  • , 標準入力から1Byte読み、データポインタの指す先に格納する
  • [ データポインタの指す値が0なら、プログラムポインタをこの[に対応する]の位置まで進める(今のプログラムポインタの位置から正方向に配列を舐めていき、[の数と]の数が等しくなったら停止)
  • ] データポインタの指す値が0以外なら、プログラムポインタをこの]に対応する[の位置まで進める(今のプログラムポインタの位置から負方向に配列を舐めていき、[の数と]の数が等しくなったら停止)
  • \0(ヌル文字) プログラムを終了する

Brainf*ckの仕様をご存じの方なら、Brainf*ckとほとんど同じ仕様であることがわかると思います。 しかしながら、実際のBFmetaはBrainf*ckよりかなり表現力に長けた*6プログラミング言語になっています。 次節ではその表現力の一部をお見せいたします。

BFmetaプログラミング

Hello World

ソースコード中に書いたデータを実行中に読むことができるので、ソースコード中に文字列を埋め込んでそれを表示するだけです。

[>]<<<<<<<<<<<<<[.>]Hello World!

一旦データの末尾まで移動した後、Hello World!の文字数分だけ戻って、そこから1文字ずつ出力しています。 ソースコードにヌル文字を許せば*7、次のように更に短く書けます。

[>]>[.>]\0Hello World!

Brainf*ck インタプリタ

標準入力から最初にヌル文字に到達するまでをソースコード、それ以降を標準入力とみなすことにします。

[>],[>,]>

まずBFmetaソースコードの末尾まで移動し、そこからBrainf*ckのソースコードを読み込み、1Byteデータポインタを進めます(これがないとBrainfckプログラムの終了時にBrainfckプログラムの配列の先頭が0でないときに誤作動してしまう)。 最初のソースコードはここまでですが、連続してさっき読み込んだBrainf*ckプログラムが格納してあり、データポインタはここからそれ以降はすべて0で初期化されているため、このままプログラムを実行し続ければ、読み込んだBrainf*ckプログラムをBrainf*ckプログラムとして実行したときの実行結果が得られます。

Brainf*ck自身でBrainf*ckインタプリタを書くと短いものでも https://arxiv.org/html/cs/0311032 これくらいありますが、それより遥かに短く書けました。

BFmetaでBFmeta自身のインタプリタを書くのはもう少し難しいです。(配列が負の方向に伸びないと仮定するなら、Brainf*ckインタプリタとほぼ同じにはなるのですが…)

Quine

空のソースコードをQuineと言い張ればBFmeta以外にもBrainf*ckやRubyでも0ByteのQuineが書けたことになりますが、それでは面白くないので、大抵は正の長さのソースコードであることが求められます。

keisukenakano.hatenablog.com

では404BytesのBrainf*ckのQuineが紹介されています。これでも十分短いのですが、BFmetaではなんと1文字のQuineが存在します。

.

まあソースコードをデータとして保持しているので、当たり前ではあります。

このソースコードには改行を含んではいけないことに注意してください。そのため、環境によってはうまく表示されないことがあります。

改行を含めたソースコードをQuineしたい場合は次のようにしてください。

[.>]

これでもBrainf*ckに比べてコード長が1/80です。

BFmeta処理系

こんなに表現力が向上したプログラミング言語、書いてみたい、実行してみたいですよね! そう思って予めインタプリタ(及びデバッガ)をRubyで書いたものがこちらになります。

github.com

実行速度があまり速くないので、今度C++かRustで速いインタプリタを書きたいと思っていますが、それはまた別の記事にしたいと思います。 そして、その速いインタプリタによって、Brainf*ckに対して本質的な計算量の改善ができる可能性についても、また別の記事にしたいと思います。乞うご期待。

*1:より正確にはリフレクション

*2:2008年になってようやく、IEC 80000-13により1Byte=8bitと定義されました

*3:オーバーフロー時にビットレベルで同じ挙動をするなら、符号付き整数でも良い

*4:初期は正の方向にのみ無限長だったが、メタプログラミングしやすくするためには、負の方向にも進めるようにしたほうが良い

*5:本当に用意する必要はなく、遅延評価をすることで有限のメモリでインタプリタを実現可能

*6:どちらもチューリング完全なので、計算可能なクラスは同一です

*7:POSIXによるテキストファイルの定義を満たさなくなってしまいますが…