03 — Growing the language (언어 키우기)
현재 위치
2장은 파일에서 작은 람다 언어 하나를 읽어 들이는 컴파일러를 남긴다:
모듈, 함수 정의, data 선언, case 식, 정수 리터럴, 적용, \x. expr
람다, 이 모두를 ParserComb.hs/Parse.hs 컴비네이터 라이브러리
(aux/parser-combinators.md)가 파싱하고,
Desugar.hs가 Exp.hs의 작은 컴비네이터 코어로 디슈가하며, eval.c가
실행한다. 모든 최상위 정의는 17587b2d가 인정한 임시방편으로 프로그램
하나에 링크된다: 소스 순서가 레이블 번호가 되고, 자신의 레이블이
출력되기 전에 쓰인 이름은 C 런타임을 ERR: shared == NIL로 멎게 한다.
이 장의 범위, b56ba28b..95ff6a34는 열두 개의 커밋이다 — 아홉 개는
2023-05-30 한 자리에서 도착하고, 나머지 세 개는 다음 작업 세션인
2023-06-01에 도착한다 — 이 최소한의 언어를 let, 중위 연산자, 튜플,
리스트, 문자, 문자열, 모듈 임포트, do 표기법을 갖춘 언어로 키워
낸다.
무슨 일이 있었나
5ccb1b2a: 주석, let, error
한 커밋 안에 서로 무관한 기능 세 개가 들어 있는데, 각각이 값싸서
"이렇게 값쌀 때는 무관한 것들이 함께 도착한다"는 것 자체가 눈여겨볼
만하다. 주석은 파서가 텍스트를 보기 전에 처리된다, 파서 안이 아니라:
parseDie는 이제 소스 문자열 전체에 대해 먼저 removeComments file을
실행하고(5ccb1b2a:Parse.hs 84행), removeComments는 "..." 문자열
리터럴 안쪽은 건드리지 않으면서 --부터 줄 끝까지를 지우는 줄 단위
패스다(5ccb1b2a:Parse.hs, 90–98행, 전문 인용):
removeComments :: String -> String
removeComments = unlines . map remCom . lines
where remCom ('-':'-':_) = ""
remCom ('"':cs) = str cs
remCom (c:cs) = c : remCom cs
remCom "" = ""
str ('"':cs) = remCom cs
str ('\\':_:cs) = str cs
str (_:cs) = str cs
str "" = ""
(문자열 리터럴은 아직 파싱 가능한 구문이 아니지만 — 그것은 일곱
커밋 뒤의 ddb1bb29다 — 주석 제거는 이미 인용된 --를 피해 가서 줄
나머지를 먹어치우지 않도록 우회해야 한다.) let은 새 식 형태
ELet [Def] Expr이며, 중첩된, 재귀하지 않는 람다 적용으로 디슈가된다 —
케이스 위의 주석이 말하듯 "그저 순차적인 바인딩"이다
(5ccb1b2a:Desugar.hs 33행, 주석 포함 인용):
-- For now, just sequential bindings.
dsExpr (ELet ds e) =
let ds' = concatMap dsDef ds
e' = dsExpr e
def (i, d) e = App (Lam i e) d
in foldr def e' ds'
let x = a; y = b in e는 (\x -> (\y -> e) b) a가 된다 — 각 바인딩은
소스 순서대로 그 안쪽을 감싸는 App (Lam ...) 하나씩으로 컴파일되며,
letrec 식의 자기 참조나 상호 재귀 지원은 전혀 없다(나중 장의
문제다). error는 새 구문 형태가 아니다 — +나 <와 같은 방식으로
도달하는 새 eval.c 프리미티브이지만, 자신의 인자를 강제 평가하고
stderr에 출력한 뒤 종료한다는 점이 다르다(5ccb1b2a:eval.c, 661–667행,
전문 인용):
case ERROR:
x = ARG(TOP(1));
x = evali(x);
fprintf(stderr, "error: ");
print(stderr, x);
fprintf(stderr, "\n");
exit(1);
3aa12deb: 중위 연산자, 그리고 여기서 결합성과 우선순위가 실제로 동작하는 방식
이 커밋 이전에는 pExpr이 pExprApp(순수 적용), pLam, pCase,
pLet만 알았다 — +나 ==처럼 이항 연산자를 담은 식은 괄호로 감싼
전위 식별자로 쓰는 것 말고는 표현할 방법이 없었다, (+) x y처럼.
3aa12deb는 새 대안 pExprOp를 추가하는데, 이것이 이 커밋 시점의
결합성/우선순위 메커니즘 전부이며, 전문 인용이다
(3aa12deb:Parse.hs, 203–212행):
pExprOp :: P Expr
pExprOp = pA
where
pA = pRightAssoc (pOpers ["$"]) pB
pB = pRightAssoc (pOpers ["||"]) pC
pC = pRightAssoc (pOpers ["&&"]) pD
pD = pNonAssoc (pOpers ["==", "/=", "<", "<=", ">", ">="]) pE
pE = pLeftAssoc (pOpers ["+", "-"]) pF
pF = pLeftAssoc (pOpers ["*", "quot", "rem"]) pG
pG = pExprApp
이 언어 어디에도 결합성/우선순위 선언은 없다. 소스에서 읽어 들이는
표는 없고, 사용자 프로그램이 영향을 줄 수 있는 것도 없다. 우선순위는
문자 그대로 이 고정된 사슬 안에서 파서의 위치다 — pA는 pB보다
느슨하게 묶이고, pB는 pC보다 느슨하고, 이런 식으로 가장 강하게
묶이는 순수 함수 적용인 pG까지 내려간다. 결합성은 어떤 단계를 세
컴비네이터 함수 pRightAssoc, pNonAssoc, pLeftAssoc 중 어느 것이
감싸는지에 달렸다 — 각각 자신의 피연산자 파서를 한 번 파싱한 다음,
자기 자신을 재귀 호출하거나(우결합), 더 이상 이어지지 않고 정확히
피연산자 하나만 더 받거나(비결합 — 이 단계에서는 ==가 연달아
나오면 파스 오류다), (op, operand) 쌍의 평평한 리스트에 대해 왼쪽으로
접거나(좌결합) 한다 — pLeftAssoc, 전문 인용
(3aa12deb:Parse.hs, 235–239행):
pLeftAssoc :: P String -> P Expr -> P Expr
pLeftAssoc pOp p = do
e1 <- p
es <- emany ((,) <$> pOp <*> p)
pure $ foldl (\ x (op, y) -> appOp op x y) e1 es
연산자 토큰 열네 개가 이 여섯 단계 어딘가에 자리를 얻는다($, ||,
&&, 비교 연산자 여섯 개, +/-, */quot/rem), 그리고 이 여섯
목록 어디에도 없는 연산자는 아직 유효한 중위 연산자가 아니다 — 이
커밋 시점에 a ++ b를 쓰면 파스 오류이며, ++는 e96d04be가 비교
단계와 +/- 단계 사이에 새 단계를 끼워 넣기 전까지는(:도 함께)
등장하지 않는다. 조악하다 — 우선순위가 파서 자신의 호출 그래프에
그대로 박혀 있어서, 새 우선순위에 연산자를 추가하려면 그 사슬에
상호 재귀하는 pN 함수 하나를 새로 끼워 넣고 다른 것은 아무것도
다시 번호 매기지 않으면 된다 — 정확히 13분 뒤 e96d04be가 하는
일이다(p0부터 p10까지, 여섯 개의 문자 단계 대신 열한 개의 번호
붙은 단계, ->, :, ++, .이 추가된다). 하지만 이것으로 동작하며,
이것이 메커니즘 전부다: 연산자 표도, 사용자가 확장 가능한 결합성도
없이, 그저 손으로 쓴 파서 사다리 하나뿐이다.
e96d04be: 타입 시그니처, 파싱은 되지만 버려진다
연산자 사다리를 넓히는 것과 같은 커밋이 f :: T를 파싱 가능한 구문으로
추가한다 — 그리고 그 외에는 아무것도 하지 않는다. 새 Def 케이스인
Sign Ident Type(e96d04be:Parse.hs 19행)은 pDef의 다른 모든 대안과
같은 방식으로 만들어진다(e96d04be:Parse.hs 178행):
<|> Sign <$> (pLIdent <* pSymbol "::") <*> pType
pType은 특기할 만하게도 별도의 문법이 전혀 아니다 — 다른 이름을 쓴
pExpr일 뿐이다(e96d04be:Parse.hs, 183–184행, 전문 인용):
pType :: P Type
pType = pExpr
타입 시그니처는 마치 평범한 식인 것처럼 파싱된다 — Type은 Expr의
타입 동의어다 — 아직 재사용할 별도의 타입 구문 문법이 없기 때문이고,
e96d04be가 방금 넓힌 중위 사슬이 이미 가장 느슨한 단계(p0)에 ->를
포함하고 있어서, T -> T 시그니처가 파싱되는 데 필요한 것을 마침
갖추고 있다. 그리고 디슈가러는 그것을 한 줄로 그냥 바닥에 버린다,
처리의 전부다(e96d04be:Desugar.hs 24행):
dsDef (Sign _ _) = []
dsDef는 각 Def에 대해 컴파일된 정의들의 리스트를 반환한다;
Sign은 그중 0개를 내놓는다. 이것은 "파싱하고 무시하기"다: 타입
시그니처를 쓰는 소스 파일이 파싱에 실패하지 않도록 지금 당장 구문을
받아들이되, 그 의미에는 아직 아무것도 걸지 않는다. 그 의미는 몇 달
뒤에 도착한다 — 9장이 마침내 Sign이 버리지 않고 담아 두는 것을
읽어내는 타입 검사기를 다룬다 — 하지만 e96d04be 이후로는, 그 사이의
모든 커밋이 아무 일도 하지 않는 타입 시그니처를 담은 코드를 자유롭게
쓰고 배포할 수 있다.
어떤 기능 커밋이든 같은 모양: 튜플, 리스트, 문자열
연달아 커밋 세 개가 같은 레시피를 보여 준다 — 새 Expr 생성자 하나,
그것을 만드는 pAExpr 대안 하나, 그리고 그것을 기존 컴비네이터 코어가
이미 이해하는 무언가로 재작성하는 dsExpr 케이스 하나.
튜플(8939d55b)은 괄호 안에 콤마로 구분된 목록으로 파싱되고,
스콧 인코딩된 연속체 전달 함수로 디슈가된다 — 2장의
a9178695:Desugar.hs가 data 생성자에 썼던 것과 같은 트릭을, 이번에는
내장 튜플 형태를 위해 손으로 만든 것이다(8939d55b:Parse.hs,
197–200행, 전문 인용):
eTuple :: [Expr] -> Expr
eTuple [] = ELam "_x" (EVar "_x") -- encoding of ()
eTuple [e] = e
eTuple es = ELam "_f" $ foldl EApp (EVar "_f") es
쌍 (a, b)는 \f -> f a b가 된다 — 자기 자신의 소거자(eliminator)이며
연속체를 기다리는 값이다. 이 모양이 흔해서, 같은 커밋이 브래킷 추상화
스마트 생성자에게 이를 알아보고 호출 지점에서 S/K/C로 만드는
대신 바로 2장의 b56ba28b가 eval.c에 추가한 P(pair) 컴비네이터로
축약하도록 가르친다(8939d55b:Exp.hs 95행, cC에 추가된 한 줄):
cC (App2 CC CI e1) e2 = App2 CP e1 e2
리스트 구문(d91b9812)은 더 작다 — [e1, e2, ...]에 대한 파서
대안 하나, 그리고 b56ba28b의 O 컴비네이터와 기존 K를 써서 중첩된
cons/nil로 바로 이어지는 두 줄짜리 디슈가링뿐이다
(d91b9812:Desugar.hs, 39–40행, 전문 인용):
dsExpr (EList es) =
foldr (App2 CO) CK $ map dsExpr es
[1,2,3]은 O 1 (O 2 (O 3 K))가 된다. 새 런타임 프리미티브는 필요
없다: O 자신의 축약 규칙(redOne (App4 (Comb "O") x1 x2 f1 f2) = Just $ App2 f2 x1 x2, 2장 b56ba28b:Exp.hs 184행)은 두 개의 연속체 —
nil 갈래와 cons 갈래 — 를 그 순서대로 받는데, K a b = a는 정확히
그 두 연속체가 주어졌을 때 언제나 첫 번째(nil 갈래)를 고르는 함수이며,
이것이 바로 CK 혼자서도 유효한 빈 리스트가 되는 이유다: 스콧
인코딩된 []는 자신의 cons 연속체를 무시하고 nil 연속체를 반환하는
값이고, K는 부분 적용된 상태로 정확히 그 일을 한다.
문자열 리터럴(ddb1bb29)은 리스트 단계에서 자기만의 디슈가링
규칙조차 필요 없다 — 문자열은 문자 리스트로 정의되어, 이미 존재하는
리스트 디슈가링 케이스에 곧바로 넘겨진다(ddb1bb29:Desugar.hs 47행,
전문 인용):
dsExpr (EStr cs) = dsExpr $ EList $ map EChar cs
두 커밋 앞선 60cd285c가 이미 이 삼총사 중 유일하게 진짜 작업이
필요했던 부분을 해 두었다: 문자 리터럴에는 실제로 새 런타임
프리미티브가 필요한데, Char가 eval.c 안에 이미 있는 것으로는
표현할 수 없기 때문이다 — 새 CHAR 노드 태그가 INT 바로 뒤에
enum node_tag에 합류하고(60cd285c:eval.c 18행), 파서는 스트림에서
바이트 하나를 그대로 읽어 CHAR 노드로 만드는 case '\''를
얻으며(60cd285c:eval.c 321–325행), eval의 축약 루프는 CHAR를
이미 INT를 다루던 것과 똑같이 비활성 값으로 다룬다 — case CHAR:
절 전체가 그냥 RET;이고, 바로 위 INT의 절과 똑같다, 축약 규칙
없이, 그저 "이것은 이미 값이다"일 뿐이다(60cd285c:eval.c, 508–511행).
이 바탕이 마련되고 나면 EStr은 공짜다: 문자열은 Chr의 리스트이고,
EList의 디슈가링과 O/K의 런타임 동작 둘 다 이미 그것들을 실어
나를 준비가 되어 있다.
4e4c5252("Refactor.", 리팩터링, 리스트 구문과 문자 리터럴 커밋
사이)는 기능이 아니다: 튜플과 리스트가 추가되면서 하나씩 덧붙여져
pLHS pUIdent/튜플/[]/:-중위 분기로 임기응변으로 자라난
case-패턴 파싱이, 하나의 Pat 타입(PConstr Ident [Ident] | PTuple [Ident])으로 뽑혀 들어가고 dsExpr의 ECase 절이 이를 매치하도록
다시 쓰이는 순간이다. 파싱되는 것은 아무것도 바뀌지 않는다; 바뀌는
것은 네 개의 임기응변 패턴 모양이 이제 네 개의 따로 꿰인 튜플 대신
하나의 표현을 공유한다는 것이다. 이것이 이 장 나머지가 계속 되풀이하는
리듬의 첫 사례다: 기능, 기능, 리팩터링 — 쌓인 지저분함을 미리가 아니라
정리할 만큼 쌓인 뒤에야 청소한다.
b25d9fc8: 모듈 임포트하기
이 범위에서 가장 큰 커밋이다 — 새 파일 Compile.hs, 91줄 — 여기서
"모듈"이 뜻하는 바는 "파싱하고 무시하기"보다 훨씬 더 실질적이다:
모듈은 파일 <Name>.uhs이며, 그 자신이 선언한 모듈 이름은 그것이
로드된 파일 이름과 일치해야 한다(b25d9fc8:Compile.hs, 40–45행,
전문 인용):
compileModule :: IdentModule -> StateT Cache IO CModule
compileModule nm = do
let fn = nm ++ ".uhs"
mdl@(Module nm' defs) <- parseDie pTop fn <$> liftIO (readFile fn)
when (nm /= nm') $
error $ "module name does not agree with file name: " ++ show nm
import M(새 Def 케이스, pDef에서 data/import의 이웃과 한
키워드 차이)은 M에 대해 compileModuleCached를 촉발하는데, 이는
어떤 작업이든 시작하기 전에 이미 컴파일된 모듈들의 Map을 확인하고,
현재 컴파일 중인 모듈들의 working 목록을 추적해서 (전이적으로) 자기
자신을 임포트하는 모듈은 무한 루프가 아니라 강한 오류가 되도록 한다
(b25d9fc8:Compile.hs, 24–38행) — 조악한 임시방편이 아니라 진짜 순환
탐지다. 모듈이 정의하는 최상위 이름 하나하나는 그 모듈 자신의 심볼
테이블 안에서 두 가지 표기로 보인다: 비한정(i)과 점 붙은
(mn ++ "." ++ i) — 둘 다 같은 한정된 Var를 가리킨다
(b25d9fc8:Compile.hs 53행, 전문 인용):
syms (mn, ds) = [ (s, [Var qi]) | (i, _) <- ds, let qi = mn ++ "." ++ i, s <- [i, qi] ]
이것이 바로 임포트된 두 모듈이 같은 비한정 이름을 정의하는 것이
임포트 시점이 아니라 참조 시점에 잡히는 모호성 오류인 이유다
(checkExpr의 Just qis -> error $ "ambiguous: " ++ ...,
17587b2d에서 바뀌지 않음). 2장의 "직접 해보기"가 정면으로 부딪혔던
빈틈 하나를 조용히 메우는, 같은 커밋에 함께 들어간 더 작은 수정도
있다: 17587b2d의 레이블 형식은 정의의 :N이 그것에 대한 어떤
_N 참조보다도 출력 텍스트에 먼저 나타나야 했으므로, 호출하는 함수보다
텍스트상 먼저 나오는 main은 C 런타임을 ERR: shared == NIL로 멎게
했다. b25d9fc8:eval.c는 어느 쪽이 먼저 보이든 _ 케이스가 자리표시자가
이미 존재하기를 요구하는 대신, _와 : 케이스 둘 다 조건 없이 간접
자리표시자를 할당하도록 만든다(b25d9fc8:eval.c, 336–343행, 전문 인용):
case '_' :
l = (int)parse_int(f); /* The label */
if (shared[l] == NIL) {
/* Not yet defined, so make it an indirection */
shared[l] = alloc_node(IND);
INDIR(shared[l]) = NIL;
}
return shared[l];
이제 링크된 프로그램 하나 안에서 전방 참조가 그냥 동작한다 —
17587b2d의 링킹 임시방편이 다시 설계되어서가 아니라, 그 밑에 있는
레이블 형식이 빠져 있던 순서 독립성 한 조각을 갖추게 되었기
때문이다.
ff4622e8와 693dc6ce: 또 한 번의 리팩터링, 그다음 do 표기법
ff4622e8("Refactor ident parsing.", 식별자 파싱 리팩터링)는 기능-기능-
리팩터링 리듬의 두 번째 사례다: 따로 정의되어 있던 식별자 파서 세 개
(소문자, 대문자, "식별자의 나머지"를 위한 임기응변 문자 집합)가 하나의
pWord/pIdent 쌍과, .로 구분된 조각들을 이어 붙이는 새
pQIdent로 통합된다 — M.name, 즉 한정 참조가 이제 표현 가능해지고,
693dc6ce가 22초 뒤 곧바로 이를 필요로 한다. do 표기법은 Monad
타입 클래스로 디스패치하지 않는다 — 아직 그런 것은 없다 — 대신 호출
지점에 명시적으로 적힌 한정자로 디스패치한다: pDo는
<Uident>.do { ... }를 파싱하고, 그 식별자는 디슈가된 모든 바인드의
연산자 이름 접두어로 실어 날라진다(ff4622e8:Parse.hs, 359–372행,
전문 인용):
pDo :: P Expr
pDo = EDo <$> pQualDo <*> pBlock pStmt
pStmt :: P Stmt
pStmt =
(Bind <$> (pLIdent <* pSymbol "<-") <*> pExpr )
<|> (Then <$> pExpr)
pQualDo :: P String
pQualDo = do
s <- pUIdent
_ <- char '.'
pKeyword' "do"
pure s
디슈가링, 693dc6ce:Desugar.hs의 새 줄 전부(49–53행, 전문 인용):
dsExpr (EDo _ []) = error "empty do"
dsExpr (EDo _ [Bind _ _]) = error "do without final expression"
dsExpr (EDo _ [Then e]) = dsExpr e
dsExpr (EDo n (Bind i e : ss)) = App2 (Var (n ++ ".>>=")) (dsExpr e) (Lam i $ dsExpr (EDo n ss))
dsExpr (EDo n (Then e : ss)) = App2 (Var (n ++ ".>>")) (dsExpr e) (dsExpr (EDo n ss))
M.do { x <- e; rest }는 (M.>>=) e (\x -> rest')가 되고, 여기서
rest'는 rest를 같은 방식으로 재귀적으로 디슈가한 것이다(문장이
하나 넘게 남아 있으면 여전히 M.do 블록으로서); M.do { e; rest }는
같은 방식으로 (M.>>) e rest'가 된다 — 교과서적인 do 디슈가링이지만,
M.>>=와 M.>>는 타입 클래스 장치를 전혀 거치지 않고 다른 한정된
이름과 마찬가지로 심볼 테이블에서 그냥 찾아질 뿐이다. (>>=)와
(>>)를 정의하는 모듈이 무엇이든, 그 모듈 자신의 이름이 do 표기법을
여는 한정자다 — 이 커밋 시점에는 IO가 그것이며, Compile.hs의
여전히 하드코딩된 primOps 목록에 두 항목으로 배선되어 있지만
(693dc6ce:Compile.hs 78–79행: ("IO.>>=", Prim "IO.>>="),
("IO.>>", Prim "IO.>>")), pQualDo나 dsExpr의 EDo 케이스
어디에도 IO에 특화된 것은 없다 — 자신만의 (>>=)/(>>)를 정의하는
어떤 모듈이든 IO 모나드든 아니든 상관없이 자기만의 쓸 수 있는 do
블록을 공짜로 얻는다("직접 해보기" 연습 문제 1은 정확히 이것을
이용해 IO를 전혀 건드리지 않고 do 표기법을 실행한다).
95ff6a34: primitive, 그리고 컴파일러를 런타임에서 떼어내기
이 커밋 이전의 모든 런타임 프리미티브는 Compile.hs의 primOps
목록에 하드코딩된 항목이다 — 손으로 관리되는, 프리미티브 하나당
하스켈 소스 한 줄이며, 새 연산자가 런타임 대응물을 필요로 할 때마다
늘어난다. 95ff6a34는 그 목록을 통째로 지우고, 아무 모듈이나 자신만의
프리미티브 바인딩을 스스로 적어 넣을 수 있게 해 주는 새 식 형태로
대체한다: primitive "tag"가 새 파싱 가능한 구문이다
(95ff6a34:Parse.hs 291행, pAExpr에 추가된 대안 하나):
<|> (EPrim <$> (pKeyword "primitive" *> pString))
그리고 매핑이 얼마나 기계적인지 그대로 보여 주듯, 옛 표가 손으로
만들어 주던 것과 정확히 같은 Exp.hs 생성자로 디슈가된다
(95ff6a34:Desugar.hs 54행, 전문 인용):
dsExpr (EPrim s) = Prim s
새 소스 파일 세 개가 같은 커밋에 함께 도착한다 — Prelude.uhs,
IO.uhs, List.uhs(List 데이터 선언과 map, primitive와는
무관하다). Prelude.uhs와 IO.uhs는 처음부터 끝까지 우변이 primitive "..."인 최상위 바인딩뿐이다 — (+) = primitive "+", error = primitive "?", (>>=) = primitive "IO.>>=", readFile = primitive "IO.readFile" 등등. 예전에는 런타임 프리미티브 하나를 추가하려면
Compile.hs(컴파일러 내부의 하스켈 소스 파일)를 편집해야 했지만,
이제는 .uhs 모듈(평범한 프로그램 소스 파일)에 한 줄만 쓰면 된다 —
primitive "..." 안의 문자열만이 eval.c가 실제로 이해하는 것과
일치해야 할 뿐이고, 컴파일러 자신은 이제 런타임의 컴비네이터 어휘를
전혀 몰라도 된다. Exp.hs의 flipOps 표(브래킷 추상화 스마트 생성자
cC가 "이 비교를 C 컴비네이터로 감싸는 대신 뒤집어라"를 알아보는
데 쓰임)도 같은 커밋에서 프리미티브 이름이 하드코딩된 순수 문자열
목록 대신 진짜 모듈 안에 살게 된 것의 작고 정직한 부작용으로
"Prelude.+", "Prelude.<" 등으로 다시 한정된다(95ff6a34:Exp.hs,
115–124행).
왜 중요한가
이 커밋들 각각이 실제로 치르는 비용을 보자. dsDef (Sign _ _) = []는
한 줄이다. dsExpr (EStr cs) = dsExpr $ EList $ map EChar cs는 한
줄이고 런타임에 새 케이스를 도입하지도 않는다 — 그저 이미 존재하는
디슈가링을 거칠 뿐이다. dsExpr (EList es) = foldr (App2 CO) CK $ map dsExpr es도 새 컴비네이터가 필요 없는데, O와 K가 이미 2장부터
eval.c에 앉아 있었기 때문이다. 그것이 런타임에 닿기 전에 모든 것을
한 줌의 SKI류 컴비네이터로 컴파일해 두는 것의 대가다: 대부분의 새
표면 구문은 백엔드에서 공짜다 — 그저 컴비네이터 코어가 이미 실행할
줄 아는 항을 만드는 새로운 방법일 뿐이다. 예외들이 오히려 시사하는
바가 크다: 문자 리터럴은 진짜 새 런타임 프리미티브가 필요했고
(CHAR 노드 태그, 파서 케이스, eval.c 안에서 GC가 볼 수 있는 표현),
그것이 이 장에서 두 하스켈 파일 몇 줄을 넘어서는 유일한 기능이다.
그 외 나머지 — let, 튜플, 리스트, 문자열, 타입 시그니처, do
표기법 — 는 모두 파서 몇 줄과 디슈가러 몇 줄뿐, 런타임 변화는
전혀 없다.
"파싱하고 무시하기"는 같은 절약을 코드가 아니라 시간에 적용한 것이다.
e96d04be는 프로그래머가 f의 정의 위에 f :: Int -> Int를 쓸 수
있게 해 주기 위해 타입 시그니처가 무엇을 뜻하는지 결정할 필요가
없다 — 구문을 받아들이고 버리는 데는 한 줄이 들지만 몇 달을 벌어
준다: 여기서부터 9장까지의 모든 커밋은 타입 검사기가 그것을 강제하거나
심지어 읽어내기 위해 존재하기도 전에, 시그니처를 문서로 쓰든 아예
쓰지 않든 자유롭다. 이 단계의 프로젝트에서는 완결성보다 추진력이
중요하며, 두 습관 — 작은 코어로 디슈가하기, 의미를 정하기 전에
구문부터 받아들이기 — 모두 언어가 모든 커밋을 작은 연구 프로젝트로
만들지 않고도 빠르게 자라나는 방법이다.
실험 노트 여백
- 커밋별 기능, 시간순:
let+주석+error, 중위 연산자, 타입 시그니처 (무시됨), 튜플, 리스트 구문, 문자 리터럴, 문자열 리터럴, 모듈 임포트,do표기법,primitive. 이 범위의 커밋 두 개는 아예 기능이 아니다 —4e4c5252와ff4622e8는 리팩터링이며, 둘 다 임기응변 특수 처리가 통일할 가치가 있을 만큼 쌓인 뒤에야 도착한다 (튜플과 리스트 둘 다 자기 케이스를 덧붙인 뒤의 패턴 파싱; 한정된 이름이do에 꼭 필요해지기 직전의 식별자 파싱). 리팩터링은 기능 작업과 뒤섞여 있지, 자기만의 커밋이나 자기만의 날로 몰아서 처리되지 않는다. - 그날의 개수: 이 장의 열두 개 커밋 중 아홉 개 —
5ccb1b2a부터b25d9fc8까지 — 는 2장이b56ba28b로 마무리되는 것과 같은 날인 2023-05-30에 도착한다. 나머지 세 개 —ff4622e8,693dc6ce,95ff6a34— 는 다음 작업 세션인 2023-06-01에 도착한다. - 하드코딩된 결합성/우선순위 사다리도 엄연한 메커니즘이다:
3aa12deb의pA/pB/.../pG사슬에는 연산자 표도 사용자에게 보이는 결합성/우선순위 선언도 없지만,*가 사슬 안에서+보다 한 단계 더 강하게 묶이기 때문에1 + 2 * 3을1 + (2 * 3)으로 올바르게 파싱한다 — 우선순위 표 전체가 어느 함수가 어느 함수를 호출하는지일 뿐, 그 이상 추상적인 것은 없다.
직접 해보기
기준점: 693dc6ce("Add do desugaring.", do 디슈가링 추가). 관례
(00-overview.md 참고):
git worktree add /tmp/mhs-693dc6ce 693dc6ce
cd /tmp/mhs-693dc6ce
2장의 b56ba28b와 마찬가지로 이 커밋의 Makefile에는 파서 주도
컴파일러(Main.hs)를 위한 타깃이 없다 — 옛 Lam.hs/eval.c의
test 타깃만 존재한다. Main.hs를 손으로 빌드하면 2장의 빌드
노트가 다루는 것과 정확히 같은 GHC-9.8/mtl 문제에 부딪히고, 거기에
더해 이 장 범위에서 처음 등장하는 문제 하나가 더 있다. 노트가
다루는 새 파일 Compile.hs가 처음으로 존재하는 커밋이기 때문이다.
빌드 노트: 쓰인 그대로 빌드하면 —
nix develop $MICROHS -c ghc Main.hs -o uhs먼저 2장의
ap-스코프에-없음 오류가ParserComb.hs에서 난다 (Variable not in scope: ap :: Prsr s (a -> b) -> Prsr s a -> Prsr s b,ParserComb.hs:52:11) — 2장이 쓰는 것과 같은 한 줄짜리 수정을ParserComb.hs의 기존import Control.Monad.State.Strict뒤에 적용한다:import Control.Monad(ap)그 수정을 적용하면 빌드는 더 나아가지만,
b25d9fc8가 추가한 모듈Compile.hs에서 같은 모양의 두 번째 문제에 부딪힌다:Compile.hs:30:7: error: [GHC-88464] Variable not in scope: when :: Bool -> a2 -> StateT Cache IO a3 Suggested fix: Perhaps use data constructor ‘Then’ (imported from Parse) | 30 | when (nm `elem` ws) $ | ^^^^(같은 모양의 두 번째 오류가
Compile.hs:44:3, 같은 함수의 다른when호출에서 뒤따른다 — 위에서는 생략했다.)when(Compile.hs안에서 두 번 쓰이며, 둘 다 잘못된 조건에서error를 일으키는 데 쓰임)도 이 GHC/mtl 조합에서Compile.hs자신의import Control.Monad.State.Strict로는 스코프에 들어오지 않는다 —ap문제와 근본 원인은 같고, 다른 심볼, 다른 파일이다.Compile.hs의 기존import Control.Monad.State.Strict뒤에 한 줄을 추가한다:import Control.Monad(when)그러면 빌드가 성공한다(2장이 짚었던 것과 같은 종류의 무해한
-Wx-partial경고,head/tail에 관한 것은 아래에서 생략했다):nix develop $MICROHS -c ghc Main.hs -o uhs[1 of 7] Compiling ParserComb ( ParserComb.hs, ParserComb.o ) [2 of 7] Compiling Parse ( Parse.hs, Parse.o ) [3 of 7] Compiling Exp ( Exp.hs, Exp.o ) [4 of 7] Compiling Desugar ( Desugar.hs, Desugar.o ) [5 of 7] Compiling Compile ( Compile.hs, Compile.o ) [6 of 7] Compiling Main ( Main.hs, Main.o ) [7 of 7] Linking uhs새 컴파일러가 만들어 내는 것을 런타임이 실행하기 전에 한 가지가 더 필요하다:
eval.c자신이며,Makefile의eval타깃이 이미 빌드할 줄 안다 —nix develop $MICROHS -c gcc -Wall -O3 eval.c -o eval아래 연습 문제들 전에 두 한 줄짜리 패치를 모두 적용하고
eval을 빌드해 둔다.
또한, Compile.hs가 b25d9fc8에서 들어온 이후로: 소스 파일은 파일
인자가 아니라 모듈 이름으로 로드된다 — Compile.hs의
compileModule은 명령줄에 넘긴 경로가 아니라 <name>.uhs를 읽으며,
./uhs Foo(./uhs Foo.uhs가 아니라)가 새 Main.hs가 그것을 호출하는
방식이다([mn] <- getArgs; ds <- compile mn, 693dc6ce:Main.hs).
연습 문제 1: let, 리스트, do 표기법, IO는 건드리지 않고
이 커밋 시점의 do 표기법은 IO 모듈도 어떤 내장 모나드도 필요로
하지 않는다 — "무슨 일이 있었나"에서 봤듯 M.do는 그저 자신만의
(>>=)와 (>>)가 스코프에 있는 모듈 M만 있으면 된다. 사소한
(>>=)/(>>) 쌍을 제공하고 그것을 do를 통해 쓰는, 작고 자족적인
모듈 하나를 써 보자:
cat > Demo.uhs <<'EOF'
module Demo where
(>>=) x f = f x
(>>) x y = y
main = Demo.do
y <- 10
let
xs = [1, 2, 3]
in case xs of
[] -> 0
(:) a as -> a + y
EOF
nix develop $MICROHS -c ./uhs Demo
importing "Demo"
importing done "Demo"
Demo.>>= = C I
Demo.>> = T
Demo.main = Demo.>>= 10 (C' (P 0) (B (B K) (C +)) (O 1 (O 2 (O 3 K))))
((T :0 (C I)) ((T :1 T) ((T :2 ((_0 10) (((C' (P 0)) ((B (B K)) (C +))) ((O 1) ((O 2) ((O 3) K)))))) _2)))
링크된 프로그램을 실행해 보자:
nix develop $MICROHS -c ./eval out.comb
((T :99996 (C I)) ((T T) ((T :99989 ((_99996 10) (((C' (P 0)) ((B (B K)) (C +))) ((O 1) ((O 2) ((O 3) K)))))) _99989)))
11
node size=16, heap size=100000
56 reductions, 0 GCs
eval.c의 main은 pp(stdout, n)을 두 번 호출한다, 파싱 직후 한 번
그리고 축약 이후 한 번(693dc6ce:eval.c 704행과 706행 — 2장의
54806439 이후로 바뀌지 않았다) — 위의 첫 줄은 pp 자신의 독립적인
공유-탐지 패스를 거쳐 출력된, 파싱은 됐지만 아직 축약되지 않은 항
(그래서 파일 자신의 :0/:1/:2와는 맞지 않는 :99996 같은 레이블
번호가 나온다)이고, 두 번째 줄은 evali가 실행된 뒤의 답이다: 11.
y는 do 블록의 Bind에 의해 10으로 묶이고, xs는 리스트
[1,2,3]이며, xs에 대한 case는 (:) a as 절에 a = 1로
매치되고, a + y = 11이다. 여기까지 오는 길에 알아 둘 만한 막다른
길 두 곳이 있는데, 둘 다 위 예제의 오타가 아니라 이 커밋 파서의
진짜 한계다:
-
let x = 5 in x를 한 줄로 쓰면 파싱되지 않는다:cat > T1.uhs <<'EOF' module T1 where main = let x = 5 in x EOF nix develop $MICROHS -c ./uhs T1importing "T1" uhs: line 3, col 11: found: "x" expeced: let ' ' ...let이 (pBlock의softLC를 통해) 여는 블록은 언제나 다음 물리적 줄에서 들여쓰기를 가져오지, 현재 줄의 나머지에서는 가져오지 않으므로, 바인딩되는 변수들은 새로, 들여쓰인 줄에서 시작해야 한다. -
in은 감싸는do블록의 열과let블록 자신의 열 사이 어딘가에 엄격하게 들여써야 한다(여기서는do가 문장을 2열에서 시작하고,let자신의 블록은 4열이므로in은 3열에 와야 한다).in을 2열 이하로 들여쓰면 레이아웃 알고리즘의 공백-기반 내어쓰기 규칙 (pWhite,Parse.hs)이let블록을 올바르게 닫기는 하지만, 같은 내어쓰기를 새do문장의 시작으로도 동시에 읽어서in앞에;를 끼워 넣어 파싱을 깨뜨린다.(:)절만 있고[]절이 없는case도 조용히 축약에 실패한다 — 2장의O컴비네이터는 그 순서로 두 연속체(nil 갈래, 그다음 cons 갈래)를 받는데, 한 절짜리case는 이를 덜 적용해서 결과가 숫자가 아니라 부분 적용인 채로 멈춘다 (한 절짜리 버전을eval로 직접 실행해 축약되지 않은 항이 그대로 나오는 것을 확인했다, 오류가 아니라).
연습 문제 2: out.comb에서 디슈가된 do 체인 읽어 보기
연습 문제 1의 out.comb는 106바이트로, 통째로 읽을 만큼 작다:
((T :0 (C I)) ((T :1 T) ((T :2 ((_0 10) (((C' (P 0)) ((B (B K)) (C +))) ((O 1) ((O 2) ((O 3) K)))))) _2)))
:0, :1, :2는 소스 순서대로의 최상위 정의 세 개 — Demo.>>=,
Demo.>>, Demo.main — 이며, 각각 컴비네이터 항으로 컴파일되어
2장의 17587b2d의 레이블 방식으로 링크되어 있다. :0의 항은
C I다 — C f x y = f y x이므로 (>>=) x f = f x가 브래킷
추상화로 컴파일되면 C I x y = I y x = y x = f x가 되어, f와 x의
이름만 맞춰지면 된다. Demo.main의 항인 :2는 693dc6ce:Desugar.hs의
do 디슈가링이 그대로 눈에 보이는 곳이다: (_0 10) (...)은 _0
(Demo.>>=, 즉 바인드 연산자)에 10(디슈가된 Bind "y" (EInt 10))을
적용한 뒤 람다에서 컴비네이터로 바뀐 연속체를 적용한 것이다 — 정확히
dsExpr (EDo n (Bind i e : ss)) = App2 (Var (n ++ ".>>=")) (dsExpr e) (Lam i $ dsExpr (EDo n ss))가 만들어 내는 모양이며, n = "Demo",
i = "y", e = EInt 10, ss는 연속체의 본문이 되는 case 식이다.
연속체 자신, (C' (P 0) (B (B K) (C +))) (O 1 (O 2 (O 3 K)))는 연습
문제 1의 막다른 길 노트에서 나온 리스트-위-case가 컴파일된 것이다:
O 1 (O 2 (O 3 K))는 [1,2,3]이고(d91b9812:Desugar.hs의 EList
디슈가링 — "무슨 일이 있었나" 참고), (P 0)/(B (B K) (C +))는 그
순서대로 컴파일된 [] -> 0과 (:) a as -> a + y 절이며, O의 축약
규칙이 기대하는 두 연속체다.
연습 문제 3: 파서 확장하기 — 정수 리터럴 안의 밑줄
이 커밋 시점의 pInt는 숫자 하나 이상만 받아들이고 그 외에는 아무것도
받아들이지 않는다(693dc6ce:Parse.hs 204행, 전문 인용):
pInt :: P Integer
pInt = (read <$> (skipWhite $ esome $ satisfy "digit" isDigit)) <?> "int"
하스켈 스타일의 자릿수 구분자가 오늘은 파싱되지 않는다는 것을 확인해 보자:
cat > Under.uhs <<'EOF'
module Under where
main = 1_000
EOF
nix develop $MICROHS -c ./uhs Under
importing "Under"
uhs: line 3, col 8:
found: "_000"
expeced: int digit
...
(pInt는 1을 읽고 숫자가 아닌 첫 문자에서 멈춘다; pExprApp은
그런 다음 1을 적용할 또 다른 원자 식을 찾는데 _000은 그런 것이
아니다 — 글자로 시작하지 않으니 식별자도 아니다.) pInt
(Parse.hs, 위에서 인용한 그 한 줄)를 고쳐 _를 자릿수 구분자로
받아들이게 하되, 앞에 숫자 하나가 오도록 요구하고 read하기 전에
밑줄을 걸러낸다:
수정 전(Parse.hs 204행):
pInt = (read <$> (skipWhite $ esome $ satisfy "digit" isDigit)) <?> "int"
수정 후:
pInt = (read . filter (/= '_') <$> (skipWhite $ (:) <$> satisfy "digit" isDigit <*> emany (satisfy "digit" isDigit <|> char '_'))) <?> "int"
다시 빌드하고 실행해 보자:
nix develop $MICROHS -c ghc Main.hs -o uhs
nix develop $MICROHS -c ./uhs Under
[2 of 7] Compiling Parse ( Parse.hs, Parse.o ) [Source file changed]
[7 of 7] Linking uhs [Objects changed]
importing "Under"
importing done "Under"
Under.main = 1000
((T :0 1000) _0)
nix develop $MICROHS -c ./eval out.comb
((T 1000) 1000)
1000
node size=16, heap size=100000
6 reductions, 0 GCs
(첫 줄은 연습 문제 1의 트랜스크립트와 같은 pp의 축약 전 에코이고,
두 번째, 1000은 축약된 답이다.) 1_000은 이제 정수 1000으로
파싱되어 1000으로 실행된다; 밑줄 없는 평범한 main = 42도 여전히
컴파일되어 바뀌지 않고 42로 실행된다 — 수정된 uhs로 같은 방식으로
다시 실행해 확인한다:
cat > Reg.uhs <<'EOF'
module Reg where
main = 42
EOF
nix develop $MICROHS -c ./uhs Reg
nix develop $MICROHS -c ./eval out.comb
((T 42) 42)
42
node size=16, heap size=100000
6 reductions, 0 GCs
정리한다:
git worktree remove --force /tmp/mhs-693dc6ce