树遍历解释器：让 AST 真正算出来

目标

有了 AST，下一步是执行它。本节课写一个"树遍历解释器（Tree-walking Interpreter）"：从根节点出发，递归访问每棵子树并算出值。这是解释型语言最朴素的执行方式。

运行环境：Node.js v18+。运行方式：保存为 interp.js，执行 node interp.js（复用 l2 的 parse）。

// interp.js —— 在 l2 的 parse 基础上增加求值
function evaluate(node, env) {
  switch (node.type) {
    case 'Number': return node.value
    case 'Ident': return env.get(node.name)
    case 'Unary': return -evaluate(node.operand, env)
    case 'Binary': {
      const a = evaluate(node.left, env)
      const b = evaluate(node.right, env)
      switch (node.op) {
        case '+': return a + b
        case '-': return a - b
        case '*': return a * b
        case '/': return a / b
      }
    }
    default: throw new Error('未知节点: ' + node.type)
  }
}

// 一个极简环境（l4 会升级成支持作用域）
const env = { get: (name) => { throw new Error('变量 ' + name + ' 在第4节才支持') } }

// ===== 调用示例 =====
const ast = parse('1 + 2 * 3')
console.log('结果 =', evaluate(ast, env)) // 7

evaluate 本身就是 AST 的"镜像"：树长什么样，求值函数就长什么样。这种"结构对结构"的映射，是解释器最易读的形态。

名词解释

Tree-walking Interpreter（树遍历解释器）：不把代码翻译成别的形式，而是直接遍历 AST、边走边算。优点是实现简单、易调试；缺点是慢（每步都要递归进树）。
求值 / 解释（evaluate）：给一个 AST 节点算出它的值。evaluate 通常是递归的，因为节点可以嵌套节点。
常用思路：用 switch (node.type) 分发到不同处理逻辑；遇到组合节点（如 Binary）就先递归求子节点、再运算。

课后练习

练习：当前 Binary 只支持四则运算。增加对字符串拼接的支持：当 op 为 + 且任一操作数是字符串时，返回拼接结果。

答案：

function evaluate(node, env) {
  if (node.type === 'Binary') {
    const a = evaluate(node.left, env)
    const b = evaluate(node.right, env)
    if (node.op === '+' && (typeof a === 'string' || typeof b === 'string')) return String(a) + String(b)
    switch (node.op) {
      case '+': return a + b
      case '-': return a - b
      case '*': return a * b
      case '/': return a / b
    }
  }
  if (node.type === 'Number') return node.value
  return 0
}
console.log(evaluate({ type: 'Binary', op: '+', left: { type: 'Number', value: 1 }, right: { type: 'Number', value: 2 } }, {}))

总结

树遍历解释器是"让语言跑起来"的最短路径。它没有编译、没有字节码、没有虚拟机，只是忠实地把语法树走一遍。你会在 Python、Ruby 的早期实现里看到它的影子。它的慢不是缺点而是特点：在语言设计早期，能"立刻跑"比"跑得快"重要得多——你改一行语义，立刻就能验证。等语言定型、性能成为瓶颈，再考虑编译成字节码（第12节会亲手做）。理解树遍历，你就理解了"解释"二字的本质：执行就是遍历。