adventar.org2日目はみみねこさんによる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です。命令数はBrainf*ckと同じ8種類です。Brainf*ckとBFmetaの最も大きな違いはプログラム空間とデータ空間が統合されていることです。これにより柔軟なメタプログラミングが可能になります。8bit(1Byte)*2符号なし整数*3の双方向に無限長*4の配列が用意され*5、0番地からプログラムのソースコードが順に格納され、配列のそれ以外の領域は0で初期化される。データポインタとプログラムポインタという二つのポインタがあり、どちらも最初は0番地を指している。命令の意味は次の通り、オリジナルのBrainf*ckとほとんど変更されていません。プログラムポインタは毎ステップの最後に1進められ、プログラムポインタの指す値が次の9種類の文字のいずれかのASCIIコードに等しい場合、それに対応する処理が行われます。それ以外の場合、何も行わず(単にプログラムポインタを1進めて)そのステップを終了します。プログラムを終了するBrainf*ckの仕様をご存じの方なら、Brainf*ckとほとんど同じ仕様であることがわかると思います。実際のBFmetaはBrainf*ckよりかなり表現力に長けた*6プログラミング言語になっています。次節ではその表現力の一部をお見せいたします。Worldソースコード中に書いたデータを実行中に読むことができるので、ソースコード中に文字列を埋め込んでそれを表示するだけです。World!の文字数分だけ戻って、そこから1文字ずつ出力しています。ソースコードにヌル文字を許せば*7、次のように更に短く書けます。インタプリタ標準入力から最初にヌル文字に到達するまでをソースコード、それ以降を標準入力とみなすことにします。[>],[>,]>まずBFmetaソースコードの末尾まで移動し、そこからBrainf*ckのソースコードを読み込み、1Byteデータポインタを進めます(これがないとBrainfckプログラムの終了時にBrainfckプログラムの配列の先頭が0でないときに誤作動してしまう)。最初のソースコードはここまでですが、連続してさっき読み込んだBrainf*ckプログラムが格納してあり、データポインタはここからそれ以降はすべて0で初期化されているため、このままプログラムを実行し続ければ、読み込んだBrainf*ckプログラムをBrainf*ckプログラムとして実行したときの実行結果が得られます。これくらいありますが、それより遥かに短く書けました。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です。思って予めインタプリタ(及びデバッガ)をRubyで書いたものがこちらになります。github.com実行速度があまり速くないので、今度C++かRustで速いインタプリタを書きたいと思っていますが、それはまた別の記事にしたいと思います。その速いインタプリタによって、Brainf*ckに対して本質的な計算量の改善ができる可能性についても、また別の記事にしたいと思います。