此笔记位置已失效,请从目录继续阅读。
全书导读
本书以 Monkey 教学语言为对象,从字符识别逐步建立语法结构和运行含义,最终加入集合与宏。Go 是实现载体;解释器的设计原理是学习主线。全文从前言到宏系统依次展开。它用可以看见输入输出的测试推进每一层,但最终交付的是教学解释器:诊断、字符集、哈希碰撞、宏卫生和若干错误路径仍有限制。学习时应区分机制已经成立与生产防御已经完整。
全书主线
源代码最初只是字符。词法分析为字符片段赋予类别,使语法分析器不必反复识别名称和符号。语法分析器再依据优先级和语法规则把这些片段组织成AST;树的嵌套保存“谁属于谁”,而不是直接给出计算结果。
求值器沿树解释每类节点。运行时对象表示结果,环境把名称与对象联系起来。函数除代码外还保存定义环境,这使离开外层调用后的函数仍能访问捕获的绑定,形成闭包。返回值与错误则是需要改变执行方向的信号,必须传播到恰当的边界。
字符串、数组和哈希展示了如何扩展这条链路:新语法必须被识别和解析,新值必须有表示与运算规则。宏进一步利用已经建立的AST与求值器,在运行前生成新的程序结构。因此宏不是普通函数换一个关键字,而是改变实参何时执行、哪些代码进入最终程序。
flowchart LR
A[字符] --> B[词法单元]
B --> C[AST]
C --> D[可选宏展开]
D --> E[求值器]
F[环境中的名称绑定] --> E
E --> G[运行时对象与副作用]
前言
本部分解释为什么从零构建树遍历解释器。程序先变成结构,再取得运行含义;函数既是值,也可以接受其他函数。顺序学习使每一步都依赖前一步的输出。
- 树遍历解释器:树遍历解释器先把源代码转换成抽象语法树(AST),再按树的结构逐节点计算结果。AST 表示程序结构,求值器为结构赋予运行含义。Monkey 的教学实现把词法分析、语法分析、内部对象系统和求值器分开,便于观察字符如何逐步变成结果。这个结构只是解释器的一种实现:不能据此断言所有解释器都会先生成 AST。
- 头等函数与高阶函数:头等函数是可以像整数或字符串一样被传递的函数值。高阶函数则把函数作为参数,或者以函数为结果。Monkey 的 twice 接受函数 f 和数据 x,再计算 f(f(x)),因此是高阶函数。两者关联在于:当函数能作为值传递,函数就可以组合别的函数的行为,而不必把每一种操作写死在调用者中。
原书依据 · 2 处
第 1 章 词法分析
本部分解释如何把字符转为可供解析器使用的符号序列。首先确定 token 的表示,再给扫描器建立位置不变量,最后加入名称、数字、双字符符号和交互入口。下面各项分别解释职责、边界与实现约定。
- 词法与语法的分工:词法分析把字符流切成带类型的词法单元;语法分析再把这些单元组织成抽象语法树。词法分析识别“这是什么符号”,不负责证明这些符号组成了合法程序。因此,词法测试可以使用包含各种运算符的乱码,检查每个符号是否被识别;不能因词法分析成功就认定程序能运行。
- 空白处理取决于语言:空白是否可以丢弃,由被解释语言的语义决定。Monkey 里,空格和换行仅分隔词法单元,连续空白不改变代码含义,因此可以统一跳过;Python 等语言会让缩进或换行参与程序结构,扫描时就必须保留相应信息。迁移词法分析器时,应先确认语言规范,不能把“忽略空白”当成通用规则。
- 词法单元的类型与字面量:词法单元需要同时保留类型与字面量。类型告诉后续阶段应该怎样处理它,例如整数、标识符或右括号;字面量保留源代码中的具体文本,区分整数 5 与 10、名称 x 与 y。Monkey 的 Token.Literal 使用字符串,因此本章的整数 token 仍保存数字文本,数值转换留到后续阶段。不要把本章最初的概念示意误当成实现字段类型。
- EOF与非法字符:EOF 表示输入结束,后续解析器据此停止取词法单元;ILLEGAL 表示扫描到了当前语言无法识别的字符。结束是正常边界,非法字符是无法分类的输入,两者不能混成同一信号。即使当前演示程序忽略详细错误位置,保留这种区分也能让下一阶段知道是正常收尾还是遇到了未知输入。
- 扫描游标的推进约定:扫描器必须明确辅助函数返回时停在哪里。Monkey 的 readIdentifier 和 readNumber 会持续推进,直到当前字符已经不是该词法单元的一部分;所以 NextToken 应直接返回,不能再执行结尾的统一前移,否则会漏掉紧跟的分号或运算符。反之,单字符分支尚未消费下一个字符,需要统一前移。组合扫描函数时,返回位置约定比“每次都前移”更可靠。
- 前瞻不消费输入:前瞻是在不改变扫描状态的前提下观察后续字符。Monkey 的 peekChar 查看下一个字节,帮助区分 = 与 ==、! 与 !=;确认双字符词法单元后,才调用 readChar 消费第二个字符。把观察与消费分开,可以避免为了判断符号而提前移动游标,使下一次 NextToken 从错误位置开始。到达末尾时也要返回明确的结束哨兵。
- ASCII扫描器的边界:按字节递增的扫描器适用于本书限定的 ASCII 字符,却不能直接用来识别完整 Unicode 字符。UTF-8 中一个字符可能占多个字节,若仍按 input[i] 取得单字节,就可能把一个字符拆坏。支持 Unicode 不只是把 ch 改为 rune,还要改变读取与推进规则,并同步检查标识符判定等辅助函数。实现的简洁来自范围约束,不能把教学限制误写成语言通用能力。
- 关键字与标识符判别:关键字与标识符可能具有相同的字符形状,适合先按共同规则读取完整名称,再查关键字表。命中 let 或 fn 就返回对应的关键字类型,未命中则返回 IDENT。这样新增关键字通常只需增加表项及 token 类型,而不必复制读取名称的扫描循环。字符规则本身仍限制名称范围:本书的 isLetter 接受英文字母与下划线,不能自动推断它支持任意 Unicode 名称。
- REPL连接交互与执行:REPL 重复执行读取输入、求值、打印结果。第1章先搭建交互外壳:每次读一行,把该行交给词法分析器,打印词法单元直到 EOF;此时还没有真正的求值能力。之后可以沿用这个外壳加入语法分析与求值。分步搭建的用途是尽早获得可观察输出,不能把“能交互打印 token”当作完整解释器已经完成。
- 词法测试检查符号边界:词法分析测试可以把全部符号集中在不符合语言语法的输入里,因为它验证的是 token 序列,而非程序求值。检查项应包括类型和字面量,还要覆盖多位数字、换行、双字符运算符以及输入末尾;这些组合能够暴露游标偏移一位的问题。测试对象的职责决定预期:若强制每个测试输入都能执行,反而会限制对扫描边界的观察。
- 当前字符与读取位置:Monkey 的扫描器保留当前字符位置 position,以及下一次读取的位置 readPosition。readChar 先从后者取字符,再令 position 指向刚读取的位置,最后把 readPosition 加一。这样当前字符和下一字符的角色清楚分离,后续可实现不移动状态的前瞻。输入结束后使用零字节作哨兵,是这个教学实现的约定;它不是通用字符集方案。
- 错误位置改善诊断:将文件名、行号和列号保存在词法单元中,可以让后续语法错误报告指出具体位置。例如,“缺少分号”只能说明错误种类,而附带文件与位置后,使用者才能迅速定位。教学版省略这些信息以减少实现负担;在生产设计中应把诊断需要作为 token 表示的输入,不能因为演示代码省略了位置,就认为解析器不需要来源坐标。
第 2 章 语法分析
词法分析只给出符号序列,本章把它变成可求值的结构。先用语句确立程序骨架,再用Pratt算法安排表达式的组合,最后把条件、函数和调用纳入同一体系。以下按这一依赖关系展开。
- 抽象语法树保留结构:抽象语法树用节点和嵌套关系表示程序结构,省略只用于指导解析的某些标点、空白和括号。省略这些字符不等于丢掉求值顺序:顺序已经体现在树的父子关系中。AST没有适合所有语言的统一格式,节点的具体形状必须服务于该语言的语义。
- 解析生成器的输入输出:语法分析器生成器把语言的正式描述转换成解析器代码,后者运行时再把源代码变成语法树。上下文无关文法描述语句的构成规则,BNF或EBNF是书中提到的规则记法。生成器与解析器处在不同层次:前者生成处理程序,后者处理被解释语言的输入。
- 手写解析器的学习边界:手写解析器可以让学习者观察构造AST、推进token和报告错误的每一步,从而理解生成器解决什么问题。这个学习价值不保证生成的解析器适合生产;书中明确承认其正确性证明、错误检测和恢复存在限制。选择工具时,应区分理解机制的目标与生产正确性、健壮性的目标。
- 语句与表达式:本书以是否产生值区分表达式与语句。表达式可嵌入需要值的位置,例如字面量、调用和Monkey的if;let与return则承载绑定或控制动作。这个划分属于具体语言的设计,不应把其他语言的分类机械移植过来。判断一段语法能否出现在等号右边,需要看Monkey是否把它定义为表达式。
- 名称节点的语境复用:同一个名称表示可以出现在绑定处,也可以出现在取值处。Monkey用Identifier节点表示两者,减少节点种类;let中的Name用来记录绑定名称,而在表达式位置,Identifier表示读取对应的值。节点形状相同并不意味着执行行为相同,具体职责由它所在的语法位置决定。
- 递归下降构造语法树:递归下降从程序根开始,按当前token选择解析函数,再由这些函数递归构造子节点。解析函数返回局部AST后,外层循环把它接到程序中并继续处理输入。它自然地映射“整体包含哪些部分”的结构,但表达式还需要处理优先级,不能只靠按关键词依次分派。
- 匹配后再推进:expectPeek检查下一个token是否符合当前语法要求,只有匹配时才推进当前位置。这个动作同时确认语法并维护游标:例如let之后应是名称,名称之后应是等号。不匹配时记录预期与实际类型,使调用方可以拒绝构造不完整节点。不要把普通的无副作用前瞻与这种成功时会消费token的断言混淆。
- 解析错误需要显式检查:若解析失败只返回nil,顶层循环可能忽略该语句,使错误输入看起来只是少了一个节点。Monkey另外维护错误列表,解析器调用方和测试先检查该列表,再使用AST。错误与部分结果可以同时存在,因此“有返回树”不足以证明解析成功。书中累积多个错误的演示也不构成完备错误恢复的证明。
- 表达式语句的包装:表达式语句把一个表达式包装成能放入程序语句序列的节点,使x+10这样单独出现的表达式合法。包装不改变表达式产生值的性质,只解决顶层结构如何统一存放的问题。这样Program可以保持语句列表,同时容纳let、return和独立表达式。
- AST打印用于结构测试:为AST节点实现递归的String表示,可以用带括号的文本观察实际分组,例如把a+b*c显示为(a+(b*c))。这种输出适合测试优先级与结合方向,而不是重建源文件的原始格式;AST已经省略部分空白和标点。结构化字段断言仍用于检查具体节点类型和内容。
- Pratt按位置选择处理:Pratt解析把处理函数关联到token类型,并按该token处于表达式开头还是已有左表达式之后选择处理方式。前缀函数不接收左操作数,中缀函数接收已经构造好的左表达式。同一个减号因此既能表示负号,也能表示减法,而不需要词法分析器区分这两种语法角色。
- 解析函数的游标协议:本书的解析协议要求:进入处理函数时,当前token是该表达式开始处理的位置;返回时,当前token停在已解析表达式的最后一个token。调用者根据这个约定决定是否继续推进,避免重复消费或漏读。单个标识符无需前移,复合表达式则可能递归消费多个token,但返回位置约定一致。
- 整数文本到数值的转换:词法阶段保存数字文本,语法阶段的parseIntegerLiteral再把文本转换为int64,并把结果存入AST节点。转换失败写入解析错误列表,不能只保存一个看似整数的节点而忽略错误。这种分层让扫描规则和数值表示分别处理;具体可接受范围仍受词法扫描规则与转换函数共同约束。
- 优先级表示相对关系:优先级常量的具体整数通常不重要,重要的是大小关系:本书让乘除高于加减、前缀运算高于普通算术、函数调用更高。解析器据此决定哪些子表达式应先组合。优先级决定语法结构,求值器随后依照该结构执行;它不是在词法阶段直接计算数值。
- Pratt循环扩展左表达式:Pratt先用前缀函数取得一个左表达式,再比较本层阈值与下一个运算符的优先级。只有后者更高时,才进入对应中缀函数,用已解析结果作左操作数继续组合。于是加法右边的乘法能在递归中先组成子树,外层再把它接到加法节点上。若无可用的中缀函数,则返回已有结果。
- 相等优先级产生左结合:解析1+2+3时,第一个加号递归解析右侧,并以加法优先级作阈值;下一个加号优先级相等,严格小于比较不成立,内层只返回2。外层再把1+2作为左侧接上第二个加号,得到(1+2)+3。结合方向来自递归阈值和比较规则,不能只看运算符的优先级排名。
- 右结合降低递归阈值:若希望a+b+c形成a+(b+c),需要让右侧递归继续接纳相同优先级的运算符。书中演示在解析加号右侧时把阈值减一,从而使后续加号进入内层。这个修改会改变原有左结合测试结果;它是说明机制的演示,不是Monkey默认加法规则。
- 分组表达式重置阈值:括号可改变表达式的组合方式,却不必对应一个独立AST节点。Monkey遇到表达式开头的左括号后,在括号内部以LOWEST重新解析,再要求匹配右括号,直接返回内部表达式树。括号的作用已经由嵌套树形保存,外层继续按自己的阈值处理,因此(5+5)*2的加法能先组合。
- 条件与块语句:块语句是一系列被大括号围住的语句,供if分支和函数体复用。if表达式包含条件、成立时的块和可选的else块;可选分支不存在时不应按缺失必需语法报错。块解析遇到右大括号或EOF停止,但提前遇到EOF只能说明已无输入,不能据此证明括号完整。
- 定义参数与调用参数:函数定义的参数列表是名称列表,函数调用的参数列表则是任意表达式列表。两者都需处理空列表、逗号和结束括号,但生成的节点类型不同。调用表达式的目标也可以是表达式,例如函数字面量,所以解析调用不能只接受一个固定函数名。
- 括号按位置区分职责:位于表达式开头的左括号启动分组解析;位于已解析表达式之后的左括号启动函数调用解析。Pratt把两种处理分别注册为同一token的前缀和中缀函数。调用还必须配置CALL优先级,仅注册处理函数不够,否则主循环可能不会进入该分支。语法角色取决于位置及绑定规则,而不只取决于字符。
- 交互解析不等于求值:RPPL读取一行代码,将其解析成AST,再打印AST的结构表示;它还没有计算程序的运行结果。交互入口先检查解析错误,有错误时输出诊断并继续下一轮,避免把不可靠的部分树当成成功结果。这个阶段可帮助观察优先级,但变量绑定与函数调用的运行语义要由后续求值器实现。
第 3 章 求值
语法树确定程序的组合方式,求值器则决定这些组合在运行时意味着什么。先建立值表示,再支持运算、分支和控制信号,随后用环境保存绑定,最后把环境与函数组合成闭包。错误和返回不是普通数值,它们需要沿递归传播到恰当边界。
- 求值决定运行语义:求值把AST结构变成运行行为:算术节点产生数值,条件节点选择分支,调用节点执行函数。语法正确的树本身并没有规定所有行为,例如参数先算左边还是右边、整数能否作为条件,都需要语言语义作出选择,并由求值器落实。测试应明确这些选择,避免把宿主语言的默认行为无意间当成被解释语言的规则。
- 求值策略的实现取舍:树遍历解释器直接访问AST并执行节点含义,容易构建和扩展,但执行结构不一定紧凑。字节码方案先转换成另一种中间表示,再由虚拟机执行;JIT进一步生成机器代码。后两种方式可能改善执行效率,却增加实现复杂度及体系结构适配工作。性能优势需要具体实现与测量支持,不能把书中的总体比较当成所有程序都成立的速度保证。
- 字节码需要虚拟机:字节码是一组供特定虚拟机理解的指令,可以包含入栈、出栈等操作。它不同于源语言的AST,也不同于CPU可以直接执行的本地机器码。虚拟机在这里模拟的是这套指令的执行规则,而不是必然模拟完整硬件。设计字节码时,表示密度、操作集合与执行器必须互相配合。
- 运行时值与语法节点:AST节点表示程序写了什么,运行时对象表示执行得到了什么。整数字面量节点可以转换成保存int64的整数对象,而名称随后绑定的是这个运行时值。对象系统在这里是“值的表示系统”,并不意味着Monkey是面向对象语言。把语法结构与运行时结果分开,求值器才能统一传递不同类型的值。
- 对象表示的设计约束:运行时值可以直接使用宿主语言原生类型,也可以包装成结构体或用其他编码表示。选择受宿主语言、被解释语言需要的数据种类、内存开销和执行速度共同约束。Monkey优先可读性,使用统一接口包住不同值;这个教学选择不能证明包装对象在所有解释器中都是性能最优方案。
- 字面量自求值:自求值表达式不需要查询名称绑定就能确定自己的值,例如整数5和布尔true。求值器把对应的AST字面量转为运行时对象。即使测试输入只有5,仍需从Program根经过表达式语句到达字面量;只实现处理整数节点的分支而不遍历外层结构,整程序求值仍会得到空结果。
- 单例布尔与空值:布尔值只有真、假两种,因此Monkey复用TRUE和FALSE对象,而不在每次求值时重新分配;空值同样复用NULL。这里的NULL是被解释语言中的一个明确值,不等同于求值器尚无结果的Go nil。复用减少了重复分配,也成为后面按对象身份判别布尔值的前提。
- 值相等与对象身份:对象身份相等是“是否同一个对象”,值相等则是“内容是否相同”。Monkey布尔值只有两个单例,可以用指针身份比较;两个整数5却可能来自不同分配,必须比较封装的int64。若把所有相等判断都写成指针比较,5==5可能错误地为假。分派顺序也重要:先处理整数内容比较,再处理可按单例身份比较的值。
- 真值与条件分支:Monkey把NULL和FALSE视为假,其余运行时值视为真;条件不要求本身就是布尔对象。条件表达式先求值,再只执行被选中的分支,避免另一分支的副作用。条件为假且没有else时返回NULL。这个真值规则属于Monkey的选择,不能直接套用到其他语言或把整数零默认视为假。
- 返回值需要穿过嵌套块:return不仅携带一个值,还要求停止当前语句序列。Monkey用ReturnValue包装该值,嵌套块遇到它时原样向上传播;如果内层块立即解包,外层会把它误当普通结果继续运行,覆盖真正应返回的值。程序边界或函数调用边界才负责解包,从而在正确的范围内结束执行。
- 错误创建与停止执行:运行时错误既要表达失败原因,也要阻止后续求值。Monkey将错误封装成Error对象,程序和块的求值循环遇到它就返回;每次递归求值子表达式后也要检查,避免把错误当普通操作数继续运算。只验证错误消息正确不够,还须检查错误之后的语句没有覆盖结果或产生副作用。
- 空值不能掩盖运算错误:“没有值”与“不支持这个操作”含义不同。Monkey早期为了搭骨架,把未知运算返回NULL;加入错误系统后,类型不匹配或未知运算应返回包含原因的Error。否则调用者无法区分合法的空结果与运算失败。这个演进提醒实现者:临时占位行为需要在完成错误协议时一并替换。
- 环境保存名称绑定:环境维护名称到运行时对象的映射。let先求出右侧表达式的值,确认无错误后才写入环境;标识符求值则查环境,找不到时报告名称未定义。环境传给递归Eval调用,使表达式能够访问同一组绑定。名称字符串与它当前绑定的值不是同一个东西,解析阶段识别出名称不代表运行时已经定义。
- 交互状态与测试隔离:交互解释器在输入循环外建立环境,使一行定义的名称能被后面的输入使用。测试辅助函数则每次创建新环境,避免前一个用例留下的绑定影响后一个用例。两者需要的生命周期不同:交互需要持续状态,独立测试需要隔离;不能为了统一调用方式把环境机械地做成全局变量。
- 调用先计算实参:Monkey调用时先求出函数目标,再从左到右求值实参,最后把所得对象交给函数。add(2+2,5+5)传入的是4和10,而不是两棵表达式树。某个实参出错后应停止,不再计算后续实参。这种顺序会影响包含副作用的程序,因此属于可观察的语言语义,而非随意的内部循环细节。
- 扩展环境保护外层绑定:函数调用需要把实参绑定到形参,但不能直接写进外层已有环境,否则同名形参会覆盖外面的变量。Monkey为每次调用建立一个新的空环境,放入形参绑定,并保留指向外层环境的引用;读取名称先查本层,缺失再向外查。这样局部名称能遮蔽外部名称,同时保留外层原来的值。
- 闭包保留定义时环境:闭包由函数代码及其定义时可访问的环境共同构成。Monkey求值函数字面量时,把当前环境引用放进Function.Env;调用时扩展这个定义环境,而不是调用者当前的环境。因此newAdder(2)返回的函数即使离开外层调用,仍可读取x=2。保存的是环境引用,不应把这个实现描述成自动复制所有变量的值。
- 函数边界解包返回值:块语句要传播ReturnValue,函数调用结束时则必须解包。如果让返回包装继续穿过调用边界,它会被外层函数误认为自己的return,导致外层提前停止。applyFunction因此先在扩展环境中求值函数体,再取出返回包装里的普通值。传播与解包各有职责,边界位置决定控制流是否正确。
- 宿主GC管理解释器对象:Monkey运行时对象由Go对象承载,因此当前教学实现借用Go的垃圾回收。临时整数和调用环境失去可达引用后,可以由宿主GC回收;闭包保留的环境仍可达,不能只因函数已经返回就宣称该环境可释放。GC减少手工管理负担,却不保证任何程序都不会耗尽内存:持续保留可达对象仍会增加内存占用。
第 4 章 扩展解释器
本章沿词法、语法、对象系统与求值器的路径接入字符串、数组和哈希,再用内置函数连接宿主能力。扩展复用了前面建立的表达式与调用框架,但各类型仍有自己的操作契约和失败边界。
- 扩展类型需要贯穿各层:新增语言类型通常不只是增加一个运行时结构体:还需要识别字面量token、构造AST节点、定义运行时值,并让求值器完成转换。字符串、数组与哈希沿同一链路接入,因此可用这条链路检查是否漏掉某层。已有词法符号或表达式列表解析可以复用,不应为了新类型重复整个前端。
- 字符串扫描的结束边界:Monkey用一个STRING token承载引号中的整段文本,避免后续解析器重新拼接文字与空白。扫描器遇到闭引号或输入结束时停止,但本书实现没有把缺少闭引号报告为错误,也没有完成转义字符支持。这是教学边界,不能把能够识别普通字符串等同于完整实现通用字符串字面量。
- 字符串运算比较内容:Monkey字符串求值复用Go字符串表示;连接操作先检查运算符,再取出两端字符串内容,产生一个新字符串对象。默认实现只支持加号连接,其他运算报错。如果扩展相等比较,应比较字符串内容,不能比较两个独立分配的对象指针。类型可以复用宿主表示,但运算语义仍须显式定义。
- 内置函数连接宿主能力:内置函数由解释器实现者用Go提供,接受运行时对象并返回运行时对象,把Monkey自身尚不能表达的能力暴露给用户。名称查找先检查用户环境,再查内置表,因此普通绑定可以遮蔽内置名称。调用分派区分用户函数和内置函数:前者建立环境并求值函数体,后者直接调用宿主函数。
- 内置函数校验调用契约:内置len先验证参数数量,再按对象类型分派,最后返回长度对象;错误数量和不支持的类型要产生Error。字符串分支实际调用Go的len,计算的是字节长度,不应凭英文示例概括成Unicode字符数;数组分支计算元素个数。同一函数名覆盖不同类型时,结果单位也需要解释清楚。
- 终止符参数复用列表解析:数组字面量和函数调用参数都是逗号分隔的表达式列表。把结束token作为parseExpressionList的参数,就能在方括号与圆括号之间复用解析循环,同时保留空列表、分隔符和闭合检查。这里复用的是相同语法结构,而不是因为两个功能名称相近就强行共享。
- 索引表达式的语义检查:数组索引的左侧与下标都可以先解析成表达式,例如returnsArray()[1]或a[1+1]。语法合法不代表运行时类型合格:求值器先计算左右表达式并传播错误,再要求数组配整数索引。Pratt还需给左方括号注册中缀函数并配置INDEX优先级,仅注册处理函数并不能保证索引被正确组合。
- 数组越界返回空值:Monkey选择对数组负下标和大于末尾的下标返回NULL,而不是抛出错误。实现先确认索引为整数,再比较0与len-1;空数组也会自然落入越界分支。这是一项语言语义选择,测试须覆盖首项、末项、负数和恰好等于长度,不能把其他语言的越界行为当作默认要求。
- 数组首尾与余项:first和last分别取数组首尾元素,空数组返回NULL。rest去掉第一个元素并返回新分配的数组:单元素数组得到空数组,空数组才得到NULL。这两个结果含义不同,递归处理列表时需要先用长度判断完成条件,避免把无剩余元素与无结果混为一谈。
- 复制数组保持原值:push分配长度多一的新数组,复制原元素,再加入新元素;rest也复制剩余元素。两者都不修改传入数组,因此同一个旧绑定仍可看到原有元素序列。这里复制的是元素对象引用,不是递归深拷贝所有对象;不可变接口与底层对象共享的区别需要保留。每次复制也有与数组长度相关的成本。
- 用基本数组操作组合高阶函数:map逐项取first,把函数作用于元素后push到累计数组,再对rest递归;reduce则把当前元素与累计值交给组合函数。空数组是结束条件。少量基础操作与头等函数就能组合出更高层行为,但这组教学实现会反复复制数组,不能仅因表达简洁就推断适合大数据量或具有线性总成本。
- 哈希键类型在运行时验证:哈希字面量的键和值在语法阶段都允许表达式。键最终能否使用,要看求值后的对象是否可哈希;否则名称表达式即使最终得到字符串,也会被过早拒绝。Monkey支持字符串、整数和布尔结果作键,其他对象报错。解析结构与判断运行时能力应分层处理。
- 哈希键不能使用对象身份:两个独立字符串对象即使内容相同,也有不同的指针身份。直接用对象指针作哈希键,会让插入时的name与查找时新建的name不能匹配。逐项比较内容可以补救,却退化为线性查找;Monkey改为从值生成可比较的HashKey,使等值对象能进入同一索引位置。
- 类型参与哈希键身份:Monkey的HashKey由对象类型和uint64值组成:布尔映射为0或1,整数转为uint64,字符串使用FNV结果。类型字段使布尔true与整数1即使数值部分相同也不会成为同一个键。复合键必须保留决定语义身份的维度,不能只比较一个散列数字。
- 哈希碰撞仍需处理:不同字符串仍可能产生相同的有限位宽哈希值。Monkey教学实现只用类型和哈希数字作map键,没有在命中后进一步区分碰撞的原始字符串,因此不能承诺所有不同字符串都能正确共存。书中提到链式法与开放寻址但未实现;这是适用边界,不应写成哈希函数已经消除碰撞。
- 原始键用于可读投影:HashKey适合索引查找,却不能替代用户原始键的展示。Monkey在HashPair里同时保存原始键对象和值对象,让Inspect能够打印可理解的键值内容。内部检索标识与外部可读表示各有职责;只存哈希数字会使展示或未来遍历接口丢失原始语义。
- 哈希缺键与不可哈希分开:哈希索引先要求下标对象实现Hashable,再计算HashKey查询映射。对象不能作键时返回Error;键合法但不存在时返回NULL。两种情况不能合并,因为前者违反调用契约,后者是合法查找的空结果。空表查询、不同支持类型与函数作键都需要独立观察。
- 打印副作用与返回值:puts逐个调用参数对象的Inspect并输出,每个参数独占一行;随后返回NULL。打印的文字是副作用,并不是函数返回的字符串。因此交互环境既可能显示Hello,又显示求值结果null。理解返回值与可观察副作用的区别,才能避免把屏幕输出误当成可绑定和继续计算的值。
第 5 章 遗失的篇章:Monkey的宏系统
宏把源代码当成结构化数据处理。本章先用quote暂停求值,用unquote局部恢复求值,再建立AST修改器,最终在运行前把宏调用替换成生成的代码。控制代码的构造与执行阶段是理解宏的主线。
- 文本宏与语法宏:文本宏主要在字符层面替换或生成代码;语法宏处理代码的结构化表示。Monkey已经把源程序解析成AST,因此语法宏可以把表达式作为数据传递、修改或生成,再交给求值器执行。两者的操作对象不同,不能把所有宏都理解成字符串拼接;语法宏的能力也取决于语言如何开放AST操作。
- quote阻止通常求值:quote返回表示参数代码的对象,而不是参数执行后的值。例如quote(4+4)保留加法AST,不计算为8。它必须在普通函数调用的实参求值之前被特殊处理;若仅注册成普通内置函数,实参已经求值,原始结构就丢失了。表面像调用的语法不保证具有普通函数的求值规则。
- unquote局部恢复求值:unquote在quote保留的代码中打开一个局部求值位置。quote(8+unquote(4+4))产生表示8+8的AST,外层加法仍不执行。unquote求值时使用当前环境,因此可读取名称绑定;它改变的是局部节点,不等于取消整段代码的引用状态。
- 值转回语法节点:Eval返回运行时对象,而AST修改器需要语法节点,所以unquote的结果不能直接塞回语法树。转换函数把整数、布尔值重建为对应字面量节点;如果结果本来就是Quote,则取出其中的节点。转换支持哪些类型,决定了哪些值可以被注入代码;不支持的情况需要明确错误处理。
- 引用代码可再次组合:Quote对象保存的AST可以通过unquote插入另一个quote,从已有结构构造新结构。例如一个分支注入计算所得8,另一个分支注入被引用的4+4,最终形成8+(4+4)的树。后者仍是代码而非已求出的8,理解这种阶段差异才能准确区分构造代码与执行代码。
- AST修改器遍历再替换:AST修改器先递归处理子节点,再把当前节点交给modifier,并返回modifier产生的节点。父节点必须接住递归返回值,才能支持将原节点替换成新节点;只调用modifier后仍返回旧节点,只能覆盖部分原地修改情形。叶节点虽无子节点,也仍需经过modifier处理。
- 结构遍历需要覆盖每个子项:树遍历的正确范围由每种节点的组成决定。条件表达式要访问条件、成立分支与可选分支;数组要访问全部元素;索引要访问对象与下标;函数要访问函数体及约定处理的参数。某种节点能正常打印不代表其内部已遍历,测试须在不同子项放入待替换节点来观察是否遗漏。
- 修改映射键需要重建:哈希字面量的键和值都是表达式,两边都可能包含待替换节点。Monkey修改器建立新的映射,将修改后的键和值重新插入,再替换原Pairs。不能只更新映射的值而忽略键中的表达式。测试也需检查实际键值内容,避免对指针键直接做深比较时误判结果。
- 宏展开位于解析与求值之间:Monkey宏展开在解析得到AST之后、运行时求值之前修改AST。这个位置让宏既能访问结构化代码,又能影响最终执行的程序。本章的实现先提取宏定义,再替换宏调用,最后求值修改后的树。这里描述的是Monkey管线,不应推断所有语言都只能采用同一种宏处理阶段。
- 宏定义提取与删除:DefineMacros识别顶层let绑定宏字面量的语句,把参数、函数体和定义环境存为宏对象,并从待运行AST中移除这些定义。删除时从末尾向前处理记录下标,避免前一次删除改变后续位置。此实现仅识别顶层字面量绑定,不会把另一个名称绑定到已有宏的别名语句当成新宏定义。
- 宏实参保留代码形态:普通函数调用先计算实参,宏调用则把实参AST包进Quote,绑定到扩展的宏环境,再求值宏体。宏体用quote构造新代码,用unquote取出参数代码,将结果替换原调用节点。这使宏能决定哪些实参代码进入最终程序,而非被迫在调用前执行全部实参。
- 宏返回值必须是代码:本章宏协议要求宏体求值结果为Quote对象,展开器取其Node替换调用。这样宏可直接返回复杂AST,不受“普通运行时值转字面量”能力的限制。教学实现对非Quote结果直接panic,说明错误协议尚不完善;不能把示例测试通过等同于可安全处理任意宏输入。
- 宏可以生成条件控制:unless宏生成取反条件的if树,再把两段分支代码插入对应位置,运行时只执行被选中的分支。如果写成普通函数,两个分支中的puts会在函数执行前作为实参先求值,无法保持条件执行。这说明扩展控制结构需要控制求值时机,而不只是把相同代码藏进一个函数。
- 宏环境与运行环境分开:REPL维护macroEnv保存宏定义,另用env保存运行时绑定。每行解析成Program后,先定义和展开宏,再把展开结果交给Eval。两个环境都要跨交互行保留,但用途和执行阶段不同;把宏定义当普通运行时对象处理会模糊代码构造与程序执行的边界。
- 语法规则限制宏表现力:Monkey把quote与unquote写成普通调用表达式的形状,因此参数只能是Expression,不能直接接收let或return语句。若要引用整个块,需要扩展语法并提供相应AST节点。宏能力不只由展开函数决定,前端允许表达哪些结构同样决定用户能生成哪些代码。
- 生成代码需要来源与诊断:AST改写不仅涉及替换子节点,还涉及父节点的token与来源信息是否一致。教学修改器不更新这些信息,可能使打印与节点内容不一致;动态生成的token也缺少可靠的原始位置。当前系统还忽略多处类型断言和转换失败,未讨论卫生宏,因此只能作为理解宏机制的起点。
跨章综合
第一条共同约束是边界协议。词法扫描要约定返回时游标停在哪,表达式解析要约定进入和返回时当前token的位置,求值要约定普通结果、返回包装和错误如何传播。各局部函数都可能看起来正确,但只要边界约定不一致,组合后就会漏字符、重复解析或错误地继续执行。
第二条约束是结构、值与身份不能混淆。AST保存程序结构,运行时对象保存执行结果;两个字符串对象可以内容相同却不是同一指针,因此哈希查找与相等运算必须按语义选择比较方式。quote与unquote又在这两个层次之间建立受控转换:先保留结构,再局部求值,必要时把结果变回结构。
第三条约束是阶段决定能力。用户函数通过运行时环境组合计算;宏通过展开环境组合代码。unless展示为什么普通函数无法接管实参的求值时机:调用之前两侧实参已经执行。宏先改写成if结构,让已有求值器负责只执行一个分支。语法、对象表示与阶段安排共同决定语言能表达什么。
这些联系也提示了实现边界:示例中可观察的成功路径不是通用正确性的证明。字符串未闭合、哈希碰撞、参数数量、AST来源和宏错误都需要单独的规则与验证。
发散与实践
以下为读者延伸和未执行的实践计划,不能作为作者已经验证的生产建议。优先阅读成熟实现以比较词法与语法边界,再用书中案例建立闭包和宏求值时机的观察矩阵。实践材料、限定范围及完成判据见ideas目录;本阶段交付计划,不声称已完成实测。