Go 로 읽는 SICP Part 10: Go 로 Scheme 인터프리터 만들기 — 파서라는 청구서

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

Part 9로 3장을 끝냈습니다. 이제 이 책의 정점인 4장 입니다.

4장이 하는 일은 한 문장으로 요약됩니다. 언어를 직접 만듭니다. 원서는 Scheme 으로 Scheme 인터프리터를 쓰고, 그래서 메타순환(metacircular) 평가기 라고 부릅니다. 평가되는 언어와 평가하는 언어가 같기 때문입니다.

Go 로 하면 메타순환이 아닙니다. Go 로 Scheme 을 만드는 것이니 그냥 인터프리터입니다. 그리고 그 차이 때문에 Part 1 과 Part 5 에서 예고한 마찰의 청구서가 여기서 도착합니다.

이번 편에서 실제로 돌아가는 인터프리터를 만듭니다. 코드가 많지만 구조는 원서를 그대로 따라갑니다.

1. 원서가 공짜로 받는 것#

원서의 평가기가 얼마나 짧은지 먼저 봐야 합니다. 핵심은 이겁니다.

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp) (make-procedure (lambda-parameters exp)
                                       (lambda-body exp) env))
        ((begin? exp) (eval-sequence (begin-actions exp) env))
        ((cond? exp) (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) env)))
        (else (error "Unknown expression type: EVAL" exp))))

열세 줄입니다. apply 도 비슷한 길이입니다. 둘이 서로를 부르면서 언어 하나를 정의합니다.

왜 이렇게 짧은가. 입력이 이미 자료구조이기 때문입니다.

'(if (> x 0) 'pos 'neg)

Scheme 에서 이건 문자열이 아닙니다. 네 원소짜리 리스트 입니다. 첫 원소는 심볼 if, 둘째는 또 리스트, 셋째와 넷째는 심볼. eval 은 그냥 car 를 보고 분기하면 됩니다.

파싱할 게 없습니다. 이것이 동형성(homoiconicity)이고, Lisp 계열이 다른 언어와 갈라지는 지점입니다.

2. Go 가 내야 하는 청구서#

Go 에서 (if (> x 0) 'pos 'neg) 는 그냥 문자열입니다. 자료구조로 만들려면 손으로 읽어야 합니다.

그래서 이번 편의 첫 절반이 렉서와 파서 입니다. 원서에는 없는 부분입니다.

이건 Go 만의 사정이 아닙니다. Part 1 에서 인용한 대로, 공식 JavaScript 판도 같은 벽에 부딪혔고 서문에 이렇게 적었습니다. “프로그램을 데이터 구조로 직접 표현하는 것을 더 이상 당연시할 수 없어서” 4장에 프로그램 파싱 절을 새로 넣었다고. Scheme 이 아닌 언어로 SICP 4장을 하는 사람은 누구나 이 비용을 냅니다.

렉서#

토큰은 다섯 종류면 충분합니다. 여는 괄호, 닫는 괄호, 따옴표, 문자열, 그 밖의 원자.

func Tokenize(src string) ([]token, error) {
	var toks []token
	rs := []rune(src)
	for i := 0; i < len(rs); {
		c := rs[i]
		switch {
		case unicode.IsSpace(c):
			i++
		case c == ';': // 주석은 줄 끝까지
			for i < len(rs) && rs[i] != '\n' { i++ }
		case c == '(' || c == '[':
			toks = append(toks, token{tkLParen, "("})
			i++
		case c == '\'':
			toks = append(toks, token{tkQuote, "'"})
			i++
		// 문자열, 원자 ...
		}
	}
	return toks, nil
}

[]rune 으로 도는 것이 Go 다운 선택입니다. []byte 로 돌면 한글이 든 심볼이나 문자열에서 깨집니다.

파서#

파서는 재귀 하강입니다. Lisp 문법이 워낙 단순해서 함수 하나로 끝납니다.

func (p *parser) parseExpr() (any, error) {
	t, _ := p.next()
	switch t.kind {
	case tkLParen:
		var items []any
		for {
			nt, ok := p.peek()
			if !ok { return nil, fmt.Errorf("닫는 괄호가 없습니다") }
			if nt.kind == tkRParen {
				p.next()
				return List(items...), nil
			}
			e, err := p.parseExpr()
			if err != nil { return nil, err }
			items = append(items, e)
		}
	case tkQuote:
		e, err := p.parseExpr()
		if err != nil { return nil, err }
		return List(Symbol("quote"), e), nil  // 'x -> (quote x)
	// ...
	}
}

tkQuote 처리에 주목할 만합니다. 'x 를 (quote x) 로 펴는 것이 파서의 일입니다. Scheme 에서도 ' 는 리더 매크로이지 평가기의 관심사가 아닙니다. 여기서도 그렇게 했습니다.

원자는 정수 → 실수 → 불리언 → 심볼 순으로 시도합니다.

func atomValue(text string) any {
	if n, err := strconv.Atoi(text); err == nil { return n }
	if f, err := strconv.ParseFloat(text, 64); err == nil { return f }
	switch text {
	case "#t", "#true": return true
	case "#f", "#false": return false
	}
	return Symbol(text)
}

파서가 실제로 무엇을 만드는지 확인해 봤습니다.

  소스 : (define (sq x) (* x x))
  구조 : (define (sq x) (* x x))
  Go 타입: *lisp.Pair
  car   : define (lisp.Symbol)
  cadr  : (sq x)
  caddr : (* x x)

Part 4 에서 만든 Pair 가 그대로 쓰였습니다. 2장에서 Cons·Car·Cdr 를 만든 것이 여기서 회수됩니다. 원서가 2장을 4장 앞에 놓은 이유가 이것입니다.

3. 환경 (4.1.3)#

Part 7 에서 배운 환경 모델을 자료구조로 만듭니다. 프레임 하나는 이름 표 하나와 부모 포인터입니다.

type Env struct {
	vars   map[Symbol]any
	parent *Env
}

func (e *Env) Lookup(s Symbol) (any, error) {
	for env := e; env != nil; env = env.parent {
		if v, ok := env.vars[s]; ok { return v, nil }
	}
	return nil, fmt.Errorf("묶이지 않은 변수: %s", s)
}

Go 에서는 33줄입니다. 원서는 프레임을 pair 두 개(이름 리스트와 값 리스트)로 만드는데, Go 에서는 map 을 쓰는 편이 나은 선택입니다. 조회가 O(1) 이고, 원서의 표현이 주는 교육적 가치(모든 것을 pair 로)는 이미 2장에서 받았습니다.

Set 과 Define 의 차이가 중요합니다.

func (e *Env) Define(s Symbol, v any) { e.vars[s] = v }  // 현재 프레임에 새로 묶는다

func (e *Env) Set(s Symbol, v any) error {                // 이미 묶인 것을 찾아 바꾼다
	for env := e; env != nil; env = env.parent {
		if _, ok := env.vars[s]; ok { env.vars[s] = v; return nil }
	}
	return fmt.Errorf("묶이지 않은 변수에 대입: %s", s)
}

define 은 현재 프레임에만 씁니다. set! 은 위로 올라가며 찾습니다. 이 차이가 클로저의 상태를 가능하게 합니다. Part 7 의 makeWithdraw 에서 set! 이 바깥 프레임의 balance 를 고쳤던 그 동작입니다.

4. 평가기 핵심 (4.1.1)#

이제 eval 입니다. 구조는 원서를 그대로 따라가되, Go 의 타입 스위치를 씁니다.

func Eval(exp any, env *Env) (any, error) {
	for { // 꼬리 호출 자리를 루프로 처리한다
		switch x := exp.(type) {
		case int, float64, string, bool, nil:
			return x, nil // 스스로 평가되는 것
		case Symbol:
			return env.Lookup(x)
		case *Pair:
			op := x.Car
			if sym, ok := op.(Symbol); ok {
				switch sym {
				case "quote":  return Cadr(x), nil
				case "if":     /* 아래 참조 */
				case "define": return evalDefine(x, env)
				case "set!":   /* ... */
				case "lambda":
					params, err := toParams(Cadr(x))
					if err != nil { return nil, err }
					return &Procedure{Params: params, Body: Cddr(x), Env: env}, nil
				// begin, cond, let, and, or ...
				}
			}
			// 적용
			proc, err := Eval(op, env)
			// ...
		}
	}
}

원서의 cond 분기와 Go 의 switch 분기가 거의 한 줄씩 대응합니다. Part 5 에서 “Go 의 태그 없는 switch 는 사실상 cond 다” 라고 한 것이 여기서 값을 합니다.

for 루프가 왜 있는가#

Eval 함수 전체를 for { ... } 로 감쌌습니다. 이게 이 시리즈에서 가장 중요한 회수입니다.

Part 2 에서 Go 에 꼬리 호출 최적화가 없다고 했습니다. 그런데 우리가 지금 만드는 것은 인터프리터 입니다. 인터프리터 안에서는 무엇이 꼬리 위치인지 우리가 압니다. 그러니 꼬리 위치의 평가를 Go 함수 호출로 하지 않고 루프의 다음 반복으로 처리하면 스택이 안 자랍니다.

case "if":
	pred, err := Eval(Cadr(x), env)   // 조건은 꼬리가 아니다 -> 재귀 호출
	if err != nil { return nil, err }
	if isTrue(pred) {
		exp = Caddr(x)                // 결과는 꼬리다 -> 루프로
	} else {
		exp = Car(Cdr(Cddr(x)))
	}
	continue

프로시저 적용도 마찬가지입니다.

case *Procedure:
	ne, err := p.Env.Extend(p.Params, args)
	// ... 본문의 마지막 식만 남기고
	exp, env = Car(body), ne
	continue                          // 호출이 아니라 반복

Go 가 안 해 주는 꼬리 호출 최적화를, 우리가 만든 언어 안에서는 직접 구현한 것입니다. Part 2 에서 “1장에서 손해 본 걸 5장에서 되찾는다” 고 했는데, 사실은 4장에서 이미 절반을 되찾았습니다. 5장에서 이 변환이 왜 기계적으로 가능한지가 밝혀집니다.

파생 식#

원서 4.1.2 의 좋은 아이디어 하나를 그대로 가져왔습니다. cond 와 let 은 평가기가 직접 처리하지 않습니다. 더 단순한 형태로 바꿔치기한 뒤 다시 평가합니다.

// (let ((a 1) (b 2)) body) -> ((lambda (a b) body) 1 2)
func letToCombination(x *Pair) (any, error) {
	bindings := Cadr(x)
	body := Cddr(x)
	var names, values []any
	for b := bindings; b != nil; b = Cdr(b) {
		names = append(names, Car(Car(b)))
		values = append(values, Cadr(Car(b)))
	}
	lambda := Cons(Symbol("lambda"), Cons(List(names...), body))
	return Cons(lambda, List(values...)), nil
}

Part 3 에서 “let 은 즉시 호출되는 lambda 의 문법 설탕” 이라고 했습니다. 여기서 그 문장이 코드가 되었습니다. cond 도 같은 방식으로 중첩된 if 로 바뀝니다.

이게 문법 설탕(syntactic sugar)의 정확한 정의입니다. 평가기의 코어를 건드리지 않고 표면 문법만 늘리는 것. 원서는 이 기법의 이름을 알려 주고, 4.1.2 의 연습문제들이 이걸 반복 훈련시킵니다.

5. 돌려 봤습니다#

원시 프로시저를 심고(+, car, cons, display 등 40여 개) 실행했습니다.

=== 우리가 만든 언어로 프로그램 짜기 ===
(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1)))))
  ;; => factorial
(factorial 20)
  ;; => 2432902008176640000

20! = 2,432,902,008,176,640,000. 맞습니다.

그리고 3장의 계좌 객체를 우리 언어 위에서 돌렸습니다.

(define (make-account balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount)) balance)
        'insufficient))
  (define (deposit amount) (set! balance (+ balance amount)) balance)
  (lambda (m)
    (cond ((eq? m 'withdraw) withdraw)
          ((eq? m 'deposit) deposit)
          (else (error "unknown request" m)))))

(list ((acc 'withdraw) 50) ((acc 'withdraw) 60) ((acc 'deposit) 40))
  ;; => (50 insufficient 90)

우리가 만든 언어가 클로저·내부 정의·set!·메시지 패싱을 전부 지원합니다. Part 7 에서 Go 로 직접 짰던 것과 같은 결과가, 이번에는 우리 언어 위에서 나왔습니다.

테스트도 붙였습니다. 재귀, 고차 함수, 클로저 상태, 에러 처리까지 통과합니다.

undefined-var    -> 묶이지 않은 변수: undefined-var
(car 5)          -> car: pair 가 아닙니다: 5
(1 2 3)          -> 프로시저가 아닙니다: 1
(/ 1 0)          -> /: 0 으로 나눌 수 없습니다

Go 답게 에러를 값으로 돌려줍니다. 원서는 error 프로시저로 호스트 Scheme 의 에러 처리에 맡기는데, Go 에서는 (any, error) 를 평가기 전체에 관통시켰습니다. 코드가 길어지는 주된 원인이지만, 인터프리터가 호스트 프로그램을 죽이지 않는다는 이득이 있습니다.

6. 청구서를 계산해 봅시다#

원서가 공짜로 받은 것과 우리가 지불한 것을 숫자로 놓아 봅니다.

Go 쪽 줄 수가 큰 이유는 셋입니다.

첫째, 파서. 171줄이 통째로 추가 비용입니다.

둘째, 에러 전파. 모든 함수가 (any, error) 를 돌려주고 호출마다 if err != nil 이 붙습니다.

셋째, 원서는 호스트의 것을 빌려 씁니다. 원서의 평가기는 + 나 car 를 구현하지 않습니다. 호스트 Scheme 의 것을 그대로 씁니다. 우리는 다 만들어야 합니다.

그런데 셋 중 진짜 마찰은 첫째뿐입니다. 둘째는 Go 의 선택이고, 셋째는 메타순환이 아니라서 생긴 당연한 결과입니다.

그리고 값을 치른 대가로 얻은 것이 있습니다. 인터프리터가 실제로 무슨 일을 하는지 처음부터 끝까지 보입니다. 원서는 파싱을 건너뛰게 해 주는데, 그건 “이 부분은 이미 되어 있다고 치자” 는 것입니다. 실제 언어를 만들 때는 아무도 그렇게 해 주지 않습니다.

7. 4.1.5 — 프로그램이 곧 데이터#

원서 4.1.5 의 제목이 Data as Programs 입니다. 평가기를 만들고 나면 관점이 뒤집힌다는 이야기입니다.

우리 언어에서 프로그램을 리스트로 만들어 봤습니다.

(define code (list '+ 1 2 3))   ; 프로그램을 리스트로 만든다
code
  ;; => (+ 1 2 3)
; 이 리스트를 그대로 실행할 수 있다
  ;; Eval(code) => 6

code 는 데이터입니다. list 로 만들었고, car 로 꺼낼 수 있고, 원소를 바꿀 수도 있습니다. 그런데 Eval 에 넣으면 프로그램입니다.

이게 평가기가 하는 일의 정확한 정의입니다.

평가기는 데이터를 프로그램으로 읽는 프로그램 이다.

그리고 원서는 여기서 한 걸음 더 갑니다. 이 관점을 뒤집으면, 어떤 프로그램도 다른 프로그램의 데이터 입니다. 컴파일러가 하는 일이 그것이고, 5장에서 실제로 만듭니다.

그런데 Go 판에서는 이 절이 원서만큼 강렬하지 않습니다. 우리 언어 안에서는 프로그램이 데이터인데, Go 자체에서는 아니기 때문입니다. 우리가 만든 세계 안에서만 성립하는 성질입니다.

역설적으로 이게 이 절의 요점을 더 선명하게 만듭니다. 동형성은 언어가 주는 선물이지 계산의 본질이 아닙니다. 그리고 그 선물을 받지 못한 언어에서도 인터프리터는 만들 수 있습니다. 조금 더 길게 쓸 뿐입니다.

8. 이번 편의 정리#

다음 편은 4.1.7 과 4.2 입니다.

4.1.7 은 구문 분석을 실행에서 분리 하는 최적화입니다. 지금 만든 평가기는 같은 식을 반복 평가할 때마다 “이게 if 인가 lambda 인가” 를 매번 다시 판정합니다. 재귀 함수 본문이라면 그 판정을 수천 번 반복합니다. 이걸 한 번만 하고 실행 프로시저를 만들어 두면 어떻게 되는지, 실제로 벤치마크를 재 보겠습니다.

4.2 는 게으른 평가기 입니다. 인자를 부를 때가 아니라 쓸 때 계산하도록 평가기를 고칩니다. 놀랍게도 고칠 곳이 몇 군데 안 되고, 그러고 나면 Part 9 의 스트림이 언어 기능으로 공짜로 딸려 옵니다.

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.
  • 4.1 절 (메타순환 평가기) — https://sarabander.github.io/sicp/html/4_002e1.xhtml
• 본문에 인용한 eval 정의는 원서 4.1.1 절의 것입니다.
• 파생 식(cond→if)은 4.1.2 절, 환경 자료구조는 4.1.3 절, Data as Programs 는 4.1.5 절입니다.
• SICP JS 판이 4장에 프로그램 파싱 절을 신설한 이유는 그 판의 Preface 에 있습니다 — https://sicp.sourceacademy.org/chapters/prefaces03.html

본문의 실측 데이터

• 인터프리터는 실제로 동작하며, 모든 출력은 go version go1.26.0 darwin/arm64 에서 직접 실행한 결과입니다.
• 6절의 줄 수는 주석과 빈 줄을 제외 하고 센 것입니다. SICP 쪽 줄 수는 원서 본문 코드 블록을 센 것으로, 두 언어의 서식이 다르므로 정확한 비교가 아니라 규모의 대비로 읽어 주십시오.
• 테스트는 기본 식 29개, 재귀, 클로저 상태, 고차 함수, 에러 처리 네 묶음이 모두 통과합니다.

시리즈

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