Crafting Interpreters 类型系统实战：clox 的标记联合（Tagged Union）值表示与动态类型运行时

• 编程语言
• 解释器
• 编译器
• 语言运行时
• 教程

导读

本篇围绕《Crafting Interpreters》第三部分 clox 字节码虚拟机的重要一章，讲解 clox 从"unityped"（单类型）的纯数字计算器进化为支持nil、Boolean、Number 三类动态类型值的完整过程。核心内容是 C 语言中"标记联合（tagged union）"值表示的设计与实现，以及运行时类型检查、错误处理、falsiness 规则和相等/比较运算的落地。读完本篇，你将掌握 clox 如何在 C 的静态类型世界里构建一套可动态承载多种类型的 Value 表示，并理解 bytecode VM 中"指令集与源码不必一一对应"的核心设计思想。

背景：从 unityped 到 dynamically typed

clox 是《Crafting Interpreters》中用 C 实现的 Lox 语言字节码虚拟机。在前几章，clox 内部所有值都是double类型——即原文中"unityped"（单类型）范式：所有变量都只有一种类型（通常是机器寄存器整数）。Forth 和 BCPL 就属于这一范式的语言。此刻的 clox 正是 unityped 的。

但 Lox 语言是动态类型的：同一个变量在不同时刻可以持有 Boolean、数字或字符串。要让 clox 真正支持这一语义，需要回答两个关键问题：

1. 如何表示一个值的类型？例如用户尝试用数字乘以true时，需要在运行时检测错误并报告，因此运行时必须能判断值的类型。
2. 如何存储值本身？不仅要能判断"3 是数字"，还要能区分它和数字 4。

同时，作为自建语言的实现者，还必须考虑效率——如何在尽量少的比特位中打包以上两类信息。语言黑客们想出了各种巧妙方案，本章采用最经典、最简单的解决方案：标记联合（tagged union）。

标记联合：Value 的数据结构设计

类型标签枚举：VM 视角的"类型"

值由两部分组成：一个类型"标签（tag）"，和一个保存实际数据的负载（payload）。首先为 VM 支持的每种值定义一个枚举：

// c/value.h typedef enum { VAL_BOOL, VAL_NIL, VAL_NUMBER, VAL_OBJ } ValueType;

需要特别强调的是（见 c/value.h）：这个枚举的每个 case 对应的是VM 内置支持的值的种类，而不是用户定义的类型。当后续为语言加入 class 时，每个用户自定义的类并不需要自己的枚举项——对 VM 而言，类的每个实例都是同一种类型："instance"（实例）。这是 VM 视角的"类型"，不是用户的类型。

为什么是 union 而不是 struct

仅存类型标签还不够，还要存数据本身：数字的double、Boolean 的true/false。一种朴素想法是定义一个包含每种类型字段的 struct，但这会浪费内存——一个值不可能同时既是数字又是 Boolean，任何时刻只有一个字段被用到。C 的union让所有字段在内存中重叠，其大小为最大字段的大小，因此更紧凑。

这种设计还对应一个概念：熟悉 ML 家族语言的读者会发现，C 的 struct/union 大致对应积类型与和类型的区别（元组 vs 代数数据类型）。同时，"用 union 将底层比特重新解释为不同类型"是 C 的精髓——它打开了大量巧妙优化的空间，但也极度不安全，必须小心使用。

完整的 Value 结构体

将类型标签与 union 组合成单个结构体：

// c/value.h typedef struct { ValueType type; union { bool boolean; double number; Obj* obj; // 后续字符串、函数、类等对象类型使用 } as; // "as" 命名：读取时读起来像一次 cast } Value;

在 64 位机器、典型 C 编译器下，布局大致为：4 字节的type标签在前，随后是 union；由于 union 内含 8 字节的double，编译器会在type后插入 4 字节**填充（padding）**以保持 double 对齐。也就是说，实际花了 8 字节来存放只需表示 0~3 的标签。把枚举塞进更小的类型只会徒增填充，并不能省内存。

因此每个 Value 是 16 字节，略大。不过它们仍足够小，可以存放在 C 栈上并按值传递。这之所以安全，是因为目前支持的这些类型都是**不可变（immutable）**的：把包含数字 3 的 Value 副本传给某个函数，无需担心调用方看到被修改的值——你无法"修改"3。原文预告：内存布局的优化留待后面的 optimization 章节（nan-boxing，见 c/value.h 中#ifdef NAN_BOXING分支）。

关于 ValueArray：每个 Chunk 的常量表由ValueArray动态数组承载（initValueArray/writeValueArray/freeValueArray，见 c/value.c），通过GROW_CAPACITY与GROW_ARRAY宏扩容。由于数组元素按 8 字节对齐存储 double，编译器会在每个 Value 之间插入同样的填充。

桥接两个世界：Lox Value 与 C Value 的转换宏

新的 Value 可以包含一个 double，但不再等价于double。clox 中所有直接 C 强转的旧代码都失效了，必须通过宏完成强制转换。核心宏定义在 c/value.h：

提升：C 值 → Lox Value（*_VAL宏）

#define BOOL_VAL(value) ((Value){VAL_BOOL, {.boolean = value}}) #define NIL_VAL ((Value){VAL_NIL, {.number = 0}}) #define NUMBER_VAL(value) ((Value){VAL_NUMBER, {.number = value}}) #define OBJ_VAL(object) ((Value){VAL_OBJ, {.obj = (Obj*)object}})

每个宏接收适当类型的 C 值，产生一个带正确类型标签并包含底层数据的 Value，将静态类型的 C 值"提升"到 Lox 的动态类型宇宙中。

解包：Lox Value → C 值（AS_*宏）

#define AS_BOOL(value) ((value).as.boolean) #define AS_NUMBER(value) ((value).as.number) #define AS_OBJ(value) ((value).as.obj)

注意没有AS_NIL宏——因为nil只有一个值，VAL_NIL类型的 Value 不携带任何额外数据。这些宏直接访问 union 字段，因此**"类型正确"是硬前提**。若写出下面的代码，就是直接打开了通往暗影位面的传送门：

Value value = BOOL_VAL(true); double number = AS_NUMBER(value); // 危险！类型不符

类型检查：IS_*宏

#define IS_BOOL(value) ((value).type == VAL_BOOL) #define IS_NIL(value) ((value).type == VAL_NIL) #define IS_NUMBER(value) ((value).type == VAL_NUMBER) #define IS_OBJ(value) ((value).type == VAL_OBJ)

任何一次AS_*调用之前，都必须先用对应的IS_*宏守卫。依靠这 8 个宏（4 组_VAL+ 4 组AS_+ 4 个IS_），数据可以在 Lox 的动态世界与 C 的静态世界之间安全往返。

让旧代码重新工作：动态类型数字与运行时错误

编译期：数字常量包装

编译数字字面量时，先把词素（lexeme）转换为 C double，再用NUMBER_VAL()包装成 Value 后存入常量表（c/compiler.c 中的number()解析函数）。运行时打印值时，则在printf()之前先用AS_NUMBER()解包出 double（见 c/value.c 的printValue的VAL_NUMBER分支）。

一元取负与运行时错误

一元取负会弹出一个操作数、取负、压回结果。有了多种类型后，不能再假设操作数一定是数字——用户完全可能写出print -false;。clox 的答案是引入runtime errors（运行时错误）：在执行要求特定类型的操作前，先确认 Value 确实是该类型。VM 中的OP_NEGATE分支（c/vm.c）如下：

case OP_NEGATE: if (!IS_NUMBER(peek(0))) { runtimeError("Operand must be a number."); return INTERPRET_RUNTIME_ERROR; } push(NUMBER_VAL(-AS_NUMBER(pop()))); break;

这里用到两个新机制：

• peek(int distance)：从栈中返回一个值但不弹出它，distance表示距离栈顶的深度（0 是栈顶，1 是下一格）。原文解释：不先 pop 再校验，是因为后续章节中，若操作中途触发垃圾回收，需要让操作数留在栈上以便 GC 能找到它们——这里主要出于习惯保持一致。
• runtimeError()：C 可变参数函数（va_list+vfprintf，定义见 c/vm.c），需要包含<stdarg.h>头。调用者可像printf()一样传入格式字符串和若干参数，后续章节会用它产生含更多数据的格式化错误信息。

打印错误信息后，还要告诉用户出错时正在执行源码的哪一行。由于编译期已经丢弃了 token，运行时通过 chunk 中编译进去的调试行信息（lines数组）查出行号。关键细节：取的是当前字节码指令索引减一——因为解释器在每条指令执行前会先推进指令指针，所以调用runtimeError()时，出错的正是上一条指令。

Lox 的错误处理相当"吝啬"：所有错误都是致命的，立即中止解释器，用户代码没有任何恢复手段。原文直言，若 Lox 是真实语言，这会是首先要改进的地方之一。

二元算术运算符

+、-、*、/四个运算符的公共逻辑被封装进一个预处理器宏BINARY_OP（在早几章看似过度设计，本章得到了回报），只需把运算符 token 作为参数传入，类型检查和转换集中在一处：

#define BINARY_OP(valueType, op) \ do { \ if (!IS_NUMBER(peek(0)) || !IS_NUMBER(peek(1))) { \ runtimeError("Operands must be numbers."); \ return INTERPRET_RUNTIME_ERROR; \ } \ double b = AS_NUMBER(pop()); \ double a = AS_NUMBER(pop()); \ push(valueType(a op b)); \ } while (false)

流程与一元取负一致：先确认两个操作数都是数字，任一不是则报错并返回；操作数合法后，弹出并解包，应用给定运算符，再包装结果压回栈。结果包装宏（valueType）作为宏参数传入——C 中宏可以作为参数传给宏。算术运算传NUMBER_VAL；而下一节会看到，比较运算传BOOL_VAL，这正是把包装宏做成参数的原因。

VM 中的四个算术分支（c/vm.c）：

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

新增三种字面量：true、false、nil

现在 clox 可以在内部表示新类型，但用户程序还无法创建这些类型的值。接下来为编译器增加三个新字面量true、false、nil的支持。

对于数字字面量，由于存在海量可能的数值，需要存入常量表并用OP_CONSTANT加载；但true/false/nil总共只有 3 个可能值，再浪费一个两字节指令和常量表项就太奢侈——而且更慢。因此定义 3 条专用指令，直接把字面量压栈（c/vm.c）：

case OP_NIL: push(NIL_VAL); break; case OP_TRUE: push(BOOL_VAL(true)); break; case OP_FALSE: push(BOOL_VAL(false)); break;

原文附注：为常见常量值提供专用指令确实更快——字节码 VM 大部分执行时间花在读取和解码指令上，行为一定时指令越少越简单就越快。例如 Java 字节码指令集就有专门加载 0.0、1.0、2.0 以及 -1 到 5 的整数的指令（多数成熟 JVM 已用 JIT 编译，这成了遗留优化）。

扫描器（scanner）已经将true、false、nil视为关键字，所以直接进入解析器。基于表的 Pratt 解析器中，只需把同一个解析函数literal()挂到三个关键字 token 对应的行上（c/compiler.c 的rules[]表）：

[TOKEN_FALSE] = {literal, NULL, PREC_NONE}, [TOKEN_NIL] = {literal, NULL, PREC_NONE}, [TOKEN_TRUE] = {literal, NULL, PREC_NONE},

由于parsePrecedence()已消费掉关键字 token，literal()只需依据 token 类型输出相应指令：

static void literal(bool canAssign) { switch (parser.previous.type) { case TOKEN_FALSE: emitByte(OP_FALSE); break; case TOKEN_NIL: emitByte(OP_NIL); break; case TOKEN_TRUE: emitByte(OP_TRUE); break; default: return; // Unreachable. } }

（原文提及：也可为每个字面量写独立解析函数以省去 switch，但作者认为那是个人品味问题。）

前端完成后，别忘了反汇编器（disassembler）也要认识新指令，OP_NIL、OP_TRUE、OP_FALSE在 c/debug.c 中通过simpleInstruction()输出名称。

此时运行程序true，解释器在打印结果时会崩溃——printValue()必须扩展以处理新类型（c/value.c）：

switch (value.type) { case VAL_BOOL: printf(AS_BOOL(value) ? "true" : "false"); break; case VAL_NIL: printf("nil"); break; case VAL_NUMBER: printf("%g", AS_NUMBER(value)); break; case VAL_OBJ: printObject(value); break; }

逻辑非与 falsiness

新类型最有用的第一批操作是逻辑运算符。一元!获得新指令OP_NOT（c/vm.c）：

case OP_NOT: push(BOOL_VAL(isFalsey(pop()))); break;

编译端复用一元运算符解析函数unary()——之前为取负写的 switch 已按 token 类型分发指令，只需加一个 case（c/compiler.c）：

case TOKEN_BANG: emitByte(OP_NOT); break; case TOKEN_MINUS: emitByte(OP_NEGATE); break;

并把!挂进解析表。与一元取负不同，Lox 对!及其它期望 Boolean 的上下文非常宽容，其规则称为falsiness（假值性）。实现于 c/vm.c：

static bool isFalsey(Value value) { return IS_NIL(value) || (IS_BOOL(value) && !AS_BOOL(value)); }

Lox 遵循 Ruby 的规则：nil和false是 falsey，其余一切值都表现得像true。所以!nil合法并得到true（而-nil则是运行时错误）。测试用例 test/operator/not.lox 完整验证了这条规则：!true→false、!false→true、!nil→true、!0→false、!""→false、!foo（函数）→false。isFalsey函数后续还被OP_JUMP_IF_FALSE用于控制流（and/or短路），是跳转章节的基础。反汇编器同样需新增OP_NOT的显示。

相等与比较运算符

最后一组是返回 Boolean 结果的运算符：==、!=、<、>、<=、>=（and/or因需要短路控制流，留到跳转章节）。

只定义三条指令的脱糖（desugaring）

新指令只有三条（c/vm.c）：OP_EQUAL、OP_GREATER、OP_LESS。为什么没有!=、<=、>=的指令？从性能角度，定义它们 VM 会执行得更快；但本书的首要教学目标是让你内化"字节码指令无需与用户源码一一对应"——VM 可以自由选择任何指令集和代码序列，只要用户可见行为正确：

• a != b语义等同!(a == b)，编译器可将前者编译为OP_EQUAL后接OP_NOT；
• a <= b等同!(a > b)，a >= b等同!(a < b)。

（严格来说，IEEE 754 规定操作数为 NaN 时所有比较都返回 false，因此NaN <= 1与NaN > 1都为 false，脱糖并非恒等——书中不做深究，但真实语言实现必须注意这类细节。）

对应地，解析表中六个运算符全部复用binary()解析函数，binary()内的 switch 扩展出六个 case（c/compiler.c）：

case TOKEN_BANG_EQUAL: emitBytes(OP_EQUAL, OP_NOT); break; case TOKEN_EQUAL_EQUAL: emitByte(OP_EQUAL); break; case TOKEN_GREATER: emitByte(OP_GREATER); break; case TOKEN_GREATER_EQUAL: emitBytes(OP_LESS, OP_NOT); break; case TOKEN_LESS: emitByte(OP_LESS); break; case TOKEN_LESS_EQUAL: emitBytes(OP_GREATER, OP_NOT); break;

六个运算符，只花三条指令的代价。

valuesEqual：跨类型相等

OP_EQUAL可以作用于任意一对值，包括不同类型的值。逻辑被拆到独立的valuesEqual()函数（声明于 c/value.h，实现在 c/value.c），它总是返回 C 的bool，所以可安全包进BOOL_VAL：

bool valuesEqual(Value a, Value b) { if (a.type != b.type) return false; switch (a.type) { case VAL_BOOL: return AS_BOOL(a) == AS_BOOL(b); case VAL_NIL: return true; case VAL_NUMBER: return AS_NUMBER(a) == AS_NUMBER(b); case VAL_OBJ: return AS_OBJ(a) == AS_OBJ(b); default: return false; // Unreachable. } }

首先比较类型标签：类型不同则必然不相等（原文对比了 JS 的隐式转换导致的 "0" == 0 之类的宽松相等问题、PHP 认为 "1" 与 "01" 等价等反例）。类型相同则解包后直接比较。每个类型一个 case，之后每加新类型这里就新增 case。

一个关键问题：为什么不能直接memcmp()两个 Value 结构体？因为填充字节和不同大小的 union 字段导致 Value 含有未使用的比特位，C 不保证这些位的内容——两个相等的 Value 可能在未使用字节上不同，memcmp会错误地判定不相等。这就是valuesEqual必须逐字段比较的原因。VM 侧OP_EQUAL分支（c/vm.c）：

case OP_EQUAL: { Value b = pop(); Value a = pop(); push(BOOL_VAL(valuesEqual(a, b))); break; }

比较运算符：复用 BINARY_OP

<、>只作用于数字，比相等更简单。直接复用上文的BINARY_OP宏，把结果包装宏换成BOOL_VAL：

case OP_GREATER: BINARY_OP(BOOL_VAL, >); break; case OP_LESS: BINARY_OP(BOOL_VAL, <); break;

这正是当初把包装宏做成BINARY_OP参数的原因——算术传NUMBER_VAL，比较传BOOL_VAL。反汇编器同样为三条新指令加上simpleInstruction名称输出。

至此，clox 从一个数字计算器成长为接近通用的表达式求值器。运行!(5 - 4 > 3 * 2 == !nil)可以正常得到结果。相等/NaN 语义由测试用例 test/operator/equals.lox（如nil == false为 false、0 == "0"为 false）与 test/number/nan_equality.lox（0/0产生的 NaN 不与自身相等）验证。

实践：构建并运行 clox

仓库根目录 Makefile 提供了构建入口：

make clox # 编译 release 版解释器，并复制到仓库顶层 ./clox make debug # 编译带调试符号的 cloxd（可开 DEBUG_TRACE_EXECUTION 跟踪执行） make test_clox # 运行 clox 的全部回归测试

make clox通过util/c.make以NAME=clox MODE=release SOURCE_DIR=c编译 c/ 目录下的源码（main.c、vm.c、compiler.c、scanner.c、chunk.c、value.c、debug.c等）。构建完成后即可在交互式 REPL 或脚本模式下体验本章新增的类型与运算符行为。当前 c/ 目录中的 c/value.h 是全书最终版本——包含VAL_OBJ（字符串、函数、闭包、类等对象类型）与#ifdef NAN_BOXING下的优化分支，其中IS_NUMBER改为按 QNaN 模式判断、AS_NUMBER用memcpy实现类型双关（valueToNum/numToValue），并定义了TAG_NIL/TAG_FALSE/TAG_TRUE三个标签位。这正是本章标记联合方案在后文 optimization 中演进为 NaN 盒（nan-boxing）的伏笔。

延伸阅读与本章挑战

• 后续章节 strings 将引入最复杂的内置类型——字符串。字符串长度可变，这一微小差异带来了巨大的实现影响，因此专章论述。
• 本章的标记联合设计在后文被 NaN 盒（nan-boxing）优化取代，详见 optimization；作为对比，jlox（Java 版解释器）中同一问题通过Object与 instanceof 解决，见 java/com/craftinginterpreters/lox。

原文给出的两道挑战题，值得动手思考：

1. 进一步缩减二元运算符：除!=、<=、>=外，还能消除哪些指令？编译器在缺少它们时如何应对？（提示：OP_NOT与OP_EQUAL的组合还能覆盖哪些情形？）
2. 反向优化：为提升字节码 VM 速度，可以增加更多对应高层操作的专用指令。针对本章新增支持的用户代码（字面量、逻辑非、相等/比较），你会定义哪些指令来加速？

• 编程语言
• 解释器
• 编译器
• 语言运行时
• 教程