포매터, 그리고 셀프 호스트가 셀프 호스트를 파싱하다

지난 회는 프론트엔드를 세웠다 —— Mere의 렉서와 파서, 공유된 구문 트리를 낳는 —— 그리고, 프리티 프린터가 먼저 와서 그 트리를 정의했음에 짚었다. 이번 회는 프리티 프린터 그 자체의 이야기다: 왜 그것이 먼저 셀프 호스트할 옳은 부품이었는지, 그리고 “도는 것처럼 보인다”를 “원본에 대해, 그리고 자기 자신에 대해 검증되었다”로 바꾸는 두 층의 체크다.

왜 포매터가 먼저 갔는가

컴파일러를 셀프 호스트하는 것은 큰 일이고, 부품의 순서는 진짜 결정이다. 포매터 —— 구문 트리를 취해, 깨끗한 소스 텍스트로 그려 되돌리는 도구 —— 가 첫 조각으로 골라졌고, 그 이유는 모두 검증 가능성에 대한 것이다.

그것은 순수하다: 구문 트리에서 문자열로의 함수, 입력 없음, 출력 없음, 상태 없음. 모킹할 것도, 순서 지을 것도 없이 —— 그저 값이 들어가고 값이 나온다. 그것은 언어가 이미 가진 것으로 표현할 수 있다: 재귀, variant 위의 패턴 매칭, 문자열 구축, 그 모두를 Mere는 할 수 있었다. 그리고 가장 중요 하게, 그것은 체크하기 쉽다. 출력이 문자열이고, 기준이 되는 문자열을 낳는 OCaml 포매터가 이미 있기 때문이다. 대안과 비교하라: 파서는 크고, 타입 검사기는 unification을 요하고, 평가기와 코드 생성기는 상태가 무겁고 네 backend에 걸친다. 포매터는, 진짜 컴파일러의 참된 한 조각이면서, 정확히 검증하기에 충분히 작고 순수한, 유일한 부품이다. 가장 검증 가능한 부품으로 셀프 호스트를 시작하는 것은, 언어 자신의 제1원칙 —— 확신할 수 있는 것을 최적화한다 —— 을, 부트스트랩 계획 그 자체에 적용한 것이다.

작업은 OCaml 포매터의 충실한 번역이었다: 열 몇 단에 걸친 같은 precedence 구동의 괄호 삽입, block 형의 같은 개행과 들여쓰기, 구문 슈가(range, cons 리스트, lambda 축약형)의 같은 복원, 중위 연산자와 record 리터럴과 match arm의 같은 레이아웃. OCaml의 Buffer는 Mere의 문자열 빌더가 되고, 그 List.map은 prelude의 것이 되고, 포매터는 결코 raise하지 않으므로, 이식할 예외는 없었다. 결과는, 육백 줄의 OCaml이 한 것을, 오백 줄쯤의 Mere가 하는 것이었다.

체크 하나: 기준에 충실

첫 검증은 parity 규칙, backend에서 바뀌지 않았다: Mere 포매터의 출력은, 테스트 코퍼스 전체에 걸쳐, OCaml 포매터의 출력에 바이트 단위로 같아야 한다. OCaml 포매터가 “Mere 코드는 어떻게 보여야 하는가”의 기준의 정의이고, 셀프 호스트 판은 그것을 꼭 재현할 의무를 진다 —— 동등한 정형도, 가까운 것도 아니라, 같은 바이트다. 전체 스위트에 걸쳐 돌리면, 둘은 일치하고, 그것은 이식이 그저 컴파일되어 돈 것뿐 아니라 —— 마지막 공백까지 원본의 동작을 재현했음을 뜻한다. 이것은 번역이 충실하다고 증명 한다: Mere 포매터는, 다시 쓰인 OCaml 포매터이고, 단지 비슷한 도구가 아니다.

체크 둘: 기준을 요하지 않는 round-trip

두 번째 체크는 더 흥미롭다. 프론트엔드를 그 자신에 대해 검증하고, OCaml 기준을 전혀 요하지 않기 때문이다. 파서와 포매터가 둘 다 존재하면, 그것들은 루프로 합성된다: 소스 텍스트를 취해, 트리로 파싱하고, 트리를 소스로 정형해 되돌린다. 올바른 포매터는 멱등이다 —— 이미 정형된 코드를 정형해도 아무것도 바뀌지 않는다 —— 그래서 루프를 두 번 돌리면 고정점에 이르러야 한다: 파싱하고, 정형하고, 그 결과를 파싱하고, 또 정형하여, 출력은 첫 정형과 동일해야 한다. 만약 그렇지 않으면, 파서와 포매터는 트리에 대해 어긋나 있다 —— 파서가, 소스가 함의한 것과 포매터가 다르게 그리는 구조를 짰다 —— 그리고 round-trip이 그것을 외부의 오라클 없이 잡는다. 두 부품이 서로를 체크하기 때문이다. 이것은 Part IV에서 네 backend가 서로를 검증한 것과 같은 아이디어이고, 이제 프론트엔드의 두 절반 사이에 있다.

셀프 호스트가 셀프 호스트를 파싱하다

그 체크의 가장 날카로운 형태는, 프론트엔드를 손에 넣을 수 있는 가장 까다로운 입력에 겨누는 것이다: 그 자신의 소스 코드. 셀프 호스트 파서가 fmt.mere와 파서 자신의 소스를 파싱하고; 셀프 호스트 포매터가 그것들을 정형하고; round-trip이 유지되어야 한다. 이것은, 셀프 호스트와 dogfood가 하나의 행위로 융합하는 마일스톤이다 —— 프론트엔드는 그 자신이 실질적인 Mere 프로그램이므로, 프론트엔드를 프론트엔드 위에서 돌리는 것은, 동시에, 그것이 마주할 수 있는 가장 현실적인 테스트이고, 도구가 도구를 처리하는 문자 그대로의 실례다. 셀프 호스트 프론트엔드가 자기 자신의 소스를 파싱하고 다시 정형하여 고정점에 이르렀을 때, “Mere는 Mere를 처리할 수 있다”는, 이 층에 대해, 소망이기를 그치고, 실증적으로 일어난 일이 된다.

그리고 그 모두를 행하는 하네스는, 한 번의 체크가 아니다; 그것은 항구적인 인프라다. OCaml 기준에 대한 cross-validation과, 자기 자신에 대한 round-trip이, 셀프 호스트 노력의 나머지 전체가 도는, 서 있는 테스트가 된다. 이 뒤에 세워지는 모든 부품 —— 평가기, 타입 검사기, 코드 생성기 —— 이 같은 규율을 잇는다: Mere로 쓰이고, OCaml의 쌍둥이에 대해 cross-validate되고, 일치를 요구받는다. 포매터는 하나의 도구를 이식했을 뿐이 아니다; 뒤의 모든 도구가 어떻게 신뢰될지를 확립했다.

프론트엔드는 이제 Mere를 읽고 다시 쓸 수 있다, 두 방식으로 검증되어. 아직 할 수 없는 것은, 그것을 돌리는 것 —— 파싱된 트리를 취해, 그 결과를 계산하는 것 —— 이다. 그것이 평가기이고, 그것을 Mere로 쓰면 특유의 진기한 것이 생긴다: Mere를 위한 인터프리터, Mere로 쓰이고, 자기 자신을 해석할 수 있는. 다음 회: 메타 순환 평가기.