解释器：Environment 找位置，Store 保存值

本节阅读量:

表面语言已经规定：外层代码和 closure 可以读写同一个词法绑定。解释器要做的核心改动，是不再让环境直接保存 Value。

第七章的模型可以概括为：

1

Env: name -> Value

创建 closure 时复制自由变量的 Value，对不可变绑定完全够用。有了 set!，若外层环境和 closure 各自保存一份 Value，修改其中一份不会自动更新另一份。

第八章把职责拆成：

1
2


Environment: name -> Location
Store:       Location -> Value

Environment 回答“这个名字是哪一个绑定”；Store 回答“这个绑定现在保存什么”。所有共享同一 Location 的环境，都能看到 Store 中的最新 Value。

Location 在解释器里只是稳定编号

当前代码定义：

1
2


using Location = std::size_t;
using Env = std::vector<std::pair<std::string, Location>>;

Location 是 Store 向量的索引，例如 0、1、2。它不是源语言整数 Value，也不是编译器生成代码中的机器地址。

选择索引有一个实际好处：std::vector 扩容时可能搬动内部元素，但已有元素的编号不变。只要解释器始终通过 Store 访问，closure 保存的 Location 就不会因为向量重新分配而失效。

Store 集中管理分配、读取和写入

当前实现是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


struct Store {
    Location allocate(Value value) {
        values.push_back(std::move(value));
        return values.size() - 1;
    }

    Value read(Location location) const {
        return values.at(location);
    }

    void write(Location location, Value value) {
        values.at(location) = std::move(value);
    }

    std::vector<Value> values;
};

三种操作的边界很清楚：

操作	含义
`allocate(value)`	建立一个新位置，初始内容为 `value`
`read(location)`	取出该位置当前保存的 Value
`write(location, value)`	替换该位置中的 Value，不创建新位置

Store 在一次 eval 期间只有一份，并以引用传给所有递归求值：

1
2
3
4
5


Value eval(const Expr& expr) {
    Env env;
    Store store;
    return eval_expr(expr, env, store);
}

如果每次递归调用都复制 Store，closure 之间就无法共享修改。

名字查找只返回 Location

环境仍用反向查找实现词法遮蔽：

1
2
3
4
5
6
7
8
9


Location lookup_location(const Env& env,
                         const std::string& name) {
    for (auto it = env.rbegin(); it != env.rend(); ++it) {
        if (it->first == name) {
            return it->second;
        }
    }
    throw std::runtime_error("undefined variable: " + name);
}

较新的绑定追加在尾部，反向遍历会先找到它。注意函数返回的是 Location，不是 Value。

普通变量读取再走第二步：

1
2
3
4
5


Value lookup(const Env& env,
             const Store& store,
             const std::string& name) {
    return store.read(lookup_location(env, name));
}

所以 VarExpr(x) 的完整路径是：

1

x -> location -> current Value

本章让所有绑定都拥有 Location

理论上，编译器可以先分析哪些变量会被修改，只给它们装箱；其余变量仍直接保存 Value。但那会立刻带来两套表示：

1
2


不可变绑定  name -> Value
可变绑定    name -> Location -> Value

每个变量读取、closure 捕获和函数参数都要先判断自己属于哪一种。为了把教学重点放在共享状态，本章采用更统一的选择：

1
2
3


let 绑定       分配 Location
letrec 名字    分配 Location
每次调用参数   分配 Location

即使某个绑定从未出现在 set! 中，也使用同一条路径。代价是多分配一些位置；好处是解释器、IR 和汇编都只有一种变量模型。只装箱真正可变变量可以作为以后独立的优化，而不是本章语义的一部分。

let 先求右侧，再建立新位置

let 的作用域规则没有改变：右侧在旧环境中求值，绑定名只进入 body。

1
2
3
4
5
6
7
8
9


case ExprKind::let: {
    const auto& let = static_cast<const LetExpr&>(expr);
    Value value = eval_expr(*let.value, env, store);
    Location location = store.allocate(std::move(value));
    env.push_back({let.name, location});
    Value result = eval_expr(*let.body, env, store);
    env.pop_back();
    return result;
}

顺序是：

1
2
3
4
5


用旧 Env 求 value
为结果分配新 Location
把 name -> Location 加入 Env
求 body
移除本次环境绑定

例如：

1
2
3


(let x 40
  (let x x
    x))

内层 value 中的 x 仍读取外层 location；得到 40 后，才为内层 x 建立另一个 location。

set! 复用位置，不分配位置

解释器分支直接对应语言规则：

1
2
3
4
5
6
7


case ExprKind::set: {
    const auto& set = static_cast<const SetExpr&>(expr);
    Location location = lookup_location(env, set.name);
    Value value = eval_expr(*set.value, env, store);
    store.write(location, value);
    return value;
}

先解析已有 location，再求右侧，最后写回并返回右侧 Value。这里没有 store.allocate，因为 set! 不是新绑定。

右侧在写入前求值，所以：

1

(set! x (+ x 1))

会从同一个 location 读出旧值，计算完才覆盖它。如果右侧求值抛出错误，write 尚未发生。

begin 只负责顺序

begin 不创建环境，也不直接操作 Store：

1
2
3
4
5


case ExprKind::begin: {
    const auto& begin = static_cast<const BeginExpr&>(expr);
    (void)eval_expr(*begin.first, env, store);
    return eval_expr(*begin.second, env, store);
}

两个子表达式收到同一份 env 和同一份 store。因此 first 写入的状态会被 second 看见。

Closure 保存名字到 Location 的映射

解释器中的 closure 现在是：

1
2
3
4
5


struct Closure {
    std::string param;
    const Expr* body;
    Env env;
};

env 不再包含 Value，而是自由变量名字及其 Location。capture_environment 按自由变量的稳定顺序复制这些映射：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Env capture_environment(
    const Env& env,
    const std::vector<std::string>& names) {
    Env captures;
    captures.reserve(names.size());
    for (const auto& name : names) {
        captures.push_back({name, lookup_location(env, name)});
    }
    return captures;
}

这里复制 location 是正确的：Location 是同一个位置的编号。复制它不会复制 Store 中的 Value，也不会建立新位置。

求值 lambda 仍然不执行函数体

普通 lambda 分支是：

1
2
3
4
5
6
7
8
9


case ExprKind::lambda: {
    const auto& lambda = static_cast<const LambdaExpr&>(expr);
    auto closure = std::make_shared<Closure>();
    closure->param = lambda.param;
    closure->body = lambda.body.get();
    closure->env =
        capture_environment(env, free_vars(lambda));
    return Value::make_closure(std::move(closure));
}

它只做三件事：保存参数名、保存函数体 AST、保存自由变量 location。函数体要等调用时才执行。

与第七章相比，free_vars(lambda) 得到的源码名字没有变化；变化的是每个名字解析出的内容：

1
2


第七章  name -> captured Value
第八章  name -> captured Location

走一遍共享读取的例子

考虑：

1
2
3
4
5


(let x 40
  (let read (lambda ignored x)
    (begin
      (set! x 42)
      (read 0))))

假设 x 分配到 location 0：

1
2


Env     [x -> 0]
Store   [0 -> 40]

创建 read 时，它捕获：

1

[x -> 0]

不是整数 40。随后 set! 更新 Store：

1

Store   [0 -> 42]

调用 read 时，函数体通过捕获环境找到 location 0，再从同一 Store 读到 42。外层代码和 closure 不需要互相通知；共享 location 已经把它们连接起来。

运行验证：

1
2


cd code/08_state
./mini run examples/captured_read_after_set.lang

输出：

1

42

调用为参数分配新的 Location

call 分支先保持第七章已经确定的错误与求值顺序：先求 callee 并检查种类，再求 argument。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


case ExprKind::call: {
    const auto& call = static_cast<const CallExpr&>(expr);
    Value callee = eval_expr(*call.callee, env, store);
    if (callee.kind != Value::Kind::closure) {
        throw std::runtime_error(
            "function call expected a function");
    }
    Value argument = eval_expr(*call.argument, env, store);
    Env call_env = callee.closure_value->env;
    Location parameter = store.allocate(std::move(argument));
    call_env.push_back(
        {callee.closure_value->param, parameter});
    return eval_expr(
        *callee.closure_value->body, call_env, store);
}

参数不能直接把 Value 塞进环境，因为函数体可能执行 (set! param ...)，内层 closure 也可能捕获参数。每次调用都执行一次 store.allocate，所以每次 activation 都有独立参数 location。

参数绑定最后加入 call_env，这还保留了词法遮蔽：若 letrec 的 self 名与参数同名，反向查找会先找到参数 location。

为什么 factory 的两次调用不会串状态

independent_counters.lang 两次调用 make。第一次为 start 分配一个 location，第二次必须再分配另一个：

1
2


第一次 make  call_env: start -> location A
第二次 make  call_env: start -> location B

各自返回的内层 closure 捕获 A 或 B。只有来自同一次调用的代码共享对应位置，两次 counter 不会因为参数源码都叫 start 就合并状态。

1

./mini run examples/independent_counters.lang

输出 42。这个示例能直接抓出“把参数 location 缓存在函数对象中并重复使用”的错误实现。

letrec 先建立 self Location，再写入 closure

不可变闭包一章可以在调用时把实际 callee 临时绑定给 self。现在 letrec 名字允许被 set! 修改，函数体必须访问原始词法绑定的共享 location。

解释器采用四步构造：

1
2
3
4


分配 self location，先放占位值
创建 closure，把 self location 放在环境首项
把 closure Value 写回 self location
把函数名绑定到该 location，求 letrec body

对应代码是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


case ExprKind::letrec: {
    const auto& letrec = static_cast<const LetRecExpr&>(expr);
    Location self =
        store.allocate(Value::make_number(0));

    auto closure = std::make_shared<Closure>();
    closure->param = letrec.param;
    closure->body = letrec.function_body.get();
    closure->env.push_back({letrec.name, self});
    Env outer =
        capture_environment(env, free_vars(letrec));
    closure->env.insert(
        closure->env.end(), outer.begin(), outer.end());

    Value function = Value::make_closure(std::move(closure));
    store.write(self, function);
    env.push_back({letrec.name, self});
    Value result = eval_expr(*letrec.body, env, store);
    env.pop_back();
    return result;
}

占位值不会被函数体观察到：closure 构造完成后立即写回，随后才求值 letrec body。它的作用是先取得一个稳定 Location，使 closure 环境和外层 body 可以引用同一位置。

普通外层自由变量排在 self 后面，调用参数又在 call 时最后加入。函数体环境的遮蔽顺序因此是：

1
2
3


self location
外层自由变量 locations
本次参数 location

可变递归为何不能只保存实际 callee

在 recursive_binding_set.lang 中，old 保存旧 closure，随后 loop 的 location 被写入新 closure。调用 old 后，旧函数体中的递归引用仍应读取 loop 的共享 location，从而调用新 closure。

如果每次 call 只是临时建立：

1

loop -> actual callee

旧函数就会永远递归调用自己，看不见 set! loop。self location 不是多余的实现细节，而是可变词法绑定的直接结果。

运行：

1

./mini run examples/recursive_binding_set.lang

结果为 42。

Location 索引避免 shared_ptr 所有权环

一种看似直接的实现是：Environment 保存 shared_ptr<Value>，递归 closure 的环境再保存指向自身 Value 的 shared_ptr。这样会形成强引用环：

1

closure -> self Value -> closure

即使求值结束，引用计数也无法降到零。

当前实现中，Store 保存 closure Value，Closure 环境只保存整数 Location：

1
2


Store[self] -> closure
closure.env -> self 的整数索引

整数索引不拥有 Store 或 Value，因此不会形成 C++ shared_ptr ownership cycle。语义上仍然能够沿 Location 回到同一个绑定。

需要区分这和编译后对象图：机器堆上的 closure 确实捕获 tagged cell pointer，cell 又可能保存 closure，因而会形成真实的可达性环。那不是引用计数泄漏，而是下一章 tracing GC 要正确扫描和回收的对象图。

解释器 Location 与机器 cell 是两种实现

两条路线共享抽象关系：

1

name -> mutable place -> Value

但具体表示不同：

解释器	编译后的程序
`Location` 是 `std::size_t` 索引	location 是 tagged heap cell pointer
`Store::values[index]` 保存 Value	cell offset `8` 保存 tagged Value
closure 环境保存整数索引	closure capture 保存 tagged cell Value
C++ 向量负责存储	`malloc` 暂时负责分配对象

不要把解释器中的整数 Location 描述成机器地址，也不要在解释器中为了“看起来一样”手动做 pointer tagging。两种实现只需遵守同一语言语义。

原有 Value 边界保持不变

Store 中可以保存 number、closure 或 record，但源语言仍看不到“cell Value”。变量读取先 load 出 cell 内容，所以：

record? 判断读出的 Value 是否为 record；
size 和 get 继续检查 record 种类与边界；
call 继续要求读出的 Value 是 closure；
eq? 仍拒绝函数值，record 继续按对象身份比较。

加入状态不应悄悄改变第六、七章已经确定的 Value 语义。

求值顺序现在能够被程序观察

没有副作用时，很多子表达式交换顺序仍可能得到同一个整数。有了 Store，既有规则变得可观察：

let 先求 value，再分配并加入新绑定；
+ 先求左 operand，再求右 operand；
record 字段从左到右求值；
call 先求并检查 callee，再求 argument；
if 只求被选中的分支；
begin 明确先 first、后 second。

解释器在相应 switch 分支中保持这个顺序，IR lowering 和汇编也必须一致。状态并没有新发明这些顺序，只是让错误顺序不再容易隐藏。

本节的检查点

解释器完成后，应能说明并验证：

Environment 为什么只保存 name -> Location；
Store 为什么在整次求值中共享，而不是逐次复制；
let 为什么先求右侧，再分配 location；
set! 为什么写回旧 location 并返回 RHS Value；
closure 为什么捕获自由变量 location，而不是当前 Value；
每次调用为什么必须分配新的参数 location；
letrec 为什么先分配 self location，再把 closure 写回；
整数 Location 为什么不会形成 shared_ptr ownership cycle；
解释器 Location 与编译器堆 cell 为什么是同一抽象的两种实现。

8.2 AST、parser 与自由变量：写入目标也是一次变量使用

8.4 结构化 IR：把值和位置分开

本节目录