Go 로 읽는 SICP Part 3: 함수를 돌려주는 함수, 그리고 제네릭이 필요해지는 순간

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

Part 2에서 SICP 1.1~1.2 를 봤고, Go 에 꼬리 호출 최적화가 없어서 “재귀 프로시저 ≠ 재귀 프로세스” 라는 구분이 통째로 지워진다는 것을 실측으로 확인했습니다.

이번 편은 1장의 마지막 절인 1.3, Formulating Abstractions with Higher-Order Procedures 입니다. 프로시저를 인자로 받고 반환값으로 돌려주는 이야기입니다.

Go 는 함수가 일급 값입니다. 그러니 원서를 그대로 따라갈 수 있습니다. 그런데 그대로 따라가면 원서에 없던 것이 하나 붙습니다. 타입 입니다. 이게 이번 편에서 가장 흥미로운 지점입니다. 타입은 추상화의 계약을 눈에 보이게 만들어 주고, 동시에 원서에서는 공짜였던 어떤 코드를 컴파일 에러로 만듭니다.

1. 1.3.1 — 세 개의 비슷한 함수에서 하나를 뽑아내기#

원서는 세 개의 합계를 나란히 놓는 것으로 시작합니다. 정수의 합, 세제곱의 합, 그리고 π/8 로 수렴하는 급수의 합. 셋을 Go 로 쓰면 이렇습니다.

func sumIntegers(a, b float64) float64 {
	if a > b { return 0 }
	return a + sumIntegers(a+1, b)
}

func sumCubes(a, b float64) float64 {
	if a > b { return 0 }
	return cube(a) + sumCubes(a+1, b)
}

func piSum(a, b float64) float64 {
	if a > b { return 0 }
	return 1/(a*(a+2)) + piSum(a+4, b)
}

세 개가 같은 뼈대 를 공유합니다. 다른 것은 두 가지뿐입니다. 항을 어떻게 계산하는가, 다음 값으로 어떻게 넘어가는가. 원서는 이 공통 뼈대를 수학의 시그마 기호에 대응시킵니다.

그 둘을 인자로 빼면 하나로 합쳐집니다.

type F1 = func(float64) float64

// term: 항 계산법, next: 다음 값 계산법
func sum(term F1, a float64, next F1, b float64) float64 {
	total := 0.0
	for x := a; x <= b; x = next(x) {
		total += term(x)
	}
	return total
}

원서는 재귀로 쓰지만, Part 2 의 방침대로 Go 에서는 루프로 씁니다. 깊이가 항의 개수에 비례하는 재귀이기 때문입니다.

이제 세 함수는 sum 을 부르는 한 줄이 됩니다.

func inc(n float64) float64      { return n + 1 }
func identity(x float64) float64 { return x }

sum(identity, 1, inc, 10) // 55
sum(cube, 1, inc, 10)     // 3025

그리고 원서는 여기서 한 번 더 밀어붙입니다. 정적분도 결국 합계입니다.

func integral(f F1, a, b, dx float64) float64 {
	addDx := func(x float64) float64 { return x + dx }
	return sum(f, a+dx/2, addDx, b) * dx
}

실행 결과입니다.

1..10 정수합       = 55
1..10 세제곱합     = 3025
integral(cube,0,1) = 0.24999988  (참값 0.25)

∫₀¹ x³ dx = 1/4 입니다. 소수점 일곱째 자리까지 맞습니다.

Go 가 덧붙이는 것 — 시그니처가 곧 계약#

여기서 Scheme 판과 Go 판이 갈립니다. 원서의 sum 은 이렇게 시작합니다.

(define (sum term a next b) ...)

term 이 뭘 받고 뭘 돌려주는지는 어디에도 적혀 있지 않습니다. 본문을 읽고 추론해야 합니다. Go 판은 이렇습니다.

func sum(term F1, a float64, next F1, b float64) float64

이 한 줄이 계약 전체입니다. term 은 float64 하나를 받아 float64 를 돌려주는 것이어야 하고, next 도 그렇습니다. 잘못 넘기면 컴파일이 안 됩니다.

원서가 “프로시저를 인자로 넘길 수 있다” 고 말할 때, 실제로 성립하려면 넘기는 쪽과 받는 쪽이 모양에 합의 해야 합니다. Scheme 은 그 합의를 문서와 관습에 맡깁니다. Go 는 타입으로 못박습니다. 원서를 Go 로 읽으면 이 합의가 코드에 드러나서, 추상화가 무엇을 약속하고 있는지가 훨씬 분명해집니다.

대가도 있습니다. F1 이라는 별칭을 만들지 않으면 func(float64) float64 를 매번 적어야 하고, 코드가 길어집니다. 이건 이 시리즈 내내 반복될 거래입니다.

2. 1.3.2 — 람다와 `let`#

원서는 inc 나 identity 같은 자잘한 이름을 만드는 게 낭비라고 지적하고, 이름 없는 프로시저를 만드는 lambda 를 도입합니다. Go 의 함수 리터럴이 정확히 같은 것입니다.

sum(func(x float64) float64 { return x },
	1,
	func(x float64) float64 { return x + 1 },
	10)

Scheme 쪽이 짧습니다. (lambda (x) x) 대 func(x float64) float64 { return x }. Go 는 타입을 두 번 적어야 해서 배 이상 길어집니다. 함수형 스타일을 밀어붙였을 때 Go 코드가 답답해지는 이유의 절반이 여기 있습니다.

원서는 이어서 let 을 소개합니다. 식 안에서 지역 이름을 만드는 장치인데, 원서는 let 이 사실 즉시 호출되는 lambda 의 문법 설탕 임을 밝힙니다.

(let ((x 3) (y 4)) (+ x y))
;; 은 사실
((lambda (x y) (+ x y)) 3 4)

Go 에도 즉시 호출 함수 리터럴이 있으니 그대로 옮길 수 있습니다.

func(x, y float64) float64 { return x + y }(3, 4)

물론 Go 에서는 그냥 지역 변수를 쓰면 됩니다.

x, y := 3.0, 4.0
_ = x + y

여기가 Go 와 Scheme 의 세계관이 갈리는 지점입니다. Scheme 은 “모든 것이 식” 이라서 지역 이름조차 함수 적용으로 환원됩니다. Go 는 “문(statement)이 따로 있다” 는 쪽이라 지역 변수가 별도 장치입니다. Scheme 이 개념적으로 더 간결하고, Go 가 읽기에 더 평범합니다.

이 차이가 4장에서 다시 계산서로 돌아옵니다. 모든 것이 식이면 평가기가 다뤄야 할 경우의 수가 적습니다.

3. 1.3.3 — 프로시저를 일반적인 방법으로#

1.3.3 에서 원서는 “함수를 인자로 받는다” 를 넘어 범용 수치 알고리즘 두 개를 만듭니다.

이분법#

부호가 다른 두 점 사이에는 근이 있습니다. 절반으로 잘라 가며 좁히면 됩니다.

func search(f F1, neg, pos float64) float64 {
	for {
		mid := (neg + pos) / 2
		if math.Abs(pos-neg) < 1e-12 {
			return mid
		}
		switch v := f(mid); {
		case v > 0:
			pos = mid
		case v < 0:
			neg = mid
		default:
			return mid
		}
	}
}

func halfIntervalMethod(f F1, a, b float64) (float64, error) {
	av, bv := f(a), f(b)
	switch {
	case av < 0 && bv > 0:
		return search(f, a, b), nil
	case bv < 0 && av > 0:
		return search(f, b, a), nil
	default:
		return 0, fmt.Errorf("값의 부호가 같습니다: %v, %v", a, b)
	}
}

원서는 부호가 같으면 에러를 냅니다. Go 답게 error 를 두 번째 반환값으로 돌려주도록 바꿨습니다. 이런 사소한 번역이 실은 언어의 성격을 보여 줍니다. Scheme 은 에러를 던지고, Go 는 값으로 돌려줍니다.

sin(x)=0 의 근 (2,4)  = 3.1415926536  (π = 3.1415926536)
x³-2x-3=0 의 근 (1,2) = 1.8932891963

π 를 소수점 열째 자리까지 정확히 찾아냈습니다. 함수를 몰라도, 부호만 바뀌면 됩니다.

고정점#

f(x) = x 인 x 를 찾습니다. 방법은 무식합니다. 아무 데서나 시작해서 f 를 계속 먹입니다.

func fixedPoint(f F1, first float64, maxIter int) (float64, int, bool) {
	guess := first
	for i := 1; i <= maxIter; i++ {
		next := f(guess)
		if math.Abs(next-guess) < 1e-12 {
			return next, i, true
		}
		guess = next
	}
	return guess, maxIter, false // 수렴하지 않았다
}

원서와 다르게 수렴 여부를 반환값에 넣었습니다. 원서의 fixed-point 는 수렴하지 않으면 영원히 돕니다. 곧 그 경우를 실제로 만나게 되므로, 미리 상한을 걸어 두는 편이 정직합니다.

cos 의 고정점 = 0.7390851332 (69회, 수렴=true)

계산기에서 아무 숫자나 넣고 cos 버튼을 계속 누르면 0.739… 로 수렴하는 그 현상입니다. 이 값을 도트리 상수(Dottie number)라고 부릅니다.

4. 평균 감쇠 — 수렴하지 않는 것을 수렴하게 만들기#

√x 는 y = x/y 를 만족하는 y 입니다. 그러니 y ↦ x/y 의 고정점을 찾으면 됩니다. 돌려 봤습니다.

감쇠 없는 y->x/y : 100회, 수렴=false

수렴하지 않습니다. 이유는 간단합니다. x=4, 추측이 1이면 다음은 4, 그 다음은 1, 그 다음은 4. 1과 4 사이를 영원히 왕복합니다. 답인 2를 지날 때마다 반대편으로 튕겨 나갑니다.

원서의 처방이 평균 감쇠(average damping) 입니다. 튕겨 나간 값과 원래 값의 평균을 취합니다. 진폭이 절반으로 줄어들어 진동이 잦아듭니다.

func averageDamp(f F1) F1 {
	return func(x float64) float64 { return (x + f(x)) / 2 }
}

이 함수의 시그니처를 보십시오. F1 을 받아 F1 을 돌려줍니다. 함수를 먹고 함수를 뱉습니다. 1.3.4 의 주제인 “반환값으로서의 프로시저” 가 여기서 등장합니다.

평균 감쇠 적용 : 2.0000000000 (6회, 수렴=true)

100회에 실패하던 것이 6회에 끝났습니다. 알고리즘을 바꾼 게 아니라 함수를 한 겹 감쌌을 뿐입니다.

그리고 감싼 결과가 무엇인지 보면 재미있습니다. (y + x/y)/2 — Part 1 에서 뉴턴법이라고 불렀던 바로 그 식입니다. 뉴턴법의 제곱근 공식이 실은 y ↦ x/y 에 평균 감쇠를 씌운 것 이었습니다. 원서는 이 사실을 이 순서로 배치해서 드러냅니다.

5. 1.3.4 — 뉴턴법을 부품으로 분해하기#

원서는 여기서 한 단계 더 올라갑니다. 뉴턴법 자체를 일반적인 변환 으로 표현합니다.

g(x) = 0 의 근은, 함수

x ↦ x − g(x)/g'(x)

의 고정점입니다. 그러니 도함수를 구하는 방법만 있으면 뉴턴법을 고정점 탐색으로 환원할 수 있습니다. 도함수는 수치 미분으로 근사합니다.

const dx = 1e-5

func deriv(g F1) F1 {
	return func(x float64) float64 { return (g(x+dx) - g(x)) / dx }
}

func newtonTransform(g F1) F1 {
	dg := deriv(g)
	return func(x float64) float64 { return x - g(x)/dg(x) }
}

func newtonsMethod(g F1, guess float64) (float64, int, bool) {
	return fixedPoint(newtonTransform(g), guess, 100)
}

deriv 도 newtonTransform 도 함수를 받아 함수를 돌려줍니다. 이제 제곱근은 이렇게 됩니다.

newtonsMethod(func(y float64) float64 { return y*y - 4 }, 1.0)

newton(y²-4) : 2.0000000000 (6회)

같은 답, 같은 횟수. 다른 길로 도착했습니다.

flowchart LR
    FP["fixedPoint<br/>f(x)=x 인 x 찾기"]
    AD["averageDamp<br/>F1 → F1"]
    DV["deriv<br/>F1 → F1"]
    NT["newtonTransform<br/>F1 → F1"]
    S1["sqrt 방법 ①<br/>y ↦ x/y 에 감쇠"]
    S2["sqrt 방법 ②<br/>y²−x 에 뉴턴법"]

    AD --> S1
    DV --> NT --> S2
    S1 --> FP
    S2 --> FP

    style FP fill:#90EE90,color:#000000
    style AD fill:#87CEEB,color:#000000
    style DV fill:#87CEEB,color:#000000
    style NT fill:#87CEEB,color:#000000
    style S1 fill:#FFD700,color:#000000
    style S2 fill:#FFD700,color:#000000

원서가 이 절에서 하는 말은 이것입니다. 제곱근을 구하는 두 가지 방법이 있는 게 아니라, 둘 다 “어떤 함수를 변환한 뒤 고정점을 찾는다” 라는 하나의 패턴 이라는 것입니다. 그 패턴을 이름 붙일 수 있게 되면, 다음에 새 문제가 왔을 때 어느 조각을 갈아 끼울지 물어보면 됩니다.

그리고 이걸 가능하게 하는 언어의 조건이 하나입니다. 함수가 일급 값이어야 합니다. 원서의 표현으로는 “일급 시민의 권리” 입니다. 이름을 붙일 수 있고, 인자로 넘길 수 있고, 반환값이 될 수 있고, 자료구조에 넣을 수 있어야 합니다.

Go 는 네 가지를 전부 만족합니다. 여기까지는 원서를 그대로 따라왔습니다.

6. 제네릭이 필요해지는 순간#

그런데 다음 연습문제에서 벽에 부딪힙니다.

원서 연습문제 1.43 은 repeated 를 만들라고 합니다. 함수 f 와 횟수 n 을 받아, f 를 n 번 합성한 함수를 돌려주는 것입니다. Scheme 으로는 이렇습니다.

(define (repeated f n) ...)

Go 로 순진하게 옮기면 이렇게 됩니다.

func repeated(f F1, n int) F1 {
	return func(x float64) float64 {
		for i := 0; i < n; i++ { x = f(x) }
		return x
	}
}

repeated(square, 2)(5) → 625. 잘 돕니다.

이제 연습문제 1.45 로 갑니다. n제곱근을 고정점으로 구하려면 평균 감쇠를 여러 번 씌워야 한다는 문제입니다. 즉 averageDamp 를 repeated 로 반복 적용해야 합니다.

repeated(averageDamp, 3)(g)

컴파일러가 이렇게 말합니다.

cannot use averageDamp (value of type func(f F1) F1) as F1 value in argument to repeated
cannot use g (variable of type func(y float64) float64) as float64 value

당연합니다. repeated 는 float64 를 받아 float64 를 돌려주는 함수용으로 만들어졌는데, averageDamp 는 F1 을 받아 F1 을 돌려줍니다. 반복 적용의 대상이 숫자가 아니라 함수입니다.

Scheme 에서는 아무 일도 일어나지 않습니다. 타입이 없으니 repeated 는 무엇이든 반복합니다. Go 에서는 같은 코드를 두 벌 쓰거나, 제네릭을 쓰거나 둘 중 하나입니다.

// T 를 float64 로 쓰면 숫자의 반복 적용,
// T 를 F1 으로 쓰면 변환의 반복 적용이 된다.
func repeated[T any](f func(T) T, n int) func(T) T {
	return func(x T) T {
		for i := 0; i < n; i++ {
			x = f(x)
		}
		return x
	}
}

repeated[F1](averageDamp, 3)(g) 로 통과합니다.

여기서 짚고 갈 것이 있습니다. 이 제네릭은 자료구조를 담기 위한 것이 아닙니다. Go 제네릭을 소개할 때 흔히 드는 예는 Map[K, V] 나 Min[T Ordered] 같은 컨테이너·비교 함수입니다. 그런데 여기서 제네릭이 필요해진 이유는 추상화의 대상이 한 층 올라갔기 때문입니다. 숫자를 반복 적용하는 것과 변환을 반복 적용하는 것은 같은 구조인데, Go 1.17 까지는 이 “같음” 을 표현할 방법이 없었습니다.

Go 1.18 의 제네릭은 이 시리즈에서 여러 번 구원 투수로 등판합니다. 다만 한계도 분명합니다. 메서드에는 타입 파라미터를 붙일 수 없고, 고차 타입(higher-kinded type)도 없습니다. 즉 “어떤 컨테이너든 Map 을 지원한다” 같은 것은 여전히 표현할 수 없습니다. 2장에서 이 벽을 다시 만납니다.

7. 연습문제 1.45 — n제곱근에 감쇠가 몇 번 필요한가#

원서 1.45 는 이렇게 묻습니다. 제곱근은 감쇠 한 번이면 되고 세제곱근도 한 번이면 되는데, 네제곱근은 한 번으로 안 됩니다. 몇 번이 필요한가.

n=2 부터 32 까지 전부 측정했습니다. 대상은 1000 의 n제곱근이고, 시작 추측은 1.0, 수렴 판정은 1e-12, 반복 상한은 100만입니다.

n	⌊log₂ n⌋	최소 감쇠 횟수	그때 반복 횟수	결과
2	1	1	10	31.6227766017
3	1	1	42	10.0000000000
4	2	2	20	5.6234132519
7	2	2	103	2.6826957953
8	3	3	36	2.3713737057
14	3	3	119	1.6378937070
15	3	3	202	1.5848931925
16	4	4	64	1.5399265261
30	4	4	216	1.2589254118
31	4	4	417	1.2496091413
32	5	5	109	1.2409377608

최소 감쇠 횟수가 n=2 부터 32 까지 전 구간에서 ⌊log₂ n⌋ 과 정확히 일치합니다. 감쇠 횟수가 늘어나는 지점이 정확히 2의 거듭제곱입니다.

그리고 표에서 눈에 띄는 것이 하나 더 있습니다. 반복 횟수가 2의 거듭제곱 바로 앞에서 폭증합니다. n=15 는 202회, n=31 은 417회가 걸리는데, 각각 다음 칸인 n=16(64회), n=32(109회)에서 뚝 떨어집니다. 감쇠가 딱 한 겹 모자란 상태로 간신히 수렴하고 있다는 뜻입니다.

이 부분은 조사 중에 한 번 틀릴 뻔했습니다. 처음에는 반복 상한을 200으로 걸고 측정했는데, 그때 n=15 가 “감쇠 3회로는 수렴하지 않음” 으로 나왔습니다. ⌊log₂ 15⌋ = 3 과 어긋나는 결과였습니다. 상한을 올려 다시 재 보니 202회 만에 수렴했습니다. 측정 도구의 상한을 알고리즘의 성질로 착각할 뻔한 것입니다. 실측을 근거로 삼을 때 늘 따라오는 함정입니다.

8. Go 에 없는 것 — 그리고 없는 게 나은 이유#

1.3 을 Go 로 옮기면서 “이게 있었으면” 싶은 게 몇 가지 있습니다.

커링과 부분 적용. sum 에서 term 과 next 를 미리 묶어 두고 구간만 바꿔 부르고 싶을 때, Haskell 이라면 sum term next 로 끝납니다. Go 는 클로저를 손으로 만들어야 합니다.

func sumOver(term, next F1) func(a, b float64) float64 {
	return func(a, b float64) float64 { return sum(term, a, next, b) }
}

함수 합성 연산자. f ∘ g 를 쓰려면 헬퍼를 직접 만들어야 합니다. 제네릭 덕분에 한 번은 만들 수 있습니다.

func compose[A, B, C any](f func(B) C, g func(A) B) func(A) C {
	return func(x A) C { return f(g(x)) }
}

파이프라인 문법. x |> f |> g 같은 것이 없어서 g(f(x)) 로 안쪽부터 읽어야 합니다.

세 가지 모두 클로저로 흉내 낼 수 있고, 흉내 낸 결과는 원본보다 깁니다. 이건 Go 의 명시적 선택입니다. Go 는 읽는 사람이 코드에서 실행 순서를 바로 읽어낼 수 있는 것 을 문법 설탕보다 위에 둡니다.

다만 이 선택에는 대가가 따르고, 대가는 1.3 같은 코드에서 가장 크게 나타납니다. 원서 1.3 의 Scheme 코드는 열 줄이 안 되는 것이 많은데, 같은 내용의 Go 코드는 두세 배가 됩니다. 길이가 곧 나쁨은 아니지만, 짧아야 보이는 구조도 있습니다.

그래서 이 시리즈의 태도는 이렇습니다. Go 로 옮기되 Go 를 Scheme 처럼 쓰지는 않습니다. 원서가 함수 합성으로 표현한 것을 Go 에서 명시적 루프가 더 읽히면 루프로 씁니다. 옮기려는 것은 코드가 아니라 구조 입니다.

9. 이번 편의 정리#

SICP 1.3 의 주장	Go 에서
프로시저를 인자로 넘길 수 있다	성립. 게다가 시그니처가 계약을 문서화
`lambda` 로 이름 없는 프로시저를 만든다	성립. 다만 타입을 두 번 적어야 해서 길다
`let` 은 즉시 호출 lambda 다	Go 는 지역 변수가 별도 장치. 개념적으로 덜 통일적
프로시저를 반환값으로 돌려준다	성립. `averageDamp`, `deriv`, `newtonTransform` 모두 그대로
같은 `repeated` 를 아무 데나 쓴다	제네릭 없이는 불가. 추상화 층이 올라가면 타입이 갈라짐
커링·합성으로 조립한다	문법 지원 없음. 클로저로 손수 만들어야 함

1장이 여기서 끝납니다. 요약하면 이렇습니다. 1장은 프로시저를 값으로 다루는 법을 가르치고, 그 결과 계산 방법 자체를 조립 대상으로 만들었습니다.

2장은 조립 대상을 바꿉니다. 이번에는 데이터 입니다. cons, car, cdr 세 개로 시작해서, 그 세 개만으로 리스트·트리·기호식·집합을 전부 만듭니다. 그리고 그 과정에서 이 책의 두 번째 큰 아이디어인 “데이터란 무엇인가” 라는 질문 이 나옵니다. 답이 꽤 충격적입니다. Go 로 옮기면 더 충격적입니다. 타입이 있는 언어에서 “이것도 데이터다” 라고 주장하려면 무엇을 포기해야 하는지가 드러나기 때문입니다.

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. 1.3 절 전문 — https://sarabander.github.io/sicp/html/1_002e3.xhtml
연습문제 1.43 (repeated), 1.45 (n제곱근과 평균 감쇠 횟수)는 위 원문의 1.3.4 절에 있습니다.

본문의 실측 데이터

모든 수치는 go version go1.26.0 darwin/arm64 에서 직접 실행한 결과입니다.
7절의 표는 n=2 부터 32 까지 전 구간 을 측정한 것입니다. 지면 관계로 표에는 경계값 위주로 실었고, 최소 감쇠 횟수가 ⌊log₂ n⌋ 과 일치한다는 서술은 31개 값 전부에 대해 확인한 것입니다.
수렴 판정 기준은 연속한 두 추측의 차이가 1e-12 미만, 반복 상한은 100만입니다. 상한을 200으로 두었을 때 n=15 가 거짓 음성으로 나온 사례를 본문에 그대로 적었습니다.

시리즈