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

Part 3까지 1장을 끝냈습니다. 1장이 조립한 것은 계산 방법 이었습니다. 프로시저를 값으로 다루니 계산 방법 자체를 인자로 넘기고 반환할 수 있게 되었습니다.

2장은 조립 대상을 바꿉니다. 이번에는 데이터 입니다.

그런데 2장을 읽다 보면 예상 못 한 질문 하나가 정면으로 나옵니다. 2.1.3 절의 제목이 What Is Meant by Data? 입니다. 데이터가 뭐냐고 묻습니다. 이미 1장 내내 숫자를 다뤄 놓고 이제 와서 묻습니다.

그리고 답이 상당히 과격합니다. Go 로 옮기면 더 과격해집니다.

1. 2.1.1 — 유리수를 만들면서 시작합니다#

유리수 산술을 만듭니다. 필요한 것은 셋입니다. 분자와 분모로 유리수를 만드는 것, 분자를 꺼내는 것, 분모를 꺼내는 것.

type Rat struct{ n, d int }

func MakeRat(n, d int) Rat {
	g := gcd(n, d)
	if d < 0 {
		n, d = -n, -d // 부호는 분자가 가진다
	}
	return Rat{n / g, d / g}
}

func Numer(r Rat) int { return r.n }
func Denom(r Rat) int { return r.d }

이 셋만 있으면 사칙연산은 산수입니다.

func AddRat(x, y Rat) Rat {
	return MakeRat(Numer(x)*Denom(y)+Numer(y)*Denom(x), Denom(x)*Denom(y))
}
func MulRat(x, y Rat) Rat {
	return MakeRat(Numer(x)*Numer(y), Denom(x)*Denom(y))
}

1/2 + 1/3 = 5/6
1/2 * 1/3 = 1/6
1/3 + 1/3 = 2/3
6/4       = 3/2
1/-2      = -1/2

주목할 것은 AddRat 이 r.n 이나 r.d 를 직접 건드리지 않는다 는 점입니다. Numer 와 Denom 을 거칩니다. 지금은 쓸데없어 보입니다. 구조체 필드를 그냥 읽으면 되는데 함수를 한 겹 씌운 것뿐이니까요.

이게 쓸데없지 않은 이유가 2.1.3 에서 나옵니다.

또 하나. 약분(gcd 로 나누는 것)을 MakeRat 안에서 합니다. 원서는 이 위치를 일부러 논의합니다. Numer/Denom 에서 약분할 수도 있습니다. 그러면 만들 때는 싸고 꺼낼 때마다 비싸집니다. 어느 쪽이 옳은지는 사용 패턴에 달렸고, 중요한 것은 이 결정을 바꿔도 AddRat 은 손댈 필요가 없다는 것입니다.

2. 2.1.2 — 추상화 장벽#

원서는 여기서 그림 하나를 그립니다. 이 책에서 가장 많이 인용되는 그림 중 하나입니다.

flowchart TD
    A["유리수를 사용하는 프로그램"]
    B["AddRat  SubRat  MulRat  DivRat"]
    C["MakeRat  Numer  Denom"]
    D["표현: 구조체? 클로저? 두 칸 슬라이스?"]

    A -->|"유리수라는 것만 안다"| B
    B -->|"분자와 분모라는 것만 안다"| C
    C -->|"pair 라는 것만 안다"| D

    style A fill:#90EE90,color:#000000
    style B fill:#87CEEB,color:#000000
    style C fill:#FFD700,color:#000000
    style D fill:#FFA07A,color:#000000

각 층은 바로 아래 층의 인터페이스만 압니다. 그 아래는 모릅니다. 화살표에 붙은 문구가 각 층이 아는 전부입니다.

이 구조가 주는 것은 두 가지입니다.

첫째, 결정을 미룰 수 있습니다. Rat 을 구조체로 할지 다른 걸로 할지 아직 안 정해도 AddRat 을 쓸 수 있습니다. 원서는 실제로 유리수 산술을 다 만들고 나서야 pair 를 도입합니다.

둘째, 결정을 바꿀 수 있습니다. 표현을 갈아도 위층은 그대로입니다.

Go 에서 이 장벽을 세우는 도구는 두 가지입니다. 패키지 경계와 대문자/소문자 규칙 입니다. Rat 을 별도 패키지에 넣고 필드를 소문자로 두면, 바깥에서는 Numer/Denom 을 거칠 수밖에 없습니다. 원서는 “그렇게 하는 게 좋다” 는 관습으로 말하지만, Go 에서는 컴파일러가 강제합니다.

3. 2.1.3 — 그래서 데이터가 뭔데#

이제 문제의 절입니다.

원서는 이렇게 묻습니다. MakeRat, Numer, Denom 이 만족해야 하는 조건이 정확히 무엇인가. 답은 딱 하나 입니다.

MakeRat(n, d) 로 만든 x 에 대해 Numer(x)/Denom(x) = n/d 이면 된다.

그게 전부입니다. 그 밖에는 아무 요구도 없습니다. 그리고 pair 로 내려가면 조건은 이렇게 됩니다.

Cons(x, y) 로 만든 z 에 대해 Car(z) = x 이고 Cdr(z) = y 이면 된다.

원서는 여기서 폭탄을 던집니다. 이 조건을 만족하는 데 저장 공간이 필요 없다는 것입니다. 클로저 세 개면 됩니다.

(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)))

cons 는 값을 어디에도 저장하지 않습니다. x 와 y 를 붙잡고 있는 함수를 하나 만들어 돌려줄 뿐입니다. car 는 그 함수에게 “두 값 중 첫 번째를 주는 방법” 을 넘겨 줍니다. cdr 은 두 번째를 주는 방법을 넘겨 줍니다.

Go 로 옮기면 이렇습니다.

type Selector = func(x, y any) any

func ConsFn(x, y any) func(Selector) any {
	return func(m Selector) any { return m(x, y) }
}
func CarFn(z func(Selector) any) any { return z(func(p, q any) any { return p }) }
func CdrFn(z func(Selector) any) any { return z(func(p, q any) any { return q }) }

돌려 봤습니다.

CarFn(z) = 37
CdrFn(z) = hello
CarFn(CarFn(zz)) = 1

동작합니다. ConsFn(ConsFn(1, 2), 3) 처럼 중첩도 됩니다.

이게 무슨 뜻인가. Rat 을 struct{ n, d int } 로 정의한 것은 하나의 선택지였을 뿐이고, 데이터를 데이터로 만드는 것은 저장 구조가 아니라 연산들이 함께 지키는 약속 이라는 것입니다.

원서는 이걸 “프로시저적 표현(procedural representation)” 이라고 부르고, 3장에서 이 아이디어를 메시지 패싱 으로 확장합니다. 객체 지향의 뿌리가 여기 있습니다. 객체란 결국 “메시지를 받으면 약속대로 답하는 무엇” 이고, 그 안에 필드가 있든 없든 상관없습니다.

데이터는 자료구조가 아니라 계약 이다.

이게 2장의 첫 번째 큰 아이디어입니다.

4. 제네릭으로 옮기려다 천장에 부딪히다#

위의 ConsFn 은 any 를 씁니다. 타입이 있는 언어에서 any 를 쓰는 건 타입을 포기한 것과 비슷합니다. 그러니 제네릭으로 제대로 써 보고 싶어집니다.

func ConsG[A, B, R any](x A, y B) func(func(A, B) R) R {
	return func(m func(A, B) R) R { return m(x, y) }
}

만들어지긴 합니다. car 도 됩니다.

z := ConsG[int, string, int](37, "hello")
z(func(p int, q string) int { return p }) // 37

그런데 같은 z 에서 cdr 을 꺼내려고 하면 이렇게 됩니다.

cannot use (func(p int, q string) string literal)
  (value of type func(p int, q string) string)
  as func(int, string) int value in argument to z

이유가 정확합니다. ConsG 를 호출하는 순간 결과 타입 R 이 하나로 고정 됩니다. 위에서는 int 로 고정했습니다. 그런데 car 는 R = A 를, cdr 은 R = B 를 원합니다. 하나의 값이 두 개의 R 을 동시에 가질 수 없습니다.

Scheme 에서는 이런 일이 없습니다. 타입이 없으니 z 에 아무 함수나 넘길 수 있습니다.

이걸 제대로 표현하려면 “어떤 R 에 대해서도” 라는 말을 타입에 쓸 수 있어야 합니다. 학술 용어로는 rank-2 다형성이라고 하고, Haskell 의 forall r. (a -> b -> r) -> r 이 그것입니다. Go 에는 없습니다. 그리고 앞으로도 들어올 계획이 없습니다.

이건 Go 의 결함이라기보다 설계 선택입니다. Go 제네릭은 “같은 코드를 여러 타입에 쓰기” 를 위한 것이지, 타입 수준에서 추상화를 쌓기 위한 것이 아닙니다.

그래서 이 시리즈의 방침을 여기서 정합니다. SICP 의 Pair 는 any 로 만듭니다.

type Pair struct{ Car, Cdr any }

func Cons(a, d any) *Pair { return &Pair{a, d} }

func Car(p any) any {
	pr, ok := p.(*Pair)
	if !ok {
		panic(fmt.Sprintf("car: pair 가 아닙니다: %v", p))
	}
	return pr.Car
}

타입 안전성을 포기하는 대신 원서의 구조를 지킵니다. 그리고 포기하지 않아도 되는 곳에서는 포기하지 않습니다. 8절에서 그 경계를 정리합니다.

5. 2.1.4 — 구간 산술, 그리고 Go 가 더 나은 자리#

2.1 의 마지막은 확장 연습문제입니다. 저항값처럼 오차 범위가 있는 수 를 다룹니다. 6.8Ω ±10% 저항 두 개를 병렬로 연결하면 합성 저항의 범위는 얼마인가.

type Interval struct{ Lo, Hi float64 }

func AddInterval(x, y Interval) Interval { return Interval{x.Lo + y.Lo, x.Hi + y.Hi} }

func MulInterval(x, y Interval) Interval {
	p := []float64{x.Lo * y.Lo, x.Lo * y.Hi, x.Hi * y.Lo, x.Hi * y.Hi}
	lo, hi := p[0], p[0]
	for _, v := range p[1:] {
		if v < lo { lo = v }
		if v > hi { hi = v }
	}
	return Interval{lo, hi}
}

여기서 원서 연습문제 2.10 이 좋은 지적을 합니다. 0을 포함하는 구간으로 나누면 안 됩니다. 결과가 무한대로 벌어지기 때문입니다. Go 답게 error 로 돌려줍니다.

func DivInterval(x, y Interval) (Interval, error) {
	if y.Lo <= 0 && y.Hi >= 0 {
		return Interval{}, fmt.Errorf("0 을 포함하는 구간 %v 로는 나눌 수 없습니다", y)
	}
	return MulInterval(x, Interval{1 / y.Hi, 1 / y.Lo}), nil
}

직렬 합성: {10.585 12.415}
병렬 합성: {2.201031010873943 3.4873689182805854}
0 포함 구간 나누기: 0 을 포함하는 구간 {-1 1} 로는 나눌 수 없습니다

이 부분은 Go 가 원서보다 낫습니다. 원서는 에러 처리를 다루지 않습니다. 다룰 언어 장치가 없어서가 아니라, 책의 관심사가 아니기 때문입니다. Go 로 옮기면 “이 연산은 부분 함수다” 라는 사실이 시그니처에 강제로 드러납니다.

그리고 2.1.4 의 진짜 요점은 따로 있습니다. 연습문제 2.14~2.16 이 지적하는 것인데, 수학적으로 같은 식이 구간 산술에서는 다른 결과를 냅니다. R1·R2/(R1+R2) 와 1/(1/R1 + 1/R2) 는 같은 병렬 저항 공식인데 구간 폭이 다릅니다. 같은 불확실성을 여러 번 세기 때문입니다.

이건 추상화가 샐 수 있다 는 경고입니다. 구간을 “값처럼” 다루기로 했지만, 구간은 값처럼 행동하지 않습니다. 대수 법칙이 성립하지 않습니다. 2장 전체를 통틀어 이 경고가 가장 유용한 대목일 수 있습니다.

6. 2.2 — 폐포 성질#

Cons 로 만든 것에 다시 Cons 를 적용할 수 있습니다. 원서는 이 성질을 폐포 성질(closure property) 이라고 부릅니다. 수학에서 “닫혀 있다” 는 그 의미이고, 프로그래밍의 클로저(closure)와는 다른 개념입니다. 영어 단어가 같아서 혼동하기 쉽습니다.

이 성질 하나에서 계층 구조 전체가 나옵니다. 리스트는 Cons 의 오른쪽에 계속 Cons 를 넣은 것입니다.

func List(xs ...any) any {
	var r any = nil
	for i := len(xs) - 1; i >= 0; i-- {
		r = Cons(xs[i], r)
	}
	return r
}

Scheme 표기법으로 찍어 보면 원서와 똑같이 나옵니다.

l            = (1 2 3 4)
Car(l)       = 1
Cdr(l)       = (2 3 4)
Length(l)    = 4
ListRef(l,2) = 3
Append       = (1 2 3 4)
Reverse      = (4 3 2 1)
점 쌍         = (1 . 2)

마지막 줄이 중요합니다. Cons(1, 2) 는 리스트가 아닙니다. (1 . 2) 로 찍힙니다. 리스트는 “cdr 을 따라가면 결국 빈 리스트가 나오는 pair 사슬” 이라는 관습 이고, Cons 자체는 그런 걸 강요하지 않습니다.

그리고 Cons 의 왼쪽에도 Cons 를 넣을 수 있습니다. 그러면 트리가 됩니다.

t := List(List(1, 2), List(3, List(4, 5)))

t              = ((1 2) (3 (4 5)))
Length(t)      = 2
CountLeaves(t) = 5

Length 는 2인데 CountLeaves 는 5입니다. 최상위 원소는 두 개지만 잎은 다섯 개입니다. 같은 자료를 리스트로 보느냐 트리로 보느냐에 따라 답이 달라집니다.

CountLeaves 는 Go 의 타입 스위치와 잘 맞습니다.

func CountLeaves(t any) int {
	switch v := t.(type) {
	case nil:
		return 0
	case *Pair:
		return CountLeaves(v.Car) + CountLeaves(v.Cdr)
	default:
		return 1 // 잎
	}
}

원서의 (cond ((null? x) 0) ((not (pair? x)) 1) (else ...)) 와 한 줄씩 대응합니다. 타입 스위치가 Scheme 의 술어 분기를 거의 그대로 표현합니다. 이 대응은 4장에서 평가기를 만들 때 아주 유용해집니다.

7. 그런데 왜 슬라이스를 안 쓰나#

Go 프로그래머라면 여기서 당연한 질문이 나옵니다. []any 를 쓰면 되지 않나.

성능만 보면 슬라이스가 압승입니다. Cons 리스트는 원소마다 포인터 하나씩 따라가야 하고, 캐시 지역성이 나쁘고, Length 가 O(n) 입니다. 슬라이스는 연속 메모리에 len 을 들고 다닙니다.

그런데 두 가지가 다릅니다.

첫째, Cons 리스트는 꼬리를 공유합니다. Cons(0, l) 은 l 을 복사하지 않습니다. 새 pair 하나만 만들고 나머지는 그대로 가리킵니다. 그래서 l 에서 파생된 리스트가 100개여도 메모리는 100개의 pair 만큼만 늘어납니다. 슬라이스에 앞쪽 삽입을 하려면 전체를 옮겨야 합니다. 불변 자료구조에서 이 차이가 결정적입니다.

둘째, Cons 는 트리를 자연스럽게 표현합니다. []any 안에 []any 를 넣어도 되지만, 그건 “리스트의 원소가 리스트일 수도 있다” 는 별도 규칙입니다. Cons 는 car 자리와 cdr 자리가 처음부터 대칭이라 트리가 특수 사례가 아닙니다.

그리고 2장의 목적을 생각하면 답이 분명해집니다. 원서가 보여 주려는 것은 “세 개의 연산에서 모든 계층 구조가 나온다” 는 것 이지 자료구조의 성능이 아닙니다.

실무 지침으로 정리하면 이렇습니다. Go 에서 순서 있는 값 묶음이 필요하면 슬라이스를 씁니다. Cons 리스트를 손으로 만드는 것은 (1) 꼬리 공유가 중요한 영속 자료구조, (2) 인터프리터의 구문 트리처럼 이종·재귀 구조를 다룰 때입니다. 4장에서 두 번째 경우를 실제로 만납니다.

8. 타입을 포기하는 경계선#

4절에서 Pair 를 any 로 만들기로 했습니다. 그런데 Go 제네릭이 되는 자리도 있습니다. 원소 타입이 전부 같으면 됩니다.

type GList[A any] struct {
	Car A
	Cdr *GList[A]
}

func GMap[A, B any](f func(A) B, l *GList[A]) *GList[B] {
	if l == nil { return nil }
	return GCons(f(l.Car), GMap(f, l.Cdr))
}

타입: *main.GList[int]
길이: 3   슬라이스: [1 2 3]
제곱: [1 4 9]
문자열로: [<1> <2> <3>]

재귀적 제네릭 타입이 잘 동작합니다. GMap 이 *GList[int] 를 받아 *GList[string] 을 돌려주는 것까지 타입으로 검사됩니다.

그럼 이종 리스트는? 타입을 붙여 볼 수는 있습니다.

l := GCons(1, GCons(2, GCons(3, Nil{})))

타입: main.GPair[int,main.GPair[int,main.GPair[int,main.Nil]]]
값:   {1 {2 {3 {}}}}

타입이 리스트 길이에 따라 달라집니다. 원소 3개면 3중 중첩, 4개면 4중 중첩입니다. 그러면 Length 를 쓸 수 없습니다. 인자 타입이 길이마다 다르니 함수 하나로 받을 방법이 없습니다.

경계선이 여기서 그어집니다.

상황Go 에서
원소 타입이 전부 같은 리스트제네릭으로 됨. GList[A] 로 타입 안전
원소 타입이 섞인 리스트타입은 붙지만 길이마다 달라져서 쓸 수 없음
프로시저 표현 pair (car/cdr 둘 다)불가. rank-2 다형성 필요
트리 (car 자리에도 pair)any 필요

SICP 2장이 다루는 것은 대부분 아래 세 줄입니다. 기호식, 이종 트리, 여러 표현이 섞인 산술 시스템. 그래서 any 로 갑니다. 타입 안전성을 잃는 대신, 4장에서 그 대가를 어떻게 치르는지(런타임 타입 검사와 panic)를 정직하게 보게 됩니다.

이건 Go 만의 사정이 아닙니다. 동적 타입 언어를 전제로 쓰인 책을 정적 타입 언어로 옮기면 반드시 나오는 청구서 입니다. 공식 JavaScript 판이 이 문제를 겪지 않은 이유는 JavaScript 가 동적 타입이라서입니다.

9. 이번 편의 정리#

SICP 2.1~2.2 의 주장Go 에서
생성자와 선택자로 추상화 장벽을 세운다성립. 패키지 + 대소문자로 강제 까지 됨
표현을 바꿔도 위층은 안 바뀐다성립
데이터는 계약이지 저장 구조가 아니다성립. 클로저 pair 그대로 동작
프로시저 표현을 타입 있게 쓰기불가. rank-2 다형성 없음
폐포 성질에서 계층 구조가 나온다성립. any 를 쓰면
술어로 자료의 종류를 분기한다성립. 타입 스위치가 거의 그대로 대응

다음 편은 2.2.3 과 2.3 입니다. 관례적 인터페이스 — map, filter, accumulate 로 프로그램을 신호 처리 파이프라인처럼 조립하는 이야기입니다. 여기서 Go 1.23 의 iter.Seq 가 등장할 자리가 나옵니다. 그리고 기호 데이터 로 넘어가서 기호식 미분과 Huffman 부호화 트리를 만듭니다. 기호 데이터는 Go 에 quote 가 없다는 마찰이 처음으로 아프게 느껴지는 대목입니다.

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.
  • 프로시저만으로 만든 pair 는 2.1.3 절 본문과 연습문제 2.4 에 나옵니다. 본문의 Go 판은 연습문제 2.4 쪽 정의를 옮긴 것입니다.
  • 구간 산술의 대수 법칙 위반은 연습문제 2.14~2.16 (Eva Lu Ator 와 Alyssa P. Hacker 의 논쟁)에서 다룹니다.

본문의 실측 데이터

  • 모든 출력값과 컴파일 에러 메시지는 go version go1.26.0 darwin/arm64 에서 직접 실행·컴파일해 얻은 것입니다.
  • 4절의 에러 메시지는 go vet 이 출력한 원문을 줄바꿈만 넣어 그대로 옮겼습니다.

시리즈