シリーズ:地獄のプログラミング言語Malbolge完全攻略(第2回/全4回)
書けないように作られたプログラミング言語に、人はどうやってプログラムを書いたのでしょうか。
前回は Esolang(難解プログラミング言語)の世界をざっと見ました。今回は、このシリーズの主役 Malbolge(マルボルジェ)です。
1998年に生まれたこの言語の設計目標は、たった1つ。「プログラムを書くことを、できるだけ不可能にすること」でした。
名前は、ダンテの地獄から

Malbolge という名前は、イタリアの詩人ダンテ・アリギエーリの『神曲』地獄篇に出てくる場所から来ています。
『神曲』の地獄は9つの圏に分かれていて、深い圏ほど重い罪を犯した者が罰を受けます。その第8圏が「Malebolge(マーレボルジェ)」で、イタリア語で「悪の溝」という意味。人をだました者たちが罰を受ける場所です。
第8圏は、さらに10の溝に分かれています。誘惑者、へつらう者、聖職を売り買いした者、占い師、汚職をした者、偽善者、盗人、悪い助言をした者、仲を裂いた者、偽造者。だます罪の種類ごとに、別の溝で罰を受けます。
ダンテの原文のつづりは Malebolge ですが、言語の名前は Malbolge です。人をだまし、混乱させる場所の名前を、プログラマをだまし、混乱させる言語に付けた、ということになります。
1998年、Ben Olmstead

Ben Olmstead は、1998年に Malbolge を作って公開しました。狙いは、Brainfuck や Befunge のような、それまでの難解言語よりも、さらに書きにくい言語を作ることでした。
その難しさは、3つの仕組みが重なってできています。
三進法
ふつうのコンピュータは0と1の2進法で動きますが、Malbolge の仮想マシンは0・1・2の 3進法で動きます。これだけで、ビット演算に慣れた人の勘が働かなくなります。
crazy 演算
データを操作する演算が、わざと直感に反するように作られています。AND、OR、XOR のどれとも違う、独自の表に従う演算です。
自分を書き換えるコード
命令は、実行されたあとに置換表で別の文字に変えられます。同じ場所をもう一度実行すると、前とは違う命令として動きます。プログラムは、走りながら自分を書き換え続ける作りです。
Olmstead 自身は、Malbolge を「線形拘束オートマトン」、つまりメモリの大きさに限りがある機械だと考えていたとされています。チューリング完全かどうかについては、のちに Lou Scheffer が、Malbolge-T という変種ならチューリング完全だ、という考えを示しています。
三進法の仮想マシン

Malbolge は、三進法の仮想マシンの機械語として決められています。その中身を見ておくと、次回の命令の話が分かりやすくなります。
トリットとワード
ふつうのコンピュータの単位がビット(0か1)なのに対して、Malbolge の単位は トリット(0か1か2)です。trinary digit の略です。
1ワードは 10トリット。表せるいちばん大きい値は、三進法で2222222222、十進法で 59,048 です。
メモリ
メモリは 59,049個(アドレス0〜59,048)で、それぞれに1ワードが入ります。
データとコードは、同じメモリを使います。どこからどこまでがコードで、どこからがデータかの区別がありません。プログラムの動きを前もって読むのは、そのぶん、さらに難しくなります。
3つのレジスタ
| レジスタ | 役目 |
|---|---|
| a(アキュムレータ) | 入出力と演算の結果を入れる。メモリに書き込んだ結果も、ここに入る |
| c(コードポインタ) | いま実行している命令のアドレス。命令を1つ実行するたびに1増える |
| d(データポインタ) | データを扱う命令が対象にするアドレス。こちらも命令ごとに1増える |
3つとも、始まったときは0です。
メモリの初期化
実行の前に、プログラムの文字がメモリの先頭から順に読み込まれます。空白は読み飛ばされます。空白以外の文字は、その位置で有効な命令になる文字でなければならず、1文字でも外れれば、読み込みの段階で失敗です。
プログラムの後ろの残りのメモリは、直前の2つのアドレスの値に crazy 演算をかけた値で、順に埋められていきます。こうして埋められたメモリは、12アドレスごとに同じ並びをくり返すことが知られています。
攻略の歴史
1998年に公開されてから、Malbolge でまともにプログラムが書けるようになるまでには、長い時間がかかりました。
2000年:最初のプログラムは、探索が見つけた
公開から 2年後の2000年に、ようやく最初のプログラムが現れます。書いたのは人ではありません。Andrew Cooke が Lisp で書いたビームサーチのプログラムが、ありうるプログラムの中から探し出したものでした。その出力は「HEllO WORld!」。大文字と小文字すら、思いどおりにはできませんでした。
ビームサーチは、幅優先探索の一種で、各段階で見込みのある候補だけを残しながら先へ進む探し方です。Malbolge の最初の Hello World は、書かれたのではなく、見つけられたものでした。
Lou Scheffer の暗号解析

Malbolge の研究でいちばん大きな仕事をしたのが Lou Scheffer です。元のサイトがなくなったあとも、オリジナルのインタプリタと仕様書を保存しました。命令を暗号化する置換表を解析して、その中の循環を見つけ、それを使って入力をそのまま出力する cat のプログラムを作りました。Malbolge でプログラムを書くための、一般的な進め方も示しています。
この解析で、Malbolge のプログラミングは「不可能」から「とても難しい」に下がりました。
2005年:99 Bottles of Beer
2005年、飯沢久(Hisashi Iizawa)さんらが、ループと条件分岐を含む「99 Bottles of Beer」のプログラムを Malbolge で書くことに成功しました。Malbolge でも、意味のあるループが書けることを示した成果です。
2007年:Malbolge Unshackled
2007年、Ørjan Johansen が、メモリの上限を外した Malbolge Unshackled を作りました。ふつうの Malbolge はメモリが59,049ワードに限られますが、Unshackled ではその限りがありません。
2020年:Lisp のインタプリタ
2020年、Kamila Szewczyk さんが、Malbolge Unshackled で Lisp のインタプリタを書きました。最初の Hello World が探索でしか見つからなかった言語で、言語処理系が動いたことになります。
なぜ、ここまで書けないのか
ここまでの話をまとめると、難しさは次の重なりから来ています。
| 仕組み | 困ること |
|---|---|
| 命令が位置で変わる | 同じ文字でも、どのアドレスにあるかで別の命令になる |
| 実行すると暗号化される | 一度実行した命令は、次は別の命令になっている |
| コードとデータが同じメモリ | コードを変えるとデータが変わり、その逆も起きる |
| LOAD や STORE がない | メモリに好きな値を、まっすぐ置く方法がない |
| 分岐は無条件のジャンプだけ | 条件分岐は、自分を書き換えるコードで遠回しに作るしかない |
作者の Olmstead 自身は、Malbolge のプログラムを一度も書いていないとされています。
Hello, world. を出すプログラム

最後に、Hello World のプログラムを1つ見ておきます。
| 1 | (=<`#9]~6ZY327Uv4-QsqpMn&+Ij"'E%e{Ab~w=_:]Kw%o44Uqp0/Q?xNvL:`H%c#DD2^WV>gY;dts76qKJImZkj |
88文字の、でたらめにしか見えない文字列です。手元のインタプリタで実行すると、Hello, world. と出力されました。
これがどういう仕組みで文字を出しているのかは、次回の命令の話を見たあとで、最終回に追います。
次回は、命令の中身へ
次回は、Malbolge の 8つの命令、位置で命令が変わるデコードの仕組み、crazy 演算、実行のたびに起きる暗号化を、1つずつ見ていきます。



コメント