Go 로 읽는 SICP Part 8: 같은 pair 세 개를 세는 네 가지 답, 그리고 이벤트 루프

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

Part 7에서 대입을 도입했습니다. 프로시저 가 상태를 가질 수 있게 되었습니다.

3.3 은 같은 일을 데이터 에 합니다. pair 의 car 와 cdr 를 나중에 바꿀 수 있게 하는 것입니다. Scheme 에서는 set-car! 와 set-cdr! 라는 새 연산이 필요하지만, Go 에서는 이미 되어 있습니다. Part 4 에서 Pair 를 구조체로 만들었으니 필드에 그냥 대입하면 됩니다.

type Pair struct{ Car, Cdr any }

p.Car = something // 이게 set-car!

기능이 공짜로 생겼다고 좋은 게 아닙니다. 공짜로 생긴 만큼 대가도 조용히 따라옵니다. 이번 편의 전반부가 그 대가에 관한 것입니다.

1. 3.3.1 — 공유는 눈에 안 보입니다#

원서의 첫 예제가 정확합니다. 리스트 (a b) 를 만들고, 그걸 두 번 가리키는 pair 와, 똑같이 생긴 리스트 두 개를 각각 가리키는 pair 를 만듭니다.

x := List(Symbol("a"), Symbol("b")).(*Pair)
z1 := Cons(x, x)  // 같은 리스트를 두 번 가리킨다
z2 := Cons(List(Symbol("a"), Symbol("b")), List(Symbol("a"), Symbol("b")))

z1 = ((a b) a b)
z2 = ((a b) a b) <- 찍어 보면 똑같다

출력이 구별되지 않습니다. 이제 x 의 첫 원소만 고쳐 봅니다.

x.Car = Symbol("wow")

z1 = ((wow b) wow b) <- 두 곳이 다 바뀐다
z2 = ((a b) a b)     <- 아무 일도 없다

같아 보이던 두 값이 건드리는 순간 갈립니다. Part 7 의 peter 와 mary 와 같은 이야기이고, 이번에는 자료구조 안쪽에서 벌어집니다.

원서는 이 현상을 공유(sharing) 라고 부르고, 두 얼굴을 함께 짚습니다. 공유는 자원 절약 이자 위험 입니다. 어느 쪽인지는 그 구조를 고치느냐에 달렸습니다. 고치지 않으면 순수한 이득이고, 고치면 원격 작용이 됩니다.

2. 연습문제 3.16 — pair 세 개를 세는 네 가지 답#

원서에서 가장 유명한 연습문제 중 하나입니다.

Ben Bitdiddle 이 자료구조 안의 pair 개수를 세는 함수를 짰습니다. 자연스러워 보입니다.

func countPairsNaive(x any) int {
	if !IsPair(x) { return 0 }
	return countPairsNaive(Car(x)) + countPairsNaive(Cdr(x)) + 1
}

원서는 묻습니다. 정확히 세 개의 pair 로 이루어진 구조를 만들어서, 이 함수가 3, 4, 7 을 각각 돌려주게 하고, 아예 안 끝나게도 만들어 보시오.

네 개를 만들어 봤습니다. 모두 Cons 를 정확히 세 번만 부릅니다.

flowchart TD
    subgraph S4["구조 4 — 순환 → 끝나지 않음"]
        A4["p1"] --> B4["p2"] --> C4["p3"] -->|"cdr"| A4
    end
    subgraph S3["구조 3 — 두 곳 공유 → 7"]
        A3["p1"] -->|"car·cdr"| B3["p2"]
        B3 -->|"car·cdr"| C3["p3"]
    end
    subgraph S2["구조 2 — 한 곳 공유 → 4"]
        A2["p1"] --> B2["p2"]
        B2 -->|"car"| C2["p3"]
        B2 -->|"cdr"| C2
    end
    subgraph S1["구조 1 — 공유 없음 → 3"]
        A1["p1"] --> B1["p2"] --> C1["p3"]
    end
    style C2 fill:#FFD700,color:#000000
    style B3 fill:#FFD700,color:#000000
    style C3 fill:#FF9999,color:#000000
    style C4 fill:#FF9999,color:#000000

돌려 봤습니다.

 구조 1: 순진한 세기 = 3, 올바른 세기 = 3, 순환 = false
 구조 2: 순진한 세기 = 4, 올바른 세기 = 3, 순환 = false
 구조 3: 순진한 세기 = 7, 올바른 세기 = 3, 순환 = false
 구조 4: 순진한 세기 = (무한 루프라 생략), 올바른 세기 = 3, 순환 = true

3, 4, 7, 무한대. 메모리를 차지하는 pair 는 언제나 세 개인데 답이 넷입니다.

원인은 하나입니다. countPairsNaive 는 같은 pair 를 몇 번 지나가는지 를 세고 있습니다. 몇 개인지 를 세는 게 아닙니다. 공유가 없으면 두 값이 우연히 일치할 뿐입니다.

고치려면 지나간 pair 를 기억해야 합니다(연습문제 3.17).

func countPairsCorrect(x any) int {
	seen := map[*Pair]bool{}
	var walk func(any)
	walk = func(x any) {
		p, ok := x.(*Pair)
		if !ok || seen[p] { return }
		seen[p] = true
		walk(p.Car)
		walk(p.Cdr)
	}
	walk(x)
	return len(seen)
}

Go 에서는 map[*Pair]bool 로 간단합니다. 포인터가 곧 동일성 이기 때문입니다. Scheme 에서는 eq? 로 같은 일을 하고, Part 7 에서 본 “동일성 대 동등성” 구분이 여기서 실제 도구로 쓰입니다.

순환은 상수 공간으로도 잡을 수 있습니다#

연습문제 3.19 가 더 어려운 것을 요구합니다. 상수 공간으로 순환을 검출하시오. 방문 집합은 O(n) 메모리를 씁니다.

답은 플로이드의 토끼와 거북이입니다.

func hasCycle(l any) bool {
	slow, fast := l, l
	for {
		if !IsPair(fast) { return false }
		fast = Cdr(fast)
		if !IsPair(fast) { return false }
		fast = Cdr(fast)
		slow = Cdr(slow)
		if fast == slow { return true }
	}
}

한 칸씩 가는 것과 두 칸씩 가는 것이 만나면 순환입니다. 변수 두 개면 됩니다.

이 연습문제가 1985년 입문 교재 에 들어 있습니다. 지금은 코딩 면접 단골 문제입니다.

3. Go 에서 같은 함정은 어디에 있는가#

“Go 에서는 Cons 를 안 쓰니 상관없다” 고 생각하기 쉽습니다. 그렇지 않습니다. 슬라이스가 정확히 같은 성질을 가집니다.

base := make([]int, 3, 8) // 길이 3, 용량 8
copy(base, []int{1, 2, 3})

a := append(base, 100)
b := append(base, 200)

a 와 b 는 서로 다른 슬라이스처럼 보입니다. 그런데 결과가 이렇습니다.

base = [1 2 3]  len/cap = 3 8
a    = [1 2 3 200]
b    = [1 2 3 200]
a[3] 이 100 인가: false   <- b 의 append 가 a 를 덮어썼다
a 와 b 가 같은 배열을 보는가: true

a 에 100 을 넣었는데 200 이 들어 있습니다. base 의 용량이 남아 있어서 두 append 가 같은 배열의 같은 칸에 썼기 때문입니다.

용량이 딱 맞으면 이 일이 안 일어납니다.

용량이 딱 맞을 때: c = [1 2 3 100]  d = [1 2 3 200]  같은 배열: false

append 가 새 배열을 할당하면서 공유가 끊겼습니다.

같은 코드가 용량에 따라 다르게 동작합니다. SICP 연습문제 3.16 이 “같은 세 개의 pair 인데 답이 넷” 이라고 한 것과 정확히 같은 구조입니다. 자료구조를 그림으로 그려 보지 않으면 안 보이고, 값만 찍어 봐서는 구별이 안 됩니다.

대응도 같습니다. 공유를 끊고 싶으면 명시적으로 복사합니다. Go 1.21 이후에는 slices.Clone 이 있고, 그전에는 append([]int(nil), base...) 였습니다. s[:n:n] 으로 용량을 잘라 두면 이후 append 가 반드시 새 배열을 만들게 강제할 수도 있습니다.

4. 3.3.2 — 큐, 그리고 왜 포인터가 두 개인가#

set-cdr! 가 있으면 큐를 O(1) 로 만들 수 있습니다. 앞과 뒤를 각각 가리키는 포인터를 두는 것입니다.

type Queue struct{ front, rear *Pair }

func (q *Queue) Insert(item any) {
	p := Cons(item, nil)
	if q.Empty() {
		q.front, q.rear = p, p
		return
	}
	q.rear.Cdr = p // set-cdr! — 여기가 핵심
	q.rear = p
}

 insert a -> (a)
 insert b -> (a b)
 delete   -> a 남은 큐: (b)
 insert c -> (b c)
 delete   -> b 남은 큐: (c)
 delete   -> c 남은 큐: ()  비었나: true

원서가 이 예제를 넣은 이유는 큐가 필요해서가 아닙니다. 가변성 없이는 이걸 O(1) 로 못 만든다 는 것을 보여 주기 위해서입니다. 불변 리스트에 뒤쪽 삽입을 하려면 전체를 다시 만들어야 하므로 O(n) 입니다.

Go 에서 큐가 필요하면 슬라이스를 씁니다. append 로 넣고 q = q[1:] 로 뺍니다. 이게 캐시 지역성 면에서 훨씬 낫습니다. 다만 q[1:] 는 앞쪽 메모리를 붙잡고 있어서 장기 실행 큐에서는 누수처럼 보일 수 있고, 그래서 표준 라이브러리의 container/list 나 링 버퍼를 쓰기도 합니다. 3장에서 손으로 만든 것이 어떤 절충 위에 있었는지 알고 나면 선택이 쉬워집니다.

5. 3.3.3 — 테이블, 그리고 Go 의 map#

원서는 테이블을 연관 리스트 로 만듭니다. ((key . value) (key . value) ...) 형태이고, 조회는 앞에서부터 훑습니다. O(n) 입니다.

Go 에는 map 이 있으니 이 절이 필요 없어 보입니다. 그런데 원서가 이 절에서 실제로 가르치는 것은 자료구조가 아니라 2차원 테이블을 1차원 테이블의 테이블로 만드는 법 입니다. 그리고 그것이 Part 6 의 applyGeneric 이 쓰던 그 표입니다.

Go 로는 이렇게 씁니다.

type key struct{ op, typ string }
var table = map[key]func(Tagged) float64{}

Go 는 구조체를 map 키로 쓸 수 있습니다. 비교 가능한 필드로만 이루어져 있으면 됩니다. 그래서 원서가 두 단계로 만든 2차원 테이블이 Go 에서는 한 줄입니다.

여기서 짚어 둘 실무 지식이 하나 있습니다. Go map 은 순회 순서가 무작위 입니다. 의도적으로 그렇게 만들었습니다. 순서에 의존하는 코드가 생기는 것을 막기 위해서입니다. 원서의 연관 리스트는 삽입 순서를 유지하므로, 원서 코드를 Go map 으로 옮길 때 순서에 의존하던 동작이 조용히 깨질 수 있습니다. Part 6 의 디스패치 테이블은 순서와 무관해서 문제가 없었습니다.

6. 3.3.4 — 디지털 회로 시뮬레이터#

3장에서 가장 재미있는 예제입니다. AND 게이트, OR 게이트, 인버터를 부품으로 놓고, 배선해서 반가산기와 전가산기를 만듭니다. 그리고 전파 지연을 시뮬레이션합니다.

핵심 부품은 셋입니다.

전선(Wire). 신호값을 들고 있고, 값이 바뀌면 등록된 동작들을 부릅니다.

func (w *Wire) SetSignal(v int) {
	if w.signal != v {       // 값이 실제로 바뀔 때만
		w.signal = v
		for _, f := range w.actions { f() }
	}
}

게이트. 입력 전선에 동작을 등록합니다. 입력이 바뀌면 출력값을 계산해서 지연 후에 반영하도록 예약합니다.

func AndGate(a1, a2, out *Wire, ag *Agenda) {
	f := func() {
		v := logicalAnd(a1.Signal(), a2.Signal())
		ag.AfterDelay(andGateDelay, func() { out.SetSignal(v) })
	}
	a1.AddAction(f)
	a2.AddAction(f)
}

아젠다(Agenda). 시각별로 대기 중인 동작을 담고, 가장 이른 것부터 실행합니다.

func (a *Agenda) Propagate() {
	for !a.Empty() {
		t := 가장 이른 시각
		a.time = t
		actions := a.slots[t]
		delete(a.slots, t)
		for _, act := range actions { act() }  // 여기서 새 동작이 추가될 수 있다
	}
}

이게 이벤트 루프입니다. 시각순 우선순위 큐를 돌면서 콜백을 실행하고, 실행 중에 미래 시각의 콜백이 추가됩니다. 1985년 교재에 이벤트 루프가 통째로 들어 있습니다.

배선은 원서 그대로입니다.

func HalfAdder(a, b, s, c *Wire, ag *Agenda) {
	d, e := NewWire(ag), NewWire(ag)
	OrGate(a, b, d, ag)
	AndGate(a, b, c, ag)
	Inverter(c, e, ag)
	AndGate(d, e, s, ag)
}

func FullAdder(a, b, cIn, sum, cOut *Wire, ag *Agenda) {
	s, c1, c2 := NewWire(ag), NewWire(ag), NewWire(ag)
	HalfAdder(b, cIn, s, c1, ag)
	HalfAdder(a, s, sum, c2, ag)
	OrGate(c1, c2, cOut, ag)
}

지연은 원서와 같은 값(인버터 2, AND 3, OR 5)을 썼습니다. 그리고 원서 본문의 시뮬레이션을 그대로 돌렸습니다.

  sum    시각  0  새 값 = 0
  carry  시각  0  새 값 = 0
input-1 을 1 로:
  sum    시각  8  새 값 = 1
input-2 를 1 로:
  carry  시각 11  새 값 = 1
  sum    시각 16  새 값 = 0

원서 본문은 이렇게 적고 있습니다. “sum 8 New-value = 1”, 그리고 “carry 11 New-value = 1 / sum 16 New-value = 0”. 시각까지 정확히 일치합니다.

전가산기는 진리표 여덟 줄을 전부 돌렸습니다.

 a b cin | sum cout   (기대값)
 0 0  0  |  0   0      (0 0) OK   안정화 시각=5
 0 0  1  |  1   0      (1 0) OK   안정화 시각=21
 0 1  0  |  1   0      (1 0) OK   안정화 시각=21
 0 1  1  |  0   1      (0 1) OK   안정화 시각=21
 1 0  0  |  1   0      (1 0) OK   안정화 시각=13
 1 0  1  |  0   1      (0 1) OK   안정화 시각=21
 1 1  0  |  0   1      (0 1) OK   안정화 시각=21
 1 1  1  |  1   1      (1 1) OK   안정화 시각=21
전가산기 진리표 8/8 통과: true

8/8 통과. 그리고 안정화 시각이 입력에 따라 다릅니다. 5부터 21까지. 이게 실제 회로에서 클럭 주기를 정하는 근거인 임계 경로(critical path) 입니다. 최악의 경우가 21 이니 그보다 짧은 클럭을 쓰면 잘못된 값을 읽습니다.

교재의 장난감 예제가 실제 하드웨어 설계의 핵심 개념을 그대로 담고 있습니다.

그리고 이 예제가 진짜로 말하는 것#

원서는 3.3.4 를 3.4(동시성) 바로 앞에 놓습니다. 우연이 아닙니다.

이 시뮬레이터에는 시간이 데이터로 들어 있습니다. agenda.time 이라는 변수가 있고, 그 값이 순서를 정합니다. 실제 회로에서는 게이트들이 진짜로 동시에 동작하지만, 시뮬레이터는 그걸 하나의 순서로 직렬화 해서 흉내 냅니다.

이게 3.4 의 질문으로 이어집니다. 진짜로 동시에 일어나는 일에는 그런 순서가 없습니다. 그러면 무슨 일이 벌어지는가.

Go 프로그래머에게 익숙한 대응물이 있습니다. time.AfterFunc 와 런타임 타이머가 같은 구조이고, Go 1.24 에 실험 도입되어 1.25 에서 정식화된 testing/synctest 는 가짜 시계 위에서 고루틴을 돌려 시간 의존 테스트를 결정적으로 만듭니다. 3.3.4 의 아젠다가 하는 일과 발상이 같습니다.

7. 이번 편의 정리#

SICP 3.3 의 주장	Go 에서
`set-car!`/`set-cdr!` 로 pair 를 고친다	이미 됨. 구조체 필드 대입
공유는 출력으로 구별되지 않는다	그대로 성립
순진한 pair 세기는 3·4·7·∞ 를 낸다	그대로 재현됨
동일성 판정이 필요하다	`map[*Pair]bool`. 포인터가 곧 동일성
상수 공간 순환 검출	성립. 플로이드 알고리즘
가변성이 있어야 O(1) 큐가 된다	성립. 다만 Go 는 슬라이스가 낫다
2차원 테이블은 테이블의 테이블	Go 는 구조체 키 map 으로 한 줄
아젠다 기반 회로 시뮬레이션	성립. 원서와 같은 시각 재현

다음 편은 3장의 마지막인 3.4 동시성 과 3.5 스트림 입니다.

3.4 는 이 시리즈에서 Go 가 원서를 넘어서는 대목입니다. 원서는 1996년 Scheme 으로 동시성을 다루느라 사고 실험에 머무는데, Go 에서는 고루틴으로 실제로 돌리고 go test -race 로 경쟁 조건을 잡아낼 수 있습니다.

3.5 는 반대입니다. Go 의 채널과 iter.Seq 가 SICP 스트림처럼 보이지만 결정적으로 다릅니다. 그 차이를 모르고 옮기면 조용히 틀린 프로그램이 됩니다. 다음 편의 핵심이 그것입니다.

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.
- 3.3 절 (가변 데이터·큐·테이블·회로 시뮬레이터) — https://sarabander.github.io/sicp/html/3_002e3.xhtml
연습문제 3.16 (순진한 pair 세기), 3.17 (올바른 세기), 3.19 (상수 공간 순환 검출)는 3.3.1 절에 있습니다.
게이트 지연값(인버터 2, AND 3, OR 5)과 시뮬레이션 결과(“sum 8”, “carry 11”, “sum 16”)는 원서 3.3.4 절 본문의 값 이며, 본문의 Go 판이 같은 값을 냈습니다.

본문의 실측 데이터

모든 출력값은 go version go1.26.0 darwin/arm64 에서 직접 실행한 결과입니다.
전가산기 진리표는 여덟 가지 입력 조합 전부를 시뮬레이터로 돌려 확인했습니다.
3절의 슬라이스 공유 실험은 make([]int, 3, 8) 로 용량을 남긴 경우와 리터럴로 용량이 딱 맞는 경우를 나란히 실행한 것입니다.

시리즈