第 14 章：字节码块（Chunks of Bytecode）

原文：Robert Nystrom, Crafting Interpreters, Chapter 14。原书以 CC BY-NC-SA 4.0 协议发布；本译文用于学习与研究。

如果你发现自己几乎把所有时间都花在理论上，就该多关注一些实践；这会改进你的理论。若你发现自己几乎把所有时间都花在实践上，就该多关注一些理论；这会改进你的实践。

Donald Knuth

我们已经用 jlox 完成了一套 Lox 实现，为什么本书还没有结束？部分原因是，jlox 依赖 JVM 替我们完成了许多工作。要把解释器一直理解到贴近硬件的层次，我们得亲手构建那些部件。

当然，第二个解释器仍依赖 C 标准库提供内存分配等基本能力，C 编译器也替我们屏蔽了所运行机器码的细节；机器码本身或许又是由芯片中的微码实现的，C 运行时还要向操作系统申请内存页。但若本书还能放进书架，我们总得在某处停下来。

更根本的原因是 jlox 实在太慢。树遍历解释器适合某些高级、声明式语言；但对 Lox 这样通用的命令式脚本语言来说，它不够用。考虑下面这个小程序：

fun fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

var before = clock();
print fib(40);
var after = clock();
print after - before;

这显然不是计算 Fibonacci 数的高效办法。这里要测的是解释器有多快，而不是程序写得多聪明；一个做了大量工作的慢程序，正好是测试用例。作者的笔记本上，jlox 约需 72 秒，而等价的 C 程序只需半秒。动态类型脚本语言不会与手工内存管理的静态类型语言一样快，但也没必要慢上两个数量级。

可以用性能分析器找出热点，再调优 jlox；但这只能走一段路。遍历 AST 的执行模型从根本上就不对，微优化无法把它打磨到目标性能。本章引入新的模型：字节码，并开始实现新解释器 clox。

14.1 字节码？（Bytecode?）

工程里的选择很少没有代价。为了理解为什么选择字节码，先把它与两个替代方案放在一起比较。

14.1.1 为什么不遍历 AST？（Why not walk the AST?）

现有解释器有两个实实在在的优点：

**实现简单。**运行时代码表示直接对应语法；从解析器到运行时数据结构几乎不费力。
**可移植。**现有实现用 Java 编写，可运行在 Java 支持的平台上。即使用 C 采用相同模型，也几乎能编译、运行在所有平台。

但它的内存效率很差。每一小段语法都会变成 AST 节点；1 + 2 这样短的表达式也会变成许多对象和指针：

表示 1 + 2 的 Java 对象树。

图中标为 (header) 的部分是 JVM 用于内存管理和保存对象类型的簿记信息，也占空间。每根指针又增加 32 或 64 位的开销；更糟的是，散落在堆上的对象网络会破坏空间局部性（spatial locality）。

现代 CPU 处理数据的速度远快于从 RAM 取数据的速度，所以芯片使用多层缓存。所需内存已在缓存中时，读取可能快两个数量级。CPU 从 RAM 读取一个字节时，通常会推测性地将相邻的一整块字节一起放进缓存；如果下次所需数据仍位于同一缓存行，执行就会很顺畅。因此，内存中代码的表示应当紧凑，并按读取顺序排列。

而 AST 的子对象可能在堆的任何地方。树遍历器每次跟随指针访问子节点，都可能跳出缓存并让 CPU 停顿，直到 RAM 中的新数据被取来。即使解析完成时对象恰好连续分配，几轮可能移动对象的垃圾收集之后，也无法知道它们在哪里。接口分派和 Visitor 模式也会产生开销；仅局部性问题就足以证明我们需要更好的代码表示。

14.1.2 为什么不编译为原生代码？（Why not compile to native code?）

若要真正高速，就要一路消除间接层，直接生成芯片支持的机器码。CPU 按顺序解码并执行这些致密的二进制指令；没有 AST 树，控制流也直接跳到代码的另一位置。这非常快，却有代价。

首先，原生代码生成不容易。当前广泛使用的芯片架构历经数十年累积，指令集庞杂，需要复杂的寄存器分配、流水线和指令调度。其次，可移植性会消失：精通一种架构只够支持一种指令集；要覆盖多个平台，就要为每一种编写独立后端。

好的编译器可在不同架构间共享前端和大部分中间层优化，主要为每个平台重写代码生成与部分指令选择。LLVM 也提供了这种分工：编译器输出 LLVM 的中间语言，再由 LLVM 编译到众多原生架构。

14.1.3 什么是字节码？（What is bytecode?）

树遍历解释器简单、可移植但慢；原生代码复杂、依赖平台但快。字节码位于中间：保留树遍历器的可移植性，牺牲一部分简单性来换取性能提升，虽然不会快到原生代码的程度。

结构上，字节码像机器码：它是紧凑、线性的二进制指令序列，开销低而且有利于缓存。但它的指令集比真实芯片简单、高层得多。许多字节码格式中，每条指令只有一个字节，因此得名 bytecode。

可以把它想成：若你在为某种源语言写原生编译器，并可以自由设计最容易生成的目标架构，字节码就是那套理想化的指令集。它并不存在于真实硬件上，所以我们再写一个模拟器，即一次解释一条字节码的软件模拟芯片，也就是虚拟机（virtual machine，VM）。模拟层带来开销，是字节码慢于原生代码的原因；但只要用 C 把 VM 写到各个关心的平台，就获得了可移植性。

最早的字节码格式之一是 Niklaus Wirth 为 Pascal 开发的 p-code。这里的 p 不是 Pascal，而是 portable（可移植）。本书的 clox 也走这条路；Python、Ruby、Lua、OCaml、Erlang 等主流实现也使用过类似路线。

两种实现的阶段：jlox 为 Parser -> Syntax Trees -> Interpreter；clox 为 Compiler -> Bytecode -> Virtual Machine。

后续不会严格按这些阶段依序完成，而会像 jlox 一样，按语言特性逐项构建。本章先搭好应用程序骨架，并创建保存一块字节码所需的数据结构。

14.2 开始（Getting Started）

从 main() 开始。新建文件：

// main.c
#include "common.h"

int main(int argc, const char* argv[]) {
  return 0;
}

这颗小种子将长成完整 VM。C 提供的设施很少，先建立公用头文件：

// common.h
#ifndef clox_common_h
#define clox_common_h

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

#endif

这里集中放解释器各处会使用的类型与常量。目前包括 NULL、size_t、C99 的 bool，以及 uint8_t 等显式位宽整数类型。

14.3 指令块（Chunks of Instructions）

接着定义代码表示模块。此前一直把字节码序列称为 chunk，现在将它作为正式模块名：

// chunk.h
#ifndef clox_chunk_h
#define clox_chunk_h

#include "common.h"

#endif

字节码格式中，每条指令都有一个单字节的操作码（operation code，通常简称 opcode）。这个数字决定该执行加法、减法、变量查找等哪种操作：

// chunk.h
typedef enum {
  OP_RETURN,
} OpCode;

现在只有 OP_RETURN。完整 VM 中它表示“从当前函数返回”。它暂时不实用，却是一个适合起步的简单指令。

14.3.1 指令的动态数组（A dynamic array of instructions）

字节码是一串指令，稍后还会和其他数据一起保存，因此先定义容器：

// chunk.h
typedef struct {
  uint8_t* code;
} Chunk;

我们在编译前不知道数组大小，所以它必须动态增长。动态数组提供紧凑、缓存友好的存储，常数时间的索引读取，以及对末尾的均摊常数时间追加。Java 中一直通过 ArrayList 使用它；现在换成 C，就要亲手实现。

除数组外，保存已分配元素数 capacity 与实际使用数 count：

// chunk.h
typedef struct {
  int count;
  int capacity;
  uint8_t* code;
} Chunk;

追加时，若 count < capacity，直接存入并递增 count。否则分配更大的数组，复制旧元素，更新容量和指针，释放旧数组，再存入新元素。单次扩容复制看起来是 O(n)，但只在部分追加发生；只要每次按当前大小的倍数增长，整段追加序列的平均成本就是 O(1)，这称为均摊分析（amortized analysis）。

先声明并实现初始化函数。C 没有构造器：

// chunk.h
void initChunk(Chunk* chunk);

// chunk.c
#include <stdlib.h>

#include "chunk.h"

void initChunk(Chunk* chunk) {
  chunk->count = 0;
  chunk->capacity = 0;
  chunk->code = NULL;
}

数组初始为空，甚至不分配原始数组。追加一个字节：

// chunk.h
void writeChunk(Chunk* chunk, uint8_t byte);

// chunk.c
#include "memory.h"

void writeChunk(Chunk* chunk, uint8_t byte) {
  if (chunk->capacity < chunk->count + 1) {
    int oldCapacity = chunk->capacity;
    chunk->capacity = GROW_CAPACITY(oldCapacity);
    chunk->code = GROW_ARRAY(uint8_t, chunk->code,
                             oldCapacity, chunk->capacity);
  }

  chunk->code[chunk->count] = byte;
  chunk->count++;
}

首次写入时数组是 NULL、容量为零，也会进入扩容分支。底层内存操作放在新模块中：

// memory.h
#ifndef clox_memory_h
#define clox_memory_h

#include "common.h"

#define GROW_CAPACITY(capacity) \
    ((capacity) < 8 ? 8 : (capacity) * 2)

#endif

此宏按旧容量计算新容量：零时直接分配 8 个元素，之后每次翻倍。8 是本书的经验常量；实际产品应通过真实工作负载的性能分析，在扩容次数和浪费空间之间选择。

GROW_ARRAY() 计算元素大小、完成转换，再调用唯一的底层内存函数 reallocate()：

// memory.h
#define GROW_ARRAY(type, pointer, oldCount, newCount) \
    (type*)reallocate(pointer, sizeof(type) * (oldCount), \
        sizeof(type) * (newCount))

void* reallocate(void* pointer, size_t oldSize, size_t newSize);

让 clox 的分配、释放、改变大小都经过这一处很重要：后面加入垃圾收集器时，才能统一记录正在使用的内存。两个尺寸决定操作：oldSize == 0 时分配；newSize == 0 时释放；两者非零时改变已有分配的大小。

当前实现只是对 realloc() 的薄封装：

// memory.c
#include <stdlib.h>

#include "memory.h"

void* reallocate(void* pointer, size_t oldSize, size_t newSize) {
  if (newSize == 0) {
    free(pointer);
    return NULL;
  }

  void* result = realloc(pointer, newSize);
  if (result == NULL) exit(1);
  return result;
}

这里的 oldSize 还未使用；稍后垃圾收集器会使用它。真实实现可改善内存不足时直接 exit(1) 的处理，但对本书 VM 已足够。

数组有足够容量时，元素直接放入末尾：

数组有足够容量时存储元素。

容量不足时先增长、再存储：

存储前增长动态数组。

最后还要释放 chunk：

// chunk.h
void freeChunk(Chunk* chunk);

// memory.h
#define FREE_ARRAY(type, pointer, oldCount) \
    reallocate(pointer, sizeof(type) * (oldCount), 0)

// chunk.c
void freeChunk(Chunk* chunk) {
  FREE_ARRAY(uint8_t, chunk->code, chunk->capacity);
  initChunk(chunk);
}

释放后再初始化，避免保留悬空指针或旧计数。至此已有可增长的字节数组。

14.4 反汇编字节码块（Disassembling Chunks）

原始字节很难阅读，所以需要调试工具，把 chunk 翻译成文本。新建 debug.h：

// debug.h
#ifndef clox_debug_h
#define clox_debug_h

#include "chunk.h"

void disassembleChunk(Chunk* chunk, const char* name);
int disassembleInstruction(Chunk* chunk, int offset);

#endif

实现先打印块名，再从偏移零开始，持续调用每条指令的反汇编函数。该函数返回下一条指令的偏移：

// debug.c
#include <stdio.h>

#include "debug.h"

void disassembleChunk(Chunk* chunk, const char* name) {
  printf("== %s ==\n", name);

  for (int offset = 0; offset < chunk->count;) {
    offset = disassembleInstruction(chunk, offset);
  }
}

int disassembleInstruction(Chunk* chunk, int offset) {
  printf("%04d ", offset);

  uint8_t instruction = chunk->code[offset];
  switch (instruction) {
    case OP_RETURN:
      printf("OP_RETURN\n");
      return offset + 1;
    default:
      printf("Unknown opcode %d\n", instruction);
      return offset + 1;
  }
}

反汇编器现在能显示当前偏移、指令名，并保证未知操作码不会卡死。为了试运行，在 main.c 中建立小块、写入两条 OP_RETURN、打印后释放：

// main.c
#include "chunk.h"
#include "debug.h"

int main(int argc, const char* argv[]) {
  Chunk chunk;
  initChunk(&chunk);

  writeChunk(&chunk, OP_RETURN);
  writeChunk(&chunk, OP_RETURN);
  disassembleChunk(&chunk, "test chunk");

  freeChunk(&chunk);
  return 0;
}

输出为：

== test chunk ==
0000 OP_RETURN
0001 OP_RETURN

这个小工具会伴随本书余下的 VM 实现。它迫使我们精确定义每条指令占多少字节、操作数怎样编码，也会在编译器出错时成为最可靠的观察窗口。

14.5 常量（Constants）

OP_RETURN 不需要数据，但多数指令需要。以数字字面量 1.2 为例：不能把所有可能的浮点数塞进单个字节操作数。通常的办法是把值放进 chunk 的常量表，再让指令携带该表的索引。

14.5.1 表示值（Representing values）

先为值建模块。当前 Lox 只需要数字，故 Value 是 double：

// value.h
#ifndef clox_value_h
#define clox_value_h

typedef double Value;

#endif

这并非最终设计。随后会让 Lox 拥有布尔值、nil 和对象；届时会替换这个简单表示。但将值抽到独立头文件，可把修改限制在明确边界内。

14.5.2 值数组（Value arrays）

常量表也是动态数组，复制 chunk 的模式：

// value.h
#include "common.h"

typedef struct {
  int capacity;
  int count;
  Value* values;
} ValueArray;

void initValueArray(ValueArray* array);
void writeValueArray(ValueArray* array, Value value);
void freeValueArray(ValueArray* array);
void printValue(Value value);

// value.c
#include <stdio.h>

#include "memory.h"
#include "value.h"

void initValueArray(ValueArray* array) {
  array->values = NULL;
  array->capacity = 0;
  array->count = 0;
}

void writeValueArray(ValueArray* array, Value value) {
  if (array->capacity < array->count + 1) {
    int oldCapacity = array->capacity;
    array->capacity = GROW_CAPACITY(oldCapacity);
    array->values = GROW_ARRAY(Value, array->values,
                               oldCapacity, array->capacity);
  }
  array->values[array->count] = value;
  array->count++;
}

void freeValueArray(ValueArray* array) {
  FREE_ARRAY(Value, array->values, array->capacity);
  initValueArray(array);
}

void printValue(Value value) {
  printf("%g", value);
}

printValue() 目前只打印数字；让调试器通过它而不是直接 printf，可让未来的值表示改变不泄漏到调试模块。

把常量表放入 Chunk，并初始化、释放它：

// chunk.h
#include "value.h"

typedef struct {
  int count;
  int capacity;
  uint8_t* code;
  ValueArray constants;
} Chunk;

// chunk.c
void initChunk(Chunk* chunk) {
  chunk->count = 0;
  chunk->capacity = 0;
  chunk->code = NULL;
  initValueArray(&chunk->constants);
}

void freeChunk(Chunk* chunk) {
  FREE_ARRAY(uint8_t, chunk->code, chunk->capacity);
  freeValueArray(&chunk->constants);
  initChunk(chunk);
}

追加常量并返回索引：

// chunk.h
int addConstant(Chunk* chunk, Value value);

// chunk.c
int addConstant(Chunk* chunk, Value value) {
  writeValueArray(&chunk->constants, value);
  return chunk->constants.count - 1;
}

14.5.3 常量指令（Constant instructions）

加入 OP_CONSTANT：

// chunk.h
typedef enum {
  OP_CONSTANT,
  OP_RETURN,
} OpCode;

它后面紧跟一个字节，值是常量表索引：

OP_CONSTANT 的格式：一个操作码字节，随后一个常量索引字节。

在测试程序中写入操作码和 addConstant() 返回的索引：

writeChunk(&chunk, OP_CONSTANT);
writeChunk(&chunk, addConstant(&chunk, 1.2));
writeChunk(&chunk, OP_RETURN);

反汇编时，常量指令占用两字节，并显示索引和实际值。先抽出无操作数指令的共同格式：

// debug.c
static int simpleInstruction(const char* name, int offset) {
  printf("%-16s\n", name);
  return offset + 1;
}

static int constantInstruction(const char* name, Chunk* chunk,
                               int offset) {
  uint8_t constant = chunk->code[offset + 1];
  printf("%-16s %4d '", name, constant);
  printValue(chunk->constants.values[constant]);
  printf("'\n");
  return offset + 2;
}

然后更新分派：

switch (instruction) {
  case OP_CONSTANT:
    return constantInstruction("OP_CONSTANT", chunk, offset);
  case OP_RETURN:
    return simpleInstruction("OP_RETURN", offset);
  default:
    printf("Unknown opcode %d\n", instruction);
    return offset + 1;
}

现在输出为：

== test chunk ==
0000 OP_CONSTANT         0 '1.2'
0002 OP_RETURN

操作数只有一个字节，所以一个 chunk 最多可引用 256 个常量。这个限制目前可接受；挑战会讨论扩展编码。

14.6 行信息（Line Information）

编译后不再保留 AST，运行时错误仍需指出源代码位置。因此为每个写入的字节平行保存一个行号：

// chunk.h
typedef struct {
  int count;
  int capacity;
  uint8_t* code;
  int* lines;
  ValueArray constants;
} Chunk;

void writeChunk(Chunk* chunk, uint8_t byte, int line);

初始化时设为 NULL，扩容时与 code 一起增长，追加时记录行号，释放时也释放它：

// chunk.c
void initChunk(Chunk* chunk) {
  chunk->count = 0;
  chunk->capacity = 0;
  chunk->code = NULL;
  chunk->lines = NULL;
  initValueArray(&chunk->constants);
}

void writeChunk(Chunk* chunk, uint8_t byte, int line) {
  if (chunk->capacity < chunk->count + 1) {
    int oldCapacity = chunk->capacity;
    chunk->capacity = GROW_CAPACITY(oldCapacity);
    chunk->code = GROW_ARRAY(uint8_t, chunk->code,
                             oldCapacity, chunk->capacity);
    chunk->lines = GROW_ARRAY(int, chunk->lines,
                              oldCapacity, chunk->capacity);
  }
  chunk->code[chunk->count] = byte;
  chunk->lines[chunk->count] = line;
  chunk->count++;
}

void freeChunk(Chunk* chunk) {
  FREE_ARRAY(uint8_t, chunk->code, chunk->capacity);
  FREE_ARRAY(int, chunk->lines, chunk->capacity);
  freeValueArray(&chunk->constants);
  initChunk(chunk);
}

这是最朴素的设计：同一条指令的两个字节会重复相同行号，连续多条指令也常重复。它浪费空间，却简单且查询为常数时间；后面设计笔记和挑战会讨论压缩。

14.6.1 反汇编行信息（Disassembling line information）

反汇编器在偏移后显示行号。若与前一字节同一行，用 | 代替重复数字：

// debug.c
printf("%04d ", offset);
if (offset > 0 && chunk->lines[offset] == chunk->lines[offset - 1]) {
  printf("   | ");
} else {
  printf("%4d ", chunk->lines[offset]);
}

测试时传入行号：

writeChunk(&chunk, OP_CONSTANT, 123);
writeChunk(&chunk, addConstant(&chunk, 1.2), 123);
writeChunk(&chunk, OP_RETURN, 123);

于是得到：

== test chunk ==
0000  123 OP_CONSTANT         0 '1.2'
0002    | OP_RETURN

这里 | 表示本指令与前一个字节来自同一源代码行。现在这只服务于反汇编器，但 VM 出现运行时错误时也将用它报告错误位置。

挑战（Challenges）

一个字节只能容纳 256 个常量索引。为超过 255 个常量的 chunk 设计长常量指令；比较两字节、三字节与变长编码的空间、复杂度和性能。
当前每一个指令字节都存一个完整行号。改为运行长度编码：保存“该行有多少连续字节”和行号。比较内存、查找速度和实现复杂度。
让反汇编器为控制流加标签，使跳转目标比裸偏移量更易读。

设计笔记：测试你的语言（Design Note: Test Your Language）

编译器和 VM 的错误往往不是立刻崩溃，而是让某个程序得到错误结果；调试这类问题需要大量小程序。测试语言实现有三个互补层次：

**端到端测试。**给 Lox 程序输入，比较输出或错误信息。这最接近用户所见的行为，也是原书后续测试套件的主体。
**单元测试。**测试扫描器、chunk、哈希表等 C 模块的局部不变量。它们定位迅速，但不能替代整语言行为测试。
**差分与性质测试。**对同一语义在 jlox、clox 上运行并比较，或随机生成程序来验证不变量；这对解释器尤其有价值。

测试不是开发结束时才添加的护栏。每增加一条指令、一个语法规则或一种值类型，都应写一个能证明该行为的最小程序。错误信息同样属于语言的可观察行为：既要验证程序正确执行，也要验证错误在正确位置、以有用的方式报告。

从本章起，反汇编输出本身也是一种测试接口。它让我们在 VM 运行前检查编译器是否生成了预期指令，并把“源代码 -> 字节码 -> 执行结果”这条链拆成可观察的阶段。小而明确的字节码块、稳定的输出，以及覆盖边界情况的测试，会让后续复杂的编译器工作保持可控。

14.1 字节码？（Bytecode?）​

14.1.1 为什么不遍历 AST？（Why not walk the AST?）​

14.1.2 为什么不编译为原生代码？（Why not compile to native code?）​

14.1.3 什么是字节码？（What is bytecode?）​

14.2 开始（Getting Started）​

14.3 指令块（Chunks of Instructions）​

14.3.1 指令的动态数组（A dynamic array of instructions）​

14.4 反汇编字节码块（Disassembling Chunks）​

14.5 常量（Constants）​

14.5.1 表示值（Representing values）​

14.5.2 值数组（Value arrays）​

14.5.3 常量指令（Constant instructions）​

14.6 行信息（Line Information）​

14.6.1 反汇编行信息（Disassembling line information）​

挑战（Challenges）​

设计笔记：测试你的语言（Design Note: Test Your Language）​