解释器：环境与变量查找
本节阅读量:
第一章的解释器只需要递归求值：
1
2
|
Int(n) -> n
Add(a, b) -> eval(a) + eval(b)
|
第二章加入变量后，解释器不能只看当前节点。遇到 Var(x) 时，它还要知道：
这份“当前可见绑定”的集合叫 environment，环境。
环境是什么
本章的环境可以先理解成一张从变量名到整数值的表：
代码在：
1
|
code/02_let/src/interp/interpreter.cpp
|
环境类型写成：
1
|
using Env = std::vector<std::pair<std::string, long>>;
|
也就是一串绑定：
这里没有用 std::unordered_map，是因为同名遮蔽（shadowing）需要保留同名绑定的先后顺序。
lookup 从后往前找
变量引用的求值规则是：
1
|
eval(Var(name), env) = lookup(env, name)
|
对应代码：
1
2
3
4
5
6
7
8
|
long lookup(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);
}
|
重点是从后往前找。
如果环境是：
后面的 x -> 32 更近，所以 lookup(x) 应该得到 32。这就是同名遮蔽的基础。
如果一路没找到，就说明变量没有绑定：
eval_expr 多了环境参数
第一章的 eval 只接收一个 Expr。第二章内部多了一个辅助函数：
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
|
long eval_expr(const Expr& expr, Env& env) {
switch (expr.kind) {
case ExprKind::integer: {
const auto& int_expr = static_cast<const IntExpr&>(expr);
return int_expr.value;
}
case ExprKind::add: {
const auto& add_expr = static_cast<const AddExpr&>(expr);
return eval_expr(*add_expr.lhs, env) + eval_expr(*add_expr.rhs, env);
}
case ExprKind::variable: {
const auto& var_expr = static_cast<const VarExpr&>(expr);
return lookup(env, var_expr.name);
}
case ExprKind::let: {
const auto& let_expr = static_cast<const LetExpr&>(expr);
long value = eval_expr(*let_expr.value, env);
env.push_back({let_expr.name, value});
long result = eval_expr(*let_expr.body, env);
env.pop_back();
return result;
}
}
throw std::runtime_error("unknown expression kind");
}
|
这里仍然沿用第一章的 kind + switch 风格。每一种表达式都有明确分支。
变量引用怎样求值
完整函数里的变量分支只做两件事：
1
2
|
1. 从 VarExpr 里拿出变量名。
2. 调用 lookup，在当前环境里查它的值。
|
VarExpr 本身不保存值。解释器每次遇到变量引用，都要根据当前环境重新查找，所以同一个名字在不同作用域里可以得到不同结果。
let 的求值顺序
let 的规则是：
1
2
3
4
5
6
|
eval((let x value body), env):
v = eval(value, env)
把 x -> v 放进 env
result = eval(body, env)
弹出 x -> v
return result
|
对照前面的完整 eval_expr()，这里有两个要点。
第一，value 在旧环境里求值：
1
|
long value = eval_expr(*let_expr.value, env);
|
这时新绑定还没有放进环境。
第二，body 求完以后要 pop_back()：
这表示离开这个 let 的作用范围。内层绑定不应该继续影响外层。
一个完整例子
程序：
求值过程：
1
2
3
4
5
6
7
8
|
eval value: 40 -> 40
push x -> 40
eval body: (+ x 2)
eval x -> lookup x -> 40
eval 2 -> 2
40 + 2 -> 42
pop x -> 40
return 42
|
运行：
1
2
3
|
cd code/02_let
make
./mini run examples/let.lang
|
输出：
同名遮蔽怎样求值
再看一个有两个同名绑定的程序：
1
|
(let x 10 (+ (let x 32 x) x))
|
求值过程是：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
eval 外层 value: 10 -> 10
push x -> 10
eval 外层 body: (+ (let x 32 x) x)
eval 左边: (let x 32 x)
eval 内层 value: 32 -> 32
push x -> 32
eval 内层 body: x
lookup 从后往前找到 x -> 32
pop x -> 32
左边结果是 32
eval 右边: x
lookup 找到外层 x -> 10
32 + 10 -> 42
pop x -> 10
return 42
|
内层绑定存在时，环境里暂时有两个 x：
lookup 从后往前找，所以内层 body 得到 32。离开内层 let 后，pop_back() 移除 x -> 32，外层的 x -> 10 又重新可见。
运行：
1
|
./mini run examples/shadow.lang
|
输出：
对外的 eval
对外接口仍然保持简单：
1
2
3
4
|
long eval(const Expr& expr) {
Env env;
return eval_expr(expr, env);
}
|
调用者不需要自己准备环境。完整程序开始求值时，环境是空的。
所以直接运行未绑定变量：
会在 lookup 里报错。这是正确行为：变量名只有进入某个 let 的 body 后才有值。
2.3 Parser：读出 identifier 和 let
上一节
