자기 자신을 출력하는 프로그램
'퀸(Quine)'이라는 말 들어보셨나요? 실행하면 자기 자신의 소스 코드를 그대로 출력하는 프로그램을 말해요. 파일을 읽어서 출력하는 반칙 없이, 순수하게 코드만으로요. 이름은 자기 참조를 연구한 철학자 윌러드 밴 오먼 콰인(W. V. O. Quine)에서 따왔어요.
처음 들으면 이상하잖아요. 자기 소스를 출력하려면 소스 안에 자기 소스가 들어 있어야 하고, 그 안에 또 들어 있어야 하고... 무한히 반복될 것 같거든요. 그런데 놀랍게도 튜링 완전한 언어라면 어떤 언어든 퀸이 반드시 존재한다는 게 수학적으로 증명돼 있어요. 그 증명이 바로 클레이니의 제2 재귀 정리(Kleene's Second Recursion Theorem)예요.
이번에 소개할 글은 이 정리의 증명을 한 단계씩 따라가면서, 증명 과정 자체를 '퀸 만드는 레시피'로 바꿔 실제 퀸을 조립해보는 내용이에요. 추상적인 계산 이론이 구체적인 코드로 바뀌는 순간을 보여주는 글이라 꼭 소개하고 싶었어요.
먼저 파이썬 퀸 하나 보고 가요
설명 전에 실물부터 보면 이해가 쉬워요. 파이썬에서 유명한 한 줄 퀸이에요.
~~~python
s='s=%r;print(s%%s)';print(s%s)
~~~
실행하면 정확히 이 한 줄이 그대로 출력돼요. 원리는 이래요. 문자열 s는 프로그램의 '틀(템플릿)'이고, 중간에 %r이라는 빈칸이 뚫려 있어요. s%s는 그 빈칸에 틀 자기 자신을 따옴표까지 붙여서 끼워 넣어요. 그러면 '틀'과 '틀을 담은 문자열'이 합쳐져서 원래 프로그램 전체가 되는 거죠.
핵심은 “자기 자신을 자기 자신에게 적용한다”는 아이디어예요. 무한히 자기를 품는 대신, 빈칸 있는 설계도 하나를 두고 그 설계도를 자기 빈칸에 넣는 거예요. 이 트릭을 '대각화(diagonalization)'라고 부르는데, 칸토어의 대각선 논법, 괴델의 불완전성 정리, 튜링의 정지 문제 증명에도 똑같이 등장하는 단골 기술이에요.
클레이니의 제2 재귀 정리, 쉽게 풀기
모든 프로그램에 번호(또는 소스 코드)가 붙어 있다고 해볼게요. 정리의 내용은 프로그램을 다른 프로그램으로 바꾸는 어떤 계산 가능한 변환 f가 주어져도, f를 적용해도 동작이 변하지 않는 프로그램 e가 반드시 존재한다는 거예요. 수식으로는 φ_e = φ_{f(e)}인 e가 있다는 거죠. 그래서 '고정점 정리'라고도 불러요.
더 직관적인 버전도 있어요. “프로그램은 언제든 자기 소스 코드를 꺼내 쓸 수 있다고 가정하고 짜도 된다.” 즉 my_source()라는 마법 함수가 있다고 치고 프로그램을 설계하면, 그 마법 없이도 똑같이 동작하는 진짜 프로그램이 반드시 존재한다는 보장이에요.
증명의 뼈대는 이렇게 흘러가요. 먼저 s-m-n 정리(매개변수화 정리)라는 도구를 써요. 이게 뭐냐면, 인자 두 개를 받는 프로그램에 첫 번째 인자를 미리 박아 넣은 새 프로그램을 자동으로 만들어주는 기계예요. 프로그래밍으로 치면 커링(currying)이나 부분 적용(partial application)이죠. 이걸로 “프로그램 x를 받아서, x를 x 자신에게 실행한 결과가 가리키는 프로그램처럼 동작하는 프로그램”을 만드는 변환 h를 정의해요. 앞의 파이썬 예시에서 s%s에 해당하는 부분이에요. 그다음 f와 h를 합성한 프로그램의 번호를 v라 하고 e = h(v)로 두면, 계산이 딱 맞아떨어지면서 고정점이 완성돼요.
이제 퀸을 만들려면 f를 “프로그램 x를 받아서, 무엇을 입력받든 x의 소스를 출력하는 프로그램으로 바꾸는 변환”으로 고르면 돼요. 정리에 의해 고정점 e가 존재하고, e는 'e의 소스를 출력하는 프로그램'과 똑같이 동작하니까 바로 퀸이 되는 거죠. 원문은 이 추상적인 단계들을 실제 코드 조각으로 하나하나 구현하면서 보여줘요.
업계 맥락: 이론 속 장난감이 아니에요
퀸이 그저 퍼즐 같지만, 이 아이디어는 꽤 중요한 곳에 숨어 있어요. 가장 유명한 건 켄 톰슨의 1984년 튜링상 수상 강연 Reflections on Trusting Trust예요. 그는 컴파일러가 자기 자신을 컴파일할 때 몰래 백도어를 심고, 그 백도어 심는 코드까지 스스로 복제하게 만드는 방법을 보여줬어요. 소스를 아무리 깨끗하게 검토해도 컴파일러 바이너리가 오염돼 있으면 소용없다는 충격적인 이야기였죠. 그 핵심 기법이 바로 퀸의 자기 복제예요.
함수형 프로그래밍의 Y 컴비네이터도 같은 계보예요. 람다 계산에는 이름 붙은 함수가 없어 재귀를 직접 못 쓰는데, Y 컴비네이터가 '자기 자신을 인자로 넘기는' 대각화로 재귀를 만들어내요. 재미있는 응용으로는 엔도 유스케(mame)의 퀸 릴레이가 있어요. 루비 코드가 다른 언어 코드를 출력하고, 그게 또 다른 언어 코드를 출력하고... 100개가 넘는 언어를 거쳐 원래 루비 코드로 돌아오는 작품이죠.
한국 개발자에게 주는 시사점
당장 실무에 퀸을 쓸 일은 없겠지만, 이 주제를 알아두면 몇 가지가 선명해져요. 첫째는 공급망 보안이에요. Trusting Trust 문제는 지금도 현재진행형이라, 재현 가능한 빌드(reproducible builds)나 최소한의 시드에서 컴파일러를 다시 세워 올리는 부트스트래핑 프로젝트가 실무적인 대응책으로 연구되고 있어요. 오픈소스 의존성이 폭증한 요즘, 빌드 신뢰성을 고민하는 DevOps·보안 엔지니어라면 꼭 알아둘 배경이죠.
둘째는 셀프 호스팅 컴파일러에 대한 이해예요. Go 컴파일러가 Go로, 러스트 컴파일러가 러스트로 짜여 있다는 게 처음엔 닭과 달걀 문제처럼 느껴지는데, 자기 참조가 무한 루프 없이 성립하는 원리를 감 잡게 해줘요. 셋째, 학부 계산이론 수업에서 정지 문제를 외우듯 넘어갔던 분이라면 '퀸을 직접 만든다'는 구체적인 목표로 다시 보면 훨씬 재미있을 거예요.
마무리
한 줄 정리: 퀸은 우연한 트릭이 아니라, '빈칸 있는 설계도를 자기 빈칸에 넣는' 대각화가 보장하는 수학적 필연이에요.
여러분은 주력 언어로 퀸을 직접 짜본 적 있나요? 아직이라면 이번 기회에 도전해 보시는 건 어떨까요. 그리고 Trusting Trust 같은 자기 복제 공격, 지금의 소프트웨어 공급망에서는 얼마나 현실적인 위협이라고 생각하시나요?
🔗 출처: Hacker News