Quine: 자기 자신의 소스코드를 출력하는 프로그램
우리가 주로 프로그래밍을 하는 목적은 문제를 효율적으로 풀거나, 특정 작업을 편리하게 처리하기 위해서일 것입니다.
그러나 어디서나 재미를 추구하는 것은 사람의 본능이기에, 오직 호기심과 흥미만을 목적으로 전혀 실용적이지 않은 코드를 짜는 경우도 꽤나 있습니다. 얼마나 창의적이게 이상한 C언어 코드를 작성했는지 겨루는 IOCCC라는 대회가 존재할 정도입니다.
이 글에서는, 쓸모는 없지만 신기한 프로그램의 대표적 예시인 ‘콰인(Quine)‘과 그 이론적 배경에 대해 알아보도록 하겠습니다.
콰인이란?
콰인(Quine) 은 실행했을 때 자기 자신의 소스 코드를 출력하는 프로그램을 이르는 말로, 미국의 철학자이자 논리학자인 윌러드 밴 오먼 콰인(Willard Van Orman Quine)의 이름을 딴 것입니다.
이 때, 콰인은 어떤 종류의 입력도 받지 않는 프로그램이어야 합니다. 입력을 허용하면, 단순히 소스 코드를 사용자에게 입력받거나 디렉토리 내의 소스 코드 파일을 찾아서 출력하는 등의 편법이 가능하기 때문입니다.
보다시피 콰인의 의미 자체는 이해하기 쉽고 명료해서, 왜 콰인이 특별한지 감이 잘 안 오실 수도 있습니다.
하지만, 직접 콰인을 짜려고 해보면 생각보다 까다롭다는 것을 알 수 있습니다. 특히 무턱대고 출력문을 사용하려다 보면, 아래와 같이 무한히 반복되는 소스코드를 만나게 될 것입니다.
#include <stdio.h>
int main() { printf("#include <stdio.h>\nint main() { printf( ... // 이 자리에 뭐가 들어가야 할까요?
과연 유한한 길이로 콰인을 만들 수 있을까요? 어떤 아이디어가 콰인을 만드는 데 있어서 핵심적인 걸까요?
충분히 생각해 보셨다면, 아래 예시와 비교해 보실 수 있습니다.
예시
아래는 C언어로 작성한 콰인의 한 예시입니다.
#include <stdio.h>
char S[] = "#include <stdio.h>%cchar S[] = %c%s%c;%cint main() { printf(S, 10, 34, S, 34, 10); return 0; }";
int main() { printf(S, 10, 34, S, 34, 10); return 0; }
이를 실제로 컴파일해서 실행해보면,
#include <stdio.h>
char S[] = "#include <stdio.h>%cchar S[] = %c%s%c;%cint main() { printf(S, 10, 34, S, 34, 10); return 0; }";
int main() { printf(S, 10, 34, S, 34, 10); return 0; }
위와 같은 출력이 나오고, 이는 소스 코드와 완전히 동일함을 알 수 있습니다. 물론 직접 확인해 보셔도 좋습니다. 신기하지 않나요?
위 예시를 보면, 콰인을 만드는 데에 C언어의 문자열 형식 지정자가 중요하게 작용했음을 알 수 있습니다. 당연하게도, 위의 구현은 C언어 문법에 한정됩니다.
사실, 콰인은 특정 프로그래밍 언어에 국한된 개념이 아니기 때문에, 이 예시만으로 콰인에 대해 일반적으로 논하기에는 한계가 있습니다.
더 일반적인 논의
이제 우리는 좀 더 넓은 범위의 질문을 할 수 있습니다. 모든 프로그래밍 언어에 콰인이 존재할까요? 특정 언어에 대한 콰인의 존재성은 어떻게 알 수 있을까요?
신기하게도, 문자열 처리가 가능한 모든 튜링 완전한 프로그래밍 언어는 콰인을 가진다고 밝혀져 있습니다. 놀랍지 않나요? 어떻게 증명이 가능했을까요?
본격적으로 설명하기에 앞서, 지금까지 추상적으로 사용하던 용어를 수학적으로 엄밀히 정하고 넘어갈 필요가 있습니다.
- 프로그래밍 언어 $\psi$ - 소스 코드와 그에 해당하는 프로그램의 함수 관계처럼 생각할 수 있습니다. 즉, 소스 코드 $x$에 해당하는 프로그램을 $\psi_x$처럼 표현할 수 있습니다.
그렇다면 소스 코드는 무엇이고 프로그램은 무엇일까요?
-
소스 코드 $x$ - 자명하게도, 문자열입니다. 그러나 모든 문자열이 소스 코드인 것은 아닙니다. $x$에 해당하는 프로그램 $\psi_x$가 존재해야, 즉 컴파일이 가능해야 $x$가 소스 코드이며, 이러한 소스 코드의 집합을 $S$라고 합시다.
-
프로그램 $f$ - 입력 문자열 $x$를 받아 유한한 시간 안에 문자열 $f(x)$를 출력하는 함수처럼 생각할 수 있습니다. 즉, 문자열 전체의 집합을 $\Sigma$라고 할 때 프로그램은 $f: \Sigma \to \Sigma$인 계산 가능한 부분 함수로 표현할 수 있습니다.
여기서, 계산 가능한 함수라는 개념에 대해서는, 말 그대로 ‘계산이 가능한 함수다’라는 정도로만 알아두셔도 밑의 내용을 이해하는 데 문제가 없습니다. 또한, 부분 함수라는 것은 함숫값이 정의역의 특정 원소에 대해 정의되지 않을 수도 있음을 의미합니다. 예를 들어, 어떤 정수 $m$에 해당하는 문자열을 입력받아 그 역수를 출력하는 프로그램은 “0”을 입력했을 때 출력이 정의되지 않는데, 이러한 경우를 고려한 것입니다.
또한, 튜링 완전한 프로그래밍 언어라는 개념이 등장했는데, 이는 프로그래밍 언어의 소스 코드가 모든 계산 가능한 부분 함수를 표현할 수 있음을 의미합니다. C언어와 같은 절차적 프로그래밍 언어가 튜링 완전한 언어의 한 예시입니다.
이에 대해서는, $\psi$가 튜링 완전하다면 어떠한 프로그램 $f:\Sigma \to \Sigma$에 대해서도 $\psi_x$와 $f$를 같게 하는 $x$, 즉, 프로그램 $f$의 소스 코드 $x$가 존재한다는 성질만 알아두어도 밑의 내용을 이해하실 수 있습니다.
위에서 대충 넘어간 개념들에 대해 더 정확히 알고 싶으실 경우 Computable function과 Turing completeness 문서를 참조하시면 되겠습니다.
한편, 위와 같은 표기법을 사용했을 때 아래와 같은 정리가 성립합니다.
로저스의 고정점 정리
- $\psi$가 튜링 완전한 프로그래밍 언어이며 $S \subset \Sigma$가 이 언어의 모든 소스 코드의 집합일 때, 임의의 계산 가능한 함수 $F:S \to S$에 대해서, 두 프로그램 $\psi_e$ 와 $\psi_{F(e)}$ 가 동일한 프로그램이 되게 하는 소스 코드 $ e \in S $ 가 존재한다.
즉, 소스 코드 $e$를 컴파일해서 만든 프로그램과 소스 코드 $F(e)$를 컴파일해서 만든 프로그램이 완벽히 동일한 소스 코드 $e$가 존재한다는 것입니다.
여기서 프로그램 $f$와 $g$가 동일하다는 것은, 모든 문자열 $x$에 대해 $f(x)$와 $g(x)$가 둘 다 정의되지 않거나 $f(x)$와 $g(x)$의 값이 같음를 의미합니다.
이 정리의 증명은 아래와 같습니다.
증명
$\psi$는 튜링 완전한 프로그래밍 언어이며 $S$가 이 언어의 모든 소스 코드의 집합이고, 임의의 계산 가능한 함수 $F:S \to S$가 주어졌다고 합시다.
다음과 같이 함수 $h:S \to S$를 정의합시다.
- $h(x)$ : 입력 문자열 $y$에 대해 $\psi_{\psi_x (x)} (y) $가 존재하면 그 값을 출력하고, 존재하지 않으면 출력값이 정의되지 않는 프로그램의 소스 코드
각각의 함수값 $h(x)$는 단순히 위의 설명을 소스 코드로 옮긴 것에 불과하므로, 함수 $h$는 자명하게 계산 가능한 함수입니다.
또한, 프로그램 $\psi_{\psi_x (x)}$가 존재하는 경우 $\psi_{h(x)}$는 $\psi_{\psi_x (x)}$와 같은 프로그램입니다.
한편, $F:S \to S$와 $h:S \to S$ 모두 계산 가능한 함수이므로, $F \circ h:S \to S$ 역시 계산 가능한 함수입니다.
- $S$가 $\Sigma$의 부분집합이므로 $F \circ h$는 $\Sigma \to \Sigma$인 계산 가능한 부분 함수이기도 하며
- $\psi$는 튜링 완전하므로 $\Sigma \to \Sigma$인 모든 계산 가능한 부분 함수를 표현할 수 있습니다.
따라서, 함수 $\psi_x $와 함수 $F \circ h$가 같도록 하는 소스 코드 $x \in S$가 존재합니다.
그러한 소스 코드를 $e$라고 합시다. 그러면, 함수 $\psi_e$와 함수 $F \circ h$는 같으며, 그에 따라 문자열 $\psi_e (e)$과 문자열 $F(h(e))$은 같습니다.
함수 $F$의 치역이 $S$이므로, 프로그램 $\psi_{F(h(e))}$은 존재하며 $\psi_{\psi_e (e)}$와 같은 프로그램입니다.
또한, $\psi_{\psi_e (e)}$가 존재하므로 위의 결과에서 $\psi_{\psi_e (e)}$와 $\psi_{h(e)}$은 같은 프로그램임을 얻습니다.
따라서, $e’ = h(e) \in S$라고 했을 때 프로그램 $\psi_{e’}$와 프로그램 $\psi_{F(e’)}$은 같습니다.
그러므로, 임의의 계산 가능한 함수 $F:S \to S$에 대해서, 프로그램 $\psi_e$와 프로그램 $\psi_{F(e)}$가 같은 $ e \in S $ 가 존재합니다.
콰인에의 활용
이 정리를 통해 문자열 처리가 가능한 모든 튜링 완전한 프로그래밍 언어는 콰인을 가진다는 것을 유도해낼 수 있습니다.
다음과 같이 함수 $F:S \to S$를 정의합시다.
- $F(x)$ : 입력을 받지 않고 $x$를 그대로 출력하는 프로그램의 소스 코드
고정점 정리에 의해, 프로그램 $\psi_e$와 $\psi_{F(e)}$가 동일한 작동을 하는 소스 코드 $e \in S$가 존재합니다.
그러면, $\psi_{F(e)}$는 함수 $F$의 정의에 의해 $e$를 그대로 출력하는 프로그램이 됩니다.
또한, $\psi_e$의 작동과 $\psi_{F(e)}$의 작동은 동일하므로, $\psi_e$ 역시 $e$를 출력하는 프로그램입니다.
즉, 소스 코드 $e$를 컴파일한 결과는 입력을 받지 않고 $e$를 출력하는 프로그램입니다. 따라서 프로그램 $\psi_e$는 콰인입니다.
마치며
위의 증명 과정을 그대로 따라한다면, 이론적으로 거의 모든 언어에서 콰인을 만들어낼 수 있습니다. 하지만 함수 $h$의 설명에서 보듯이, $h(x)$의 소스 코드는 $x$를 컴파일한 것에 해당하는 프로그램에 입력으로 $x$를 넣은 결과를 시뮬레이션할 수 있어야 합니다.
즉, 함수 $h$를 실제 구현하는 데에는 자기 자신의 언어로 작성한 자기 자신의 인터프리터가 필요합니다. Python으로 작성한 Python 인터프리터 PyPy처럼 말이죠. 이는 결코 쉬운 일이 아닐 것입니다.
인터프리터를 구현하는 대신, 사람들은 각 프로그래밍 언어에서 짧고 간결한 콰인들을 찾아냈습니다. 그 목록은 이 링크에서 확인할 수 있으니 관심이 있다면 둘러보는 것도 좋을 것입니다.
마지막으로, 이 글에서는 읽는 사람의 이해를 돕기 위해 생략하거나 바꿔 쓴 부분이 꽤 있습니다. 원본 증명이 궁금하시다면 아래 참고 문헌 링크를 참조해 주시면 감사하겠습니다.