0x07.闭包与可变量 - 实现一个解释器 in Racket

发表于 更新于
在解释器中实现闭包和可变量，理解 BoxC 类型与环境的关系

本文是0x06.环境实现的续篇，探讨如何支持可变量和闭包。

前言

在真实的编程语言中，变量是可变的。赋值语句是基本特性：

1
2
int x = 0;
x = x + 1;  // 赋值改变变量值

但在前面的解释器实现中，我们只支持不可变的变量。本文将扩展解释器，支持：

  1. 可变量（BoxC）
  2. 闭包捕获
  3. 环境与作用域

可变量的表示

为什么需要 BoxC？

在函数式语言中，我们可以用**代换（substitution）**来处理变量：

  • ((lambda (x) (+ x 1)) 5) → (+ 5 1) → 6

但这种方法在以下情况会失效：

  1. 赋值：x = x + 1，需要先读取再写入
  2. 闭包：函数捕获自由变量，需要持久化环境

解决方案：引入 Box（盒子）作为值的容器。

BoxC 类型定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#lang typed-plai

;; 值类型
(define-type Value
  [numV (n : number)]
  [closV (args : (listof symbol))
         (body : ExprC)
         (env : Env)]  ;; 闭包捕获的环境
  [boxV (val : Value)])  ;; 可变量的盒子

;; 表达式类型
(define-type ExprC
  [numC (n : number)]
  [idC (s : symbol)]
  [appC (fun : ExprC) (args : (listof ExprC))]
  [lamC (args : (listof symbol)) (body : ExprC)]
  [boxC (val : ExprC)]      ;; 创建盒子
  [unboxC (box : ExprC)]    ;; 打开盒子
  [setboxC (box : ExprC) (val : ExprC)]  ;; 设置盒子值
  [seqC (e1 : ExprC) (e2 : ExprC)]  ;; 顺序执行
  [plusC (l : ExprC) (r : ExprC)]
  [multC (l : ExprC) (r : ExprC)])

图解：Box 的工作原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
┌─────────────────────────────────────────────────────────────┐
│                      盒子（Box）是什么？                      │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│   普通变量：           盒子（Box）：                         │
│                                                             │
│   x = 5                    ┌─────────┐                      │
│   ─────────►               │  boxV   │                      │
│   直接存值                 │  ────┐  │                      │
│                            │  5   │◄─┼── 环境指向盒子       │
│                            │  ────┘  │                      │
│                            └─────────┘                      │
│                                                             │
│   ❌ 不能修改                  ✅ 可以修改                   │
│   x = x + 1               unbox → 修改 → setbox!            │
│                                                             │
└─────────────────────────────────────────────────────────────┘

环境表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
;; 绑定：一个变量名对应一个盒子
(define-type Binding
  [bind (name : symbol) (box : Value)])

(define-type-alias Env (listof Binding))

;; 查找变量
(define (lookup [for : symbol] [env : Env]) : Value
  (cond
    [(empty? env) (error 'lookup "name not found: ~a" for)]
    [else
     (if (symbol=? for (bind-name (first env)))
         (bind-box (first env))
         (lookup for (rest env)))]))

解释器实现

核心解释函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
;; 解释表达式
(define (interp [e : ExprC] [env : Env]) : Value
  (type-case ExprC e
    [numC (n) (numV n)]
    [idC (s) (unboxV (lookup s env))]

    [lamC (args body) (closV args body env)]

    [appC (fun args)
          (local
            [(define fun-val (interp fun env))
             (define arg-vals (map (λ (a) (interp a env)) args))]
            (type-case Value fun-val
              [closV (f-args f-body f-env)
                     ;; 扩展环境，绑定实参到盒子
                     (interp f-body
                             (extend-env*
                              (map bind f-args
                                   (map boxV arg-vals))
                              f-env))]
              [else (error 'interp "not a function")]))]

    ;; 可变量操作
    [boxC (val) (boxV (interp val env))]
    [unboxC (box) (unboxV (interp box env))]
    [setboxC (box val)
             (local
               [(define b (interp box env))]
               (set-boxV! b (interp val env))
               b)]
    [seqC (e1 e2)
          (begin
            (interp e1 env)
            (interp e2 env))]

    [plusC (l r)
           (num+ (interp l env) (interp r env))]
    [multC (l r)
           (num* (interp l env) (interp r env))]))

辅助函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
;; 环境扩展
(define (extend-env [b : Binding] [env : Env]) : Env
  (cons b env))

(define (extend-env* [bs : (listof Binding)] [env : Env]) : Env
  (append bs env))

;; 数值运算
(define (num+ [l : Value] [r : Value]) : Value
  (type-case Value l
    [numV (n) (type-case Value r
                [numV (m) (numV (+ n m))]
                [else (error 'num+ "not a number")])]
    [else (error 'num+ "not a number")]))

(define (num* [l : Value] [r : Value]) : Value
  (type-case Value l
    [numV (n) (type-case Value r
                [numV (m) (numV (* n m))]
                [else (error 'num* "not a number")])]
    [else (error 'num* "not a number")]))

测试用例

测试 1：基本赋值

1
2
3
4
5
;; let x = 5 in x + 1
(interp (seqC (boxC (numC 5))
              (plusC (unboxC (idC 'x)) (numC 1)))
        mt-env)
;; => (numV 6)

测试 2：修改变量

1
2
3
4
5
6
;; let x = 5 in (set! x 10; x)
(interp (seqC (boxC (numC 5))
              (seqC (setboxC (idC 'x) (numC 10))
                    (unboxC (idC 'x))))
        mt-env)
;; => (numV 10)

图解：闭包捕获过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
┌──────────────────────────────────────────────────────────────────┐
│                    闭包如何捕获自由变量？                           │
├──────────────────────────────────────────────────────────────────┤
│                                                                  │
│  代码：                                                           │
│    (let ((x 10))                                                 │
│      (lambda (y) (+ x y)))                                       │
│                                                                  │
│  当 lambda 创建时：                                               │
│                                                                  │
│     ┌──────────────────────────────────────────────────────┐     │
│     │                    lambda 表达式                       │     │
│     │  ┌─────────────────────────────────────────────────┐  │     │
│     │  │ args: [y]                                       │  │     │
│     │  │ body: (+ x y)                                   │  │     │
│     │  │                                                │  │     │
│     │  │  x 是自由变量 ──────────► 被当前环境"冻结"      │  │     │
│     │  │                             │                    │  │     │
│     │  │                             ▼                    │  │     │
│     │  │                   ┌─────────────────┐           │  │     │
│     │  │                   │ env: {x -> 10}  │───────────┼──┘     │
│     │  │                   └─────────────────┘           │        │
│     │  └─────────────────────────────────────────────────┘        │
│     └──────────────────────────────────────────────────────────────┘
│                                                                  │
│  当函数被调用：                                                   │
│    ((f 5)) → x=10, y=5 → 结果: 15                                │
│                                                                  │
└──────────────────────────────────────────────────────────────────┘

测试 3：闭包捕获

1
2
3
4
5
6
7
8
9
10
11
12
13
14
;; let f = (lambda (y) (lambda () x + y)
;;     in ((f 5) 10)
;;
;; 预期结果：15（x=10, y=5）

(interp (appC (appC (lamC '(y)
                          (lamC '()
                                (plusC (unboxC (idC 'x))
                                       (unboxC (idC 'y)))))
                    (numC 5))
              (numC 10))
        (extend-env (bind 'x (boxV (numV 10)))
                    mt-env))
;; => (numV 15)

测试 4：计数器工厂

1
2
3
4
5
6
7
8
9
10
11
12
13
;; make-counter 返回一个闭包，每次调用返回递增的值
(define make-counter
  (lamC '()
        (seqC (boxC (numC 0))
              (lamC '()
                    (seqC (setboxC (idC 'cnt)
                                   (plusC (unboxC (idC 'cnt)) (numC 1)))
                          (unboxC (idC 'cnt)))))))

;; 测试
(interp (seqC (boxC make-counter)
              (appC (unboxC (idC 'c)) mt-env))
        (extend-env (bind 'c make-counter) mt-env))

闭包与环境

闭包的生命周期

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
┌─────────────────────────────────────────────────────┐
│                    闭包结构                          │
├─────────────────────────────────────────────────────┤
│                                                     │
│   ┌─────────────┐                                   │
│   │  closV      │                                   │
│   ├─────────────┤                                   │
│   │ args: [x,y] │                                   │
│   │ body: ...   │                                   │
│   │ env ────────┼──► ┌─────────────────────────┐   │
│   │             │    │ Binding 'x -> boxV(10)  │   │
│   │             │    │ Binding 'y -> boxV(5)   │   │
│   └─────────────┘    └─────────────────────────┘   │
│                                                     │
│   当函数被调用时，它携带这个环境副本               │
│   即使外层作用域已结束，环境仍被保留               │
└─────────────────────────────────────────────────────┘

环境链查找

graph LR
    A[调用函数] --> B[使用闭包中的env]
    B --> C{查找变量x}
    C -->|在env中找到| D[返回对应的盒子]
    C -->|找不到| E[报错：未绑定变量]

    style A fill:#e3f2fd
    style B fill:#f3e5f5
    style D fill:#c8e6c9

图解：进化历程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
┌─────────────────────────────────────────────────────────────────┐
│                    从代换到闭包：解释器的进化                      │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Step 1: 纯代换              Step 2: 环境                       │
│  ──────────────              ────────────────                   │
│                                                                 │
│  ((λ(x) (+ x 1)) 5)          env = {x: box(5)}                 │
│  → (+ 5 1)                   x 变成盒子                          │
│  → 6                                                           │
│                                                                 │
│  ❌ 不支持闭包              ❌ 不支持闭包                         │
│                                                                 │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Step 3: 闭包（本文）                                                │
│  ─────────────────                                                │
│                                                                 │
│  closV {                                     ┌─────────────────┐│
│    args: [y],                               │ 捕获的环境       ││
│    body: (+ x y),     ──────────────────►   │ {x: box(10),    ││
│    env: {x: box(10)}                       │    y: box(5)}   ││
│  }                                          └─────────────────┘│
│                                                                 │
│  ✅ 支持闭包 ✅ 支持赋值                                          │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

从环境到闭包：完整进化

Step 1：纯代换（不可变）

1
2
3
4
5
6
7
;; 简单的代换解释器
(define (interp-subst [e : ExprC] [env : Env]) : Value
  ;; ...
  [appC (fun args)
        (let ([f (interp-subst fun env)])
          (interp-subst (lam-body f)
                        (substitute* (lam-args f) args env)))])

局限性：不支持赋值，不支持闭包。

Step 2：环境 + 可变量

1
2
3
4
;; 使用盒子存储变量值
(define (interp-box [e : ExprC] [env : Env]) : Value
  ;; ...
  [idC (s) (unboxV (lookup s env))])

进步：支持赋值，但闭包仍需处理环境捕获。

Step 3：闭包

1
2
3
4
5
6
7
8
9
;; 完整的闭包实现
[lamC (args body) (closV args body env)]
[appC (fun args)
      (let ([f (interp fun env)])
        (interp (clos-body f)
                (extend-env*
                 (map bind (clos-args f)
                      (map boxV (map (λ (a) (interp a env)) args)))
                 (clos-env f))))]

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#lang typed-plai

;; ===========================================
;; 类型定义
;; ===========================================

(define-type Value
  [numV (n : number)]
  [closV (args : (listof symbol))
         (body : ExprC)
         (env : Env)]
  [boxV (val : Value)])

(define-type Binding
  [bind (name : symbol) (box : Value)])

(define-type-alias Env (listof Binding))

(define-type ExprC
  [numC (n : number)]
  [idC (s : symbol)]
  [appC (fun : ExprC) (args : (listof ExprC))]
  [lamC (args : (listof symbol)) (body : ExprC)]
  [boxC (val : ExprC)]
  [unboxC (box : ExprC)]
  [setboxC (box : ExprC) (val : ExprC)]
  [seqC (e1 : ExprC) (e2 : ExprC)]
  [plusC (l : ExprC) (r : ExprC)]
  [multC (l : ExprC) (r : ExprC)])

;; ===========================================
;; 环境操作
;; ===========================================

(define mt-env empty)

(define (extend-env [b : Binding] [env : Env]) : Env
  (cons b env))

(define (extend-env* [bs : (listof Binding)] [env : Env]) : Env
  (append bs env))

(define (lookup [for : symbol] [env : Env]) : Value
  (cond
    [(empty? env) (error 'lookup "name not found: ~a" for)]
    [else
     (if (symbol=? for (bind-name (first env)))
         (bind-box (first env))
         (lookup for (rest env)))]))

;; ===========================================
;; 解释器
;; ===========================================

(define (interp [e : ExprC] [env : Env]) : Value
  (type-case ExprC e
    [numC (n) (numV n)]
    [idC (s) (unboxV (lookup s env))]
    [lamC (args body) (closV args body env)]
    [appC (fun args)
          (local
            [(define fun-val (interp fun env))
             (define arg-vals (map (λ (a) (interp a env)) args))]
            (type-case Value fun-val
              [closV (f-args f-body f-env)
                     (interp f-body
                             (extend-env*
                              (map bind f-args (map boxV arg-vals))
                              f-env))]
              [else (error 'interp "not a function")]))]
    [boxC (val) (boxV (interp val env))]
    [unboxC (box) (unboxV (interp box env))]
    [setboxC (box val)
             (local [(define b (interp box env))]
               (set-boxV! b (interp val env))
               b)]
    [seqC (e1 e2)
          (begin
            (interp e1 env)
            (interp e2 env))]
    [plusC (l r) (num+ (interp l env) (interp r env))]
    [multC (l r) (num* (interp l env) (interp r env))]))

;; ===========================================
;; 辅助函数
;; ===========================================

(define (num+ [l : Value] [r : Value]) : Value
  (type-case Value l
    [numV (n) (type-case Value r
                [numV (m) (numV (+ n m))]
                [else (error 'num+ "not a number")])]
    [else (error 'num+ "not a number")]))

(define (num* [l : Value] [r : Value]) : Value
  (type-case Value l
    [numV (n) (type-case Value r
                [numV (m) (numV (* n m))]
                [else (error 'num* "not a number")])]
    [else (error 'num* "not a number")]))

总结

核心概念

概念 说明
BoxC 将值包装为可修改的容器
闭包 函数 + 捕获的环境
环境链 支持词法作用域的变量查找

下一步

  • 添加 if 条件表达式
  • 支持递归函数
  • 实现垃圾回收

系列文章

本系列文章从零实现一个完整的解释器：

  1. 0x06 - 环境实现 - 从代换到环境
  2. 0x07 - 闭包与可变量（本文）- 支持赋值和闭包

计划持续更新…