코드 생성기를 Mere로: 자기 자신을 뱉는 컴파일러

셀프 호스트 파이프라인은 이제 Mere를 읽고, 그 타입을 검사하고, 해석할 수 있다. 하지만 프로그램을 해석하는 것은, 그것을 컴파일하는 것과 같지 않다 —— 인터프리터는 트리를 직접 돌리고, 컴파일러는 인터프리터가 없어도 도는 코드를 뱉는다. 셀프 호스트 컴파일러의 마지막 조각은, 그 차이를 낳는 것: 코드 생성기, Mere로 쓰이고, 검사된 프로그램을 WebAssembly로 바꾸는. 그것을 마치면, 이 Part 전체가 돌아온 루프가 닫힌다.

셋 중, 왜 WebAssembly인가

OCaml 컴파일러는 세 코드 생성기 —— C로, LLVM으로, Wasm으로 —— 를 가지고, 셀프 호스트는 하나를 골랐다: Wasm 생성기, WAT emitter다. 선택은 자의적이지 않다. Wasm은 브라우저의 타깃이고, 브라우저는 셀프 호스트 파이프라인이 이미 사는 곳이다 —— 포매터, REPL, 타입 검사기는 모두 웹 페이지로 돌았다. 셀프 호스트 Wasm 생성기는, 셀프 호스트 노력 전체가 향해 온 데모를 닫는다: Mere 소스를 페이지에 붙이면, Wasm 모듈이 돌아온다, 서버 없이, 루프에 OCaml 없이. 그것은 또 원래의 셋 중 가장 작고, 그것이 그것을, 셀프 호스트할 자연스러운 첫 —— 그리고 판명되었듯, 유일하게 필요한 —— 타깃으로 만든다. C와 LLVM의 생성기는 OCaml에 머문다; 셀프 호스트 컴파일러는 Wasm을 뱉는다.

Mere에서 Wasm을 뱉는 것은, Wasm backend의 회가 기술한 것과 같은 작업이, 이제 그것이 타깃하는 언어로 쓰인 것이다: 값을 선형 메모리에 레이아웃하고, 클로저를 함수 테이블의 인덱스와 환경 offset의 쌍으로 표현하고, match를 로드와 분기로 낮추고, 모든 것을 샌드박스의 import 기구에 통과시킨다. 그 모두가, 이번에는, 프론트엔드가 낳고 타입 검사기가 축복하는 공유된 구문 트리를 소비하는 Mere로.

컴파일러를 뱉는 컴파일러

여기서 자기 참조가 가장 깊은 점에 다다른다. 코드 생성기는 그 자신이 Mere 프로그램 —— 실질적인 것이다. 그래서, 컴파일러를 참으로 셀프 호스트라 이름 붙이는 것을, 할 수 있다: 코드 생성기를 자기 자신의 소스에 겨눠 돌린다. Mere로 쓰인 Wasm 생성기에, 그 자신의 소스 파일을 주면, 그것은 자기 자신의 valid한 WebAssembly를 뱉는다 —— 백만 자를 훌쩍 넘는 WAT 텍스트로, 표준 Wasm 어셈블러가 그것을 받아들여 Wasm 모듈로 바꾼다. 컴파일러가 컴파일러를 컴파일했다.

그것이 부트스트랩 가능한 컴파일러의 정의이고, 장식이 아니라 참된 마일스톤이다. 자기 자신의 소스를 뱉을 수 있는 컴파일러는, 원리적으로, 처음 쓰인 언어에서 자유롭다: OCaml은 Mere를 이륙시킨 발판이었지만, Mere로 쓰인 생성기가 Mere로 쓰인 생성기를 낳을 수 있게 되면, OCaml의 원판은 언어를 살려 두는 데 논리적으로는 더 이상 요하지 않는다. 실제로는 머문다 —— 셀프 호스트 부품이 검증되는 대상의 레퍼런스 로서, 그리고 extern primitive의 host로서 —— 하지만 의존은 원리적으로 끊기고, 그것이 부트스트랩의 요점 그 자체다.

루프가 어디서 멈추는가, 그리고 red herring에 대해 정직하게

달성된 것을 정확히 말할 가치가 있다, 프로젝트가 지키는 정직한 장부의 정신으로. 컴파일 시간의 셀프 컴파일은 돈다: Mere 코드 생성기는, 기존의 툴체인 아래에서 돌리면, 자기 자신의 소스의 valid한 Wasm을 뱉고, 어셈블러가 그것을 받아들인다. 그 마일스톤은 지속적 통합 스위트에 못 박혀 있다 —— self-emit이 크기 임계 이상의 WAT 출력을 낳고, 어셈블러가 그것을 검증한다는 서 있는 테스트로.

완전한 런타임 부트스트랩 루프 —— 그 self-emit된 Wasm을 취해, 돌리고, 그것이 이번에는 Mere를 컴파일한다 —— 는 닫기가 더 어려웠고, 어려웠던 이유는 틀린 원인을 좇는 것에 대한 작은 우화다. 컴파일된 컴파일러를 Wasm 안에서 돌리면 trap했고, 그 trap은 불길한 서명을 가지고 있었다: 이름이 다섯 글자인 함수를 참조하는 프로그램은 문제없이 컴파일되고, 여섯 글자에서는 trap한다 —— 정확하고, 내용과 무관한 경계로, 이름이나 메모리의 레이아웃의 깊은 버그로 보였다. 그것은 red herring이었다. 진짜 원인은 평범했다: 셀프 컴파일은, 작은 프로그램을 컴파일하는 것보다 훨씬 많은 작업 메모리를 요한다 —— 수십 메가바이트의 스크래치 arena —— 그리고 생성된 Wasm 모듈의 선형 메모리는, 그것을 훨씬 밑도는 몇 메가바이트로 상한이 매겨져 있었다. “다섯이냐 여섯 글자냐의 경계”는, 그저 arena가 천장을 넘는 입력이었을 뿐이고, 이름의 길이가 우연히 총 할당량과 상관하여 bisection을 속였다. 메모리 상한을 올리자 루프는 닫혔고, 이제 runtime-bootstrap 체크가 CI에 선다: 컴파일된 컴파일러가 돌고, 프로그램을 끝에서 끝까지 컴파일한다. 아직 미뤄진 한 조각은, 그 올린 천장보다 큰 워크로드를 위한 성장할 수 있는 할당자뿐이다.

교훈은, 정직한 장부가 양방향으로 벤다는 것이다. 그것은 과한 주장을 멈췄다 —— 한동안 루프는 정말로 닫히지 않았다 —— 그리고 그것은 또한, 메모리 천장을 정확성의 버그로 착각하지 않는 것, 컴파일러에 대해 이론을 세우는 대신 불길한 경계를 지루한 진실까지 좇는 것을 뜻했다. “충분히 가깝다”는 양방향에서 거부된다: 가지지 않은 부트스트랩을 주장하지 말고, 가지지도 않은 깊은 결함을 진단하지도 말라.

파이프라인, 통째로

코드 생성이 셀프 호스트되어, 컴파일러의 모든 단이 Mere에 존재한다 —— 렉서, 파서, 포매터, 평가기, 타입 검사기, 그리고 코드 생성기, 수천 줄의 언어가 자기 자신을 기술하고, 모두가 하나의 구문 트리를 공유하고, 저마다가 OCaml의 쌍둥이에 대해 cross-validate된다. OCaml 컴파일러의 역할은, 이 Part의 과정에서 조용히 반전되었다: 그것은 구현의 전부로 시작해, 발판으로 끝난다 —— 대조할 레퍼런스와, primitive의 host —— 한편, 도는 컴파일러는 이제, 그것이 컴파일하는 언어에 존재한다. 그 반전은 도약으로 일어나지 않았다; 한 번에 하나의 cross-validate된 부품씩, 그 저마다가 앞에 온 것에 유지되어, 일어났다.

컴파일러는 Mere에 존재하고, 자기 자신을 뱉을 수 있다. 이야기에 남는 것은, 또 하나의 부품이 아니라, 장소다: 여기서 세워진 모든 것은, 사람이 닿을 수 있는 어딘가에서 돌기 위한 것이었다. 포매터, REPL, 타입 검사기, 컴파일러는, 떨어질 때마다 웹 페이지에 배선되었다. 다음 회, Part V의 마무리: 브라우저에서 도는 Mere —— 네 개의 live page, 거기서 셀프 호스트 파이프라인이, 그것이 타깃하는 샌드박스로 컴파일 되어, 당신의 눈앞에서 일을 한다.