말레볼제

말레볼제(영어: Malbolge)는 벤 올름스테드(Ben Olemstead)가 1998년에 만든 난해한 프로그래밍 언어로, 그 이름은 단테의 신곡에 나오는 지옥 중 제8옥인 말레볼제에서 왔다.

말레볼제의 특징은 존재할 수 있는 가장 최악의 (가장 어렵고 난해한) 프로그래밍 언어로 설계되었다는 것이다. 하지만 이해를 어렵게 만들기 위해 사용된 방법 중 몇몇은 단순화할 수 있다.

역사

말레볼제가 처음 발표되었을 때 매우 이해하기 어려웠기 때문에, 첫 말레볼제 프로그램이 만들어질 때까지는 2년이 걸렸다. 이 프로그램은 사람의 손으로 쓰여진 것이 아니다. 이 프로그램은 앤드루 쿡(Andrew Cooke)이 디자인하고 리스프로 구현된 빔 탐색 알고리즘을 통해서 만들어졌다.

2000년 8월 24일에, Anthony Youhas는 자신의 블로그에 "말레볼제의 신비를 벗겨냈다"고 소개하면서 그 증거로 여러 문장을 출력하는 세 개의 말레볼제 프로그램을 제시하였다. 하지만 그는 그 프로그램을 만드는 방법에 대해서는 언급하지 않았다.

그 뒤, Lou Scheffer가 말레볼제의 암호학적 분석을 하고 입력을 출력으로 되돌리는 프로그램을 공개했다.

올름스테드는 말레볼제가 튜링 완전하다고 생각하였으나, 말레볼제 프로그램이 접근할 수 있는 메모리 공간의 한계 때문에, 말레볼제의 상태 모델은 유한하며 따라서 말레볼제는 튜링 완전하지 않다. 또 다른 흥미로운 제안은 말레볼제로 실용적인 루프를 구현할 수 있느냐는 것인데 이는 7년 만에 가능한 것으로 밝혀졌다.

2004년 8월 19일에, Tomasz Wegrzanowski는 임의의 문자열을 출력하는 말레볼제 프로그램을 생성하는 생성기를 만들었다. 그에 따르면, 이 생성기는 이동 명령을 무시하고, D 레지스터를 메모리의 맨 처음을 가리키게 한 후, A 레지스터가 필요한 값이 될 때까지 NOP, ROT, 그리고 Crazy 연산을 반복하여 원하는 값을 만들어 낸다. 이 방법으로 만들어진 프로그램은 Anthony의 프로그램보다 훨씬 더 크다.

2005년에 이자와 히사시(飯澤恒)는 〈난해한 프로그래밍 언어 말레볼제의 프로그래밍 방법(難読プログラミング言語Malbolgeにおけるプログラム構成手法〉이라는 논문을 통해 말레볼제에서 반복문을 구현하는 방법을 보였으며, 그 예제로 "99 bottles of beer" 프로그램을 만들었다.[1] 그는 Crazy 연산의 조합으로 덧셈 등의 연산을 구현하고, 일정한 횟수만큼 메모리를 접근해서 원하는 값을 만들어 내는 방법을 사용하였다.

말레볼제로 만든 "Hello, world" 프로그램

다음 프로그램은 "Hello, world."라는 문장을 출력한다.

(=<`:9^o^876Z4321UT.-Q+*)M'&%$H"!~}|Bzy?=|{z^o^]KwZY44Eq0/{mlk** hKs_dG5[m_BA{?-Y;;Vb'rR5^o^431M}/.zHGwEDCBA@98\6543W10/.R,+O

구성

말레볼제는 삼진법 가상 머신, 즉 말레볼제 인터프리터의 기계어이다. 표준 인터프리터와 공식 명세서의 내용은 서로 약간 다른데, 여기서는 실제로 작동하는 프로그램을 만들 수 있도록 표준 인터프리터의 작동을 설명하겠다.

레지스터와 포인터

말레볼제에는 다른 언어들의 변수와 대응되는 세 개의 레지스터, 즉 a, c, d 레지스터가 있다. 프로그램이 실행될 때 세 레지스터의 값은 모두 0이다. c 레지스터는 현재 실행되는 명령을 가리키는 특수한 용도로 사용된다.

아래에서 [d]는 d 레지스터의 값이 메모리 주소이며, [d]는 그 주소에 저장되는 값이라는 것을 나타낸다. [c]도 마찬가지이다.

메모리

가상 머신에는 각각 10자리 삼진수 숫자를 저장할 수 있는 59049개의 메모리 공간이 있다. 각각의 공간에는 0부터 59048까지의 주소가 붙어 있으며 0부터 59048까지의 값을 저장할 수 있다. 59049가 저장될 경우 0으로 바뀐다.

말레볼제 프로그램이 시작되기 전에, 메모리의 앞부분이 프로그램으로 채워진다. 프로그램에 들어 있는 모든 공백 문자는 사라지며, 프로그래밍을 더욱 더 어렵게 하기 위해, 공백 문자를 제외한 프로그램은 아래에 설명된 명령 중 하나로 시작하여야 한다.

나머지 메모리 공간은 이전의 두 메모리 주소를 crazy 연산으로 계산한 값으로 채워진다 ([m] = crz [m-2], [m-1]). 이 방법으로 채워진 메모리는 12개 간격으로 그 값이 반복된다. (각각의 삼진수 한 자리는 3개나 4개 간격으로 그 값이 반복되기 때문에, 전체 값은 12개 간격으로 반복된다고 할 수 있다)

명령

말레볼제에는 여덟 개의 명령이 있다. 말레볼제는 [c]의 값에 c를 더하고, 그 값을 94로 나눈 나머지에 따라 어떤 명령을 실행할 지 결정한다. 각각의 결과에 따라 실행되는 명령은 다음과 같다.

([c] + c) mod 94	어셈블리 표현	설명
4	jmp [d] + 1	[d]의 값에 1을 더한 위치로 이동해서 그 위치부터 프로그램 실행을 진행한다.
5	out a	a의 값을 아스키 문자로 화면에 출력한다.
23	in a	문자 하나를 입력받아서, 그 문자의 아스키 코드를 a에 넣는다. 개행문자는 항상 10으로 입력되며, 파일의 끝(EOF)에서는 59048이 입력된다.
39	rotr [d] mov a, [d]	[d]의 값을 3진수 한 자리만큼 돌린다. (즉 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	프로그램을 종료한다.

위에 속하지 않는 모든 값은 68과 같은 역할(아무 일도 하지 않음)을 한다. 이 값들은 프로그램이 처음에 불릴 때는 허용되지 않지만 프로그램이 실행되면서 메모리 공간이 바뀐 상태에서는 명령으로 쓰일 수 있다.

각각의 명령이 실행된 후, 해당 명령은 아래에서 설명하는 방법으로 암호화되어서, 이동 명령이 실행되지 않았다면 다음에 실행되었을 때 같은 역할을 하지 않게 된다. 이동 명령이 실행되었을 경우에는 현재 명령이 아닌 이동된 위치 바로 앞에 있는 명령이 암호화된다. 그 후, c와 d의 값이 1씩 증가한 후 다음 명령이 실행된다.

Crazy 연산

두 숫자의 각각의 3진법 자리마다 다음 표를 적용해서 결과를 얻는다. 예를 들어서 crz 0001112220, 0120120120의 결과는 1001022211이다.

crz		Input 2
crz		0	1	2
Input 1	0	1	0	0
	1	1	0	2
	2	2	2	1

암호화

명령이 실행된 후, [c]의 값이 94보다 작을 때까지 94를 뺀다. 그 결과는 다음과 같은 (실제로는 완전히 같은) 두 방법을 통해 암호화되어 다시 [c]에 저장된다.

첫째 방법

다음에서 결과값을 찾은 후, 그 아래에 있는 문자의 아스키 코드를 [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

둘째 방법

다음 표에서 결과값을 찾은 후 대응되는 저장할 값을 [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의 말레볼제를 암호학적으로 분석한 결과에서는 암호화 과정에서의 다음과 같은 여섯 개의 사이클을 언급하고 있다:

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는 이 아이디어를 (아래에 링크된 그의 분석 결과에 포함되어 있는) 사용자의 입력을 모두 출력으로 되돌리는 말레볼제 프로그램을 만드는 데 사용했다.