Zenn
😈

難解言語 Malbolge でラクして FizzBuzz

2023/09/03に公開
#
fizzbuzz
#
esolang
#
Malbolge
tech

はじめに

背景

みなさんご存じのことと思いますが、Malbolge とは esolang の中でも悪魔的に嫌らしい難解言語と言えます。ちなみになぜか Brainf**k がよく比較対象にあがりますが、こちらはシンプルで全然難しくありません。
そして最近、このような記事がありました。難解言語 Malbolge は HelloWorld に「2 年」かかった こちらは非常に興味深い内容ではあったのですが、同時に「そんなに(golf等の)拘りなかったらラクに組めるのでは?」という感想もいだきました。そこで、折角なので FizzBuzz をラクして Malbolge で組もうと思い立ち、簡単なツールを作って実現したため、折角なので記事にしたという次第になります。

概要

ところで、なぜ FizzBuzz なのかというと、それは Hello, world と同じく「決められた固定データを出力する」という意味で、類似の問題に対処していると見做せるからです。
つまり、今回実現した内容は次のようにまとめられます。

  • (ある程度までの規模で) 文字列が与えられた際、その内容を出力する Malbolge コードを生成することを、簡単なツールを作って実現した。

実際に、ツール群はgithubのリポジトリで公開し、その成果はTIO(try it online!)でのFizzBuzz実行例 や、TIOでのHello,world実行例 で確かめることができます。

導入

基本のアイデア

さて、Malbolge のヤバさ楽しさは背景の章で紹介したQiitaの記事で十分知ることができますが、まず気付く厄介なポイントは次の通りでしょう。

  • 命令を実行する毎に、その命令が変換されるため ( XLAT2 )、ループを組んで再利用するのが困難
  • データを操作する命令が3進数1桁右巡回シフトと、いわゆるcrazy演算しかなく、狙った値を生成するのが困難
  • 命令ポインタ(C)だけでなくデータポインタ(D)も命令毎に増え続けるため、データポインタを巻き戻してデータを再利用するのが困難
  • プログラムのコードとして許される文字が、コード位置毎にASCII33～126の範囲で8種類しかなく、これが初期データも兼ねている

しかし、厄介に見える中で4番目、これは実は「コード位置が替われば8種類の内訳も変わっていくのでデータにバリエーションを持たせることができる」というメリットも秘めています。しかも文字出力は mod 256 の世界の話で済むので、ピンポイントな値でなくても済むという優しさを秘めています。であれば、「一度使った命令・データを使い捨てにしつつ、コード位置によるデータのバリエーションを活かして好みの値を作りつつ出力する」ことを繰り返せば、極めてラクして実装できるのではないでしょうか? これが基本のアイデアとなります。

実現する上での課題

コード位置毎に変化する使用可能文字

Malbolgeは、命令実行毎にデータをXLAT1変換にかけて命令内容を決定するため、コード位置毎にどの文字が8種類のどの命令に対応するかリニアに変化していきます。しかも、コード全体を最初にメモリにロードする時に候補外の変換結果になる文字は許容されません。地味にコードを表現するのが面倒です。

そこで、各命令に改めて独自に名前をつけ、コード位置に応じて適切なMalbolgeコードに変換するコンバータを最初に作ることにしました。リポジトリにはmalconv.rbというファイル名で保存しています。これだけでも実装の見通しが、それはもう真夏の日中位に明るくなります。

以下、その命令を説明文中でも使いますので、ここで紹介します。
※レジスタのC,Dと一部文字が被っていて紛らわしいことに後から気付きましたが、そこは文脈で判断して貰えると幸いです。

  • D : XLAT1変換後のj : Dレジスタ(データアドレス)の変更 D=*D
  • I : XLAT1変換後のi : Cレジスタ(命令アドレス)の変更 C=*D
  • R : XLAT1変換後の* : ローテート演算 A=*D=rotr(*D)
  • C : XLAT1変換後のp : crazy演算 A=*D=crazy(A,*D)
  • P : XLAT1変換後の< : 文字出力 putc(A)
  • G : XLAT1変換後の/ : 文字入力 A=getc()
  • E : XLAT1変換後のv : プログラム終了 exit()
  • N : XLAT1変換後のo : 何もしない nop()
  • ? : (実行時に使われないため) 任意のコードで良いことを示す文字として導入、コンバータではNとして扱う

C,Dレジスタの値の分離

当初、「なにも調整しなければ C=D、つまり命令がそのままデータとして使えるのでなんとかできるか」と軽く考えていたのですが、直ぐに壁にぶち当たってしまいました。
実は C=D のままだと、*D を書き換えるデータ操作命令で直ぐに異常終了してしまうのです。

これは、命令実行後に *C を書き換える ( XLAT2変換 ) という言語仕様から来るものです。この時、実は書き換え前のデータとして命令文字列候補のASCII33～126を前提としているため、データ操作命令で *D ( つまり *C と同じメモリ位置 ) に作られる大抵の数値データではこの候補に収まらず、言語エンジン内部で配列外参照を引き起こしてしまうのです。

この件に関して、shinhさんによるHello golf in Malbolgeが非常に参考になりました。つまり、プログラムの最初でC,Dの値にC＜Dとなるように差をつけて、前半部分に命令、後半部分にデータを配置すれば良いのです。
ただ、このshinhさんの記事は非常に小規模なコードでの話であり、使っているのは D=C+40 と命令を配置するには容量が心許ない例になっています。なのでそこは頑張って C=48, D=2197 の状態を作り出してアドレス48～を各文字の出力用命令、2197～をデータ領域としてコードを配置し、1命令毎に使い捨てていく構成を実現しました。

出力文字の作り方

さてここがある意味一番大事なポイントです。
出力用の文字データをAレジスタに作るためには、Rによるローテート、Cによるcrazy、後は地味ながらGによる値の取得 ( 入力無しを前提としてEOFに対応する59048の固定値の取得) の3種類を駆使する必要があります。
この中で、Aレジスタの内容に結果が左右されるのはCによるcrazyのみです。が、毎回毎回Aの内容を意識して探索するのなんてラクとは言えません。

そこで、そんなややこしい探索はすっぱり諦めて、値が一意に決まる R や G を起点にして C を何回か繰り返して好みの値を作る、そういう対応に決めました。つまり、そのときのデータアドレス位置と作りたい文字によって、一意にコードを決めることができるわけで、探索も単純に全検索すればよく、非常にラクができます。
※注: R で値が一意に決まるのは、Aレジスタへの値格納用のためだけに、コードから来る初期データをその一度きりの処理で済ますためです。何度も同じメモリ位置を処理するなら、もちろん話はもっと複雑になります。

ざっくり1文字進めるごとに8種類強の選択肢 ( 使えるデータの種類が変動するので、N で値を保留する、という選択肢も考慮に入れます ) と考えると、mod 256 の世界なんてせいぜい深さ3～4の探索で済むはずです。
※実際、一部が深さ5、最悪のケースでも深さ6で済み、大抵は3～4の深さで探索が済んでいます

ちなみにコード位置によるバリエーションは mod 94 の世界で 94通りなので、出力用文字として改行(10)とASCII32～126の範囲の96通りとしても、せいぜい10,000通りの探索結果をデータベースとして持っておけば、直ぐに適切なコードが決定できるわけです。なんてラクなんでしょう!
この探索用の補助ツールは、リポジトリにsearch-op-pattern.rbとして保存しています。

例えば、データの配置をアドレス3,000(=86 mod 94)で考える場合、空白文字(ASCII 32)を作るためには、次の3命令で実現できます。

  • アドレス3,000のI (コード j : 106) を R によりローテートし、A=19718 を得る
  • アドレス3,001のC (コード E : 69) を C によりcrazy演算にかけ、A=crazy(19718,69)=9867 を得る
  • アドレス3,002のG (コード { : 123) を C により crazy演算にかけ、A=crazy(9867,123)=19744=32 mod 256 を得る

ツールによるコード生成

以上のネタを元にして、固定テキスト出力用のコードを生成するツールを作成しました。
これはリポジトリにmksrc4fixed.rbとして保存しています。

コード生成ロジック

最初に、コードのテンプレートとして N*6 DRDN DRDN DRDN DD N>25 I ?>35 GE ?>47 E N>2196 E というのを決めておき、アドレス48～とアドレス2197(末尾)～を、出力したいテキストに従って適切なコードに置き換えていく、という形になります。
なお、コンバート用のツールの書式の話になるのですが、* は同一命令の繰り返し回数指定、> は指定のアドレスまでの同一命令繰り返しを意味するため、このテンプレートは次のものと同じです。4行目先頭から文字データ生成・出力用命令を、末尾の E の後に対応するデータを埋め込んでいくことになります。

繰り返しを展開したテンプレート(16文字区切り)
NNNNNNDRDNDRDNDR
DNDDNNNNNI??????
???GE??????????E
…(N のみ 134行分)
NNNNE

例えば ABC と3文字を出力するコード ( TIOでの実行例 ) であれば、命令として RCCPRCCPNGCP を、データとして NIC?CDI???I? をテンプレートに埋め込む形になるのですが、次のような内訳になっています。

  • 1文字目のA
    データアドレス2197開始のため、RCC の3命令とデータ NIC の3文字で mod 256 での65 を作成し、P で1回出力 ( 出力時もDは進むため、? で埋める )
  • 2文字目のB
    データアドレス2201開始のため、RCC の3命令とデータ CDI の3文字で mod 256 での66 を作成し、P で1回出力 ( 出力時もDは進むため、? で埋める )
  • 3文字目のC
    データアドレス2205開始のため、NGC の3命令とデータ ??I の3文字で mod 256 での67 を作成し、P で1回出力 ( N,Gの時はデータ参照しないため ? で埋める )

テンプレートの内容

後残りは、「テンプレートの内容をどのように決めたか」ですが、ここはちょっと頭を使っています。
まず前提として、初期データとしてメモリに記録されるのは、コード長以降に埋められる領域を除くと 33～126 の範囲のデータに過ぎず、命令を埋めるのに必要なアドレス帯を確保するための「そこそこ大きな値」になっていません。
今回、FizzBuzz には zz のような同じ文字の繰り返しを除くと 355文字分のデータ生成が必要であり、余裕を見てざっくり2,000文字程度の命令用領域の余裕が欲しいところです。( 逆に多すぎるとコードサイズが膨れるのでほどほどに済ませたい )
つまり、何とか2,000程度の値を作った上で D 命令で D レジスタにセットしたいのですが、そのためには R命令によるローテートで何度か同じメモリ位置を書き換えていく必要があります。
※C命令によるcrazy演算は、実はこれくらいの丁度いい値を作るのには不向きです。

そこで、前述のようなテンプレートを考えて組んだわけですが、これにより次のように処理を進めていきます。

  • C=0～5 ( D=0～5 )
    • Nで特になにもせず、C,Dのみインクリメントさせる
  • C=6 ( D=6 )
    • D ( コード " : 34 ) で、D=34 をセットする
  • C=7～10 ( D=35,36,46,47 )
    • R で、インクリメントされた D=35 にある G ( コード R : 82 ) がローテートにより 19710 に変わる
    • D により、今度は D=36 にある E ( コード - : 45 ) により、D=45 をセットする
    • N で一命令何もせず回し、C,Dをインクリメントさせる
    • D により、その時の D=47 にある E ( コード " : 34 ) で、再び D=34 に戻す
  • C=11～14 ( D=35,36,46,47 )
    • C=7～10 と同じように R,D,N,D を実行し、D=35 にある 19710 のみ 6570 に変わる
  • C=15～18 ( D=47,35,36,46 )
    • C=7～10, C=11～14 と同じように R,D,N,D を実行し、D=35 にある 6570 のみ 2190 に変わる
  • C=19 ( D=35 )
    • 今度は D を実行することで、D=35 にある 2190 をローテートする代わりに D に値をセットする
  • C=20～24 ( D=2191～2195 )
    • N でひたすら命令を回し C,D のみインクリメントさせる
  • C=25 ( D=2196 )
    • I により、その時の D=2196 にある E ( コード / : 47 ) で、C=47 をセットする
      ※アドレス47まで、これまでの処理に使ったデータが幾つかあるので、命令位置をすっ飛ばす
  • C=48～2196 ( D=2197～ )
    • 以降、文字出力用に埋め込んだ命令が実行される
    • 残った部分は N で埋められるため、特に何も処理せず進む
    • C=2196 には E が置いてあるため、そこでプログラムが終了する ( C=25 の時に I で使うデータとのオーバーラップ )

ということで、目出度く固定のテキストを出力するプログラムが実現できている、ということです。

おわりに

ということで、終わってみれば難解言語 Malbolge といえども、かなりラクに組めることがお判りいただけたと思います。
まあ流石に「コードを再利用する」という形で Malbolge に取り組むのはかなり難しい問題ではあると思うのですが、こういった実装例をきっかけに取り組む人が増えると良いのではないかなあと思います。( 無責任 )

Discussion