编程语言解释器编译器语言运行时教程【免费下载链接】craftinginterpretersRepository for the book Crafting Interpreters项目地址https://gitcode.com/gh_mirrors/cr/craftinginterpreters点击查看免费下载导读本篇围绕《Crafting Interpreters》第三部分 clox 字节码虚拟机的重要一章讲解 clox 从unityped单类型的纯数字计算器进化为支持nil、Boolean、Number 三类动态类型值的完整过程。核心内容是 C 语言中标记联合tagged union值表示的设计与实现以及运行时类型检查、错误处理、falsiness 规则和相等/比较运算的落地。读完本篇你将掌握 clox 如何在 C 的静态类型世界里构建一套可动态承载多种类型的 Value 表示并理解 bytecode VM 中指令集与源码不必一一对应的核心设计思想。背景从 unityped 到 dynamically typedclox 是《Crafting Interpreters》中用 C 实现的 Lox 语言字节码虚拟机。在前几章clox 内部所有值都是double类型——即原文中unityped单类型范式所有变量都只有一种类型通常是机器寄存器整数。Forth 和 BCPL 就属于这一范式的语言。此刻的 clox 正是 unityped 的。但 Lox 语言是动态类型的同一个变量在不同时刻可以持有 Boolean、数字或字符串。要让 clox 真正支持这一语义需要回答两个关键问题如何表示一个值的类型例如用户尝试用数字乘以true时需要在运行时检测错误并报告因此运行时必须能判断值的类型。如何存储值本身不仅要能判断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_listvfprintf定义见 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.ccase 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.ccase 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()已消费掉关键字 tokenliteral()只需依据 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.cswitch (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_NOTc/vm.ccase OP_NOT: push(BOOL_VAL(isFalsey(pop()))); break;编译端复用一元运算符解析函数unary()——之前为取负写的 switch 已按 token 类型分发指令只需加一个 casec/compiler.ccase TOKEN_BANG: emitByte(OP_NOT); break; case TOKEN_MINUS: emitByte(OP_NEGATE); break;并把!挂进解析表。与一元取负不同Lox 对!及其它期望 Boolean 的上下文非常宽容其规则称为falsiness假值性。实现于 c/vm.cstatic 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.cOP_EQUAL、OP_GREATER、OP_LESS。为什么没有!、、的指令从性能角度定义它们 VM 会执行得更快但本书的首要教学目标是让你内化字节码指令无需与用户源码一一对应——VM 可以自由选择任何指令集和代码序列只要用户可见行为正确a ! b语义等同!(a b)编译器可将前者编译为OP_EQUAL后接OP_NOTa b等同!(a b)a b等同!(a b)。严格来说IEEE 754 规定操作数为 NaN 时所有比较都返回 false因此NaN 1与NaN 1都为 false脱糖并非恒等——书中不做深究但真实语言实现必须注意这类细节。对应地解析表中六个运算符全部复用binary()解析函数binary()内的 switch 扩展出六个 casec/compiler.ccase 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_VALbool 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.ccase OP_EQUAL: { Value b pop(); Value a pop(); push(BOOL_VAL(valuesEqual(a, b))); break; }比较运算符复用 BINARY_OP、只作用于数字比相等更简单。直接复用上文的BINARY_OP宏把结果包装宏换成BOOL_VALcase 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.lox0/0产生的 NaN 不与自身相等验证。实践构建并运行 clox仓库根目录 Makefile 提供了构建入口make clox # 编译 release 版解释器并复制到仓库顶层 ./clox make debug # 编译带调试符号的 cloxd可开 DEBUG_TRACE_EXECUTION 跟踪执行 make test_clox # 运行 clox 的全部回归测试make clox通过util/c.make以NAMEclox MODErelease SOURCE_DIRc编译 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作为对比jloxJava 版解释器中同一问题通过Object与 instanceof 解决见 java/com/craftinginterpreters/lox。原文给出的两道挑战题值得动手思考进一步缩减二元运算符除!、、外还能消除哪些指令编译器在缺少它们时如何应对提示OP_NOT与OP_EQUAL的组合还能覆盖哪些情形反向优化为提升字节码 VM 速度可以增加更多对应高层操作的专用指令。针对本章新增支持的用户代码字面量、逻辑非、相等/比较你会定义哪些指令来加速赞分享编程语言解释器编译器语言运行时教程【免费下载链接】craftinginterpretersRepository for the book Crafting Interpreters项目地址https://gitcode.com/gh_mirrors/cr/craftinginterpreters点击查看免费下载相关推荐Graphene 联合类型Union完整指南定义、Schema 表示与运行时解析Graphene 联合类型Union完整指南定义、Schema 表示与运行时解析 联合类型Union是 GraphQL 中用于表达一个字段可能返回多后端API设计Darklang运行时类型动态类型系统实现Darklang运行时类型动态类型系统实现 还在为静态类型系统的编译时约束感到束手束脚Darklang的动态类型系统为你提供了运行时灵活性同时保持了类型安深入理解Crafting Interpreters类型系统实现的艺术与科学深入理解Crafting Interpreters类型系统实现的艺术与科学 在编程语言设计的核心领域类型系统的实现是一项既富有挑战性又充满艺术性的工作。今天编程语言解释器编译器语言运行时教程上一篇Playwright GenericAssertions 全解析expect 通用值断言的完整用法与底层实现下一篇ESPnet2 × PortMedia 法语语料XLS-R 预训练语音编码器 mBART-50 预训练文本编码器-解码器的 ASR/SLU 训练实战创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考