来源书籍

用Go语言自制编译器

Skill 版本:v24 经典原理(高浓度、高稳定性) 107 张卡片

高浓度、高稳定性(经典原理,全文阅读确认)。编译与执行分离、字节码协议、栈帧和闭包实现具有耐久性;具体性能数字仅限书内环境与样例。 [整书笔记](_book_note.md)

索斯藤·鲍尔(Thorsten Ball) · 廖彬 译 · 人民邮电出版社 · 2022-06-01 · ISBN 9787115591104

全书导读

本书延续Monkey的词法与语法前端,把AST直接求值升级为字节码编译和虚拟机执行。它从小指令集同时推进编译器与执行器,再加入跳转、绑定、集合、函数与闭包。前言明确不包含解释器书追加的宏系统。性能对比限于书内斐波那契案例。

全书主线

本书核心问题是:怎样把已有语言语义变成可编码、可检查、可执行的字节码协议。作者并非一次设计完整机器,而是从常量和加法开始,让每个新能力依次穿过指令定义、编译器、反汇编、VM和测试。这个递增方式使失败能定位到协议的一侧。

前半部先确立值如何进入、离开栈,再以跳转控制执行路径,以符号索引连接名称和值。集合让多个临时对象组合成单个结果。函数随后把代码与一次调用分开,调用帧和局部区维持可恢复执行。闭包最后将“代码已编译,但需要的值尚未产生”的时间差显式化:编译器安排捕获位置,VM在创建闭包时填入对象。

flowchart LR
 A[源程序] --> B[复用词法和语法前端]
 B --> C[AST]
 C --> D[编译器与符号表]
 D --> E[字节码与常量池]
 E --> F[VM取指解码]
 F --> G[操作数栈与全局存储]
 F --> H[调用帧与闭包]
 G --> I[语言结果或错误]
 H --> I

代码生成和执行共享的关键契约包括指令长度、索引含义、值的入栈顺序及调用后栈形状。它们任何一项变化都需要检查生产者、消费者及工具;仅让某个局部测试通过不足以证明所有组合成立。

前言

本书沿用Monkey的词法、语法前端与对象系统,把树遍历执行替换成编译器和VM。宏不是本书目标;阅读重点是每增加一种语言能力,编译结果与运行时协议如何一起变化。

  • 复用前端替换执行方式:从树遍历升级到编译器和虚拟机,不必重写整个语言前端。Monkey继续把字符解析成AST,但后续不再直接递归求值,而是生成字节码,再交给虚拟机执行。复用语言语法与对象表示,可以把学习焦点放在执行架构变化上;本书明确从前作第4章衔接,不包含追加的宏系统。
原书依据 · 1 处

第 1 章 编译器与虚拟机

编译器把一种表示翻译为另一种表示,虚拟机则解释执行目标指令。先理解物理机取指、状态与调用上下文,再看软件VM的指令选择,后续的字节码设计才有清楚的职责边界。

  • 编译是表示之间的翻译:编译器把源语言程序变成目标语言程序,生成可执行机器文件只是其中一种形式。目标也可以是字节码、汇编、其他高级语言或内存中的代码。判断是否发生编译,应关注表示转换及语义保持,而不能仅看有没有输出文件或是否立即运行。
  • 编译与求值复用语法前端:解释器和编译器都可先用词法与语法分析把文本变成AST。差别在后续遍历的用途:树遍历解释器直接执行节点含义,编译器生成表达同等行为的目标代码,由后续执行器运行。因此同一AST能够成为不同执行方案的共同入口,前端相同不意味着运行方式相同。
  • 中间表示服务后续变换:AST适合表达源语言结构,但未必最适合优化和生成目标代码。编译器可以把它转成另一种IR,再执行死代码删除、常量预计算等变换,最后交给后端。IR可以是树、文本或二进制表示;额外IR和优化阶段都不是所有编译器的必备步骤,选择应由目标和约束决定。
  • 取指解码执行循环:执行器通过程序计数器找到下一条指令,解码其操作和参数,再执行并决定后续位置,循环直到程序结束。把代码作为数据存储并不自动产生执行行为,只有数据被按指令规则读取和执行时才构成程序。这种循环可以由硬件或软件实现,虚拟机不需要在物理上复制CPU全部组件。
  • 调用栈保存返回上下文:函数调用结束后需要知道回到哪里,并恢复外层参数与局部状态。调用栈按后进先出保存这些嵌套上下文,当前函数返回时移除当前层,外层上下文重新成为栈顶。调用栈是一种职责与组织约定,不等同于某个固定硬件地址区域;虚拟机可以在软件管理的内存中实现它。
  • 寄存器与栈指针:寄存器保存少量频繁访问的执行状态,避免每次都从主内存读取。栈指针记录栈顶位置,是这种状态的典型例子;具体硬件的寄存器数量和用途由架构决定。软件虚拟机也能用普通变量表达栈指针,不应因为名称相同就把虚拟寄存器等同于物理CPU寄存器。
  • 虚拟机是软件执行模型:本书虚拟机以软件维护程序计数器、栈和指令循环,执行为语言设计的指令集。它服务于语言实现,并不要求像整机虚拟化软件那样模拟磁盘、显卡或另一个操作系统。一个函数也能承担虚拟机职责;是否是虚拟机取决于它怎样解释机器状态与指令,而不是代码规模。
  • 栈式与寄存器式的取舍:栈式虚拟机用压栈和弹栈传递操作数,指令与编译器通常较简单,但同一计算可能需要更多指令。寄存器式指令可直接指明虚拟寄存器,减少部分栈搬运,却增加编译与状态分配工作。指令更少是可能的性能来源,不是任何程序都更快的保证;仍需结合编码、分派和实际工作负载比较。
  • 指令分派选择执行实现:分派为已解码指令选择对应执行逻辑,例如用switch把ADD映射为弹出两个值、求和并压回结果。它处在高频执行循环中,可能形成开销。跳转表等是其他实现方向,但不能仅凭分支数量推断当前语言和编译器中的switch一定最慢;实现选择需由实测和可维护性共同约束。
  • 虚拟机隔离体系结构差异:编译到本地机器码需要面向不同目标体系结构生成代码;编译到自定义虚拟指令则把这些差异集中到虚拟机及宿主工具链。源语言编译器可以继续输出同一字节码协议,但仍需保证目标平台上有兼容执行器,不能把字节码存在等同于自动获得所有平台兼容性。
  • 领域指令减少表达距离:虚拟机指令集可直接表达源语言常用操作,例如对象创建、字段访问或函数调用,而不必完整仿照通用CPU。目标更聚焦,使编译映射与调试更容易,也可能用较少指令表达同一行为。设计时仍要考虑执行成本:把操作命名成一条指令,不等于消除了它内部的工作。
  • 操作码不等于整条指令:字节码指令由操作码及其操作数组成。操作码标识动作,操作数提供索引或参数;操作数可以占多个字节,也可以不存在。因此一字节操作码不意味着每条指令都只有一字节。解码器必须知道每种操作数的宽度,才能正确找到下一条指令。
  • 多字节操作数需要字节序:同一个多字节整数在指令流中需要确定编码顺序:小端先放低位字节,大端先放高位字节。编码器和解码器必须采用相同约定,否则常量索引等参数会被读成另一个值。字节序描述字节的排列,不能与栈上操作数的左右顺序混为一谈。
  • 汇编与反汇编连接可读形式:助记符给操作码提供便于记忆的名称,但实际字节码保存的是数字与参数。汇编器把可读指令转为二进制,反汇编器按格式把二进制恢复成可读指令。它们不是把源程序完整还原出来的逆编译器;可读指令主要用于检查编码、定位偏移与调试执行协议。
  • 编译器与虚拟机共同演进:编译器生成什么与虚拟机能执行什么必须一致。学习时先让两者支持同一组极少指令,形成从输入到结果的可运行闭环,再逐个扩展,比先写完一端更容易暴露协议缺口。这个顺序服务于反馈与理解;已有明确目标平台时,并不要求所有工程都采用同样的实现节奏。
原书依据 · 15 处

第 2 章 你好,字节码!

本章沿着最小可执行链路推进:整数进入常量池,编译器发出索引指令,VM解码并压栈;随后加入加法并接入交互入口。编码、反汇编与执行器处理同一份指令协议,是后续扩展的基本方法。

  • 常量池把值与指令分开:编译器在编译时确定字面量的值,将对象放入常量池,在指令中只保存索引。OpConstant据此取出对象并压栈。这样字符串等值不必直接嵌入每条指令,但指令序列必须与对应常量池一起交付;只有索引字节而没有相同的池,程序含义并不完整。
  • 操作数宽度是协议的一部分:OpConstant的操作数占两字节,以uint16表示常量池索引,范围为0到65535。这限制了当前编码能引用的常量位置,同时缩小指令体积。增加常量池容量不能仅扩展容器,还必须同时修改编码、解码和相关测试;宽度是编译器与虚拟机共享的协议。
  • 字节编码测试使用非对称值:测试字节序时,65534的大端编码是255、254,交换字节后可直接观察错误;65535则是255、255,无法发现顺序颠倒。选择输入应让待验证的差异可观察,而不是只选最大值。这个原则也适用于左右操作数顺序、字段布局与其他对称输入容易掩盖的问题。
  • 指令定义统一编码元数据:Definition保存操作码的可读名称和各操作数宽度。Make据宽度分配并写入字节,ReadOperands按相同信息读取,反汇编使用名称显示。共享元数据减少格式知识散落,但VM可以在热点执行循环直接按已知格式解码;优化不能改变双方对指令长度的约定。
  • 教学编码器的输入假设:本章Make遇到未知操作码返回空字节切片,写操作数时也依赖调用方提供与定义匹配的参数,整数转uint16没有额外范围保护。这建立在指令由受控编译器生成的假设上,不等于可以安全处理任意字节码输入。若扩展成外部格式入口,需要显式规定未知指令、参数数量、越界值与截断输入的错误行为。
  • 字节码同时携带常量与指令:Bytecode将指令流与常量对象列表一起传给VM。Compiler维护这两部分,递归遍历AST,遇到整数时创建常量并发出引用其索引的指令。测试因此应分别检查池中对象与指令字节;指令顺序正确但常量内容错误,仍不能证明编译正确。
  • 反汇编显示真实字节偏移:可读字节码输出包含指令起始偏移、助记符和已解码操作数。偏移按1字节操作码加实际操作数宽度递增,而不是按指令条数递增。这样可把失败断言与真实编码位置对应起来,也为后续跳转修补提供可检查坐标。反汇编改善诊断,并不替代对原始字节和常量池的验证。
  • 发射指令返回起始位置:emit先编码指令,再追加到当前指令流,返回追加前的长度作为该指令的起始位置。该值是字节偏移,不是指令序号;编译器后续可以据此定位和修补已发出的指令。返回值描述发射动作的业务结果,也避免调用者重新扫描整个字节流寻找位置。
  • 栈指针指向下一个空槽:VM预分配栈,通过sp管理逻辑使用范围:push把值写到stack[sp]再加一,栈顶读取stack[sp-1],pop先取此位置再减一。sp等于0意味着空栈,不应读取sp-1。这个一致的不变量比“sp是栈顶”这一含糊说法更精确,也使越界检查有明确位置。
  • 解码后跳过操作数字节:VM循环默认每次将ip加一;OpConstant还要额外跳过其两字节操作数,才能使下一轮落在下一个操作码。若只执行循环自增,操作数会被误当新指令。变长指令的推进规则必须与编码宽度一致,正常算术结果不能掩盖某类宽度组合下的解码错位。
  • 栈运算保留左右次序:编译中缀表达式时先发出左侧、再发出右侧,执行时栈顶先弹出的是右操作数,再弹出左操作数。加法具有交换性,错误地反过来相加也可能通过测试,但减法会暴露错误。因此操作数角色必须由压入顺序和弹出协议确定,不能依赖当前运算恰好可交换。
  • 新操作码贯穿工具与执行器:加入无操作数OpAdd时,编码器可能已自然支持,但反汇编需要零操作数格式化,编译器要在左右子表达式后发射它,VM还要实现弹出、相加与压回结果。每层的测试验证不同责任:格式工具可工作不代表编译器已经发出指令,发出正确指令也不代表VM已经执行。
  • 交互入口按阶段处理错误:本章REPL每行依次解析、编译和运行,并在各阶段失败时报告错误后继续下一轮。编译失败时不启动VM,运行失败时不把结果当成功展示。此时每轮都新建编译器与VM,尚未支持跨行绑定持久化;不能因能够交互计算加法就推断完整语言和状态管理已经完成。
原书依据 · 13 处

第 3 章 编译表达式

表达式编译遵循先子节点后操作符的顺序,VM消费操作数并生成结果。语句结束时清理结果,使连续程序不会无界积累工作值。对象类型、比较与真值规则决定操作码的实际语义,不能只看栈效果。

  • 表达式语句结果需要出栈:单独的表达式语句只包装一次计算,其结果如果不再被其他语法使用,就不能永久留在操作数栈上。编译器在其后发出OpPop,让多个连续语句执行后不持续占用栈空间。不能给所有子表达式都加Pop,否则外层运算会失去需要的操作数;清理位置由语法上下文决定。
  • 逻辑出栈不等于清空存储:本章pop只减小sp,没有把底层槽位置nil,因此刚弹出的对象仍暂存于stack[sp]。LastPoppedStackElem利用这个实现细节读取最终表达式结果,供测试与REPL展示。它不是新的逻辑栈顶,也不是永久结果寄存器:后续push会覆盖该槽,其他清理策略也可能使这种读取失效。
  • 压栈与弹栈必须配套:表达式语句后有OpPop,要求其表达式执行前确实压入一个结果。编译器发出了布尔指令但VM尚未实现压栈时,清理指令会在空栈上pop并触发越界。因而新增语法的集成不仅要有操作码,还要验证每条路径的栈效果;合法字节码生产者与执行器不同步也会破坏这个不变量。
  • 类型检查与具体运算分层:二元运算入口统一弹出右、左两个对象,检查类型组合,再委托整数等具体实现解包与计算。这样新增类型时可扩展分派,而不必让运行主循环处理每个细节。不支持的组合返回错误;类型判断成功也不自动保证除零或整数溢出等数值边界已受到保护,本章代码不能据此视为通用安全算术。
  • 布尔字面量用专门指令:布尔字面量只有两种,Monkey用无操作数的OpTrue和OpFalse直接把单例对象压栈,不必为每次引用携带两字节常量索引。这个设计减少常量池与编码开销,同时为布尔身份比较提供前提。它是有限固定值的专门化,不适合未经分析地推广到无限整数或任意字符串。
  • 重排操作数复用比较指令:编译器把a编译成先计算b、再计算a、最后执行大于比较,从而复用OpGreaterThan并缩小指令集。对纯值示例,比较结果相同;但这个具体实现同时改变了两边的求值顺序。如果表达式有副作用或错误,必须按语言规定检查是否仍语义等价,不能仅凭数学关系就无条件重排代码。
  • 整数内容与布尔身份比较:VM对两个整数先解包比较数值,对单例布尔则可比较对象引用。相同内容的独立整数对象不能用指针相等替代值相等,所以比较入口应先处理整数分支,再处理依赖单例的路径。后续新增对象类型也要重新检查相等语义,不能默认当前的引用比较适用于全部类型。
  • 前缀编译先处理子树:前缀表达式的编译先递归生成右侧操作数代码,再发出OpBang或OpMinus。若只添加运算符分派而忘记遍历子树,编译结果连装载操作数的指令也会缺失。AST节点支持情况决定哪些子节点能被到达;叶节点处理器已有,并不意味着包裹它的新语法已经接通。
  • 真值取反属于语言语义:本章感叹号把False取反为True,其他已支持值取反为False,因此整数5也是真值。整数负号则要求操作数为整数,其他类型报错。两个前缀运算共用单操作数的栈形状,却有不同类型契约;后续加入Null时还需调整真值规则,不能把本章的临时类型集合当最终语义。
原书依据 · 9 处

第 4 章 条件语句

条件表达式把树状选择展开为平坦指令流。尚未知晓的目标先占位,分支完成后按字节偏移修补;VM按条件调整ip。每条分支必须向后续表达式提供同样形状的栈结果,无else时需要Null。

  • 平坦字节码用跳转表达分支:AST把条件与两条分支保存为子树,树遍历器可直接选择执行其中一棵;平坦字节码则必须显式改变指令指针。条件跳转在假时越过成立分支,无条件跳转在成立分支完成后越过备选分支。两者配合才能保证只执行一个分支,不能仅把两段指令按顺序拼起来。

  • 跳转位置以字节偏移计量:绝对跳转目标给出指令流中的位置,相对跳转给出相对于某个基点的距离。Monkey采用绝对字节偏移;一字节Pop与三字节Constant对后续位置的贡献不同。图中为了说明而采用的逐指令编号,不能直接替代真实字节布局;编码和反汇编必须使用一致坐标。

  • 前向跳转先占位再回填:生成条件跳转时,后面的分支还未编译,目标位置尚未知。编译器先发出含占位操作数的指令,保存其起始偏移;分支编译完成后,再用当前指令流长度计算真实目标并替换占位值。占位是内部构建状态,不能在发布给VM的最终代码中保留。

  • 原位修补依赖长度不变:本章changeOperand重新编码同一种操作码,再覆盖旧指令字节。这个办法依赖新旧指令等长,否则后续指令位置、已记录偏移与跳转目标都可能失效。更复杂的变长替换需要重新布局或独立IR等方案,不能只多复制几个字节而不更新相关位置。

  • 分支末值需要保留在栈上:Monkey的if是表达式,选中分支的最后一个表达式要作为整个if的值。编译分支时删除最后一条OpPop,使末值留栈;前面独立语句的Pop仍保留,防止临时结果累积。最后若整个if作为独立语句出现,外层表达式语句再清理一次,不能把内外两种清理职责混在一起。

  • 删除末指令同步发射记录:编译器记录最后和倒数第二条发射指令的操作码及起始位置。删除最后的Pop时,截短字节流,并把last恢复为previous,使后续判断仍对应当前指令流。这些辅助记录是派生状态,修改真实指令后必须同步;本章只支持一次末指令删除,不能假定两条记录等于任意编辑历史。

  • 空分支也要产生一个值:条件为假而没有else时,if仍是表达式,外层需要一个结果。若直接跳到外层Pop,栈上没有值就会下溢。编译器因此为缺少的备选路径插入OpNull,使任一正常分支都留下一个值;成立路径通过无条件跳转越过这条Null指令。控制流汇合处需要兼容的栈效果。

  • 新增空值影响所有消费者:加入Null不仅是新增一个压栈指令。由于表达式可嵌套,Null还可能成为感叹号操作数或另一个if的条件;因此取反应得到True,真值判断应把Null视为假。新增类型会改变既有运算的输入集合,必须追踪消费该类型的地方,而不能只验证产生它的分支。

  • 跳转执行补偿循环自增:VM主循环结尾会将ip加一,所以跳到目标pos时,分支内部先设置ip=pos-1。条件跳转还要解码并跳过两字节操作数,然后弹出条件,仅在条件为假时改目标。不跳转路径同样必须越过操作数字节,否则下一轮会把数据误认成操作码。

原书依据 · 9 处

第 5 章 追踪名称

名称在编译期变成Scope与Index,实际对象值留在运行期存储中。符号表提供地址解释,globals提供值,两者不在同一阶段完成初始化。交互会话还要共同保留名称、常量池和全局对象,才能让下一行解释旧索引。

  • 名称解析与值存储分阶段:编译器把名称解析成作用域与槽位索引,VM再用索引存取实际对象。符号表保存的是名称含义的元信息,全局存储保存的是运行时值;两者不能互相代替。编译器与VM只需共享索引协议,执行阶段不必反复用名称字符串查表。

  • 符号表关联名称与元信息:符号表为名称关联结构化信息,例如作用域、索引、类型或来源位置。本章Symbol仅含Name、Scope、Index,Define建立关联并分配编号,Resolve查询关联并用布尔值表示是否存在。它不是求值器的环境映射:符号存在不意味着对应运行时槽位已经得到有效值。

  • 全局读写配对同一槽位:OpSetGlobal弹出栈顶对象,存入操作数指定的全局槽位;OpGetGlobal从同一槽位取对象并压栈。编译let右侧会先产生值,再发出Set;编译名称引用则解析符号索引并发出Get。写入与读取索引一致是绑定正确性的核心,不能只检查两种操作码都出现了。

  • 未定义名称可在编译时报错:遇到标识符时,编译器先Resolve名称,找不到就停止生成并返回未定义变量错误,从而无需等VM运行到该位置才发现名称不存在。不过这种检查只证明符号可解析,不证明控制流一定已经初始化该槽位,也不是完整的运行时值有效性证明。

  • 槽位宽度约束存储容量:全局读写指令用16位索引,可寻址65536个槽位,因此本章VM预先分配同等长度的全局存储。固定容量让索引直接映射到切片位置,但也形成表示上限。扩大容器本身不能扩大指令可表达的索引范围,符号编号、编码宽度与执行器边界必须共同设计。

  • 交互会话保留三组状态:跨行REPL需要同时保留符号表、全局对象存储和常量池。只保留名字而丢失全局值,引用会失效;只保留值而重建符号编号,名字可能指向错误槽位;丢失常量池又会让先前代码引用的常量索引失去含义。每轮可以新建编译器和VM外壳,但必须把会话状态显式传入。

  • 追加切片后更新持久引用:编译器向常量切片append后,可能分配新的底层数组并返回新的切片头。REPL必须在每次编译完成后用Bytecode.Constants更新自己保存的引用,再传给下一轮编译器;仅把初始切片传入一次不足以保证后续新增常量对会话可见。共享对象与共享切片头是不同的状态管理问题。

  • 符号定义不等于运行初始化:本章Define每次以numDefinitions分配新索引,再把名称映射更新为新Symbol。它没有实现同名定义去重,也没有记录该绑定是否在运行时被执行。阅读符号表时要区分“解析某次定义的元信息”与“该值已被初始化”;这些语义若要扩展,需要明确重定义和控制流规则,而非仅依赖map中有键。

原书依据 · 8 处

第 6 章 字符串、数组和哈希表

字符串可直接复用常量装载,数组和哈希则要在运行时把已计算的元素组合成对象。编译器负责元素顺序与数量,VM负责构造、键能力检查与索引语义。确定性编译与语言求值顺序需要分别判断。

  • 字符串复用常量与加法指令:字符串字面量可在编译时转为String对象放入常量池,因此继续使用OpConstant。连接两个字符串也复用OpAdd,但VM必须按操作数类型分派到字符串实现,并拒绝不支持的字符串运算。指令相同不意味着所有类型共享相同计算:编译器安排栈形状,运行时类型决定具体行为。
  • 集合字面量在运行时构造:数组和哈希字面量的成员可以是函数调用等任意表达式,所以通常不能只在编译期构造固定对象。编译器先发出计算成员的代码,再发出集合构造指令,让VM用实际运行结果组装。纯常量成员可能支持进一步优化,但不能因几个示例可预计算就假设所有集合字面量都是编译期常量。
  • 数组构造消费连续栈区间:OpArray的操作数是元素个数N。VM按原有顺序复制栈区间[sp-N,sp)中的对象到数组,再将sp减N,最后压入一个Array。空数组对应N=0,同样应产生一个对象而不消费已有元素。不能把反复pop得到的逆序直接当数组顺序;构造前后要核对栈净变化为1-N。
  • 哈希构造计数键和值:OpHash的操作数是栈上键和值的总个数,而不是键值对数量。编译每对时先键后值,VM以步长2重建HashPair,因此有效计数必须为偶数。这种约定省去运行时再翻倍,但宽度上限限制的是总元素数,不能误认为相同位宽允许同样多的键值对。
  • 确定性编译需要规定遍历顺序:哈希AST用Go map保存键值对,迭代顺序不稳定,会使常量池顺序和生成指令不稳定。本章先按键表达式的String表示排序,再依次编译键与值,使测试有可重复结果。这里规定的是实现的编译顺序,并非保留源文件书写顺序;包含副作用或重复求值键的语义需要另行明确,不能只把排序当无影响的测试技巧。
  • 可哈希能力在执行期检查:VM构造哈希时,先取得每对键和值,再检查键对象是否实现Hashable。可哈希对象用HashKey索引,并保存原始键和值供对象表示使用;不能作键时返回错误。语法阶段允许键表达式,并不保证它求出的对象可哈希,生成成功的字节码仍可能在执行时失败。
  • 索引指令与具体容器分离:编译索引表达式时,先计算被索引对象,再计算下标,最后发出无操作数OpIndex。VM先弹出下标,再弹出对象,按类型组合分派到数组或哈希。编译器负责生成正确的计算顺序,VM负责判断运行时容器和下标是否支持该操作;两层测试检查的是不同职责。
  • 缺失元素与错误类型分开:数组只接受整数下标,负数或越界返回Null;哈希要求下标可哈希,合法键不存在也返回Null。不可哈希键或不支持的容器/下标组合则返回错误。查不到值是一次合法查询的空结果,类型契约错误是操作无效,不能统一吞成Null;空集合、嵌套索引和计算所得下标都需覆盖。
原书依据 · 8 处

第 7 章 函数

函数代码存入CompiledFunction,调用时用Frame保存ip和basePointer。局部索引依靠本次基址映射到栈区,参数先占局部区前部,临时计算位于其上;返回同时恢复调用帧和栈活动范围。编译作用域隔离的是生成状态,调用帧隔离的是运行进度,二者不能混为一种环境。

  • 编译函数用对象承载独立指令:树遍历版Function保存AST,编译版CompiledFunction保存函数体的字节码。它仍实现运行时Object接口,可进入常量池、绑定给名称或作为结果返回。函数体指令与主程序指令必须分开,函数对象被加载不等于立即执行其函数体。后续闭包还会扩展这种表示,不能把当前的纯代码对象视为最终捕获环境方案。

  • 调用约定连接编译与执行:调用约定规定编译器如何摆放待调用对象、参数和结果,以及VM怎样消费和恢复它们。本章最初的无参调用先把函数压栈,再发出OpCall;返回时由VM移除被调函数并以结果替换。隐式清理属于约定的一部分,不需要调用者额外发Pop;加入实参后,布局也必须同步演进。

  • 显式与隐式返回统一为指令:显式return先计算返回表达式,再发出OpReturnValue;隐式返回则把函数体最后一个表达式后的OpPop改为同一返回指令。前面表达式的Pop仍要保留,避免积累临时值。两条源语法路径最终使用相同运行时机制,使VM无需再次辨认返回值来自哪种写法。

  • 无返回值函数仍产生空值:函数调用是表达式,因此空函数体或只做绑定的函数也应给调用者一个结果。编译器在不能产生OpReturnValue的结尾补OpReturn,VM据此退出函数并压入Null。OpReturn本身不从栈顶取返回值,不能把“没有返回值”当成调用之后栈上什么都不用留下。

  • 编译作用域隔离指令流:编译函数时进入新的CompilationScope,将指令流和最近发射记录与外层隔开;完成后取出内部指令,恢复外层作用域,把函数对象加入共享常量池。这样函数体不会混入主程序自动执行,也不会破坏外层用于末指令修补的记录。编译作用域首先服务代码生成,并不等于运行时调用帧。

  • 末指令查询先处理空作用域:隐式返回改写前要检查函数体最后一条指令,但空函数没有可检查的末项。lastInstructionIs先检查当前指令流是否为空,再查看发射记录,空时返回false。派生记录的默认操作码不能证明曾经发射过对应指令;处理零元素情形能让后续补OpReturn保持清晰。

  • 调用帧保存可恢复执行上下文:调用帧把函数代码引用与该次调用的指令指针放在一起。嵌套调用按后进先出压入帧,返回时弹出当前帧,先前帧中的位置自然成为恢复点。不同调用即使执行同一函数,也需要独立的执行进度;函数代码对象与一次调用的活动记录不能混为一物。

  • 主程序也采用调用帧:把主程序字节码也包装成函数并建立主帧后,VM主循环始终从currentFrame取指和更新ip,不必维护主程序与函数两套执行逻辑。初始ip设为-1,循环先加一再取第0字节。切换帧时只改变当前上下文,不能继续使用旧帧的局部ip或指令切片作为后续执行真源。

  • 返回同时恢复帧与操作数栈:在最初的无参、无局部绑定版本中,OpReturnValue先保存返回对象,再弹出调用帧和被调用函数,最后把结果压回调用者的操作数栈。帧栈恢复代码位置,操作数栈恢复表达式布局,两者缺一不可。后续有局部变量和实参时需按帧基址回收,不能把两次pop推广成所有调用的通用清理。

  • 头等函数来自统一值表示:函数对象遵循普通值的装载、绑定和返回协议,所以一个函数可返回另一个函数,再对结果调用。它不要求为每种组合新增一条专用操作码。头等函数与闭包仍有区别:能够传递代码对象,不代表已经捕获外层局部绑定;后者需要后续自由变量机制。

  • 局部索引的宽度限定单函数容量:OpSetLocal和OpGetLocal的操作数采用一字节,可表示0到255的局部槽索引;全局操作数仍采用两字节。编码宽度属于指令协议,Make、ReadOperands、反汇编和VM取指都须一致。索引有256个可选值,不等于所有以一字节编码的数量也能直接表示256,调用实参数量还要单独检查其表示范围。

  • 嵌套符号表区分名称的可见范围:函数进入编译作用域时创建带Outer的符号表,退出时恢复外表;每张局部表独立分配从零开始的索引。Resolve先查当前表,再查Outer,使局部名称遮蔽同名全局名称,而其他函数的同名局部名称互不影响。本章的递归查找还不构成闭包捕获;外层局部值的保存和装载需要后续自由变量机制。

  • 编译期统计局部槽供运行时预留:函数体编译完成、离开符号表前,编译器取出numDefinitions并写入CompiledFunction.NumLocals。VM凭这个元数据为每次调用预留局部槽,无需扫描字节码重新计算。加入参数后,参数先作为局部符号定义,因此NumLocals包含参数与let绑定,不能再额外把参数数量加一遍。

  • 帧基址把局部索引映射到栈槽:每次调用的Frame保存basePointer,同一个局部索引在不同调用中映射到不同的绝对栈位置:槽位置等于basePointer加localIndex。OpSetLocal把弹出的值存入该槽,OpGetLocal从该槽再压入工作栈。指令使用相对索引,调用帧提供本次执行的起点,因此代码可以在多次调用中复用。

  • 栈上局部区与临时工作区分开:VM令sp等于basePointer加NumLocals,为局部区留出空间,表达式临时值在其上方压入和弹出。移动sp只划出活动范围,并没有初始化每个槽,原书也明确可能残留旧值。因此这种布局解释了存储位置,不能单凭预留空间就声称读取未赋值局部变量是安全的。

  • 按基址回收整次调用的栈范围:返回先保存返回对象并弹出当前帧,再将sp设置为该帧basePointer减一,最后压入返回对象或Null。减一同时移除基址下的被调用函数,基址以上的参数、局部槽和临时值也退出活动栈。只弹出返回值与函数的旧逻辑在加入局部区后失效;恢复帧和恢复栈范围需要一起完成。

  • 参数是隐式创建的局部绑定:参数与let局部绑定具有相同的函数作用域和生命周期,区别在于参数的值由调用时布局建立。编译器进入函数作用域后先按声明顺序Define所有参数,再编译函数体,使参数占据从零开始的局部索引;函数体读取参数可以复用OpGetLocal,无需新增一套参数读取操作码。

  • 调用参数数量定位被调用对象:编译调用表达式时先压入函数,再按源顺序压入各实参;OpCall携带实参数量numArgs。由于sp指向下一个可写槽,被调用对象位于stack[sp-1-numArgs]。不能向下扫描寻找函数对象,因为实参本身也可能是函数。OpCall增加操作数字节后,编译器与VM的指令长度处理必须同步更新。

  • 调用基址必须落在第一个实参:实参已经位于函数对象之上并占据将来的局部槽,因此新帧basePointer应为调用前sp减numArgs,而不是直接复制sp。随后令sp等于basePointer加NumLocals,为剩余局部绑定预留空间。这样参数索引零对应第一个实参,返回时basePointer减一仍准确指向被调用对象的位置。

  • 在建立调用帧前验证参数数量:CompiledFunction单独保存NumParameters,VM取得调用对象后先比较实际numArgs与声明参数数目,不匹配就返回明确错误,再决定是否建立帧。NumLocals不能替代参数数量,因为它还包含函数体中的绑定。数量正确是栈布局解释成立的前提;报错并不意味着错误调用已清空参数,原书说明它们仍留在栈上。

原书依据 · 20 处

第 8 章 内置函数

内置函数由Go实现,但仍遵守Monkey函数值加实参加一次调用产生一项结果的协议。共享注册表提供稳定索引,BuiltinScope选择装载方式,VM在调用边界分派执行并统一空结果。复用REPL状态时必须保留相同的预定义名称。

  • 共享内置实现应放在共同依赖层:编译器、VM和树遍历求值器都需要内置函数时,将实现移动到共同依赖的object包,比让新执行器依赖旧求值器更直接,也避免复制后语言行为发生分歧。移动时同步迁移错误构造辅助函数,并用原求值器测试确认重构保留原有行为,再接入新调用路径。
  • 内置函数索引依赖稳定注册顺序:内置函数注册表使用名称与Builtin配对的切片,编译器按该顺序分配BuiltinScope索引,VM按同一索引装载函数。map的遍历顺序无法提供这个协议保证。若要持久化字节码,注册顺序改变还会影响旧索引含义;本书内存中的共同注册表不自动解决跨版本兼容。
  • 在执行器边界统一宿主空结果:共享内置函数以Go nil表示没有结果,求值器与VM分别把它转换成自身使用的Monkey Null对象。这样共享实现不依赖任一执行器私有的空值实例,函数调用在语言层仍产生一个值。转换应在调用边界完成,不能将宿主nil直接当作正常Monkey Object交给后续类型检查。
  • 内置名称使用独立符号作用域:BuiltinScope把内置名称与用户全局、局部槽区分开。DefineBuiltin接收注册表中既定索引,不增加普通局部或全局绑定计数;编译器初始化时预定义这些符号,嵌套表仍可向外解析。loadSymbol按Scope分别发出GetGlobal、GetLocal、GetBuiltin,二分式if-else已不能正确表达三种装载位置。
  • 统一调用协议容纳不同执行实现:内置函数仍以“被调用值、实参、OpCall”的形式参与调用;只有装载值时使用OpGetBuiltin。VM的executeCall检查被调用对象类型,分派到字节码函数或Go内置函数。源程序和编译调用表达式不必了解函数体由哪个执行机制完成,差异集中在执行器内部。
  • 内置调用一次替换函数与实参区:callBuiltin以stack[sp-numArgs:sp]提供参数,调用Go函数后将sp减去numArgs加一,移除实参与被调用对象,再压入结果或Null。它直接执行宿主函数,不像编译函数那样建立字节码调用帧。两条执行路径都满足一次调用产生一个栈结果的共同约定。
  • 错误对象与VM执行错误分属两层:本章内置函数对不支持的参数类型或错误数量返回*object.Error,并将该对象作为调用结果压栈;这与VM无法调用某个对象时返回Go error不同。测试分别核对错误对象类型及消息。读代码时应明确失败通过语言值还是执行器返回错误传播,不能因二者都有错误文字而混为同一控制流程。
  • 替换初始化状态会覆盖预注册内容:compiler.New预定义内置符号,但REPL通过NewWithState替换了新符号表,因而会丢失刚初始化的内置名称。解决方式是在REPL复用的外部符号表上同样注册内置函数。验证单次New的测试通过,不能证明注入既有状态的运行入口也保留相同初始化条件。
  • 数组扩展的复制不等于深复制:push分配新元素切片并复制旧元素,再附加新对象;rest也复制元素到新数组,保留原数组的元素序列。切片中保存的是Object接口值,copy并未递归克隆所有引用对象,因此这里保证的是数组容器不被原地追加或截去首项,不能扩展成任意嵌套对象都深度独立。
原书依据 · 9 处

第 9 章 闭包

闭包把固定代码与运行时捕获值合在一起,使定义时的局部数据在外层调用结束后仍可用。编译器解析FreeScope并安排逐层传值,VM构造Closure.Free,调用帧据当前闭包读取。自引用不能捕获尚未形成的自己,因此通过CurrentClosure从正在执行的帧取得对象。

  • 闭包把代码与运行时捕获分开形成:编译器生成函数字节码时还不知道参数或局部绑定的运行时值,因此不能像树遍历求值器那样同时保存当前环境。它先生成CompiledFunction及捕获指令,VM执行函数字面量对应的OpClosure时才把实际自由值与代码组合成Closure。编译期决定捕获哪些位置,运行期决定这些位置里的对象。

  • 自由变量需要相对于当前函数判断:同一个名称在外函数中可能是局部参数,在内函数中却是自由变量。闭包实现中的FreeScope用于外层局部绑定;全局与内置名称继续直接从公共存储装载,不必复制进Free。数学定义中的自由变量与此实现选择的捕获集合并不完全相同,必须结合存储位置理解。

  • 统一闭包表示减少执行器分支:所有用户函数统一包装成Closure,即使Free为空,调用帧也持有Closure并通过cl.Fn取指。CompiledFunction保留可共享代码和局部槽、参数数目,Closure保留一次构造所捕获的值。这样无捕获函数与真正闭包共用调用路径,但仍有包装分配和间接访问的成本,不应由此推断性能必然更好。

  • 闭包指令分开代码与捕获:OpClosure带两个操作数:两字节常量池索引与一字节自由值数量。代码位置的宽度与OpConstant一致,避免同一函数能加载却不能包装。第二项是数量而非索引,单字节直接编码范围为0到255;书中“256个自由变量”的说法不能替代对数量边界的校验。未使用某个操作数时也必须按完整长度推进ip。

  • 多层闭包需要逐层转交捕获值:最内层函数引用祖父函数的局部值时,中间函数也要把该值捕获为自己的Free项,即使自己的计算表达式不直接使用它。创建最内层闭包时,中间函数用OpGetFree把它放回栈,再交给内层OpClosure。逐层转交让每个函数只依赖自身局部区、自由区和公共存储,避免持有已退出调用的栈槽。

  • 离开编译作用域后装载捕获来源:编译器在leaveScope前取出内部符号表的FreeSymbols和局部计数,离开后才遍历原始自由符号并loadSymbol。此时发出的加载指令属于外函数,随后OpClosure按同一顺序消费它们。若在内函数作用域发这些装载指令,就会把捕获准备放错执行位置,函数创建时仍得不到应保存的对象。

  • 捕获顺序是生产与读取的共同协议:VM从stack[sp-numFree+i]按低地址到高地址复制自由值到新切片,回收这段临时区,然后压入Closure。顺序必须与编译器FreeSymbols、装载指令及OpGetFree索引一致。捕获本身只是复制Object值到新切片,没有递归深复制对象;它保证捕获数组不依赖被回收的栈槽,而不是任意对象内容都不可变化。

  • 自由值从当前闭包读取:OpGetFree以一字节索引访问currentFrame().cl.Free并把对象压入工作栈。它不再尝试从定义时外函数的basePointer读取,因为那个调用可能早已返回,原栈区也可能复用。Frame必须持有本次调用的Closure,只有CompiledFunction代码指针不足以区分同一代码在不同构造时捕获的值。

  • 定义名称不等于形成闭包:让let先Define名称再编译右值,可使函数体编译时解析到自己的名称。全局递归因此可工作,但局部递归仍可能失败:创建闭包时要捕获的自引用值尚未通过OpSetLocal写入槽位。编译期名称存在与运行期值已初始化是不同条件,必须分别验证。

  • 自引用不能捕获未成闭包:局部递归若被当作普通自由变量,会产生GetLocal、Closure、SetLocal的顺序,在闭包对象形成前读取将来保存它的槽,因此捕获nil。问题并非缺少指令,而是数据建立顺序形成循环依赖。字节码转储能直接暴露先读后写,比只看最终“不可调用”错误更能定位原因。

  • 当前闭包解开自引用循环:对函数自身名称的引用发出无操作数OpCurrentClosure,VM直接从当前Frame取得正在执行的Closure并压栈。递归调用发生时闭包已经存在,所以不必在创建闭包时捕获自己。这个机制保留同一Closure携带的自由值,不能替换成只从常量池重新构造一个空环境函数。

  • 函数名元数据识别自引用:parseLetStatement发现右值是FunctionLiteral时把绑定名写入Name;编译器进入函数作用域后将它定义为FunctionScope符号,loadSymbol据此生成CurrentClosure。后续同名普通绑定可覆盖store中的函数名,应按新绑定解析。原书遮蔽测试示例的expected仍写FunctionScope,与其说明和Define覆盖机制冲突,不能照抄为遮蔽语义。

  • 组合测试揭示初始化缺口:全局递归测试和嵌套函数测试分别通过,不代表局部递归也正确。把递归函数定义在另一函数内部,会让自引用进入自由值捕获路径,暴露尚未初始化的槽。测试组合应围绕共享状态与执行顺序的交点挑选,而不是仅对每项功能各举一个成功例子。

  • 解析自由名称同时保存原始符号:Resolve在当前表找不到名称时递归查询Outer;无法解析就保留失败,全局和内置符号直接返回,其他外层符号经defineFree转换为当前表的FreeScope符号。FreeSymbols同时保存外层原始符号,store缓存转换后符号。内函数据新索引读取Free,外函数据原始Scope和Index知道如何装载被捕获值。

原书依据 · 14 处

第 10 章 最后的测试

最后用递归斐波那契串联分支、参数、递归与返回,并比较两种执行策略。这个工作负载能作为集成示例,却不能替代生产性能评估;测量是否包含编译阶段也会改变结论含义。

  • 微基准不能代表生产性能:递归斐波那契可检验函数、分支与递归协作,也能比较特定实现上的执行开销,但不能代表生产工作负载。本书示例还在编译完成后才启动VM计时,因此测到的是运行阶段,而非解析加编译加执行的端到端耗时。使用其约三倍结果时必须保留程序、环境和计时边界。
原书依据 · 1 处

跨章联系与边界

栈效果贯穿所有章节:二元运算用两个值换一个值,条件分支保留选中结果,集合用若干元素换一个容器,函数用被调对象与实参换一个结果。按这一统一视角追踪sp,比只记每个操作码的实现更容易看出清理缺口。帧栈则负责代码位置,两种栈的职责互补。

符号表也逐渐从“名称到全局槽”演变为位置说明:Global、Local、Builtin、Free与Function分别指向不同装载方式。名称能够解析只说明编译期存在一条路径,不证明运行时槽已经写入;局部递归正是这个区别的反例。闭包保存的Object值也不等同于任意可变对象的深复制。

这是教学实现。编码器的输入假设、单字节数量边界、栈与帧容量、畸形字节码处理,以及原书遮蔽测试中可见的预期冲突,都不能被测试成功文字抹去。性能数字还须保留程序、硬件与计时范围,不能把运行期快直接推断为端到端快。

实践与延伸

读者延伸采用两条有限路线:Lua闭包实现深读(路径:ideas/idea-001-Lua闭包实现深读.md)已核验官方源码入口并形成首轮机制映射;调用边界测试观察(路径:ideas/idea-002-调用边界测试观察.md)交付书内测试与反例的观察计划。两项均未声称已完成全量源码阅读或实际运行测量。

生成进度与管理记录

用Go语言自制编译器

Skill 版本:v24

执行模式:light

建档进度:done

四象限:经典原理(高浓度、高稳定性)

理由:高浓度、高稳定性(经典原理,全文阅读确认)。编译与执行分离、字节码协议、栈帧和闭包实现具有耐久性;具体性能数字仅限书内环境与样例。

整书笔记

章节进度追踪表

章节号 章节标题 状态(pending/done) 卡片数
04 前言 done 1
05 第 1 章 编译器与虚拟机 done 15
06 第 2 章 你好,字节码! done 13
07 第 3 章 编译表达式 done 9
08 第 4 章 条件语句 done 9
09 第 5 章 追踪名称 done 8
10 第 6 章 字符串、数组和哈希表 done 8
11 第 7 章 函数 done 20
12 第 8 章 内置函数 done 9
13 第 9 章 闭包 done 14
14 第 10 章 最后的测试 done 1

非正文排除

spine项 类型 排除理由
1 cover.xhtml 封面 无正文文本
2 copyright.xhtml 版权 已读取并用于出版元数据,不含技术论述
3 epub_0002.html 致谢 已全文读取,仅感谢家人和审读者
15 epub_0014.html 作者简介 已全文读取,仅作者职业履历

待关联术语

术语名 出现章节 一句话语境
direnv 04 早于Go1.13工具环境的辅助选择,未展开原理

引用文献

标题 类型(书/论文/框架/源码项目) 出现章节 一句话语境
用Go语言自制解释器 书 04 本书复用其第4章结束后的前端与对象系统,宏系统不在本书范围
GNU Guile 源码项目 13 闭包设计参考,未展开其源码
Lua 源码项目 13 闭包实现参考及读者实践入口
Wren 源码项目 13 实现灵感,未展开源码
Matt Might的闭包编译文章 论文 13 深入学习入口,书中纯提名

资金安全问题案例

问题标题 问题卡 解决方案卡(如有) 出现章节 一句话说明

实践卡进度

序号 实践标题 实践方式 状态(pending/done) 关联章节 产出

| 1 | Lua闭包实现深读 | 实现深读 | done | 13 | ideas/idea-001-Lua闭包实现深读.md及首轮映射 | | 2 | 调用边界测试观察 | 其他 | done | 11–13 | ideas/idea-002-调用边界测试观察.md,计划未执行 |

实践候选筛选:done

未采用:重写完整VM与现有深读目标重复;生产性能复测缺少真实负载,不能用斐波那契代替。

轻量模式未执行复核、独立审查及审查结果优化;导入、归档与验收证据见_workflow.md。

相关主题

从本书的主题进入跨书阅读,对照其他书籍的讲解。下方数量包含主题关联的全部卡片与书籍。

暂无公开主题。