🌐 Read in English

02 — A real compiler (진짜 컴파일러)

현재 위치

1장은 두 개의 파일과 그 사이에 놓인 텍스트 형식 하나를 남겼다: Lam.hs는 손으로 만든 Exp 값 하나 — nfib 35를 계산하는 eNfib — 를 컴비네이터로 컴파일하고, eval.c는 그 결과를 실행한다. 아직 파서는 없다. 시스템이 실행할 수 있는 모든 예제는 하스켈 소스이지만, 컴파일러가 읽어들이는 텍스트가 아니라 Lam.hs 안에 손으로 작성한 Exp 값 그대로의 하스켈 소스다. 커밋 21168890("Clean more", 더 정리하기)은 이 장의 범위 직전 마지막 커밋이며, Makefile의 한 줄만 바꾼다. 하드코딩된 프로그램이라는 모양은 아직 전혀 움직이지 않았다.

무슨 일이 있었나

준비 운동: 2023-05-26

씨앗 다음 금요일에 세 개의 커밋이 도착하는데, 모두 여전히 옛 두 파일 세계(Lam.hs/eval.c) 안에 있으며, 아직 작성되지 않은 파서를 건드리는 것은 하나도 없다:

54806439("Use file handle for printing.", 출력에 파일 핸들 사용하기)는 eval.c의 pretty/pp 함수를 하드코딩된 printf/putchar 호출에서 명시적인 스트림을 받는 print(FILE *f, ...)/pp(FILE *f, ...)로 바꾼다. main은 여전히 두 번 다 pp(stdout, n)을 호출하므로 프로그램이 눈에 보이는 출력은 아무것도 바뀌지 않는다 — 하지만 이제 그 함수는 아무 파일 핸들이나 가리킬 수 있게 되었고, 이것이 34분 뒤 b0c33a8f가 같은 종류의 핸들에서 읽어 들이는 레이블 파싱 경로를 추가할 수 있게 해 주는 바탕이 된다.

6485a341("Move some improvements earlier.", 개선을 더 일찍 적용하기)는 규칙 집합은 바꾸지 않은 채 Lam.hs의 최적화기 순서만 재배치한다: "교환 연산의 인자를 뒤집는" 재작성((CC, Prim "+") -> Prim "+" 등)이 improveT의 케이스 목록에서 나와 improveC의 케이스 목록으로, 그것도 improveC 자신의 catch-all보다 앞으로 옮겨 간다. 두 패스는 여전히 모두 존재하지만(improve = improveT . improveC), 이제 항은 두 번째 순회를 기다릴 필요 없이 첫 번째 순회에서 뒤집기 정규화를 거친다 — 바로 위에 있는 improveC의 S'/C' 규칙이 이미 뒤집힌 피연산자에 대해 한 번의 패스만으로 발화할 기회가 늘어난다. 커밋 메시지는 의도("더 일찍 ... 옮기기")를 말할 뿐 이 메커니즘은 말하지 않는다 — 이 장이 계속 마주치는 패턴이다 ("실험 노트 여백" 참고).

b0c33a8f("Print and parse sharing/cycles.", 공유/순환 출력 및 파싱)는 인용할 가치가 있는 준비 운동 커밋이다. 이 커밋이 도입하는 형식이 a9178695부터 2장 자체의 컴파일러 출력이 사용하는 형식이기 때문이다: 트리뿐 아니라 DAG나 순환도 평평한 텍스트로 출력하는 방법이다. 파서 쪽 (b0c33a8f:eval.c, 295–306행):

  case '_' :
    l = (int)parse_int(f);  /* The label */
    if (shared[l] == NIL) ERR("shared == NIL");
    return shared[l];
  case ':' :
    l = (int)parse_int(f);  /* The label */
    if (!gobble(f, ' ')) ERR("parse ' '");
    if (shared[l] != NIL) ERR("shared != NIL");
    shared[l] = alloc_node(IND); /* Must have a placeholder for cycles */
    r = parse(f);
    INDIR(shared[l]) = r;
    return r;

:N <expr>은 공유 노드 N을 정의한다(간접 노드 자리표시자가 <expr>이 파싱되기 전에 미리 할당되는데, 이는 <expr> 내부에서 N을 되가리키는 순환 참조가 가리킬 대상을 갖도록 하기 위해서다); _N은 그것을 다시 가리킨다. 출력 쪽은 사전 패스(find_sharing)에서 두 번 방문된 노드를 모두 SHARED로 표시한 다음, 실제 출력 패스에서 SHARED 노드에 처음 도달했을 때만 :N 을 찍고 그 이후로는 매번 _N만 찍는다 (b0c33a8f:eval.c, 327–333행):

  if (MARK(n) == PRINTED) {
    fprintf(f, "_%d", LABEL(n));
    return;
  } else if (MARK(n) == SHARED) {
    fprintf(f, ":%d ", LABEL(n));
    MARK(n) = PRINTED;
  }

이 커밋 자신의 테스트 데이터에서는 아직 실제로 노드를 공유하는 것이 없다 — 기반 다지기일 뿐이다. 나흘 뒤, 17587b2d의 "hack"이 처음으로 이 레이블 형식을 실전에 쓴다.

a9178695: "Make a real compiler."(진짜 컴파일러 만들기) (2023-05-29, 16:14)

전환점이다. 새 파일 여섯 개, 561줄, git show a9178695 --stat:

 Desugar.hs    |  31 +++++++++
 Exp.hs        | 141 ++++++++++++++++++++++++++++++++++++++++
 Lam.hs        |   6 ++
 Main.hs       |  14 ++++
 Parse.hs      | 204 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ParserComb.hs | 165 +++++++++++++++++++++++++++++++++++++++++++++++

ParserComb.hs와 Parse.hs는 파서 컴비네이터 라이브러리와 그 위에 세운 문법이다 — aux/parser-combinators.md가 둘 다 자세히 다룬다. 여기서 중요한 것은 이들이 무엇을 받아들이고 그 아래 방향으로 무엇이 바뀌는가이다. 이 커밋 시점의 표면 언어는 작다: 모듈 (module Name where와 정의 블록), 함수 정의(f x y = expr), 데이터 선언(data T = C1 t1 t2 | C2), 그리고 변수/생성자 이름, 정수 리터럴, 적용, \x. expr 람다, 생성자 패턴 절을 가진 case expr of, 괄호로 묶은 부분식으로 만들어지는 식들이다 — 대표적인 생성 규칙 하나 (a9178695:Parse.hs, 147–150행):

pDef :: P Def
pDef =
      Data <$> (pKeyword "data" *> pLHS pUIdent <* pSymbol "=") <*> esepBy1 ((,) <$> pUIdent <*> many pAType) (pSymbol "|")
  <|> Fcn <$> (pLHS pLIdent <* pSymbol "=") <*> pExpr

Exp.hs는 Lam.hs 자신의 Exp 타입과 compile/abstract/improve/ reduce 파이프라인(aux/bracket-abstraction.md가 원본을 다룬다)을 거의 그대로 자기 모듈로 복사해 넣은 것이다 — Lam.hs는 자신의 사본을 수정하지 않은 채 그대로 두고 make test의 뒷단으로 계속 남으며, Exp.hs는 새 파서 주도 경로의 뒷단이 된다. 이 커밋부터 둘은 갈라진다. Desugar.hs는 Parse.hs의 Expr/Def/Module AST를 Exp.hs의 Exp로 잇는 다리다: 식에 대해서는 단순한 case를 적용으로 바꾸는 재작성이고(a9178695:Desugar.hs, 25–31행, 전문 인용) —

dsExpr :: Expr -> Exp
dsExpr (EVar i) = Var i
dsExpr (EApp f a) = App (dsExpr f) (dsExpr a)
dsExpr (ELam x e) = Lam x (dsExpr e)
dsExpr (EInt i) = Int i
dsExpr (ECase e as) = apps (dsExpr e) (map dsArm as)
  where dsArm ((_, xs), r) = lams xs $ dsExpr r

— 더 흥미로운 것은 데이터 선언 디슈가링(문법 설탕 풀어내기)인데, 각 생성자를 자신의 필드들 뒤에 생성자마다 하나씩의 연속(continuation) 인자를 받아 그중 자기 것을 고르는 평범한 함수로 바꾼다 (a9178695:Desugar.hs, 16–22행): dsDef (Data _ cs) = zipWith dsConstr [0..] cs는 n개 중 i번째 생성자에 대해 \x1 x2 ... $f0 $f1 ... $f(n-1) -> $fi x1 x2 ... 모양의 함수를 만든다 — 스콧 인코딩이며, 런타임에 별도의 패턴 매칭 장치 없이 케이스 분석을 바로 적용으로 컴파일한다. main은 하드코딩된 항 하나를 출력하던 것에서 다음으로 바뀐다(a9178695:Main.hs, 전문 인용):

import System.Environment(getArgs)
import Parse
import Desugar
import Exp

main :: IO ()
main = do
  [fn] <- getArgs
  mdl <- parseDie pTop fn <$> readFile fn
  let ds = desugar mdl
      ds' = [ (i, improve $ compile e) | (i, e) <- ds ]
  mapM_ (\ (i, e) -> putStrLn $  i ++ " = " ++ toString e) ds
  mapM_ (\ (i, e) -> putStrLn $  i ++ " = " ++ toString e) ds'

이제 명령줄 인자는 파일 이름 하나뿐이다. 프로그램을 읽어들이고 (readFile fn), 파싱하고(parseDie pTop fn), 디슈가한 다음, 최상위 정의 각각을 독립적으로 컴파일하고 개선한다 — 이 버전은 아직 정의들을 하나의 실행 가능한 프로그램으로 연결하려 하지 않는다. 이름별로 나이브한 형태와 최적화된 컴비네이터 형태를 출력할 뿐이다. 아직 writeFile도 없고, 어느 정의가 진입점인지에 대한 개념도 없다. 그 빈틈을 정확히 채우는 것이 다섯 커밋 뒤의 17587b2d다.

648aeef0("Add another node representation.", 노드 표현 하나 추가하기, a9178695 13분 뒤)과 71729105("Add pair and cons.", pair와 cons 추가하기, 그로부터 19초 뒤)는 같은 날 오후에 이어진다. 둘 다 각자 주제상 속하는 커밋들과 함께 아래에서 설명한다.

648aeef0: eval.c의 세 번째 노드 레이아웃

1장의 eval.c는 노드 표현 하나, NODE_NAIVE — 진짜 포인터를 담은 C struct이며 파일 맨 위의 #define NODE_NAIVE로 선택됨 — 만 실행했지만, 파일은 이미 같은 #if/#elif 사슬 안에 컴파일은 되지만 선택되지 않은 두 번째 옵션, NODE_SPLIT을 갖고 있었다(ccb31388:eval.c, 5–8행: 아래 인용된 것과 같은 주석 블록에서 아직 존재하지 않는 NODE_INDEX 줄만 뺀 것). 이 커밋은 세 번째로 살아있는 옵션 NODE_INDEX를 추가하고 활성 #define을 그쪽으로 바꾼다(648aeef0:eval.c, 5–10행):

/* Node representation:
 * NODE_NAIVE   all fields in a struct, regular pointers
 * NODE_INDEX   use 32 bit indices instead of pointers
 * NODE_SPLIT   split flags, funs, and args
 */
#define NODE_INDEX

NODE_INDEX는 각 셀(FUN/ARG) 안의 8바이트 포인터 두 개를 하나의 cells 배열을 가리키는 32비트 배열 인덱스로 바꾼다(648aeef0:eval.c, 51–67행, 유니온 본체는 생략 — NODE_NAIVE와 같은 모양):

#elif defined(NODE_INDEX)
/* Naive node representation with minimal unions */
typedef u_int32_t NODEPTR;
typedef struct node {
  enum node_mark mark;
  enum node_tag tag;
  union {
    ...
  } u;
} node;
#define NIL (-1)
#define HEAPREF(i) (i)
#define MARK(p) cells[p].mark

이것은 가상의 효과가 아니라 실제로 측정된 효과다: 1장의 ccb31388 빌드는 NODE_NAIVE에 대해 node size=24, heap size=100000을 보고하는데, 이 장의 b56ba28b(NODE_INDEX를 계속 활성 상태로 유지)를 빌드해 수정 없는 Lam.hs 파이프라인으로 정확히 같은 nfib 35 프로그램을 실행하면 node size=16을 보고한다 — 3분의 1 더 작으며, 축약 횟수와 GC 횟수는 둘 다 그대로다(1045124618회 축약, 1944회 GC, 둘 다 동일 — 아래 "직접 해보기"의 트랜스크립트 참고). 세 가지 표현 선택지가 이제 같은 #if 사슬 안에 나란히 존재한다. NODE_NAIVE와 NODE_SPLIT 둘 다 여전히 컴파일은 되지만 선택되지 않을 뿐이다 — 표현에 관한 실험은 나중에 합칠 브랜치가 아니라 메인라인 위에서 #define 하나를 편집하는 것으로 일어난다.

9cf1e937 + b4e44ded: "New optimiser."(새 최적화기) (2023-05-30, 12:46–12:47)

다음 세션, 그러니까 다음 날은 같은 커밋 메시지가 40초 간격으로 두 번 등장하며 시작한다. 문자 그대로 읽으면 첫 번째 것은 빌드되지 않는다: 9cf1e937의 전체 diff는 Exp.hs에 추가된 한 줄, toStringP (Lbl i e) = ":" ++ show i ++ " " ++ toStringP e — 이 커밋의 Exp 타입이 아직 선언하지 않은 생성자 Lbl에 대한 프리티 프린터 케이스다(Lbl은 b4e44ded에 가서야 data Exp에 추가된다). Exp.hs를 정확히 9cf1e937에서만, 그리고 이 범위의 다른 어느 지점에서도 아니게 빌드해 보면 이를 확인할 수 있다:

Exp.hs:129:37: error: [GHC-58481] parse error on input ‘=’
    |
129 | redOne (App4 (Comb "O") x1 x2 f1 f2 = Just $ App2 f2 x1 x2

— 빠진 Lbl 생성자 때문에 예상할 법한 오류조차 아니다. 평범한 괄호 짝이 안 맞는 오타이며, 전날 오후 71729105("Add pair and cons.")에서 고쳐지지 않은 채 물려받은 것으로, 그것 하나만으로도 파일 전체가 컴파일되지 못하게 막기에 충분하다. 두 번째 "New optimiser." 커밋인 b4e44ded는 그 구문 오류를 고치는 동시에 진짜 재작성을 수행한다: 옛 2패스 compile(나이브 브래킷 추상화) 다음 improve = improveT . improveC(별도의 정리 패스)가, 항을 만드는 도중에 같은 재작성 규칙을 스마트 생성자 — cS/cC/cB/cS'/cC' — 를 통해 인라인으로 적용하는 한 패스로 바뀐다(b4e44ded:Exp.hs, 73–100행):

abstract :: Ident -> Exp -> Exp
abstract x e@(Var y) | x == y = CI
abstract x (App f a) = cS (abstract x f) (abstract x a)
abstract x (Lam y e) = abstract x $ abstract y e
abstract x e = cK e

cK :: Exp -> Exp
--cK CI = CT
cK e  = App CK e

cS :: Exp -> Exp -> Exp
cS (App CK e1)     (App CK e2) = cK (App e1 e2)    -- S (K e1) (K e2) = K (e1 e2)
cS (App CK e1)     CI          = e1                -- S (K e1) I      = e1
cS (App CK e1)     e2          = cB e1 e2          -- S (K e1) e2     = B e1 e2
cS e1              (App CK e2) = cC e1 e2          -- S e1     (K e2) = C e1 e2
cS (App2 CB e1 e2) e3          = cS' e1 e2 e3      -- S (B e1 e2) e3  = S' e1 e2 e3
cS e1 e2                       = App2 CS e1 e2

cC :: Exp -> Exp -> Exp
cC (App2 CB e1 e2) e3          = cC' e1 e2 e3      -- C (B e1 e2) e3  = C' e1 e2 e3
--cC (Prim op)       e2 | Just op' <- lookup op flipOps = App (Prim op') e2 -- C op e = flip-op e
cC (Var op)        e2 | Just op' <- lookup op flipOps = App (Var op') e2 -- C op e = flip-op e
cC e1              e2          = App2 CC e1 e2

cB :: Exp -> Exp -> Exp
cB CC          (App CC CI) = CP -- Pair
cB (App CB CK) CP          = CO -- Cons
cB e1          e2          = App2 CB e1 e2

옛 improveC/improve 블록은 지워지지 않고, 1장 커밋 1에서 짚었던 "탐색적 코드는 지우지 말고 실행만 멈춰라"는 습관 그대로 파일 안에 주석 처리({- ... -})된 채 남아 있다. 읽어서만이 아니라 기계로도 검증된다: compileOpt = improveT . compile일 때, a9178695에서 \x. \y. \f. f x y(pair 함수)를 컴파일하면 P 컴비네이터로 축약되기 위해 별도의 improve 패스가 필요하다 —

compile epair            = S (K C) (S (S (K C) (K I)) I)
improve (compile epair)  = P

— 반면 b4e44ded에서는 compile 혼자서 이미 P를 만들어 내며, 두 번째 패스가 필요 없다:

compile epair    = P
compileOpt epair = P

같은 입력, 같은 최종 답, 도달하는 데 순회 한 번이 줄었다 — "New optimiser."라는 제목은 의도를 말할 뿐이며, diff를 읽어야만 이것이 새 규칙을 추가하는 게 아니라 정리 패스를 추상화 안으로 합치는 것임을 알 수 있다(규칙 집합 — Pair/Cons 포함 — 은 improveC가 이미 가지고 있던 것을 거의 그대로 옮긴 것에 가깝다. cB의 Pair/Cons 케이스는 전날 71729105가 주석 처리해 둔 바로 그 두 규칙이 이제 다시 살아난 것이다).

17587b2d: "Hack around a problem."(문제를 임시방편으로 피해 가기) (2023-05-30, 12:47:15, 13초 뒤)

a9178695의 main은 최상위 정의 각각을 독립적으로 컴파일해 각각을 따로 출력했다 — 그것들을 하나의 실행 가능한 항으로 합친 적이 없었고, 어느 것이 진입점인지도 알지 못했다. 그것이 문제다. 그 해법은 (17587b2d:Main.hs, 전문 인용):

import Data.Maybe
import System.Environment(getArgs)
import Parse
import Desugar
import Exp

primOps :: [(Ident, Exp)]
primOps =
  [ ("error", Prim "?")
  , ("+",     Prim "+")
  , ("-",     Prim "-")
  , ("-'",    Prim "-'")
  , ("*",     Prim "*")
  , ("quot",  Prim "/")
  , ("rem",   Prim "%")
  , ("<",     Prim "<")
  , ("<=",    Prim "<=")
  , (">",     Prim ">")
  , (">=",    Prim ">=")
  , ("==",    Prim "==")
  , ("/=",    Prim "!=")
  ]

main :: IO ()
main = do
  [fn] <- getArgs
  mdl <- parseDie pTop fn <$> readFile fn
  let ds = desugar mdl
      ds' = [ (n, compileOpt e) | (n, e) <- ds ]
      defs :: [(Ident, Exp)]
      defs = [ (n, ref i) | ((n, _), i) <- zip ds' [0..] ] ++ primOps
      find n = fromMaybe (error $ "undefined: " ++ show n) $ lookup n defs
      emain = find "main"
      res = foldr def emain (zip ds' [0..])
      def :: ((Ident, Exp), Int) -> Exp -> Exp
      def ((n, e), i) r = App2 CT (Lbl i (subst e)) r
      subst (Var n) = find n
      subst (App f a) = App (subst f) (subst a)
      subst e = e
      ref i = Var $ "_" ++ show i
--  mapM_ (\ (i, e) -> putStrLn $  i ++ " = " ++ toString e) ds
  mapM_ (\ (i, e) -> putStrLn $  i ++ " = " ++ toString e) ds'
  putStrLn $ toStringP res
  writeFile "out.comb" $ toStringP res

최상위 정의 n마다 정수 인덱스 i가 붙고(소스 파일 순서, zip ds' [0..]), 다른 정의의 본문 안에서 어떤 최상위 이름을 자유 변수로 참조하든 그것은 (subst에 의해) 텍스트 상으로 Var "_i"로 바뀐다 — b0c33a8f의 레이블 형식으로 들어가는 참조이지, 진짜 속박 변수가 아니다. 프로그램 전체는 중첩된 T (Lbl i body_i) rest 적용이 되고(T x y = y — 여기서 T는 정의의 텍스트를 출력에 이어붙이기 위해 순수하게 순서를 정하는 용도로만 쓰인다. 그 값은 버려지고, 그 레이블만 중요하다), main이 받은 인덱스에 대한 참조로 끝난다. 의존성 분석도, 레이블 형식 자신의 파싱 전 자리표시자 트릭(b0c33a8f)이 공짜로 벌어다 주는 것 이상의 전방 선언 처리도 없으며, 해결되지 않은 이름은 파싱에 실패하는 게 아니라 — find에서, error $ "undefined: " ++ show n이라는 하스켈 예외로 실패한다. 파서가 내는 진단이 아니다. 그것은 커밋 메시지가 말하는 그대로다: 실제 문제(독립적으로 컴파일된 N개의 정의를 하나의 닫힌, 실행 가능한 그래프로 만드는 것)에 적용된 임시방편(hack)이지, 그 문제에 대한 일반적인 해법(링킹, 의존성 순서 매기기, 진짜 모듈 시스템)이 아니다 — 그리고 커밋 로그에 그렇다고 정직하게 표시되어 있을 뿐, 설계 결정으로 포장되지 않는다. 아래 "직접 해보기" 연습 문제 1은 바로 이 임시방편의 한계에 정확히 부딪힌다.

4030f721과 b56ba28b: 파싱과 컴비네이터가 계속 자라다

4030f721("Parse more", 더 파싱하기)는 새 식 형태 하나 — 괄호로 감싼 연산자 (+), 평범한 식별자를 쓸 수 있는 곳이면 어디서든 쓸 수 있음 — 를 열두 줄만 추가해 넣는데, 모두 aux/parser-combinators.md 3절이 이미 다룬 조각들로 만든 평범한 컴비네이터 코드다. 그 문서가 diff 전체를 5절에서 따라간다. b56ba28b("More combinators.", 컴비네이터 추가)는 b4e44ded가 되살린 Pair/Cons 규칙의 eval.c 쪽 대응이다: P/O 컴비네이터가 enum node_tag에 태그를 얻고, 전역 combP/combO 노드, 파서 케이스('P'/'O'), 프린터 케이스, 런타임 축약 규칙을 얻는다 (b56ba28b:eval.c, 599–620행, 전문 인용):

    case P:                     /* P x y f = f x y */
      CHECK(3);
      GCCHECK(1);
      x = ARG(TOP(1));
      y = ARG(TOP(2));
      f = ARG(TOP(3));
      POP(3);
      n = TOP(0);
      FUN(n) = new_ap(f, x);
      ARG(n) = y;
      GOTO ap;
    case O:                     /* P x y g f = f x y */
      CHECK(4);
      GCCHECK(1);
      x = ARG(TOP(1));
      y = ARG(TOP(2));
      f = ARG(TOP(4));
      POP(4);
      n = TOP(0);
      FUN(n) = new_ap(f, x);
      ARG(n) = y;
      GOTO ap;

P는 pair 자신의 컴비네이터로, 세 인자를 받아 세 번째를 처음 둘에 적용한다; O는 cons로, 네 인자를 받아 처음 둘에 네 번째를 적용한다(세 번째 — "nil" 연속체 — 는 건너뛰는데, 이것이 바로 cons-대-nil 케이스 분석에 필요한 것이다). case O: 위의 주석조차 여전히 P x y g f = f x y라고 적혀 있다 — 바로 위 케이스에서 복사-붙여넣기 되었지만 O로 고쳐지지 않은 것이다. 이 커밋으로 범위가 마무리된다: b56ba28b 이후, 소스 파일이 표현할 수 있는 언어는 아무것도 없는 상태에서 모듈, 함수, 데이터 선언, case 식, 정수로 자라났고, 런타임은 하루 전에는 모르던 컴비네이터 둘을 새로 이해하게 되었다.

왜 중요한가

한 개의 손으로 만든 항만 실행할 수 있던 컴파일러가 나흘 만에, a9178695는 그것에 진짜 정문을 달아 준다: 손으로 main 안에 조립한 하스켈 값이 아니라, 진짜 파서를 거친 소스 텍스트가 입력이 된다. 그것이 헤드라인이다. 하지만 이 열한 개 커밋 전체에서 더 오래 지속되는 습관은 헤드라인 커밋 다음에 일어나는 일이다: 노드 표현이 바뀌고(648aeef0), 최적화기가 2패스 설계에서 1패스 설계로 다시 쓰이며 첫 시도에서 컴파일이 깨지고(9cf1e937/b4e44ded, 40초 간격), 빠져 있던 "N개의 정의를 프로그램 하나로 합치기" 조각이 인정된 임시방편으로 덧붙는다 (17587b2d) — 9cf1e937부터 b56ba28b까지 다섯 커밋이 커밋 타임스탬프로 총 98초(12:46:22부터 12:48:00까지)에 걸쳐 있는데, 이는 그 코드를 작성하는 데 걸린 시간이 아니라 이미 끝나 있던 작업을 커밋하는 데 걸린 시간이다. 이틀 된 코드 — 최적화기, 그것도 두 번 — 를 다시 쓰는 일이 여기서는 아무 비용도 들지 않는데, 이 프로젝트 바깥 어디에도 아직 그것에 의존하는 것이 없기 때문이다. 그것은 장난감이 누리는 사치이지 출시된 컴파일러는 누리지 못하는 것이며, 이 범위는 그것을 거리낌 없이 활용한다.

실험 노트 여백

• 커밋 메시지는 메커니즘이 아니라 의도를 말한다. "Make a real compiler."는 파서 컴비네이터 라이브러리와 디슈가러, 브래킷 추상화 파이프라인의 두 번째 사본을 새 파일 여섯 개에 추가한다고 말하지 않는다; "New optimiser."(40초 간격으로 두 번)는 둘 중 첫 번째가 컴파일되지 않는다는 것도, 진짜 변화가 정리 패스를 추상화 안으로 합치는 것이지 새 규칙을 추가하는 것이 아니라는 것도 말하지 않는다.
• 표현에 관한 실험은 브랜치가 아니라 메인라인 위 커밋으로 일어난다: 648aeef0은 eval.c의 기존 #if/#elif 사슬에 NODE_INDEX를 세 번째 옵션으로 추가하고 #define 하나를 바꿔 그것을 활성화한다; NODE_NAIVE(1장의 표현)는 파일에 그대로 남아 컴파일은 되지만 선택되지 않을 뿐이다.
• 적용되고 정직하게 표시된 임시방편: 17587b2d는 diff를 열어 보기도 전에 이미 커밋 메시지가 말해 준다. 그것이 임시방편으로 피해 가는 것 — 독립적으로 컴파일된 최상위 정의들을 진입점을 아는 하나의 실행 가능한 그래프로 만드는 것 — 은 이 범위가 끝내 일반적인 해법을 내놓지 않는 실제 문제다.

직접 해보기

기준점: b56ba28b. 관례(00-overview.md 참고):

git worktree add /tmp/mhs-b56ba28b b56ba28b
cd /tmp/mhs-b56ba28b
nix develop $MICROHS -c make test

이것은 여전히 옛 Lam.hs/nfib.comb 파이프라인을 실행한다 — Makefile의 test 타깃은 이 범위 안에서 새 Main.hs/Parse.hs 경로를 빌드하도록 한 번도 갱신되지 않았다(git show b56ba28b:Makefile은 6485a341의 것과 바이트 단위로 동일하다). 1장과 같은 nfib 35 계산을, 새 NODE_INDEX 표현 위에서 기대할 수 있다:

./eval nfib.comb
((Y (((C' C) ((B (S (> 2))) (((C' (C' +)) (((S' (S' +)) ((C B) (-' 1))) ((C B) (-' 2)))) 1))) 1)) 35)
29860703
node size=16, heap size=100000
1045124618 reductions, 1944 GCs

1장에서 본 ccb31388의 node size=24 빌드와 답, 축약 횟수, GC 횟수 모두 같다 — 표현 변경은 계산에는 보이지 않고 노드당 메모리에만 보인다.

빌드 노트: 새 파서 주도 경로(Main.hs)는 이 커밋 시점에 Makefile 타깃이 없으며, 이 프로젝트의 flake 툴체인(GHC 9.8.4, mtl 2.3.1)으로 빌드하려면 한 줄이 필요하다. 쓰인 그대로 빌드하면 실패한다:

nix develop $MICROHS -c ghc Main.hs -o uhs

ParserComb.hs:52:11: error: [GHC-88464]
    Variable not in scope:
      ap :: Prsr s (a -> b) -> Prsr s a -> Prsr s b
    Suggested fix: Perhaps use ‘map’ (imported from Data.List)
   |
52 |   (<*>) = ap
   |           ^^

ap(ParserComb.hs의 Applicative 인스턴스에서 쓰임, aux/parser-combinators.md 2절)은 이 GHC/mtl 조합에서 ParserComb.hs 자신의 임포트 어디로도 스코프에 들어오지 않는다 — Control.Monad를 명시적으로 임포트해야 한다. ParserComb.hs의 기존 import Control.Monad.State.Strict 뒤에 한 줄을 추가한다:

import Control.Monad(ap)

그러면 빌드가 성공한다:

nix develop $MICROHS -c ghc Main.hs -o uhs

[1 of 6] Compiling ParserComb       ( ParserComb.hs, ParserComb.o )
[2 of 6] Compiling Parse            ( Parse.hs, Parse.o )
[3 of 6] Compiling Exp              ( Exp.hs, Exp.o )
[4 of 6] Compiling Desugar          ( Desugar.hs, Desugar.o )
[5 of 6] Compiling Main             ( Main.hs, Main.o )
[6 of 6] Linking uhs

(Parse.hs:203의 부분 함수 tail에 대한 GHC 경고도 나타난다 — 1장이 Lam.hs에서 짚었던 것과 같은 종류의 부분성이다; 여기서는 무해하며 위에서는 생략했다.) 아래 연습 문제들 전에 이 한 줄짜리 패치를 적용해 둔다.

연습 문제 1: 받아들여지는 문법으로 작은 프로그램 만들어 보기

cat > pair.hs <<'EOF'
module Pair where
f x = x
main = f 3
EOF
./uhs pair.hs

f = I
main = f 3
((T :0 I) ((T :1 (_0 3)) _1))

첫 두 줄은 ds'다(각 정의의 컴파일되고 최적화된 형태 — f x = x는 항등 컴비네이터 I로 축약되는데, 정확히 aux/bracket-abstraction.md 1절이 다루는 (\x. x) = I 사례다). 세 번째 줄은 17587b2d가 링크한 프로그램으로, 표준 출력뿐 아니라 out.comb에도 쓰인다. 실행해 보자:

nix develop $MICROHS -c ./eval out.comb

3
node size=16, heap size=100000
14 reductions, 0 GCs

예상대로 3이다. 해 볼 만한 가치가 있고, 의존하기 전에 17587b2d의 임시방편에 대해 알아 둘 가치도 있는 실험: pair.hs에서 선언 순서를 바꿔 — f x = x보다 main = f 3을 먼저 — 다시 빌드해 보자:

cat > fwd.hs <<'EOF'
module Fwd where
main = f 3
f x = x
EOF
./uhs fwd.hs
nix develop $MICROHS -c ./eval out.comb

ERR: shared == NIL

레이블은 소스 순서대로 매겨지므로(zip ds' [0..]), 이 파일에서 첫 번째인 main이 이제 레이블 0이 되어, 레이블 1인 f를 _1로 참조하는데, 출력 텍스트에 :1이 등장하기도 전에 그렇게 된다. b0c33a8f의 파서는 전방 선언 지원이 전혀 없는 단일한 좌에서 우로의 패스다 — 레이블은 텍스트 안에서 필요해지기 전이 아니라 참조되기 전에 정의되어 있어야 한다. 17587b2d의 "임시방편"은 이 제약을 조용히 물려받는다 — C 수준의 ERR 위에서 이를 잡거나 보고하는 것은 아무것도 없다. (계속하기 전에 main 앞에 f를 다시 놓거나, 그냥 다시 pair.hs를 쓴다.)

연습 문제 2: 파스 오류 일으켜 보기

cat > bad.hs <<'EOF'
module Bad where
main = )
EOF
./uhs bad.hs

실제 동작: 잡히지 않은 하스켈 예외가 모두 stderr로, 종료 코드 1 (parseDie, a9178695:Parse.hs 85행: Left err -> error err):

uhs: line 2, col 7:
   found: ")"
   expeced: = white-space
   expeced: lower case
   expeced: upper case
   expeced: int digit
   expeced: '('
   expeced: \ symbol
   expeced: case letter, digit
   expeced: case <empty>

CallStack (from HasCallStack):
  error, called at ./Parse.hs:85:17 in main:Parse

문자 그대로 읽으면: 실제 소스에서 expeced는 철자가 틀려 있다 (formatFailed, a9178695:ParserComb.hs 109행: pr e = " expeced: " ++ e) — 여기서 전사(transcription) 실수가 아니라, 실제로 실행 중인 바이너리가 정말로 그렇게 출력한다. 목록은 가장 멀리 나아간 지점(7열, main = 바로 뒤)에서 시도되어 실패한 모든 대안이며, <?>의 레이블링과 LastFail의 longest를 통해 합쳐진 것이다. "case <empty>"는 구체적으로 확인 가능한 지점으로 거슬러 올라간다: pExpr의 세 번째 대안인 pCase는 pKeyword "case"로 시작한다(a9178695:Parse.hs, 98–102행, 전문 인용):

pKeyword kw = (skipWhite $ do
  s <- pIdentRest
  guard (kw == s)
  pure ()
  ) <?> kw

)에 대해서는 pIdentRest가 문자를 0개 읽고()는 글자도 숫자도 아니므로), 그래서 s = "", guard ("case" == "")는 guard False이며, 이는 Alternative의 empty이고(guard는 ParserComb.hs 자신의 것이 아니라 Control.Monad의 것이다), <?> "case"는 empty 자신의 "<empty>" 메시지 앞에 "case"를 붙인다 — unwords ["case", "<empty>"]다. 의도적으로 설계된 것이 아니라, 이틀 된 오류 보고 패스의 정직한 부산물이다(empty의 문자 그대로의 자리표시자 텍스트가 실제 오류 메시지로 새어 나온 것).

연습 문제 3: 최적화기, 전과 후

9cf1e937~1..9cf1e937(첫 번째 "New optimiser." 커밋의 문자 그대로의 양 끝점)는 빌드되지 않는다 — 위 "무슨 일이 있었나"에서 이미 확인했다: 9cf1e937 혼자서는 71729105의 오타에서 물려받은 파스 오류로 실패하며, 그 자신의 diff 때문에 그렇지 않았다면 드러났을 Lbl이-스코프에-없음 문제가 나타날 기회조차 갖지 못한다. 이 쌍도, 71729105/9cf1e937/ b4e44ded의 어떤 조합도 재작성 양쪽에 빌드 가능한 Main.hs 바이너리 두 개를 내놓지 않는다: b4e44ded 자신의 Exp.hs는 빌드되지만, 그 커밋 시점에 나란히 있는 Main.hs는 여전히 옛날의, 이제는 제거된 improve 함수를 호출해 Variable not in scope: improve로 실패한다.

빌드 노트: 관련 코드(Exp.hs의 compile/improve/compileOpt)가 그 자체로 파싱되고 타입 검사되는 가장 가까운 커밋 쌍 — a9178695(재작성 전; 원래의 2패스 improveC/improveT)와 b4e44ded(재작성 후; 합쳐진 스마트 생성자 버전) — 로 대신하고, ap 패치가 이 범위의 모든 커밋에서 필요하며 실제로 바뀐 부분이 아닌 전체 Main.hs 파이프라인을 거치는 대신 aux/bracket-abstraction.md 2절과 같은 방식으로 ghci/ghc -e로 Exp.hs 위에서 직접 비교한다.

git worktree add /tmp/mhs-a9178695 a9178695
cd /tmp/mhs-a9178695

위와 같은 한 줄짜리 ParserComb.hs 수정(import Control.Monad(ap), 여기서도 필요하다. Exp.hs가 ParserComb를 임포트하는 Parse를 임포트하기 때문이다)을 적용한 다음:

nix develop $MICROHS -c ghc -e 'let epair = Lam "x" (Lam "y" (Lam "f" (App2 (Var "f") (Var "x") (Var "y")))) in putStrLn (toString (compile epair)) >> putStrLn (toString (improve (compile epair)))' Exp.hs

S (K C) (S (S (K C) (K I)) I)
P

epair은 \x. \y. \f. f x y — pair 함수이며, Pair 규칙이 매치하는 정확한 형태다. 나이브한 compile만으로는 이것을 축약하지 못한다; P에 도달하려면 별도의 improve 호출이 필요하다. 두 번째 워크트리:

git worktree add /tmp/mhs-b4e44ded b4e44ded
cd /tmp/mhs-b4e44ded

같은 한 줄짜리 수정을 적용한 다음:

nix develop $MICROHS -c ghc -e 'let epair = Lam "x" (Lam "y" (Lam "f" (App2 (Var "f") (Var "x") (Var "y")))) in putStrLn (toString (compile epair)) >> putStrLn (toString (compileOpt epair))' Exp.hs

P
P

compile만으로 이미 P를 만들어 낸다 — "무슨 일이 있었나"가 diff를 읽고 설명한 그대로, 추상화 단계와 최적화가 이제 두 패스가 아니라 한 패스다; 같은 입력을 재작성 양쪽에서 실행해 보면 diff의 모양이 아니라 그 의미를 확인할 수 있다.

끝나면 워크트리 세 개를 모두 정리한다:

git worktree remove --force /tmp/mhs-b56ba28b
git worktree remove --force /tmp/mhs-a9178695
git worktree remove --force /tmp/mhs-b4e44ded