🌐 Read in English

7장의 배경지식.

컴파일러 부트스트랩

"셀프 호스팅"은 자기 자신의 소스 코드를 컴파일할 수 있는 컴파일러를 뜻한다. 순환적으로 들리는데, 처음 겪을 때는 실제로 그렇다: 어떤 버전의 uhs도 존재하기 전에는, uhs 자신의 소스를 컴파일할 수 있는 것이 아무것도 없다 — 그것들은 그저 디스크에 놓인 하스켈 텍스트일 뿐이다. MicroHs는 셀프 호스팅 컴파일러라면 모두가 쓰는 평범한 방법으로 이 순환을 깬다: 같은 언어의 (충분히 큰 부분집합을 지원하는) 다른 이미 동작하는 구현으로 첫 번째 동작 사본을 만들고, 그 첫 사본이 이후를 넘겨받게 하는 것이다. 이 프로젝트에서 그 "다른 구현"은 GHC이며, 이 책의 모든 장이 빌드에 쓰는 nix develop 셸에 이미 들어 있다.

사다리, 7장이 끝난 시점의 모습

8장이 이를 위한 전용 make 타깃을 배선할 즈음에는, 부트스트랩 사다리에 세 개의 가로대가 있고, Makefile이 이들을 직접 이름 붙여 부른다(456ce17c:Makefile 66–69행, 전문 인용):

bootcombtest:	$(BIN)/uhs uhs.comb
	$(BIN)/uhs -ilib -isrc -omain-uhs.comb  MicroHs.Main
	$(BIN)/eval -H10000000 -K1000000 -ruhs.comb --  -ilib -isrc -omain-comb.comb MicroHs.Main
	cmp main-uhs.comb main-comb.comb

사다리로 읽으면:

  1. GHC가 컴파일러를 컴파일한다. $(BIN)/uhs — 평범한 네이티브 바이너리다 — 는 src/MicroHs/Main.hs와 그것이 임포트하는 모든 것을 GHC가 빌드해 만든다(456ce17c:Makefile 23행: $(GHCE) -package mtl -isrc -Wall -O src/MicroHs/Main.hs -main-is MicroHs.Main -o $(BIN)/uhs). 아직 자기 참조는 전혀 없다 — 앞선 모든 장의 "직접 해보기"가 이미 해 온 것과 똑같은 "GHC가 하스켈 프로그램을 빌드한다"일 뿐이다.
  2. bin/uhs가 같은 소스를 컴파일한다. uhs.comb 규칙 (456ce17c:Makefile 80–81행)은 $(BIN)/uhs -ilib -isrc -ouhs.comb MicroHs.Main을 실행한다 — GHC로 빌드된 컴파일러가 자기 자신의 src/MicroHs/*.hs 소스를 읽어 uhs.comb를 내놓는데, 이는 2장 이래 각 장의 .comb 출력이 써 온 것과 같은 텍스트 형식의 컴비네이터 파일이다. 이것이 진정한 의미의 셀프 호스팅 첫 단계다: 컴파일러가 자기 자신을 컴파일하고 있지만, 아직 자기 자신으로 실행되는 것은 아니다.
  3. bin/eval이 uhs.comb를 실행하고, 그것이 소스를 두 번째로 컴파일한다. bootcombtest의 가운데 줄이 uhs.comb를 C 런타임에 건넨다($(BIN)/eval ... -ruhs.comb -- ... MicroHs.Main) — 런타임은 2장이 그 첫 버전을 빌드했던 그 컴비네이터 파일 형식을 해석하는데, 지금 해석하고 있는 것은 다름 아닌 컴파일러 자신이다. 그렇게 해석 실행된 컴파일러는 MicroHs.Main을 소스로부터 다시 한 번 컴파일해 main-comb.comb를 쓴다. 한편 같은 타깃의 첫 줄인 $(BIN)/uhs -ilib -isrc -omain-uhs.comb MicroHs.Main은 원래의 GHC로 빌드된 바이너리가 독립적으로 동일한 소스를 main-uhs.comb로 컴파일하게 한다.
  4. 비교한다. cmp main-uhs.comb main-comb.comb — 평범한 바이트 단위 동등성 비교이며, 특별 취급은 없다.

이것과 나란히 존재하는 두 번째 검사가 있는데, 이는 이 장 자체의 7월 1일 커밋들이 추가하는 "로컬 lib" 하부구조로 지어졌다 (7장의 "무슨 일이 있었나" 참고): bootboottest(456ce17c:Makefile 61–64행, 전문 인용):

bootboottest:	$(BIN)/uhs $(BIN)/bootuhs
	$(BIN)/uhs     -ilib -isrc -omain-uhs.comb  MicroHs.Main
	$(BIN)/bootuhs -ilib -isrc -omain-boot.comb MicroHs.Main
	cmp main-uhs.comb main-boot.comb

$(BIN)/bootuhs는 두 번째 네이티브 바이너리다 — 여전히 GHC가 빌드하지만, GHC 자체의 base 패키지 대신 MicroHs 자신의 손으로 지은 lib/ 소스(ghc/의 프리미티브 심, -XNoImplicitPrelude, 그리고 아래 설명할 convertY.sh 전처리기를 거쳐)를 대상으로 모듈 단위로 컴파일된다. bootboottest는 이 대안적인, 라이브러리를 바꿔 낀 GHC 빌드가 보통의 빌드와 일치하는지 검사한다 — 컴비네이터 파일을 인터프리터로 돌리는 것과는 별개의, "이것이 여전히 같은 것을 뜻하는가" 의 다른 축이다.

왜 바이트 단위로 동일한 출력이 오라클인가

두 검사 어느 것도 "출력이 맞아 보이는가"를 묻지 않는다. 둘 다 그저 두 파일을 cmp할 뿐이다. 이는 의도적이며, 여기서 규모가 통하는 유일한 오라클(정답 판별 기준)이다: 컴파일러 버그 — 이를테면 케이스 절이 잘못된 순서로 처리되거나, 연산자가 잘못된 결합 방향으로 컴파일되는 것 — 는 버그가 되기 위해 무언가를 크래시시킬 필요가 없다. 잘 실행되지만, 같은 컴파일러의 다른 빌드가 같은 소스를 컴파일해 내놓는 것과 다른 값을 계산하는 .comb 파일을 만들어낼 수 있다. 잡아내지 못하고 넘어가면, 그런 종류의 버그는 이후 모든 빌드에 태연히 스스로를 컴파일해 넣을 것이다. 각 가로대에서의 바이트 단위 비교는 "컴파일러가 미묘하게 틀렸다"를 "이 두 파일이 다르다"로 바꾼다 — 잘못 컴파일된 정확한 경로를 우연히 건드리는 테스트를 누군가 작성해야만 드러나는 버그 대신, cmp가 즉시 알려주는 차이가 된다. 7장의 고된 작업 전체 — 실제로 bootcombtest를 진짜로 실행하는 것(8장의 이야기)만 빼고 모든 것 — 는 컴파일러 자신의 소스를 위 사다리의 2단계(bin/uhs가 자기 자신을 컴파일하는 것)가 파싱되고 실행되기라도 하는 uhs.comb를 내놓을 수 있는 상태로 만드는 작업이다.

제약: uhs는 오직 uhs만 쓸 수 있다

위 사다리가 무언가를 증명하려면, 컴파일러 자신의 소스가 GHC와, 결국에는 자기 자신 양쪽 모두에 대해 합법적인 입력이어야 한다. 이는 평범한 하스켈보다 훨씬 좁은 방언이다 — 타입 클래스가 없고(이 장 자체의 "직접 해보기"에서 src/MicroHs/와 src/Text/ParserComb.hs 전체에 grep -rn "class \|instance "를 돌려도 살아 있는 것이 하나도 나오지 않으며, lib/ 전체에 대한 같은 검색도 마찬가지다), deriving이 없고, 결합성 선언이 없다. 7장은 대체로 이 제약이 강제하는 다이어트이며, 이를 구체화하는 세 가지 예시는 다음과 같다:

  • Integer가 아니라 Int다. a721e046("Use Int instead of Integer"(Integer 대신 Int 쓰기))는 src/MicroHs/Parse.hs/Desugar.hs 전체에서 EInt의 페이로드를 Integer에서 Int로 좁힌다 — uhs 자신의 Exp 타입은 이미 6장의 Translate.hs에서 기계 폭의 Int로 정한 바 있고(그 산술 테이블은 Int -> Int -> Int 타입이다), 프론트엔드가 뒤늦게 이를 맞춘다.
  • 손으로 지은 Map. Data.Map은 Ord 인스턴스가 필요하지만 uhs에는 인스턴스가 아예 없다 — 그래서 f113210f이 src/MicroHs/Map.hs(33줄)를 추가하며, 타입 바로 옆 주석에서 스스로의 한계를 인정한다(f113210f:src/MicroHs/Map.hs 5행): -- This is a pretty bad implementation. 모든 조회와 병합 함수는 타입 클래스 제약을 통해 (==)에 손을 뻗는 대신, 동등성 검사를 명시적 인자로 받는다(lookup :: (k -> k -> Bool) -> k -> Map k v -> Maybe v).
  • 결합성 메커니즘이 없다 — 그래서 uhs 자신의 파서는 infixl/infixr 선언을 읽는 대신, pExpr 안의 pLeftAssoc/ pRightAssoc/pNonAssoc 호출로 손으로 짠 하나의 사다리에서 모든 연산자의 우선순위를 알아낸다(f113210f:src/MicroHs/Parse.hs 450–462행) — 읽을 선언이 아예 없다; 이 장의 커밋 범위 전체에서 src/MicroHs/Parse.hs에 infix를 프로젝트 전체로 검색해도 아무것도 나오지 않는다. 이 범위의 lib/*.hs에 실제로 나타나는 --Yinfixr 2 || 스타일 주석들(7장의 "무슨 일이 있었나"가 하나를 인용한다)은 아래의 "로컬 lib" 빌드 경로에서 GHC를 위한 것이지, uhs 자신의 파서를 위한 것이 아니다.

--X/--Y 트릭

같은 소스 파일이 서로 다른 필요를 가진 두 컴파일러를 동시에 만족시켜야 한다 — GHC는 진짜 hiding 절, 진짜 결합성 선언, 진짜 deriving을 원하고; uhs는 이들 중 무엇도 이해하지 못하며 시도했다간 막혀 버릴 것이다. 해법은 텍스트 층위다: GHC 전용 문법을 두 글자짜리 마커 접두사가 붙은 평범한 주석으로 적어 두고, GHC가 파일을 파싱하기 직전에 GHC 전처리기(-F -pgmF, 컴파일 전에 소스를 재작성하는 단계)가 그 마커를 벗겨내게 한다. uhs 자신은 이 전처리기를 결코 실행하지 않으므로, 그저 평범한 주석으로 보고 건너뛴다. 두 스크립트 모두 두 줄이다(b71e0e90:convert.sh가 67715b16:convertX.sh와 bea8283d:convertY.sh로 나뉜다; 여기서는 둘 다 존재하게 된 시점의 모습인 f113210f:convertX.sh와 f113210f:convertY.sh를 각각 전문 인용한다):

#!/bin/sh
( echo "{-# LINE 1 \"$1\" #-}" ; sed -e 's/--X//' $2 ) > $3

#!/bin/sh
( echo "{-# LINE 1 \"$1\" #-}" ; sed -e 's/--Y//' $2 ) > $3

convertX.sh는 $(BIN)/uhs 빌드 자체(GHCE, 위의 1단계)에 공급된다: import Prelude --Xhiding (Monad(..), ...) 같은 줄은 GHC가 보는 순간 import Prelude hiding (Monad(..), ...)가 된다 — uhs의 소스는 자신만의 >>=/pure/<*>를 평범한 최상위 함수로 손수 지어 쓰는데(7장 참고), 그렇지 않으면 GHC의 진짜 Prelude가 그 이름들을 두고 충돌할 것이므로 필요하다. convertY.sh는 "로컬 lib" 빌드(GHCC, bootboottest의 $(BIN)/bootuhs가 의존하는 장치)에 공급된다: lib/Data/Bool.hs의 --Yinfixr 2 || 같은 줄은 진짜 infixr 2 || 선언이 되는데, 그 빌드는 lib/의 손으로 지은 (||)를 GHC 자신의 식 문법 아래서 컴파일하며, uhs 자신의 파서와 달리 이 문법은 선언된 결합성을 정말로 신경 쓰므로 필요하다. 같은 소스, 두 개의 마커, 두 종류의 독자.

여기에 붙일 이름이 하나 더 있다

이 두 단계짜리 자기 검사 — 한 단계 건너서 컴파일러 출력이 컴파일러 출력과 일치하는 것 — 는 켄 톰프슨(Ken Thompson)의 1983년 튜링상 강연 "Reflections on Trusting Trust"(1984년 CACM에 게재)가 제기하는 것과 같은 모양의 신뢰 문제다: 통과한 cmp는 두 빌드가 서로 일치한다는 것을 증명할 뿐, 둘 중 어느 쪽이 옳다는 것을 증명하지 않는다 — 그래서 최초의 GHC로 빌드된 bin/uhs에 심어진 버그(혹은 그보다 더한 무언가)는 원리상 이후의 모든 부트스트랩을 아무도 눈치채지 못한 채 살아남을 수 있다.