第 15 章：虚拟机（A Virtual Machine）

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

魔术师保护秘密，不是因为秘密庞大或重要，而是因为它们太小、太平凡。舞台上的奇妙效果，往往来自一个荒谬到魔术师都不好意思承认的秘诀。

Christopher Priest，《致命魔术》

我们已经讨论过如何把程序表示为字节码序列，但若从未看过指令执行，就像只借标本学习生物学：理解理论，却难以知道它们实际做什么。在构建新解释器的前端之前，先构建后端，即执行指令的虚拟机。它为字节码注入生命，也让我们更清楚编译器如何把源程序翻译为指令序列。

15.1 指令执行机（An Instruction Execution Machine）

虚拟机是解释器内部架构的一部分：交给它一个 Chunk，它就执行其中的代码。新建 VM 模块：

// vm.h
#ifndef clox_vm_h
#define clox_vm_h

#include "chunk.h"

typedef struct {
  Chunk* chunk;
} VM;

void initVM();
void freeVM();

#endif

它当前只保存待执行的 chunk，后续会逐渐增加状态。实现中声明一个全局 VM：

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

VM vm;

void initVM() {
}

void freeVM() {
}

初始化与释放函数暂时为空，但先建立其生命周期接口。使用全局对象可避免把 VM* 传递给本书中即将出现的许多函数，让示例更轻；这并非真实语言实现的普遍最佳实践。嵌入宿主应用的 VM 应显式传递 VM 指针，使宿主能决定内存位置、同时运行多个 VM 等。这里对全局变量的选择只是教学篇幅上的取舍。

在 main() 中创建和销毁 VM：

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

int main(int argc, const char* argv[]) {
  initVM();

  Chunk chunk;
  initChunk(&chunk);
  // 手写测试字节码。
  disassembleChunk(&chunk, "test chunk");

  freeVM();
  freeChunk(&chunk);
  return 0;
}

15.1.1 执行指令（Executing instructions）

VM 的入口是 interpret()。它接收一个 chunk、记录下来，并把指令指针指向代码的第一个字节：

// vm.h
typedef enum {
  INTERPRET_OK,
  INTERPRET_COMPILE_ERROR,
  INTERPRET_RUNTIME_ERROR
} InterpretResult;

InterpretResult interpret(Chunk* chunk);

这个结果稍后用于向操作系统报告正确执行、编译错误或运行时错误。现阶段尚未使用它，但先固定接口可以避免后面重塑入口。

// vm.h
typedef struct {
  Chunk* chunk;
  uint8_t* ip;
} VM;

ip 是指令指针（instruction pointer）。它不用数组索引，而是直接指向字节码数组中间的 C 指针：解引用指针通常比每次按索引计算数组位置更快。IP 这一名称很传统，x86/x64 与 CLR 使用它；68k、PowerPC、ARM、p-code 和 JVM 则常把同一概念称为 PC（program counter）。它始终指向下一条要执行的指令，而非刚刚执行的指令：

// vm.c
static InterpretResult run();

InterpretResult interpret(Chunk* chunk) {
  vm.chunk = chunk;
  vm.ip = vm.chunk->code;
  return run();
}

若只追求极限速度，ip 应放在 run() 的局部变量中，以增加编译器把它置于寄存器的机会；它会在执行期间频繁修改。但后续还有其他函数需要访问它，本书先放在 VM 内。

真正的执行循环如下：

// vm.c
static InterpretResult run() {
#define READ_BYTE() (*vm.ip++)
  for (;;) {
    uint8_t instruction;
    switch (instruction = READ_BYTE()) {
      case OP_RETURN: {
        return INTERPRET_OK;
      }
    }
  }
#undef READ_BYTE
}

这是 clox 最重要的函数。解释用户程序时，绝大部分时间都会在这里度过。循环的每一轮读取并执行一条字节码指令。READ_BYTE() 读取 ip 当前所指的字节，再推进指针；一条指令的第一个字节就是 opcode。根据数值 opcode 选择对应 C 代码的过程称为解码或分派（dispatch）。

读取 opcode 后，ip 会立即前进，所以在执行该指令的语义时，它已经指向下一段待使用代码。分派路径对每条指令、每次执行都会走到，是 VM 的最热路径。语言实现中存在 direct threaded code、jump table、computed goto 等更快技术，但它们往往依赖非标准 C 扩展或手写汇编；clox 保持一个大的 switch，以可移植性和可读性为先。

当前 OP_RETURN 暂时结束执行循环；之后函数出现时，它才会承担“从当前 Lox 函数返回”的真正语义。让 main() 调用入口：

interpret(&chunk);

再实现常量指令。暂时没有保存中间值的机制，先把常量打印出来以观察执行：

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

static InterpretResult run() {
#define READ_BYTE() (*vm.ip++)
#define READ_CONSTANT() (vm.chunk->constants.values[READ_BYTE()])
  for (;;) {
    uint8_t instruction;
    switch (instruction = READ_BYTE()) {
      case OP_CONSTANT: {
        Value constant = READ_CONSTANT();
        printValue(constant);
        printf("\n");
        break;
      }
      case OP_RETURN:
        return INTERPRET_OK;
    }
  }
#undef READ_BYTE
#undef READ_CONSTANT
}

READ_CONSTANT() 读取紧随 opcode 的字节，将其作为常量表索引，然后取出 Value。两个宏都只在 run() 内定义并在结尾取消定义；C 预处理器会放大疏忽造成的影响，明确限制宏的作用域是值得坚持的习惯。

15.1.2 执行跟踪（Execution tracing）

现在运行 clox 会在终端打印 1.2，但这只是 OP_CONSTANT 临时日志的结果。等常量正确流向其他指令后，VM 会变成黑箱。因此加入仅供实现者使用的诊断跟踪开关：

// common.h
#define DEBUG_TRACE_EXECUTION

定义此标记后，VM 会在每条指令执行之前反汇编并打印它：

// vm.c
#include "debug.h"

for (;;) {
#ifdef DEBUG_TRACE_EXECUTION
  disassembleInstruction(vm.chunk,
      (int)(vm.ip - vm.chunk->code));
#endif
  uint8_t instruction;
  // 读取并分派 instruction。
}

反汇编器接收整数偏移量，而 ip 是真实指针，所以利用指针相减将它转换为相对 chunk 开头的偏移。第 14 章的反汇编器是静态地遍历完整 chunk；这里则在执行时动态反汇编当前指令。一个 for 包住 switch 看起来并不起眼，却是 VM 两大核心部件之一：它以极少工作完成命令式执行，这种朴素正是速度来源。

15.2 值栈操纵器（A Value Stack Manipulator）

Lox 除了命令式副作用，还有产生、修改、消费值的表达式。例如：

print 3 - 2;

它需要 3、2、减法和 print 的指令。但减法如何知道 3 是被减数、2 是减数？print 又如何取得结果？更复杂地，观察副作用揭示求值顺序的程序：

fun echo(n) {
  print n;
  return n;
}

print echo(echo(1) + echo(2)) + echo(echo(4) + echo(5));

Lox 指定从左到右求值，因此任何正确实现都必须按下列顺序打印：

// echo(1)
// echo(2)
// echo(1 + 2)
// echo(4)
// echo(5)
// echo(4 + 5)
// print 3 + 9

也可以把求值顺序留给实现决定，从而让优化编译器能重排带可见副作用的算术表达式；C 与 Scheme 就不指定这一点。Lox 和 Java 一样规定从左到右，因为不同实现以令人意外的顺序运行表达式会给用户制造难以诊断的问题。

jlox 通过递归后序遍历 AST 做到这一点：先左子树，再右子树，最后处理节点。求出左操作数后，它存放在 Java 局部变量中，等待遍历右子树；每个递归节点都有自己的 Java 调用帧与局部变量。

clox 的 run() 不递归，嵌套表达式树已经压平为线性指令，不能靠 C 局部变量保存任意多临时值。下面的 AST 标出上述 print 语句的节点求值顺序：

示例 print 语句的 AST；数字标出节点的求值顺序。

每个临时结果产生后，会存活到被某项操作消费为止：

指令序列与数值的存活区间。

已消费数值所占位置可复用。把后续数值向左压紧后，会发现每个值在整个生命周期内仍占一列，且没有空隙：

把数值存活区间向左压紧，形成栈。

先出现的值至少活得和后出现的值一样久，第一个出现的最后才被消费。这正是后进先出（last-in, first-out）的栈。产生值的指令将其压栈，需要值的指令从栈顶弹出。

一叠煎饼：栈的直观比喻。

15.2.1 VM 的栈（The VM's Stack）

基于栈的 VM 很朴素：执行简单、把源语言编译到它也简单，却足以用于生产实现。当然它不是银弹；现代 JVM、CLR 与 JavaScript 实现通常还会用即时编译（JIT）动态生成更快的原生代码。

在原始 C 数组上实现栈：

// vm.h
#define STACK_MAX 256

typedef struct {
  Chunk* chunk;
  uint8_t* ip;
  Value stack[STACK_MAX];
  Value* stackTop;
} VM;

栈底，即第一个压入、最后弹出的值，在数组元素零；随后压入的值顺序放在后面。比如依次压入 crepe 的字母，数组从零开始依次为 c、r、e、p、e：

从元素 0 开始，按顺序保存 crepe 字母的数组。

第 0 个元素为 c 的栈数组。

前五个元素为 c、r、e、p、e 的栈数组。

stackTop 指向最后一个值之后的数组元素，而不是最后一个值。这一惯例让空栈可自然地表示为指向元素零：

空栈：stackTop 指向数组第一个元素。

和 ip 一样，直接指针避免每次依据整数索引计算地址。初始化与重置：

// vm.c
static void resetStack() {
  vm.stackTop = vm.stack;
}

void initVM() {
  resetStack();
}

void freeVM() {
}

压栈先写入 stackTop 所指的空槽、再递增；弹栈先递减、再读取得到的槽：

static void push(Value value) {
  *vm.stackTop = value;
  vm.stackTop++;
}

static Value pop() {
  vm.stackTop--;
  return *vm.stackTop;
}

向栈压入再从栈顶弹出会逆转顺序：

每条指令对应的栈，展示 push 后 pop 如何反转值的顺序。

目前还没有溢出保护，STACK_MAX 只是为了本章给出固定边界；函数调用出现后，栈容量和错误报告会成为更实际的问题。

15.2.2 栈跟踪（Stack tracing）

只反汇编当前指令还不够，调试时也要看到每一步前栈中有什么。仍置于调试开关内：

#ifdef DEBUG_TRACE_EXECUTION
  printf("          ");
  for (Value* slot = vm.stack; slot < vm.stackTop; slot++) {
    printf("[");
    printValue(*slot);
    printf("]");
  }
  printf("\n");
  disassembleInstruction(vm.chunk,
      (int)(vm.ip - vm.chunk->code));
#endif

它从数组开头迭代到 stackTop（不含），以方括号打印每个值，再打印将要执行的指令。这样既可看到编译器生成的字节码，也可看到每一条指令改变的运行时状态。

15.3 算术计算器（An Arithmetic Calculator）

有了栈，常量终于不必直接输出了。OP_CONSTANT 从常量表读取值后压栈：

case OP_CONSTANT: {
  Value constant = READ_CONSTANT();
  push(constant);
  break;
}

对表达式 -((1.2 + 3.4) / 5.6)，每个操作的栈状态如下：

求值 -((1.2 + 3.4) / 5.6) 时的表达式与栈状态。

加入一元负号 opcode：

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

case OP_NEGATE:
  push(-pop());
  break;

这会弹出栈顶、取负、压回结果。然后扩展 OpCode：

typedef enum {
  OP_CONSTANT,
  OP_NEGATE,
  OP_ADD,
  OP_SUBTRACT,
  OP_MULTIPLY,
  OP_DIVIDE,
  OP_RETURN,
} OpCode;

15.3.1 二元运算符（Binary operators）

二元运算都遵循同一栈模式：弹出右操作数 b，弹出左操作数 a，计算 a op b，再压入结果。暂时 Value 只是 double，可以直接写：

case OP_ADD: {
  double b = pop();
  double a = pop();
  push(a + b);
  break;
}

但后续 Value 会支持不同类型，因此现在先把数值表示封装为宏：

// value.h
#define IS_NUMBER(value) true
#define AS_NUMBER(value) (value)
#define NUMBER_VAL(value) (value)

四个二元指令只有运算符不同，抽成宏以防止重复与不一致：

// vm.c，在 run() 内定义。
#define BINARY_OP(valueType, op) \
  do { \
    double b = AS_NUMBER(pop()); \
    double a = AS_NUMBER(pop()); \
    push(valueType(a op b)); \
  } while (false)

do { ... } while (false) 把多条语句包装成一条语句，因此在 if 等上下文中也能安全使用。随后每种 opcode 只需：

case OP_ADD:      BINARY_OP(NUMBER_VAL, +); break;
case OP_SUBTRACT: BINARY_OP(NUMBER_VAL, -); break;
case OP_MULTIPLY: BINARY_OP(NUMBER_VAL, *); break;
case OP_DIVIDE:   BINARY_OP(NUMBER_VAL, /); break;

并在 run() 结尾取消定义：

#undef BINARY_OP

操作数顺序不能写反：第一个 pop() 得到右操作数 b，第二个才是左操作数 a。加法和乘法的交换性会掩盖这个错误，但减法必须是 a - b，除法必须是 a / b。

现在可以在 main() 手写生成并执行：

Chunk chunk;
initChunk(&chunk);

int constant = addConstant(&chunk, 1.2);
writeChunk(&chunk, OP_CONSTANT, 123);
writeChunk(&chunk, constant, 123);

constant = addConstant(&chunk, 3.4);
writeChunk(&chunk, OP_CONSTANT, 123);
writeChunk(&chunk, constant, 123);

writeChunk(&chunk, OP_ADD, 123);
writeChunk(&chunk, OP_RETURN, 123);

interpret(&chunk);
freeChunk(&chunk);

虽然还没有编译器，也还不能打印最终值，VM 已能正确执行常量、栈操作和基本算术。下一章将把手写的字节码换成来自源代码的扫描结果。

挑战（Challenges）

下列表达式各应生成什么字节码序列？
```
1 * 2 + 3
1 + 2 * 3
3 - 2 - 1
1 + 2 * 3 - 4 / -5
```
注意 Lox 没有负数字面量语法，因此 -5 是对数字 5 执行取负。
若真想要最小指令集，可以删除 OP_NEGATE 或 OP_SUBTRACT 之一。为 4 - 3 * -2 生成字节码：先限制自己不用 OP_NEGATE，再限制自己不用 OP_SUBTRACT。依据结果判断是否值得保留两条指令；还有哪些冗余指令可能值得加入？
VM 的栈有固定大小，且 push() 不检查溢出。错误的指令序列可能使解释器崩溃或进入未定义行为。将栈改为按需动态增长，并分析这样做的成本和好处。
OP_NEGATE 当前弹出操作数、取负、再压入结果；栈最终高度不变，却无谓地递增和递减 stackTop。改为直接在栈顶原地取负，测量是否存在性能差异。还有哪些指令可以做类似优化？

设计笔记：基于寄存器的字节码（Design Note: Register-Based Bytecode）

栈式字节码并非唯一选择。另一类常见 VM 是寄存器式：每条指令显式写出输入和输出所在的虚拟寄存器槽位。例如 var c = a + b; 在栈机中通常需 load a、load b、add、store c 四条指令，至少七个字节，并伴随三次压栈与三次弹栈。寄存器式字节码可以用一条四字节指令 add a b c：从局部变量槽位读出 a、b，相加后直接写入 c。

寄存器式 add 虽有更多操作数、解码更复杂，却少了一次分派和全部中间栈操作。Lua 的主实现曾是栈式 VM，在 Lua 5.0 转换为寄存器指令集后记录到性能提升。改善幅度会强烈依赖语言语义、具体指令集与编译器成熟度；Lua 团队关于这一实现的论文 The Implementation of Lua 5.0 是很好的延伸阅读。

寄存器 VM 往往执行更少指令，却让每条指令更宽，编译器还必须分配和复用寄存器。栈 VM 的指令短，编译器可按表达式后序遍历自然产生代码；解释器的临时值规则也很透明。Lua 采用寄存器式字节码，JVM 与本章的 clox 采用栈式字节码。

两者没有放之四海皆准的胜者。若目标是很小、易于教学和实现的解释器，栈模型尤其有吸引力；若指令分派成本占主导，减少指令数量可能值得承担更复杂的编码和编译。真正的语言实现通常还会配合 JIT、内联缓存、专用指令等手段，架构选择必须以真实的工作负载与实现目标来检验。

15.1 指令执行机（An Instruction Execution Machine）​

15.1.1 执行指令（Executing instructions）​

15.1.2 执行跟踪（Execution tracing）​

15.2 值栈操纵器（A Value Stack Manipulator）​

15.2.1 VM 的栈（The VM's Stack）​

15.2.2 栈跟踪（Stack tracing）​

15.3 算术计算器（An Arithmetic Calculator）​

15.3.1 二元运算符（Binary operators）​

挑战（Challenges）​

设计笔记：基于寄存器的字节码（Design Note: Register-Based Bytecode）​