元循环求值器（上）：用 Racket 写 Racket

为什么这件事这么重要

「用一门语言写它自己的解释器」——这个动作有个名字，叫元循环求值器(metacircular evaluator)。它是 SICP 第四章的高潮，也是很多人编程生涯里的一个分水岭时刻。

为什么是分水岭？因为在你写出它之前,「编程语言」对你是一个黑盒 —— 一套你必须遵守、但不知其所以然的规则。写出它之后，语言变成了一个你亲手拆装过的机器。你会开始把所有语言 —— Kotlin、JS、Rust —— 都看成「某台 eval 机器上的一组配置」，而不是「必须背下来的戒律」。

整个求值器，就是 eval 和 apply

在写代码之前，先把那张架构图刻进脑子。整台机器只有两个函数：

动手：一块一块搭

下面这份代码，你可以一段段粘进 DrRacket 跑。我在本机 Racket v9.2 上完整跑过它。

零件 1：环境（第 5 章那张图，变成代码）

#lang racket

; 一个环境帧:一张「名字→值」的表 + 指向父帧的指针
(struct frame (vars parent))

(define (make-env parent) (frame (make-hash) parent))

(define (env-lookup env name)               ; 查变量:顺着链往上找
  (cond
    [(not env) (error 'eval "未绑定的标识符: ~a" name)]
    [(hash-has-key? (frame-vars env) name)
     (hash-ref (frame-vars env) name)]
    [else (env-lookup (frame-parent env) name)]))   ; ← 找不到就往父帧找

(define (env-define! env name val)
  (hash-set! (frame-vars env) name val))

这就是第 5 章那个环境链，一字不差地变成了代码。env-lookup 的 else 分支「往父帧找」，就是你在环境链 demo 里看到的那根向上的箭头。

零件 2：闭包（第 6 章那个「代码 + 出生环境」）

; 闭包 = 参数 + 函数体 + 「我出生时的环境」
(struct closure (params body env))

三个字段。第 5 章我说「闭包就是一个三字段结构体」，这里它真的是。

零件 3：全局环境，装几个原语

(define global (make-env #f))              ; 顶层,没有父帧

; 把宿主 Racket 的一些函数,借给我们的小语言用
(for ([pair (list (cons '+ +) (cons '- -) (cons '* *) (cons '/ /)
                  (cons '= =) (cons '< <) (cons '> >)
                  (cons 'cons cons) (cons 'car car) (cons 'cdr cdr)
                  (cons 'list list) (cons 'null? null?))])
  (env-define! global (car pair) (cdr pair)))

这些「原语」是我们语言的地基 —— 我们不自己实现加法，直接借宿主 Racket 的 +。（一个真正从零开始的解释器会连加法都自己实现到位运算，但那是另一个故事。）

零件 4:eval —— 机器的一半

(define (my-eval expr env)
  (cond
    ; —— 自求值:数字、布尔,就是它们自己(第 7 章步进器里的「值」)
    [(number? expr)  expr]
    [(boolean? expr) expr]

    ; —— 符号:查环境(第 5 章)
    [(symbol? expr)  (env-lookup env expr)]

    ; —— 复合表达式:看第一个词是不是特殊形式
    [(pair? expr)
     (case (car expr)

       ; quote:原样返回,不求值(第 4 章)
       [(quote) (cadr expr)]

       ; if:特殊形式 —— 只求值一个分支(第 7 章!)
       [(if) (if (my-eval (cadr expr) env)
                 (my-eval (caddr expr) env)
                 (my-eval (cadddr expr) env))]

       ; define:给名字绑个值
       [(define)
        (if (pair? (cadr expr))
            ; (define (f x) body) 是糖(第 6 章)
            (env-define! env (car (cadr expr))
                         (closure (cdr (cadr expr)) (cddr expr) env))
            (env-define! env (cadr expr) (my-eval (caddr expr) env)))]

       ; lambda:造一个闭包 —— 把当前环境装进去(第 5、6 章)
       [(lambda) (closure (cadr expr) (cddr expr) env)]

       ; let:新建一帧,绑定,在新帧里求值体
       [(let)
        (define new-env (make-env env))
        (for ([b (cadr expr)])
          (env-define! new-env (car b) (my-eval (cadr b) env)))
        (for/last ([e (cddr expr)]) (my-eval e new-env))]

       ; —— 都不是?那就是函数调用:
       [else
        (my-apply (my-eval (car expr) env)                       ; 算出函数
                  (map (lambda (a) (my-eval a env)) (cdr expr)))])] ; 算出所有参数
    [else (error 'eval "不认识的表达式: ~a" expr)]))

零件 5:apply —— 机器的另一半

(define (my-apply f args)
  (cond
    ; 原语:直接借宿主的力
    [(procedure? f) (apply f args)]

    ; 闭包:第 5 章那个「调用」动作
    [(closure? f)
     (define new-env (make-env (closure-env f)))   ; ← 新帧的父 = 闭包的出生环境!
     (for ([p (closure-params f)] [a args])        ;   (不是调用者的环境 —— 词法作用域)
       (env-define! new-env p a))                  ;   绑定参数
     (for/last ([e (closure-body f)])              ;   在新帧里求值函数体
       (my-eval e new-env))]                       ;   ↑ apply 又调回了 eval!

    [else (error 'apply "不是一个函数: ~a" f)]))

让它跑起来

(define (run expr) (my-eval expr global))

(run '(+ 1 (* 2 3)))                    ; ⇒ 7
(run '(if (> 3 2) 'yes 'no))            ; ⇒ 'yes

(run '(define (square x) (* x x)))
(run '(square 7))                       ; ⇒ 49

(run '(define (fact n)
        (if (= n 0) 1 (* n (fact (- n 1))))))
(run '(fact 5))                         ; ⇒ 120   ← 递归!

(run '(define (adder n) (lambda (x) (+ x n))))
(run '((adder 10) 5))                   ; ⇒ 15    ← 闭包!

(run '(let ([a 3] [b 4]) (+ (* a a) (* b b))))   ; ⇒ 25

(run '(define (map1 f lst)
        (if (null? lst) '()
            (cons (f (car lst)) (map1 f (cdr lst))))))
(run '(map1 (lambda (x) (* x x)) (list 1 2 3 4)))   ; ⇒ '(1 4 9 16)  ← 高阶!

它全都跑通了。递归、闭包、高阶函数、let —— 一个真正的编程语言的核心，一百行。而这一百行里，没有一行是这一章新学的 —— 全是前二十章零件的组装。

看着 eval 和 apply 互相咬尾巴

光看代码不够。下面这台机器，就是上面那个 my-eval / my-apply 的忠实翻版（我用 JS 重写了一遍，好让它一边跑一边把自己的调用轨迹吐出来 —— 但它的逻辑和上面的 Racket 一一对应）。选一个例子，一步步走，盯着 eval 和 apply 交替出现：

特别看那个 fact 的例子：你会看到 eval 遇到 (fact 4) → apply 展开函数体 → 又 eval 到 (fact 3) → 又 apply……那条一层层深下去又一层层浮上来的轨迹，就是递归的全貌。而 if 的例子会让你看到：没被选中的那个分支，轨迹里一行都没有 —— 特殊形式的威力，肉眼可见。

「元循环」这个名字的深意

回流

下一章

我们造出了一台会求值的机器。但目前它只能解释 Racket 已经有的东西。

下一章，我们做一件真正激动人心的事：修改这台机器，让我们的小语言长出宿主 Racket 没有的特性。加一个 let?小菜。加一个自己的宏系统？可以。加一个 amb（能回溯的非确定性选择，直接用上第 14 章的续延）?——你会发现，给一门你自己造的语言加特性，比你想象的容易得多。

因为这一次，eval 是你的了。