Go 로 읽는 SICP Part 13: 기계 수준에서 갚는 꼬리 호출의 빚

이 글은 Claude Opus 5 를 이용해 초안이 작성되었으며, 이후 퇴고를 거쳤습니다.

Part 12로 4장을 끝냈습니다. 인터프리터를 네 개 만들었고, 그때마다 같은 문제가 돌아왔습니다. 꼬리 호출을 어떻게 상수 공간으로 만드는가.

5장이 그 질문에 답합니다. 방법은 더 내려가는 것 입니다.

지금까지 만든 평가기는 전부 Go 라는 고수준 언어 위에 있었습니다. 재귀는 Go 의 함수 호출이었고, 스택은 Go 의 스택이었습니다. 5장은 그 아래로 내려갑니다. 레지스터 몇 개와 명령어 대여섯 개만 있는 기계 를 만들고, 그 위에서 모든 것을 다시 구현합니다.

그러고 나면 “왜 그런가” 가 자명해집니다. 이번 편의 결론이 그것입니다.

1. 5.1 — 기계를 기술하는 언어#

원서는 먼저 기계를 글로 적는 방법 을 정합니다. 명령어는 여섯 종류뿐입니다.

명령어	하는 일
`(assign r ...)`	레지스터에 값을 넣는다
`(test (op o) ...)`	조건을 검사해 플래그를 세운다
`(branch (label l))`	플래그가 참이면 점프
`(goto (label l))` / `(goto (reg r))`	무조건 점프
`(save r)` / `(restore r)`	레지스터를 스택에 넣고 뺀다
`(perform (op o) ...)`	값을 안 쓰는 연산

이게 전부입니다. 그리고 이 여섯 개로 유클리드 호제법을 씁니다.

(test-b
   (test (op =) (reg b) (const 0))
   (branch (label gcd-done))
   (assign t (op rem) (reg a) (reg b))
   (assign a (reg b))
   (assign b (reg t))
   (goto (label test-b))
 gcd-done)

Part 2의 Go 코드와 한 줄씩 대응합니다. for b != 0 { a, b = b, a%b } 가 여섯 줄이 되었습니다.

2. 5.2 — 시뮬레이터, 그리고 파서 재사용#

이제 저 텍스트를 실행하는 기계를 Go 로 만듭니다.

첫 번째로 좋은 소식이 있습니다. 위 컨트롤러 텍스트는 그냥 Lisp 리스트입니다. 그러니 Part 10에서 만든 파서를 그대로 쓰면 됩니다.

func (m *Machine) Install(controller string) error {
	items, err := scheme.ReadAll(controller) // 4장의 파서를 재사용
	// ...
}

4장에서 171줄을 주고 산 파서가 5장에서 값을 합니다. 원서에서는 이 재사용이 너무 당연해서 눈에 안 띄는데(둘 다 Scheme 리스트니까), Go 에서는 파서를 한 번 만들어 두면 기계 기술 언어까지 공짜로 읽힌다 는 것이 눈에 보입니다.

어셈블러 (5.2.2)#

설치는 두 번 훑습니다.

1단계, 레이블 위치를 잡습니다. 리스트에서 심볼이 나오면 명령어가 아니라 레이블입니다.

for e := items[0]; e != nil; e = Cdr(e) {
	x := Car(e)
	if sym, ok := x.(Symbol); ok {
		m.labels[sym] = len(raw) // 레이블은 다음 명령어를 가리킨다
		continue
	}
	raw = append(raw, x)
}

2단계, 명령어마다 실행 프로시저를 만듭니다.

case Symbol("assign"):
	reg := Cadr(x).(Symbol)
	g, err := m.value(Car(Cddr(x)))
	return func() { m.regs[reg] = g(); m.pc++ }, nil

이게 Part 11의 구문 분석 평가기와 정확히 같은 기법입니다. 명령어를 볼 때마다 “이게 assign 인가” 를 다시 판정하지 않고, 설치 시점에 한 번 판정해서 클로저를 만들어 둡니다. 원서가 4.1.7 을 5.2.3 직전에 배치한 이유가 이것입니다. 같은 아이디어를 두 번 쓰게 하려는 것입니다.

실행 루프는 세 줄입니다.

for m.pc < len(m.insts) {
	m.Count++
	m.insts[m.pc].exec()
}

돌려 봤습니다.

gcd(206, 40)       = 2     실행 명령어 26개
gcd(1071, 462)     = 21    실행 명령어 20개
gcd(121393, 75025) = 1     실행 명령어 146개

마지막 줄이 연속한 피보나치 수입니다. Part 2에서 유클리드 호제법의 최악의 경우라고 했던 그 입력이고, 이번에는 명령어 개수로 최악임이 드러납니다.

3. 5.1.4 — 재귀를 스택으로 만들기#

이제 진짜 주제입니다. 위 GCD 기계에는 save/restore 가 없습니다. 반복이니까 필요 없습니다.

재귀는 다릅니다. (factorial n) 은 (factorial (- n 1)) 을 부르고, 그 결과가 돌아온 뒤에 n 을 곱해야 합니다. 그러려면 두 가지를 기억해야 합니다. 돌아올 자리 와 그때의 n 입니다.

  fact-loop
    (test (op =) (reg n) (const 1))
    (branch (label base-case))
    (save continue)                       ; 돌아올 자리를 기억
    (save n)                              ; 그때의 n 을 기억
    (assign n (op -) (reg n) (const 1))
    (assign continue (label after-fact))
    (goto (label fact-loop))
  after-fact
    (restore n)                           ; 기억해 둔 것을 꺼내
    (restore continue)
    (assign val (op *) (reg n) (reg val)) ; 이제 곱한다
    (goto (reg continue))

(goto (reg continue)) 에 주목할 만합니다. 점프할 곳이 레지스터에 들어 있습니다. 이것이 반환 주소 이고, 서브루틴 호출의 정체입니다.

돌려 봤습니다.

  n   결과                 명령어수  push수  최대깊이
  1   1                    5        0       0
  3   6                    27       4       4
  5   120                  49       8       8
  10  3628800              104      18      18
  20  2432902008176640000  214      38      38

최대 스택 깊이가 2(n−1) 입니다. continue 와 n 을 한 쌍씩 쌓으니까요. 20! = 2,432,902,008,176,640,000. 맞습니다.

트리 재귀는 어떤가#

피보나치 기계도 만들었습니다. fib(n-1) 과 fib(n-2) 를 둘 다 불러야 하므로 스택을 두 번 씁니다.

  n   fib(n)   명령어수   push수   최대깊이
  5   5        166        28       8
  10  55       2029       352      18
  15  610      22683      3944     28
  20  6765     251740     43780    38

이 표가 Part 2의 주장을 기계 수준에서 증명합니다.

push 횟수 는 43,780 까지 폭증합니다. n 이 5 늘 때마다 11배씩. 지수 시간.
최대 깊이 는 38 입니다. 계승 기계와 똑같습니다. 여전히 2(n−1). 선형 공간.

Part 2 에서 “트리 재귀는 시간이 지수인데 공간은 O(n) 이다. 두 자원이 따로 논다” 고 썼습니다. 그때는 원서의 서술을 옮긴 것이었는데, 여기서는 push 횟수와 최대 깊이라는 두 개의 숫자 로 직접 보입니다.

4. 빚 갚기 — 꼬리 재귀는 왜 상수 공간인가#

시리즈 내내 세 번 미룬 질문입니다.

Part 2: Go 에 꼬리 호출 최적화가 없어서 꼬리 재귀가 16.25 MB 를 썼습니다.
Part 11: 구문 분석 평가기가 꼬리 호출을 잃어 512 MB 를 썼습니다.
Part 12: amb 평가기의 CPS 사슬이 256 MB 를 썼습니다.

이제 답합니다. 같은 계승을 두 기계 로 만들어 나란히 돌렸습니다.

  n    (a) 재귀 기계                     (b) 반복 기계
       결과            명령어 push 깊이 | 결과            명령어 push 깊이
  5    120             49     8    8    | 120             30     0    0
  10   3628800         104    18   18   | 3628800         55     0    0
  20   2432902008...   214    38   38   | 2432902008...   105    0    0
  100  (오버플로)       1094   198  198  | (오버플로)       505    0    0
  1000 (오버플로)       10994  1998 1998 | (오버플로)       5005   0    0

(b) 는 n 이 1000 이어도 push 0, 깊이 0 입니다.

반복 기계의 컨트롤러를 보면 이유가 한눈에 보입니다.

  test-counter
    (test (op >) (reg counter) (reg n))
    (branch (label fact-done))
    (assign product (op *) (reg counter) (reg product))
    (assign counter (op +) (reg counter) (const 1))
    (goto (label test-counter))

save 도 restore 도 없습니다. 상태가 전부 레지스터 두 개(product, counter)에 들어 있고, 매 반복이 그것을 덮어씁니다. 돌아와서 할 일이 없으므로 기억할 것도 없습니다.

그러면 꼬리 호출 최적화란 무엇인가. 이 관점에서 정의하면 이렇게 됩니다.

꼬리 호출 최적화란, save 를 하지 않아도 되는 호출을 알아보고 실제로 하지 않는 것 이다.

프로시저 호출이 끝난 뒤에 할 일이 없으면 continue 를 저장할 필요가 없습니다. 지금 들고 있는 continue 를 그대로 넘겨주면, 안쪽 호출이 끝났을 때 바로 바깥의 바깥으로 돌아갑니다.

“프레임을 재활용한다” 는 비유가 아니라 문자 그대로 save 명령어 한 줄을 생략하는 일 입니다. Part 2 에서 “Go 가 안 해 주는 그 일” 이라고 했던 것의 정체가 이것입니다.

그리고 이 관점에서 보면 Part 10 에서 Eval 을 for 루프로 감싼 것이 무엇이었는지도 분명해집니다. 꼬리 위치에서 Go 함수를 부르는 대신 exp 와 env 라는 레지스터를 덮어쓰고 루프의 처음으로 goto 한 것 입니다. 우리는 이미 5장의 기법을 쓰고 있었습니다.

5. 5.3 — 무한 메모리라는 착각을 유지하기#

5장의 다음 주제는 메모리입니다.

지금까지 Cons 를 부를 때마다 새 pair 가 생겼습니다. 무한히 생깁니다. 실제 기계에는 메모리가 유한한데 어떻게 그런 착각을 유지하는가.

원서 5.3.1 의 답이 먼저 필요합니다. 메모리를 벡터 두 개로 봅니다. the-cars 와 the-cdrs. pair 하나가 같은 인덱스의 두 칸입니다. 포인터는 그냥 인덱스 입니다.

type Ptr struct {
	Kind string // "pair" | "num" | "sym" | "nil" | "broken-heart"
	Idx  int
	Sym  string
}

type Memory struct {
	cars, cdrs []Ptr
	free       int
	// ...
}

Kind 가 타입 태그 입니다. Part 6의 태그드 데이터가 여기서 하드웨어 이야기로 돌아옵니다. 실제 Lisp 머신은 워드의 상위 몇 비트를 이 태그에 씁니다.

stop-and-copy#

5.3.2 의 가비지 컬렉터입니다. 메모리를 절반씩 두 덩어리로 나누고, 한쪽만 씁니다. 가득 차면 살아 있는 것만 다른 쪽으로 옮기고 두 쪽을 맞바꿉니다.

flowchart LR
    A["루트<br/>(레지스터들)"] -->|"1. relocate"| B["새 반쪽으로<br/>한 칸 복사"]
    B --> C["옛 자리에<br/>broken-heart 표시<br/>+ 새 주소"]
    B --> D["2. scan 이<br/>복사본을 훑는다"]
    D -->|"그 안의 포인터도"| B
    D -->|"scan == free"| E["3. 끝"]
    E --> F["두 반쪽을 맞바꾼다"]

    style A fill:#90EE90,color:#000000
    style C fill:#FFD700,color:#000000
    style F fill:#87CEEB,color:#000000

핵심은 broken-heart 입니다. 옮긴 pair 의 옛 자리에 “나는 저기로 갔다” 는 표시와 새 주소를 남깁니다. 그러면 같은 것을 두 번 옮기지 않고, 순환 구조에서도 무한 루프에 안 빠집니다.

func relocate(p Ptr) Ptr {
	if p.Kind != "pair" { return p }
	oldCar := m.cars[p.Idx]
	if oldCar.Kind == "broken-heart" { // 이미 옮겼다
		return Ptr{Kind: "pair", Idx: oldCar.Idx}
	}
	newIdx := free; free++
	m.newCars[newIdx] = m.cars[p.Idx]
	m.newCdrs[newIdx] = m.cdrs[p.Idx]
	m.cars[p.Idx] = Ptr{Kind: "broken-heart", Idx: newIdx}
	return Ptr{Kind: "pair", Idx: newIdx}
}

그리고 scan 포인터가 복사된 영역을 따라가며 그 안의 포인터도 옮깁니다. scan 이 free 를 따라잡으면 끝입니다. 작업 큐가 복사된 영역 자체입니다. 별도 자료구조가 필요 없습니다. 이 절약이 stop-and-copy 의 우아한 점입니다.

12칸짜리 메모리로 돌려 봤습니다.

메모리 크기: 12칸

root = (1 2 3)               free=3/12
쓰레기 (9 9 9) 를 만들었다     free=6/12

다음 할당에서 자리가 모자라 GC 가 돌아간다...

GC 실행 횟수: 1, 마지막 GC 가 회수한 칸: 3
root = (106 105 104 103 102 101 100 1 2 3)
free=10/12

루트에서 닿지 않는 (9 9 9) 세 칸이 회수되었습니다. 그리고 순환 구조도 확인했습니다.

순환 만들기 전 free=2
GC 실행 횟수=1, free=4, 살아남은 것: car=a
순환이 있어도 무한 루프에 빠지지 않았다 (broken-heart 표시 덕분)

6. 루트 집합을 빠뜨린 사고#

이 GC 를 처음 돌렸을 때 이렇게 나왔습니다.

root = (106 () . ())

리스트가 깨졌습니다. 원인은 Cons 였습니다.

func (m *Memory) Cons(a, d Ptr, roots []*Ptr) (Ptr, error) {
	if m.free >= m.size {
		m.Collect(roots)   // <- 여기가 문제
	}
	// ... a 와 d 를 새 칸에 쓴다
}

GC 는 객체를 옮깁니다. roots 에 든 포인터는 새 주소로 갱신되지만, a 와 d 는 지역 변수라 루트 집합에 없습니다. GC 후에도 옛 반쪽의 주소를 그대로 들고 있고, 그 주소는 이미 다른 것이 덮어썼거나 비어 있습니다.

고치는 법은 한 줄입니다.

m.Collect(append(append([]*Ptr{}, roots...), &a, &d))

살아 있는 모든 포인터가 루트 집합에 있어야 합니다. 하나라도 빠지면 그 포인터는 조용히 쓰레기를 가리킵니다.

원서에서는 이 문제가 안 보입니다. 원서의 GC 는 레지스터 머신 안에서 돌고, 그 기계의 레지스터가 곧 루트 집합이기 때문입니다. cons 의 인자도 레지스터에 들어 있으니 자동으로 포함됩니다. 제가 Go 함수 인자로 받으면서 그 보장이 깨졌습니다.

이게 실제 GC 구현이 어려운 이유의 축소판입니다. 이동식 GC 를 쓰는 런타임은 “지금 이 순간 살아 있는 포인터가 전부 어디에 있는가” 를 정확히 알아야 합니다. Go 런타임이 스택 맵과 쓰기 장벽(write barrier)을 유지하는 이유가 이것입니다.

7. Go 의 GC 와 나란히 놓고 보면#

SICP 의 stop-and-copy 와 Go 의 GC 는 성격이 꽤 다릅니다.

	SICP stop-and-copy	Go 의 GC
방식	복사형(copying)	표시-쓸기(mark-sweep)
객체 이동	옮긴다	옮기지 않는다
메모리	절반만 씀	전체를 씀
멈춤	전면 정지	대부분 동시 실행
단편화	없음 (모아서 복사하니까)	크기 등급으로 완화

가장 큰 차이가 객체를 옮기느냐 입니다. Go 는 안 옮깁니다. 그래서 6절의 버그가 Go 프로그램에서는 안 생깁니다. unsafe.Pointer 로 주소를 정수에 넣어 두는 것이 위험한 이유가 “언젠가 옮길지도 모르니까” 인데, 현재 구현은 옮기지 않습니다.

그리고 SICP 의 GC 는 전면 정지 입니다. 메모리가 찰 때까지 아무 일도 안 하다가, 차면 모든 것을 멈추고 전부 옮깁니다. Go 가 지연 시간을 위해 대부분의 작업을 동시에 하려고 애쓰는 것과 대비됩니다.

원서의 것이 더 낫다는 이야기가 아닙니다. 1985년에 30줄로 설명할 수 있는 GC 가 존재했고, 그걸 이해하면 오늘날의 GC 가 무슨 문제를 풀려고 복잡해졌는지 읽힌다는 것입니다. 동시 실행, 세대별 수집, 쓰기 장벽 — 전부 “전면 정지가 너무 길다” 는 하나의 문제에 대한 대응입니다.

8. 이번 편의 정리#

SICP 5.1~5.3 의 주장	Go 에서
명령어 여섯 개로 기계를 기술한다	성립. 4장 파서를 그대로 재사용
어셈블러가 실행 프로시저를 만든다	성립. 4.1.7 과 같은 기법
`save`/`restore` 로 재귀를 구현한다	성립. 최대 깊이 2(n−1)
트리 재귀는 시간 지수·공간 선형	숫자로 증명됨. push 43,780 vs 깊이 38
반복 프로세스는 스택을 안 쓴다	push 0. 시리즈의 빚을 갚음
메모리는 벡터 둘, 포인터는 인덱스	성립
broken-heart 로 순환을 처리한다	성립. 무한 루프 없음
(원서에 없음)	루트 집합 누락 버그. 실제로 겪음

5장에 절이 다섯인데 세 개를 봤습니다. 남은 것은 5.4 명시적 제어 평가기 와 5.5 컴파일러 입니다.

다음 편이 이 시리즈의 마지막입니다. 5.4 는 4장에서 만든 평가기를 이 레지스터 머신 위에서 다시 구현합니다. 그러면 eval 과 apply 가 명령어 목록이 되고, 4장에서 Go 재귀에 맡겼던 것들이 전부 save/restore 로 드러납니다. 그리고 5.4.2 절에서 꼬리 재귀가 실제로 어떻게 구현되는지 를 봅니다.

5.5 는 컴파일러입니다. 평가기가 실행 중에 하던 분석을 미리 해서 명령어 목록을 뽑아냅니다. 그러면 같은 프로그램이 얼마나 빨라지는지, 실제로 재 보겠습니다.

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.
- 5.1 절 (레지스터 머신 설계) — https://sarabander.github.io/sicp/html/5_002e1.xhtml
- 5.2 절 (시뮬레이터) — https://sarabander.github.io/sicp/html/5_002e2.xhtml
- 5.3 절 (저장 공간 할당과 가비지 컬렉션) — https://sarabander.github.io/sicp/html/5_002e3.xhtml
GCD 기계는 5.1.1 절, 재귀·반복 계승 기계와 피보나치 기계는 5.1.4 절, stop-and-copy 는 5.3.2 절입니다.

본문의 실측 데이터

모든 명령어 수, push 횟수, 최대 스택 깊이는 이 글의 Go 시뮬레이터가 실제로 세어 출력한 값입니다. go version go1.26.0 darwin/arm64.
n=100 이상의 계승 값은 Go 의 int 범위를 넘어 오버플로합니다. 스택 통계만 유효하므로 값 자리를 “(오버플로)” 로 표시했습니다.
6절의 버그는 실제로 발생했고, root = (106 () . ()) 는 고치기 전의 실제 출력입니다.
7절의 Go GC 특성(비이동, 표시-쓸기, 대부분 동시 실행)은 현재 Go 런타임의 설계이며, 향후 구현이 바뀔 수 있는 사항입니다.

시리즈