09 — Types at last (마침내 타입)
현재 위치
8장은 298c9824("Rename uhs to mhs.", uhs를 mhs로 이름 바꾸기),
2023-07-20 14:58:46에서 끝난다: 컴파일러는 셀프 호스팅하고,
bootcombtest는 통과하며, 바이너리는 마침내 이 책이 처음부터 써 온
이름 mhs에 답한다. 그 바이너리는 타입을 단 하나도 검사하지 않는다.
f :: T는 3장의 e96d04be(2023-05-30) 이래로 파싱되어 왔고, 곧장
dsDef (Sign _ _) = []로 흘러갔다 — 받아들여졌다가 버려졌다. 8장
자신의 db418344(2023-07-18)는 시그니처에 진짜 문법을 부여했다 —
Expr과 구별되는 TVar/TConstr/TUVar 타입인 EType과,
forall을 위한 ETypeScheme — 하지만 디슈가러의 판정은 바꾸지
않은 채로 남겼다: Sign _ _ -> [], 여전히 그 뒤 어디서도 파싱된
것을 읽지 않는다. 이 장의 범위인 298c9824..a38c64ce, 21일에 걸친
커밋 24개는 마침내 무언가가 그렇게 하는 지점이다.
무슨 일이 있었나
"Update"라는 이름의 커밋 세 개
이 범위는 7936c701, bca0b02d, 3719955b로 열리는데, 셋 다
2023-07-20에, 모두 "Update"(갱신)라는 제목으로, 매번 정확히 파일
하나만 건드린다: README.md(순서대로 4줄 추가/13줄 삭제, 1/1,
그리고 삭제 없이 6줄 추가). 셋 중 어느 것도 타입 검사와는 무관하다
— 8장의 끝과 이 장의 첫 실질적인 커밋 사이 공백에 놓인 문서 정비일
뿐이다. 여기 실린 것은 오직 "모호하게 이름 붙은 커밋도 어쨌든
확인한다"가 이 책 자신의 기준이기 때문이지, 이들에 대해 더 할 말이
있어서가 아니다.
하루 만의 준비: 33b009fa부터 e5bc9236까지
다섯 커밋, 전부 2023-07-21, 누군가 그 위에 타입 검사기를 쓰려 시도하기 전에 하나하나 바닥을 다진다.
33b009fa("Use Expr for EType.", EType에 Expr 쓰기)는 db418344가
이틀 하고도 스무 시간 전에 도입했던 세 생성자짜리 EType을 지우고
type EType = Expr와 validType 술어로 대체한다 —
aux/hindley-milner-gently.md가 이
결정으로 문을 여는데, 이것이 검사기의 나머지 전부가 그 위에 세워지는
단 하나의 결정이기 때문이다. 같은 커밋은, 제목에는 언급되지 않은
채, showEType — 사람을 위해 타입을 프리티 프린트했을 함수 — 를
결코 반환하지 않는 함수로 망가뜨린다(33b009fa:src/MicroHs/Parse.hs,
전문 인용, 이 함수에 대한 diff 전체):
showEType :: EType -> String
-showEType at =
- case at of
- TVar i -> i
- TConstr c ts ->
- if null ts then
- c
- else
- "(" ++ unwords (c : map showEType ts) ++ ")"
- TUVar n -> "a" ++ showInt n
+showEType = showEType
더 이상 패턴 매칭할 TVar/TConstr/TUVar가 없다 — EType은
이제 그냥 Expr이다 — 그리고 showEType을 Expr을 직접 걷도록
다시 쓰는 대신, 33b009fa는 호출된다면 영원히 도는 스텁을 남긴다.
직접 확인한 결과: 33b009fa와 (아래) 617475b6 사이의 어떤
커밋에서도 TypeCheck.hs나 Main.hs가 showEType이나
showETypeScheme를 호출하지 않는다 — 이 스텁은 거의 열엿새(15일
21시간) 동안, c0b279fc의 뼈대 검사기, 두 개의 "Transfer" 커밋,
f7db30f1의 라이브러리 전역 시그니처 정비를 거치는 내내, 단 한 번도
실행되지 않은 채 소스 안에 죽어 있다.
16초 뒤 45b34015는 또 다른 함수 showExpr의 진짜 다시 쓰기다 —
예전에 쓰던 (EVar "x") 식의 생성자-태그 붙은 디버그 형식 없이 항을
출력하도록 열여섯 개의 대안이 교체된다("(EVar " ++ v ++ ")"가
그냥 v가 되는 식이다) — 이는 unify 자신의 오류 메시지가
읽어내는 형식이다
(aux/hindley-milner-gently.md가
unifyR이 그것을 쓰는 대목을 직접 인용한다). 93a2f76e("Allow '()'
and '[]' as uppercase identifiers.", '()'와 '[]'를 대문자 식별자로
허용하기)는 pUIdent에 새로운 대안 두 개를 가르쳐, ()와 []가
튜플/리스트 전용 문장부호로만이 아니라 평범한 생성자 이름으로도
파싱되게 한다(93a2f76e:src/MicroHs/Parse.hs, pUIdent에 추가된
두 줄, 전문 인용):
<|> ("()" <$ (pSym '(' *> pWhite *> pSym ')')) -- Allow () as a constructor name
<|> ("[]" <$ (pSym '[' *> pWhite *> pSym ']')) -- Allow [] as a constructor name
— 이것이 필요한 이유는, 타입이 이제 그냥 Expr이므로 ()나 [a]
같은 타입도 Int나 Maybe와 같은 방식으로 평범한 EVar 생성자
이름(검사기 자신의 어휘로는 tCon "()", tApps "[]" [...])으로
귀결되어야 하는데, 이 커밋 이전에는 ()/[]가 오직 식 구문 안에서만
파싱 가능했고, 타입 적용이 적용할 수 있는 맨 대문자 식별자로는 결코
파싱되지 않았기 때문이다. ca512ed2("Get rid of Data.List_Type",
Data.List_Type 없애기)는 data [] a = [] | (:) a [a]를
lib/Data/List.hs 안으로 곧바로 접어 넣어, 타입 선언만 담고 있던
별도의 Data.List_Type 모듈을 지운다 — 이제 한 모듈 자신의
Data/Sign 정의와 항 수준 바인딩이 검사기가 함께 읽는 같은 EDef
목록에 살고 있으니, 이들을 따로 둘 구조적 이유가 없다. e5bc9236
("Change ELam to abstract just one variable.", ELam이 변수 하나만
추상화하도록 바꾸기)는 ELam [Ident] Expr을 ELam Ident Expr로
좁히면서, 다중 인자 람다를 파싱 시점에 중첩된 단일 인자 람다들로
접는 새 함수 eLams :: [Ident] -> Expr -> Expr를 더한다
(e5bc9236:src/MicroHs/Parse.hs, 전문 인용):
pLam :: P Expr
pLam = eLams <$> (pSymbol "\\" *> esome pLIdent_) <*> (pSymbol "->" *> pExpr)
eLams :: [Ident] -> Expr -> Expr
eLams is e = foldr ELam e is
— 다음 날 추가되는 검사기 자신의 ELam case는 람다마다 정확히
속박 변수 하나를 기대해서 한 번에 정확히 하나의 tArrow와 단일화할
수 있게 한다; 다중 인자 ELam이었다면 대신 그 자체의 다단계
단일화 로직이 필요했을 것이다.
c0b279fc: 어디에도 연결되지 않은 뼈대
c0b279fc("Start of type checking.", 타입 검사의 시작),
2023-07-22 10:50:52는 새 파일 하나, src/MicroHs/TypeCheck.hs
(57줄)를 추가한다 — 그리고 다른 어떤 것도 건드리지 않는다.
Makefile도, Compile.hs도, Main.hs도 아니다. 빌드 안 어디에서도
아직 이것을 임포트하지 않는다. GHC가 그 자체로 받아들일 하스켈조차
아니다: tcExpr의 타입 시그니처는 모나드 T를 언급하지만
(tcExpr :: Maybe EType -> Expr -> T (Typed Expr)), 이 파일의
유일한 임포트는 import Control.Monad.State as T
(c0b279fc:src/MicroHs/TypeCheck.hs 3행)다 — 이는 T.get 같은
이름을 쓸 수 있게 하는 한정 임포트 구문이지, T라는 이름의 맨
타입이 아니다. 몇몇 case는 그냥 undefined다(ECase _ = undefined,
ELet _ = undefined, EDo _ = undefined), 그리고 함수는 정의
도중에 끝나 버린다 — 파일의 마지막 줄은 tc, 뒤에 아무것도 없는
미완의 식별자다. 이는 가장 글자 그대로의 의미에서 첫 초안이다:
검사기의 Expr에 대한 핵심 재귀가 어떤 모양이 될지에 대한 윤곽
(tcExpr, 양방향 검사를 위한 Maybe EType을 가진
EVar/EApp/ELam/EInt 순회이며, 2주 뒤 cc57346e의 동작하는
버전에서 이미 알아볼 수 있는 모양이다)이, 컴파일되기는커녕
실행되기도 전에 커밋된 것이다.
무관한 수정 하나, 그리고 "Transfer"라 불리는 커밋 두 개
7ae8c443("Make int64_t printing portable.", int64_t 출력을
이식성 있게 만들기), 2023-07-22 15:57:15는 파일 하나짜리 런타임
수정 — eval.c의 숫자 포맷팅 — 으로 타입 검사와는 아무 상관이 없다;
c0b279fc와 다음 TypeCheck.hs 작업 사이에 끼어 있기 때문에 여기
실었으며, 이 프로젝트의 git 역사가 한 기능이 진행 중이라고 다른
작업을 멈추지 않는다는 것을 상기시킨다. 그런 다음, 같은 날 저녁
1분 50초 간격으로, 둘 다 "Transfer"라는 제목을 단 3437518f와
031d2125가 오직 src/MicroHs/TypeCheck.hs만 건드린다 — 114줄
변경(74줄 추가, 40줄 삭제), 그다음 6줄 더(4/2). 두 커밋 메시지 모두
무엇이 어디서 옮겨지는지 말하지 않는다; diff로 읽으면 둘 다
c0b279fc가 시작한 같은 뼈대를 단순히 다듬은 것이지(더 많은 case가
채워지고, 더 많은 헬퍼 함수가 추가된다) 전면 교체가 아니다 — diff
자체 이외에 저장소의 무엇으로도 확인되지는 않지만, 다른 어딘가
(두 번째 체크아웃, 다른 기계)에서 초안을 작성한 뒤 병합이 아니라
손으로 옮겨 붙인 작업과 부합한다.
f7db30f1: 3장의 빚을 갚다 — 라이브러리에서
f7db30f1("Add lots of type signatues and forall.", 타입
시그니처와 forall을 잔뜩 추가하기), 2023-07-23 19:28:49는
aux/hindley-milner-gently.md가
자세히 인용하는 커밋이다: 파일 9개, 134줄 추가, 74줄 삭제, forall을
담은 추가 줄 80개, ::를 담은 추가 줄 128개. 정확히 짚어 둘
가치가 있다, 그 모양을 잘못 짚기 쉽기 때문이다: 이 커밋이 건드리는
모든 파일은 lib/ 아래(Data/Either.hs, Data/Function.hs,
Data/Int.hs, Data/List.hs, Data/Map.hs, Data/Maybe.hs,
Data/Tuple.hs, Primitives.hs)와 Makefile이며 — 모든 MicroHs
프로그램(그것을 임포트하는 컴파일러 자신의 src/ 트리를 포함해)이
끌어오는 표준 라이브러리이지, src/MicroHs 자신이 아니다. 그리고
그 128개의 :: 줄 대부분은 완전히 새로운 시그니처가 아니다 —
const :: a -> b -> a는 이미 lib/Data/Function.hs에 있었다;
f7db30f1이 여기에 더하는 것은 앞에 붙는 forall a b .뿐이다.
3장의 e96d04be:Desugar.hs 주석은 "의미는 몇 달 뒤에 도착한다"고
말한다 — f7db30f1은 e96d04be로부터 54일 뒤에 도착하고,
cc57346e의 동작하는 검사기는 그로부터 다시 14일 뒤, 합쳐서
68일이다. f7db30f1에서 먼저 도착하는 것은 "컴파일러가 Sign을
읽는다"가 아니다 — 검사기는 아직 동작하는 기능으로 존재하지 않는다
— 라이브러리가, 검사기의 고정 변수 메커니즘이 언젠가 다형적인
무언가라도 받아들이려면 필요할 정량자를 얻는 것이다. 바로
aux/hindley-milner-gently.md의
forall/인스턴스화 절이 하나를 제거해 보임으로써 보여 주는 것과
정확히 같다.
무관한 커밋 두 개 더, 그중 하나는 조용히 중요한 역할
677a0f0e("Handle negative literals.", 음수 리터럴 처리하기),
2023-07-25 14:58:16은 또 다른 런타임 전용 수정으로, eval.c에
12줄 추가, 1줄 삭제다. 18초 뒤 17b450fc("Add more lib modules.",
라이브러리 모듈 더 추가하기)는 파일 두 개를 완전히 새로 추가한다:
lib/Control/Monad/State.hs(52줄)와 lib/Data/IntMap.hs(77줄).
커밋 메시지는 컴파일러에 왜 IntMap이 필요한지 말하지 않지만,
TypeCheck.hs 자신의 상태 — TCState의 마지막 필드, 단일화 치환
(aux/hindley-milner-gently.md의
"메타변수와 치환" 절) — 은 정확히 IM.IntMap EType이고,
cc57346e의 임포트 목록이 이를 확인해 준다: import qualified Data.IntMap as IM. 17b450fc는 타입 검사 작업이라는 제목을 달고
있지 않지만, 검사기의 핵심 자료 구조를 손 닿는 곳에 두는 커밋이다.
조용한 뚝심: 9a392312부터 617475b6까지
9a392312("Temp commit", 임시 커밋), 2023-07-27 13:47:19은
TypeCheck.hs에 173줄 추가, 26줄 삭제로 손대고, 그 밖에 다른 다섯
파일도 건드린다(Makefile, Compile.hs, Desugar.hs, Main.hs,
Parse.hs) — 그 이전의 어떤 커밋과도 달리, 검사기를 처음으로 빌드에
연결한다. 그 뒤로는 아무 일도 없다가, 9일 21시간 51분 만에
617475b6("Temp", 임시), 2023-08-06 11:38:42가 온다 —
TypeCheck.hs를 다시 한번 다시 쓰는 단일 커밋으로, 이번에는 543줄
추가, 65줄 삭제이며, Desugar.hs의 거의 전면적인 재구성(67줄 추가,
205줄 삭제)을 포함해 총 11개 파일에 걸쳐 있다. 저장소 안 어디에도
그 공백을 설명하는 것은 없다 — 7장의 24일 침묵이
00-overview.md에서 설명되지 않은 채 남는 것과
마찬가지로, 로그는 그저 다시 이어질 뿐이다. 두 커밋의 제목이
공유하는 것 — "Temp commit", "Temp" — 은 정직한 서술이다: 둘 다
끝났다고 주장하지 않으며, 둘 다 깨끗하게 동작하는 상태라기보다는
저장점으로서 커밋되어 있다. 617475b6은 또한 거의 열엿새 전
33b009fa가 남긴 showEType의 무한 루프가 마침내 고쳐지는 지점이기도
하다 — 이 커밋이 건드리는 다른 모든 것과 나란히 놓인 한 줄이다
(617475b6:src/MicroHs/Parse.hs, 전문 인용): showEType = showExpr.
재설계가 아니라, EType이 내내 Expr이었으니 타입 출력기를 (이미
45b34015에서 다시 쓰인) 항 출력기로 그저 돌려 보낸 것뿐이다.
cc57346e: "First version with type checking."(타입 검사가 있는 첫 버전)
617475b6의 다시 쓰기가 도착한 지 7시간 38분 뒤, 같은 날,
cc57346e(2023-08-06 19:16:48)는 이 장과
aux/hindley-milner-gently.md 둘 다
검사기의 첫 진짜 스냅샷으로 다루는 커밋이다: 파일 16개, 187줄 추가,
78줄 삭제. src/MicroHs/TCMonad.hs가 새로 생긴다 — 13줄, 컴파일러
자신의 한정 이름 T 아래 Control.Monad.State.Strict를 얇게
재수출하는 것으로, 마침내 c0b279fc의 2주 묵은, 한 번도 컴파일된
적 없는 타입 시그니처에 가리킬 실체를 준다. 이 커밋 시점의
TypeCheck.hs 자신은
aux/hindley-milner-gently.md가 내내
인용하는 그 파일이다 — unify/unifyR, 메타변수로서의 EUVar,
tInst, tcDefValue, 모두 존재하며 그 문서가 서술하는 모양 그대로다.
이 커밋 시점에 할 수 있는 것: EVar/EApp/ELam/리터럴, ECase,
ELet, ETuple, EList, EDo, EIf, 리스트 컴프리헨션을 검사하는
것이다 — 2주 전 c0b279fc가 undefined로 남겨 두었던 모든 case가
채워져 있다. 그 대가로 요구하는 것은 같은 커밋 자신의 테스트
스위트에서 즉시 드러난다: tests/ 아래 여섯 파일 전부가 예전에는
없던 main :: IO () 시그니처를 얻는다(tests/Arith.hs,
ListTest.hs, StringTest.hs는 각각 그 한 줄만 필요하고;
Fac.hs는 res :: (Int, Int)도 필요하며; IOTest.hs는
f :: Int -> Int와 foo :: IO ()가 필요하고; Misc.hs의 기존
first :: (a, b) -> a는 앞에 forall a b .가 더해져야 한다) —
aux/hindley-milner-gently.md가
lib/Data/List.hs의 null에서 하나를 제거해 보여 주는 바로 그
"모든 최상위 바인딩은 명시적 시그니처가 필요하다"는 규칙이, 검사를
켠 바로 그 커밋에서 프로젝트 자신의 테스트 파일에 그대로 나타난
모습이 이제 눈에 보인다.
수정 연속선
커밋 여섯 개, da5350d2부터 64345fe2까지가, 가운데 온전히
조용한 이틀을 사이에 두고 사흘에 걸쳐 있다 — 2023-08-06(da5350d2
19:31, 3bf3924a 23:56), 2023-08-07(a90d1175 12:21, bb8aec3b
12:22), 8일과 9일은 아무 일도 없다가, 2023-08-10(64345fe2
11:06, 이 장의 마지막 커밋과 같은 날). 함께 읽으면, 이들의
TypeCheck.hs diff 대부분은 새로운 타입 검사 로직이 전혀 아니다 —
aux/bootstrapping-a-compiler.md가
컴파일러의 나머지 부분에 대해 서술하는 것과 같은 "다이어트"를,
가장 최신 모듈에도 적용해서, 이 모듈 역시 GHC뿐 아니라 결국 mhs
자신 아래서도 컴파일될 수 있게 하는 것이다.
da5350d2("Improve.", 개선하기)는 모든 HasCallStack => 제약을
--X 주석 표시 뒤로 감추고, 맨 mapM/mapM_을 한정된
T.mapM/T.mapM_로 바꾼다 — GHC.Stack과 한정되지 않은
Prelude의 mapM은 정확히 mhs 자신의 제한된 방언에는 없는
종류의 임포트다. 3bf3924a("Various type fixes.", 여러 타입 수정)는
같은 패턴을 이어간다: EApp <$> expandType f <*> expandType a 식의
Applicative 코드는 mhs가 제공할 타입 클래스가 없는 <$>/<*>
인스턴스가 필요한데, 이를 명시적인 T.do 바인드로 다시 쓰고, 맨
return/pure를 T.return으로 한정한다. a90d1175("Better
import", 더 나은 임포트)는 TCMonad.hs에서 3줄 추가, 2줄 삭제인
임포트 손질이다. bb8aec3b("More type fixes", 타입 수정 더)는
Parse.hs에서 6줄 추가, 1줄 삭제로, 대부분 살아 있는 코드가 아니라
showExpr을 위한 주석 처리된(--X로 표시된) 프리티 프린터
대안들이다. 64345fe2("More type checking fixes.", 타입 검사 수정
더)는 여섯 중 가장 크다 — TypeCheck.hs 안에서만 163줄이다 —
그리고 제목만 보고 짐작하는 대신 직접 확인해 보면, 단순한 이식성
손질만이 아니라 진짜 정확성 수정도 적어도 하나 담고 있다:
expandSyn이 다중 인자 타입 시노님을 다루는 방식이다. 이 커밋
이전에는 인자 두 개로 쓰인 type Pair a b = (a, b)가 타입 검사를
아예 통과하지 못한다 — cc57346e를 빌드해 그것을 쓰는 한 줄짜리
프로그램을 컴파일해 확인했다: mhs: Cannot unify SynTest.Pair and ,. 64345fe2는 expandSyn의 EApp case를 다시 써서, 잘못된
부분 항으로 재귀하는 대신 각 인자를 누산기에 밀어 넣기 전에
확장하면서 적용 스파인을 올바르게 걷는다
(64345fe2:src/MicroHs/TypeCheck.hs, 전문 인용, 바뀐 case):
EApp f a -> T.do
aa <- expandSyn a
syn (aa:ts) f
— a38c64ce를 빌드하고 동일한 SynTest.hs를 컴파일해 고쳐졌음을
확인했다: 컴파일되고 실행되어 1을 출력한다. 정직한 사실 하나 더,
diff만 읽지 않고 64345fe2 자체를 빌드해 보려다 발견한 것: 이
커밋은 GHC 아래서 단독으로 컴파일되지 않으며, TypeCheck.hs가
T.do 블록 안에서 패턴 매칭을 하는 곳마다 Not in scope: 'T.fail'
/ Not in scope: 'T.>>='로 실패한다. 그 수정은,
aux/bootstrapping-a-compiler.md가
기록하는 --X/--Y 표시 기법으로, a38c64ce 자신의 TCMonad.hs
변경이며, 뒤바뀌던 도중에 붙잡힌 것이다: 64345fe2 시점에는
src/MicroHs/TCMonad.hs 16행이 --X 표시가 없는 평범한 주석
--import Control.Monad로 되어 있어서, convertX.sh가 이를 전혀
건드리지 않고, MicroHs.TCMonad의 module MicroHs.TCMonad 익스포트
항목이 재수출할 fail/(>>=)를 스코프로 들여올 Control.Monad가
GHC 빌드에는 실제로 임포트되지 않는다. a38c64ce는 그 한 줄을
--Ximport Control.Monad hiding(ap)로 바꾸고
(a38c64ce:src/MicroHs/TCMonad.hs 17행) — 이제 표시가 붙어서
convertX.sh의 sed -e 's/--X//'가 표시를 벗겨내고 bin/mhs
빌드는 실제로 import Control.Monad hiding(ap)를 보게 되어,
T.fail/T.>>=가 해소된다. 00-overview.md가 이 프로젝트의 커밋
역사에 대해 짜 놓은 틀 — 깨진 상태도 깨끗해질 때까지 붙들고 있지
않고 그대로 커밋된다 — 과 부합한다.
a38c64ce: 고정점
a38c64ce("Now bootstraps with type checking.", 이제 타입 검사와
함께 부트스트랩한다), 2023-08-10 20:37:30은 파일 7개, 29줄 추가,
24줄 삭제 — 이 책 전체 이야기의 흐름을 닫는 커밋치고는, 이 장의
기준으로는 작다. Makefile 변경은 숫자 하나다: bootcombtest의
eval 호출이 힙을 -H10000000에서 -H50000000으로 키우고, 같은
커밋은 $(MHS)test 타깃(원래 uhstest, 7장의 1d6d1210,
2023-07-05, 8장에서 298c9824가 이름을 바꿈)을 지운다 — 이는
인터프리트 모드 스모크 테스트로, 인자 없는 $(BIN)/$(MHS) -ilib -isrc Main; $(BIN)/eval이며, bootcombtest 자신이 반드시 동작해야
하는 것이 되고 나자 대체된다. TypeCheck.hs에서 중요한 변경은 네
줄로, 모든 최상위 정의 자신의 검사 사이에서 호출되는 새 함수다
(a38c64ce:src/MicroHs/TypeCheck.hs 360–364행, 전문 인용):
-- Reset type variable and unification map
tcReset :: T ()
tcReset = T.do
TC mn _ tenv venv _ <- get
put (TC mn 0 tenv venv IM.empty)
— 모듈의 정의 목록을 걷는 두 호출 지점인 tcDefsType과
tcDefsValue에 연결되며, 둘 다 T.mapM tcDefType ds /
T.mapM tcDefValue ds에서 T.mapM (\ d -> T.do {tcReset; tcDefType d}) ds와 값 검사 쪽의 동등한 형태로 바뀐다. 이 커밋 이전에는 새
메타변수 카운터와 단일화 치환 맵이 모듈 안의 모든 최상위 정의에
걸쳐, 한 번도 비워지지 않은 채 계속 쌓였다; 이 커밋 이후에는 각
정의가 EUVar 0과 빈 치환에서 다시 시작한다. 커밋 메시지는 그
리셋 없이 컴파일러 자신의 ~30개 파일짜리 소스 — 결과로 나오는
mhs.comb에서 직접 센 571개의 서로 다른 최상위 컴비네이터 레이블 —
를 검사하는 것이 실제로 무엇을 했는지 설명하지 않는다 — 단순히
느렸던 것인지, 그보다 더 나쁜 무언가였는지 — 다만 tcReset을
더하는 것이 마침내 동작하게 만든 것이라고 제목이 보고할 뿐이다.
그와 나란히, 범위가 더 좁은 정확성 수정 두 개도 있다: ESectR의
case는 검사된 연산자를 곧바로 EVar ii로 패턴 매칭하던 것이,
평범한 함수가 아니라 데이터 생성자로 만들어진 섹션이면 크래시를
냈다(검사기 자신의 EVar case는 tLookupInst에서 EVar뿐 아니라
ECon cti qi도 반환할 수 있다) — 일반적인 var와 매칭하고
getIdent로 이름을 뽑아내도록 고쳐졌다(a38c64ce:src/MicroHs/TypeCheck.hs
694행: T.return (ESectR (getIdent var) ee, t)). 그리고
primTypes는 새 항목 "Any"를 하나 얻는데, 같은 커밋이
lib/Unsafe/Coerce.hs의 unsafeCoerce :: a -> b에 forall a b .
를 더하기도 한다 — "Any" 프리미티브 타입과 unsafeCoerce의 강제된
전칭 정량화가 함께 도착한다. diff의 나머지 — StateIO.hs에서 이제
둘 다 스코프에 있는 두 return 사이에서 모호했던 맨 return을
MicroHs.StateIO.return으로 한정한 것, Compile.hs에서 한정되지
않은 Handle 임포트를 고친 것, Desugar.hs의 단일 분기 case
처리에서의 대체 분기 손질 — 은 위의 수정 연속선이 이미 이 범위의
지배적인 결이라고 확립해 놓은 것과 같은 셀프 호스팅 호환성 정비다.
이 커밋에서 bootcombtest가 그것을 실행하는 그대로 빌드하고 실행해
보면(아래 "직접 해보기" 참고): bin/mhs가 소스로부터 MicroHs.Main
을 컴파일하고; mhs 자신의 컴비네이터 번역본을 인터프리트하는
bin/eval이 같은 소스를 두 번째로 컴파일하며; 두 출력물은 각각
140,782바이트로 바이트 단위로 동일하다. 타입이 있는 컴파일러가
스스로를 타입 검사하며, 스스로를 컴파일한다.
밝히지 않은 부가 사항
제목이 아니라 diff를 읽어서 찾아낸 세 가지를 여기 모은다:
33b009fa가 (EType의 출력이 아니라 그 표현에 관한 제목 아래서)
조용히 도입하고 617475b6이 거의 열엿새 뒤 조용히 고치는, 그 사이
단 한 번도 실행되지 않는 showEType = showEType 무한 루프;
64345fe2("More type checking fixes.")가 GHC 아래서 단독으로
컴파일되지 않는다는 것으로, 다음 커밋의 메시지를 믿는 대신 직접
빌드해 봐야만 발견되는 사실; 그리고 "Transfer"라 불리는 두 커밋
3437518f/031d2125로, 제목은 무엇이 옮겨지는지 아무것도 말하지
않지만 diff — 114줄과 6줄, 둘 다 TypeCheck.hs에 국한됨 — 는
적어도 자신이 주장하는 바와 부합한다. 제목이 전혀 언급하지 않은
안전 플래그를 떨어뜨린 8장의 8e2f7109와는 다르다. 이 장에서
찾아낸 것 중 그 수준까지 올라가는 것은 없다 — 여기 있는 것은 모두
효과가 제목과 모순되는 것이 아니라, 범위가 분명히 언급되지 않은
것들이다.
왜 중요한가
타입은 가장 마지막에 왔다. 처음도 아니고, 파서와 나란히도 아니고,
do-표기법이나 모듈과 나란히도 아니다 — 언어와 런타임, IO, 셀프
호스팅이 모두 동작한 뒤에, 이미 스스로를 3주 동안 컴파일해 왔고 그
소스 안의 모든 시그니처가 그동안 아무것도 하지 않던 컴파일러 위에서다.
그 순서는 어느 한 프로젝트의 우연이 아니라 이 책이 다루는 방법의
전체 모양이다: 3장의 dsDef (Sign _ _) = []는 두 달 남짓 동안
시그니처를 참이 되게 해야 한다는 어떤 의무도 없이 문서로서 적을 수
있게 해 주었고; 5장의 습관들 — 자주 커밋하기, 무엇이 깨졌는지
적어 두기, 실험 노트를 유지하기 — 은 정확히 9a392312와
617475b6이, 미완성임을 인정하는 제목 아래 아흐레 떨어져 있으면서도
프로젝트가 멎지 않게 해 준 것이며; 8장의 셀프 호스팅 총력전은 이
장에 tcReset이 애초에 필요할 만큼 큰 작업 부하 — 컴파일러 자신의
~30개 파일짜리 소스 — 를 준 것이고, 이는 더 작은 어떤 것으로도
드러나지 않았을 수정이다. 타입 없는 컴파일러는 타입이 있는
컴파일러를 만드는 데서 벗어난 우회로가 아니었다 — 그것은, 누군가
증명해야 하기 전에 이미 동작하던 언어 위에서, 한 번에 작은 커밋
하나씩, 타입이 있는 컴파일러를 만드는 일을 다루기 쉽게 만든
발판이었다. 2023-05-25, 두 파일 Lam.hs와 eval.c. 77일 뒤
2023-08-10, a38c64ce에서, 스스로를 컴파일하며 스스로를 검사하는
셀프 호스팅 타입 컴파일러. 이 기록이 여기서 멈추는 이유는,
00-overview.md가 약속한 이야기가 전부 이야기되었다고
git log가 말해 주는 지점이 바로 여기이기 때문이다: "8월 초까지
이어지는 마지막 구간은 힌들리-밀너 타입 검사기를 더하고 셀프
호스팅 컴파일러가 타입 검사와 함께 부트스트랩하게 만든다..."
실험 노트 여백
- "Temp commit"과 "Temp"는 채우기용 제목이 아니다 — 이들은 일부러
생각 도중에 커밋된 저장점으로, 9일 21시간 51분 떨어져 있으며 그
공백에 대한 설명은 사이에 없다. 이 책이 5장 이래로 추적해 온
습관 — 동작하지 않아도 커밋한다 — 이야말로
617475b6의 608줄짜리TypeCheck.hsdiff 같은 몇 주짜리 다시 쓰기를,9a392312의 199줄짜리 첫 시도를 잃지 않고도 가능하게 만드는 것이다. - 기능보다 리팩터링이 먼저, 다시 한번:
33b009fa/e5bc9236의 준비(타입을Expr로, 변수 하나짜리 람다)는c0b279fc의 실제 검사기 코드 첫 줄보다 꼬박 하루 앞서 도착한다 — 3장의 "실험 노트 여백"이4e4c5252와ff4622e8에 대해 이름 붙였던 것과 같은 리듬이, 이제 파서가 아니라 검사기 자신의 전제 조건들 위에서 한 단계 위 수준으로 작동하고 있다. - 수정 연속선의 리듬: 커밋 여섯 개, 사흘, 가운데 온전히 조용한
이틀(08-08, 08-09) — 그리고 그 연속선의 바로 마지막 커밋인
64345fe2는 단독으로는 빌드조차 되지 않는다. 진짜 버그를 고치는 것(다중 인자 타입 시노님)과 셀프 호스팅 이식성을 고치는 것(한정된T.do바인드, 벗겨낸HasCallStack)이 "정확성" 패스와 "정리" 패스로 나뉘지 않고 같은 커밋들 안에서 함께 일어난다. 17b450fc("Add more lib modules.")는 컴파일러가 왜IntMap을 필요한지 결코 말하지 않는다 —TypeCheck.hs자신의 치환 맵과의 연결은 두 커밋 메시지 어느 쪽에서도 아니라, 두 파일을 모두 읽어야만 읽어낼 수 있다.
직접 해보기
기준점: a38c64ce("Now bootstraps with type checking."),
2023-08-10 20:37:30 — 타입이 있는 셀프 컴파일이 스스로와 일치하게
만드는 커밋이다. 관례(참고:
00-overview.md):
git worktree add /tmp/mhs-a38c64ce a38c64ce
cd /tmp/mhs-a38c64ce
이 커밋 시점에는 빌드 노트 패치가 필요 없다 — 2장, 3장을 비롯한
이 책의 다른 장들이 우회해야 했던 GHC-9.8/mtl 문제들은, 프로젝트의
이 지점에 이르러서는 Main.hs 자신의 임포트 목록에서 사라지고
없다. 두 바이너리를 쓰인 그대로 빌드한다:
mkdir -p bin
nix develop $MICROHS -c make bin/mhs
nix develop $MICROHS -c make bin/eval
[...]
[16 of 16] Linking bin/mhs
gcc -Wall -O3 src/runtime/eval.c -o bin/eval
(이전 모든 장의 빌드 노트가 이미 짚은 같은 -Wx-partial
head/tail 경고가 bin/mhs 빌드 중에도 나타난다; 생략.) 먼저
평범한 테스트 스위트를 실행한다 — tests/*.hs 파일 일곱 개(위의
"무슨 일이 있었나"에서처럼 cc57346e가 main :: IO ()를 추가해야
했던 여섯 개에, 이미 그것이 있던 Case.hs를 더한 것)로, 각각
컴파일되어 그 출력이 저장소에 체크인된 .ref 파일과 diff된다:
nix develop $MICROHS -c make test
cd tests; make test
../bin/mhs -i../lib IOTest && (echo q | ../bin/eval -- a bb ccc > IOTest.out) && diff IOTest.ref IOTest.out
../bin/mhs -i../lib StringTest && ../bin/eval > StringTest.out && diff StringTest.ref StringTest.out
../bin/mhs -i../lib ListTest && ../bin/eval > ListTest.out && diff ListTest.ref ListTest.out
../bin/mhs -i../lib Fac && ../bin/eval > Fac.out && diff Fac.ref Fac.out
../bin/mhs -i../lib Misc && ../bin/eval > Misc.out && diff Misc.ref Misc.out
../bin/mhs -i../lib Case && ../bin/eval > Case.out && diff Case.ref Case.out
../bin/mhs -i../lib Arith && ../bin/eval > Arith.out && diff Arith.ref Arith.out
위의 diff는 모두 조용하다 — 일곱 개 전부 통과한다. 이제 핵심
장면, 8장의 "직접 해보기"가 타입 검사 없이 실행했던 그 동일한
bootcombtest 타깃이다 — 먼저 make bootcombtest 전체를, 그다음
8장 자신의 "직접 해보기"가 하듯 세 줄 각각의 시간을 따로 잰다:
nix develop $MICROHS -c bash -c 'time make bootcombtest'
bin/mhs -ilib -isrc -omhs.comb MicroHs.Main
bin/mhs -ilib -isrc -omain-mhs.comb MicroHs.Main
bin/eval -H50000000 -rmhs.comb -- -ilib -isrc -omain-comb.comb MicroHs.Main
cmp main-mhs.comb main-comb.comb
real 0m37.674s
nix develop $MICROHS -c bash -c 'time bin/mhs -ilib -isrc -omain-mhs.comb MicroHs.Main'
real 0m1.794s
nix develop $MICROHS -c bash -c 'time bin/eval -H50000000 -rmhs.comb -- -ilib -isrc -omain-comb.comb MicroHs.Main'
real 0m32.254s
cmp는 아무것도 출력하지 않고 종료 코드 0으로 끝난다:
main-mhs.comb와 main-comb.comb — 각각 140,782바이트, ls -la와
두 번째 명시적 cmp 실행으로 확인함 — 은 바이트 단위로 동일하다.
이 장 자신의 출발점인 298c9824에서의 8장 자신의 수치(75,052바이트
출력물, 네이티브 0.890초 / 인터프리트 20.715초, 타입 검사 전혀
없음)와 비교하면: 타입이 있는 컴파일러의 셀프 컴파일 출력물은
거의 두 배 크고, 네이티브 컴파일은 약 두 배 느리며(1.794초),
인터프리트 단계는 약 55% 느리다(32.254초) — 그리고 이제 그 출력물의
모든 바이트가 도중에 unify를 거쳤다. 8장이 확립한 것과 같은
컴비네이터 수준 오라클이, 이제 8장이 증명할 수 없었던 것을
증명한다: 타입이 없는 컴파일러가 그런다는 것뿐 아니라, 타입
검사기가 자신의 소스에 대해 스스로와 일치한다는 것이다.
연습 문제 1: 의도적인 타입 오류를 원인까지 추적하기
cat > TypeErr.hs <<'EOF'
module TypeErr(module TypeErr) where
import Prelude
bad :: Int
bad = 1 + "hello"
main :: IO ()
main = putStrLn (showInt bad)
EOF
nix develop $MICROHS -c ./bin/mhs -ilib TypeErr
mhs: Cannot unify [Char] and Primitives.Int
EApp (EVar "Data.List.[]") (EVar "Primitives.Char") - EVar "Primitives.Int"
Map [("Data.Char.String",ETypeScheme [] (EApp (EVar "Data.List.[]") (EVar "Primitives.Char")))]
CallStack (from HasCallStack):
error, called at src/MicroHs/TypeCheck.hs:334:11 in main:MicroHs.TypeCheck
unifyR, called at src/MicroHs/TypeCheck.hs:326:3 in main:MicroHs.TypeCheck
...
(종료 코드 1; 위에서 CallStack의 나머지 — + 자신의 두 인자
검사에서 나오는 더 많은 unify/unifyR 프레임들 — 은 생략했다.)
이 메시지는 unifyR의 bad 바인딩에서 나온다
(a38c64ce:src/MicroHs/TypeCheck.hs 334행, 인용): bad = error $ "Cannot unify " ++ showExpr a ++ " and " ++ showExpr b ++ "\n".
1 + "hello"는 "hello"의 타입인 [Char](String은 그것의 타입
시노님이라, Map 줄이 Data.Char.String이라는 이름을 담고 있다)가,
+의 두 번째 인자 타입인 Int와 단일화되기를 요구하는데 —
unifyR의 구조적 case가 곧바로 거부하는 EApp/EVar 불일치이며,
aux/hindley-milner-gently.md의 단일화
절이 손으로 추적하는 것과 정확히 같다.
연습 문제 2: 검사기에 필요한 시그니처 지우기
(python3는 여기서도 devShell이 아니라 호스트 시스템에서 오는
것이다 — 1장이 diff에 대해 밝힌 것과 같은 주의 사항이다.)
python3 -c "
with open('lib/Data/List.hs') as f:
lines = f.readlines()
out = [l for l in lines if l.strip() != 'null :: forall a . [a] -> Bool']
with open('lib/Data/List.hs', 'w') as f:
f.writelines(out)
"
nix develop $MICROHS -c ./bin/mhs -ilib Example
mhs: undefined variable null
CallStack (from HasCallStack):
error, called at src/MicroHs/TypeCheck.hs:382:16 in main:MicroHs.TypeCheck
추론은 대처하지 못한다 — 누락된 최상위 시그니처가 기댈 만한 추론
단계가 없다. addValueType(a38c64ce:src/MicroHs/TypeCheck.hs
553–559행)은 Sign을 볼 때만 값 테이블에 이름을 추가한다; 같은
모듈 안에 대응하는 Sign이 없는 Fcn은 결코 하나를 얻지 못하고,
그 이름에 대한 tcDefValue의 tLookup i는 곧장 "찾지 못함" 분기로
떨어진다 — null이 Example.hs 안 어디에서도 호출되지 않더라도,
무언가가 그것을 임포트하는 순간 lib/Data/List.hs 자신은 여전히
모듈 전체로서 타입 검사를 받아야 하고, 쓰이든 안 쓰이든 그 안의
최상위 바인딩 하나하나가 검사를 받으려면 자신의 시그니처가 있어야
한다. 계속하기 전에 파일을 되돌린다:
git checkout -- lib/Data/List.hs
연습 문제 3: 프렐류드 함수를 손으로 추론한 뒤 소스와 대조하기
lib/Data/Function.hs, flip:
flip :: forall a b c . (b -> a -> c) -> a -> b -> c
flip f a b = f b a
검사기 자신의 알고리즘에 맞춰 flip f a b = f b a의 본문을 손으로
추론해 본다(tcExpr'의 EApp case: g x를 검사하려면, 먼저 x를
기대 타입 없이 검사한 다음, g를 (x의 타입) -> (새 결과)에 대해
검사한다):
f b a는EApp (EApp f b) a다. 바깥 적용을 검사하면:a(인자)가 먼저 타입을 얻는다 — 람다로 속박된 변수이므로, 그 타입은flip자신의ELamcase가a를 속박할 때 준 새 메타변수다; 이를τ_a라 하자. 식 전체의 결과도 새 메타변수τ_r을 얻는다. 그런 다음f b가 기대 타입τ_a -> τ_r에 대해 검사된다.f b자신은EApp f b다.b의 타입은 그 자신의 바인딩의 메타변수τ_b다.f는τ_b -> (τ_a -> τ_r)에 대해 검사된다.f역시 속박 변수이며,flip의 가장 바깥ELam에서 온 자신의 메타변수τ_f를 가진다;τ_f를τ_b -> (τ_a -> τ_r)에 대해 단일화하면 곧바로 이를 결정짓는다(f의 타입은 바로τ_b -> τ_a -> τ_r이며, 더 검사할 것이 남지 않는다).- 풀어내면:
flip의 구성된 타입은τ_f -> τ_a -> τ_b -> τ_r이고, 2단계의 결과를τ_f에 대입하면:(τ_b -> τ_a -> τ_r) -> τ_a -> τ_b -> τ_r. 선언된(b -> a -> c) -> a -> b -> c와 단일화하면:τ_b ↦ b,τ_a ↦ a,τ_r ↦ c, 모든 메타변수가 정확히 시그니처 자신의 이름들로 풀리며 모순이 없다 — aux/hindley-milner-gently.md의const에 대한 손 풀이가 끝나는 것과 같은 모양이다.
소스와 대조하면: a38c64ce:lib/Data/Function.hs 자신의 flip
시그니처는 정확히 forall a b c . (b -> a -> c) -> a -> b -> c로,
위에서 손으로 추론한 타입과 항 단위로 일치한다. 눈으로 확인하는
데 그치지 않고, 구체적인 타입에서 그것을 쓰는 프로그램으로 실제로
확인했다:
cat > FlipDemo.hs <<'EOF'
module FlipDemo(module FlipDemo) where
import Prelude
main :: IO ()
main = putStrLn (showInt (flip (-) 3 10))
EOF
nix develop $MICROHS -c ./bin/mhs -ilib FlipDemo
nix develop $MICROHS -c ./bin/eval
7
(flip (-) 3 10 = (-) 10 3 = 7, b ↦ Int, a ↦ Int, c ↦ Int
모두 여기서는 같은 구체적 타입으로 인스턴스화되며, 그래서 이 호출
하나만으로는 flip의 타입이 단형적인 것과 구별되지 않는다 — 위
손 추적의 요점은, 검사기가 미리 그것을 알 필요가 전혀 없었다는
것이다.)
정리한다:
git worktree remove --force /tmp/mhs-a38c64ce