Hello golf in Malbolge

Esolang Advent Calendar 2012 用のエントリです。 Esolang 的な自己紹介としては、今年は ICFP のコンテストのために巨大な befunge プログラムを書きました。

Malbolge 概要

ご存じの人が多いかと思いますが、 Malbolge という超難解言語があります。この言語の難解さは brainfuck などがかわいく見える、というか、私の感覚では ruby と brainfuck くらいの差が brainfuck と malbolge の間には存在しています。いや、もっと広いかもしれず。

Malbolge について一言で紹介すると、「抜群のバランス感覚で適当に設計された神クソゲー」という感じ。ざっくりとした説明としては、 A,C,D の3進10ケタ(つまり0-59048の値を持てる)レジスタと、 59049 個の 0-59048 の値が持てるメモリがあって、その上で VM を実行する感じになっています。なぜ brainfuck に比べてはるかに難しいかというと、シンプルな VM にそこらじゅうに仕込まれた嫌がらせのせいです。具体的には

演算が常識的な規則じゃないので、欲しい値を計算で作るのに探索が必要
常に動いているデータレジスタ。これによって狙った値をロードすることも困難に
実行後に意味が変わるコード。単純なループが書けない
演算時に壊れるデータ。つまり定数をデータとして置くことができ無い
isprint じゃないものを実行すると無限ループ。これはインタプリタのバグだと思われてますが、難しくなる方が面白いので、バグではなく仕様として受け入れられている模様。これによってデータとして使った部分はほぼ実行できなくなる
プログラムとしてメモリに展開されるデータは命令として valid な8種類しかない。インタプリタのバグで isprint じゃないものは置けるというものがあるが、難しくなる方が面白いので、バグであってこの仕様は利用するべきでないとされている模様 (ゴルフ場ではこのバグは修正してあります)
プログラムとしてメモリに展開されるデータは謎の変換が行なわれるので逆変換しておかないといけない。サイズが 59049 に満たないプログラムが与えられた場合、残った空間には 0 ではなく謎演算の結果が埋められる。これはデータを置いた位置によって意味が変わるので、定石的なものが作れなくて都度探索しないといけないことを示す

これらの制約のせいで、基本的に Malbolge プログラムは手で書くことが不可能です。適当に作りたいプログラムに向けてツールを作成して Malbolge プログラムを生成することになると思います。

詳しい仕様は Malbolge でぐぐるとすぐに出てくる、 id:Robe さんのエントリに詳しいです。二つのバグ以外に関しては大変良いまとめになっていますので、こちらを参照してください。

http://d.hatena.ne.jp/Robe/20060824

これらの制約をうまくクリアして、 99 bottles of bear を書いたという偉大な研究があります。

http://www.sakabe.i.is.nagoya-u.ac.jp/~nishida/DB/pdf/iizawa05ss2005-22.pdf

これを読むとなるほどなぁという感じで、自分でも同じようなツールを整備してみたいなぁと思うんですが、かなり手間そうなのでできていません。まあ老後の楽しみ的な感じでしょうか…さらに難しくするとすると nop を消すとか jmp でコードが変わるようにするとかがあるかと思うんですが、アドレススペースの狭さからいよいよコードが書けなくなるだけな気がします。

Hello, world! ゴルフ

さて、言語がクソ難しい上にマイナーなのでやっと本題ですが、 Malbolge で Hello world! ゴルフをしていた、という話です。ここからの話は何を言ってるかさっぱりわからないかと思いますが、対象読者は未来の自分と、これから Malbolge ゴルフに挑戦しようという酔狂な人以外にいないので、全部読み飛ばせば全く問題ないです。というかここまでも全部読み飛ばしたかと思いますが。

まず、 Malbolge のプログラムはコードレジスタ C とデータレジスタ D が両方とも 0 でスタートして、かつ命令を実行するたびにインクリメントされるので、そのままでは常に C==D となって、そのままでは基本的に何もできません。具体的には演算命令を実行したら SEGV します。

というわけで最初の命令で C か D を移動させることになると思います。最初の命令で i で C を移動させると C=99 になり、 j で移動させると D=41 になります。ちなみに命令を実行する場所によって行き先が変わるため、2命令目だと C=98 or D=40 になります。 C>90 にしてしまうと、プログラムが 90 bytes 以上になるのは確定してしまうため、ゴルフとしてはよろしくないです。よって最初の命令を j にして D=41 にするのが良いぽいです。1命令挟んで D=40 でスタートするパターンも試してみたのですが、挟める命令が rotate 命令 * と nop 命令 o しか無いので、最初の H を作るのが遅れてしまってイマイチぽかったです。

さて、これでだいたいの構成が決まって、

j(Hを作って出力)(eを作って出力)...(!を作って出力)v(Hello, world!を作るためのデータ)

という感じになります。 v は出力命令で、 j と v の間は 38 bytes あるので、この範囲でうまいこと Hello, world! が作れれば良いな、ということになります。使う命令は p * の2種類、データは全命令の8種類あるので、 1 byte につきざっくり 4bits の情報があり、だいたい 2bytes あれば 8bits あるので、これに出力命令 < を足してだいたい 3bytes の命令で1文字が作れる計算になるので、 13*3==39 でまぁだいたいおさまりそうです。実際1文字ごとに幅優先探索するプログラムを書いてみると、

jpp<*p<*p<<pp<*pp<pp<*p<pp<pp<*p<*p<*<v??j/?vp?<*??pp?ijv?<v?ji?iv?i<?/<?<*?v

というものが出てきました。これは 77 bytes あり、この探索に使ったのが以下のコードです。 common.h と common.cc は同じディレクトリに置いてあります。

http://shinh.skr.jp/obf/hello.cc

上記のコードで ? になっている部分は、どの命令でも良い部分です。終了命令 v の後にふたつ ? があるのは実際には 2 bytes 命令が余ったことを示していて、後半のデータ部分にたくさんある ? は出力命令 < に対応している部分なのでなんでも良い部分です。

命令の方が 2 bytes あまっているのはもったいないです。最後の ! を出力するために1命令1dataで実現していますが、最後の v を消して、 3 命令と 3 つの自分で自由に完全には決められないデータの組み合わせで ! が出力できないかな、と ruby で適当に全探索をかけてみたところ、うまいこと見つかってくれて、 76B となりました。

この探索は1文字が決まるごとに今までの計算が長期的にも最善であることを仮定しているので、厳密には最短では無い可能性があります。つまり、 H を上のパターンと違うやり方で作れば ! が短くなる、というようなことが原理的にありえます。

というわけで全部探索したいな、と思ったのですが、計算量的にナイーブなものでは無理です。しかし、明らかに計算しなくていい部分が多いのは間違いないので、なんかうまい方法は無いかな、と考えました。

よく考えると、今回の仮定の元では D レジスタは常に C レジスタ + 40 であり、 C レジスタは最大40程度、出力は 13 bytes 、そして A レジスタは 59049 種類の値しか取りえないので、状態数は 3000 万程度しかありません。このくらいの数なら DP で一発です。そこで書いたのがこのコード

http://shinh.skr.jp/obf/hello_dp.cc

実行した結果、上記の命令数が最短であることがわかりました。ただし、幅優先の時に例えば H を同じ 2bytes で同じ A レジスタの値にして作る方法が 6 種類あるなど、上記と同じ命令数を実現する方法は無数にあります。

そう考えてみると、データ部分に何も情報を持っていない個所 (? になっている部分) が結構あるのはもったいないです。最後の方でもう一度 j 命令を使ってデータレジスタをデータ部分の真ん中に戻してきて、データ部分の ? になってる部分の任意性と、余ってる命令を使ってうまいこと 75 bytes 以下にできないかと考えました。 75 bytes に関して手動であれこれいじっていると、

jpp<*p<*p<<pp<*pp<pp<*p<pp<pp<*p<pjp<**<vj/ovpo<*ooppoijvo<v<jioivoi<o/<oo*

というものができ、 75 bytes を達成することができました。 pjp となっている部分の、真ん中の j が D を 60 byte 目に戻してくる部分です。 j と末尾の * の組み合わせでこのちょうどいい感じの位置に戻ってこれるようでした。

さて、この j をもう 1,2 bytes 早く持って来れればあと 1,2 bytes 縮められることになります。ざっとした感覚では、こういった解は存在してもおかしくないけど、かなりキチンと探索しないと見つからなさそうだったので、また C++ コードを書きました。

http://shinh.skr.jp/obf/hello_tweak.cc

このコードの最後の部分の 74 を 73 とかに変えると探す対象を変えられます。 j で飛ぶ直前の命令を探索していないので、 75B には対応できていません。この形の 74B と 73B に関しては完全に探索している、と思います。おそらく…

残念ながら、このコードは数時間ぶん回して終了したものの、首尾よく短い解を見つけることはできませんでした。逆の発想で D を2回目に動かす j を序盤の方に持ってきてやる方法もあるかと思います。この方法で見つかる可能性もおおいにあると思うのですが、ちょっと実験してみた感じでは難しそうで、マジメな探索はまたかなりのコードを書く必要がありそうで、今日までに書くことはできませんでした。

中盤に書いた DP を使った方法で、 D レジスタに関しても DP してやれるといいと思うのですが、この場合既に元々置いたデータが書き変わってしまっている場合があって、なにか難しそうな気がしました。 topcoder な人たちならなんとかなるのかもですが…それ以外にも、私が考えていなかったような方法でもっと短いコードが実現できる可能性はあると思います。誰かやってみてくれませんかね…

まとめると、 Malbolge で Hello, world! をゴルフしようと思うと、 1000 行弱の C++ コードが必要になった、という話でした。