01 — The seed (씨앗)

현재 위치

아무것도 없다. 이 커밋은 ccb31388, "First version,"(첫 버전) 2023-05-25 19:33:17 +0200 — 저장소의 첫 커밋이다. 가정할 이전 상태가 없다. 이 장의 모든 내용은 이 커밋 하나에서 그대로 읽어낸 것이다.

네 개의 파일이 함께 도착한다: .gitignore, Lam.hs(하스켈 227줄), Makefile(14줄), eval.c(C 539줄) — 총 786줄(커밋 통계는 00-overview.md 참고). 코드가 정당화하는 만큼만 읽으면, 코드가 보여주는 것은 이렇다: 작성자는 작은 하스켈류 언어에서 컴비네이터로 내려가는 컴파일러와, 한 개의 C 파일에 들어갈 만큼 작은 런타임을 원하며, 이 세션이 끝나기 전에 둘을 함께 동작시키고 싶어한다. 파서도, 타입 검사기도, 모듈 시스템도, 이름값 하는 오류 처리도 없다 — 그저 하드코딩된 람다 항 하나를 컴파일하고 실행할 만큼의 장치만 있을 뿐이다.

무슨 일이 있었나

이 커밋은 두 개의 파일로 이루어진 구조와, 그 사이에 놓인 세 번째 산출물 — 텍스트 파일 하나 — 로 구성된다.

`Lam.hs`: 파서 없는 컴파일러

Lam.hs는 Exp AST(Var, App, Lam, Int, Comb, Prim — 각 생성자의 역할은 aux/lambda-calculus-and-ski.md 참고)와, Var/Lam을 포함한 Exp 항을 순수 컴비네이터 항으로 바꾸는 브래킷 추상화 컴파일러(유도 과정은 aux/bracket-abstraction.md 참고), 컴비네이터 출력을 줄여주는 키셀료프(Kiselyov) 스타일의 improve 패스, 프리티 프린터, 그리고 — 파일 맨 아래에 — 하드코딩된 프로그램 하나, nfib 35를 계산하는 eNfib를 정의한다. readFile도 없고, Makefile이 넘겨주는 것 이상의 getArgs 파싱도 없으며, 소스 언어를 위한 렉서나 파서도 전혀 없다. 이 커밋의 모든 예제는 Lam.hs 안에서 손으로 직접 Exp 값으로 만들어 넣은 하스켈 소스다.

전체 파이프라인은 Makefile 하나에 다 들어갈 만큼 작다. 전문을 그대로 인용한다(ccb31388:Makefile):

test:	eval nfib.comb
	./eval nfib.comb

eval:	eval.c
	gcc -O3 eval.c -o eval

nfib.comb:	Lam
	./Lam > nfib.comb

Lam:	Lam.hs
	ghc Lam.hs -o Lam

clean:
	rm -f *.hi *.o eval Lam

아래에서 위로 읽으면 이야기의 전부다. ghc가 Lam.hs를 Lam 바이너리로 컴파일하고, Lam을 실행해 표준 출력을 리다이렉트하면 텍스트 파일 nfib.comb가 생기고, gcc가 eval.c를 eval 바이너리로 컴파일하며, eval을 nfib.comb에 대해 실행하는 것이 실제 프로그램이다. 서로 무관한 두 개의 툴체인(GHC와 C 컴파일러)이 텍스트 파일 하나에서 만난다.

컴파일러 본체는 compile이며, 모든 Lam에 대해 abstract로 위임한다. 전문을 그대로 인용한다(ccb31388:Lam.hs, 97–101행 — 그 위의 compile은 생성자당 한 줄씩이며 aux/bracket-abstraction.md 1절에서 다룬다):

abstract :: Ident -> Exp -> Exp
abstract x e@(Var y) | x == y = CI
abstract x (App f a) = App2 CS (abstract x f) (abstract x a)
abstract x (Lam y e) = abstract x $ improveC $ abstract y e
abstract x e = App CK e

네 개의 식뿐, 이름 테이블로의 재귀도 없고 환경도 없다 — 설계상 그렇다. 왜 그런지는 aux 문서가 짚어준다. Lam.hs는 이 커밋에서 227줄을 넘지 않으며, 그 길이의 대부분은 프리티 프린터와 improve/improveC/improveT 재작성 규칙 (aux/bracket-abstraction.md 3절), 참조용 축약기 reduce/redOne, 그리고 eNfib를 읽기 좋은 형태로 작성하기 위한 작은 컴비네이터 조립 DSL(ToLam, $$, comp)이 차지한다.

`eval.c`: 런타임

eval.c는 독립적인 C 프로그램이다. 고정 크기의 셀 힙, 노드 태그에 대한 스위치문으로 구현된 모든 컴비네이터 축약 규칙, 명시적인 스파인 스택, 그리고 제자리 갱신을 위해 간접 노드를 사용하는 진짜 마크-스캔 가비지 컬렉션으로 이루어져 있다. 여기서는 더 요약하지 않는다 — aux/graph-reduction-and-laziness.md가 셀 표현, 스파인 순회, 공유, GC를 줄 단위 인용과 함께 상세히 다루고, aux/y-combinator-and-recursion.md가 Y가 재귀를 위해 진짜로 순환하는 그래프를 어떻게 만드는지 다룬다. 둘 다 바로 이 커밋을 기준으로 검증했으므로, 여기서 중복할 이유가 없다.

`.comb` 파일: 읽을 수 있는 텍스트 인터페이스

nfib.comb — Lam이 쓰고 eval이 읽는 파일 — 은 평범한 텍스트로, 한 줄짜리이며 사람이 읽을 수 있는 컴비네이터 구문이다. 이 커밋 시점의 워크트리에서 새로 생성해 보면 이렇게 나온다(파일 전체이며, 정말로 한 줄이다):

((Y (((C' C) ((B (S (> 2))) (((C' (C' +)) (((S' (S' +)) ((C B) (-' 1))) ((C B) (-' 2)))) 1))) 1)) 35)

이것은 압축된 바이너리 덩어리가 아니다 — S/K/I/B/C/S'/C' 등이 왼쪽부터 오른쪽으로 괄호로 묶여 있으며, eval.c의 pretty()가 찍어내고 같은 파일의 parse()가 다시 읽어들인다(둘 다 aux 문서에서 다룬다). 서로 무관한 두 프로그램 사이의 교환 형식으로 평문 텍스트를 택한 것 자체가 눈여겨볼 만한 결정이다. 이 덕분에 중간 표현을 cat으로 볼 수 있고, 두 버전을 diff할 수 있고, 두 컴파일러 중 어느 쪽도 없이 테스트 케이스를 손으로 작성할 수 있다.

`main` 안의 주석 처리된 블록

main은 배포되는 eNfib-출력 한 줄만으로 이루어져 있지 않다. ccb31388:Lam.hs의 8–30행은 실행되는 그 줄 바로 위에 놓인 {- ... -} 주석 블록이다:

main :: IO ()
main = do
{-
  let c1 = compile e1
      c1' = improve c1
      r1' = reduce (App c1 (Var "k"))
      r1'' = reduce (App c1 (Int 5))
  pp e1
  pp c1
  ...
  pp $ improve $ compile $ App (Lam "x" (App2 (Var "x") (Int 10) (Int 2))) (Prim "-")
-}
  putStrLn $ toStringP $ eNfib `App` 35

이 블록은 e1, e2, e3(main 아래 몇 줄에 손으로 작성된 세 개의 작은 테스트 항)를 다루는 21줄짜리 pp/let 호출로, 이들을 컴파일하고, 개선하고, 축약하고, 모든 중간 결과를 출력한다. 이것은 못 쓰게 되어 버려진 코드가 아니다 — main 안에 붙여넣은 뒤 지우지 않고 주석 처리만 한 REPL 세션이며, 그래서 여전히 그 자리에 있고, 여전히 올바르며, 여전히 실행할 수 있다 — "직접 해보기" 절 참고.

커밋 2: "Clean more"(더 정리하기)

21168890은 ccb31388 30초 뒤에 작성(및 커밋)되었다 — 같은 날, 30초 차이의 두 타임스탬프 — 그리고 Makefile의 정확히 한 줄만 바꾼다:

 clean:
-	rm -f *.hi *.o eval Lam
+	rm -f *.hi *.o eval Lam *.comb

이것이 diff의 전부다. make clean이 생성된 nfib.comb를 지우지 않고 있었는데, 첫 버전을 커밋한 지 30초 만에 이를 알아채고 고쳤다. 이 커밋에서 바뀐 것은 이것뿐이다.

`B'` 공백

이 커밋에서 배포되어 그대로 남는 미해결 사항이 하나 있다. eval.c는 BB 태그(B'로 출력됨)를 선언하고, 파서는 B' 구문을 받아들이며, pretty()도 이를 출력할 줄 안다 — 하지만 eval의 스위치문에는 case BB:가 없어서, B' 노드가 런타임에 도달하면 bad tag 12로 멎는다. 이것이 문제가 되지 않는 이유는, Lam.hs의 redOne이 이 규칙을 올바르게 구현하고 있음에도 improveC가 이 커밋에서는 B'를 전혀 발생시키지 않기 때문이다. aux/lambda-calculus-and-ski.md 5절에서 검증된 충돌을, aux/bracket-abstraction.md 4절에서 compile/improve가 왜 이를 유발하지 않는지를 다룬다.

왜 중요한가

이 책의 나머지 전부는 이 두 파일, 혹은 그 사이의 형식이 자라나는 과정이다. 나흘 뒤 등장하는 파서(2장)는 main 안에 손으로 만든 Exp 값들을 대체하고, 개선된 노드 표현과 최적화기는 eval.c의 태그 스위치와 improve의 재작성 규칙을 확장하며, 이후의 셀프 호스팅 작업은 파이프라인의 모양을 한 번도 바꾸지 않은 채 Lam.hs 자체를 모듈 단위로 대체해 나간다. .comb 파일을 통한 인계 — 텍스트 형식으로 컴파일한 뒤, 별도의 프로그램으로 그 텍스트 형식을 실행하는 것 — 은 두 달 뒤의 부트스트랩이 사용하는 것과 같은 모양이며, 한쪽에 훨씬 큰 컴파일러가 있을 뿐이다. 파서 대신 하드코딩된 프로그램으로 시작한 것이야말로 첫날이 처음부터 끝까지 실제로 동작하는 무언가로 끝나게 만드는 이유다: 그날 아침에는 존재하지 않았던 그래프 축약 기계가 실제로 계산해 낸 nfib 35.

실험 노트 여백

커밋 1과 2에서 이미 드러나는 습관들:

탐색적으로 작성한 코드는 지우지 않고 주석 처리한다. main 안의 e1/e2/e3 스크래치 블록은 파일에 온전히 기능하는 채로 남아 있으며, 다만 기본으로는 실행되지 않을 뿐이다.
"Clean more"(더 정리하기)는 "First version"(첫 버전) 30초 뒤에 도착한다 — 나중에 정리를 몰아서 하는 대신, 같은 세션에서 make clean의 누락을 즉시 고친다.
하스켈 쪽과 C 쪽 사이의 인터페이스는 눈으로 읽을 수 있는 텍스트 파일이지, 직렬화된 바이너리 형식이 아니다.
이 커밋은 모든 컴비네이터가 끝까지 연결되기를 기다리지 않고, 알려진 충돌 케이스(B')를 그대로 안은 채 배포된다. 아직 그 경로에 도달할 수 없기 때문에 배포를 막지 않는다.

직접 해보기

이 책 전체에서 쓰는 관례: 커밋을 자신만의 워크트리로 체크아웃한다.

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

($MICROHS는 최상위 README.md의 안내대로 한 번 설정해 둔, 여러분의 클론의 절대 경로다.) GHC 컴파일에서 무해한 경고 하나가 뜨고, 이어서 프로그램 출력이 나올 것이다:

Lam.hs:211:13: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘head’
    ...
./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=24, heap size=100000
1045124618 reductions, 1944 GCs

29860703이 nfib 35다. 경고는 Data.List.\\가 부분 함수 head를 211행에서 사용하는 것에 관한 것이다(새 변수 이름을 고르는 데 쓰이는 \\의 한 버전) — 이 커밋의 용례에서는 빼는 대상 리스트가 항상 비어 있지 않으므로 여기서는 무해하지만, 실제로 부분성이 있는 함수이니 GHC가 지적하는 것이 옳다.

연습 문제 1: 주석 처리된 실험 실행해 보기

Lam.hs를 열어 주석 표시 두 개만 지운다: 8행의 {-와 30행의 -}. 그 사이는 그대로 둔다. 그런 다음:

nix develop $MICROHS -c make Lam
nix develop $MICROHS -c ./Lam

이렇게 하면 16줄이 출력된다 — 블록 자체의 pp/putStrLn 호출들에 이어 평소의 nfib 항이 나온다. 첫 세 줄은 e1 = \x. + x x에 compile/improve를 적용한 결과다:

(\x. + x x)
S (S (K +) I) I
S + I

— aux/bracket-abstraction.md 2절이 손으로 유도한 compile e1, 3절의 improve (compile e1)과 정확히 일치하지만, 이번에는 (ghci가 아니라) 독립적인 두 번째 방식으로 재확인된 것이다. 좀 더 아래(실행의 14번째 줄)에서 pp $ improve $ compile e3는 다음을 출력한다:

— aux/bracket-abstraction.md 5절이 ghci로 확인하기 전에 손으로 예측해 보라고 한 것과 같은 답이다. 여기서는 같은 계산을 ghci 대신 컴파일된 Lam 바이너리 안에서 인라인으로 수행한 것일 뿐이다. (다음으로 넘어가기 전에 {-/-}를 다시 붙여 놓는다 — 다음 두 연습 문제가 nfib.comb를 다시 생성하는데, 주석을 풀어놓은 채로 두면 이 블록의 추가 출력도 그 파일에 함께 들어가 버린다. nfib.comb는 그저 Lam의 표준 출력을 리다이렉트한 것이기 때문이다.)

연습 문제 2: 더 작은 `nfib` 실행해 보기

31행을 eNfib \App` 35에서 eNfib `App` 25로 바꾼다. 다시 빌드하기 전에, eNfib자신의 점화식으로부터 답을 예측해 본다 ([aux/y-combinator-and-recursion.md](aux/y-combinator-and-recursion.md) 3절에서 인용):n < 2이면 nfib n = 1, 아니면 nfib(n-1) + nfib(n-2) + 1`. 기저 사례부터 전개하면:

nfib: 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219,
      1973, 3193, 5167, 8361, 13529, 21891, 35421, 57313, 92735,
      150049, 242785
       (n= 0  1  2  3  4   5   6   7   8    9   10   11   12   13   14
            15    16    17    18     19     20     21     22     23
              24      25)

따라서 nfib 25는 242785가 되어야 한다. 다시 빌드해 확인한다:

nix develop $MICROHS -c make test

./eval nfib.comb
((Y (((C' C) ((B (S (> 2))) (((C' (C' +)) (((S' (S' +)) ((C B) (-' 1))) ((C B) (-' 2)))) 1))) 1)) 25)
242785
node size=24, heap size=100000
8497488 reductions, 15 GCs

예측대로 242785다 — 그리고 지나가는 김에 짚어 두자면, 호출 횟수가 대략 피보나치 성장률을 따르는 함수치고는 nfib 35보다 두 자릿수 넘게 적은 축약 횟수다(1,045,124,618 대비 8,497,488). 다음 연습 문제로 넘어가기 전에 31행을 다시 35로 되돌리고 다시 빌드한다 — Lam.hs만 고쳐서는 디스크에 남아 있는 nfib.comb가 재생성되지 않으며, 그 파일은 여전히 25 버전이다:

nix develop $MICROHS -c make test

이제 원래의 ... 35) 항과 29860703이 다시 출력되어야 한다. nfib.comb는 이제 원래 내용으로 되돌아왔다.

연습 문제 3: `improveC`를 부수고 항이 커지는 것을 지켜보기

improveC(ccb31388:Lam.hs, 106–117행)에는 catch-all 앞에 특수 처리된 여섯 개의 패턴 중 하나로 다음이 있다:

    (App CS (App CK e1),     e2)        -> improve (App2 CB e1 e2)

이것은 B를 도입하는 규칙이다 — 왜 존재하는지는 aux/bracket-abstraction.md 4절 참고. 먼저, 나중에 비교할 수 있도록 현재(아직 깨지지 않은) nfib.comb를 저장해 둔다:

cp nfib.comb nfib.comb.orig

그런 다음 improveC의 그 한 줄을 지우고 다시 빌드한다:

nix develop $MICROHS -c make test

./eval nfib.comb
((Y ((C ((S (K C)) ((S (K (S (> 2)))) ((C ((S (K C)) ((S (K (S (K +)))) ((S ((S (K S)) ((S (K (S (K +)))) ((C ((S (K S)) K)) (-' 1))))) ((C ((S (K S)) K)) (-' 2)))))) 1)))) 1)) 35)
29860703
node size=24, heap size=100000
1373651156 reductions, 2542 GCs

여전히 29860703이다 — improve 규칙 하나를 제거해도 프로그램이 계산하는 값은 바뀌지 않는다. 컴파일된 항의 크기와 eval이 이를 축약하는 데 드는 작업량만 바뀔 뿐이다. 편집 직전에 저장해 둔 nfib.comb.orig와 비교하면:

$ nix develop $MICROHS -c diff nfib.comb.orig nfib.comb
1c1
< ((Y (((C' C) ((B (S (> 2))) (((C' (C' +)) (((S' (S' +)) ((C B) (-' 1))) ((C B) (-' 2)))) 1))) 1)) 35)
---
> ((Y ((C ((S (K C)) ((S (K (S (> 2)))) ((C ((S (K C)) ((S (K (S (K +)))) ((S ((S (K S)) ((S (K (S (K +)))) ((C ((S (K S)) K)) (-' 1))))) ((C ((S (K S)) K)) (-' 2)))))) 1)))) 1)) 35)

(diff는 이 프로젝트 자체의 Makefile에는 없지만, nix develop이 넘겨주는 PATH에는 있다. devShell이 호스트와 완전히 격리되어 빌드되지 않기 때문이다.) 한 줄짜리 항은 102바이트에서 181바이트로 커진다 — 빠진 규칙이 만들어 냈을 B 하나하나가 대신 S (K _) _ 형태로 풀려서 나타난다. eval은 그 대가를 치른다: 축약 횟수는 원래의 1,045,124,618 대비 1,373,651,156(31% 증가), GC 횟수는 1,944 대비 2,542(31% 증가) — 재작성 규칙 하나가 빠졌을 뿐인데, 관찰 가능한 동작은 그대로인 함수 하나를 두고 프로그램 텍스트와 런타임 비용이 나란히 3분의 1가량 늘어난다.

끝나면 정리한다:

git worktree remove --force /tmp/mhs-ccb31388

MicroHs에서 배우기 (Learning from MicroHs)