컴파일러에게 점프를 가르치다

앞 Part는 진단으로 끝났다: self-hosted한 코드 생성기는 모든 함수 호출을 같은 방식으로, 프레임을 쌓는 평범한 call로 lower했고, 그래서 tail-recursive한 코드 —— 스택을 기르지 않고 루프해야 할 규율 있는 것 —— 가 그것에 컴파일되면 그럼에도 스택을 길렀다. 레퍼런스 생성기, 호스트 언어로 쓰인 것, 은 그 위치에서 보증된 말단 호출을 emit할 줄 알았다. Mere로 쓰인 것은 하지 않았다. behavioral한 fixpoint 통째가 하나의 빠진 명령을 기다리고 있었고, 이 Part는 그것을 넣는 것에 대해서다.

「말단 위치」가 실제로 요하는 것

말단 호출이란, 그 결과가 감싸는 함수의 결과인 call이다 —— 그것이 return한 뒤에 아무것도 일어나지 않으므로, 호출자의 프레임을 간직할 이유가 없고, call은 점프가 될 수 있다. 그것을 인식하는 것은 로컬한 체크로 들리나, 그렇지 않다: 말단 위치는 프로그램의 구조를 통해 안으로 흐르는 성질이다. 함수가 마지막으로 하는 것은 if일 수 있고, 그러면 그 두 분기가 말단 위치에 있다. match일 수 있고, 그러면 모든 arm이 그렇다. 진짜 말단이 그 body인 let일 수 있다. 그래서 코드 생성기는 단지 call을 보고 정할 수 없다; 프로그램을 걸으며, 한 비트의 문맥 —— 지금 말단 위치에 있는가? —— 을 나르고, 그 비트를 함수를 끝낼 수 있는 모든 구문의 분기로 올바로 전파시키고, 다른 어디서든 그것을 클리어해야 한다, 왜냐하면 식의 도중에 묻힌 call은 단호히 말단 호출이 아니고, 그 프레임을 지녀야 하기에.

그래서 변경은, 그 비트를 생성기를 통해 threaded하는 것이었다. 생성기가 걸으며 나르는 상태가, 현재의 식이 말단 위치에 있는가의 플래그를 얻었다. 함수 body에 들어가면 그것이 세팅되고; if의 분기, match의 arm, let의 body가 그것을 물려받고; 평범한 부분식이 그것을 클리어한다. 그리고 call이 마침내 emit되는 유일한 점에서, 플래그가 두 명령 사이를 정한다: 프레임을 쌓는 평범한 call이냐, 점프하는 보증된 말단 호출이냐. 작업의 대부분은 이 참을성 있는 전파로, 한 번에 하나의 구문, 비트를 꼭 올바른 곳에, 다른 어디도 아닌 곳에 닿게 한다.

무언가를 밝힌 반대

하나의 걸림이 있었고, 그것이 요한 것이 아니라 폭로한 것 때문에 말할 값이 있다. 말단 위치 플래그를 뒤집는 자연스러운 방식은, 생성기의 상태를 취해 그 한 필드를 바꾼 복사본을 낳는 것 —— 평범한 record 갱신 —— 이었다. 하지만 타입 추론기가 그것을 거부했다, 생성기의 함수들이 모두 서로를 참조하고 그 타입이 아직 함께 산정되고 있는 문맥에서. 갱신되는 값이 그 시점에 아직 구체적인 record 타입에 고정되지 않았고, 정확한 타입이 아직 열려 있는 값의 필드를 갱신하는 것은, 바로 엄격한 추론기가 통과시킬 수 없는 종류의 것이다, 왜냐하면 갱신이 well-formed인지 아직 알 수 없기에. 수정은 작았다 —— 플래그를, inline 갱신이 아니라 함수 호출로서 변경을 적용하는 작은 헬퍼를 통해 뒤집고, 그것이 추론기에 필요한 구체적인 타입을 주었다. 하지만 반대는 노이즈가 아니었다. 그것은 언어가 자기 자신을 컴파일하도록 요구받은 바로 그 순간에 타입 시스템이 그 일을 하고 있던 것이고, 때로 현학적으로 느껴지는 엄격함이, 보증을 실하게 만드는 같은 엄격함이라는 정직한 일깨움이었다.

이십만 프레임, 평평하게

명령이 threaded되어, 중요했던 테스트는 깊이가 입력과 함께 자라는 재귀 —— overflow하던 형태. 이십만 레벨 깊이 구동된 tail-recursive한 카운터가, self-hosted한 생성기에 컴파일되어 WebAssembly 바이너리로 돌고, 이제 스택 제한에 닿지 않고 완주했다, 이전에는 크래시하던 곳에서. 말단 호출은 점프가 되었다; 프레임은 더는 쌓이지 않았다; 재귀의 깊이는 더는 문제가 아니었다. fixpoint를 막던 overflow는 그저 사라졌다. 생성기는 결코 몰랐던 명령을 emit할 줄 배웠고, interpreter의 관대한 스택이 숨기던 자원 한계가, 이제 소스에서, 컴파일된 코드 자신 안에서 다루어졌다.

너머의, 더 나쁜 것

그리고 컴파일된 컴파일러는, 더는 스택 고갈로 크래시하지 않고, 이제껏보다 멀리 달렸다 —— 그리고 또 멈췄다, 다르게. 이번엔 overflow하지 않았다; 명시적 실패에 부딪혀 exit했다, 조용히, 컴파일해야 할 입력에서. 이것의 의미는 처음엔 명백하지 않았고, 말단 호출 작업의 퇴행으로 읽기 쉬웠다. 반대였다. 말단 호출은 바로 그 일을 했다: 재귀를 너무나 철저히 평평하게 해서, 컴파일된 컴파일러가 이제 처음으로 자기 자신의 logic을 끝까지 달렸다 —— overflow가 닿기 전에 늘 크래시하던 결함에 이를 만큼 멀리. 구조적 self-hosting은 컴파일러가 valid한 바이너리를 emit할 수 있음을 증명했을 뿐; 바이너리는 자기 자신의 logic을 끝에서 끝까지 실행한 적이 없었다. 이제 했고, 그리고 처음으로 끝에서 끝까지 도는 것은, 프로그램의 깊은 곳에 사는 버그가 나와 당신을 만나는 바로 그 때다.

그래서 하나의 빠진 명령은 쉬운 쪽의 절반으로 판명되었다. 그것은 컴파일된 컴파일러를 일찍 멈추던 벽을 치웠고, 그렇게 함으로써, 컴파일러가 그 존재에서 처음으로, 결코 실제로 돈 적 없는 자기 자신의 부분에 닿게 허락했다. 그것이 거기서 찾은 것은 하나의 버그가 아니라 셋이었고, 그 저마다가, 프로그램이 자기 자신에 컴파일되었을 때에만 나타나는 종류였다. 다음 Part는, 그 사냥이다.