Malbolge
Malbolgeは1998年にBen Olmsteadによって開発された、パブリックドメインの難解プログラミング言語である。名前は、ダンテの神曲地獄篇における地獄の第8圏であるマーレボルジェ(Malebolge)にちなんで名付けられた。
Malbolgeはチューリング完全であるが、実用言語ではない。Malbolgeの異常な点は、最悪の、すなわち最も扱いにくく難解であるプログラミング言語となるべく設計されたことである。MalbolgeはINTERCAL、機械語、Brainfuckの最悪な部分を組み合わせたものであるという。しかし、理解を困難にするために用いたトリックのいくつかはごく単純化することができる。
プログラミング言語Malbolgeが世に出たとき、理解することが非常に難しく、最初に書かれたプログラムが出現するのに2年を要した。しかもそのプログラムは人間によって書かれたものではなく、Andrew Cookeが設計しLISPで実装したビーム探索アルゴリズムにより生成したものだった。
2000年8月24日、Anthony Youhasは彼のブログでMalbolgeを打ちのめし解決の鍵を極めたと宣言し、様々な語句を表示する3つのMalbolgeプログラムコードによりその証拠とした。しかし、どのような技法を用いたかは明らかにはしなかった。
後にLou Schefferは、Malbolgeはプログラミング言語というより暗号システムとして見るべきであり、暗号システムとして見た場合のMalbolgeにはいくつかの脆弱性があると指摘した。また、これらの脆弱性を突くことでMalbolgeプログラムを書くことができるとし、例として入力された文字を出力するプログラムを示した。
OlmsteadはMalbolgeが線形拘束オートマトンであると考えていた。
Malbolgeのプログラム難読化への応用可能性に着目した名古屋大学の酒井正彦らにより、3段階の中間言語やSATソルバを用いてMalbolgeプログラムを生成する手法が提案されている。これらの研究成果を用いて、while文や配列、再帰関数などを含むC言語のサブセットをMalbolgeプログラムにコンパイルすることが可能となっている。
次のMalbolgeプログラムは"Hello, world"を出力する。
<pre>
(=<`:9876Z4321UT.-Q+*)M'&%$H"!~}|Bzy?=|{z]KwZY44Eq0/{mlk**
hKs_dG5[m_BA{?-Y;;Vb'rR5431M}/.zHGwEDCBA@98\6543W10/.R,+O<
</pre>
Malbolgeは三進仮想マシンであるMalbolgeインタプリタ用の機械語である。
標準のインタプリタと公式の仕様が完全には一致していない。コンパイラは33–126の範囲外のデータにおいて実行を停止させるという違いがある。これは当初はコンパイラのバグとされていたが、Ben Olmsteadはこれを意図した動作であり、実際には「仕様のバグ」であるとした。
Malbolgeにはa、c、dの3つのレジスタがある。プログラムの開始時点では、3つのレジスタの値はすべて0である。
aはアキュムレータ (Accumulator) の略であり、メモリへの書き込み命令や標準入出力に使われる。cはコード (Code) ポインタであり、現在の命令を指すプログラムカウンタである。dはデータ (Data) ポインタである。各命令後に自動的にインクリメントされるが、これが指す場所はデータ操作コマンドにしか使われない。
dはメモリアドレスを表す。[d]はレジスタ間接、すなわちそのアドレスに格納された値を表す。[c]についても同様。
仮想マシンは59,049 (310) のメモリ空間を持ち、それぞれ10桁の三進数を格納することができる。各メモリ空間には0から59048までのメモリアドレスが割り当てられ、0から59048までの値をとることができる。この上限を超えてインクリメントした場合、0に戻る。
この言語ではデータと命令が同じメモリ空間を使用する。これはx86アーキテクチャなどのハードウェアの仕組みに影響されている。
Malbolgeのプログラムが始まる前に、メモリの初めの部分はプログラムで埋められる。プログラム中のホワイトスペースはすべて無視され、そのほかはすべて下記の命令のいずれかで始まらなければならない。これはプログラミングをより難しくするためのものである。
メモリの残りは前2つのアドレスに対するcrazy演算(後述)で埋められる ([m] = crz [m - 2], [m - 1])。この方法で埋められたメモリは12アドレスごとに繰り返しのパターンになる。
Ørjan JohansenはMalbolgeの精神をできる限り維持したうえでチューリング完全な言語を作りたいと考え、2007年にメモリ制限の無いバージョンであるMalbolge Unshackledを開発した。それ以外のルールは変わっていないため、メモリ制限に達していない通常のMalbolgeのプログラムもすべて完全に動く。
Malbolgeには8つの命令がある。どの命令を実行するかを決めるために、[c]の値にcの値を加え、94で割った余りを用いる。計算結果と実行する命令の対応は下表のとおり。
各命令が実行された後、[c]を暗号化(後述)する。これにより暗号化される命令は、ジャンプ命令が実行された場合はジャンプ先の命令、そうでない場合は実行された命令である。暗号化により、次に同じ番地に処理が戻ってきても違う処理がされる。暗号化の後、cとdが1増え、次の命令が実行される。
入力の三進数における桁ごとに、下表を用いて結果を求める。例として、crz 0001112220, 0120120120は1001022211である。
各命令の実行後、cをインクリメントする前に、[c]の値を ([c] mod 94) に置き換える。その後、結果を以下に示す等価な2つの方法で暗号化する。
方法1: 下記において、結果に対応する文字のASCIIコードを[c]に代入する。
方法2: 下表において、結果に対応する暗号を[c]に代入する。
Lou SchefferによるMalbolgeの暗号解析において、以下に示す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 ...
これらのサイクルを使うことで、毎回違う動作をするループを作り出し、最終的には反復動作を指せることができる。Lou Schefferはこのアイデアを用いて、ユーザの入力をそのまま出力するプログラムを作った。