この記事は Brainf*ck Advent Calendar 2019 の 14 日目です。昨日はあんでぃさんの『brainfuck でオセロを書く(後編)』でした。
(自分語りパートです。)
こんにちは。去年 AtCoder で Brainfuck の提出をしまくって Language Owner に載ったものの、最近サボっているため 3 位を脅かされそうになっています。やっぱりこういうのは継続が大事ですね。
最近 Brainfuck を書いた場面といえば、先月学園祭があったのですが、自分の所属しているプログラミングサークルではプログラミングをテーマにした生放送をやっていました。そこに「実用プログラミング言語・難解プログラミング言語のコードゴルフで戦う」という企画があり、プレイヤーとして Brainfuck を書きました。まあ制限時間がシビアなので、お題を満たすコードが書けたらゴルフせずに次の言語に移ったんですけどね……。詳しい話は別の記事でも書いています。あと 18・19 日目の Szkieletor さんの話でもその辺りに触れられると思います。
本題
さて、世の中には Brainfuck の命令を置き換えたり命令を拡張したような有象無象の派生言語がある中(そこまで強く批判しているわけではないです)、当アドベントカレンダーの 3 日目に prime さんがこのような記事を書いてくれました。
というわけで BFmeta で遊んでいきたいと思います。
インタプリタ
まず自分はブラウザ上でなんでもやりたがる人間なので、ブラウザで動かせるインタプリタを作りました。
といっても急に作ろう!となったわけではなくて、上で触れたサークルに現在「コードゴルフ分科会」というのがあって、そこで難解プログラミング言語の処理系を各自作ろうみたいな回があったので、それを機に作ったものです。デザインとか機能とかまだ納得行ってないのでこれから直して行きます。
これでスマホでもプログラムが書けますね!
はろーわーるど
公式にはこんな Hello World が載っています。
[>]<<<<<<<<<<<<<[.>]Hello World!
ヌル文字を許容すると
[>]>[.>]\0Hello World!
(これ試してみたのですが、 ←改行の分だそうです。<
が一個多いような?)
まずは Hello World の他の書き方を探すところから始めます。
Brainfuck ではデータポインタの位置だけ考えれば良かったのが、BFmeta ではプログラムポインタとデータポインタ両方の位置を考える必要があります。Hello World の出力にあたって、プログラムポインタとデータポインタをうまく「分離する」必要があるのですが、単に >
だと揃ってしまうので、[>]
のようにして何らかの境界にデータポインタを引き寄せなければなりません。
ヌル文字許容版を参考にすると、ASCII コードで扱えるうち文字コードが小さいのはタブ(0x09)や改行(0x0a)なので、そのあたりをデリミタにしましょう。
Hello World! ----------[++++++++++.>----------]
これで (文字数) + 35 bytes ですね。複数行に対応するために、処理を一行目に持ってきたらどうでしょう。
----------[++++++++++>----------]>[.>] Hello World!
なんとこれは動きませんでした(最初自作インタプリタのバグを疑いました)。エラーをみると Unmatched bracket ]
と書いてあるのですが、動きを追うと、[
が 10 減らされたところで ]
からジャンプできてないんですね。リフレクション怖い!と思うと同時に BFmeta の可能性を感じるエラーですね。
データポインタを右ではなく左に引き寄せるのはどうでしょう? BFmeta では負のインデックスが扱えることが言語仕様で決まっているので、データポインタを左に追いやればプログラムポインタと別行動をさせられます。
!dlroW olleH>>>>>>>>>>>[.<]
これで (文字数) × 2 + 3 bytes ですね。
もっと考えると、データ領域とプログラム領域を交互に配置することで互いの影響を受けないことがわかります。
[!>d]l<r[o.W< <o]l_l_e_H
これで (文字数) × 2 bytes ですね。そうすると逆に配置する必要もなくなり、
H[e.l>l>o] _W_o_r_l_d_!
これで (文字数) × 2 - 1 bytes ですね。
ところで、よく見るハローワールドはコンマが入っていると思いますが、この例には入っていません。そりゃ、コンマはプログラムに影響を及ぼすので置きたくないですからね。これをごまかさない方法を考えます。
普通の Brainfuck プログラムでコメントアウトしたいときに「メモリが 0 であることが保証されている場所で [
]
で囲む」という手法がありますが、同じように考えて、特殊文字を「エスケープ」することができます。
[H>e.l>l]o[,] _W_o_r_l_d_!
これで、6 文字目以降ならギリギリエスケープできることがわかりました。
以上でわかったのが、「データ領域とプログラム領域を適切に分離することで、今までの Brainfuck と同じように扱える」ということですね。
リフレクション
ここまで来ると、リフレクション、やりたくないですか?
まず命令の文字コードを確認します。
命令 | 文字コード |
---|---|
+ |
0x2B |
, |
0x2C |
- |
0x2D |
. |
0x2E |
< |
0x3C |
> |
0x3E |
[ |
0x58 |
] |
0x5D |
命令に使う文字は、 +,-.
<=>
[\]
みたいに分かれてそこそこ近くに集まっていることがわかります。
というわけで、「そこを最初に通ったときとそれ以降に通ったときで命令が変わる」コードに挑戦してみます。
[>]<<<<<[[>[-]>[-]<<[->+>+<<]>>[-<<+>>]]+<<-__.]
これは自己を書き換えることで +
と -
を交互に出力し続けるコードです。
後ろの -_
の部分が、奇数回目に --
、偶数回目に ++
となります。+
に 2 を足せば -
になるのが原理なんですが、2 を足すには 2 回 +
を書かなければいけなく、それを「2 を引く」にするには両方に 2 を足さなければいけなく、これでは倍々に増えていってしまうので書き換えた -
を右にコピーしています。
こんなんやらなくても +[-.++.-]
のほうが早いので、どう活かせるかというと難しいですね。+
と -
の差が 1 だったらもう少しきれいになったかも……。
>
とか [
の書き換えはプログラムポインタの位置が変わるので +
を考えるより格段に難しいと思います。[
を書き換えると対応を変えられるのでプログラムポインタの大域的な脱出ができたり……とか妄想してますが、よくわかりません。人間の頭で考えられるものなんだろうか……。
誰か BFmeta でできる面白いリフレクション考えてください。