퀸(Quine)에 대한 개념, 작성 원리, 예시, 고정점 정리, 멀티퀸, 부트스트래핑(자체회복성) 등 자기출력 프로그램의 이론과 실전 예시를 다루는 글.
"퀸(Quine)" 혹은 "selfrep"은 자신의 소스코드를 출력하는 컴퓨터 프로그램을 일컫습니다. 이 개념이 불가능하다고 느껴질 수도, 시시하거나 무의미하다고 생각될 수도 있지만, 사실 이는 수학적으로 상당히 흥미로운 아이디어와 고정점 정리 (Cantor의 대각선 논법의 한 사례)에서 비롯됩니다.
이 용어는 미국의 수학자이자 논리학자 윌러드 반 오만 퀸(Willard van Orman Quine)을 기려 명명되었고, 더글러스 호프스태터는 그의 저서 "괴델, 에셔, 바흐"에서 이 이름을 퍼뜨리고 퀸의 중요성과 괴델 불완전성 정리와의 연결을 쉽고 명확하게 설명했습니다.
이 페이지는 두 학자 모두에게 헌정합니다.
퀸은 자신의 전체 소스코드를 출력하는 프로그램입니다. 즉, 실행 시 프로그래머가 작성한 모든 코드를 (출력 코드와 출력에 쓰이는 데이터까지) 정확히 다시 출력해야 합니다.
가장 쉬운 방법은 소스 파일을 디스크에서 읽어 그대로 출력하는 것이지만, 보통 이를 금기로 간주합니다. 또한 프로그램이 소스 위치를 모를 수도 있고, 소스 접근이 불가할 수도 있기 때문이죠.
흥미로운 점은 퀸을 작성하는 데 특수한 트릭(예: 소스 파일 읽기)이 전혀 필요 없다는 것입니다. 모든 튜링 완전 언어(모든 문자열을 출력 함수에 넣을 수 있는 언어 – 실질적으로 모든 언어)는 고정점 정리 덕분에 퀸, 심지어 무한히 많은 변형 퀸을 가질 수 있습니다. 고정점 정리는 구성적(constructive)이므로 퀸을 만드는 과정엔 인내만 필요하며, 되어가는 과정을 이해하면 전혀 어려울 게 없습니다.
물론 짧고 아름다운, 혹은 특이한 퀸을 만드는 데는 지적 기지가 필요하지만, 퀸의 존재 자체에 뭔가 신비로운 마법 같은 것은 없습니다. 또, 퀸은 전혀 난독화될 필요가 없으며, 주석도 얼마든지 넣을 수 있습니다.
C 언어로 퀸을 만들어 봅시다. C는 널리 알려져 있고, printf() 덕에 퀸 작성이 조금 수월합니다.
먼저, C 프로그램의 기본 뼈대는 아래와 같겠죠:
#include <stdio.h>
int
main (void)
{이제 지금까지 코드를 출력해야 합니다. 단순히 printf("#include <stdio.h>\n\nint\nmain (void)\n{\n");로 할 수 있겠지요. 다시, 그 출력 명령문 자체도 출력해야 할 테니, 연속으로 printf()를 써야 하고…. 이 방식은 곧 무한 반복에 빠지게 되어 실패합니다.
사람들이 퀸이 불가능하다고 생각하는 바로 그 이유이기도 하죠. s라는 문자열을 출력하고, 또 s 자체를 출력하기 위해 또 다른 문자열을 만들고 – 반복의 늪입니다.
하지만, s를 출력할 때 반드시 새로운 문자열이 필요한 게 아님을 눈치채야 합니다. 이를 이용해 시도해보면:
char *s="#include <stdio.h>\n\nint\nmain (void)\n{\n";
printf(s); printf("char *s=\"%s\";\n",s);아직 안 됩니다만, 퀸 작법의 중심 사상을 도입했습니다. 즉, 출력을 위한 데이터(여기서는 s)가 필요하지만, 이 데이터를 자기 자신을 출력하는 데 재활용할 수 있다는 점입니다. 현재는 s의 이스케이프 부호()가 문제로, 이를 적절히 처리(백슬래시 이스케이프)해야 하는데요. 하지만 printf 포맷팅의 편리함을 활용하면 다음과 같이 단축할 수 있습니다:
char *s1="#include <stdio.h>%c%cint%cmain (void)%c{%c";
char *s2=" char *s1=%c%s%c;%c char *s2=%c%s%c;%c";
char n='\n', q='"';
printf(s1,n,n,n,n,n);
printf(s2,q,s1,q,n,q,s2,q,n);이제 이 코드는 자신의 일부 출력을 포함하는 퀸의 부분 형태가 되었습니다. 데이터(s)가 자기 자신에 대한 표현을 포함시켰다는 "catching up point"를 지났다 볼 수 있죠. 실제로 전체 퀸 완성은 비교적 간단하며, 아래와 같이 완성 가능합니다(좀 복잡해 보이지만, 더 명확한 예시는 아래 두 번째 예시에서 제시하겠습니다).
(이하 코드 생략: 원문 참조)
여기서 중요한 점은 'intron'(여기서는 sx 문자열)이라는 불필요 데이터가 있을 수 있지만, 퀸의 구조에는 필요 없는 데이터도 포함될 수 있다는 점입니다. 또한 printf 포매팅 덕에 아스키 코드에 의존하지 않고, 포맷도 적절하게 맞췄습니다.
핵심 개념은 다음과 같습니다:
대부분의 프로그래밍 언어에서는 프로그램이 자기 자신(즉, 소스 형태) 전체를 직접 다루는 것이 불가능하다.
그러므로, 프로그램을 두 부분으로 나눈다: 하나는 _코드_이고, 하나는 _데이터_이다. 데이터 부분은 코드의 (텍스트) 형태를 알고리즘적으로 변형한 값(보통은 쌍따옴표로 감싸거나 기타 변환)이다. 코드 부분은 데이터를 이용해 코드를 출력하고, 다시 데이터를 출력한다.
이 원리가 요약된 문장이 바로 “quine ‘quine’”입니다. 여기서 to quine이라는 동사는 “어떤 문구를 한 번 쓰고 따옴표까지 써서 다시 한 번 쓴다”라는 뜻입니다.
이때 데이터는 DNA에, 코드는 세포에 비유할 수도 있습니다. DNA 자체는 복제 정보를 담고 있지만, 세포(코드)가 없이는 아무 소용이 없습니다.
이 데이터 안에는 프로그램의 복사에는 필요하지 않지만, 프로그램이 출력할 때는 포함되어 같이 복제되는 부분이 있을 수 있습니다(