Malbolge
Malbolgeは1998年にBen Olmsteadによって開発された、パブリックドメインの難解プログラミング言語である。名前は、ダンテの神曲地獄篇における地獄の第8圏であるMalebolgeにちなんで名付けられた。
Malbolgeはチューリング完全である[1][2]が、実用言語ではない。Malbolgeの異常な点は、最悪の、すなわち最も扱いにくく難解であるプログラミング言語となるべく設計されたことである。MalbolgeはINTERCAL、機械語、Brainfuckの最悪な部分を組み合わせたものであるという[3]。しかし、理解を困難にするために用いたトリックのいくつかはごく単純化することができる[要出典]。
Malbolgeでのプログラミング[編集]
プログラミング言語Malbolgeが世に出たとき、理解することが非常に難しく、最初に書かれたプログラムが出現するのに2年を要した。しかもそのプログラムは人間によって書かれたものではなく、Andrew Cookeが設計しLISPで実装したビーム探索アルゴリズムにより生成したものだった。
2000年8月24日、Anthony Youhasは彼のブログでMalbolgeを打ちのめし解決の鍵を極めたと宣言し、様々な語句を表示する3つのMalbolgeプログラムコードによりその証拠とした[4]。しかし、どのような技法を用いたかは明らかにはしなかった。
後にLou Schefferは、Malbolgeはプログラミング言語というより暗号システムとして見るべきであり、暗号システムとして見た場合のMalbolgeにはいくつかの脆弱性があると指摘した[5]。また、これらの脆弱性を突くことでMalbolgeプログラムを書くことができるとし、例として入力された文字を出力するプログラムを示した。
OlmsteadはMalbolgeが線形拘束オートマトンであると考えていた。無限ループが初めて発表されるまでに何年も要しており、Malbolgeにおける実用的なループのインプリメント可能性に関し、さらに興味深い議論がある。[要出典]
Malbolgeのプログラム難読化への応用可能性に着目した名古屋大学の酒井正彦らにより、3段階の中間言語やSATソルバを用いてMalbolgeプログラムを生成する手法が提案されている[6][7]。これらの研究成果を用いて、while文や配列、再帰関数などを含むC言語のサブセットをMalbolgeプログラムにコンパイルすることが可能となっている[8]。
Malbolgeで書いたHello, worldプログラム[編集]
次のMalbolgeプログラムは"Hello, world"を出力する。
(=<`:9876Z4321UT.-Q+*)M'&%$H"!~}|Bzy?=|{z]KwZY44Eq0/{mlk**
hKs_dG5[m_BA{?-Y;;Vb'rR5431M}/.zHGwEDCBA@98\6543W10/.R,+O<
脚注[編集]
- ^ 正確には、Malbolgeは言語仕様によりメモリが有限に制限されているため弱チューリング完全である。
- ^ 長坂哲、酒井正彦、坂部俊樹、草刈圭一朗、西田直樹「難解言語Malbolgeのチューリング完全性について」『信学技報』第110巻第227号、一般社団法人電子情報通信学会、2010年10月、 55-60頁、 ISSN 0913-5685。
- ^ The Random Programming Languages List - ウェイバックマシン（2004年4月4日アーカイブ分）
- ^ Antwon, Malbolge guru - ウェイバックマシン（2007年10月13日アーカイブ分）
- ^ [1]
- ^ 安藤聡、酒井正彦、坂部俊樹、草刈圭一朗、西田直樹「Malbolgeの高級アセンブリ言語への配列機能の追加」『信学技報』第112巻第23号、一般社団法人電子情報通信学会、2012年5月、 43-48頁、 ISSN 0913-5685。
- ^ 安藤聡、酒井正彦、坂部俊樹、草刈圭一朗、西田直樹「Malbolge低級アセンブリプログラミングにおける制御命令の配置設計のためのSATソルバの利用」『信学技報』第112巻第373号、一般社団法人電子情報通信学会、2013年1月、 25-30頁、 ISSN 0913-5685。
- ^ 坂梨元軌、河邉翔平、酒井正彦、西田直樹、橋本健二「再帰呼び出しを持つC言語サブセットからMalbolgeへのコンパイラ」『信学技報』第117巻第137号、一般社団法人電子情報通信学会、2017年7月、 145-150頁、 ISSN 0913-5685。
