말레볼제
"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차
1. 개요
말레볼제는 1998년에 만들어진 난해한 프로그래밍 언어이다. 최초의 말레볼제 프로그램은 2년 후에 등장했으며, 앤드루 쿡이 설계하고 리스프로 구현된 빔 탐색 알고리즘을 통해 생성되었다. 말레볼제는 튜링 완전성을 갖추지 못했지만, 2000년대 초반부터 암호학적 분석과 튜링 완전성을 위한 시도가 이루어졌다. 2020년에는 리스프 인터프리터가 발표되었고, C 언어 서브셋을 말레볼제 프로그램으로 컴파일하는 기술도 개발되었다. 말레볼제는 세 개의 레지스터와 메모리를 사용하며, 8개의 명령어를 가지고 있다. 또한, Crazy 연산과 암호화 과정을 통해 난해성을 더한다. 말레볼제의 변형으로 Malbolge20, Malbolge-T, Malbolge Unshackled 등이 있으며, "Hello, world" 프로그램과 cat 프로그램의 예시가 있다.
더 읽어볼만한 페이지
- 영어 기반이 아닌 프로그래밍 언어 - 두리틀 (프로그래밍 언어)
두리틀은 다국어 지원, 터틀 그래픽스 기반 직관적인 프로그래밍, 충돌 감지, 음악 지원, 프로토타입 기반 객체 지향 특징을 갖춘, 레고 조립 방식의 쉬운 프로그래밍 언어로서 다양한 운영체제와 웹 브라우저를 지원한다. - 영어 기반이 아닌 프로그래밍 언어 - 비펀지
비펀지는 1993년 크리스 프레시에가 만든 자기 수정 능력을 강조하는 2차원 격자 구조의 스택 기반 난해한 프로그래밍 언어이다. - 난해한 프로그래밍 언어 - HQ9+
HQ9+는 간단한 인터프리터 구현이 가능한 난해한 프로그래밍 언어로, 'Hello, world!' 출력, 소스 코드 출력, "99 Bottles of Beer" 가사 출력, 누산기 값 증가의 네 가지 명령을 제공한다. - 난해한 프로그래밍 언어 - FRACTRAN
FRACTRAN은 정수의 소인수 지수를 레지스터로 활용하여 분수 목록을 곱하는 과정을 반복하며 다양한 계산을 수행하는 계산 모델이다.
| 말레볼제 - [IT 관련 정보]에 관한 문서 | |
|---|---|
| 개요 | |
| 유형 | 난해한 프로그래밍 언어, 명령형 프로그래밍, 스칼라, 값-레벨 |
| 설계자 | 벤 올름스테드 |
| 개발자 | 벤 올름스테드 |
| 발표일 | 1998년 |
| 영향 받은 언어 | Brainfuck, INTERCAL (Tri-INTERCAL), Befunge |
| 영향을 준 언어 | Dis, Malbolge Unshackled |
| 파일 확장자 | .mal, .mb |
| 타이핑 | 타입 없음 |
| 특징 | |
| 패러다임 | 난해한 프로그래밍 언어 |
2. 역사
말레볼제는 1998년 벤 올름스테드(Ben Olmstead)가 개발한 난해한 프로그래밍 언어이다. 이름은 단테의 《신곡》 〈지옥편〉에 등장하는 여덟 번째 지옥 고리 '말레볼제'에서 따왔으며, 의도적으로 프로그래밍을 어렵고 혼란스럽게 만든 것으로 유명하다.[13]
언어 발표 초기에는 극심한 난해함으로 인해 첫 프로그램이 등장하기까지 2년이 걸렸고, 개발자 본인조차 직접 프로그램을 작성한 적이 없다고 알려져 있다.[13] 최초의 프로그램은 사람이 아닌, 앤드루 쿡(Andrew Cooke)이 리스프로 구현한 빔 탐색 알고리즘을 통해 자동으로 생성되었다.[2]
이후 여러 연구자들이 말레볼제의 난해함을 극복하려 시도했다. 2000년 앤서니 유하스(Anthony Youhas)는 몇 가지 프로그램을 공개하며 해독의 실마리를 제시했다고 주장했고,[21] 루 셰퍼(Lou Scheffer)는 말레볼제를 암호 시스템으로 분석하여 입력을 출력으로 복사하는 프로그램을 만들었다.[16][22]
올름스테드는 말레볼제가 튜링 완전하지 않고 선형 경계 오토마톤에 해당한다고 보았다.[3] 특히 실용적인 루프 구현은 매우 어려운 과제로 여겨졌으나, 언어 발표 7년 만인 2005년 이자와 히사시(飯澤 恒|이자와 히사시일본어)가 반복문 구현 방법을 제시하고 "99 병의 맥주" 프로그램을 작성하며 가능성을 입증했다.[4]
그 외에도 토마시 베그자노프스키(Tomasz Wegrzanowski)의 프로그램 생성기 개발, 나고야 대학 연구팀의 C 언어 일부 기능 컴파일 연구[23][24][25], 카밀라 세브치크(Kamila Szewczyk)의 리스프 인터프리터 개발[5][6] 등 말레볼제를 다루기 위한 다양한 도구와 연구가 진행되었다. 이러한 노력에도 불구하고 말레볼제는 여전히 가장 이해하고 사용하기 어려운 프로그래밍 언어 중 하나로 평가받는다.
2. 1. 초기 개발
말레볼제는 처음 발표되었을 때 매우 이해하기 어려웠기 때문에, 첫 말레볼제 프로그램이 만들어지기까지 2년이 걸렸다. 심지어 언어의 창시자인 벤 올름스테드(Ben Olmstead) 본인도 말레볼제 프로그램을 작성한 적이 없다.[13] 최초의 프로그램은 사람이 직접 작성한 것이 아니라, 앤드루 쿡(Andrew Cooke)이 설계하고 리스프로 구현한 빔 탐색 알고리즘을 통해 생성되었다.[2]2000년 8월 24일, 앤서니 유하스(Anthony Youhas)는 자신의 블로그를 통해 "말레볼제의 신비를 벗겨냈다"고 주장하며 여러 문장을 출력하는 세 개의 말레볼제 프로그램을 공개했다.[21] 하지만 그는 프로그램 생성 방법에 대해서는 구체적으로 설명하지 않았다.
이후 루 셰퍼(Lou Scheffer)는 말레볼제에 대한 암호 해독 분석을 발표하고, 입력을 그대로 출력으로 복사하는 간단한 프로그램을 공개했다.[16] 그는 말레볼제를 프로그래밍 언어보다는 암호 시스템으로 간주해야 하며, 몇 가지 취약점이 존재한다고 지적했다.[22] 또한, 그는 원본 인터프리터와 사양을 보존했으며, 말레볼제 프로그래밍 전략과 튜링 완전성에 대한 자신의 견해를 제시했다.[3]
올름스테드는 말레볼제가 튜링 완전하지 않다고 생각했다. 말레볼제 프로그램이 접근할 수 있는 메모리 공간의 한계 때문에 상태 모델이 유한하며, 따라서 선형 경계 오토마톤에 해당한다고 보았다. 말레볼제에서 실용적인 루프를 구현할 수 있는지에 대한 논의가 있었는데, 이는 매우 어려운 과제로 여겨졌으나 발표 후 7년 만인 2005년에 가능한 것으로 밝혀졌다. 최초의 제대로 된 루프와 조건을 포함하는 99 병의 맥주 프로그램은 이자와 히사시(Hisashi Iizawa)에 의해 작성되었다.[4]
2004년 8월 19일, 토마시 베그자노프스키(Tomasz Wegrzanowski)는 임의의 문자열을 출력하는 말레볼제 프로그램을 생성하는 생성기를 만들었다. 이 생성기는 특정 연산(NOP, ROT, Crazy)을 반복하여 원하는 값을 만들어내는 방식으로 작동하며, 이 방식으로 생성된 프로그램은 앤서니 유하스의 프로그램보다 크기가 훨씬 컸다.
2005년, 飯澤 恒|이자와 히사시일본어는 〈難読プログラミング言語Malbolgeにおけるプログラム構成手法|난도쿠 프로그래밍구 겐고 마루보루제 니 오케루 프로구라무 코세이 슈호일본어〉[4]이라는 논문을 통해 말레볼제에서 반복문을 구현하는 구체적인 방법을 제시했다. 그는 Crazy 연산의 조합으로 덧셈과 같은 기본적인 연산을 구현하고, 메모리 접근을 통해 원하는 값을 얻는 방식을 사용했다. 이후 이자와 등은 말레볼제를 소프트웨어 보호를 위한 난독화 목적으로 활용하는 방안을 연구하기도 했다.[14]
나고야 대학의 酒井 政彦|사카이 마사히코일본어 등은 말레볼제의 프로그램 난독화 가능성에 주목하여, 3단계의 중간 언어와 SAT 솔버를 이용해 말레볼제 프로그램을 생성하는 기법을 제안했다.[23][24] 이 연구를 통해 while 문, 배열, 재귀 함수 등을 포함하는 C 언어의 일부 기능을 말레볼제 프로그램으로 컴파일하는 것이 가능해졌다.[25]
2020년에는 카밀라 세브치크(Kamila Szewczyk)가 말레볼제 언섕클드(Malbolge Unshackled)라는 변형된 말레볼제로 작성된 리스프 인터프리터를 발표하며 언어의 가능성을 더욱 확장했다.[5][6]
2. 2. 난해성 극복
말레볼제는 처음 발표되었을 때 이해하기 매우 어려웠기 때문에, 첫 말레볼제 프로그램이 만들어지기까지 2년이 걸렸다. 심지어 언어 개발자인 벤 올름스테드 본인도 말레볼제 프로그램을 작성한 적이 없다.[13] 최초의 프로그램은 사람이 직접 작성한 것이 아니라, 앤드루 쿡(Andrew Cooke)이 설계하고 리스프로 구현한 빔 탐색 알고리즘을 통해 생성되었다.[2]2000년 8월 24일, Anthony Youhas는 [https://web.archive.org/web/20071013071419/http://www.antwon.com/index.php?p=234 자신의 블로그]에 "말레볼제의 신비를 벗겨냈다"고 선언하며, 여러 문장을 출력하는 세 개의 말레볼제 프로그램을 증거로 제시하였다.[21] 하지만 그는 프로그램을 만드는 구체적인 방법에 대해서는 언급하지 않았다.
이후 Lou Scheffer는 말레볼제에 대한 암호 해독 분석을 발표하고, 입력을 그대로 출력으로 복사하는 프로그램을 공개했다.[16] 그는 말레볼제를 프로그래밍 언어보다는 암호 시스템으로 간주해야 하며, 몇 가지 취약점이 존재한다고 지적했다.[22] 또한, 그는 말레볼제 프로그램을 작성하는 일반적인 전략과 튜링 완전성에 대한 자신의 생각을 제시하기도 했다.[3]
올름스테드는 말레볼제가 튜링 완전하다고 생각했으나[3], 프로그램이 접근할 수 있는 메모리 공간의 한계 때문에 실제로는 선형 경계 오토마톤에 해당하며 튜링 완전하지 않다는 분석이 있다. 말레볼제에서 의미 있는 루프를 구현할 수 있는지에 대한 논의가 있었는데, 최초의 비종료 루프가 등장하기까지 여러 해가 걸렸으며, 실용적인 루프 구현은 7년 만에 가능한 것으로 밝혀졌다. 복잡한 루프와 조건을 처리하는 99 병의 맥주 프로그램은 2005년 이자와 히사시(飯澤 恒|이자와 히사시일본어)에 의해 작성되었다.[4]
2004년 8월 19일, Tomasz Wegrzanowski는 임의의 문자열을 출력하는 말레볼제 프로그램 생성기를 만들었다. 이 생성기는 특정 연산(NOP, ROT, Crazy)을 반복하여 원하는 값을 만들어내는 방식을 사용하며, 이렇게 만들어진 프로그램은 Anthony Youhas의 프로그램보다 크기가 훨씬 크다.
2005년, 이자와 히사시는 〈난해한 프로그래밍 언어 말레볼제의 프로그래밍 방법(難読プログラミング言語Malbolgeにおけるプログラム構成手法|난도쿠 프로그래밍 겐고 마루보루제 니 오케루 프로그라무 고세이 슈호일본어)〉이라는 논문을 통해 말레볼제에서 반복문을 구현하는 방법을 제시했으며, 그 예제로 "99 병의 맥주" 프로그램을 만들었다.[http://www.sakabe.i.is.nagoya-u.ac.jp/~nishida/DB/pdf/iizawa05ss2005-22.pdf] 그는 Crazy 연산의 조합으로 덧셈 등의 연산을 구현하고, 일정한 횟수만큼 메모리를 접근하여 원하는 값을 만들어 내는 방법을 사용했다. 이자와 등은 소프트웨어 보호를 위한 코드 난독화 목적으로 말레볼제 프로그래밍 가이드를 제안하기도 했다.[14][23][24]
말레볼제의 코드 난독화 응용 가능성에 주목한 나고야 대학의 사카이 마사히코(坂井 正彦) 등은 3단계의 중간 언어와 SAT 솔버를 이용하여 말레볼제 프로그램을 생성하는 기법을 제안했다.[23][24] 이 연구를 통해 while 문, 배열, 재귀 함수 등을 포함하는 C 언어의 일부 기능을 말레볼제 프로그램으로 컴파일하는 것이 가능해졌다.[25]
2020년, 카밀라 세브치크(Kamila Szewczyk)는 말레볼제 언섕클드(Malbolge Unshackled)로 작성된 리스프 인터프리터를 발표했다.[5][6]
2. 3. 튜링 완전성 논쟁과 발전
말레볼제가 처음 발표되었을 때 이해하기 매우 어려웠기 때문에, 첫 말레볼제 프로그램이 만들어지기까지 2년이 걸렸다. 심지어 언어의 창시자인 벤 올름스테드(Ben Olmstead) 본인도 말레볼제 프로그램을 작성한 적이 없다.[13] 최초의 프로그램은 사람이 직접 작성한 것이 아니라, 앤드루 쿡(Andrew Cooke)이 리스프로 구현한 빔 서치 알고리즘을 통해 생성되었다.[2]2000년 8월 24일, Anthony Youhas는 자신의 블로그에서 말레볼제를 격파하고 해결의 열쇠를 찾았다고 주장하며, 여러 문장을 출력하는 세 개의 말레볼제 프로그램을 증거로 제시했다.[21] 하지만 그는 프로그램을 만드는 구체적인 방법에 대해서는 밝히지 않았다.
이후 루 셰퍼(Lou Scheffer)는 말레볼제를 프로그래밍 언어라기보다는 암호 시스템으로 간주해야 하며, 몇 가지 취약점이 존재한다고 지적했다.[22] 그는 말레볼제에 대한 암호 해독 분석을 게시하고, 이러한 취약점을 이용해 입력된 문자를 그대로 출력하는 프로그램을 공개했다.[16] 또한, 그는 원래 사이트가 사라진 후에도 인터프리터와 사양을 보존했으며, 말레볼제 프로그램 작성 전략과 튜링 완전성에 대한 자신의 견해를 제시했다.[3]
올름스테드는 말레볼제가 튜링 완전하다고 생각했으나, 프로그램이 접근할 수 있는 메모리 공간의 한계 때문에 실제로는 유한 상태 모델이며 따라서 튜링 기계의 정의에 따른 완전성은 가지지 않는다고 보았다. 그는 말레볼제를 선형 경계 오토마톤으로 간주했다. 말레볼제에서 의미 있는 루프를 구현할 수 있는지에 대한 논의가 있었는데, 이는 난제로 여겨졌으나 결국 7년 만에 가능한 것으로 밝혀졌다.[4] 최초의 비종료 루프가 등장하기까지는 여러 해가 걸렸다.
2004년 8월 19일, Tomasz Wegrzanowski는 임의의 문자열을 출력하는 말레볼제 프로그램을 생성하는 생성기를 만들었다. 이 생성기는 특정 연산을 반복하여 원하는 값을 만들어내는 방식으로 작동하며, 이 방식으로 만들어진 프로그램은 Anthony Youhas의 프로그램보다 크기가 훨씬 컸다.
2005년, 이자와 히사시(飯澤 恒|이자와 히사시일본어)는 〈難読プログラミング言語Malbolgeにおけるプログラム構成手法|난해한 프로그래밍 언어 말레볼제에서의 프로그래밍 기법일본어〉이라는 논문을 통해 말레볼제에서 반복문을 구현하는 방법을 제시했다. 그는 이 방법의 예시로 복잡한 루프와 조건 처리가 필요한 "99 병의 맥주" 프로그램을 성공적으로 작성했다.[4] 이는 말레볼제가 발표된 지 7년 만에 등장한 제대로 된 프로그램으로 평가받는다. 그는 Crazy 연산의 조합으로 덧셈과 같은 기본적인 연산을 구현하고, 메모리 접근을 통해 원하는 값을 만들어내는 기법을 사용했다. 이자와 등은 이후 말레볼제를 소프트웨어 보호를 위한 코드 난독화 목적으로 활용하는 방안을 제안하기도 했다.[14]
나고야 대학의 사카이 마사히코 등은 말레볼제의 코드 난독화 응용 가능성에 주목하여, 3단계 중간 언어와 SAT 솔버를 이용해 말레볼제 프로그램을 생성하는 기법을 제안했다.[23][24] 이 연구를 통해 while 문, 배열, 재귀 함수 등을 포함하는 C 언어의 일부 기능을 말레볼제 프로그램으로 컴파일하는 것이 가능해졌다.[25]
2020년에는 카밀라 세브치크(Kamila Szewczyk)가 말레볼제 언섕클드(Malbolge Unshackled)라는 변형 언어로 작성된 리스프 인터프리터를 발표하며 말레볼제 연구의 새로운 가능성을 열었다.[5][6]
3. 구성
말레볼제는 삼진법 가상 머신, 즉 말레볼제 인터프리터를 위한 기계어이다.[9] 이 언어는 특유의 복잡성과 난해함으로 잘 알려져 있다.
표준 인터프리터와 공식 사양 사이에는 약간의 차이가 존재한다.[9] 예를 들어, 표준 컴파일러는 ASCII 코드 33부터 126까지의 범위를 벗어나는 데이터가 입력될 경우 실행을 중단하도록 설계되었다. 이는 초기에 버그로 간주되었으나, 개발자 벤 올름스테드(Ben Olmstead)는 이를 의도된 사양이며, 오히려 기존 공식 사양에 오류가 있었다고 밝혔다.[13] 말레볼제의 구체적인 작동 방식은 레지스터, 메모리 구조, 명령어 세트 등을 통해 정의된다.
3. 1. 레지스터
말레볼제에는 다른 프로그래밍 언어의 변수와 유사한 역할을 하는 세 개의 레지스터, 즉 '''''a''''', '''''c''''', '''''d'''''가 있다. 프로그램이 실행될 때 이 세 레지스터의 값은 모두 0으로 초기화된다.- '''''a''''' 레지스터는 '누산기'(Accumulator) 역할을 한다. 메모리에 값을 쓰는 연산의 결과가 이 레지스터에 저장되며, 입출력 작업에도 사용된다.
- '''''c''''' 레지스터는 '코드 포인터'(Code Pointer)로, 현재 실행해야 할 명령어가 있는 메모리 위치를 가리키는 특별한 프로그램 카운터이다.[10][27]
- '''''d''''' 레지스터는 '데이터 포인터'(Data Pointer)이다. 데이터 조작 명령어가 사용할 메모리 주소를 가리키며, 명령어가 하나 실행될 때마다 자동으로 값이 1씩 증가한다.
코드 설명 등에서 '''''[d]'''''라는 표기는 '''''d''''' 레지스터가 저장하고 있는 메모리 주소에 실제로 들어있는 값을 의미한다. 이는 레지스터 간접 주소 지정 방식과 유사하다. '''''[c]'''''도 같은 방식으로 이해할 수 있다.
3. 2. 메모리
가상 머신은 59,049 (310) 개의 메모리 공간을 가지며, 각각 10자리의 삼진수를 저장할 수 있다. 각 메모리 공간에는 0부터 59048까지의 메모리 주소가 할당되며, 0부터 59048까지의 값을 가질 수 있다. 이 상한을 초과하여 증가시키면 0으로 돌아간다.이 언어는 데이터와 명령어를 위해 동일한 메모리 공간을 사용한다. 이는 x86 아키텍처와 같은 하드웨어의 작동 방식에 영향을 받았다.[29][13]
말레볼제 프로그램이 시작되기 전에, 메모리의 첫 번째 부분은 프로그램으로 채워진다. 프로그램에 포함된 모든 공백 문자는 무시되며, 프로그래밍을 더 어렵게 만들기 위해 프로그램의 나머지 부분은 아래에 설명된 명령어 중 하나로 시작해야 한다.
메모리의 나머지 공간은 이전 두 메모리 주소에 대한 ''crazy'' 연산(아래 참조)을 사용하여 채워진다 ('''[m] = crz [m - 2], [m - 1]'''). 이 방식으로 채워진 메모리는 12개의 주소마다 값이 반복되는 패턴을 보인다.
공식 사양은 ''crazy'' 연산을 사용하여 두 번째 메모리 위치를 채우려고 할 때 '''[m - 2]'''가 프로그램 메모리 영역 외부를 가리키는 1-명령어 프로그램의 예외적인 경우를 다루지 않는다. 참조 구현 역시 이 경우를 명시적으로 고려하지 않아 정의되지 않은 동작이 발생할 수 있다.[11]
2007년, Ørjan Johansen은 임의의 메모리 제한이 없는 Malbolge Unshackled 버전을 만들었다. 이는 Malbolge의 기본 정신을 최대한 유지하면서 튜링 완전한 언어를 만들려는 시도였다. 다른 규칙은 변경되지 않았으며, 메모리 제한에 도달하지 않는 모든 기존 Malbolge 프로그램은 이 버전에서도 완전히 작동한다.[28][12]
3. 3. 포인터 표기법
말레볼제에는 다른 언어들의 변수와 유사한 역할을 하는 세 개의 레지스터, 즉 '''''a''''', '''''c''''', '''''d'''''가 있다. 프로그램이 시작될 때 이 세 레지스터의 값은 모두 0이다.- '''''a'''''는 어큐뮬레이터(Accumulator)의 약자로, 메모리 쓰기 명령이나 표준 입출력에 사용된다.
- '''''c'''''는 코드(Code) 포인터로, 현재 실행 중인 명령을 가리키는 프로그램 카운터 역할을 한다.[27]
- '''''d'''''는 데이터(Data) 포인터이다. 이 레지스터는 각 명령이 실행된 후 자동으로 증가하며, 가리키는 메모리 주소는 데이터 조작 명령에 사용된다.
포인터 표기법에서 '''''[d]'''''는 '''''d''''' 레지스터에 저장된 값을 메모리 주소로 사용하여, 해당 주소에 저장된 실제 값을 의미한다. 이는 레지스터 간접 주소 지정 방식이다. '''''[c]''''' 역시 동일한 방식으로 '''''c''''' 레지스터가 가리키는 주소의 값을 나타낸다.
3. 4. 명령어
mov a, [d]mov a, [d]