最凶言語 Malbolge

プログラム

　プログラムの話題はあまり書かないと言う舌の根も乾かぬうちにプログラムの話題です。


　この世には様々なプログラミング言語がありますが、そんな中にはいくつもの変わった言語があります。チューリング完全な最小の処理系を作る事を目指した Brainf*ck とか、見えない文字のみを使った Whitespace（空白）とか、レシピ風に書く Chef（シェフ）とか、台本風に書く Shakespeare（シェークスピア）とか、実用性とか関係なく、興味深いからとか、面白いからと作られた言語です。これらは難解なので、esoteric programming language（難解なプログラミング言語）と呼ばれています。

　それでは、most esoteric（最も難解）な言語を決めるとしたら何になるでしょうか？　上に書かれたものも分かり辛くはありますが、世の中には「この世で一番分かり辛くする事」を目標とした言語が存在します。それが Malbolge です。


Malbolge 仕様
http://www.antwon.com/other/malbolge/malbolge.txt

Malbolge インタプリタ
http://www.lscheffer.com/malbolge_interp.html

Malbolge - Wikipedia
http://en.wikipedia.org/wiki/Malbolge


　Malbolge は 1988 年に Ben Olmstead によって作られたプログラミング言語です。Malbolge という名前は、ダンテの神曲の地獄篇における、第８圏目の地獄（悪意者の地獄）内での区画（悪の嚢）にちなんで付けられました。その名の通り、Malbolge は意図的に最悪になるよう設計されたプログラミング言語です。なにしろ、初めてのプログラムが提出されたのが言語が出来てから２年後、しかもプログラムに生成させたものだというのだから、それはそれは大変な言語だということが分かると思います（マイナーだったから時間がかかったということもあるでしょうが）。

　今日はそんな最凶言語 Malbolge を紹介してみたいと思います（Wikipedia 用に改変転載したいという人がいれば、勝手にやっちゃって構いません）。なお、公式の仕様は上記のインタプリタと完全には一致していないようなので、上記の標準インタプリタの動作の解説を行う事にします。

　また、上記のインタプリタにはバグがあり、

#if '\n' != 10
        if ( x == 10 ) putc( '\n', stdout ); else
#endif

は

#if '\n' != 10
        if ( a == 10 ) putc( '\n', stdout ); else
#endif

が正しいです（ほとんどの環境で影響は無いと思いますが）。

バーチャルマシンの仕様

　Malbolge はバーチャルマシン上で動くマシン語です。Malbolge のバーチャルマシンは 3 個のレジスタと 59049 ワードのメモリを持っています。このセクションでは、先ずこのバーチャルマシンの仕様に関して解説します。

値

　Malbolge では、値は三進数で扱われます。以下、三進数の値は 0200110201T のように、最後に T を付けて書く事にします。

　1 ワード（１つの値のサイズ）は三進数で 10 桁になります。310 = 10000000000T = 59049 なので、1 ワードで 0 〜 59048 の値が扱える事になります。

　二進数の 1 桁はビット（bit）と呼びますが、三進数ではトリット（trit）と呼ばれます。つまり、1 ワードは 10 トリットになります。

レジスタ

　Malbolge の 3 個のレジスタは A, C, D と名付けられています。これは普通のアセンブリ言語と似たような名付け方で、

A アキュムレータ 計算用レジスタ
C コードポインタ 命令のアドレスを保持するためのレジスタ
D データポインタ 主にデータのアドレスを保持するためのレジスタ

という役割を持っています。Malbolge の命令は、一部を除いてこのレジスタの値を元にして実行されます。

　レジスタのサイズは全て 1 ワードで、最初は 0 で初期化されています。

　以下、「C に格納されている値をアドレスとするメモリ」を [C] のように表記します。C 言語をやってる人だと *C の方が分かりやすいと思いますが、ここはアセンブリ言語風に [C] と記述します。

メモリ

　Malbolge のメモリは 59049 ワードで、先頭から 0 〜 59048 の番号（アドレス）がふられています。命令もデータも全部このメモリ上に置かれます。

命令

　Malbolge は、[C] の値を元にして動作します。この時、[C] の値が直接使われるわけではありません。([C] - 33 + C) mod 94 を求め（x mod y は x を y で割ったときの余り）、その結果をさらに次の変換テーブル（ASCII コードの場合）で変換した値を元に、実行する処理を決定します。

+b(29e*j1VMEKLyC})8&m#~W>qxdRp0wkrUo[D7,XTcA"lI
.v%{gJh4G\-=O@5`_3i<?Z';FNQuY]szf$!BS/|t:Pn6^Ha

この一連の変換演算を crypt1 C と呼ぶ事にします。

　Malbolge の命令は、以下の 8 種類です。もし、これら以外の値が登場した場合は、何もしません（111 と同じ扱い）。

crypt1 C 対応する
ASCII 文字		 疑似アセンブリ言語 動作
106 j mov D, [D] [D] の値を D に代入します。
105 i mov C, [D]
あるいは jmp [D]		 [D] の値を C に代入します。要するに、実行位置を移動します。
42 * rotr [D]
mov A, [D]		 [D] の値を右に 1 桁ローテイトし（一番下の桁を一番上に持って行き）、さらにその結果を A にも代入します。
112 p crz [D], A [D] の値と A の値を元に ある「変な命令」を実行し、その結果を [D] と A の両方に格納します。
60 out A A の値を文字コードと見なして、文字を一文字出力します。
47 / in A 文字を一文字入力し、その文字コードを A に格納します。改行文字の文字コードは必ず 10 になります。
118 v end プログラムを終了します。
111 o nop 何もしません。

　ここで出てきた「変な命令」はトリット演算で、crz x, y はそれぞれの桁について次のような演算規則を持ちます。演算規則とは言っても、別に何らかの法則のある演算ではなく、適当に決められた規則ですが。

x＼y 0 1 2
0 1 0 0
1 1 0 2
2 2 2 1

例えば、crz 0000111222T, 0012012012T は 1100102221T になります。

プログラムの流れ

　Malbolge のプログラムの動作は以下ような流れになります。

  1. メモリにプログラムをロード
  2. 残りのメモリを crz を使って埋める
  3. C の値を元に命令を実行
  4. [C] の値を変更
  5. C と D をインクリメント
  6. 3 に戻る
メモリにプログラムをロード

　プログラムは 1 バイトずつ読み込まれ、Malbolge のメモリの各ワードに先頭から順番に格納されます。ただし、空白（改行等含む）は無視されます。

　全ての値は必ず正規の 8 つの命令のどれかでなくてはなりません。すなわち、m をあるメモリのアドレスとすると、crypt1 m が j, i, *, p, <, /, v, o のどれかにならなくてはなりません。もしそれ以外の値が出現した場合はプログラムのロードに失敗します。

残りのメモリを crz を使って埋める

　プログラムが 59049 ワードより短いときは、残りのメモリは crz 演算を使って、プログラムの直後のメモリから順に埋められて行きます。アドレス m にある値 [m] は、crz [m-2], [m-1] の値で埋められます（crz 演算により [m-2] と [m-1] の値は変更されません）。

C の値を元に命令を実行

　crypt1 C の結果を元に命令を実行します。ただし、プログラムをロードする際とは異なり、[C] の値は必ず 33 〜 126（印字可能な ASCII 文字）でなくてはなりません。それ以外だった場合はフリーズしてしまいます（仕様ではプログラムが終了するとされていますが）。また、crypt1 後に j, i, *, p, <, /, v, o のどれにもならなくても構いません。その場合は、o と同じく、何もしません。

[C] の値を変更

　命令を実行後、[C] の値を変更してしまいます。i（jmp 命令）を実行する場合は、ジャンプ後のメモリの値を変更します。

　この変更は crypt1 とは異なります。[C] - 33 を求め、その結果をさらに次の変換テーブル（ASCII コードの場合）で変換します。

5z]&gqtyfr$(we4{WP)H-Zn,[%\3dL+Q;>U!pJS72FhOA1C
B6v^=I_0/8|jsb9m<.TVac`uY*MK'X~xDl}REokN:#?G"i@

これを crypt2 と呼ぶ事にします。

　この crypt2 の変換は次の 6 つのサイクルに分類されます。

  • 33 → 53 → 45 → 119 → 78 → 49 → 87 → 48 → 123 → 71 → 83 → 94 → 57 → 91 → 106 → 77 → 65 → 59 → 92 → 115 → 82 → 118 → 107 → 75 → 104 → 89 → 56 → 44 → 40 → 121 → 35 → 93 → 98 → 84 → 61 → 100 → 97 → 46 → 101 → 99 → 86 → 95 → 109 → 88 → 47 → 52 → 72 → 55 → 110 → 126 → 64 → 81 → 54 → 90 → 124 → 34 → 122 → 63 → 43 → 36 → 38 → 113 → 108 → 39 → 116 → 69 → 112 → 68 → 33
  • 37 → 103 → 117 → 111 → 120 → 58 → 37
  • 41 → 102 → 96 → 60 → 51 → 41
  • 42 → 114 → 125 → 105 → 42
  • 50 → 80 → 66 → 62 → 76 → 79 → 67 → 85 → 73 → 50
  • 70 → 74 → 70

例えば、crypt2 70 = 74 となり、さらに変換すると crypt2 74 = 70 になります。

　ASCII 文字に直すと

  • ! → 5 → - → w → N → 1 → W → 0 → { → G → S → ^ → 9 → [ → j → M → A → ; → \ → s → R → v → k → K → h → Y → 8 → , → ( → y → # → ] → b → T → = → d → a → . → e → c → V → _ → m → X → / → 4 → H → 7 → n → ~ → @ → Q → 6 → Z → | → " → z → ? → + → $ → & → q → l → ' → t → E → p → D → !
  • % → g → u → o → x → : → %
  • ) → f → ` → < → 3 → )
  • * → r → } → i → *
  • 2 → P → B → > → L → O → C → U → I → 2
  • F → J → F

となります。

C と D をインクリメント

　次の位置の命令を実行する為に、C がインクリメントされます。そして、D も一緒にインクリメントされます。

Malbolge のプログラム

　数少ない Malbolge で書かれたプログラムを紹介します。

Hello, world.（作者：Andrew Cooke）

　"Hello, world." を出力するプログラムです。世界で初めて作られた Malbolge プログラムでもあります。

(=<`:9876Z4321UT.-Q+*)M'&%$H"!~}|Bzy?=|{z]KwZY44Eq0/{mlk**
hKs_dG5[m_BA{?-Y;;Vb'rR5431M}/.zHGwEDCBA@98\6543W10/.R,+O<
入力のコピー（作者：Lou Scheffer）

　入力をそのまま出力するプログラムです。

D'BA@?>=<;:9876543210/.-,+*)('&%$#"!~}|{zyxwvutsrqponmlkji
hgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/
.-,+*)('&%$#"!~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTS
RQPONMLKJIHGFEDC&_ｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽ菴ｽｽ
ｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽ
ｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽ
ｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽ菴ｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽ
ｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽｽ
99 Bottles of Beer（作者：Johannes E. Schindelin）

　「99 Bottles of Beer」という（色んな言語で生成してみることを目的とした）詩を出力するプログラムです。ただし、gzip されたあとに uuencode されてるので、uudecode して gunzip する必要があります。

　非常に長いので、リンクですみません。

http://www.99-bottles-of-beer.net/language-malbolge-375.html

99 Bottles of Beer（作者：Hisashi Iizawa（飯澤 恒））

　こっちは圧縮も暗号化もされていません。この詩はループ構造をとっているので、それを忠実に反映した構造のプログラムにすることを目指して作ったようです。

　これも非常に長いのでリンクで。

http://www.99-bottles-of-beer.net/language-malbolge-995.html

最後に

　「人類が設計しうる最も邪悪な言語」という噂を耳にしたので調べてみましたが、Malbolge はまさにその通りな言語でした（とはいえ、もっと酷い言語を作ろうと思えば作れますが。Malbolge にさらに手を加えればいいだけなので）。そもそも、基本的な演算が crz と rotr だけというのが凄い話です。いつか Malbolge で何か実用的なプログラムを書いてみたいですなあ・・・。