Malbolge

Malbolgeは1998年にBen Olmsteadによって開発された、パブリックドメインの難解プログラミング言語である。名前は、ダンテの神曲地獄篇における地獄の第8圏であるマーレボルジェ(Malebolge)にちなんで名付けられた。

Malbolgeはチューリング完全である^{[注釈 1]}^[1]が、実用言語ではない。Malbolgeの異常な点は、最悪の、すなわち最も扱いにくく難解であるプログラミング言語となるべく設計されたことである。MalbolgeはINTERCAL、機械語、Brainfuckの最悪な部分を組み合わせたものであるという^[2]。しかし、理解を困難にするために用いたトリックのいくつかはごく単純化することができる^[要出典]。

Malbolgeでのプログラミング

プログラミング言語Malbolgeが世に出たとき、理解することが非常に難しく、最初に書かれたプログラムが出現するのに2年を要した。しかもそのプログラムは人間によって書かれたものではなく、Andrew Cookeが設計しLISPで実装したビーム探索アルゴリズムにより生成したものだった。

2000年8月24日、Anthony Youhasは彼のブログでMalbolgeを打ちのめし解決の鍵を極めたと宣言し、様々な語句を表示する3つのMalbolgeプログラムコードによりその証拠とした^[3]。しかし、どのような技法を用いたかは明らかにはしなかった。

後にLou Schefferは、Malbolgeはプログラミング言語というより暗号システムとして見るべきであり、暗号システムとして見た場合のMalbolgeにはいくつかの脆弱性があると指摘した^{[注釈 2]}。また、これらの脆弱性を突くことでMalbolgeプログラムを書くことができるとし、例として入力された文字を出力するプログラムを示した。

OlmsteadはMalbolgeが線形拘束オートマトンであると考えていた。無限ループが初めて発表されるまでに何年も要しており、Malbolgeにおける実用的なループのインプリメント可能性に関し、さらに興味深い議論がある。^[要出典]

Malbolgeのプログラム難読化への応用可能性に着目した名古屋大学の酒井正彦らにより、3段階の中間言語やSATソルバを用いてMalbolgeプログラムを生成する手法が提案されている^[4]^[5]。これらの研究成果を用いて、while文や配列、再帰関数などを含むC言語のサブセットをMalbolgeプログラムにコンパイルすることが可能となっている^[6]。

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インタプリタ用の機械語である。

標準のインタプリタと公式の仕様が完全には一致していない^[7]。コンパイラは33–126の範囲外のデータにおいて実行を停止させるという違いがある。これは当初はコンパイラのバグとされていたが、Ben Olmsteadはこれを意図した動作であり、実際には「仕様のバグ」であるとした^[8]。

レジスタ

Malbolgeにはa、c、dの3つのレジスタがある。プログラムの開始時点では、3つのレジスタの値はすべて0である。

aはアキュムレータ (Accumulator) の略であり、メモリへの書き込み命令や標準入出力に使われる。cはコード (Code) ポインタであり、現在の命令を指すプログラムカウンタである^[9]。dはデータ (Data) ポインタである。各命令後に自動的にインクリメントされるが、これが指す場所はデータ操作コマンドにしか使われない。

ポインタの表記

dはメモリアドレスを表す。[d]はレジスタ間接、すなわちそのアドレスに格納された値を表す。[c]についても同様。

メモリ

仮想マシンは59,049 (3¹⁰) のメモリ空間を持ち、それぞれ10桁の三進数を格納することができる。各メモリ空間には0から59048までのメモリアドレスが割り当てられ、0から59048までの値をとることができる。この上限を超えてインクリメントした場合、0に戻る。

この言語ではデータと命令が同じメモリ空間を使用する。これはx86アーキテクチャなどのハードウェアの仕組みに影響されている。^[8]

Malbolgeのプログラムが始まる前に、メモリの初めの部分はプログラムで埋められる。プログラム中のホワイトスペースはすべて無視され、そのほかはすべて下記の命令のいずれかで始まらなければならない。これはプログラミングをより難しくするためのものである。

メモリの残りは前2つのアドレスに対するcrazy演算（後述）で埋められる ([m] = crz [m - 2], [m - 1])。この方法で埋められたメモリは12アドレスごとに繰り返しのパターンになる。

Ørjan JohansenはMalbolgeの精神をできる限り維持したうえでチューリング完全な言語を作りたいと考え、2007年にメモリ制限の無いバージョンであるMalbolge Unshackledを開発した。それ以外のルールは変わっていないため、メモリ制限に達していない通常のMalbolgeのプログラムもすべて完全に動く^[10]。

命令

Malbolgeには8つの命令がある。どの命令を実行するかを決めるために、[c]の値にcの値を加え、94で割った余りを用いる。計算結果と実行する命令の対応は下表のとおり。

命令
([c] + c) % 94	命令	説明
4	jmp [d]	[d]の値をcに代入する。この命令の実行後にcをインクリメントするため、次に実行されるのは ([d] + 1 (modulo 59049)) 番地の命令である。
5	out a	aの値をASCII文字として画面に出力する。
23	in a	入力された文字のASCIIコードをaに代入する。改行は10、ファイル終端は59048を代わりに代入する。
39	rotr [d] mov a, [d]	[d]の値を1桁回転させる（0002111112が2000211111になる）。結果を[d]とaに代入する。
40	mov d, [d]	[d]の値をdに代入する。
62	crz [d], a mov a, [d]	[d]の値とaの値のcrazy演算（後述）をする。結果を[d]とaに代入する。
68	nop	何もしない。
81	end	Malbolgeプログラムを終了する。
（上記以外）	68と同じ（何もしない）。上記以外の値はプログラムのロード直後には許されないが、実行中には許可される。

各命令が実行された後、[c]を暗号化（後述）する。これにより暗号化される命令は、ジャンプ命令が実行された場合はジャンプ先の命令、そうでない場合は実行された命令である。暗号化により、次に同じ番地に処理が戻ってきても違う処理がされる。暗号化の後、cとdが1増え、次の命令が実行される。

crazy演算

入力の三進数における桁ごとに、下表を用いて結果を求める。例として、crz 0001112220, 0120120120は1001022211である。

*crazy*演算^[8]^[11]
crz		入力2
crz		0	1	2
入力1	0	1	0	0
	1	1	0	2
	2	2	2	1

暗号化

各命令の実行後、cをインクリメントする前に、[c]の値を ([c] mod 94) に置き換える。その後、結果を以下に示す等価な2つの方法で暗号化する。

方法1: 下記において、結果に対応する文字のASCIIコードを[c]に代入する。

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

方法2: 下表において、結果に対応する暗号を[c]に代入する。

暗号表
結果	暗号	結果	暗号	結果	暗号	結果	暗号	結果	暗号
0	57	19	108	38	113	57	91	76	79
1	109	20	125	39	116	58	37	77	65
2	60	21	82	40	121	59	92	78	49
3	46	22	69	41	102	60	51	79	67
4	84	23	111	42	114	61	100	80	66
5	86	24	107	43	36	62	76	81	54
6	97	25	78	44	40	63	43	82	118
7	99	26	58	45	119	64	81	83	94
8	96	27	35	46	101	65	59	84	61
9	117	28	63	47	52	66	62	85	73
10	89	29	71	48	123	67	85	86	95
11	42	30	34	49	87	68	33	87	48
12	77	31	105	50	80	69	112	88	47
13	75	32	64	51	41	70	74	89	56
14	39	33	53	52	72	71	83	90	124
15	88	34	122	53	45	72	55	91	106
16	126	35	93	54	90	73	50	92	115
17	120	36	38	55	110	74	70	93	98
18	68	37	103	56	44	75	104

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はこのアイデアを用いて、ユーザの入力をそのまま出力するプログラムを作った。

注釈

^ 正確には、Malbolgeは言語仕様によりメモリが有限に制限されているため弱チューリング完全である。
^ [1]

出典

^ 長坂哲、酒井正彦、坂部俊樹、草刈圭一朗、西田直樹「難解言語Malbolgeのチューリング完全性について」『信学技報』第110巻第227号、一般社団法人電子情報通信学会、2010年10月、55-60頁、ISSN 0913-5685。
^ The Random Programming Languages List - ウェイバックマシン（2004年4月4日アーカイブ分）
^ Antwon, Malbolge guru - ウェイバックマシン（2007年10月13日アーカイブ分）
^ 安藤聡、酒井正彦、坂部俊樹、草刈圭一朗、西田直樹「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。
^ Green, Austin (2000年12月1日). “Malbolge”. Louisiana Tech University. 2017年6月9日閲覧。
^ ^a ^b ^c Temkin, Daniel (2014年11月3日). “Interview with Ben Olmstead”. esoteric.codes. 2021年1月7日閲覧。
^ Olmstead, Ben (1998年). “Malbolge Specification”. www.lscheffer.com. 2017年6月9日閲覧。
^ Johansen, Ørjan (2013年10月25日). “An interpreter for the Malbolge Unshackled dialect” (Haskell). oerjan.nvg.org. 2017年6月9日閲覧。
^ 飯澤恒. “難読プログラミング言語Malbolgeにおけるプログラム構成手法”. 名古屋大学. 2017年6月9日閲覧。

外部リンク

[1] 正確には、Malbolgeは言語仕様によりメモリが有限に制限されているため弱チューリング完全である。

[5] [1]

[2] 長坂哲、酒井正彦、坂部俊樹、草刈圭一朗、西田直樹「難解言語Malbolgeのチューリング完全性について」『信学技報』第110巻第227号、一般社団法人電子情報通信学会、2010年10月、55-60頁、ISSN 0913-5685。

[3] The Random Programming Languages List - ウェイバックマシン（2004年4月4日アーカイブ分）

[4] Antwon, Malbolge guru - ウェイバックマシン（2007年10月13日アーカイブ分）

[6] 安藤聡、酒井正彦、坂部俊樹、草刈圭一朗、西田直樹「Malbolgeの高級アセンブリ言語への配列機能の追加」『信学技報』第112巻第23号、一般社団法人電子情報通信学会、2012年5月、43-48頁、ISSN 0913-5685。

[7] 安藤聡、酒井正彦、坂部俊樹、草刈圭一朗、西田直樹「Malbolge低級アセンブリプログラミングにおける制御命令の配置設計のためのSATソルバの利用」『信学技報』第112巻第373号、一般社団法人電子情報通信学会、2013年1月、25-30頁、ISSN 0913-5685。

[8] 坂梨元軌、河邉翔平、酒井正彦、西田直樹、橋本健二「再帰呼び出しを持つC言語サブセットからMalbolgeへのコンパイラ」『信学技報』第117巻第137号、一般社団法人電子情報通信学会、2017年7月、145-150頁、ISSN 0913-5685。

[9] Green, Austin (2000年12月1日). “Malbolge”. Louisiana Tech University. 2017年6月9日閲覧。

[:0-10] Temkin, Daniel (2014年11月3日). “Interview with Ben Olmstead”. esoteric.codes. 2021年1月7日閲覧。

[11] Olmstead, Ben (1998年). “Malbolge Specification”. www.lscheffer.com. 2017年6月9日閲覧。

[12] Johansen, Ørjan (2013年10月25日). “An interpreter for the Malbolge Unshackled dialect” (Haskell). oerjan.nvg.org. 2017年6月9日閲覧。

[:1-13] 飯澤恒. “難読プログラミング言語Malbolgeにおけるプログラム構成手法”. 名古屋大学. 2017年6月9日閲覧。

[注釈 1]

[1]

[2]

[3]

[注釈 2]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

結果	暗号	結果	暗号	結果	暗号	結果	暗号	結果	暗号
0	57	19	108	38	113	57	91	76	79
1	109	20	125	39	116	58	37	77	65
2	60	21	82	40	121	59	92	78	49
3	46	22	69	41	102	60	51	79	67
4	84	23	111	42	114	61	100	80	66
5	86	24	107	43	36	62	76	81	54
6	97	25	78	44	40	63	43	82	118
7	99	26	58	45	119	64	81	83	94
8	96	27	35	46	101	65	59	84	61
9	117	28	63	47	52	66	62	85	73
10	89	29	71	48	123	67	85	86	95
11	42	30	34	49	87	68	33	87	48
12	77	31	105	50	80	69	112	88	47
13	75	32	64	51	41	70	74	89	56
14	39	33	53	52	72	71	83	90	124
15	88	34	122	53	45	72	55	91	106
16	126	35	93	54	90	73	50	92	115
17	120	36	38	55	110	74	70	93	98
18	68	37	103	56	44	75	104

結果	暗号	結果	暗号	結果	暗号	結果	暗号	結果	暗号
0	57	19	108	38	113	57	91	76	79
1	109	20	125	39	116	58	37	77	65
2	60	21	82	40	121	59	92	78	49
3	46	22	69	41	102	60	51	79	67
4	84	23	111	42	114	61	100	80	66
5	86	24	107	43	36	62	76	81	54
6	97	25	78	44	40	63	43	82	118
7	99	26	58	45	119	64	81	83	94
8	96	27	35	46	101	65	59	84	61
9	117	28	63	47	52	66	62	85	73
10	89	29	71	48	123	67	85	86	95
11	42	30	34	49	87	68	33	87	48
12	77	31	105	50	80	69	112	88	47
13	75	32	64	51	41	70	74	89	56
14	39	33	53	52	72	71	83	90	124
15	88	34	122	53	45	72	55	91	106
16	126	35	93	54	90	73	50	92	115
17	120	36	38	55	110	74	70	93	98
18	68	37	103	56	44	75	104