Go 로 읽는 SICP Part 9: 채널은 SICP 스트림이 아니다

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

Part 8에서 3.3 까지 왔습니다. 이번 편은 3장의 마지막 두 절인 3.4 동시성 과 3.5 스트림 입니다.

두 절의 성격이 정반대입니다.

3.4 는 Go 가 원서를 넘어서는 대목입니다. 원서는 1996년 Scheme 으로 동시성을 다뤄야 했고, 표준 Scheme 에는 스레드가 없습니다. 그래서 대부분 그림과 사고 실험으로 설명합니다. Go 에서는 실제로 돌리고 실제로 깨뜨릴 수 있습니다.

3.5 는 반대입니다. Go 에는 채널과 iter.Seq 가 있고, 둘 다 SICP 스트림처럼 보입니다. 그런데 아닙니다. 이 차이를 모르고 옮기면 조용히 틀린 프로그램이 됩니다. 이번 편의 제목이 그 이야기입니다.

1. 3.4.1 — 동시성에서 “시간” 이란#

원서의 설정은 은행 계좌입니다. 잔액이 100원이고, 두 사람이 동시에 인출합니다.

문제는 인출이 원자적이지 않다는 것입니다. 세 단계로 이루어집니다.

func (a *UnsafeAccount) Withdraw(n int) {
	b := a.Balance // (1) 읽고
	b = b - n      // (2) 계산하고
	a.Balance = b  // (3) 쓴다
}

(1)과 (3) 사이에 다른 인출이 끼어들면, 그 인출은 낡은 잔액을 보고 계산합니다. 그리고 나중에 쓰는 쪽이 앞의 결과를 지웁니다.

원서는 이 상황을 그림으로 설명하는데, Go 에서는 그냥 돌려 볼 수 있습니다. 1000원짜리 계좌에서 1000개의 고루틴이 1원씩 뺐습니다.

시행 1: 1000원에서 1원씩 1000번 인출 -> 잔액  878 (사라진 인출 878건)
시행 2: 1000원에서 1원씩 1000번 인출 -> 잔액  987 (사라진 인출 987건)
시행 3: 1000원에서 1원씩 1000번 인출 -> 잔액  986 (사라진 인출 986건)
시행 4: 1000원에서 1원씩 1000번 인출 -> 잔액  966 (사라진 인출 966건)
시행 5: 1000원에서 1원씩 1000번 인출 -> 잔액  984 (사라진 인출 984건)

1000번 인출했는데 20~120번만 반영되었습니다. 그리고 매번 다른 값이 나옵니다.

솔직하게 밝혀 둘 것이 있습니다. 위 결과는 읽기와 쓰기 사이에 runtime.Gosched() 를 하나 넣어 틈을 벌린 것입니다. 그 한 줄이 없으면 인출이 너무 짧아서 대부분의 실행에서 잔액이 그냥 0 으로 맞게 나옵니다.

이게 경쟁 조건의 가장 고약한 성질입니다. 버그가 있어도 대부분의 실행에서 안 보입니다. 테스트를 통과하고, 스테이징을 통과하고, 프로덕션의 어느 바쁜 날에 처음 나타납니다.

그래서 -race 가 있습니다#

Go 에는 이걸 위한 도구가 있습니다. 틈을 벌리지 않은 원래 코드, 즉 잔액이 정상으로 나오던 그 코드에 -race 를 걸었습니다.

==================
WARNING: DATA RACE
Read at 0x00c000012328 by goroutine 10:
  sicp/p09race.(*UnsafeAccount).Withdraw()
      .../account.go:9 +0x6c

Previous write at 0x00c000012328 by goroutine 8:
  sicp/p09race.(*UnsafeAccount).Withdraw()
      .../account.go:11 +0x7c

결과가 맞게 나온 실행에서도 경쟁을 잡아냅니다. 9번 줄(읽기)과 11번 줄(쓰기)을 정확히 지목했습니다.

레이스 디텍터는 “이번에 값이 틀렸는가” 를 보지 않습니다. “두 고루틴이 동기화 없이 같은 주소를 건드렸는가” 를 봅니다. 그래서 증상이 안 나타난 실행에서도 원인을 찾아냅니다.

원서 3.4.1 이 열 쪽에 걸쳐 그림으로 설명하는 것을, Go 에서는 플래그 하나로 재현하고 진단할 수 있습니다. 원서가 쓰인 시점에 없던 도구입니다.

2. 3.4.2 — 직렬화기는 뮤텍스입니다#

원서의 처방은 직렬화기(serializer) 입니다. 어떤 프로시저들을 묶어 두고, 그중 하나가 실행 중이면 다른 것은 기다리게 합니다.

Go 에서는 sync.Mutex 입니다.

type SafeAccount struct {
	mu      sync.Mutex
	Balance int
}

func (a *SafeAccount) Withdraw(n int) {
	a.mu.Lock()
	defer a.mu.Unlock()
	a.Balance -= n
}

100번 인출하면 정확히 0 이 됩니다. 몇 번을 돌려도 0 입니다.

그리고 원서는 바로 교착 상태를 꺼냅니다#

3.4.2 의 마지막이 이 시리즈에서 가장 실무적인 대목일 수 있습니다. 원서는 직렬화기를 준 다음, 직렬화기만으로는 부족한 경우 를 보여 줍니다.

두 계좌의 잔액을 맞바꾸려면 자물쇠 두 개가 필요합니다. 그런데 두 요청이 반대 방향으로 오면 이렇게 됩니다.

func exchangeNaive(a, b *Acct, hold time.Duration) {
	a.mu.Lock()
	time.Sleep(hold) // 상대가 반대편을 잡을 시간을 준다
	b.mu.Lock()
	// ...
}

한쪽은 exchange(a1, a2), 다른 쪽은 exchange(a2, a1). 각자 첫 자물쇠를 잡고 상대의 두 번째 자물쇠를 기다립니다. 영원히.

순진한 판        2초 안에 끝나지 않음 -> 교착 상태
번호순 잠금       완료. 잔액 a1=100 a2=200

원서의 처방은 계좌에 번호를 매기고 항상 작은 번호부터 잠그는 것입니다.

func exchangeOrdered(a, b *Acct, hold time.Duration) {
	first, second := a, b
	if first.id > second.id {
		first, second = second, first
	}
	first.mu.Lock()
	// ...
}

이러면 두 요청이 같은 순서로 잠그므로 순환 대기가 생기지 않습니다. 순환 대기는 교착 상태의 네 가지 필요조건 중 하나이고, 그 하나를 없애면 교착이 불가능해집니다.

이 처방이 1985년 교재에 있습니다. 지금 어느 동시성 강의를 들어도 나오는 “자물쇠 순서를 전역으로 통일하라” 가 여기 있습니다.

Go 진영에는 이 문제에 대한 다른 접근이 하나 더 있습니다. “메모리를 공유해서 통신하지 말고, 통신해서 메모리를 공유하라.” 계좌를 고루틴 하나가 소유하고 다른 고루틴은 채널로 요청만 보내면, 자물쇠가 아예 없으니 교착도 없습니다. 원서의 직렬화기와 다른 방향의 답이고, 원서에는 없는 선택지입니다.

3. 3.5 — 스트림이 필요한 이유#

이제 방향이 바뀝니다.

Part 5 에서 map/filter/accumulate 파이프라인을 만들면서 약점 하나를 지적했습니다. 단계마다 리스트를 통째로 만듭니다. 100만 개를 걸러 변환하면 100만 개짜리 리스트가 두 번 더 생깁니다.

그리고 무한 수열은 아예 표현할 수 없습니다. “1부터 시작하는 모든 정수” 를 리스트로 만들면 프로그램이 끝나지 않습니다.

3.5 의 답이 스트림 입니다. 한 줄로 요약하면 이렇습니다.

스트림은 머리는 이미 계산된 값이고 꼬리는 아직 계산하지 않은 약속 인 pair 다.

flowchart LR
    S["스트림 s"] -->|"car"| H["1<br/>이미 계산됨"]
    S -->|"cdr"| T["thunk<br/>아직 계산 안 됨"]
    T -->|"force 하면"| S2["다음 스트림"]
    S2 -->|"결과를 저장"| M["memo<br/>다음부터는 재계산 없음"]

    style H fill:#90EE90,color:#000000
    style T fill:#FFD700,color:#000000
    style M fill:#87CEEB,color:#000000

Go 로 옮기면 이렇습니다.

type Stream struct {
	head any
	tail func() *Stream // 지연된 나머지
	memo *Stream        // force 한 결과
	done bool
}

func (s *Stream) Cdr() *Stream {
	if !s.done {
		s.memo = s.tail() // 여기서 처음 계산한다
		s.done = true
		s.tail = nil
	}
	return s.memo // 두 번째부터는 저장된 것을 준다
}

done 과 memo 가 핵심입니다. 원서에서 memo-proc 이라고 부르는 것이고, 스트림을 스트림답게 만드는 유일한 장치입니다. 이게 없으면 그냥 게으른 계산이고, 있으면 재사용 가능한 무한 자료구조 가 됩니다.

무한 정수와 소수의 체를 만들어 봤습니다.

func IntegersFrom(n int) *Stream {
	return ConsStream(n, func() *Stream { return IntegersFrom(n + 1) })
}

func Sieve(s *Stream) *Stream {
	p := s.Car().(int)
	return ConsStream(p, func() *Stream {
		return Sieve(FilterStream(func(x any) bool { return x.(int)%p != 0 }, s.Cdr()))
	})
}

앞 10개: [1 2 3 4 5 6 7 8 9 10]
앞 20개 소수: [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71]
앞 15개 피보나치: [0 1 1 2 3 5 8 13 21 34 55 89 144 233 377]

에라토스테네스의 체가 일곱 줄 입니다. 배열도 없고 상한도 없습니다. “2를 뺀 나머지에서 2의 배수를 거른 것을 다시 체질한다” 를 그대로 적었습니다.

피보나치는 더 이상합니다. 원서 3.5.2 의 암묵적 정의 인데, 스트림이 자기 자신을 참조합니다.

func Fibs() *Stream {
	var a, b *Stream
	a = ConsStream(0, func() *Stream { return b })
	b = ConsStream(1, func() *Stream { return AddStreams(a.Cdr(), a) })
	return a
}

a 의 정의에 b 가 나오고 b 의 정의에 a 가 나옵니다. 보통은 무한 루프인데, 지연 평가라서 성립합니다. 필요한 순간에만 한 칸씩 풀립니다.

4. 메모이제이션이 있는지 확인하기#

memo 가 정말로 일하는지 세어 봤습니다. tail() 을 실제로 호출한 횟수를 셉니다.

첫 순회에서 계산한 tail: 1000개
두 번째 순회에서 계산한 tail: 0개  <- 메모이제이션

같은 스트림을 두 번 훑었는데 두 번째는 아무것도 계산하지 않았습니다.

그리고 같은 소수 스트림을 두 번 읽어도 같은 값이 나옵니다.

첫 번째 읽기: [2 3 5 7 11 13 17 19]
두 번째 읽기: [2 3 5 7 11 13 17 19] <- 같은 값

당연해 보이는 이 두 성질이, 다음 절에서 채널과 갈라지는 지점입니다.

5. 채널은 SICP 스트림이 아닙니다#

Go 프로그래머가 “무한 수열” 을 들으면 채널이 먼저 떠오릅니다. 생성기 고루틴을 하나 띄우고 값을 흘려보내면 됩니다.

func integersChan(done <-chan struct{}) <-chan int {
	ch := make(chan int)
	go func() {
		defer close(ch)
		for i := 1; ; i++ {
			select {
			case ch <- i:
			case <-done:
				return
			}
		}
	}()
	return ch
}

무한하고, 게으르고, 필요할 때만 값을 만듭니다. 스트림처럼 보입니다. 그런데 두 가지를 해 보면 다릅니다.

같은 것을 두 번 읽어 봅니다.

첫 번째 읽기: [1 2 3 4 5]
두 번째 읽기: [6 7 8 9 10] <- 이어서 나온다. 처음부터가 아니다

소비자를 둘 붙여 봅니다.

소비자 A: [6 7 8 9 10]
소비자 B: [1 2 3 4 5]

다시 돌리면 이렇게 나옵니다.

소비자 A: [4 5 6 7 8]   소비자 B: [1 2 3 9 10]
소비자 A: [2 3 4 5 6]   소비자 B: [1 7 8 9 10]

값이 나뉘어 가고, 어떻게 나뉠지는 실행마다 다릅니다. 둘 다 1..5 를 보는 일은 없습니다.

이유는 근본적입니다. 채널은 자료구조가 아니라 전달 통로입니다. 값을 하나 꺼내면 그 값은 채널에서 사라집니다. SICP 스트림은 자료구조 입니다. 리스트를 읽는다고 리스트가 줄어들지 않는 것과 같습니다.

iter.Seq 를 두 번 돌려 봤습니다.

첫 번째: [1 2 3 4 5]  생산 횟수: 5
두 번째: [1 2 3 4 5]  추가 생산 횟수: 5 <- 처음부터 다시 만든다

값은 같은데 다시 계산합니다. iter.Seq 는 값의 모음이 아니라 값을 만드는 절차 이기 때문입니다. 돌릴 때마다 절차가 처음부터 실행됩니다.

그래서 셋의 자리가 갈립니다.

• 채널 — 진짜로 동시에 일어나는 일을 전달할 때. 생산자와 소비자가 별개의 고루틴일 때.
• iter.Seq — 한 번만 훑을 때. 재계산이 싸거나 값이 매번 달라도 될 때. Go 관용구에 가장 잘 맞습니다.
• 메모이즈된 스트림 — 같은 무한 수열을 여러 번, 여러 곳에서 봐야 하고 재계산이 비쌀 때.

소수의 체가 마지막 경우의 좋은 예입니다. n번째 소수를 구하려면 그 앞의 소수를 전부 알아야 하는데, 매번 다시 계산하면 감당이 안 됩니다. 메모이제이션이 필수입니다.

이게 원서 3.5 를 Go 로 읽을 때 가장 중요한 판정입니다. 채널이 스트림처럼 생겼다고 채널로 옮기면, 두 번 읽는 순간 조용히 틀립니다.

6. 3.5.5 — 3장이 스스로를 뒤집습니다#

3장의 마지막 절이 이 책답습니다.

3.1 부터 3.4 까지 원서는 대입과 객체 로 세상을 모형화했습니다. 은행 계좌는 상태가 있고, 시간이 흐르면 그 상태가 바뀝니다.

그런데 3.5 에서 스트림을 손에 넣고 나면 같은 것을 대입 없이 표현할 수 있습니다. 계좌의 잔액을 “시간에 따라 변하는 값” 이 아니라 “잔액들의 무한 수열” 로 보면 됩니다. 아무것도 바뀌지 않습니다. 수열 전체가 이미 거기 있고, 우리가 뒤쪽을 아직 안 봤을 뿐입니다.

원서는 두 세계관을 나란히 놓고 어느 쪽도 편들지 않습니다.

객체의 세계 는 시간을 프로그램의 시간에 맡깁니다. 직관적이고, 국소적으로 상태를 감출 수 있고, 대신 참조 투명성과 치환 모델을 잃습니다.

스트림의 세계 는 시간을 수열의 색인으로 만듭니다. 참조 투명성을 지키고, 대신 “지금” 이라는 개념이 사라집니다. 그리고 원서는 여기서 정직하게 인정합니다. 여러 스트림을 합치는 순간(merge) 어떤 순서로 합칠지가 문제가 되고, 그건 동시성 문제가 다른 옷을 입고 돌아온 것입니다.

Go 프로그래머에게는 이 대비가 낯설지 않습니다. 뮤텍스로 상태를 지키는 방식과 채널로 소유권을 옮기는 방식이 정확히 같은 두 세계관입니다. 그리고 채널을 쓴다고 문제가 사라지지 않는다는 것도 겪어 보면 압니다. select 의 분기 순서, 버퍼 크기, 닫힘 시점이 전부 “합치는 순서” 문제입니다.

어느 쪽도 공짜가 아니라는 것이 3장의 결론입니다.

7. 이번 편의 정리#

3장이 여기서 끝납니다. 그리고 다음 편부터 이 책의 정점인 4장 입니다.

4장에서 하는 일은 하나입니다. 언어를 직접 만듭니다. 원서는 Scheme 으로 Scheme 인터프리터를 쓰는데, eval 과 apply 두 함수가 서로를 부르는 30줄 남짓한 코드가 언어 하나를 정의합니다.

Go 에서는 그렇게 안 됩니다. Part 1 과 Part 5 에서 예고한 마찰 — 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.
  • 3.4 절 (동시성) — https://sarabander.github.io/sicp/html/3_002e4.xhtml
  • 3.5 절 (스트림) — https://sarabander.github.io/sicp/html/3_002e5.xhtml
• 교환(exchange)에서의 교착 상태와 계좌 번호로 순서를 정하는 처방은 3.4.2 절 본문에 있습니다.
• 스트림의 memo-proc 은 3.5.1 절, 암묵적 피보나치 정의와 소수의 체는 3.5.2 절에 있습니다.
• 3.5.5 절의 “함수형 프로그램의 모듈성과 객체의 모듈성” 대비는 원서의 3장 마무리입니다.

본문의 실측 데이터

• 모든 수치와 출력은 go version go1.26.0 darwin/arm64 에서 직접 실행한 결과입니다.
• 1절의 잔액 소실 실험은 읽기와 쓰기 사이에 runtime.Gosched() 를 넣어 인터리빙을 유도한 것입니다. 그 한 줄이 없으면 대부분의 실행에서 잔액이 정상으로 나온다는 사실도 본문에 적었습니다.
• -race 출력은 go test -race 의 실제 출력이며, 경로만 줄였습니다.
• 교착 상태는 2초 시간 제한으로 판정했습니다. “끝나지 않음” 은 그 제한 안에 완료되지 않았다는 뜻입니다.
• 채널 소비자 분할 결과는 실행마다 다릅니다. 본문에 서로 다른 세 번의 실행 결과를 실었습니다.

시리즈

• Part 1: 마법사 책은 왜 아직도 살아 있나
• Part 2: 프로시저는 재귀인데 프로세스는 반복이다
• Part 3: 함수를 돌려주는 함수, 그리고 제네릭이 필요해지는 순간
• Part 4: 데이터란 무엇인가 — 저장 공간 없는 pair
• Part 5: 파이프라인으로서의 프로그램, 그리고 quote 가 없는 언어
• Part 6: 1985년에 쓰인 Go 인터페이스 설계 지침
• Part 7: 시간이 들어오면 치환 모델이 무너진다
• Part 8: 같은 pair 세 개를 세는 네 가지 답, 그리고 이벤트 루프