Go 로 읽는 SICP Part 5: 파이프라인으로서의 프로그램, 그리고 quote 가 없는 언어

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

Part 4에서 Cons·Car·Cdr 세 개로 리스트와 트리를 만들었습니다. 이번 편은 그 위에서 두 가지를 합니다.

앞쪽은 2.2.3 관례적 인터페이스 입니다. map, filter, accumulate 세 개로 프로그램의 모양을 바꾸는 이야기이고, 이 책에서 실무에 가장 직접적으로 쓸모 있는 절입니다. Go 1.23 이 iter.Seq 를 넣은 이유와 정확히 같은 이야기이기도 합니다.

뒤쪽은 2.3 기호 데이터 입니다. 여기서 Part 1 에 예고한 마찰 두 번째 — Go 에는 quote 가 없다 — 를 처음 만납니다.

1. 2.2.3 — 같은 뼈대가 자꾸 나온다#

원서는 두 프로그램을 나란히 놓습니다.

하나는 트리에서 홀수인 잎을 찾아 제곱해 더하는 것, 다른 하나는 피보나치 수 중 짝수만 모아 리스트로 만드는 것입니다. 하는 일이 전혀 다릅니다. 그런데 원서는 둘이 같은 모양 이라고 말합니다.

flowchart LR
    E1["열거<br/>enumerate"] --> F1["거르기<br/>filter: 홀수"] --> M1["변환<br/>map: 제곱"] --> A1["모으기<br/>accumulate: +"]
    E2["열거<br/>enumerate"] --> M2["변환<br/>map: fib"] --> F2["거르기<br/>filter: 짝수"] --> A2["모으기<br/>accumulate: cons"]

    style E1 fill:#90EE90,color:#000000
    style E2 fill:#90EE90,color:#000000
    style F1 fill:#FFD700,color:#000000
    style F2 fill:#FFD700,color:#000000
    style M1 fill:#87CEEB,color:#000000
    style M2 fill:#87CEEB,color:#000000
    style A1 fill:#FFA07A,color:#000000
    style A2 fill:#FFA07A,color:#000000

원서의 비유가 신호 처리 파이프라인 입니다. 신호가 단계를 거치며 흘러가고, 각 단계는 자기 일만 합니다. 그런데 보통 이렇게 짜지 않습니다. 재귀 함수 하나에 열거·거르기·변환·모으기가 전부 뒤엉켜 들어갑니다. 구조가 있는데 코드에 안 보이는 상태 가 됩니다.

원서의 처방은 각 단계를 실제 함수로 만드는 것입니다.

func Map(f func(any) any, l any) any {
	if l == nil { return nil }
	return Cons(f(Car(l)), Map(f, Cdr(l)))
}

func Filter(pred func(any) bool, l any) any {
	switch {
	case l == nil:
		return nil
	case pred(Car(l)):
		return Cons(Car(l), Filter(pred, Cdr(l)))
	default:
		return Filter(pred, Cdr(l))
	}
}

// 오른쪽 접기
func Accumulate(op func(a, b any) any, initial any, l any) any {
	if l == nil { return initial }
	return op(Car(l), Accumulate(op, initial, Cdr(l)))
}

그리고 열거자 두 개.

func EnumerateInterval(lo, hi int) any { /* (lo lo+1 ... hi) */ }

func EnumerateTree(t any) any {
	switch v := t.(type) {
	case nil:
		return nil
	case *Pair:
		return Append(EnumerateTree(v.Car), EnumerateTree(v.Cdr))
	default:
		return List(t) // 잎
	}
}

이제 두 프로그램이 파이프라인이 됩니다.

func sumOddSquares(tree any) int {
	return Accumulate(
		func(a, b any) any { return a.(int) + b.(int) }, 0,
		Map(func(x any) any { return square(x.(int)) },
			Filter(func(x any) bool { return x.(int)%2 == 1 },
				EnumerateTree(tree)))).(int)
}

tree          = ((1 (2 3)) (4 (5 (6 7))))
EnumerateTree = (1 2 3 4 5 6 7)
sumOddSquares = 84        (1² + 3² + 5² + 7² = 84)
evenFibs(10)  = (0 2 8 34)

타입 단언(.(int))이 눈에 거슬립니다. Part 4 에서 Pair 를 any 로 만들기로 한 대가가 여기서 청구됩니다. 원서의 Scheme 코드에는 이 잡음이 없습니다.

원서가 이 절에서 강조하는 것은 재사용성입니다. 파이프라인 부품이 표준화되면 조각을 바꿔 끼워서 새 프로그램을 만들 수 있습니다. 실제로 원서는 같은 부품으로 여러 프로그램을 조립해 보입니다. 이 아이디어가 30년 뒤에 Stream, LINQ, RxJS, iterator 라는 이름으로 거의 모든 언어에 들어왔습니다.

2. 같은 것을 Go 1.23 방식으로 쓰면#

Go 는 오랫동안 이 이야기에 냉담했습니다. for 문이 있는데 왜 map 이 필요하냐는 입장이었습니다.

그런데 Go 1.23 이 range-over-func 을 넣으면서 상황이 바뀌었습니다. iter.Seq[T] 는 사실 func(yield func(T) bool) 일 뿐이고, 이걸로 파이프라인을 만들 수 있습니다.

func MapSeq[A, B any](f func(A) B, s iter.Seq[A]) iter.Seq[B] {
	return func(yield func(B) bool) {
		for v := range s {
			if !yield(f(v)) { return }
		}
	}
}

func FilterSeq[A any](pred func(A) bool, s iter.Seq[A]) iter.Seq[A] {
	return func(yield func(A) bool) {
		for v := range s {
			if pred(v) && !yield(v) { return }
		}
	}
}

같은 계산을 이렇게 씁니다.

nums := Seq(1, 2, 3, 4, 5, 6, 7)
odds := FilterSeq(func(x int) bool { return x%2 == 1 }, nums)
squares := MapSeq(func(x int) int { return x * x }, odds)
Fold(func(a, b int) int { return a + b }, 0, squares) // 84

합: 84
라벨: [#1 #2 #3]
무한 수열 앞 5개: [1 2 3 4 5]

원서의 리스트 판과 결과가 같습니다. 그런데 성질이 셋 다릅니다.

	SICP 리스트 파이프라인	Go `iter.Seq` 파이프라인
타입	`any` 뿐. 단언 필요	제네릭. `iter.Seq[int]` → `iter.Seq[string]` 이 타입 검사됨
중간 결과	단계마다 새 리스트 전부 생성	생성하지 않음. 값이 하나씩 흘러감
무한 수열	불가 (3장의 스트림이 필요)	가능. `yield` 가 `false` 를 돌려주면 멈춤

두 번째가 원서도 인정하는 약점입니다. 2.2.3 의 파이프라인은 단계마다 리스트를 통째로 만듭니다. 원소 100만 개를 걸러서 변환하면 100만 개짜리 리스트가 두 번 더 생깁니다. 원서는 이 문제를 3.5 절의 스트림 으로 풀고, 그게 Part 9 의 주제입니다.

iter.Seq 는 그 문제를 처음부터 겪지 않습니다. 소비자가 값을 하나 요구하면 생산자가 하나 만듭니다. SICP 3.5 가 손으로 만드는 것을 Go 1.23 이 언어에 넣은 셈 입니다. 다만 완전히 같지는 않은데, 그 차이가 Part 9 의 핵심입니다.

3. 중첩된 매핑, 그리고 여덟 퀸#

2.2.3 의 마지막은 중첩 매핑 입니다. 리스트 안에서 리스트를 만들고 평평하게 펴는 패턴입니다. 다른 언어에서 flatMap 이라고 부르는 것입니다.

func FlatMap(f func(any) any, l any) any {
	return Accumulate(func(a, b any) any { return Append(a, b) }, nil, Map(f, l))
}

원서의 첫 예제는 1 ≤ j < i ≤ n 인 쌍 중 i+j 가 소수인 것을 찾는 것입니다.

primeSumPairs(6) = ((2 1 3) (3 2 5) (4 1 5) (4 3 7) (5 2 7) (6 1 7) (6 5 11))

그리고 연습문제 2.42, 여덟 퀸 문제 가 나옵니다. 8×8 체스판에 퀸 여덟 개를 서로 공격하지 않게 놓는 방법을 전부 찾는 문제입니다.

원서의 해법이 아름다운 이유는 백트래킹을 명시적으로 짜지 않기 때문입니다. k-1 열까지의 모든 안전한 배치를 구해 놓고, 각각에 대해 k 열의 모든 행을 시도하고, 안전한 것만 거릅니다. 그게 전부입니다.

func queens(boardSize int) any {
	var queenCols func(k int) any
	queenCols = func(k int) any {
		if k == 0 {
			return List(nil) // 빈 배치 하나
		}
		return Filter(func(positions any) bool { return safe(k, positions) },
			FlatMap(func(rest any) any {
				return Map(func(newRow any) any { return Cons(newRow, rest) },
					EnumerateInterval(1, boardSize))
			}, queenCols(k-1)))
	}
	return queenCols(boardSize)
}

k == 0 일 때 빈 리스트가 아니라 “빈 배치 하나를 담은 리스트” 를 돌려주는 게 요령입니다. List(nil) 입니다. 빈 리스트를 돌려주면 FlatMap 이 아무것도 못 만들어서 전부 사라집니다. 원서 연습문제를 처음 푸는 사람이 가장 많이 걸리는 곳입니다.

queens(4) 해의 개수 = 2
queens(5) 해의 개수 = 10
queens(6) 해의 개수 = 4
queens(7) 해의 개수 = 40
queens(8) 해의 개수 = 92
queens(8) 첫 해 = (4 2 7 3 6 8 5 1)

92개. 여덟 퀸 문제의 해가 92개라는 건 잘 알려진 값입니다. 4×4가 2개, 6×6이 4개로 뚝 떨어지는 것도 맞습니다.

여기서 짚을 것이 있습니다. 이 코드에는 “되돌아가라” 는 명령이 한 줄도 없습니다. 백트래킹처럼 보이는 동작이 filter 에서 저절로 나옵니다. 조건에 안 맞는 후보는 다음 단계로 넘어가지 않을 뿐입니다.

이 발상이 4장의 amb 평가기로 직행합니다. 4.3 절이 하는 일은 이 “생성하고 거른다” 패턴을 언어 기능으로 승격시키는 것입니다. Part 12 에서 다시 만납니다.

4. 2.3 — 기호 데이터, 그리고 quote 라는 마찰#

이제 후반부입니다.

지금까지 리스트에 넣은 것은 숫자였습니다. 2.3 은 심볼 을 넣습니다. Scheme 에서 심볼을 만드는 것은 따옴표 하나입니다.

(define a 1)
(define b 2)
(list a b)     ; => (1 2)
(list 'a 'b)   ; => (a b)

'a 는 “a 라는 이름이 가리키는 값” 이 아니라 "a 라는 이름 자체" 입니다. quote 는 평가를 한 단계 멈추는 장치입니다.

Go 에는 이런 게 없습니다. Go 소스의 x 는 항상 변수 x 의 값을 뜻하고, 그 이름 자체를 값으로 얻을 방법이 문법에 없습니다.

우회는 어렵지 않습니다. 심볼 타입을 하나 만들면 됩니다.

// 문자열과 구별하기 위해 별도 타입으로 둔다
type Symbol string

Symbol("a") 가 'a 를 대신합니다. 그런데 이 우회가 잃는 것이 하나 있습니다. quote 는 심볼만 만드는 게 아니라 리스트 전체를 만듭니다.

'(* (* x y) (+ x 3))

Scheme 에서는 이 한 줄이 곧 식이자 데이터입니다. Go 에서는 이렇게 써야 합니다.

List(Symbol("*"), List(Symbol("*"), Symbol("x"), Symbol("y")),
	List(Symbol("+"), Symbol("x"), 3))

이 차이가 4장에서 결정적으로 커집니다. 원서의 메타순환 평가기가 짧은 이유는 프로그램을 quote 로 그냥 받을 수 있기 때문입니다. Go 에서는 문자열을 파싱해야 합니다. Part 10 에서 렉서와 파서를 손으로 만듭니다.

지금 단계에서는 List(Symbol(...), ...) 이 장황할 뿐 막히지는 않습니다. 그래서 2.3 은 무사히 통과합니다.

5. 2.3.2 — 기호 미분#

d/dx (x·y·(x+3)) 을 계산하는 프로그램입니다. 수식을 데이터로 다룹니다.

미분 규칙은 재귀적으로 정의됩니다. 상수의 미분은 0, 변수의 미분은 자기 자신이면 1 아니면 0, 합의 미분은 미분의 합, 곱의 미분은 곱셈 규칙. 그대로 옮기면 됩니다.

func deriv(exp, v any) any {
	switch {
	case isNumber(exp):
		return 0
	case isVariable(exp):
		if sameVariable(exp, v) { return 1 }
		return 0
	case isSum(exp):
		return makeSum(deriv(Cadr(exp), v), deriv(Caddr(exp), v))
	case isProduct(exp):
		return makeSum(
			makeProduct(Cadr(exp), deriv(Caddr(exp), v)),
			makeProduct(deriv(Cadr(exp), v), Caddr(exp)))
	}
	panic("알 수 없는 식: " + Write(exp))
}

여기서 원서의 설계가 빛나는 지점 이 있습니다. deriv 는 식이 리스트로 표현된다는 사실을 모릅니다. isSum, Cadr, makeSum 같은 이름만 씁니다. 표현을 바꿔도 deriv 는 그대로입니다. Part 4 의 추상화 장벽이 여기서 실제로 값을 합니다.

그리고 단순화가 생성자 안 에 들어 있습니다.

func makeSum(a, b any) any {
	switch {
	case isSameNumber(a, 0):
		return b          // 0 + b = b
	case isSameNumber(b, 0):
		return a
	case isNumber(a) && isNumber(b):
		return a.(int) + b.(int)
	}
	return List(Symbol("+"), a, b)
}

deriv 는 단순화를 전혀 모릅니다. 그냥 makeSum 을 부를 뿐입니다.

d/dx (+ x 3)             = 1
d/dx (* x y)             = y
d/dx (* (* x y) (+ x 3)) = (+ (* x y) (* y (+ x 3)))

세 번째 줄을 손으로 확인해 보면, (xy)·1 + y·(x+3) = xy + y(x+3) 입니다. 맞습니다. 그리고 (* (* x y) 1) 이 (* x y) 로 줄어든 것이 makeProduct 의 단순화 덕분입니다.

원서는 여기서 정직하게 한계를 인정합니다. 이 단순화는 형편없습니다. xy + xy + 3y 로 더 줄일 수 있는데 안 합니다. 그러려면 대수 시스템이 필요하고, 그게 2.5.3 절의 주제입니다.

Go 로 옮기면서 눈에 띄는 것은 switch { case ... } 가 Scheme 의 cond 와 거의 1:1 이라는 점입니다. Go 의 태그 없는 switch 는 사실상 cond 입니다. 이 대응 덕분에 2~4장의 술어 분기 코드가 거의 기계적으로 옮겨집니다.

6. 2.3.4 — Huffman 부호화 트리#

2장의 마지막 큰 예제입니다. 자주 나오는 심볼에 짧은 부호를, 드문 심볼에 긴 부호를 주는 가변 길이 부호화입니다.

핵심 제약은 접두 부호(prefix code) 여야 한다는 것입니다. 어떤 부호도 다른 부호의 접두사가 되면 안 됩니다. 그래야 구분자 없이 붙여 써도 해독됩니다. 트리로 표현하면 이 제약이 저절로 만족됩니다. 심볼이 전부 잎에 있으면 되기 때문입니다.

Go 로는 두 타입으로 표현합니다.

type Leaf struct {
	Sym    Symbol
	Weight int
}
type Node struct {
	Left, Right any
	Syms        []Symbol
	Weight      int
}

원서는 이것도 리스트로 표현합니다((leaf symbol weight) 같은 태그된 리스트). Go 에서는 구조체 두 개와 타입 스위치가 훨씬 자연스럽고, 표현만 바뀌었지 인터페이스는 원서와 같습니다. symbolsOf, weightOf, makeCodeTree 세 개면 위층이 돌아갑니다. 추상화 장벽이 실제로 작동한다는 증거입니다.

트리 생성은 Huffman 의 원래 알고리즘 그대로입니다. 가장 가벼운 둘을 합치기를 반복합니다.

for len(set) > 1 {
	merged := makeCodeTree(set[0], set[1]) // 가장 가벼운 둘
	set = append([]any{merged}, set[2:]...)
	sortSet()
}

A=8, B=3, 나머지 여섯 개가 각각 1인 빈도로 만들어 봤습니다.

  A -> [0]
  B -> [1 1 1]
  C -> [1 1 0 0]
  D -> [1 1 0 1]
  E -> [1 0 1 0]
  F -> [1 0 1 1]
  G -> [1 0 0 0]
  H -> [1 0 0 1]

메시지    : [B A C A D A E A F A B B A A A G A H]
부호화    : 총 42 비트
고정길이면: 54 비트 (심볼 8종 -> 3비트)
복호화 일치: true

A 는 1비트, B 는 3비트, 나머지는 4비트입니다. 18개 심볼을 42비트 로 담았습니다. 고정 길이라면 54비트가 필요합니다. 22% 절약입니다.

한 가지 밝혀 둘 것이 있습니다. 위 부호는 원서 그림 2.18 의 트리와 모양이 다릅니다. 원서는 A=0, B=100, C=1010 … 을 얻습니다. 부호 길이는 같습니다(A 1비트, B 3비트, 나머지 4비트). 같은 무게를 가진 노드가 여러 개일 때 어느 쪽을 먼저 합치느냐에 따라 트리 모양이 갈리고, 어느 쪽이든 총 비트 수는 같습니다. Huffman 알고리즘의 최적성은 트리 모양이 아니라 부호 길이 분포에 대한 것입니다.

원서 연습문제 2.71 이 이 구조를 일반화합니다. 빈도가 1, 2, 4, 8, …, 2ⁿ⁻¹ 처럼 배치되면 가장 흔한 심볼은 몇 비트가 되는가. n=2 부터 12 까지 실제로 트리를 만들어 재 봤습니다.

n= 2  가장 흔한 심볼 1비트, 가장 드문 심볼 1비트 (n-1=1)
n= 5  가장 흔한 심볼 1비트, 가장 드문 심볼 4비트 (n-1=4)
n=10  가장 흔한 심볼 1비트, 가장 드문 심볼 9비트 (n-1=9)
n=12  가장 흔한 심볼 1비트, 가장 드문 심볼 11비트 (n-1=11)

가장 흔한 심볼은 n 과 무관하게 항상 1비트, 가장 드문 심볼은 n−1비트 입니다. 트리가 완전히 한쪽으로 늘어진 모양이 되기 때문입니다. 위 A=8 예제에서 A 가 1비트인 것도 같은 현상의 약한 버전입니다.

7. 2.3.3 집합 — 표현을 바꾸면 복잡도가 바뀐다#

지면상 코드는 생략하지만, 2.3.3 절의 요점만 정리해 둘 값어치가 있습니다. 원서는 같은 “집합” 을 세 가지로 표현하고 복잡도를 비교합니다.

표현	`elementOfSet?`	`adjoinSet`	`intersectionSet`
정렬 안 된 리스트	Θ(n)	Θ(n)	Θ(n²)
정렬된 리스트	Θ(n) (평균 n/2)	Θ(n)	Θ(n)
이진 트리 (균형 잡힌 경우)	Θ(log n)	Θ(log n)	리스트로 변환 후 Θ(n)

그리고 원서는 마지막에 함정을 짚습니다. 이진 트리의 Θ(log n) 은 트리가 균형 잡혀 있을 때만 성립합니다. 정렬된 데이터를 순서대로 넣으면 트리가 한쪽으로 늘어져서 연결 리스트가 되고, 복잡도는 Θ(n) 으로 돌아갑니다.

이 절이 전달하는 것은 자료구조 지식이 아니라 인터페이스가 같아도 성능 특성은 표현이 결정한다 는 것입니다. Part 4 에서 “표현을 바꿔도 위층은 안 바뀐다” 고 했는데, 그건 정확성 에 대한 이야기이지 성능 에 대한 이야기가 아니었습니다. 추상화 장벽은 복잡도를 숨겨 주지 않습니다.

Go 에서 이 교훈이 나타나는 자리가 있습니다. map[K]V 를 인터페이스 뒤에 숨겼는데 실제 구현이 슬라이스 선형 탐색이면, 호출하는 쪽 코드는 그대로여도 프로덕션에서 죽습니다. 인터페이스는 계약이지 성능 보증서가 아닙니다.

8. 이번 편의 정리#

SICP 2.2.3~2.3 의 주장	Go 에서
map/filter/accumulate 로 파이프라인을 만든다	성립. 다만 `any` 라 타입 단언 잡음이 생김
파이프라인 부품은 재사용된다	성립. `iter.Seq` 로 쓰면 제네릭까지 얻음
중첩 매핑으로 백트래킹이 저절로 나온다	성립. 여덟 퀸 92개 재현
`quote` 로 기호를 만든다	없음. `Symbol` 타입으로 우회. 4장에서 청구서 도착
`cond` 로 표현의 종류를 분기한다	성립. Go 의 태그 없는 `switch` 가 거의 `cond`
표현을 바꿔도 위층은 안 바뀐다	성립. Huffman 을 구조체로 바꿔도 인터페이스 동일
추상화 장벽이 복잡도를 숨겨 주지는 않는다	그대로 성립

다음 편은 2장의 마지막인 2.4~2.5 입니다. 하나의 연산이 여러 표현을 동시에 지원하는 시스템을 만듭니다. 태그드 데이터, 데이터 지향 프로그래밍, 그리고 메시지 패싱.

이 대목이 이 시리즈에서 Go 와 궁합이 가장 좋은 곳 입니다. 원서가 1985년에 “데이터 지향 프로그래밍” 이라고 부른 것이 Go 인터페이스 설계 이야기와 사실상 같은 내용이기 때문입니다. 그런데 완전히 같지는 않고, 다른 부분이 오히려 더 흥미롭습니다. 원서가 지적하는 “새 타입을 추가하기 쉬운가, 새 연산을 추가하기 쉬운가” 라는 딜레마가 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.
- 2.2 절 (관례적 인터페이스·중첩 매핑) — https://sarabander.github.io/sicp/html/2_002e2.xhtml
- 2.3 절 (기호 데이터·집합·Huffman) — https://sarabander.github.io/sicp/html/2_002e3.xhtml
여덟 퀸은 연습문제 2.42, Huffman 부호 길이의 일반화는 연습문제 2.71 입니다.

본문의 실측 데이터

모든 출력값은 go version go1.26.0 darwin/arm64 에서 직접 실행한 결과입니다.
여덟 퀸의 해 개수(4×4=2, 5×5=10, 6×6=4, 7×7=40, 8×8=92)는 잘 알려진 값과 일치합니다.
Huffman 부호는 원서 그림 2.18 과 트리 모양이 다릅니다. 같은 무게 노드의 병합 순서 차이 때문이며, 부호 길이 분포(A 1비트, B 3비트, 나머지 4비트)는 같습니다. 이 사실을 본문에 명시했습니다.
연습문제 2.71 의 부호 길이(가장 흔한 심볼 1비트, 가장 드문 심볼 n−1비트)는 n=2 부터 12 까지 실제로 트리를 만들어 Go 테스트로 확인했습니다.
42비트·54비트·“20% 이상 절약” 은 원서 2.3.4 절 본문의 값과 일치합니다. 예제 메시지 BACADAEAFABBAAAGAH 도 원서와 같은 것입니다.
7절의 복잡도 표는 원서 2.3.3 절의 서술을 정리한 것이며, 코드로 측정한 값이 아닙니다. unionSet 은 원서가 연습문제로 남겨 두었으므로 표에서 제외했습니다.

시리즈