Go 로 읽는 SICP Part 11: 1.74배 빨라지고 꼬리 호출을 잃다

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

Part 10에서 Go 로 Scheme 인터프리터를 만들었습니다. 렉서, 파서, 환경, eval/apply 까지 649줄이었고, 실제로 factorial(20) 과 3장의 계좌 객체를 돌렸습니다.

이번 편은 그 평가기를 두 방향으로 고칩니다.

앞쪽(4.1.7)은 빠르게 만듭니다. 그리고 얼마나 빨라지는지, 대신 무엇을 잃는지 를 실측합니다. 잃는 것이 있다는 게 이번 편의 발견입니다.

뒤쪽(4.2)은 게으르게 만듭니다. 인자를 부를 때가 아니라 쓸 때 계산하도록 바꿉니다. 고칠 곳이 놀랍도록 적고, 그러고 나면 Part 9 의 스트림이 언어 기능으로 공짜로 딸려 옵니다.

1. 4.1.7 — 평가기가 같은 일을 반복하고 있습니다#

Part 10 의 Eval 을 다시 봅니다.

func Eval(exp any, env *Env) (any, error) {
	switch x := exp.(type) {
	case *Pair:
		if sym, ok := x.Car.(Symbol); ok {
			switch sym {
			case "quote": ...
			case "if": ...
			case "lambda": ...
			}
		}
		// ...
	}
}

fib(25) 를 돌리면 이 switch 가 몇 번 실행될까요. fib 본문의 (if ...) 하나만 봐도, 재귀 호출 수만큼 반복됩니다. 매번 “이게 if 인가” 를 처음부터 다시 판정합니다.

그런데 그 판정 결과는 절대 안 바뀝니다. 소스가 그대로인데 어떻게 바뀌겠습니까.

원서 4.1.7 의 처방이 이것입니다. 판정은 한 번만 하고, 그 결과로 “실행만 하는 프로시저” 를 만들어 둡니다.

type ExecProc func(*Env) (any, error)

func Analyze(exp any) (ExecProc, error)

Analyze 는 식을 받아 함수를 돌려줍니다. 그 함수는 환경만 받으면 바로 실행합니다. 무엇을 할지는 이미 정해져 있습니다.

if 를 예로 보면 차이가 분명합니다.

func analyzeIf(x *Pair) (ExecProc, error) {
	pred, err := Analyze(Cadr(x))    // 여기서 한 번 분석
	conseq, err := Analyze(Caddr(x)) // 여기서 한 번 분석
	alt, err := Analyze(...)

	return func(env *Env) (any, error) { // 실행할 때는 이것만 돈다
		p, err := pred(env)
		if err != nil { return nil, err }
		if isTrue(p) { return conseq(env) }
		return alt(env)
	}, nil
}

클로저 세 개를 미리 만들어 둡니다. 실행 시점에는 타입 스위치도, 심볼 비교도, Cadr 호출도 없습니다. 그냥 함수를 부릅니다.

이건 인터프리터와 컴파일러 사이의 중간 지점입니다. 원서도 그렇게 소개합니다. 그리고 5.5 절에서 진짜 컴파일러로 갑니다.

2. 얼마나 빨라지는가#

두 평가기가 같은 답을 내는지 먼저 확인하고(테스트 통과), fib(22) 로 벤치마크를 돌렸습니다.

BenchmarkDirectEval-14      139   25993151 ns/op   41845805 B/op   877693 allocs/op
BenchmarkDirectEval-14      139   25703503 ns/op   41845694 B/op   877693 allocs/op
BenchmarkAnalyzeEval-14     242   14867348 ns/op   27175045 B/op   419245 allocs/op
BenchmarkAnalyzeEval-14     247   14566442 ns/op   27175012 B/op   419245 allocs/op

	직접 평가	구문 분석 후 실행	비율
시간	25.7~26.0 ms	14.6~14.9 ms	1.74배 빠름
할당 바이트	41.8 MB	27.2 MB	35% 감소
할당 횟수	877,693	419,245	52% 감소

할당 횟수가 절반으로 줄었습니다. 이게 속도 향상의 주된 원인입니다. 직접 평가기는 매 호출마다 Cadr·Caddr 로 리스트를 훑고, evalOperands 가 슬라이스를 새로 만듭니다. 구문 분석 판은 인자 개수를 이미 알고 있어서 make([]any, len(aprocs)) 한 번이면 됩니다.

원서는 이 최적화의 효과를 “상당하다” 정도로만 말하고 숫자를 주지 않습니다. 1.74배 입니다.

3. 그런데 꼬리 호출을 잃었습니다#

여기서 예상 못 한 것이 나왔습니다.

Part 10 에서 Eval 을 for 루프로 감싸 꼬리 위치의 평가를 Go 함수 호출이 아니라 루프의 다음 반복으로 처리했습니다. Go 에 없는 꼬리 호출 최적화를 우리 언어 안에서 직접 구현한 것이었습니다.

구문 분석 판에서는 그게 안 됩니다. 프로시저 적용이 이렇게 끝나기 때문입니다.

case *AProcedure:
	ne, err := p.Env.Extend(p.Params, args)
	return p.Body(ne)   // <- Go 함수 호출이다
}

p.Body 는 클로저이고, 이걸 부르는 것은 Go 스택을 한 칸 쌓는 일입니다. 루프로 돌릴 자리가 없습니다. 무엇을 실행할지가 이미 클로저 안에 갇혀 있어서, 바깥에서 “다음에 이걸 평가해라” 로 바꿔치기할 수가 없습니다.

꼬리 재귀 루프를 돌리면서 호스트 스택을 재 봤습니다.

(define (loop i acc)
  (if (= i 0) acc (loop (- i 1) (+ acc i))))

n=10000     직접 평가기 StackInuse=   0.41 MB   구문분석 평가기 StackInuse=   4.44 MB
n=100000    직접 평가기 StackInuse=   0.44 MB   구문분석 평가기 StackInuse=  32.62 MB
n=1000000   직접 평가기 StackInuse=   0.62 MB   구문분석 평가기 StackInuse= 512.66 MB

직접 평가기는 상수 공간입니다. n 이 100배 늘어도 0.41 MB 에서 0.62 MB. 반면 구문 분석 평가기는 선형입니다. n=1,000,000 에서 512 MB 를 씁니다. Go 의 기본 스택 상한이 1 GB 이니, 여기서 두 배만 더 가면 죽습니다.

Part 2 에서 봤던 그래프가 여기서 다시 나온 셈입니다. 이번에는 우리가 만든 언어의 사용자가 그 대가를 치릅니다.

이 절충을 어떻게 볼 것인가#

1.74배 빠른 대신 깊은 꼬리 재귀가 죽습니다. Scheme 사용자에게 이건 받아들일 수 없는 거래입니다. Scheme 에서 반복문은 꼬리 재귀로 쓰는 것이 표준이기 때문입니다.

해결하려면 구문 분석 판에도 “꼬리 위치” 개념을 넣어야 합니다. ExecProc 이 값을 바로 돌려주는 대신 “다음에 실행할 것” 을 돌려주게 하고, 바깥 루프가 그걸 받아 도는 구조로 바꾸는 것입니다. 트램폴린(trampoline)이라고 부릅니다.

원서 4.1.7 은 이 문제를 다루지 않습니다. 원서의 호스트가 Scheme 이라 호스트의 꼬리 호출 보장이 그대로 새어 나오기 때문입니다. (analyze-application ...) 이 반환하는 프로시저가 호스트 Scheme 의 꼬리 위치에서 불리면 호스트가 알아서 프레임을 재활용합니다.

즉, 원서에서는 이 문제가 존재하지 않고, Go 에서는 존재합니다. 그리고 존재한다는 사실을 알려면 재 봐야 합니다. Part 1 에서 “Go 로 읽으면 원서가 무엇을 당연시했는지 드러난다” 고 했는데, 이번 것이 그 사례 중 가장 선명합니다.

4. 4.2 — 게으른 평가기#

이제 방향을 바꿉니다.

원서 4.2.1 이 던지는 질문은 이것입니다. 프로시저의 인자를 언제 계산해야 하는가.

지금까지의 평가기는 적용 순서(applicative order) 입니다. 프로시저를 부르기 전에 인자를 전부 계산합니다. 대안은 정규 순서(normal order) 입니다. 인자를 계산하지 않고 넘긴 뒤, 실제로 값이 필요한 순간에 계산합니다.

차이가 드러나는 고전적인 예제가 있습니다.

(define (try a b) (if (= a 0) 1 b))
(try 0 (/ 1 0))

a 가 0 이므로 b 는 쓰이지 않습니다. 그러니 (/ 1 0) 을 계산할 이유가 없습니다. 두 평가기에 돌려 봤습니다.

  적용 순서(보통 평가기) : /: 0 으로 나눌 수 없습니다
  정규 순서(게으른 평가기): 1

같은 프로그램인데 하나는 죽고 하나는 답을 냅니다.

5. 고칠 곳은 세 군데뿐입니다#

게으른 평가기를 만들려면 무엇을 바꿔야 하나. 원서의 답이 놀랍도록 짧습니다.

첫째, 복합 프로시저의 인자를 평가하지 말고 감쌉니다.

type Thunk struct {
	exp  any
	env  *Env
	memo any
	done bool
}

Thunk 는 “이 식을 이 환경에서 평가하면 되는데, 아직 안 했다” 는 쪽지입니다.

둘째, 원시 프로시저의 인자는 실제 값이어야 합니다. + 는 Thunk 를 더할 수 없습니다.

셋째, 값이 실제로 필요한 자리에서 풉니다. 연산자 자리(프로시저를 불러야 하니까)와 if 의 조건(참거짓을 봐야 하니까)입니다.

func force(v any) (any, error) {
	t, ok := v.(*Thunk)
	if !ok { return v, nil }
	if t.done { return t.memo, nil }   // 이미 계산했으면 그것을
	r, err := LazyEval(t.exp, t.env)
	// ...
	t.memo, t.done = r, true
	t.exp, t.env = nil, nil            // 참조를 끊어 준다
	return r, nil
}

memo 와 done 이 있는 것에 주목할 만합니다. Part 9 의 스트림에서 봤던 그 메모이제이션입니다. 같은 thunk 를 두 번 force 해도 계산은 한 번입니다.

원서 연습문제 4.29 가 이걸 확인하는 실험을 제시합니다. 우리 언어로 그대로 돌려 봤습니다.

(define count 0)
(define (id x) (set! count (+ count 1)) x)
(define (square x) (* x x))
(define r (square (id 10)))
(list r count)

(square (id 10)) 결과와 id 호출 횟수: (100 1)

x 가 본문에 두 번 나오는데 id 는 한 번만 불렸습니다. 메모이제이션이 없다면 2가 나왔을 것입니다.

6. `unless` 를 프로시저로 만들 수 있는가#

원서 연습문제 4.25~4.26 이 좋은 질문을 던집니다. if 같은 것을 특수 형식이 아니라 그냥 프로시저로 쓸 수 있는가.

(define (unless condition usual except) (if condition except usual))
(define (factorial n) (unless (= n 1) (* n (factorial (- n 1))) 1))
(factorial 6)

적용 순서에서는 안 됩니다. unless 를 부르기 전에 인자를 전부 계산해야 하는데, 그 인자 중 하나가 (factorial (- n 1)) 입니다. 재귀가 멈추지 않습니다.

  적용 순서 : 최대 재귀 깊이 초과 (100000). 끝나지 않는 재귀일 수 있습니다
  정규 순서 : 720

6! = 720. 게으른 평가기에서는 그냥 됩니다.

이 결과에 딸린 이야기가 하나 있습니다. 처음 이 실험을 돌렸을 때 프로그램이 통째로 죽었습니다.

runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

Go 에서 스택 오버플로는 recover 로 잡을 수 없습니다. 프로세스가 그냥 끝납니다. 그래서 평가기에 재귀 깊이 상한을 넣었습니다.

var MaxDepth = 100_000

func Eval(exp any, env *Env) (any, error) {
	evalDepth++
	if evalDepth > MaxDepth {
		evalDepth--
		return nil, fmt.Errorf("최대 재귀 깊이 초과 (%d). 끝나지 않는 재귀일 수 있습니다", MaxDepth)
	}
	v, err := evalCore(exp, env)
	evalDepth--
	return v, err
}

원서에는 이런 게 없습니다. 호스트 Scheme 이 알아서 에러를 내고 REPL 로 돌아가기 때문입니다. Go 를 호스트로 쓰면 “손님 프로그램의 무한 재귀가 호스트를 죽인다” 는 문제를 직접 처리해야 합니다. 실제 언어 런타임을 만들 때 반드시 만나는 요구사항이고, 원서는 이걸 건너뜁니다.

7. 4.2.3 — 스트림이 공짜로 딸려 옵니다#

게으른 평가기의 진짜 보상이 여기 있습니다.

Part 9 에서 스트림을 만들 때 ConsStream 이라는 특별한 장치가 필요했습니다. 꼬리를 클로저로 감싸고 메모이즈해야 했습니다. 원서도 cons-stream 을 특수 형식 으로 만듭니다. 보통 프로시저로는 안 되기 때문입니다.

게으른 평가기에서는 필요 없습니다. 복합 프로시저의 인자가 이미 지연되니, 그냥 cons 를 쓰면 됩니다.

단 조건이 하나 있습니다. cons 가 복합 프로시저 여야 합니다. 원시 프로시저의 인자는 force 되기 때문입니다. 그래서 원서는 cons 를 언어 안에서 다시 정의합니다.

(define (cons x y) (lambda (m) (m x y)))
(define (car z) (z (lambda (p q) p)))
(define (cdr z) (z (lambda (p q) q)))

Part 4 의 “저장 공간 없는 pair” 가 여기서 돌아옵니다. 그때는 “데이터란 계약일 뿐” 이라는 철학적 논점이었는데, 여기서는 실용적인 필요 입니다. 게으른 언어에서 스트림을 얻으려면 pair 가 프로시저여야 합니다.

돌려 봤습니다.

(define (integers-from n) (cons n (integers-from (+ n 1))))
(define ones (cons 1 ones))
(define (add-streams a b) (cons (+ (car a) (car b)) (add-streams (cdr a) (cdr b))))
(define fibs (cons 0 (cons 1 (add-streams (cdr fibs) fibs))))

(정수 10개 / 1 다섯 개 / 피보나치 12개)
((1 2 3 4 5 6 7 8 9 10) (1 1 1 1 1) (0 1 1 2 3 5 8 13 21 34 55 89))

세 줄이 전부입니다. delay 도 force 도 cons-stream 도 안 씁니다. 그냥 재귀 정의를 적었고, 그게 무한 스트림이 되었습니다.

(define ones (cons 1 ones)) 를 보십시오. 자기 자신을 참조하는 정의 인데 그냥 됩니다. fibs 는 더 이상합니다. 자기 cdr 를 자기와 더한 것이 자기의 꼬리입니다. 적용 순서 언어에서는 문장으로도 성립하지 않는 정의입니다.

이게 원서 4.2 의 요점입니다. 평가 전략을 바꾸면 표현할 수 있는 것이 달라집니다. 3.5 절에서 특수 형식과 매크로로 어렵게 만든 것이, 4.2 에서는 언어의 기본 성질이 됩니다.

8. 게으름의 대가#

원서는 4.2.1 에서 정규 순서를 소개하면서 왜 대부분의 언어가 적용 순서를 쓰는지도 설명합니다.

첫째, 언제 무슨 일이 일어나는지 알기 어렵습니다. set! 이나 출력 같은 부수 효과가 있으면 게으른 평가에서 순서가 예측하기 어려워집니다. 원서는 “대입을 도입하면 게으른 평가는 아주 혼란스러워진다” 고 명시합니다.

둘째, 메모리를 예측하기 어렵습니다. thunk 는 자기가 참조하는 환경을 통째로 붙잡고 있습니다. 위 force 구현에서 t.exp, t.env = nil, nil 로 참조를 끊은 것이 그 대응입니다. 이 한 줄이 없으면 계산이 끝난 thunk 가 환경 사슬 전체를 살려 둡니다. Haskell 진영에서 “space leak” 이라고 부르는 문제입니다.

셋째, 성능이 예측하기 어렵습니다. thunk 를 만들고 푸는 비용이 계산 자체보다 클 수 있습니다.

Go 는 물론 적용 순서입니다. 그리고 Go 가 게으른 계산을 원할 때 쓰는 도구가 정확히 우리가 만든 Thunk 입니다.

var once sync.Once
var val T
func Get() T {
	once.Do(func() { val = expensive() })
	return val
}

sync.OnceValue 는 이걸 한 줄로 만들어 줍니다. memo + done 이 sync.Once 이고, 나머지가 클로저입니다. 4.2 를 읽고 나면 sync.OnceValue 가 “게으른 평가를 값 하나에 국소적으로 적용한 것” 으로 보입니다.

9. 이번 편의 정리#

SICP 4.1.7~4.2 의 주장	Go 에서
구문 분석을 실행에서 분리하면 빨라진다	성립. 1.74배, 할당 52% 감소
(원서에 없음)	그 대신 꼬리 호출 최적화를 잃음 (0.62 MB → 512 MB)
정규 순서는 안 쓰는 인자를 계산하지 않는다	성립. `(try 0 (/ 1 0))` → 1
세 군데만 고치면 게으른 평가기가 된다	성립
thunk 메모이제이션이 필요하다	성립. 연습문제 4.29 재현
게으른 언어에서는 `cons` 만으로 스트림이 된다	성립. Part 4 의 프로시저 pair 가 필수
(원서에 없음)	손님 프로그램의 무한 재귀로부터 호스트를 지켜야 함

다음 편은 4장의 마지막인 4.3 amb 비결정성 평가기 입니다.

(amb 1 2 3) 이라고 쓰면 세 값 중 하나가 나오고, 뒤에서 모순이 발견되면 시간을 되감아 다른 값을 고릅니다. 백트래킹을 언어 기능으로 만드는 것입니다.

Part 1 에서 예고한 세 번째 마찰이 여기 있습니다. Go 에는 일급 연속(call/cc)이 없습니다. 그런데 결론부터 말하면, 그게 문제가 되지 않습니다. 문제가 되지 않는 이유가 꽤 흥미롭고, 대신 다른 곳에서 값을 치릅니다. 어디서 치르는지는 다음 편에서 재 보겠습니다.

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.
- 4.1.7 절 (구문 분석 분리) 및 4.2 절 (게으른 평가) — https://sarabander.github.io/sicp/html/4_002e1.xhtml , https://sarabander.github.io/sicp/html/4_002e2.xhtml
unless 예제는 연습문제 4.25~4.26, thunk 메모이제이션 실험은 연습문제 4.29 입니다.
게으른 언어에서 cons/car/cdr 를 프로시저로 정의하는 것은 4.2.3 절 본문입니다.

본문의 실측 데이터

모든 수치는 go version go1.26.0 darwin/arm64 에서 직접 실행한 결과입니다.
벤치마크는 fib(22) 를 대상으로 -benchtime 3s -count=2 로 두 번씩 측정한 값을 그대로 실었습니다.
스택 사용량은 각 평가기를 별도 고루틴에서 돌린 뒤 그 고루틴이 끝나는 시점의 runtime.MemStats.StackInuse 입니다.
6절의 fatal error: stack overflow 는 재귀 깊이 상한을 넣기 전에 실제로 발생한 것이며, 그 사고 때문에 상한을 넣었다는 경위를 본문에 적었습니다.

시리즈