Go 로 읽는 SICP Part 14: 한 줄이 만드는 상수 공간, 그리고 4.2배 빠른 컴파일러
이 글은 Claude Opus 5 를 이용해 초안이 작성되었으며, 이후 퇴고를 거쳤습니다.
시리즈의 마지막 편입니다.
Part 13에서 레지스터 머신을 만들고, save/restore 로 재귀를 구현하고, 반복 기계는 push 를 한 번도 안 한다는 것을 확인했습니다.
이번 편은 그 위에 두 가지를 올립니다.
5.4 명시적 제어 평가기 는 4장의 평가기를 레지스터와 명시적 스택으로 다시 만듭니다. 그러면 시리즈 내내 미룬 꼬리 호출 문제가 코드 한 줄 로 해결됩니다. 실제로 그 한 줄을 빠뜨렸다가 다시 찾았고, 그 과정을 숫자와 함께 싣습니다.
5.5 컴파일러 는 평가기가 실행 중에 하던 일을 미리 해 둡니다. 얼마나 빨라지는지 재 봤습니다.
1. 5.4 — 제어를 코드 밖으로 꺼내기#
4장의 평가기는 이렇게 생겼습니다.
proc, err := Eval(op, env) // Go 함수 호출
args, err := evalOperands(Cdr(x), env)
“연산자를 평가하고, 그 다음에 피연산자를 평가하고, 그 다음에 적용한다” 는 순서가 Go 코드의 순서에 숨어 있습니다. 그리고 “그 다음에 무엇을 할지” 는 Go 의 호출 스택이 기억합니다.
5.4 는 그것을 밖으로 꺼냅니다. 레지스터 몇 개와 스택 하나, 그리고 “지금 어느 단계인가” 를 나타내는 라벨 만 남깁니다.
type ECE struct {
exp any // 평가할 식
env *Env // 환경
val any // 결과
proc any // 적용할 프로시저
argl []any // 모은 인자
unev any // 아직 평가하지 않은 것들
cont ecLabel // 어디로 돌아갈지
stack []any // 명시적 스택
}
레지스터 이름이 원서와 같습니다. exp, env, val, proc, argl, unev, continue.
실행은 라벨을 도는 하나의 루프입니다.
label := evalDispatch
for {
switch label {
case evalDispatch:
// ...
case evAppOperandLoop:
// ...
case applyDispatch:
// ...
}
}
Go 재귀가 한 번도 안 나옵니다. 모든 “다음에 할 일” 이 label 변수와 stack 에 명시적으로 들어 있습니다.
예를 들어 if 는 이렇게 처리됩니다.
case "if":
m.push(m.cont) // 돌아갈 곳을 기억
m.push(m.env)
m.push(x) // 원래 if 식
m.cont = evIfDecide
m.exp = Cadr(x) // 조건부터 평가
label = evalDispatch
조건을 평가하러 가면서 “끝나면 evIfDecide 로 오라” 는 쪽지를 남깁니다. 조건 평가가 끝나면 그 라벨로 돌아와서 가지를 고릅니다.
case evIfDecide:
x := m.pop().(*Pair)
m.env = m.pop().(*Env)
m.cont = m.pop().(ecLabel) // 원래 돌아갈 곳을 되찾는다
if isTrue(m.val) {
m.exp = Caddr(x)
} else {
m.exp = Car(Cdr(Cddr(x)))
}
label = evalDispatch // ★ 여기서 아무것도 push 하지 않는다
마지막 줄이 중요합니다. if 의 가지는 꼬리 위치입니다. 가지를 평가하고 나면 if 가 할 일이 없습니다. 그러니 save 하지 않고 그냥 갑니다.
먼저 4장 평가기와 결과가 같은지 확인했습니다. 열두 가지 프로그램(재귀, 클로저 상태, 고차 함수, let, cond, set! 등)이 전부 일치했습니다.
2. 꼬리 재귀 — 한 줄이 전부입니다#
이제 시리즈 내내 미룬 질문입니다.
프로시저 본문을 평가하는 곳이 evSequence 입니다. 본문의 마지막 식 을 평가할 때 무엇을 해야 하는가.
처음에는 이렇게 썼습니다.
if Cdr(m.unev) == nil {
m.exp = Car(m.unev)
m.cont = returnToCaller // 끝나면 스택에서 cont 를 꺼내 돌아가자
label = evalDispatch
}
말이 되어 보입니다. 그리고 답도 맞게 나왔습니다. 그런데 스택 깊이를 재 보니 이랬습니다.
(a) 꼬리 재귀 루프
n=10 최대 스택 깊이=20
n=100 최대 스택 깊이=110
n=1000 최대 스택 깊이=1010
n=10000 최대 스택 깊이=10010
n=100000 최대 스택 깊이=100010
깊이가 n 에 비례합니다. 꼬리 재귀인데 상수 공간이 아닙니다.
원인을 찾아보니 이랬습니다. 위 코드는 호출자의 continue 를 스택에 그대로 둔 채 본문 마지막 식을 평가하러 갑니다. 그런데 그 마지막 식이 또 프로시저 호출이면, 그 호출이 자기 continue 를 또 push 합니다. 한 번 돌 때마다 하나씩 쌓입니다.
원서 5.4.2 의 컨트롤러를 다시 보면 답이 있습니다.
ev-sequence-last-exp
(restore continue)
(goto (label eval-dispatch))
(restore continue). 마지막 식으로 가기 전에 호출자의 continue 를 스택에서 꺼내 레지스터로 되돌립니다. 그러면 스택은 호출자 시점으로 돌아가고, 다음 호출이 push 하는 것과 상쇄됩니다.
Go 로 한 줄입니다.
if Cdr(m.unev) == nil {
m.cont = m.pop().(ecLabel) // ★ 이 한 줄
m.exp = Car(m.unev)
label = evalDispatch
}
다시 재 봤습니다.
(a) 꼬리 재귀 루프 — 돌아와서 할 일이 없다
n=10 최대 스택 깊이=10 push 총계=495 명령 단계=351
n=100 최대 스택 깊이=10 push 총계=4725 명령 단계=3321
n=1000 최대 스택 깊이=10 push 총계=47025 명령 단계=33021
n=10000 최대 스택 깊이=10 push 총계=470025 명령 단계=330021
n=100000 최대 스택 깊이=10 push 총계=4700025 명령 단계=3300021
(b) 비꼬리 재귀 (계승) — 돌아와서 곱해야 한다
n=10 최대 스택 깊이=55
n=100 최대 스택 깊이=505
n=1000 최대 스택 깊이=5005
n=10000 최대 스택 깊이=50005
깊이 10. n 이 만 배로 늘어도 10.
push 총계는 여전히 n 에 비례해 늘어납니다. 인자를 평가하느라 넣었다 빼는 것들입니다. 하지만 동시에 쌓여 있는 최대 개수 는 상수입니다. 그것이 공간 복잡도입니다.
그리고 (b)를 보면 대비가 분명합니다. 계승은 “돌아와서 곱해야” 하므로 깊이가 n 에 비례합니다. 같은 평가기, 같은 규칙인데 프로그램의 모양이 공간 복잡도를 정합니다.
Part 2에서 이렇게 썼습니다. “재귀적으로 생긴 프로시저와 재귀적으로 동작하는 프로세스는 다르다. 그런데 Go 에서는 이 구분이 지워진다.” 그 구분을 우리 손으로 되살렸습니다. 되살리는 데 든 것은 m.pop() 한 번이었습니다.
이게 5.4.2 의 요점입니다.
꼬리 재귀는 언어의 마법이 아니라 평가기의 구현 세부 다. 어디서
save를 생략하느냐의 문제다.
3. 그런데 명시적 제어 평가기는 느립니다#
같은 fib(22) 를 네 가지로 돌려 봤습니다.
BenchmarkECE-14 94 36202102 ns/op 49436676 B/op 1257002 allocs/op
BenchmarkDirectEval-14 139 25740125 ns/op 41845789 B/op 877693 allocs/op
BenchmarkAnalyzeEval-14 236 15043670 ns/op 27175023 B/op 419245 allocs/op
BenchmarkCompiled-14 607 5949990 ns/op 8834744 B/op 304619 allocs/op
명시적 제어 평가기가 가장 느립니다. 직접 평가보다 1.4배 느립니다.
당연합니다. Go 의 호출 스택이 공짜로 해 주던 일(레지스터 저장, 복귀 주소 관리)을 슬라이스에 손으로 넣었다 빼기 때문입니다. 할당 횟수가 125만 회로 가장 많습니다.
원서도 5.4 를 빠른 구현으로 제시하지 않습니다. 이 평가기의 목적은 모델 입니다. 4장에서 “그냥 되는 것” 으로 두었던 제어 흐름을 전부 드러내 보이는 것입니다. 그리고 그렇게 드러내고 나니 꼬리 호출을 다룰 자리가 생겼습니다.
속도는 다음 절에서 되찾습니다.
4. 5.5 — 컴파일러, 그리고 이름이 사라지는 순간#
Part 11의 구문 분석기는 “무엇을 할지” 를 미리 정했습니다. 그런데 아직 실행 중에 하는 일이 하나 남아 있습니다. 변수를 이름으로 찾는 것 입니다.
func (e *Env) Lookup(s Symbol) (any, error) {
for env := e; env != nil; env = env.parent {
if v, ok := env.vars[s]; ok { return v, nil }
}
// ...
}
fib 본문에서 n 을 볼 때마다 맵 조회를 합니다. 그런데 n 이 어느 프레임 어느 자리에 있는지는 소스만 보면 알 수 있습니다. 실행 중에 알아낼 이유가 없습니다.
원서 5.5.6 의 어휘 주소 지정(lexical addressing) 이 이 일을 합니다. 컴파일 시점에 이름을 (프레임 번호, 칸 번호) 두 정수로 바꿉니다.
type CEnv struct { // 컴파일 시점 환경: 이름의 위치만 안다
names []Symbol
parent *CEnv
}
case Symbol:
if f, i, ok := ce.lookup(x); ok {
// ★ 이름이 사라지고 정수 두 개만 남는다
return func(r *RFrame) (any, error) { return r.at(f, i), nil }, nil
}
실행 시점 프레임도 맵이 아니라 슬라이스 가 됩니다.
type RFrame struct {
vals []any
parent *RFrame
}
func (r *RFrame) at(frame, idx int) any {
for i := 0; i < frame; i++ { r = r.parent }
return r.vals[idx]
}
맵 해싱이 포인터 몇 번 따라가기와 배열 인덱싱으로 바뀝니다.
여기에 하나를 더 얹었습니다. 전역 이름(원시 프로시저)은 컴파일 시점에 값을 확정 합니다. + 를 볼 때마다 찾는 대신, 컴파일할 때 이미 그 프로시저를 손에 넣습니다.
결과입니다.
BenchmarkCompiled-14 607 5949990 ns/op 8834744 B/op 304619 allocs/op
| 방식 | 시간 | 직접 평가 대비 | 할당 바이트 |
|---|---|---|---|
| 5.4 명시적 제어 | 36.1 ms | 0.71배 | 49.4 MB |
| 4.1 직접 평가 | 25.4 ms | 1.00배 | 41.8 MB |
| 4.1.7 구문 분석 | 14.8 ms | 1.72배 | 27.2 MB |
| 5.5 컴파일 | 6.0 ms | 4.2배 | 8.8 MB |
해석 대비 4.2배, 구문 분석 대비 2.5배 빠릅니다. 메모리는 5분의 1입니다.
그리고 이게 컴파일이 무엇인지에 대한 가장 정직한 설명입니다.
컴파일이란 실행할 때마다 하던 일 중 소스만 보고 알 수 있는 것을 미리 해 두는 것 이다.
기계어를 뽑느냐 아니냐는 부차적입니다. 4.1.7 은 “무엇을 할지” 를 미리 정했고, 5.5 는 거기에 “값이 어디 있는지” 까지 미리 정했습니다. 각 단계가 얼마씩 벌었는지가 위 표입니다.
5. 이 글의 컴파일러가 하지 않은 것#
정직하게 밝힐 것이 있습니다. 이 글의 컴파일러는 꼬리 호출을 처리하지 않습니다.
네 가지 방식으로 100만 번짜리 꼬리 재귀 루프를 돌리고 호스트 스택을 재 봤습니다.
4.1 직접 평가 호스트 스택 0.47 MB
4.1.7 구문 분석 호스트 스택 512.66 MB
5.4 명시적 제어 호스트 스택 0.66 MB
5.5 컴파일 (이 글의 판) 호스트 스택 256.66 MB
속도가 빠른 두 방식이 공간에서 집니다. 이유는 같습니다. 컴파일된 코드가 프로시저를 부를 때 Go 함수 호출을 쓰기 때문입니다.
case *CProc:
return p.body(&RFrame{vals: args, parent: p.frame}) // Go 호출 = 스택 한 칸
원서 5.5 의 컴파일러는 이 문제를 처리합니다. compile 이 식마다 연결 방식(linkage) 을 함께 받기 때문입니다. next(다음 명령어로), return(호출자에게), 또는 특정 라벨. 꼬리 위치의 호출은 linkage = 'return 으로 컴파일되고, 그러면 save continue 없이 (goto (reg continue)) 만 남습니다. 2절에서 손으로 한 restore continue 를 컴파일러가 자동으로 하는 것입니다.
제대로 하려면 이 글의 컴파일러를 명시적 명령어 목록 을 뽑는 형태로 다시 써야 합니다. Go 클로저 트리로는 “꼬리 위치니까 프레임을 재활용해라” 를 표현할 자리가 없습니다. Part 11에서 구문 분석 평가기가 같은 이유로 꼬리 호출을 잃었던 것과 정확히 같은 벽입니다.
즉 이 표의 마지막 두 줄은 원서의 한계가 아니라 이 글의 구현이 멈춘 지점입니다. 원서를 끝까지 따라가면 속도와 공간을 둘 다 가질 수 있습니다.
6. 시리즈 총결산 — Go 는 SICP 에 적합했는가#
Part 1에서 마찰 세 곳을 예고했습니다. 열네 편을 지나온 지금 결산합니다.
마찰 1 — 꼬리 호출 최적화 없음#
예고한 대로 아팠고, 예고한 것보다 자주 나왔습니다.
| 어디서 | 증상 |
|---|---|
| Part 2 | 꼬리 재귀 100만 번에 16.25 MB. 루프는 0.25 MB |
| Part 11 | 구문 분석 평가기가 512 MB |
| Part 12 | amb 의 CPS 사슬이 256 MB |
| Part 14 | 컴파일된 코드가 256 MB |
네 번 나왔습니다. 그리고 네 번 다 같은 원인이었습니다.
그런데 이게 손해였느냐 하면, 아닙니다. 이 마찰이 없었다면 5.4.2 의 (restore continue) 한 줄이 무엇인지 끝까지 몰랐을 것입니다. Scheme 으로 읽으면 그 줄은 그냥 지나가는 최적화입니다. Go 로 읽으면 그 한 줄이 512 MB 와 0.66 MB 를 가릅니다.
마찰 2 — 프로그램이 데이터가 아님#
예고한 대로 비용이 들었고, 예고한 것보다 값을 했습니다.
렉서와 파서 171줄이 순수한 추가 비용이었습니다. 그런데 그 파서를 4장에서 만들어 두니 5장의 기계 기술 언어를 공짜로 읽었습니다. 그리고 파싱을 직접 해 본 덕에 “프로그램이 곧 데이터” 라는 말이 언어가 주는 선물이지 계산의 본질이 아니라는 것 이 분명해졌습니다.
마찰 3 — 일급 연속 없음#
예고가 빗나갔습니다. 문제가 되지 않았습니다.
amb 평가기가 필요로 한 연속은 우리가 만든 인터프리터 안의 것이었고, Go 클로저로 충분했습니다. call/cc 를 쓸 자리가 없었습니다.
대신 값은 마찰 1 쪽으로 청구되었습니다. CPS 사슬이 호스트 스택을 먹었습니다.
그리고 궁합이 좋았던 곳#
| 어디서 | 무엇이 |
|---|---|
| Part 6 (2.4~2.5) | 데이터 지향 프로그래밍이 Go 인터페이스 설계 지침 그 자체 |
| Part 7 (3.2) | 환경 모델이 moved to heap 으로 실측 가능 |
| Part 8 (3.3.4) | 회로 시뮬레이터가 이벤트 루프. Go 로 자연스러움 |
| Part 9 (3.4) | 동시성을 실제로 실행. 원서는 사고 실험에 머묾 |
| Part 13 (5장) | 레지스터 머신 시뮬레이터는 Go 가 잘하는 일 |
특히 Part 9 는 Go 가 원서를 넘어선 유일한 대목 입니다. 1000번 인출 중 900건 가까이가 사라지는 것을 재현하고 -race 로 잡아낸 것은 1996년 Scheme 으로는 할 수 없는 일입니다.
최종 판정#
Go 는 SICP 를 읽기에 좋은 언어입니다. 최적은 아니지만, 최적이 아니라서 좋습니다.
Part 1 에서 대안으로 Python(접근성)과 OCaml(4~5장 충실도)을 꼽았습니다. 그 판단은 지금도 유지합니다. 둘 다 Go 보다 마찰이 적습니다.
그런데 열네 편을 쓰고 나서 보니, 마찰이 적은 것이 반드시 좋은 것은 아니었습니다. 이 시리즈에서 가장 배운 것이 나온 자리는 전부 Go 가 막힌 자리였습니다. 꼬리 호출, 파서, 타입 시스템의 천장, GC 의 루트 집합.
없는 것을 손으로 만들어 봐야 그게 무엇이었는지 압니다. 그게 이 시리즈의 결론입니다.
전체 코드는 2,576줄이 되었습니다. 리스트 라이브러리 152줄, 인터프리터 네 개와 컴파일러 2,140줄, 레지스터 머신 186줄, 가비지 컬렉터 98줄. 주석과 빈 줄은 뺀 숫자입니다.
7. 이 책을 읽으려는 사람에게#
시리즈를 마치며 몇 가지를 남겨 둡니다.
입문서로 읽지 마십시오. Part 1에서 인용한 대로, MIT 자신이 이 책으로 가르치던 과목을 2007년에 접었습니다. 프로그래밍을 처음 배우는 사람에게 던지기에는 잔인합니다.
두 번째나 세 번째 책으로 읽으십시오. 라이브러리를 조립해 돌아가는 것을 만들 줄 알게 된 다음, “내가 지금 뭘 하고 있는지 모르겠는데” 라는 감각이 올 때가 적기입니다.
연습문제를 푸십시오. 이 시리즈에서 가장 값진 것들 — 카마이클 수(1.27), ⌊log₂ n⌋ 감쇠(1.45), 3·4·7·무한대(3.16), 다세대 주택 퍼즐(4.3.2) — 이 전부 연습문제나 그 언저리에서 나왔습니다. 본문만 읽으면 절반만 읽는 것입니다.
전부 읽지 않아도 됩니다. 1~3장만 읽어도 값을 합니다. 4장은 언어를 만들어 보고 싶을 때, 5장은 “그래서 기계가 실제로 어떻게” 가 궁금할 때 오면 됩니다. 순서대로 완주해야 한다는 압박은 이 책을 안 읽게 만드는 가장 흔한 이유입니다.
모르는 언어로 읽어 보십시오. Scheme 도, JavaScript 도, Go 도 좋습니다. 원서가 어느 언어로 쓰였든, 여러분이 쓰는 언어로 옮기는 순간 원서가 무엇을 당연시했는지가 드러납니다. 그 드러남이 이 책을 40년 살아남게 한 이유일 것입니다.
마지막으로, 원서 전문은 저자들이 CC BY-SA 4.0 으로 공개해 두었습니다. 사서 읽어도 좋고 그냥 읽어도 좋습니다. 아래 References 의 링크로 지금 바로 열립니다.
References#
1차 자료
- Abelson, H., Sussman, G. J., with Sussman, J. Structure and Interpretation of Computer Programs, 2nd ed. MIT Press, 1996. CC BY-SA 4.0. 전문 — https://sarabander.github.io/sicp/html/
- 5.4 절 (명시적 제어 평가기) — https://sarabander.github.io/sicp/html/5_002e4.xhtml
- 5.5 절 (컴파일) — https://sarabander.github.io/sicp/html/5_002e5.xhtml
ev-sequence-last-exp의(restore continue)와 꼬리 재귀 논의는 5.4.2 절 본문입니다.- 연결 방식(linkage)과 어휘 주소 지정은 각각 5.5.1 절과 5.5.6 절입니다.
본문의 실측 데이터
- 모든 수치는
go version go1.26.0 darwin/arm64에서 직접 실행한 결과입니다. - 벤치마크는
fib(22)를 대상으로-benchtime 3s -count=2로 측정했고, 표에는 각 방식의 대표값을 실었습니다. - 스택 깊이는 명시적 제어 평가기가 자기 스택 슬라이스의 최댓값을 직접 센 값입니다. 호스트 스택은 별도 고루틴에서 실행한 뒤의
runtime.MemStats.StackInuse입니다. - 2절의 “고치기 전” 수치(깊이가 n 에 비례)는 실제로 겪은 결과이며,
m.cont = m.pop()한 줄을 넣은 뒤 다시 측정한 값과 나란히 실었습니다. - 5절에 적은 대로, 이 글의 컴파일러는 꼬리 호출을 처리하지 않습니다. 원서의 컴파일러는 처리합니다. 표의 마지막 두 줄은 원서의 한계가 아니라 이 글 구현의 한계 입니다.
- 네 가지 평가기·컴파일러는 열두 가지 프로그램에 대해 서로 같은 결과를 내는 것을 테스트로 확인했습니다.
시리즈 전체
- Part 1: 마법사 책은 왜 아직도 살아 있나
- Part 2: 프로시저는 재귀인데 프로세스는 반복이다
- Part 3: 함수를 돌려주는 함수, 그리고 제네릭이 필요해지는 순간
- Part 4: 데이터란 무엇인가 — 저장 공간 없는 pair
- Part 5: 파이프라인으로서의 프로그램, 그리고 quote 가 없는 언어
- Part 6: 1985년에 쓰인 Go 인터페이스 설계 지침
- Part 7: 시간이 들어오면 치환 모델이 무너진다
- Part 8: 같은 pair 세 개를 세는 네 가지 답, 그리고 이벤트 루프
- Part 9: 채널은 SICP 스트림이 아니다
- Part 10: Go 로 Scheme 인터프리터 만들기 — 파서라는 청구서
- Part 11: 1.74배 빨라지고 꼬리 호출을 잃다
- Part 12: call/cc 없이 시간 되감기 — amb 평가기
- Part 13: 기계 수준에서 갚는 꼬리 호출의 빚
- Part 14: 이 글