Crafting Interpreters 选读：树遍历（jlox）与字节码 VM（clox）两种实现对照（主题精读） 未开始

题记与说明

• 日期：2026-11-05
• 形式：主题研究（先检索并精读 6 个来源，再综合对照）
• 本次阅读的来源（均为在线精读原文，检索方式见文末附注）：
  1. A Map of the Territory — Crafting Interpreters Ch.2（实现策略全景图：树遍历/字节码/JIT/转译器在"登山图"上的位置）
  2. Evaluating Expressions — Crafting Interpreters Ch.7（jlox 树遍历求值的完整机制）
  3. Chunks of Bytecode — Crafting Interpreters Ch.14（jlox→clox 的过渡章：为什么放弃走树）
  4. Local Variables — Crafting Interpreters Ch.22（clox 把变量解析挪进编译期的槽位机制）
  5. Optimization — Crafting Interpreters Ch.30（profiler 实测数据与两项优化）
  6. Review of Crafting Interpreters — tinycomputers.io（第三方书评：双实现教学法与书级局限）
• 辅助检索：WebSearch（关键词 jlox vs clox performance），用于交叉确认量级表述；未直接读到原书页面的数字均已标注为二手。
• 检索失败记录：langdev.stackexchange Q&A（WebFetch 403、web_reader 网络错误）与 StackPrinter 镜像（连接超时）未能读取；Ch.30 的 web_reader 首次调用报 500 后改用 WebFetch 成功。

0. TL;DR

《Crafting Interpreters》用同一门语言 Lox 写了两遍完整实现：jlox（Java，把代码表示成 AST，递归 Visitor 走树求值）和 clox（C，把代码编译成线性字节码，用栈式 VM 的 switch 循环执行）。书的真正论点是：决定解释器性能的不是优化技巧，而是"代码在内存里长什么样"。AST 是散布堆上的对象图，走树 = 不断追逐指针、浪费缓存；字节码是紧凑线性数组，天然缓存友好，且编译期就能把变量解析、名字查找这些工作做完。作者的判词很直白：树遍历"简单、可移植、慢"，对通用命令式语言 "it won't fly"，执行模型本身就是错的——"你没法把一辆 AMC Gremlin 打磨成 SR-71 黑鸟"。基准是 fib(40)：jlox 约 72 秒，等效 C 程序 0.5 秒。第三方书评称这种"故意写两遍"的做法给了读者"立体镜式的视角"——树遍历让语义可触摸，字节码 VM 揭示生产级实现的工程取舍。

1. 核心问题

这组材料共同回答的问题是：同一种语言语义，为什么"直接解释语法树"和"编译成字节码再模拟执行"会有数量级的性能差距？差距的每一分钱花在哪里？又各自付出了什么代价？ 拆开是四个子问题：

1. 谱系定位：树遍历解释器、字节码 VM、原生编译、JIT 在实现策略的光谱上各占什么位置？"解释器"和"编译器"到底是不是互斥概念？
2. 树遍历的实现机制：jlox 如何用 Visitor 模式在 AST 上递归求值？它简单在哪里、慢在哪里（指针、装箱、虚分派、缓存）？
3. 字节码的折中逻辑：为什么选字节码而不是直接编译到机器码？字节码到底"是"什么？
4. 关键机制对照：变量解析、作用域、动态类型值表示、运行时错误展开，两种实现各怎么做？性能证据是什么？

2. 主要主张

2.1 谱系：树遍历是"学生的和玩具语言的"，字节码是主流动态语言的路

• Ch.2 对树遍历解释器的定义与判词：

"Some programming languages begin executing code right after parsing it to an AST (with maybe a bit of static analysis applied). To run the program, the interpreter traverses the syntax tree one branch and leaf at a time, evaluating each node as it goes. ... This implementation style is common for student projects and little languages, but is not widely used for general-purpose languages since it tends to be slow."（Ch.2 §2.2.2）

• 字节码的来源与命名：从 Wirth 的 p-code 而来，"today, we generally call it bytecode because each instruction is often a single byte long"（Ch.2 §2.1.6）；p-code 的 "p" 是 portable 而非 Pascal。
• VM 的本质代价与回报：

"Running bytecode in a VM is slower than translating it to native code ahead of time because every instruction must be simulated at runtime each time it executes. In return, you get simplicity and portability."（Ch.2 §2.1.7）

• 概念正名（对写作和面试都有用）：编译与解释不是二选一。老版 Matz Ruby 是纯树遍历解释器；CPython "is an interpreter, and it *has* a compiler"——用户视角从源码运行所以是解释器，内部确实编译到字节码。本书第二个解释器（clox）就住在这个交集里（Ch.2 §2.3）。

2.2 树遍历（jlox）：最短路径，"让每个节点自己求值"

• Ch.7 开篇明确路线："For our first interpreter, though, we are going to take the simplest, shortest path and execute the syntax tree itself."
• 组织方式刻意选了 Visitor 模式而非 GoF 的解释器模式："we could tell each syntax tree node, 'Interpret thyself'. This is the Gang of Four's Interpreter design pattern. It's a neat pattern, but ... it gets messy if we jam all sorts of logic into the tree classes."（Ch.7 §7.2）
• 求值顺序是后序遍历："our interpreter is doing a __post-order traversal__—each node evaluates its children before doing its own work."（Ch.7 §7.2.3）
• 动态类型的本质在 jlox 里被压缩成一句话——运行时 cast：

"This type cast happens at runtime when the - is evaluated. That's the core of what makes a language dynamically typed right there."（Ch.7 §7.2.3）

• 值表示完全托管给 JVM：所有 Lox 值 = Java Object（nil→null、Boolean→Boolean、number→Double、string→String），靠 instanceof + 强转做动态检查（Ch.7 §7.1）。
• 运行时错误的展开方式暴露了树遍历的结构：递归调用栈 = 求值状态，"Throwing an exception in Java is a fine way to accomplish that"（Ch.7 §7.3.1）——后面会看到 clox 连异常都不用，控制流全在字节码里。

2.3 为什么放弃走树：三条硬伤（Ch.14 的完整论证）

Ch.14 是全书对照的枢纽，作者先承认树遍历的两个真实优点（"this style of interpreter is *really simple* to implement. The runtime representation of the code directly maps to the syntax"；以及可移植），再逐条拆解：

1. 总判词：

"An even more fundamental reason that jlox isn't sufficient is that it's too damn slow. A tree-walk interpreter is fine for some kinds of high-level, declarative languages. But for a general-purpose, imperative language—even a 'scripting' language like Lox—it won't fly."（Ch.14 开篇）

1. 微优化救不了错误的执行模型：

"We could take jlox and run it in a profiler and start tuning and tweaking hotspots, but that will only get us so far. The execution model—walking the AST—is fundamentally the wrong design. We can't micro-optimize that to the performance we want any more than you can polish an AMC Gremlin into an SR-71 Blackbird."（Ch.14 开篇）

1. 内存与缓存的定量论证：1 + 2 这样一个表达式会展开成一串 Java 对象，每个指针"adds an extra 32 or 64 bits of overhead"，对象头还要占记账空间；而"Those sub-objects could be *anywhere*. Every step the tree-walker takes where it follows a reference to a child node may step outside the bounds of the cache and force the CPU to stall"——缓存命中与走 RAM 的差距是"upwards of 100 *times* faster"（Ch.14 §14.1.1）。即使解析时对象恰好连续分配，几轮 GC 搬移之后也无从保证。
2. 分派开销："Our AST walker has other overhead too around interface dispatch and the Visitor pattern, but the locality issues alone are enough to justify a better code representation."（Ch.14 §14.1.1）
3. 为什么不是原生编译：机器码快，但"compiling to native code ain't easy"——寄存器分配、流水线、指令调度，且可移植性直接归零；LLVM 可以缓解但引入重型依赖（Ch.14 §14.1.2）。
4. 字节码 = 折中点的正式定义：

"On one end, a tree-walk interpreter is simple, portable, and slow. On the other, native code is complex and platform-specific but fast. Bytecode sits in the middle. It retains the portability of a tree-walker ... It sacrifices *some* simplicity to get a performance boost in return, though not as fast as going fully native."（Ch.14 §14.1.3）

设计观一句话："It's an idealized fantasy instruction set that makes your life as the compiler writer easier."——为"最容易实现的架构"设计指令集，再用软件模拟（VM）执行它。

1. 师承关系："We'll follow in the footsteps of the main implementations of Python, Ruby, Lua, OCaml, Erlang, and others."（Ch.14 §14.1.3）

2.4 字节码的表示革命：AST 类家族 → 三个数组

• 全书最精炼的一组对照（Ch.14 §14.6 结尾）：

"Remember that whole family of AST classes we defined in jlox? In clox, we've reduced that down to three arrays: bytes of code, constant values, and line information for debugging. ... You can think of bytecode as a sort of compact serialization of the AST, highly optimized for how the interpreter will deserialize it in the order it needs as it executes."

• 行号信息刻意放在平行数组而非指令流里："Since line information is only used when a runtime error occurs, we don't want it between the instructions, taking up precious space in the CPU cache and causing more cache misses."（Ch.14 §14.6）——为热路径让出缓存，这是全书内存观的一个缩影。
• jlox 的 AstPrinter ↔ clox 的 disassembler：两种实现各自配了"观察自己内部表示"的工具（Ch.14 §14.4）。

2.5 关键机制对照：把"查找"从运行时搬进编译期

Ch.22 给出两种实现最典型的一对差异——词法作用域的实现：

• jlox："In jlox, we used a linked chain of 'environment' HashMaps to track which local variables were currently in scope."——作者称之为 "the classic, schoolbook way of representing lexical scope"；每进一个块就"allocated an entire new HashMap for each one"（Ch.22 §22.3/22.5）。
• clox：编译器持有与运行时栈同构的 locals 数组，"the locals array in the compiler has the exact same layout as the VM's stack will have at runtime. The variable's index in the locals array is the same as its stack slot"；编译期 resolveLocal() 从后向前扫找槽位，找不到才按全局处理（Ch.22 §22.3）。
• 收益的表述：

"Accessing a variable from a known stack slot is an indexed array lookup." / "Allocating space for a new local requires only incrementing the stackTop pointer, and freeing is likewise a decrement."（Ch.22）

• 方法论金句（放之四海皆准）：

"Any processing work we do in the compiler is work we don't have to do at runtime."（Ch.22）

• 代价也要如实记：槽位操作数只有一个字节 → 最多 256 个局部变量（Ch.22）；局部变量的名字根本不进字节码——"The local variable's name never leaves the compiler to make it into the chunk at all."

2.6 第三方视角：双实现是"立体镜"，但书也有边界

tinycomputers.io 书评（第三方，非作者自述）：

• 教学法评价："The tree-walk interpreter makes the abstract concepts tangible; the bytecode VM reveals the performance and engineering considerations that production language implementations face."——两者合起来是 "a stereoscopic view of language implementation that neither could achieve alone"。
• 也点出读者须在 clox 部分"implement all of these from scratch"（动态数组、哈希表、mark-sweep GC），Pratt 解析一章已成引用经典，GC 一章是"全书系统编程深度的顶峰"。
• 总评："It will not make you a compiler engineer, but it will demystify the machinery that powers every programming language you have ever used."

3. 方法：两种实现的技术路线逐维对照

书的方法本身就是"控制变量"：同一门语言 Lox、同一种语法（Pratt/递归下降）、同一组特性逐章对应实现两遍，差异被隔离在"代码的中间表示 + 执行循环"上。阶段图（Ch.14 图注原文）："jlox is Parser to Syntax Trees to Interpreter. clox is Compiler to Bytecode to Virtual Machine." clox 在 Pratt 解析的同时直接产出字节码、不构建 AST，正符合 Ch.2 §2.2.1 所述 single-pass compiler 的特征（"produce output code directly in the parser, without ever allocating any syntax trees"）。

方法论要点：jlox 章节把精力花在语义（闭包、类、继承的语义设计），clox 章节把精力花在表示与工程（值编码、内存布局、GC、哈希表）——两部分的分工本身就是一种学习路径设计。

4. 数据与证据

1. 基准锚点（Ch.14 原文）：递归 fib(40)，"On my laptop, that takes jlox about 72 seconds to execute. An equivalent C program finishes in half a second." 作者设定的工程目标："we don't need to settle for more than *two orders of magnitude* slower"（与 C 比）。
2. 量级交叉确认：WebSearch 检索摘要将书中结论概括为 clox 比 jlox 快"约一个数量级（~10×）"（并援引 tinycomputers 书评称 clox 靠架构而非高级优化取胜）。注：该"10×"为二手概括，本次未能在原书页面直接核对到这一具体倍数；可直接核对的是上面 72s vs 0.5s（jlox vs C）与 Ch.30 的相对数字。
3. Ch.30 profiler 实测（WebFetch 提取）：优化前热点画像——OP_INVOKE 42%、OP_GET_GLOBAL 17%、OP_GET_PROPERTY 12%，tableGet() 占执行时间 "a whole 72% ... (inclusive)"；VM 总时间的 70% 花在 findEntry() 里取模那一行。硬件事实："division and modulo are about 30-50 times slower than addition and subtraction on x86."
4. 优化收益（Ch.30）：把 hash % capacity 换成位掩码 hash & (capacity-1)（容量恒为 2 的幂）后，十秒内跑完的批次数从 3,192 提升到"almost exactly twice as much work ... We made the VM twice as fast (usual caveat: on this benchmark)"；tableGet() 占比从 72% 降到 35%。NaN boxing 把 Value 从 16 字节压到 8 字节后："the new value representation seems to make everything roughly 10% faster across the board."
5. 证据充分性评估：fib(40) 微基准 + profiler 百分比足以支撑"执行模型/表示决定量级差距"的主张（这正是作者论证所用的证据）；但全部数字来自作者单机、单基准，作者自己也反复标注 "on this benchmark"；第三方书评属于定性佐证。没有多基准、多机器的独立复现，这是证据面的主要缺口。

5. 结论

1. 树遍历解释器是"语义学习器"和原型工具的正确形态：简单、直接映射语法、宿主语言兜底内存与错误处理；但它在内存布局（散布堆上的对象图）、缓存局部性（指针追逐）、分派开销（虚方法）三处结构性失血，且这些都不是微调能救的。
2. 字节码 VM 的胜利来自表示的更换，而非优化叠加：AST 类家族压缩成三个数组；变量解析从运行时 HashMap 链前移到编译期栈槽；名字根本不进运行时。"编译器里做的每件事都是运行时不用做的"是整条路线的纲领。
3. 这条路线是主流动态语言的实际历史：CPython/Ruby(旧版树遍历→后改字节码)/Lua/OCaml/Erlang 的主要实现都编译到字节码；"解释器"与"编译器"是可叠加的属性而非对立选项。
4. 双实现教学法有效：先写慢而清晰的 jlox 把语义跑通，再写快而工程化的 clox 对照理解"为什么"——第三方书评的"立体镜"比喻成立。

6. 局限

作者承认/书中自带的：

• Ch.30 全书只做了两项优化（哈希探测位掩码、NaN boxing），且收益附 "usual caveat: on this benchmark"；"we didn't know that the modulo operator was a performance drain until our profiler told us so"——作者明确说这只是示例，不是优化教程。
• 行号编码是"embarrassingly inefficient with memory"的占位实现（每字节一个 int），RLE 压缩留作课后挑战。
• Ch.14 的挑战题自认 OP_CONSTANT 单字节操作数限制（256 个常量）在真实代码里会撞上，多尺寸指令的取舍留作练习。

第三方指出的书级局限（tinycomputers 书评）：

• 无静态类型系统："static type systems (one of the most active and important areas of modern language design) receive no coverage"——读完仍不会写类型检查器。
• 无经典编译优化 pass："does not cover constant folding, dead code elimination, register allocation, or any of the optimization passes"；JIT 只在 Ch.2 一笔带过，全书不写。
• 错误处理与恢复极简；数组、迭代器、模块、模式匹配、异常处理等留作练习，"the gap between Lox and a practical language is significant"。

我（精读者）补充的局限：

• 对照只覆盖作者自己写的两种实现；树遍历→字节码之外的路线（AOT、JIT、trace compiling）只有 Ch.2 的地图级介绍。
• 书中性能数字是 2015–2021 年代硬件/特定 JVM 的单点测量，今天复测的绝对值会变，但表示层面的论证不受影响。
• "clox 比 jlox 快约 10×"这一说法我只从检索摘要与书评获得，未能直接核对原书页面（见 §4.2 的标注）；langdev.stackexchange 的正反方讨论因 403/超时未能纳入。

7. 对我的启发

1. "表示决定速度"优先于"算法决定速度"：jlox 与 clox 算的是同一棵"表达式"，差距全部来自内存里的表示（对象图 vs 线性字节）与缓存行为。做任何性能敏感系统（DSL、序列化、渲染、数据处理管线）时，第一步应该审视数据布局是否对硬件友好，而不是先找热点微调。
2. "编译器是最大的优化锤"：能在编译期完成的解析、绑定、常量计算，绝不留到运行时。这个原则可以平移到提示词模板编译、正则预编译、shader 编译、配置校验前移——凡是"同一份静态描述被反复执行"的场景。
3. 先写两遍，再谈取舍：jlox→clox 的路径是可复用的学习法——先实现"慢而正确"的参照版本锁定语义，再实现"快而工程化"的版本，用同一套端到端测试（作者先写测试套件再写书，Ch.14 Design Note）保证两者行为一致。迁移/重写架构前先固化行为测试，这条纪律比任何实现技巧都值钱。
4. Profiler 是唯一的热点来源：直觉热点（全局变量查询）不是最大头（OP_INVOKE 42%）；取模运算 30–50× 于加减这种"常识"只有被 profiler 指着才值得动手。优化前先测，优化后复测验证。
5. 写作素材：文中"AMC Gremlin → SR-71"、" Interpreter, and it has a compiler"、"compact serialization of the AST" 都是可直接复用的讲解范式——用具体比喻把抽象权衡讲到位，这正是本书写作上最值得学的一点。

附注：本次检索与阅读方式

• 来源 1–3、6 由 web_reader 抓取全文精读；来源 5（Ch.30）web_reader 报 500 后经 WebFetch 以定向提问方式提取（引文为该工具返回的原文摘录）；来源 4（Ch.22）经 WebFetch 定向提取。
• WebSearch（jlox vs clox performance）提供交叉佐证，其中"约一个数量级"的表述已在 §4.2 标注为未直接核对的二手信息。
• 未能读取：langdev.stackexchange.com Q1607（WebFetch 403；web_reader 网络错误）、stackprinter.appspot.com 镜像（连接超时）。
• 原书免费在线全文：https://craftinginterpreters.com/（Robert Nystrom，© 2015–2021，纸质版由 Genever Benning 出版）。