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

Part 11에서 평가기를 빠르게 만들고 게으르게 만들었습니다. 이번 편은 아무 값이나 고르게 만듭니다.

4.3 절이 도입하는 것은 amb 하나입니다.

(amb 1 2 3)

이 식의 값은 1이거나 2이거나 3입니다. 어느 것인지는 정해지지 않습니다. 그리고 이 값을 쓴 계산이 나중에 모순에 부딪히면, 시간이 되감겨서 다른 값으로 다시 시도합니다.

즉 백트래킹이 언어 기능이 됩니다. 프로그래머는 “무엇을 원하는가” 만 적고, “어떻게 찾는가” 는 평가기가 합니다.

그리고 여기가 Part 1에서 예고한 세 번째 마찰 의 자리입니다. Go 에는 일급 연속(call/cc)이 없습니다. 결론부터 말하면 그건 문제가 되지 않았습니다. 문제가 되지 않는 이유가 흥미롭고, 대신 다른 곳에서 값을 치렀습니다.

1. 연속이 두 개 필요합니다#

원서의 아이디어는 이것입니다. 평가기의 모든 실행 프로시저가 성공했을 때 갈 곳 과 실패했을 때 갈 곳 을 함께 받습니다.

type AmbFail func()
type AmbSucceed func(value any, fail AmbFail)
type AmbExec func(env *Env, succeed AmbSucceed, fail AmbFail)

읽는 법이 중요합니다.

  • succeed(값, fail) — “값을 얻었다. 그런데 이 값이 나중에 틀린 것으로 밝혀지면 이 fail 을 불러라. 그러면 다른 선택지로 넘어간다.”
  • fail() — “이 갈래는 막혔다. 위로 올라가서 다른 선택지를 시도해라.”

succeed 가 fail 을 함께 넘기는 것 이 핵심입니다. 성공은 잠정적입니다. 되돌아올 길을 항상 들고 다닙니다.

이제 amb 자체는 열 줄입니다.

func analyzeAmbChoices(exps any) AmbExec {
	var choices []AmbExec
	for e := exps; e != nil; e = Cdr(e) {
		choices = append(choices, AnalyzeAmb(Car(e)))
	}
	return func(env *Env, s AmbSucceed, f AmbFail) {
		var tryNext func(i int)
		tryNext = func(i int) {
			if i >= len(choices) {
				f() // 선택지가 다 떨어졌다. 실패를 더 위로 올린다
				return
			}
			choices[i](env, s, func() { tryNext(i + 1) })
		}
		tryNext(0)
	}
}

choices[i] 에게 넘기는 실패 연속이 “다음 선택지를 시도해라” 입니다. 이 한 줄이 백트래킹 전체입니다.

flowchart TD
    A["(amb 1 2 3)"] -->|"성공 연속 s"| B["1 을 골랐다"]
    B -->|"뒤에서 require 실패"| C["실패 연속 호출"]
    C --> D["2 를 골랐다"]
    D -->|"또 실패"| E["실패 연속 호출"]
    E --> F["3 을 골랐다"]
    F -->|"성공"| G["답"]
    E2["선택지 소진"] -.->|"더 위로 실패를 올린다"| H["바깥 amb 로"]

    style B fill:#FFD700,color:#000000
    style D fill:#FFD700,color:#000000
    style F fill:#90EE90,color:#000000
    style G fill:#90EE90,color:#000000
    style H fill:#FF9999,color:#000000

2. call/cc 가 없는데 왜 되는가#

Part 1 에서 “Go 에는 일급 연속이 없다” 를 마찰로 예고했습니다. 그런데 위 코드에는 call/cc 가 안 보입니다.

이유는 간단하고 중요합니다.

4.3 이 필요로 하는 연속은 우리가 만든 인터프리터 안의 연속이지, 호스트 언어의 연속이 아니다.

우리는 평가기를 연속 전달 방식(CPS) 으로 새로 씁니다. 그러면 “다음에 할 일” 이 항상 손에 잡히는 클로저로 존재합니다. 호스트에게 “지금 이 시점의 실행 상태를 값으로 달라” 고 요청할 필요가 없습니다.

원서도 호스트 Scheme 의 call/cc 를 쓰지 않습니다. 이건 Go 로 옮기면서 알게 된 게 아니라 원서의 설계 그대로입니다. 다만 Scheme 으로 읽으면 “어차피 call/cc 도 있는데” 라는 생각에 이 사실이 눈에 안 들어옵니다. Go 로 읽으면 연속이 언어 기능이 아니라 프로그래밍 기법이라는 점 이 분명해집니다.

일급 연속이 진짜로 필요한 것은 다른 경우입니다. 이미 CPS 로 쓰이지 않은 코드에서 실행 상태를 잡아내려 할 때입니다. 4.3 은 그 경우가 아닙니다.

3. require 와 탐색#

amb 하나에 프로시저 하나를 더하면 도구가 완성됩니다.

(define (require p) (if (not p) (amb)))

(amb) 는 선택지가 없는 amb 입니다. 항상 실패합니다. 그러니 require 는 “조건이 거짓이면 이 갈래를 버려라” 가 됩니다.

이 두 개로 리스트에서 원소 하나를 고르는 것도 만들 수 있습니다.

(define (an-element-of items)
  (require (not (null? items)))
  (amb (car items) (an-element-of (cdr items))))

첫 원소를 고르거나, 나머지에서 고르거나. 재귀적 정의가 그대로 비결정적 선택이 됩니다.

돌려 봤습니다.

(amb 1 2 3) 의 모든 해: 1, 2, 3

그리고 조건을 붙이면 이렇게 됩니다.

(let ((x (amb 1 2 3 4 5)) (y (amb 1 2 3 4 5)))
  (require (= (+ x y) 6))
  (list x y))

x+y=6 인 모든 (x y): (1 5), (2 4), (3 3), (4 2), (5 1)

25개 조합 중 5개를 찾아냈습니다. 프로그램에는 루프도, 후보 목록도, “안 맞으면 되돌아가라” 도 없습니다.

여기서 한 가지 함정을 확인해 뒀습니다. 같은 것을 최상위 식으로 쪼개면 안 됩니다.

같은 것을 최상위 식으로 쪼개면: (1 1)  <- 되감기가 끊긴다

(define x (amb ...)) 를 따로 평가하면 그 시점에 선택이 확정 됩니다. 나중에 다른 최상위 식이 실패해도 되돌아갈 수 없습니다. 되감기는 하나의 식 안에서만 일어납니다.

원서의 REPL 은 try-again 이라는 특별한 입력으로 이 경계를 넘습니다. 마지막 식의 실패 연속을 REPL 이 붙잡고 있다가 다시 부르는 방식입니다. 이 글의 드라이버도 같은 일을 합니다. 위에서 해를 다섯 개 다 모은 것이 그 동작입니다.

4. 피타고라스 삼조#

원서 4.3.1 의 예제입니다.

(define (a-pythagorean-triple-between low high)
  (let ((i (an-integer-between low high)))
    (let ((j (an-integer-between i high)))
      (let ((k (an-integer-between j high)))
        (require (= (+ (* i i) (* j j)) (* k k)))
        (list i j k)))))

세 겹 중첩 루프가 세 줄로 표현되었습니다. an-integer-between 이 세 번 불리고, 각각이 비결정적으로 값을 고르고, require 가 조건을 겁니다.

1~20 의 모든 삼조: (3 4 5), (5 12 13), (6 8 10), (8 15 17), (9 12 15), (12 16 20)

여섯 개. 손으로 확인하면 맞습니다. 3-4-5 와 그 배수인 6-8-10, 9-12-15, 12-16-20, 그리고 5-12-13 과 8-15-17.

j 가 i 부터 시작하고 k 가 j 부터 시작하는 것에 주목할 만합니다. 중복을 없애는 최적화가 탐색 코드가 아니라 범위 지정에 들어 있습니다. 무엇을 찾는지만 적어도 어떻게 찾을지가 나오는 구조입니다.

5. 4.3.2 — 다세대 주택 퍼즐#

원서에서 가장 유명한 논리 퍼즐입니다.

Baker, Cooper, Fletcher, Miller, Smith 가 5층 건물에 서로 다른 층에 산다. Baker 는 꼭대기가 아니다. Cooper 는 1층이 아니다. Fletcher 는 꼭대기도 1층도 아니다. Miller 는 Cooper 보다 위층이다. Smith 는 Fletcher 와 인접하지 않는다. Fletcher 는 Cooper 와 인접하지 않는다. 각자 몇 층에 사는가.

프로그램이 문제 진술을 거의 그대로 옮긴 것 입니다.

(define (multiple-dwelling)
  (let ((baker (amb 1 2 3 4 5)) (cooper (amb 1 2 3 4 5))
        (fletcher (amb 1 2 3 4 5)) (miller (amb 1 2 3 4 5))
        (smith (amb 1 2 3 4 5)))
    (require (distinct? (list baker cooper fletcher miller smith)))
    (require (not (= baker 5)))
    (require (not (= cooper 1)))
    (require (not (= fletcher 5)))
    (require (not (= fletcher 1)))
    (require (> miller cooper))
    (require (not (= (abs (- smith fletcher)) 1)))
    (require (not (= (abs (- fletcher cooper)) 1)))
    (list (list 'baker baker) (list 'cooper cooper)
          (list 'fletcher fletcher) (list 'miller miller)
          (list 'smith smith))))

require 한 줄이 조건 하나입니다. 탐색 알고리즘은 한 줄도 없습니다.

해: ((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))
시도한 갈래 수: 3905,  호스트 스택: 132.34 MB

Baker 3층, Cooper 2층, Fletcher 4층, Miller 5층, Smith 1층. 원서의 답과 같습니다. 그리고 해가 유일합니다. 모든 해를 찾도록 돌렸는데 하나만 나왔습니다.

이게 원서가 이 절에서 보여 주려는 것입니다. 적절한 언어를 만들면 문제 진술이 곧 프로그램이 됩니다. 그리고 그 언어를 만드는 데 필요한 것은 amb 하나였습니다.

되감을 때 set! 은 어떻게 되나#

4.3.3 이 짚는 미묘한 문제입니다. 되감을 때 대입도 되돌려야 합니다. 안 그러면 실패한 갈래의 부작용이 남습니다.

func analyzeAmbSet(x *Pair) AmbExec {
	name := Cadr(x).(Symbol)
	val := AnalyzeAmb(Caddr(x))
	return func(env *Env, s AmbSucceed, f AmbFail) {
		val(env, func(v any, f2 AmbFail) {
			old, _ := env.Lookup(name)   // 옛 값을 기억해 둔다
			env.Set(name, v)
			s(nil, func() {              // 되감을 때
				env.Set(name, old)       // 옛 값을 되돌리고
				f2()                     // 계속 위로 올라간다
			})
		}, f)
	}
}

실패 연속을 한 겹 감싸서 롤백을 끼워 넣습니다. 데이터베이스 트랜잭션의 언두 로그와 구조가 같습니다. 1985년 교재에서 트랜잭션 롤백을 여덟 줄로 구현합니다.

6. 그래서 값은 어디서 치르나#

call/cc 가 없어도 되는 것을 확인했습니다. 그런데 위 출력의 마지막 숫자가 걸립니다.

호스트 스택 132.34 MB.

5⁵ = 3,125 개 조합을 훑는 데 132 MB 를 썼습니다. 왜인가.

CPS 로 쓰면 “다음에 할 일” 이 전부 클로저 호출로 표현됩니다. 그리고 그 호출들은 서로의 꼬리 위치에 있습니다. 꼬리 호출 최적화가 있는 언어에서는 이 사슬이 스택을 안 먹습니다.

Go 에는 없습니다. Part 2의 그래프가 여기서 세 번째로 돌아옵니다.

탐색 깊이를 늘려 가며 재 봤습니다. 1부터 n 까지에서 7의 배수를 전부 찾는 프로그램입니다.

탐색 범위 n찾은 해호스트 스택
10014개2.28 MB
1,000142개16.41 MB
5,000714개64.41 MB
20,0002,857개256.44 MB

깊이에 정확히 선형입니다. n 이 20배 늘 때 스택도 20배 늘었습니다. Go 의 기본 스택 상한이 1 GB 이니, 이 추세면 n ≈ 8만 근처에서 죽습니다.

정리하면 이렇습니다.

Go 에서 amb 평가기를 만드는 것은 가능하고 어렵지도 않다. 대신 탐색 깊이가 호스트 스택에 갇힌다.

원서에서는 이 제약이 없습니다. 호스트 Scheme 이 꼬리 호출을 보장하므로 CPS 사슬이 상수 공간에서 돕니다. Part 11의 구문 분석 평가기와 완전히 같은 구조의 문제 이고, 해법도 같습니다. 트램폴린으로 바꾸거나, 명시적 스택으로 바꾸는 것입니다.

그리고 명시적 스택으로 바꾸는 방법이 바로 5장의 주제 입니다.

7. 실무에서 백트래킹을 짤 때#

이 절을 읽고 나면 Go 에서 백트래킹 코드를 볼 때 보이는 것이 달라집니다.

보통 이렇게 씁니다.

func solve(state *State, depth int) bool {
	if depth == n { return check(state) }
	for _, choice := range choices {
		state.apply(choice)
		if solve(state, depth+1) { return true }
		state.undo(choice)   // <- 이게 실패 연속이다
	}
	return false
}

state.undo(choice) 가 amb 의 실패 연속입니다. 그리고 return true 가 성공 연속입니다. 4.3 을 읽고 나면 이 관용구가 “관례” 가 아니라 연속 전달 방식을 스택으로 접은 것임을 알게 됩니다.

깊이가 문제가 되면 Go 에서도 대응은 같습니다. 재귀를 명시적 스택으로 바꿉니다.

type frame struct{ depth, next int }
stack := []frame{{0, 0}}
for len(stack) > 0 { /* ... */ }

이 변환이 기계적으로 가능하다는 것, 그리고 왜 가능한지가 다음 편의 내용입니다.

8. 4.4 논리 프로그래밍은 다루지 않았습니다#

정직하게 밝혀 둘 것이 있습니다. 4장에는 절이 네 개인데 이 시리즈는 셋만 다뤘습니다.

4.4 절은 논리 프로그래밍 질의 시스템 입니다. 이 책에서 단일 예제로는 가장 큰 것이고, 원서에서도 절 하나가 다른 장 하나만 한 분량입니다. 하는 일은 이렇습니다.

데이터베이스에 사실을 넣습니다.

(address (Bitdiddle Ben) (Slumerville (Ridge Road) 10))
(job (Bitdiddle Ben) (computer wizard))
(supervisor (Tweakit Lem E) (Bitdiddle Ben))

그리고 패턴으로 묻습니다.

(job ?x (computer ?type))

시스템이 데이터베이스를 뒤져 ?x 와 ?type 에 들어갈 값을 전부 찾아 줍니다. 규칙으로 추론도 합니다. Prolog 를 만드는 것입니다.

구현의 핵심 부품은 셋입니다. 패턴 매칭(질의를 사실과 맞춰 본다), 단일화(unification)(양쪽에 변수가 있을 때 맞춰 본다), 그리고 스트림(가능한 답을 지연 평가로 흘려보낸다). 3.5 의 스트림이 여기서 회수됩니다.

이걸 Go 로 제대로 옮기면 이 시리즈에서 가장 긴 편이 하나 더 필요합니다. 스트림·단일화·규칙 적용·재귀 규칙의 종료 문제까지 다뤄야 합니다. 이번 시리즈에서는 그 분량을 5장에 배정했습니다.

한 가지만 짚어 두면, 4.3 과 4.4 는 형제입니다. amb 는 “고르고 검사한다” 이고, 질의 시스템은 “패턴으로 맞춘다” 입니다. 둘 다 프로그램이 “어떻게” 대신 “무엇을” 적게 만들려는 시도이고, 4장의 마지막 두 절이 그 두 방향을 나란히 보여 줍니다.

9. 이번 편의 정리#

SICP 4.3 의 주장Go 에서
성공·실패 연속 두 개로 백트래킹을 만든다성립. 클로저로 그대로 옮겨짐
call/cc 가 필요하다필요 없음. 필요한 연속은 우리 평가기 안의 것
amb 하나 + require 하나면 탐색 언어가 된다성립
문제 진술이 곧 프로그램이 된다성립. 다세대 주택 퍼즐 원서와 같은 답
되감을 때 set! 도 되돌려야 한다성립. 실패 연속을 감싸서 롤백
(원서에 없음)탐색 깊이가 호스트 스택에 갇힘 (선형 증가)

4장이 여기서 끝납니다. 세 편에 걸쳐 인터프리터 세 개 를 만들었습니다. 보통 평가기, 구문 분석 평가기, 게으른 평가기, 그리고 비결정성 평가기까지 네 개입니다. 전부 같은 뼈대에서 갈라져 나왔습니다.

그리고 세 편 내내 같은 문제가 세 번 나왔습니다. 꼬리 호출을 어떻게 상수 공간으로 만드는가. Part 10 에서는 루프로 풀었고, Part 11 과 12 에서는 못 풀었습니다.

다음 편부터 5장입니다. 레지스터 머신 을 만듭니다. 레지스터 몇 개와 명령어 몇 개로 이루어진 기계를 시뮬레이션하고, 그 위에서 재귀를 스택으로 구현합니다. 그러고 나면 “꼬리 호출은 왜 스택을 안 먹어도 되는가” 가 기계 수준에서 자명해집니다. 지금까지 세 번 미룬 빚을 5장에서 갚습니다.

References#

1차 자료

본문의 실측 데이터

  • 모든 출력과 수치는 go version go1.26.0 darwin/arm64 에서 직접 실행한 결과입니다.
  • 다세대 주택 퍼즐의 답(Baker 3, Cooper 2, Fletcher 4, Miller 5, Smith 1)은 원서의 답과 일치합니다.
  • 호스트 스택 값은 평가를 별도 고루틴에서 돌린 뒤 그 고루틴이 끝나는 시점 의 runtime.MemStats.StackInuse 입니다. Go 는 스택을 즉시 줄이지 않으므로 이 값을 최댓값의 근사로 읽어 주십시오.
  • “n ≈ 8만 근처에서 죽는다” 는 측정한 선형 추세로부터의 외삽 이며, 그 지점까지 실제로 돌려 보지는 않았습니다.
  • 4.4 절은 구현하지 않았고 개요만 서술했습니다. 이 사실을 본문에 명시했습니다.

시리즈