자기 자신을 한 번도 돌린 적 없는 컴파일러

Mere가 여러 Part 전에 달성한 무언가에 쓰여 온 말이 있다 —— self-hosting —— 그리고 그것은 혼동하기 쉬운 두 다른 것을 의미한다고 판명되었다. 하나는, Mere로 쓰인 컴파일러가 자기 자신의 소스를 취해 valid한 바이너리를 emit할 수 있다는 것: 모든 module, 자기 자신의 코드를 컴파일하는 코드 생성기를 포함해, validator가 받아들이는 WebAssembly로 lower된다. 그것은 이루어졌고, 실이었고, 당시 그것은 프로젝트 통째의 summit처럼 느껴졌다. 다른 의미는 더 강하고, 조용히 아직 손이 닿지 않는 곳에 있었다: emit된 바이너리가, 프로그램으로 돌면, 그 자체로 동작하는 컴파일러라는 것 —— 소스 파일을 건네면 올바른 출력을 낳는다는 것. 그 둘 사이의 gap이 이 Part 통째이고, 그것은 첫 의미가 결코 요하지 않는 하나의 것을 할 때까지 보이지 않는 gap이다: 실제로 그것을 돌리는 것.

한 번도 돌려진 적 없는 테스트

강한 쪽의 주장을 결말짓는 방식은 fixpoint 테스트이고, 진술하기는 단순하다. 작은 프로그램을 취한다. 두 번 컴파일한다. 첫 번째는, 컴파일러를 평범한 방식으로, interpreter 아래에서 돌리고, 출력을 간직한다. 두 번째 는, 자기 자신에 의해 WebAssembly 바이너리로 컴파일되어, 이제 그 바이너리로 돌고 있는 컴파일러로 —— 같은 프로그램을 건네고 그 출력을 간직한다. 두 출력이 동일하고, 어느 것을 돌려도 올바른 것을 하면, 컴파일된 컴파일러는 컴파일러의 충실한 복제다: 진정한 bootstrap fixpoint. 구조적 self-hosting은 그 테스트의 후반에 요하는 바이너리를 낳고 있었지만, 거기서 멈춰 있었다. valid한 바이너리를 emit하는 것과 그것을 실행하는 것은 다른 행위이고, 두 번째는 결코 행해진 적이 없었다.

첫 실행

그래서 그것이 행해졌고, 즉시 실패했다. 자기 컴파일된 컴파일러는, 더할 나위 없이 자명한 프로그램을 건네받고, 틀린 출력을 낳지 않았다 —— 출력을 전혀 낳지 않았다, 왜냐하면 스택의 끝을 달려 지나 크래시했기에. runtime의 스택 제한을 올리는 반사적인 첫 수는, 아무 유용한 것도 하지 않았고; 충분히 높이 밀어 올리면, 프로그램보다 먼저 runtime 자신이 나가떨어졌다. 무엇이 잘못이든, 더 많은 여지를 주는 것으로는 고쳐지지 않는 것이었다. 컴파일된 컴파일러의 무언가가, 끝없이 스택을 소비하고 있었다.

버그가 아니라, 한계

결정적인 실마리는 비교였다. 그 같은 자명한 프로그램이, 첫 번째 방식으로 컴파일되어 —— interpreter 아래의 컴파일러로 —— 어려움 없이 끝나 답을 낳았다. 그러므로 계산은 종료했다; 유한했다. 그래서 크래시는 무한 재귀가 아니라, 영원히 루프하는 logic 에러가 아니었다. 그것은 자원의 한계였다: 꼭 같은 유한한 계산이 interpreter의 관대한 스택에서 완주하고, WebAssembly runtime의 훨씬 얕은 스택을 오버플로했다. 이것은 이 연재에서 관대한 호스트가 이미 두 번 가르친 같은 교훈이, 새 옷을 입은 것이다. interpreter는, 큰 native 스택 위에서 돌며, 줄곧 비용을 숨기고 있었다. 계산이 모든 프레임을 세는 스택 위로 옮겨졌을 때에만 비용이 보였고 —— 그리고 그것은 프로그램이 계산하는 것의 결함이 아니라, 그것을 계산하는 데 얼마나 깊이 내려가야 하는가의 결함이었다.

컴파일러가 emit하지 않은 명령

왜 그렇게 깊이 내려가는가? tokenizer와 parser는 tail-recursive한 스타일로 쓰여 있었다, 중첩하는 게 아니라 결과를 누적해 루프하는 규율 있는 것 —— 바로 스택을 기르지 않아야 할 형태. 그리고 그것은 차이를 낳지 않았고, 그것이 수수께끼였다, 원인이 한 단 아래라고 판명될 때까지. tail-recursive한 스타일이 평평한 채 있을 수 있는 것은, 컴파일러가 말단 호출을 프레임을 쌓는 call이 아니라 점프로 바꿀 때뿐이다. WebAssembly 에는 바로 이것을 위한 명령, 보증된 말단 호출이 있고, 레퍼런스 코드 생성기는 그것을 emit했다. self-hosted한 코드 생성기 —— Mere로 쓰인, 방금 자기 자신을 컴파일한 것 —— 는 하지 않았다. 그것은 모든 call을 같은 방식으로, 프레임을 쌓고 return을 기다리는 평범한 call로 lower했다. 그래서 tail-recursive한 Mere는, self-hosted한 컴파일러에 컴파일되면, 그럼에도 프레임을 쌓아 올렸고, 깊이가 입력의 크기와 함께 자라는 재귀 —— 긴 token의 list를 걷는, 예컨대 —— 는 스택이 다할 때까지 올랐다. 소스는 규율 바르고; 타겟은 스택 기반이고; 그리고 사이의 컴파일러가 그것들을 다리 놓기를 거부했다.

그 거부는, 컴파일러가 그저 emit될 뿐 결코 컴파일러로서 돌려지지 않는 한, 보이지 않았다. 구조적 self-hosting은 실의 달성이고, 그리고 부분적인 것, 뒤에 더 높은 봉우리가 있다고 판명된 summit이었다. behavioral한 fixpoint —— 컴파일된 컴파일러가 실제로 동작하는 것 —— 은 하나의 빠진 명령을 기다렸고, 그 gap이 마침내 보인 유일한 이유는, 그 물건이, 마침내, 돌려졌다는 것이었다. 다음 Part는, 그것이 emit하기를 한 번도 배우지 않은 명령을, 그것에 가르치는 것에 대해서다.