1. 编译器与虚拟机
正如“解释器”和“web 服务器”有多种实现一样，编译器和虚拟机本质上也是某种思想（模式），掌握核心思想，可以更好地理解虚拟机和编译器
1.1 编译器
可以编译的内容不止编程语言，还有正则表达式、数据库查询甚至 HTML 模板。
wiki 定义：
编译器是一种计算机程序，它会将某种编程语言写成的源代码（原始语言）转换成另一种编程语言（目标语言）。编译器是一种支持数字设备（主要是计算机）的编译器。编译主要是将源代码从高级编程语言转换为低级语言（例如汇编语言、目标代码或机器代码），以创建可执行程序
编译器本质上就是翻译器，翻译是它实现编程语言的方式
编程意味着对计算机发号施令。指令用计算机可以理解的编程语言编写。实现一种编程语言意味着让计算机理解它，有两种办法：1.为计算机即时解释编程语言；2.将编程语言翻译成计算机可以理解的另一种语言
编译器和解释器都有前端，用于读取源语言编写的源代码并将其解析为数据结构。前端通常由词法分析器和语法分析器构成，二者合作将源代码转换成语法树。在前端，编译器和解释器有很多相似之处，之后，它们都会遍历 AST，后续就不同了
解释器在遍历 AST 时，会进行求值，也就是直接执行树中编码的指令。
编译器则相反，它不会输出任何内容，而会以另一种语言（目标语言）生成源代码。源代码中包含源语言（如 puts）的等效目标语言，生成的代码由计算机执行
编译器以哪种目标语言生成源代码？计算机能理解哪种语言？编译器如何生成这种语言的代码？格式是文本还是二进制？在文件还是内存中？用目标语言生成什么？如果目标语言没有等效部分又如何替换？
这些都要根据实际情况改变，没有统一的答案
词法分析器和语法分析器对源代码进行标记和语法分析，这被称为前端，经过这个步骤，源代码从文本转换成 AST。
接着，被称为“优化器”（有时也被称为编译器）的组件将 AST 翻译成另一种中间表示（IR）。这个额外的 IR 可能是另一棵语法树，或者是二进制格式，甚至是文本格式。额外翻译成另一个 IR 的原因是多种多样的，主要的原因是 IR 可能比 AST 更适于优化和翻译成目标语言
然后，这个新 IR 进入优化阶段：消除死代码，预先计算简单的算术，移出循环体内的多余代码……
最后，代码生成器（也称为编译后端）以目标语言生成代码。这是编译真正起作用的步骤。
有的编译器会在 IR 上多次扫描，多次遍历，每次进行不同优化；有的不对 IR 优化，而是优化目标语言的源代码；有的只优化 AST；或 AST 和 IR 都优化；有的根本没优化；有的没 IR；有的不输出机器代码，而是输出汇编或其他高级语言；或者存在多个用于生成不同体系结构机器代码的后端。
更有甚者，不一定读取源代码并输出目标代码，也可以是接收 AST 并返回字符串的单个函数……
基本理念：编译器获取一种语言的源代码并转换成另一种语言的源代码。其他的大部分都是看情况而定
1.2 虚拟机与物理机
VMWare 和 VirtualBox 这类模拟计算机的程序，和我们这里说的虚拟机不同
我们这里讨论的是用来实现编程语言特性的虚拟机。它并不模拟已经存在的机器。它自身就是机器
“虚拟”体现在，它仅存于软件，不存在于软件，是纯抽象的构造
1.2.1 物理机
几乎每台计算机都遵循冯·诺依曼体系结构，该体系结构描述了一种用数量很少的组件构建功能强大的计算机的方法
在这个模型中，计算机包括两个核心部分：一个是包括算术逻辑单元（ALU）和多个处理器寄存器的处理单元，另一个是包括指令寄存器和程序计数器的控制单元。它们统一称为中央处理器，简称
CPU。除此之外，计算机还包括内存（RAM）、大容量存储（硬盘）和输入输出（I/O）设备（键盘和显示器）
在计算机打开的时候，CPU 执行以下操作：
- 从内存中预取指令。程序计数器告知 CPU 从内存的哪个位置获取下一条指令。
- 解析指令。甄别需要执行什么操作。
- 执行指令。可能会修改寄存器的内容，将数据从寄存器输出到内存，数据在内存中移动，生成输出，读取输入……
随后再次从 1 开始循环执行
以上称为取指-解码-执行周期，也称指令周期，“计算机的时钟速度以每秒的周期数表示，例如 500MHz”
我们重点关注 I/O 机制
CPU 如何处理内存的不同部分？如何知道在何处存储和检索内存中的内容？
首先了解如何取指。程序计数器始终追踪从何处获取下一条指令。“计数器”的字面意思是：计算机直接利用数字对内存中的不同部分进行寻址
计算机内存并非“数组元素”，而是被分隔成了一个个的“字”。“字”是计算机内存中的最小可寻址区域，是寻址时的基本单位。字的大小取决于 CPU 的类型，在我们使用的计算机中，标准字的大小是 32 位和 64 位
假设有一台虚构的计算机，字大小为 8 位，内存大小为 13 字节，内存中一个字可以包含一个 ASCII 字符
字母“H”的内存地址为 0，以此类推，可以通过内存地址 0~12 访问这些字母，如果将数字（内存地址）保存到内存中的另一个位置，就完成了一个指针的创建
现实的取值复杂得多
不同计算机字的大小不同，有 8、16、24、32、64 位。有时 CPU 使用字的大小与地址大小无关。还有些计算机采用字节寻址，而不是字寻址
如果使用字寻址，并希望寻址单字节，则不仅要处理不同的字长，还需要处理偏移量。这种操作开销很大，必须优化
而且，直接告诉 CPU 在内存中存储和检索数据的行为在概念上虽然正确，但是如今的内存访问是抽象化的，并且处于一层又一层的安全和性能优化问题之后。内存不再是能够随意访问的区域，安全规则和虚拟机内存机制会尽力组织这种情况发生
冯·诺依曼体系结构的创新在于，计算机的内存不仅包含数据，还包含由 CPU 指令构成的程序。
虽然这些程序与任何其他数据存储在相同的内存中，但它们通常不会存储在相同的位置。特定的内存区域用于存储特定的内容。不仅是因为约定俗成，更是受操作系统、CPU 和计算机体系结构其余部分的支配
“无意义数据”，如“文本文件的内容”或“HTTP 请求的响应”，位于内存的某个区域。构成程序的指令存储在另一个区域中，CPU 可以从该区域直接获取它们。此外，有一个区域保存程序使用的静态数据；还有一个区域是空的且未初始化，但属于保留区域，程序运行后就可以使用它。操作系统内核的指令在内存中也有自己的特定区域
程序和无意义数据都存在同一个内存中，实际上由指令构成的程序也是数据的一种。数据只有经过 CPU 从内存中预取、解码、确认正确并执行这一过程，才会成为指令。如果 CPU 解码的数据不是有效的指令，后果取决于 CPU 的设计，有的会触发事件并给程序一次发送正确指令的机会，有的会直接停止执行程序。
这是一个特定的内存区域，用于存放栈
栈是内存的一个区域，以后进先出（LIFO）的方式管理数据，以压栈和弹栈实现数据的伸缩。栈的目的是实现调用栈
我们拥有一个内存区域，CPU 以 LIFO 方式访问和存储其中的数据，这是为了实现专门的栈，叫调用栈
为什么需要调用栈？因为 CPU 需要追踪某些信息才能执行程序。追踪什么信息？最重要的是当前正在执行哪个函数，以及接下来执行哪个指令。当前函数之后需要执行的指令信息，被称为返回地址。这是 CPU 执行当前函数之后返回的地方。如果没有这个消息，CPU 只会把程序计数器+1 并执行下一高地址处的指令。但是指令在内存中并不是按照执行顺序存放的。想象一下，如果 go 的 return 丢失了发生什么————这就是 CPU 需要追踪返回地址的原因。调用栈还有助于保存函数局部的执行相关数据：函数调用的参数和仅在函数中使用的局部变量
返回地址、参数和局部变量，理论上可以将这些信息保存在内存中其他合适的可访问区域。但是用栈来保存是完美的解决方案，因为函数调用通常是嵌套的。但进入一个函数时，相关数据被压栈。执行当前函数时，就不必通过调用外部函数来访问局部化相关数据，只需要访问栈顶相关元素即可。如果当前函数返回，则将局部化相关数据弹栈（因为不再使用）。现在栈顶保留的是所调用外部函数的局部化相关数据
为什么叫栈？因为使用这个内存区域来实现调用栈是一个牢固而广泛的约定，要注意现在它已被转换为硬件。甚至某些 CPU 仅支持压栈和弹栈的指令。在它们上面运行的程序都以这种方式使用这个内存区域来实现此机制
调用栈只是一个概念，不受特定内存区域特定实现的约束。没有硬件和操作系统强制支持和约束时，在内存中的任何一个区域都可以实现调用栈。而我们将自己实现一个虚拟调用栈。此外，还有一个概念：
当执行一个程序，CPU 访问这个内存区域的频率。肯定很高，这说明 CPU 访问内存的速度决定了程序运行的速度。虽然内存访问速度很快，但是不是即时，仍然有成本
此时需要在另一个地方存储数据：处理器寄存器。寄存器是 CPU 的一部分，访问寄存器的速度远快于访问内存的速度。寄存器的数目很小，而且不能容纳和内存一样多的数据，通常每个寄存器只能存储一个字。比如 x86-64 架构的 CPU 包含 16 个通用寄存器，每个寄存器可以存储 64 位数据
寄存器用于存储小且被经常访问的数据。例如，指向张顶部的内存地址通常存储在寄存器中。因为这种用法很普遍，以至于大多数 CPU 有一个专门用于存储该指针的指定寄存器，即所谓的栈指针。某些 CPU 指令的操作数和结果也可以存储在寄存器中。如果经常访问某一程序中的大量数据，则可以将其地址存储到寄存器中，这样 CPU 就可以快速访问它。
1.2.2 什么是虚拟机
虚拟机是由软件实现的计算机。是模拟计算机工作的软件实体。
虚拟机跟物理机一样，有特定的运行循环，即通过循环执行“取指-解码-执行”来完成运转。它有一个程序计数器，可以获取指令，然后解析并执行它。它拥有栈，有时是调用栈，有时是寄存器。所有一切全部内置在软件中。
let virtualMachine = function (program) {
let programCounter = 0
let stack = []
let stackPointer = 0
while (programCounter < program.length) {
let currentInstruction = program[programCounter]
switch (currentInstruction) {
case 'PUSH':
stack[stackPointer] = program[programCounter + 1]
stackPointer++
programCounter++
break
case 'ADD':
right = stack[stackPointer - 1]
stackPointer--
left = stack[stackPointer - 1]
stackPointer--
stack[stackPointer] = left + right
stackPointer++
break
case 'MINUS':
right = stack[stackPointer - 1]
stackPointer--
left = stack[stackPointer - 1]
stackPointer--
stack[stackPointer] = left - right
stackPointer++
break
}
programCounter++
}
console.log('stacktop: ', stack[stackPointer - 1])
}
这个用 js 写的虚拟机有一个程序计数器 programCounter、一个栈 stack，以及一个栈指针 stackPointer。有一个运行循环，先取出程序计数器指向的指令，然后解析并运行它。这个循环每迭代一次，就是虚拟机的一个“循环周期”
// (3 + 4) - 5
let program = ['PUSH', 3, 'PUSH', 4, 'ADD', 'PUSH', 5, 'MINUS']
virtualMachine(program)
不同虚拟机最主要的区别就是功能和性能的不同选择
一个重要的设计选择是使用栈式虚拟机还是寄存器式虚拟机，这个选择非常重要，也因为虚拟机就是根据此架构进行分类的。简单来说，二者的区别是：虚拟机是利用栈还是利用寄存器（虚拟）来完成计算。
一般认为栈式虚拟机及其相应的编译器跟易于构建。需要的组件更少，指向的指令也更简单，因为仅使用了栈。缺点在于，需要执行指令的频率更高，因为所有操作必须通过压栈和弹栈才能完成。这限制了人们可以采用性能优化的基本规则的程度：与其尝试做得更快，不如先尝试做得更少。
构建寄存器式虚拟机需要更多工作，因为寄存器是辅助添加的，他也有栈，但是没有那么频繁地使用，只是仍然有必要实现调用栈。优点是指令可以使用寄存器，和栈式相比，指令密度更高。指令可以直接使用寄存器，而不必将它们放到栈上，保证压栈和弹栈的顺序正确。与栈式相比，寄存器式虚拟机使用的指令更少，带来更好的性能，但是构建这种产生密集指令的编译器需要花费更多精力。
构建虚拟机还涉及很多决策，比如如何使用内存，如何确定值的中间表示
上面的例子使用 switch 完成虚拟机运行循环中的分派工作。分派意味着在指令执行之前，为该指令选择一个合理的实现。
当寻求更高的性能时，分派会使用跳转表、GOTO 表达式、使用直接或间接的线程代码，在 case 分支足够多的情况下，switch 可能是所有方案中最慢的一种。
1.2.3 为什么要构建虚拟机
我们希望一门编程语言是通用的，通用计算是我们的目标，如果这么看，则虚拟机是拥有和计算机相同的计算能力，并且是执行程序最快的方式之一
但是为什么不直接使用计算机自身来执行，而是用虚拟机，答案是：可移植性。不需要为不同的计算机架构都设计新的编译器，而是将程序转换成虚拟机指令。
虚拟机是领域特定的，计算机是计算的通用解决方案，当不是领域特定的。
虚拟机就像一台定制计算机，优化成只能使用单一的编程语言。所有不需要的功能都被裁剪，剩下的都是高度专业化的功能，不再像计算机一样通用，但功能更集中
1.2.4 字节码
虚拟机执行字节码，就像计算机执行机器码，字节码也是由机器指令构成，之所以叫字节码，是因为所有指令的操作码大小均为一字节
“操作码”是指令的“操作”部分。前文提到的 PUSH 也是一种操作码，但是在示例代码中它是多字节操作码，不是一字节。在正常实现中，PUSH 只是一个引用操作码的名称，该操作码本身是一字节宽的。这些名称被称为助记符，为了帮助程序员记住操作码而设计出来。
操作码的操作数（也称作参数）也包含在字节码中。操作数紧跟着操作码，它们并列在一起。操作数的大小不一定是一字节。如果操作数是一个大于 255 的整数，就需要多个字节来表示。有些操作码有多个操作数，有些只有一个，有些没有操作数。
可以把字节码想象成一系列的操作码和操作数，一个接一个并排分布在内存中。
字节码是几乎毫无可读性的二进制格式。助记符不会出现在实际的字节码中，取而代之的是它所引用的操作码，这些操作码以数字表示，具体是什么数字取决于定义字节码的人。
操作数同样依赖于它自身的值决定用多少字节来进行编码。如果需要多字节表示，编码顺序就格外重要。目前有两种编码顺序：大端编码和小端编码。小端编码的意思是原始数据中的低位放在最前面并存储在最低的内存中。大端编码则相反：高位存储在最低的内存中。
假设我们将助记符 PUSH 用 1 表示，ADD 用 2 表示，整数用大端存储。
将人类可读的字节码转换成二进制数据，由汇编器完成。汇编语言是字节码的可读版本，包含助记符和可读操作数，汇编器能将其转换为二进制字节码。反之，将二进制表示转换成可读表示的程序，称为反汇编器。
字节码是一种领域特定语言，是定制虚拟机的定制机器语言。不是通用的，不必支持所有的情况。只需支持可以编译为字节码的源语言所需的功能。
字节码还包括领域特定虚拟机上下文中才有的领域特定指令。例如 JVM 的字节码包含：invokeinterface 用于调用接口方法，getstatic 用于获取类的静态字段，new 用于为指定的类创建对象。Ruby 字节码有：putself 用于将 self 压入栈，send 用于向对象发送消息，putobject 用于将对象压入栈。lua 字节码有访问和操作表和元组的专用指令。在 x86-64 的通用指令集中找不到以上任何命令。
这种通过使用自定义字节码格式实现专业化的能力是构建虚拟机的重要原因之一。不仅使编译、维护和调试变得更容易，而且代码也更密集，因为它表达某些内容所使用的指令更少，从而使代码执行更快
1.3 虚拟机和编译器的二元性
我们将同时构建虚拟机与编译器
如果优先构建编译器并定义字节码，那么在不知道后续虚拟机如何执行它时，很难理解当下的事情为什么如此。在编译器之前构建虚拟机也有缺陷，因为字节码需要实现定义，虚拟机才能执行。如果不仔细查看字节码旨在表示的源语言结构，很难提取定义字节码，这意味着无论如何都要优先构建编译器。
2. 你好，字节码！
本章目标：
- 可以接受表达式 1 + 2 作为输入
- 利用已有的 lexer、token、parser 对表达式进行标记和语法分析
- 生成 AST，其节点定义在 ast 包中
- 将字节码作为新构建虚拟机的输入，并由虚拟机执行
- 确保虚拟机输出结果 3
2.1 第一条指令
我们将建造栈式虚拟机，主要是为了方便学习而考虑
为了编译执行 1 + 2，需要将其翻译成使用栈的字节码指令。
- 将 1 压入栈中
- 将 2 压入栈中
- 将栈顶两个元素相加
需要定义两种指令，一个是将某些内容压入栈中，一个是将已经存入栈中的内容相加
实现流程：首先，定义它们的操作码以及它们在字节码中的编码方式。然后扩展编译器，用于生成这些指令。当编译器知道如何生成指令时，就可以构建解码并执行指令的虚拟机
2.1.1 以字节作为开端
字节码由指令组成，指令是一系列字节，单条指令由操作码和可选操作数组成。一个操作码的长度正好是一字节，具有任意当唯一的值，并且操作码是指令的第一字节。
// code/code.go
package code
type Instructions []byte
type Opcode byte
Instructions 是字节集合，操作码 Opcode 长度为 1 字节。但是这里缺失两个定义：
- Instruction（单数），不定义为[]byte，因为这样更容易在 Go 类型系统里传参。否则会频繁使用 byte，而且 Instruction 的类型断言和转换会变得很繁琐
- 没有定义 Bytecode，代表对字节码的描述，告知我们它是由指令组成，但是如果在 code 里定义这个参数，会产生循环导入（依赖）问题，之后将在编译器的包里定义
接下来定义压栈的操作码，不过其实不需要定义
如果定义一个操作数为整数的‘push’指令来实现压栈，可以将整数操作数获取并压栈，对于整数来说很容易，因为整数编码很简单，可以直接放入字节码中。但是如果是其他内容，比如字符串字面量，虽然也是字节组成，可以放入字节码，但是会导致字节码变得臃肿和笨拙
此时需要用到常量（常量表达式），指的是值不发生变化且在编译时可以确定的表达式。
这意味着我们无需通过运行程序就知道这些表达式的求值结果。编译器可以在代码中找到它们并存储它们的值。随后，编译器可以在生成的指令中引用常量，而不是将值嵌入其中。‘引用’是将一个普通的整数作为常量池的索引来完成工作。常量池是保存所有常量的数据结构
这才是编译器要做的。在编译过程遇到整数字面量（常量表达式）时，我们会对它进行求值，然后将其存储在内存中并为它分配一个数字来追踪结果*object.Integer。
在字节码指令中，我们通过这个数字来引用*object.Integer。完成编译并将指令传给虚拟机执行时，在编译期间找到的所有常量都会被统一存入数据结构（常量池），其中分配给每个常量的数字就是它在常量池中的索引。
回到第一个操作码的定义。他应该称为 OpConstant 且有一个操作数————之前分配给常量的数字。虚拟机执行 OpConstatn 时，它使用操作数作为索引检索常量并压栈。
// code/code.go
// [...]
// 操作码定义
const (
OpConstant OpCode = iota
)
以后每个操作码都以 Op 作为前缀，引用的值由 iota 递增生成，因为不需要关注操作码代表的实际值。只需要彼此不同且大小为 1 字节。
这个定义缺少 OpConstant 的操作数部分，因为我们在编译器和虚拟机之间隐式共享这个知识点。但是为了方便调试，最好能方便地查找操作码有多少个操作数以及他们的可读名称是什么。
// code/code.go
import (
"fmt"
)
type Definition struct {
Name string
OperandWidths []int
}
var definitions = map[Opcode]*Definition{
OpConstant: {"OpConstant", []int{2}},
}
func Lookup(op byte) (*Definition, error) {
def, ok := definitions[Opcode(op)]
if !ok {
return nil, fmt.Errorf("opcode %d undefined", op)
}
return def, nil
}
操作码 Opcode 的 Definition 有两个字段：Name 和 OperandWidths。Name 使操作码可读性更强，OperandWidths 包含每个操作数占用的字节数
OpConstant 定义显示，它唯一的操作数有两字节宽，这表示它的类型是 uint16，最大值为 65535，算上 0，可以表示 65536 个数。使用 uint16 而非 uint32 可以让生成的指令更小，因为使用的字节更少
现在构建第一条字节码指令。如果不涉及任何操作数，则只需简单地将 Opcode 加入到 Instructions 切片中即可。但是 OpConstant 需要正确编码两字节宽的操作数。
为此，我们创建一个函数，以便快速创建包含操作码和可选操作数的单字节码指令。命名为 Make，提供了一个不错的标识符 code.Make
// 快速构建单字节码指令
func Make(op Opcode, operands ...int) []byte {
// 从已定义的操作码中寻找
def, ok := definitions[op]
if !ok {
return []byte{}
}
instructionLen := 1
// 根据操作数的个数决定需要返回的[]byte长度（操作码+操作数）
for _, w := range def.OperandWidths {
instructionLen += w
}
// 返回单字节码编译后的机器指令
instruction := make([]byte, instructionLen)
// 操作码占首1字节
instruction[0] = byte(op)
// 第一位是操作码，已经放入
offset := 1
// 遍历操作数
for i, o := range operands {
width := def.OperandWidths[i]
switch width {
case 2:
// 操作数大端编码为uint16到instruction
binary.BigEndian.PutUint16(instruction[offset:], uint16(o))
}
// 向后移动，继续遍历操作数
offset += width
}
return instruction
}
这里做的第一件事是，确定目标指令的长度，使我们能以合适的长度分配字节切片。
一旦获取 instructionLen 的值，就可以分配指令[]byte 并将 Opcode 添加到第 1 字节。然后遍历定义好的 OperandWidths，从操作数 operands 中取出匹配的元素并将其放入指令中。具体取决于操作数的宽度。
当需要定义额外的 Opcode 时，必须扩展该 switch 语句。只需确保两字节操作数为大端编码。
对操作数编码后，通过其宽度和循环的下一次迭代来递增 offset。
测试，我们只将操作码 OpConstant 和操作数 65534 传递给 Make，期望得到一个包含 3 字节的[]byte。这 3 字节中，第一字节必须是操作码，另外两个字节必须是 65534 的大端编码。这也是使用 65534 而非最大值 65535 的原因：这样就可以检查重要的字节是否在前。65534 在大端模式下表示的字节序列编码为 0xFF 0xFE，而 65535 则会被编码为 0xFF 0xFF，很难通过顺序识别
// code/code_test.go
package code
import "testing"
func TestMake(t *testing.T) {
ts := []struct {
op Opcode
operands []int
expected []byte
}{
{OpConstant, []int{65534}, []byte{byte(OpConstant), 255, 254}},
}
for _, tt := range ts {
instruction := Make(tt.op, tt.operands...)
if len(instruction) != len(tt.expected) {
t.Errorf("instruction has wrong length. want=%d, got=%d", len(tt.expected), len(instruction))
}
for i, b := range tt.expected {
if instruction[i] != tt.expected[i] {
t.Errorf("wrong byte at pos %d. want=%d, got=%d", i, b, instruction[i])
}
}
}
}
2.1.2 最小编译器
这个最小编译器只需要做一件事：生成两条 OpConstant 指令。用于让虚拟机将整数 1 和 2 正确地加载到栈中
需要完成以下工作：遍历传入的 AST,查找*ast.IntegerLiteral 节点，通过将其转换成*object.Integer 对其进行求值，将这些对象添加到常量池中，最后发出引用常量池内常量的 OpConstant 指令
// compiler/compiler.go
package compiler
import (
"malang/ast"
"malang/code"
"malang/object"
)
type Compiler struct {
instructions code.Instructions
constants []object.Object
}
func New() *Compiler {
return &Compiler{
instructions: code.Instructions{},
constants: []object.Object{},
}
}
func (c *Compiler) Compiler(node ast.Node) error {
return nil
}
func (c *Compiler) Bytecode() *Bytecode {
return &Bytecode{
Instructions: c.instructions,
Constants: c.constants,
}
}
type Bytecode struct {
Instructions code.Instructions
Constants []object.Object
}
compiler 包含 instruction 和 constants 两个字段。前者保存生成的字节码，后者是切片类型，表示常量池
Bytecode 包含编译器生成的 Instructions 和编译器求值的 Constants
Bytecode 是需要传输给虚拟机并在编译器测试中做断言的内容
测试
package compiler
import (
"fmt"
"malang/ast"
"malang/code"
"malang/lexer"
"malang/object"
"malang/parser"
"testing"
)
func parse(input string) *ast.Program {
l := lexer.New(input)
p := parser.New(l)
return p.ParseProgram()
}
type compilerTestCase struct {
input string
expectedConstants []interface{}
expectedInstructions []code.Instructions
}
// expectedInstructions是[][]byte，需要转为[]byte
func concatInstructions(s []code.Instructions) code.Instructions {
out := code.Instructions{}
for _, ins := range s {
out = append(out, ins...)
}
return out
}
func testIntegerObject(expected int64, actual object.Object) error {
res, ok := actual.(*object.Integer)
if !ok {
return fmt.Errorf("object is not Integer. got=%T (%+v)", actual, actual)
}
if res.Value != expected {
return fmt.Errorf("object has wrong value. got=%d, want=%d", res.Value, expected)
}
return nil
}
func testConstants(
t *testing.T,
expected []interface{},
actual []object.Object,
) error {
if len(expected) != len(actual) {
return fmt.Errorf("wrong number of constants. got=%d, want %d", len(actual), len(expected))
}
// 遍历比较常量池
for i, constant := range expected {
switch constant := constant.(type) {
case int:
err := testIntegerObject(int64(constant), actual[i])
if err != nil {
return fmt.Errorf("constant %d - testIntegerObject failed: %s", i, err)
}
}
}
return nil
}
func testInstructions(
expected []code.Instructions,
actual code.Instructions,
) error {
concatted := concatInstructions(expected)
if len(actual) != len(concatted) {
return fmt.Errorf("wrong instructions length.\nwant=%q\ngot=%q", concatted, actual)
}
for i, ins := range concatted {
if actual[i] != ins {
return fmt.Errorf("wrong instruction at %d.\nwant=%q\ngot=%q", i, concatted, actual)
}
}
return nil
}
func TestIntegerArithmetic(t *testing.T) {
ts := []compilerTestCase{
{
input: "1 + 2",
expectedConstants: []interface{}{1, 2},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
},
},
}
runCompilerTests(t, ts)
}
func runCompilerTests(t *testing.T, ts []compilerTestCase) {
t.Helper()
// 编译器生成字节码
for _, tt := range ts {
program := parse(tt.input)
compiler := New()
err := compiler.Compiler(program)
if err != nil {
t.Fatalf("compiler error: %s", err)
}
// 将传给虚拟机的指令
bytecode := compiler.Bytecode()
// 测试字节码是否正确
err = testInstructions(tt.expectedInstructions, bytecode.Instructions)
if err != nil {
t.Fatalf("compiler error: %s", err)
}
// 测试常量池是否正确
err = testConstants(t, tt.expectedConstants, bytecode.Constants)
if err != nil {
t.Fatalf("compiler error: %s", err)
}
}
}
输出的内容令人不解，需要改变输出
2.1.3 字节码与反汇编程序
go 可以通过 String 方法通知类型系统打印内容，这种方法对于字节码指令同样适用。
// code/code_test.go
package code
import "testing"
func TestMake(t *testing.T) {
ts := []struct {
op Opcode
operands []int
expected []byte
}{
{OpConstant, []int{65534}, []byte{byte(OpConstant), 255, 254}},
}
for _, tt := range ts {
instruction := Make(tt.op, tt.operands...)
if len(instruction) != len(tt.expected) {
t.Errorf("instruction has wrong length. want=%d, got=%d", len(tt.expected), len(instruction))
}
for i, b := range tt.expected {
if instruction[i] != tt.expected[i] {
t.Errorf("wrong byte at pos %d. want=%d, got=%d", i, b, instruction[i])
}
}
}
}
func TestInstructionsString(t *testing.T) {
instructions := []Instructions{
Make(OpConstant, 1),
Make(OpConstant, 2),
Make(OpConstant, 65535),
}
expected := `0000 OpConstant 1
0003 OpConstant 2
0006 OpConstant 65535
`
concatted := Instructions{}
for _, ins := range instructions {
concatted = append(concatted, ins...)
}
if concatted.String() != expected {
t.Errorf("instructions wrongly formatted.\nwant=%q\ngot=%q", expected, concatted.String())
}
}
这是我们对 Instructions.String 的期望：多行输出格式、打印需要的信息。每行开头都有计数器，告知我们应该关注哪些字节，也有人类可读形式的操作码以及解码后的操作数。
// code/code.go
func (ins Instructions) String() string {
return ""
}
编写另一个测试
// code/code.go
func TestReadOperands(t *testing.T) {
ts := []struct {
op Opcode
operands []int
bytesRead int
}{
{OpConstant, []int{65535}, 2},
}
for _, tt := range ts {
instruction := Make(tt.op, tt.operands...)
def, err := Lookup(byte(tt.op))
if err != nil {
t.Fatalf("definition not found: %q\n", err)
}
operandsRead, n := ReadOperands(def, instruction[1:])
if n != tt.bytesRead {
t.Fatalf("n wrong. want=%d, got=%d", tt.bytesRead, n)
}
for i, want := range tt.operands {
if operandsRead[i] != want {
t.Errorf("operands wrong. want=%d, got=%d", want, operandsRead[i])
}
}
}
}
ReadOperands 是 Make 的对立面，Make 为字节码指令的操作码进行编码，ReadOperands 则用于解码
在这个测试中，Make 编码了一条连同包含操作数的指令子切片的完全编码指令，并将其定义传递给 ReadOperands。ReadOperands 需要返回解码后的操作数，并告知我们它读取了多少字节来执行此操作。
func ReadOperands(def *Definition, ins Instructions) ([]int, int) {
operands := make([]int, len(def.OperandWidths))
offset := 0
for i, width := range def.OperandWidths {
switch width {
case 2:
operands[i] = int(ReadUint16(ins[offset:]))
}
offset += width
}
return operands, offset
}
func ReadUint16(ins Instructions) uint16 {
return binary.BigEndian.Uint16(ins)
}
我们用操作码的*Definitions 寻找操作数的宽度，并为其分配足够大小的切片来保存。随后遍历 Instructions 切片，尽量多地读入并转换定义中的字节。
修改之前的打印函数
// code/code.go
func (ins Instructions) String() string {
var out bytes.Buffer
i := 0
for i < len(ins) {
def, err := Lookup(ins[i])
if err != nil {
fmt.Fprintf(&out, "ERROR: %s\n", err)
continue
}
// 读取操作数，read是读取了多少字节
operands, read := ReadOperands(def, ins[i+1:])
fmt.Fprintf(&out, "%04d %s\n", i, ins.fmtInstruction(def, operands))
// 向后移动read个字节
i += 1 + read
}
return out.String()
}
func (ins Instructions) fmtInstruction(def *Definition, operands []int) string {
operandCount := len(def.OperandWidths)
if len(operands) != operandCount {
return fmt.Sprintf("ERROR: operand len %d does not match defined %d\n", len(operands), operandCount)
}
switch operandCount {
case 1:
return fmt.Sprintf("%s %d", def.Name, operands[0])
}
return fmt.Sprintf("ERROR: unhandled operandCount for %s\n", def.Name)
}
code 包下所有测试，通过，现在看看效果
2.1.4 回归初心，继续前行
编译器需要做什么：递归遍历 AST、找到*ast.IntegerLiterals、对其求值并将其转换为*object.Integers、将它们添加到常量字段、最后将 OpConstant 指令添加到内部的 Instructions 切片
// compiler/compiler.go
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
case *ast.Program:
for _, s := range node.Statements {
err := c.Compiler(s)
if err != nil {
return err
}
}
case *ast.ExpressionStatement:
err := c.Compiler(node.Expression)
if err != nil {
return err
}
case *ast.InfixExpression:
err := c.Compiler(node.Left)
if err != nil {
return err
}
err = c.Compiler(node.Right)
if err != nil {
return err
}
case *ast.IntegerLiteral:
integer := &object.Integer{Value: node.Value}
}
return nil
}
这里首先在*ast.Program 中遍历了所有 node.Statement，并为每一个节点调用了 c.Compiler。对于*ast.IntegerLiteral，会进行求值，创建一个*object.Integer
拥有求值的结果，就需要将其添加到常量池
// compiler/compiler.go
func (c *Compiler) addConstant(obj object.Object) int {
c.constants = append(c.constants, obj)
return len(c.constants) - 1
}
该方法将 obj 存入常量池，然后返回其在常量池的索引，作为 OpConstant 指令的操作数，该指令驱使虚拟机从常量池加载此常量到栈
是时候发出第一条指令了，在编译器中，发出的意思是生成和输出。可以理解为：生成指令并将其添加到最终结果，也就是打印它，可以将其添加到文件，还可以将其添加到内存中某个区域。
// compiler/compiler.go
// 传入操作码和操作数，返回操作码在字节码里的位置
func (c *Compiler) emit(op code.Opcode, operands ...int) int {
ins := code.Make(op, operands...)
pos := c.addInstruction(ins)
return pos
}
// 将新生成的字节码指令添加到字节码
func (c *Compiler) addInstruction(ins []byte) int {
posNewInstruction := len(c.instructions)
c.instructions = append(c.instructions, ins...)
return posNewInstruction
}
emit 返回的位置是发出指令的起始位置。当需要修改 c.instructions 时，可以使用
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.IntegerLiteral:
integer := &object.Integer{Value: node.Value}
// 发出OpConstant指令
c.emit(code.OpConstant, c.addConstant(integer))
}
return nil
}
2.1.5 给机器上电
现在这个编译器还只能表达‘将常量压栈’而不是‘用它来做某事’
虚拟机需要：指令、常量、栈
// vm/vm.go
package vm
import (
"malang/code"
"malang/compiler"
"malang/object"
)
const StackSize = 2048
type VM struct {
// compiler生成的常量和指令
constants []object.Object
instructions code.Instructions
stack []object.Object
sp int // 始终指向栈中的下一个空闲槽。栈顶的值是stack[sp-1]
}
func New(bytecode *compiler.Bytecode) *VM {
return &VM{
instructions: bytecode.Instructions,
constants: bytecode.Constants,
stack: make([]object.Object, StackSize),
sp: 0,
}
}
测试辅助方法
runVmTests 负责设置和运行每个 vmTestCase：对输入进行词法分析和语法分析，生成 AST，将其传递给编译器，检查编译器的错误，然后将*compiler.Bytecode 传递给 New 函数
New 函数会返回一个新的虚拟机实例，并复制给 vm。通过 vm.Run 启动 vm，在确保没有运行错误后，利用 StackTop 方法获取留在虚拟机栈顶的对象，随后将其传递给 testExpectedObejct，来确认是否和预期匹配
这里期望留在栈顶的是 2，因为现在只实现常量压栈指令，所以栈顶应该是最后被压入栈的 2
// vm/vm_test.go
package vm
import (
"fmt"
"malang/ast"
"malang/compiler"
"malang/lexer"
"malang/object"
"malang/parser"
"testing"
)
func parse(input string) *ast.Program {
l := lexer.New(input)
p := parser.New(l)
return p.ParseProgram()
}
func testIntegerObject(expected int64, actual object.Object) error {
res, ok := actual.(*object.Integer)
if !ok {
return fmt.Errorf("object is not Integer. got=%T (%+v)", actual, actual)
}
if res.Value != expected {
return fmt.Errorf("object has wrong value. got=%d, want=%d", res.Value, expected)
}
return nil
}
type vmTestCase struct {
input string
expected interface{}
}
func runVmTests(t *testing.T, ts []vmTestCase) {
t.Helper()
for _, tt := range ts {
program := parse(tt.input)
comp := compiler.New()
err := comp.Compiler(program)
if err != nil {
t.Fatalf("compiler error: %s", err)
}
vm := New(comp.Bytecode())
err = vm.Run()
if err != nil {
t.Fatalf("vm error: %s", err)
}
stackElem := vm.StackTop()
testExpectedObject(t, tt.expected, stackElem)
}
}
func testExpectedObject(
t *testing.T,
expected interface{},
actual object.Object,
) {
t.Helper()
switch expected := expected.(type) {
case int:
err := testIntegerObject(int64(expected), actual)
if err != nil {
t.Errorf("testIntegerObject failed: %s", err)
}
}
}
func TestIntegerArithmetic(t *testing.T) {
ts := []vmTestCase{
{"1", 1},
{"2", 2},
{"1 + 2", 2},
}
runVmTests(t, ts)
}
根据约定：sp 将始终指向栈的下一个空闲槽。假如栈上有一个元素，位于索引 0，则 sp 的值将为 1，并且要访问该元素则应该使用 stack[sp - 1]，在 sp 递增前，新元素存储在 stack[sp]中
// vm/vm.go
func (vm *VM) StackTop() object.Object {
if vm.sp == 0 {
return nil
}
return vm.stack[vm.sp-1]
}
现在缺失 Run 方法，它包含虚拟机的核心：主循环，即取指-解码-执行循环
// vm/vm.go
func (vm *VM) Run() error {
for ip := 0; ip < len(vm.instructions); ip++ {
op := code.Opcode(vm.instructions[ip])
switch op {
}
}
return nil
}
以上是循环第一部分，取指。这里通过递增指针 ip 来遍历 vm.instructions，并通过直接访问 vm.instructions 来获取当前指令。然后将字节转换为操作码。
添加解码和执行模块，解码就是添加一个 case 分支并解码指令的操作数
// vm/vm.go
func (vm *VM) Run() error {
// 取指
// ...
// 解码
switch op {
case code.OpConstant:
constIndex := code.ReadUint16(vm.instructions[ip+1:])
ip += 2
// ...
}
使用 ReadUint16 而非使用 ReadOperands，以及上面不使用 Lookup 而使用直接访问 vm.instructions 的理由都是为了速度
ReadUint16 函数从紧接着操作码的位置 ip+1 开始，解析字节码中的操作数。解码完操作数之后，需要正确地添加 ip 的值，增加量为解码后操作数的字节大小。如此，下一次迭代时，让 ip 指向的是操作码而不是操作数。
添加执行模块
func (vm *VM) Run() error {
// ...
switch op {
case code.OpConstant:
constIndex := code.ReadUint16(vm.instructions[ip+1:])
ip += 2
err := vm.push(vm.constants[constIndex])
if err != nil {
return err
}
}
// ...
}
func (vm *VM) push(o object.Object) error {
if vm.sp >= StackSize {
return fmt.Errorf("stack overflow")
}
vm.stack[vm.sp] = o
vm.sp++
return nil
}
这里利用 constIndex 从 vm.constants 中获取常量并将其压栈。push 方法负责检查栈大小、添加对象、递增栈指针 sp
2.2 栈上加法
新操作码用于将压栈的整数相加。该操作码是 OpAdd，作用是让虚拟机将最顶部两个元素弹栈，将他们相加并将最终结果压栈。它没有操作数，只是一个单字节操作码
// code/code.go
const (
OpConstant Opcode = iota
OpAdd
)
// ...
// 操作码定义详细信息
var definitions = map[Opcode]*Definition{
OpConstant: {"OpConstant", []int{2}},
OpAdd: {"OpAdd", []int{}},
}
测试 Make 是否可以处理没有操作数的操作码
// code/code_test.go
func TestMake(t *testing.T) {
ts := []struct {
op Opcode
operands []int
expected []byte
}{
{OpConstant, []int{65534}, []byte{byte(OpConstant), 255, 254}},
{OpAdd, []int{}, []byte{byte(OpAdd)}},
}
// ...
}
测试 Instructions.String
// code/code_test.go
func TestInstructionsString(t *testing.T) {
instructions := []Instructions{
Make(OpAdd),
Make(OpConstant, 2),
Make(OpConstant, 65535),
}
expected := `0000 OpAdd
0001 OpConstant 2
0004 OpConstant 65535
`
// ...
}
测试失败，我们需要为 Instructions.fmtInstruction 新增 case 分支
// code/code.go
func (ins Instructions) fmtInstruction(def *Definition, operands []int) string {
// ...
switch operandCount {
case 0:
return def.Name
case 1:
return fmt.Sprintf("%s %d", def.Name, operands[0])
}
return fmt.Sprintf("ERROR: unhandled operandCount for %s\n", def.Name)
}
因为没有操作数，所以不用更新 ReadOperands
// compiler/compiler_test.go
func TestIntegerArithmetic(t *testing.T) {
ts := []compilerTestCase{
{
input: "1 + 2",
expectedConstants: []interface{}{1, 2},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpAdd),
},
},
}
runCompilerTests(t, ts)
}
只更新工具，没有更新编译器，所以测试结果表示，指令没有发出
// compiler/compiler.go
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.InfixExpression:
err := c.Compiler(node.Left)
if err != nil {
return err
}
err = c.Compiler(node.Right)
if err != nil {
return err
}
switch node.Operator {
case "+":
c.emit(code.OpAdd)
default:
return fmt.Errorf("unknown operator %s", node.Operator)
}
// ...
return nil
}
修改之前 vm 里的测试
// vm/vm_test.go
func TestIntegerArithmetic(t *testing.T) {
ts := []vmTestCase{
// ...
{"1 + 2", 3},
}
runVmTests(t, ts)
}
此时虚拟机没有实现加法计算，所以测试失败
加法需要对压入栈的整数进行处理，所以第一步是弹栈
// vm/vm.go
func (vm *VM) pop() object.Object {
o := vm.stack[vm.sp-1]
vm.sp--
return o
}
为 OpAdd 指令添加‘解码’部分
// vm/vm.go
func (vm *VM) Run() error {
// 取指
for ip := 0; ip < len(vm.instructions); ip++ {
// ...
// 解码
switch op {
// ...
case code.OpAdd:
right := vm.pop()
left := vm.pop()
leftValue := left.(*object.Integer).Value
rightValue := right.(*object.Integer).Value
res := leftValue + rightValue
// 结果压栈
vm.push(&object.Integer{Value: res})
}
}
return nil
}
需要注意这里弹栈的顺序，有的计算需要操作数有正确的顺序（如减法）
2.3 连接 REPL
从 REPL 的 Start 函数中删除求值器和环境设置，并替换为对编译器和虚拟机的调用
func Start(in io.Reader, out io.Writer) {
scanner := bufio.NewScanner(in)
for {
fmt.Fprintf(out, PROMPT)
scanned := scanner.Scan()
if !scanned {
return
}
line := scanner.Text()
l := lexer.New(line)
p := parser.New(l)
program := p.ParseProgram()
if len(p.Errors()) != 0 {
printParserErrors(out, p.Errors())
continue
}
// 求值不同
comp := compiler.New()
err := comp.Compiler(program)
if err != nil {
fmt.Fprintf(out, "Woops! Compilation failed:\n %s\n", err)
continue
}
machine := vm.New(comp.Bytecode())
err = machine.Run()
if err != nil {
fmt.Fprintf(out, "Woops! Executing bytecode failed:\n %s\n", err)
continue
}
stackTop := machine.StackTop()
io.WriteString(out, stackTop.Inspect())
io.WriteString(out, "\n")
}
}
3. 编译表达式
3.1 栈清理
现在可以将两个数相加，但是有个问题：如果不采取任何措施，1+2 的结果会永远留在栈中
Monkey 里有 3 种语句：let 语句、return 语句、表达式语句。1+2 是表达式语句。前两种语句可以显式复用子表达式节点的值，而表达式语句只是用来包装表达式，从定义上说，它的值无法复用。
如果输入 1;2;3; 则栈中会存在 1、2、3。如果表达式语句更多，栈会被填满，这是个大问题
为了解决这个问题，需要做两件事：1.定义一个新操作码 OpPop，让虚拟机将栈顶元素弹出；2.每一个表达式语句之后都执行这个新的操作码
// code/code.go
const (
// ...
OpPop
)
// 操作码定义详细信息
var definitions = map[Opcode]*Definition{
// ...
OpPop: {"OpPop", []int{}},
}
向编译器添加 c.emit 调用
// compiler/compiler.go
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.ExpressionStatement:
err := c.Compiler(node.Expression)
if err != nil {
return err
}
c.emit(code.OpPop)
// ...
}
return nil
}
测试
// compiler/compiler_test.go
func TestIntegerArithmetic(t *testing.T) {
ts := []compilerTestCase{
{
input: "1 + 2",
expectedConstants: []interface{}{1, 2},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpAdd),
code.Make(code.OpPop),
},
},
{
input: "1; 2",
expectedConstants: []interface{}{1, 2},
expectedInstructions:[]code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpPop),
code.Make(code.OpConstant, 1),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
虚拟机处理弹栈
// vm/vm.go
func (vm *VM) Run() error {
// 取指
for ip := 0; ip < len(vm.instructions); ip++ {
// ...
switch op {
// ...
case code.OpPop:
vm.pop()
}
}
}
为了测试“在虚拟机弹出它之前，它必须在栈上”，添加一个用于测试的方法来代替 StackTop
// vm/vm.go
func (vm *VM) LastPoppedStackElem() object.Object {
return vm.stack[vm.sp]
}
按照约定，vm.sp 总是指向 vm.stack 的下一个空槽。这是一个新元素被压栈的地方。用于我们只是递减 vm.sp（没有将值设置为 nil）使元素弹栈，因此 vm.sp 也可以指向之前的栈顶元素。
// vm/vm_test.go
func runVmTests(t *testing.T, ts []vmTestCase) {
t.Helper()
for _, tt := range ts {
// ...
stackElem := vm.LastPoppedStackElem()
testExpectedObject(t, tt.expected, stackElem)
}
}
修改 REPL
// repl/repl.go
func Start(in io.Reader, out io.Writer) {
scanner := bufio.NewScanner(in)
for {
// ...
lastPopped := machine.LastPoppedStackElem()
io.WriteString(out, lastPopped.Inspect())
io.WriteString(out, "\n")
}
}
3.2 中缀表达式
添加四则运算剩下的三则
将操作码 Opcode 定义在 code 包里
// code/code.go
const (
OpConstant Opcode = iota
OpAdd // +
OpSub // -
OpMul // *
OpDiv // /
OpPop
)
// ...
var definitions = map[Opcode]*Definition{
OpConstant: {"OpConstant", []int{2}},
OpAdd: {"OpAdd", []int{}},
OpSub: {"OpSub", []int{}},
OpMul: {"OpMul", []int{}},
OpDiv: {"OpDiv", []int{}},
OpPop: {"OpPop", []int{}},
}
compiler 中添加解析新的运算，发起指令调用的 case 分支
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.InfixExpression:
// ...
switch node.Operator {
case "+":
c.emit(code.OpAdd)
case "-":
c.emit(code.OpSub)
case "*":
c.emit(code.OpMul)
case "/":
c.emit(code.OpDiv)
default:
return fmt.Errorf("unknown operator %s", node.Operator)
}
// ...
}
return nil
}
测试 compiler
// compiler/compiler.go
func TestIntegerArithmetic(t *testing.T) {
ts := []compilerTestCase{
// ...
{
input: "1 - 2",
expectedConstants: []interface{}{1, 2},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpSub),
code.Make(code.OpPop),
},
},
{
input: "1 * 2",
expectedConstants: []interface{}{1, 2},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpMul),
code.Make(code.OpPop),
},
},
{
input: "1 / 2",
expectedConstants: []interface{}{1, 2},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpDiv),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
修改 vm，支持四则运算
// vm/vm.go
func (vm *VM) executeBinaryIntegerOperation(
op code.Opcode,
left, right object.Object,
) error {
leftValue := left.(*object.Integer).Value
rightValue := right.(*object.Integer).Value
var res int64
switch op {
case code.OpAdd:
res = leftValue + rightValue
case code.OpSub:
res = leftValue - rightValue
case code.OpMul:
res = leftValue * rightValue
case code.OpDiv:
res = leftValue / rightValue
default:
return fmt.Errorf("unknown integer operator: %d", op)
}
return vm.push(&object.Integer{Value: res})
}
func (vm *VM) executeBinaryOperation(op code.Opcode) error {
right := vm.pop()
left := vm.pop()
leftType := left.Type()
rightType := right.Type()
if leftType == object.INTEGER_OBJ && rightType == object.INTEGER_OBJ {
return vm.executeBinaryIntegerOperation(op, left, right)
}
return fmt.Errorf("unsupported types for binary operation: %s %s", leftType, rightType)
}
func (vm *VM) Run() error {
// 取指
for ip := 0; ip < len(vm.instructions); ip++ {
// 字节转换为操作码
op := code.Opcode(vm.instructions[ip])
// 解码
switch op {
// ...
case code.OpAdd, code.OpSub, code.OpMul, code.OpDiv:
err := vm.executeBinaryOperation(op)
if err != nil {
return err
}
// ...
}
}
return nil
}
测试
// vm/vm_test.go
func TestIntegerArithmetic(t *testing.T) {
ts := []vmTestCase{
{"1 - 2", -1},
{"1 * 2", 2},
{"4 / 2", 2},
{"50 / 2 * 2 + 10 - 5", 55},
{"5 + 5 + 5 + 5 - 10", 10},
{"2 * 2 * 2 * 2 * 2", 32},
{"5 * 2 + 10", 20},
{"5 + 2 * 10", 25},
{"5 * (2 + 10)", 60},
}
runVmTests(t, ts)
}
3.3 布尔类型
还剩比较运算符==、!、<、>，以及两个前缀表达式!和-。需要用到布尔类型
如果像整数字面量一样编译为 OpConstant 指令，会浪费字节码和编译器和虚拟机资源，我们只需要定义两个操作码，将求值结果*object.Boolean 压入栈中
// code/code.go
const (
// ...
OpTrue
OpFalse
)
// ...
var definitions = map[Opcode]*Definition{
// ...
OpTrue: {"OpTrue", []int{}},
OpFalse: {"OpFalse", []int{}},
}
在编译器 compiler 里添加一个 case，发出指令 OpTrue 或 OpFalse
// compiler/compiler.go
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.Boolean:
if node.Value {
c.emit(code.OpTrue)
} else {
c.emit(code.OpFalse)
}
}
return nil
}
测试
// compiler/compiler_test.go
func TestBooleanExpression(t *testing.T) {
ts := []compilerTestCase{
{
input: "true",
expectedConstants: []interface{}{},
expectedInstructions: []code.Instructions{
code.Make(code.OpTrue),
code.Make(code.OpPop),
},
},
{
input: "false",
expectedConstants: []interface{}{},
expectedInstructions: []code.Instructions{
code.Make(code.OpFalse),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
让虚拟机处理 true 和 false
先添加测试
// vm/vm_test.go
func TestBooleanExpression(t *testing.T) {
ts := []vmTestCase{
{"true", true},
{"false", false},
}
runVmTests(t, ts)
}
func testExpectedObject(
t *testing.T,
expected interface{},
actual object.Object,
) {
t.Helper()
switch expected := expected.(type) {
// ...
case bool:
err := testBooleanObject(bool(expected), actual)
if err != nil {
t.Errorf("testBooleanObject failed: %s", err)
}
}
}
func testBooleanObject(expected bool, actual object.Object) error {
res, ok := actual.(*object.Boolean)
if !ok {
return fmt.Errorf("object is not Boolean. got=%T (%+v)", actual, actual)
}
if res.Value != expected {
return fmt.Errorf("object has wrong value. got=%T (%+v)", actual, actual)
}
return nil
}
这里虚拟机崩溃了，因为每个表达式语句都会发出 OpPop，但是此时没有东西被压栈（还不能识别布尔类型，没有处理并压栈），所以弹栈指针移动，报错 index out of range
先在虚拟机定义全局布尔变量
// vm/vm.go
var True = &object.Boolean{Value: true}
var False = &object.Boolean{Value: false}
设为全局变量，1.它们是唯一且不变的值；2.每次使用 bool 都是引用全局变量，省空间；3.更容易实现比较运算（只需要对比两个指针，无需对比指向的值）
扩展虚拟机的主循环，添加将 True、False 压栈的逻辑
// vm/vm.go
func (vm *VM) Run() error {
// 取指
for ip := 0; ip < len(vm.instructions); ip++ {
// 字节转换为操作码
op := code.Opcode(vm.instructions[ip])
// 解码
switch op {
// ...
case code.OpTrue:
err := vm.push(True)
if err != nil {
return err
}
case code.OpFalse:
err := vm.push(False)
if err != nil {
return err
}
}
}
return nil
}
3.4 比较运算符
Monkey 支持 4 个比较运算符: == != > <，首先添加 3 个新操作码
// code/code.go
const (
// ...
OpEqual
OpNotEqual
OpGreaterThan
)
// ...
var definitions = map[Opcode]*Definition{
// ...
OpEqual: {"OpEqual", []int{}},
OpNotEqual: {"OpNotEqual", []int{}},
OpGreaterThan: {"OpGreaterThan", []int{}},
}
这些操作码通过比较栈顶两个元素来完成工作。它们让虚拟机将栈顶待比较的元素弹出，然后将比较结果压栈
为什么没有 OpLessThan？因为可以通过编译器的代码重排序来完成。比如 3<5 可以重新排序为 5>3，结果不变。让编译器将小于表达式重排序为大于表达式，可以保持更小的指令集，虚拟机循环更紧凑。
测试
// compiler/compiler_test.go
func TestBooleanExpression(t *testing.T) {
ts := []compilerTestCase{
// ...
{
input: "1 > 2",
expectedConstants: []interface{}{1, 2},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpGreaterThan),
code.Make(code.OpPop),
},
},
{
input: "1 < 2",
expectedConstants: []interface{}{2, 1},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpGreaterThan),
code.Make(code.OpPop),
},
},
{
input: "1 == 2",
expectedConstants: []interface{}{1, 2},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpEqual),
code.Make(code.OpPop),
},
},
{
input: "1 != 2",
expectedConstants: []interface{}{1, 2},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpNotEqual),
code.Make(code.OpPop),
},
},
{
input: "true == false",
expectedConstants: []interface{}{},
expectedInstructions: []code.Instructions{
code.Make(code.OpTrue),
code.Make(code.OpFalse),
code.Make(code.OpEqual),
code.Make(code.OpPop),
},
},
{
input: "true != false",
expectedConstants: []interface{}{},
expectedInstructions: []code.Instructions{
code.Make(code.OpTrue),
code.Make(code.OpFalse),
code.Make(code.OpNotEqual),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
扩展 Compile 方法
// compiler/compiler.go
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.InfixExpression:
// ...
switch node.Operator {
// ...
case ">":
c.emit(code.OpGreaterThan)
case "==":
c.emit(code.OpEqual)
case "!=":
c.emit(code.OpNotEqual)
default:
return fmt.Errorf("unknown operator %s", node.Operator)
}
// ...
}
return nil
}
添加对<的处理
// compiler/compiler.go
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.InfixExpression:
if node.Operator == "<" {
err := c.Compiler(node.Right)
if err != nil {
return err
}
err = c.Compiler(node.Left)
if err != nil {
return err
}
c.emit(code.OpGreaterThan)
return nil
}
// ...
// ...
}
return nil
}
这里<作为一个特殊用例来处理。如果遇到<，就调整编译顺序，首先编译 node.Right，然后是 node.Left，再发出 OpGreaterThan 操作码。
// vm/vm_test.go
func TestBooleanExpression(t *testing.T) {
ts := []vmTestCase{
// ...
{"1 < 2", true},
{"1 > 2", false},
{"1 < 1", false},
{"1 > 1", false},
{"1 == 1", true},
{"1 != 1", false},
{"1 == 2", false},
{"1 != 2", true},
{"true == true", true},
{"false == false", true},
{"true == false", false},
{"true != false", true},
{"false != true", true},
{"(1 < 2) == true", true},
{"(1 < 2) == false", false},
{"(1 > 2) == true", false},
{"(1 > 2) == false", true},
}
runVmTests(t, ts)
}
// vm/vm.go
func nativeBoolToBooleanObject(input bool) *object.Boolean {
if input {
return True
}
return False
}
// 比较数字
func (vm *VM) executeIntegerComparison(
op code.Opcode,
left, right object.Object,
) error {
leftValue := left.(*object.Integer).Value
rightValue := right.(*object.Integer).Value
switch op {
case code.OpEqual:
return vm.push(nativeBoolToBooleanObject(rightValue == leftValue))
case code.OpNotEqual:
return vm.push(nativeBoolToBooleanObject(rightValue != leftValue))
case code.OpGreaterThan:
return vm.push(nativeBoolToBooleanObject(leftValue > rightValue))
default:
return fmt.Errorf("unknown operator: %d", op)
}
}
func (vm *VM) executeComparison(op code.Opcode) error {
right := vm.pop()
left := vm.pop()
if left.Type() == object.INTEGER_OBJ && right.Type() == object.INTEGER_OBJ {
return vm.executeIntegerComparison(op, left, right)
}
switch op {
// 将go的布尔类型转换成*Object.Boolean
case code.OpEqual:
return vm.push(nativeBoolToBooleanObject(right == left))
case code.OpNotEqual:
return vm.push(nativeBoolToBooleanObject(right != left))
default:
return fmt.Errorf("unknown operator: %d (%s %s)", op, left.Type(), right.Type())
}
}
func (vm *VM) Run() error {
// 取指
for ip := 0; ip < len(vm.instructions); ip++ {
// 字节转换为操作码
op := code.Opcode(vm.instructions[ip])
// 解码
switch op {
// ...
case code.OpEqual, code.OpNotEqual, code.OpGreaterThan:
err := vm.executeComparison(op)
if err != nil {
return err
}
}
}
return nil
}
3.5 前缀表达式
Monkey 支持前缀运算符-和!
定义操作码
// code/code.go
const (
// ...
OpMinus
OpBang
)
// ...
// 操作码定义详细信息
var definitions = map[Opcode]*Definition{
// ...
OpMinus: {"OpMinus", []int{}},
OpBang: {"OpBang", []int{}},
}
-是整数运算符，!是布尔运算符，各自添加测试
// compiler/compiler_test.go
func TestIntegerArithmetic(t *testing.T) {
ts := []compilerTestCase{
// ...
{
input: "-1",
expectedConstants: []interface{}{1},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpMinus),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
func TestBooleanExpression(t *testing.T) {
ts := []compilerTestCase{
// ...
{
input: "!true",
expectedConstants: []interface{}{},
expectedInstructions: []code.Instructions{
code.Make(code.OpTrue),
code.Make(code.OpBang),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
因为我们之前 Compile 方法中的*ast.PrefixExpression 节点没有处理，所以没有编译带前缀的整数字面量和布尔字面量，测试输出没有出现 OpConstant 和 OpTrue。
// compiler/compiler.go
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.PrefixExpression:
err := c.Compiler(node.Right)
if err != nil {
return err
}
switch node.Operator {
case "!":
c.emit(code.OpBang)
case "-":
c.emit(code.OpMinus)
default:
return fmt.Errorf("unknown operator %s", node.Operator)
}
}
return nil
}
为虚拟机添加测试
// vm/vm_test.go
func TestIntegerArithmetic(t *testing.T) {
ts := []vmTestCase{
// ...
{"-5", -5},
{"-10", -10},
{"-50 + 100 + -50", 0},
{"(5 + 10 * 2 + 15 / 3) * 2 + -10", 50},
}
runVmTests(t, ts)
}
func TestBooleanExpression(t *testing.T) {
ts := []vmTestCase{
// ...
{"!true", false},
{"!false", true},
{"!5", false},
{"!!true", true},
{"!!false", false},
{"!!5", true},
}
runVmTests(t, ts)
}
补充虚拟机主循环
// vm/vm.go
func (vm *VM) executeMinusOperator() error {
operand := vm.pop()
if operand.Type() != object.INTEGER_OBJ {
return fmt.Errorf("unsupported type for negation: %s", operand.Type())
}
value := operand.(*object.Integer).Value
return vm.push(&object.Integer{Value: -value})
}
func (vm *VM) executeBangOperator() error {
operand := vm.pop()
switch operand {
case True:
return vm.push(False)
case False:
return vm.push(True)
default:
return vm.push(False)
}
}
func (vm *VM) Run() error {
// 取指
for ip := 0; ip < len(vm.instructions); ip++ {
// 字节转换为操作码
op := code.Opcode(vm.instructions[ip])
// 解码
switch op {
// ...
case code.OpBang:
err := vm.executeBangOperator()
if err != nil {
return err
}
case code.OpMinus:
err := vm.executeMinusOperator()
if err != nil {
return err
}
}
}
return nil
}
在 executeBangOperator 中，我们实现操作数弹栈，并通过将除 False 以外的所有内容视为真值来否定其值。从技术上说，True 分支没必要，但是就文档而言是有保留意义的，这种方法现在是我们的虚拟机对 Monkey 的真实性概念的实现。
4. 条件语句
前面都是添加运算符之类的，而接下来难度会提升很多
一个问题：如何让虚拟机根据条件执行不同的字节码指令？
条件语句的 if 分支称为条件语句的‘结果’，else 分支称为‘备选’
回顾解释器中的实现：evaluator 包的 Eval 函数遇到*ast.IfExression 时会对条件进行求值，并检查 isTruthy 函数的结果。如果为真，就执行结果部分，如果非真且包含备选，则执行备选，如果没有备选，就返回*object.Null
之所以可以这样做，是因为有 AST 节点。可以决定对*ast.IfExpression 的任意侧进行求值。
但是现在，不会递归遍历 AST 并同时执行它，而是将 AST 转换为字节码并将其铺平。铺平的原因是，字节码是一系列指令，而且它们没有子节点，无法递归
假设这段代码
if (5 > 2) {
30 + 20
} else {
50 -25
}
已经知道如何表达 5 > 2 和 30 + 20、50 - 25
如何根据 OpGreaterThen 指令的结果让机器执行某一部分呢？
我们使用一个指令来跳转，实现根据 OpGreaterThan 的结果执行不同部分
4.1 跳转
在机器码中，跳转指令用于实现分支（条件语句），这里说的机器码不仅包括计算机执行的代码，也包括虚拟机执行的字节码。翻译成虚拟机术语是：跳转是告知虚拟机将指令指针转化为一个确定值的指令
当虚拟机从上到下执行这些指令，会先执行前面构成条件的指令，结果是栈中保存一个布尔值
接下来是 JUMP_IF_NOT_TRUE，会让虚拟机跳到 OpConstant 4 指令，前提是栈中的布尔值不为真。如果不为真，就会跳过条件语句的结果部分，转到条件语句的备选部分。如果栈中布尔值为真，则 JUMP_IF_NOT_TRUE 不会生效，虚拟机往下正常执行。
执行完条件的结果部分后，会遇到 JUMP_NO_MATTER_WHAT 指令，直接跳到条件备选部分结束后的第一条指令（跳出了条件语句）
跳转是告诉虚拟机更改指令指针值，它的操作数就是虚拟机应该跳转到的指令的索引。该值称为偏移量。跳转目标是指令的索引，它是一个绝对偏移量。相对偏移量是相对于跳转指令本身的位置，表示的不是跳转到的确切位置，而是跳转的距离
实现条件语句，我们将定义两个跳转操作码：一个带有条件（“如果不为真则跳转”），一个没有条件（“直接跳转”）。它们都有一个操作数，即虚拟机应该跳转到的指令的索引
4.2 编译条件语句
发出跳转指令的难点不是操作码，而是操作数。
我们应该为跳转指令添加什么操作数呢？虚拟机要跳转到哪里呢？因为我们没有编译结果分支和备选分支，也不知道要跳多少条指令，这才是挑战
先定义操作码，一个直接跳转，一个有条件跳转
// code/code.go
const (
// ...
OpJumpNotTruthy // 有条件跳转
OpJump // 无条件跳转
)
// 操作码定义详细信息
var definitions = map[Opcode]*Definition{
// ...
// 跳转指令有两字节大小（16位）的操作数（目标指令的绝对偏移量）
OpJumpNotTruthy: {"OpJumpNotTruthy", []int{2}},
OpJump: {"OpJump", []int{2}},
}
测试
// compiler/compiler_test.go
func TestConditional(t *testing.T) {
ts := []compilerTestCase{
{
input: `
if (true) { 10 }; 3333
`,
expectedContants: []interface{}{10, 3333},
expectedInstructions: []code.Instructions{
// 0000
code.Make(code.OpTrue),
// 0001
code.Make(code.OpJumpNotTruthy, 7),
// 0004
code.Make(code.OpConstant, 0),
// 0007
code.Make(code.OpPop),
// 0008
code.Make(code.OpConstant, 1),
// 0011
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
条件语句的条件和结果部分都没有被编译。扩展 Compiler 方法
// compiler/compiler.go
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.IfExpression:
err := c.Compiler(node.Condition)
if err != nil {
return err
}
}
return nil
}
目前最大的跳转是，在编译 node.Consequence 之前，发出一个偏移量为 node.Consequence 之后的 OpJumpNotTruthy 指令
在不知道要跳转多远的时候，先使用虚假的偏移量，后面再处理
// compiler/compiler.go
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.IfExpression:
err := c.Compiler(node.Condition)
if err != nil {
return err
}
// 发出带虚假偏移量的OpJumpNotTruthy
c.emit(code.OpJumpNotTruthy, 9999)
err = c.Compiler(node.Consequence)
if err != nil {
return err
}
}
return nil
}
测试发现还是不能编译条件语句的结果部分
目前编译器还不能处理*ast.BlockStatement，我们扩展 Compiler 方法
// compiler/compiler.go
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.BlockStatement:
for _, s := range node.Statements {
err := c.Compiler(s)
if err != nil {
return err
}
}
}
}
此时有个问题，在 0007 位置多了一个编译器自动生成的 OpPop 指令，而我们希望条件的结果部分和备选部分中，有一个能在栈中保留值。
let result = if (5 > 4) { 5 } else { 3 }
似乎可以直接删掉 node.Consequence 中的最后一条 OpPop 指令，但是如果遇到这种情况：
if (true) {
3;
2;
1;
}
我们希望 3 和 2 弹栈，而 1 留在栈中
为了摆脱额外的 OpPop 指令，我们先更改编译器，以追踪发出的最后两条指令，包括追踪它们的操作码和它们被发出的位置。准备一个新类型和两个新字段
// compiler/compiler.go
type EmittedInstruction struct {
Opcode code.Opcode
Position int
}
type Compiler struct {
instructions code.Instructions
constants []object.Object
lastInstruction EmittedInstruction
previousInstruction EmittedInstruction
}
func New() *Compiler {
return &Compiler{
instructions: code.Instructions{},
constants: []object.Object{},
lastInstruction: EmittedInstruction{},
previousInstruction: EmittedInstruction{},
}
}
lastInstructions 是发出的最后一条指令，previousInstructions 是倒数第二条，接下来修改编译器 emit 方法来填充两者的字段
// compiler/compiler.go
// 传入操作码和操作数，返回操作码在字节码里的位置
func (c *Compiler) emit(op code.Opcode, operands ...int) int {
ins := code.Make(op, operands...)
pos := c.addInstruction(ins)
// 记录最后两条指令
c.setLastInstruction(op, pos)
return pos
}
// 记录最后两条指令
func (c *Compiler) setLastInstruction(op code.Opcode, pos int) {
previous := c.lastInstruction
last := EmittedInstruction{Opcode: op, Position: pos}
c.previousInstruction = previous
c.lastInstruction = last
}
接下来我们采用类型安全的方式检查最后发出的指令的操作码，如果最后一条发出的指令是 OpPop，就将其移除
// compiler/compiler.go
// 移除最后一条指令OpPop
func (c *Compiler) removeLastPop() {
c.instructions = c.instructions[:c.lastInstruction.Position]
c.lastInstruction = c.previousInstruction
}
// 判断if最后一个指令是不是OpPop
func (c *Compiler) lastInstructionsIsPop() bool {
return c.lastInstruction.Opcode == code.OpPop
}
// 遍历AST，触发指令
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.IfExpression:
err := c.Compiler(node.Condition)
if err != nil {
return err
}
// 发出带虚假偏移量的OpJumpNotTruthy
c.emit(code.OpJumpNotTruthy, 9999)
err = c.Compiler(node.Consequence)
if err != nil {
return err
}
if c.lastInstructionsIsPop() {
c.removeLastPop()
}
// ...
}
return nil
}
从移除 OpPop 的例子可以看出，发出的指令是可以改变的。我们也可以修改 OpJumpNotTruthy 9999
我们不用删除 c.emit(code.OpJumpNotTruthy, 9999)，只需要使用 c.lastInstruction 的 Position 字段。我们在编译 node.Consequence 之后修改 OpJumpNotTruthy 的操作数。此时，我们知道虚拟机需要跳转的距离和替换 9999 的正确偏移量
这个操作被称为回填，广泛应用于编译器。由于只遍历 AST 一次，因此这样的编译器被称为单遍编译器。更高级的编译器会将跳转指令的目标留空，直到知道要跳转的距离，然后对 AST（或其他 IR）进行第二次遍历并填充目标
我们继续发出 9999，记住其位置，一旦知道要跳转到哪里，就返回并将 9999 替换为正确的偏移量
添加一个方法，可以替换 instructions 切片中任意偏移处的指令
// compiler/compiler.go
// 替换instructions切片中任意偏移处的指令
func (c *Compiler) replaceInstruction(pos int, newInstruction []byte) {
for i := 0; i < len(newInstruction); i++ {
c.instructions[pos+i] = newInstruction[i]
}
}
changeOperand 方法用于替换指令的操作数
// compiler/compiler.go
// 替换指令的操作数
func (c *Compiler) changeOperand(opPos int, operand int) {
// 从编译器的指令s里找到要修改的指令
op := code.Opcode(c.instructions[opPos])
// 重新创建指令
newInstruction := code.Make(op, operand)
// 替换
c.replaceInstruction(opPos, newInstruction)
}
changeOperand 没有真的修改操作数本身（防止修改多字节操作数变得混乱），而是使用新操作数重新创建指令，并把旧指令替换为新指令。
这里的基本假设是：只替换具有相同非可变长度的相同类型的指令。如果不成立，必须相应地更新 c.lastInstruction 和 c.previousInstruction。一旦编译器发出的指令变得更复杂，另一个类型安全且独立于编码指令字节大小的 IR 是如何派上用场的。
不过，当前解决方案仍然符合我们的需求。即 replaceInstruction 和 changeOperand，我们现在使用它们
// compiler/compiler.go
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.IfExpression:
err := c.Compiler(node.Condition)
if err != nil {
return err
}
// 发出带虚假偏移量的OpJumpNotTruthy
jumpNotTruthyPos := c.emit(code.OpJumpNotTruthy, 9999)
err = c.Compiler(node.Consequence)
if err != nil {
return err
}
if c.lastInstructionsIsPop() {
c.removeLastPop()
}
// if的结果部分后下一条指令的地址
afterConsequencePos := len(c.instructions)
c.changeOperand(jumpNotTruthyPos, afterConsequencePos)
// ...
}
return nil
}
现在只能编译条件语句的结果部分，不能编译同时具有结果和备选部分的条件语句。现在写测试
// compiler/compiler_test.go
func TestConditional(t *testing.T) {
ts := []compilerTestCase{
// ...
{
input: `
if (true) { 10 } else { 20 }; 3333;
`,
expectedConstants: []interface{}{10, 20, 3333},
expectedInstructions: []code.Instructions{
// 0000
code.Make(code.OpTrue),
// 0001
code.Make(code.OpJumpNotTruthy, 10),
// 0004
code.Make(code.OpConstant, 0),
// 0007
code.Make(code.OpJump, 13),
// 0010
code.Make(code.OpConstant, 1),
// 0013
code.Make(code.OpPop),
// 0014
code.Make(code.OpConstant, 2),
// 0017
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
这个用例条件部分编译为 OpTrue，此时，OpJump 会跳过备选部分。OpJump 之后应该是组成备选部分的指令，条件为真，OpJump 生效，跳过备选，否则忽略 OpJump，执行备选，备选需要被编译，才能知道 OpJump 要跳到哪
测试
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.IfExpression:
err := c.Compiler(node.Condition)
if err != nil {
return err
}
// 发出带虚假偏移量的OpJumpNotTruthy
jumpNotTruthyPos := c.emit(code.OpJumpNotTruthy, 9999)
err = c.Compiler(node.Consequence)
if err != nil {
return err
}
if c.lastInstructionsIsPop() {
c.removeLastPop()
}
if node.Alternative == nil {
// if后下一条指令的地址
afterConsequencePos := len(c.instructions)
c.changeOperand(jumpNotTruthyPos, afterConsequencePos)
} else {
// 发出带有虚假偏移量的OpJump，跳过备选
c.emit(code.OpJump, 9999)
afterConsequencePos := len(c.instructions)
c.changeOperand(jumpNotTruthyPos, afterConsequencePos)
}
// ...
}
return nil
}
OpJump 操作数错误，并且缺失整个备选部分
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.IfExpression:
// ...
if node.Alternative == nil {
// if后下一条指令的地址
afterConsequencePos := len(c.instructions)
c.changeOperand(jumpNotTruthyPos, afterConsequencePos)
} else {
// 发出带有虚假偏移量的OpJump
jumpPos := c.emit(code.OpJump, 9999)
// 跳转到备选部分
afterConsequencePos := len(c.instructions)
c.changeOperand(jumpNotTruthyPos, afterConsequencePos)
// 编译备选部分
err := c.Compiler(node.Alternative)
if err != nil {
return err
}
// 去掉OpPop，保留fn内表达式值
if c.lastInstructionsIsPop() {
c.removeLastPop()
}
afterAlternativePos := len(c.instructions)
c.changeOperand(jumpPos, afterAlternativePos)
}
// ...
}
return nil
}
首先将 OpJump 指令的位置保存在 jumpPos 中，以便后续回来修改，如何回填之前发出的 OpJumpNotTruthy 指令的操作数，将其修改到 jumpNotTruthyPos 处，以便在 OpJump 之后立即跳转（jumpNotTruthy 跳转到 OpJump 后-备选部分的第一条指令处）
随后编译 node.Alternative。最后将 OpJump 指令的操作数改为下一条需要发出指令的偏移量，即备选部分之后的位置。
4.3 执行跳转
// vm/vm_test.go
func TestConditionals(t *testing.T) {
ts := []vmTestCase{
{"if (true) { 10 }", 10},
{"if (true) { 10 } else { 20 }", 10},
{"if (false) { 10 } else { 20 }", 20},
{"if (1) { 10 }", 10},
{"if (1 < 2) { 10 }", 10},
{"if (1 < 2) { 10 } else { 20 }", 10},
{"if (1 > 2) { 10 } else { 20 }", 20},
}
runVmTests(t, ts)
}
虚拟机可以跳过操作码，但是操作数不能，因为操作数是整数，可能和被解码的操作码有相同的值，这会导致虚拟机错误地将它们识别为操作码
// vm/vm.go
func (vm *VM) Run() error {
// 取指
for ip := 0; ip < len(vm.instructions); ip++ {
// 字节转换为操作码
op := code.Opcode(vm.instructions[ip])
// 解码
switch op {
// ...
case code.OpJump:
pos := int(code.ReadUint16(vm.instructions[ip+1:]))
ip = pos - 1
}
}
return nil
}
第一步，利用 code.ReadUint16 来对操作数解码。第二步，将指令指针 ip 设置到跳转指令的目标处。这里有个细节：由于此时是在循环中，因此需要每次迭代时把 ip 设置到它需要跳转到指令的索引处。
// vm/vm.go
func (vm *VM) Run() error {
// 取指
for ip := 0; ip < len(vm.instructions); ip++ {
// 字节转换为操作码
op := code.Opcode(vm.instructions[ip])
// 解码
switch op {
// ...
case code.OpJumpNotTruthy:
pos := int(code.ReadUint16(vm.instructions[ip+1:]))
// 跳过操作码的2字节
ip += 2
condition := vm.pop()
if !isTruthy(condition) {
// 跳转
ip = pos - 1
}
}
}
return nil
}
再次使用 code.ReadUint16 读取并解码操作数。随后将 ip 加 2，以便在下一循环中跳过操作数的 2 字节。
我们将栈顶元素弹出并借助 isTruthy 函数判断它是否为真，不为真则跳转，将 ip 设置到目标指令之前的索引位置，执行 for 循环
如果为真，则继续执行主循环的下一次迭代
测试通过，但是我们发现新 bug
4.4 欢迎回来，Null 值
如果条件语句的条件不为真，但是条件语句没有备选部分，则返回 Monkey 的 null 值————*object.Null
表达式在无法求值时也返回 Null
因为*object.Null 为常量，所以定义为全局变量
// vm/vm.go
var Null = &object.Null{}
测试
// vm/vm_test.go
func testExpectedObject(
t *testing.T,
expected interface{},
actual object.Object,
) {
t.Helper()
switch expected := expected.(type) {
// ...
case *object.Null:
if actual != Null {
t.Errorf("object is not Null: %T (%+v)", actual, actual)
}
}
}
func TestConditionals(t *testing.T) {
ts := []vmTestCase{
// ...
{"if (1 > 2) { 10 }", Null},
{"if (false) { 10 }", Null},
}
runVmTests(t, ts)
}
导致崩溃的原因是条件语句之后发出的 OpPop 指令。这些指令没有产生任何值，因此当虚拟机强制从栈中弹出数据时就会崩溃，现在将 vm.Null 压栈来解决
我们做两件事：1.定义一个备选操作码，让虚拟机将 vm.Null 压栈；2.修改编译器，当条件部分为空时强制插入一个备选部分，该部分仅包含将 vm.Null 压栈的新操作码
// code/code.go
const (
// ...
OpNull // 将Null压栈
)
// 操作码定义详细信息
var definitions = map[Opcode]*Definition{
// ...
OpNull: {"OpNull", []int{}},
}
测试
// compiler/compiler_test.go
func TestConditional(t *testing.T) {
ts := []compilerTestCase{
{
input: `
if (true) { 10 }; 3333
`,
expectedConstants: []interface{}{10, 3333},
expectedInstructions: []code.Instructions{
// 0000
code.Make(code.OpTrue),
// 0001
code.Make(code.OpJumpNotTruthy, 10),
// 0004
code.Make(code.OpConstant, 0),
// 0007
code.Make(code.OpJump, 11),
// 0010
code.Make(code.OpNull),
// 0011
code.Make(code.OpPop),
// 0012
code.Make(code.OpConstant, 1),
// 0015
code.Make(code.OpPop),
},
},
// ...
}
runCompilerTests(t, ts)
}
这里是更新了第一个测试用例
// compiler/compiler.go
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.IfExpression:
err := c.Compiler(node.Condition)
if err != nil {
return err
}
// 发出带虚假偏移量的OpJumpNotTruthy
jumpNotTruthyPos := c.emit(code.OpJumpNotTruthy, 9999)
err = c.Compiler(node.Consequence)
if err != nil {
return err
}
if c.lastInstructionsIsPop() {
c.removeLastPop()
}
// 发出带有虚假偏移量的OpJump
jumpPos := c.emit(code.OpJump, 9999)
// 编译完结果部分和OpJump，就知道备选部分的第一条指令的位置
afterConsequencePos := len(c.instructions)
c.changeOperand(jumpNotTruthyPos, afterConsequencePos)
if node.Alternative == nil {
// 备选部分为空则将Null压栈
c.emit(code.OpNull)
} else {
// 编译备选部分
err := c.Compiler(node.Alternative)
if err != nil {
return err
}
// 去掉OpPop，保留fn内表达式值
if c.lastInstructionsIsPop() {
c.removeLastPop()
}
}
afterAlternativePos := len(c.instructions)
c.changeOperand(jumpPos, afterAlternativePos)
// ...
}
return nil
}
不管是否存在 node.Alternative，我们均发出 OpJump 指令和更新 OpJumpNotTruthy 指令的操作数作为开始。后续检查 node.Alternative 是否为空，为空，则发出 OpNull，不为空就正常编译，并去掉 OpPop
// vm/vm.go
func (vm *VM) Run() error {
// 取指
for ip := 0; ip < len(vm.instructions); ip++ {
// 字节转换为操作码
op := code.Opcode(vm.instructions[ip])
// 解码
switch op {
// ...
case code.OpNull:
err := vm.push(Null)
if err != nil {
return err
}
}
}
return nil
}
表达式在使用时是可以交换的，因此任何表达式在虚拟机中都可能产生 Null，这似乎不太好
在遇到非期待的值时，往往会抛出错误，但是需要有显式处理 Null 的函数和方法
// vm/vm_test.go
func TestBooleanExpression(t *testing.T) {
ts := []vmTestCase{
// ...
{"!(if (false) { 5; })", true},
}
runVmTests(t, ts)
}
这个测试将!Null 转为 True
让 executeBangOperator 处理 Null 不会崩溃
// vm/vm.go
func (vm *VM) executeBangOperator() error {
operand := vm.pop()
switch operand {
case True:
return vm.push(False)
case False:
return vm.push(True)
case Null:
return vm.push(True)
default:
return vm.push(False)
}
}
条件语句是表达式，条件部分也是表达式，也就是说可以把条件语句作为另一个条件语句的条件部分。也就是说，虚拟机需要能实现处理内驱的条件语句产生的 Null
// vm/vm_test.go
func TestConditionals(t *testing.T) {
ts := []vmTestCase{
// ...
{"if ((if (false) { 10 })) { 10 } else { 20 }", 20},
}
runVmTests(t, ts)
}
// vm/vm.go
func isTruthy(obj object.Object) bool {
switch obj := obj.(type) {
case *object.Boolean:
return obj.Value
case *object.Null:
return false
default:
return true
}
}
5. 追踪名称
本章实现通过支持 let 语句和标识符表达式来实现绑定
但是只支持顶层和非函数体块语句这两种形式的 let 语句，在实现函数和闭包时，将处理局部变量，这是函数内部的 let 语句产生的
5.1 计划
需要将 let 语句和标识符表达式编译成字节码指令，并使虚拟机支持这些指令。需要添加的新操作码：一个用于告诉虚拟机将标识符绑定到值上，另一个用来检索之前绑定到标识符的值。
实现绑定的主要步骤是，将标识符正确解析到之前绑定的值，如果在执行代码时可以传递标识符（就像求值器那样）就可以将标识符用作映射的键，存储和检索值，但是我们不能这么做。
现在我们不是在求值器中，而是在虚拟机使用字节码。不能在字节码中传递标识符，因为操作码的操作数是整数。如何才能在新指令中表示标识符？又如何引用标识符需要绑定的值？
第二个问题的答案是：栈。不必显式地引用绑定的值，只需将值压栈并告知虚拟机：“将栈顶元素绑定给那个标识符”，就可以使用
而第一个问题的答案是，用数字表示标识符。
每遇到一个标识符，就单独赋予它一个新的数字，赋予的数字从 0 开始递增。如果标识符已经遇见过，就复用之前赋予的数字。
新定义两个操作码：OpSetGlobal 和 OpGetGlobal。每一个都有 16 位宽的操作数，用来保存之前赋予该标识符的唯一的数字。当编译 let 语句时，发出 OpSetGlobal，生成一个绑定。当编译标识符，发出 OpGetGlobal，用来获取绑定的值。
以上是编译器的工作。在虚拟机中，我们使用切片完成全局绑定的创建和检索。这个切片被称为‘全局存储’。执行 OpGetGlobal 指令时，我们需要以操作数为索引从全局存储中读取值并将其压栈
5.2 编译绑定
第一步，定义两个操作码
// code/code.go
const (
// ...
OpGetGlobal // 从全局存储中取值
OpSetGlobal // 向全局存储中存值
)
// 操作码定义详细信息
var definitions = map[Opcode]*Definition{
// ...
OpGetGlobal: {"OpGetGlobal", []int{2}},
OpSetGlobal: {"OpSetGlobal", []int{2}},
}
编译器测试
// compiler/compiler_test.go
func TestGlobalLetStatements(t *testing.T) {
ts := []compilerTestCase{
{
input: `
let one = 1;
let two = 2;
`,
expectedConstants: []interface{}{1, 2},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpSetGlobal, 1),
},
},
{
input: `
let one = 1;
one;
`,
expectedConstants: []interface{}{1},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpPop),
},
},
{
input: `
let one = 1;
let two = one;
two;
`,
expectedConstants: []interface{}{1},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpSetGlobal, 1),
code.Make(code.OpGetGlobal, 1),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
Compile 方法添加 case 分支处理 let 语句
// compiler/compiler.go
func (c *Compiler) Compiler(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.LetStatement:
err := c.Compiler(node.Value)
if err != nil {
return err
}
}
return nil
}
遇到 let 语句时，首要认为是编译等号右边的表达式。这个表达式是需要绑定到标识符的值，编译这个表达式意味着让虚拟机将这个值压栈
5.2.1 添加符号表
符号表是解释器和编译器中用于将标识符与信息关联的数据结构。它可以用在从词法分析到代码生成的所有节点，作用是存储和检索有关标识符（也被称为符号）的信息，比如标识符的位置、所在作用域、是否已被定义、绑定值的类型以及解释过程和编译过程有用的信息
我们将使用符号来关联标识符与作用域和特定的数字。它需要完成两件事：
- 将全局范围内的标识符与特定的数字相关联
- 获取与给定标识符相关联的数字
以上两件事在符号表中分别称为“定义”和“解析”。在已知作用域内“定义”一个标识符并为其关联部分信息，随后将这个标识符“解析”成之前关联的信息。我们将这些信息称为“符号”。标识符与包含这个信息的符号相关
符号表定义
// compiler/symbol_table.go
package compiler
type SymbolScope string
const (
GlobalScope SymbolScope = "GLOBAL"
)
type Symbol struct {
Name string
Scope SymbolScope
Index int
}
type SymbolTable struct {
store map[string]Symbol
numDefinitions int
}
func NewSymbolTable() *SymbolTable {
s := make(map[string]Symbol)
return &SymbolTable{store: s}
}
这里定义 SymbolScope 表示作用域，它的值是唯一的，因为我们需要区分作用域。使用 string 类型是为了方便调试
Symbol 结构体定义了 Monkey 代码中有关符号的所有信息
SymbolTable 将 string 与 Symbol 关联，并追踪它拥有的 numDefinitions，string 的内容是用户定义的标识符
我们正在构建一个将字符串与其相关信息关联在一起的 map。SymbolTable 还缺少 Define 函数和 Resolve 函数
测试
// compiler/symbol_table_test.go
package compiler
import "testing"
func TestDefine(t *testing.T) {
expected := map[string]Symbol{
"a": Symbol{Name: "a", Scope: GlobalScope, Index: 0},
"b": Symbol{Name: "b", Scope: GlobalScope, Index: 1},
}
global := NewSymbolTable()
a := global.Define("a")
if a != expected["a"] {
t.Errorf("expected a=%+v, got=%+v", expected["a"], a)
}
b := global.Define("b")
if b != expected["b"] {
t.Errorf("expected b=%+v, got=%+v", expected["b"], b)
}
}
func TestResolveGlobal(t *testing.T) {
global := NewSymbolTable()
global.Define("a")
global.Define("b")
expected := []Symbol{
Symbol{Name: "a", Scope: GlobalScope, Index: 0},
Symbol{Name: "b", Scope: GlobalScope, Index: 1},
}
for _, sym := range expected {
res, ok := global.Resolve(sym.Name)
if !ok {
t.Errorf("name %s not resolvable", sym.Name)
continue
}
if res != sym {
t.Errorf("expected %s to resolve to %+v, got=%+v", sym.Name, sym, res)
}
}
}
Define 函数将标识符作为参数，创建定义并返回 Symbol。不必指定创建定义的作用域，符号表会自动追踪。Index 是我们之后要处理的特殊数字
Resolve 函数将先前定义的标识符交给符号表，返回它关联的 Symbol，如果标识符未定义，则 Resolve 第二个参数返回 false。
// compiler/symbol_table.go
func (s *SymbolTable) Define(name string) Symbol {
symbol := Symbol{Name: name, Index: s.numDefinitions, Scope: GlobalScope}
s.store[name] = symbol
s.numDefinitions++
return symbol
}
func (s *SymbolTable) Resolve(name string) (Symbol, bool) {
obj, ok := s.store[name]
return obj, ok
}
Definn 创建新的 Symbol，并将其与 store 内的名称关联起来，递增 numDefinitions 计数器，最后返回新构建的 Symbol
5.2.2 在编译器中使用符号
// compiler/compiler.go
type Compiler struct {
// ...
symbolTable *SymbolTable
}
func New() *Compiler {
return &Compiler{
// ...
symbolTable: NewSymbolTable(),
}
}
现在可以在*ast.LetStatement 中定义标识符
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.LetStatement:
err := c.Compile(node.Value)
if err != nil {
return err
}
symbol := c.symbolTable.Define(node.Name.Value)
c.emit(code.OpSetGlobal, symbol.Index)
}
return nil
}
我们获取标识符节点的值并尝试在符号表中解析，如果不能解析，就返回错误。这个错误是编译时错误，之前在求值器运行时，只能判断是否定义了某个变量，现在可以在字节码传递给虚拟机之前就抛出错误。
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.Identifier:
symbol, ok := c.symbolTable.Resolve(node.Value)
if !ok {
return fmt.Errorf("undefined variable %s", node.Value)
}
c.emit(code.OpGetGlobal, symbol.Index)
}
return nil
}
5.3 在虚拟机中支持全局变量
// vm/vm_test.go
func TestGlobalLetStatements(t *testing.T) {
ts := []vmTestCase{
{"let one = 1; one", 1},
{"let one = 1; let two = 2; one + two", 3},
{"let one = 1; let two = one + one; one + two", 3},
}
runVmTests(t, ts)
}
// vm/vm.go
const GlobalsSize = 65536
type VM struct {
// ...
globals []object.Object
}
func New(bytecode *compiler.Bytecode) *VM {
return &VM{
// ...
globals: make([]object.Object, GlobalsSize),
}
}
globals 字段就是虚拟机的“全局存储”，底层数据结构可以使用切片，因为它可以在没有任何开销的情况下直接基于索引访问单个元素
// vm/vm.go
func (vm *VM) Run() error {
// 取指
for ip := 0; ip < len(vm.instructions); ip++ {
// 字节转换为操作码
op := code.Opcode(vm.instructions[ip])
// 解码
switch op {
// ...
case code.OpSetGlobal:
globalIndex := code.ReadUint16(vm.instructions[ip+1:])
ip += 2
vm.globals[globalIndex] = vm.pop()
}
}
return nil
}
先解析了操作数 globalIndex，并将虚拟机的指令指针 ip 以 2 字节递增。随后将栈顶元素弹出，绑定到名称，并将其保存到指定索引下的 globals 存储中。当再次压栈，就很容易被检索到
// vm/vm.go
func (vm *VM) Run() error {
// 取指
for ip := 0; ip < len(vm.instructions); ip++ {
// 字节转换为操作码
op := code.Opcode(vm.instructions[ip])
// 解码
switch op {
// ...
case code.OpGetGlobal:
globalIndex := code.ReadUint16(vm.instructions[ip+1:])
ip += 2
err := vm.push(vm.globals[globalIndex])
if err != nil {
return err
}
}
}
return nil
}
此时，如果在 REPL 中运行
为什么会失败？因为 REPL 中，主循环的每一次迭代都会创建新的编译器和虚拟机，也就是说，每次都是新的符号表和全局存储
我们需要构造一个新函数，以便在 REPL 中保持全局状态
// compiler/compiler.go
// repl中创建新编译器并保留旧符号表和常量
func NewWithState(s *SymbolTable, constants []object.Object) *Compiler {
compiler := New()
compiler.symbolTable = s
compiler.constants = constants
return compiler
}
// vm/vm.go
// repl中创建新编译器并保留旧字节码和全局存储
func NewWithState(bytecode *compiler.Bytecode, s []object.Object) *VM {
vm := New(bytecode)
vm.globals = s
return vm
}
修改 repl
// repl/repl.go
func StartVM(in io.Reader, out io.Writer) {
scanner := bufio.NewScanner(in)
constants := []object.Object{}
globals := make([]object.Object, vm.GlobalsSize)
symbolTable := compiler.NewSymbolTable()
for {
// ...
comp := compiler.NewWithState(symbolTable, constants)
err := comp.Compile(program)
if err != nil {
fmt.Fprintf(out, "Woops! Compilation failed:\n %s\n", err)
continue
}
code := comp.Bytecode()
constants = code.Constants
machine := vm.NewWithState(code, globals)
// ...
}
}
6. 字符串、数组和哈希表
本章目标是将字符串、数组、哈希表数据类型添加到编译器和虚拟机中，并且实现字符串连接、数组的索引运算符、哈希表的索引运算符
6.1 字符串
字符串字面量的值从编译到运行时都不会发生改变，因此将其视为常量表达式，和整数字面量类似，我们在编译器中将其转化为*object.String，并在 compiler.Bytecode 中将其添加到常量池中
// compiler/compiler_test.go
func TestStringExpressions(t *testing.T) {
ts := []compilerTestCase{
{
input: `"monkey"`,
expectedConstants: []interface{}{"monkey"},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpPop),
},
},
{
input: `"mon" + "key"`,
expectedConstants: []interface{}{"mon", "key"},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpAdd),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
为了能测试是否含*object.String，需要给 testConstants 添加一个 case 分支
// compiler/compiler_test.go
func testStringObject(expected string, actual object.Object) error {
res, ok := actual.(*object.String)
if !ok {
return fmt.Errorf("object is not String. got=%T (%+v)", actual, actual)
}
if res.Value != expected {
return fmt.Errorf("object has wrong value. got=%q, want=%q", res.Value, expected)
}
return nil
}
func testConstants(
t *testing.T,
expected []interface{},
actual []object.Object,
) error {
if len(expected) != len(actual) {
return fmt.Errorf("wrong number of constants. got=%d, want %d", len(actual), len(expected))
}
// 遍历比较常量池
for i, constant := range expected {
// 根据不同类型，进行测试
switch constant := constant.(type) {
// ...
case string:
err := testStringObject(constant, actual[i])
if err != nil {
return fmt.Errorf("constant %d - testStringObject failed: %s", i, err)
}
}
}
return nil
}
修改编译器的 Compile 方法，处理*object.String
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.StringLiteral:
str := &object.String{Value: node.Value}
c.emit(code.OpConstant, c.addConstant(str))
}
return nil
}
虚拟机测试
// vm/vm_test.go
func TestStringExpressions(t *testing.T) {
ts := []vmTestCase{
{`"monkey"`, "monkey"},
{`"mon" + "key"`, "monkey"},
{`"mon" + "key" + "banana"`, "monkeybanana"},
}
runVmTests(t, ts)
}
这里也需要 testStringObject 辅助函数
// vm/vm_test.go
func testStringObject(expected string, actual object.Object) error {
res, ok := actual.(*object.String)
if !ok {
return fmt.Errorf("object is not String. got=%T (%+v)", actual, actual)
}
if res.Value != expected {
return fmt.Errorf("object has wrong value. got=%d, want=%d", res.Value, expected)
}
return nil
}
func testExpectedObject(
t *testing.T,
expected interface{},
actual object.Object,
) {
t.Helper()
switch expected := expected.(type) {
// ...
case string:
err := testStringObject(expected, actual)
if err != nil {
t.Errorf("testStringObject failed: %s", err)
}
}
}
添加对 string 的运算支持
// vm/vm.go
func (vm *VM) executeBinaryStringOperation(
op code.Opcode,
left, right object.Object,
) error {
if op != code.OpAdd {
return fmt.Errorf("unknown string operation: %d", op)
}
leftValue := left.(*object.String).Value
rightValue := right.(*object.String).Value
return vm.push(&object.String{Value: leftValue + rightValue})
}
// 四则运算前判断
func (vm *VM) executeBinaryOperation(op code.Opcode) error {
right := vm.pop()
left := vm.pop()
leftType := left.Type()
rightType := right.Type()
switch {
case leftType == object.INTEGER_OBJ && rightType == object.INTEGER_OBJ:
return vm.executeBinaryIntegerOperation(op, left, right)
case leftType == object.STRING_OBJ && rightType == object.STRING_OBJ:
return vm.executeBinaryStringOperation(op, left, right)
default:
return fmt.Errorf("unsupported types for binary operation: %s %s", leftType, rightType)
}
}
6.2 数组
数组是复合数据类型,也就是说,数组由其他数据类型组成。所以不能将数组字面量视为常量表达式。
数组由多个元素组成，而数组字面量由产生这些元素的多个表达式组成，因此数组字面量本身的值可能会在编译和运行时发生变化。
[1 + 2, 3 + 4, 5 + 6]
不必但是表达式，因为优化编译器可以预先计算它们，重点是，数组的元素可以是任何类型的表达式————整数字面量、字符串连接、函数字面量、函数调用等。只有在运行时，我们才能确定它们的求值结果
与整数字面量和字符串字面量有所不同，对数组的实现需要有些改变，现在不需要在编译阶段构建数组并将其传递给虚拟机，而是要让虚拟机自己构建数组
我们定义一个名为 OpArray 的操作码，它的操作数是数组字面量的元素个数，编译*ast.ArrayLiteral 时，我们先编译它的所有元素。它的元素都是表达式，编译完会生成一条在虚拟机栈中压入 N 个值的指令，N 是数组字面量中的元素个数。然后发出 OpArray 指令，操作数为 N，虚拟机接受到该指令，从栈中弹出 N 个元素，构建一个*object.Array，然后将他压栈，完成数组构建。
// code/code.go
const (
// ...
OpArray // 构建数组
)
// 操作码定义详细信息
var definitions = map[Opcode]*Definition{
// ...
OpArray: {"OpArray", []int{2}},
}
OpArray 唯一的操作数只有两字节宽，因此数组字面量最多只能存 65535 个元素。
编写测试
// compiler/compiler_test.go
func TestArrayLiterals(t *testing.T) {
ts := []compilerTestCase{
{
input: "[]",
expectedConstants: []interface{}{},
expectedInstructions: []code.Instructions{
code.Make(code.OpArray, 0),
code.Make(code.OpPop),
},
},
{
input: "[1, 2, 3]",
expectedConstants: []interface{}{1, 2, 3},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpConstant, 2),
code.Make(code.OpArray, 3),
code.Make(code.OpPop),
},
},
{
input: "[1 + 2, 3 - 4, 5 * 6]",
expectedConstants: []interface{}{1, 2, 3, 4, 5, 6},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpAdd),
code.Make(code.OpConstant, 2),
code.Make(code.OpConstant, 3),
code.Make(code.OpSub),
code.Make(code.OpConstant, 4),
code.Make(code.OpConstant, 5),
code.Make(code.OpMul),
code.Make(code.OpArray, 3),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.ArrayLiteral:
for _, el := range node.Elements {
err := c.Compile(el)
if err != nil {
return err
}
}
c.emit(code.OpArray, len(node.Elements))
}
return nil
}
虚拟机的测试
// vm/vm_test.go
func TestArrayLiterals(t *testing.T) {
ts := []vmTestCase{
{"[]", []int{}},
{"[1 ,2, 3]", []int{1, 2, 3}},
{"[1 + 2, 3 * 4, 5 + 6]", []int{3, 12, 11}},
}
runVmTests(t, ts)
}
func testExpectedObject(
t *testing.T,
expected interface{},
actual object.Object,
) {
t.Helper()
switch expected := expected.(type) {
// ...
case []int:
array, ok := actual.(*object.Array)
if !ok {
t.Errorf("object is not Array: %T (%+v)", actual, actual)
return
}
if len(array.Elements) != len(expected) {
t.Errorf("wrong num of elements. wanted %d, got %d", len(expected), len(array.Elements))
return
}
for i, expectedElem := range expected {
err := testIntegerObject(int64(expectedElem), array.Elements[i])
if err != nil {
t.Errorf("testIntegerObject failed: %s", err)
}
}
}
}
在这里，确保空的数组字面量可以正常工作更加重要，因为在虚拟机中比编译器中更容易遇到差一错误
虚拟机实现解码操作数，从栈中取出指定数量的元素，构造一个*object.Array，将其压栈。
// vm/vm.go
// 构建数组object.Array
func (vm *VM) buildArray(startIndex, endIndex int) object.Object {
elements := make([]object.Object, endIndex-startIndex)
for i := startIndex; i < endIndex; i++ {
elements[i-startIndex] = vm.stack[i]
}
return &object.Array{Elements: elements}
}
func (vm *VM) Run() error {
// 取指
for ip := 0; ip < len(vm.instructions); ip++ {
// 字节转换为操作码
op := code.Opcode(vm.instructions[ip])
// 解码
switch op {
// ...
case code.OpArray:
numElements := int(code.ReadUint16(vm.instructions[ip+1:]))
ip += 2
array := vm.buildArray(vm.sp-numElements, vm.sp)
vm.sp = vm.sp - numElements
err := vm.push(array)
if err != nil {
return err
}
}
}
return nil
}
6.3 哈希表
哈希表和数组一样，最终值无法在编译时确定。哈希表并不只有 N 个元素，而是有 N 个键和 N 个值，并且都由表达式构成
{1 + 1: 2 * 2, 3 + 3: 4 * 4}
// 等价于
{2: 4, 6: 16}
我们依然让虚拟机自己构建哈希字面量，第一步是构建一个新的操作码 OpHash
// code/code.go
const (
// ...
OpHash // 构建哈希
)
// 操作码定义详细信息
var definitions = map[Opcode]*Definition{
// ...
OpHash: {"OpHash", []int{2}},
}
操作数用于指定栈中的键和值的数量。使用键值对的数量同样可行，但是那就必须在虚拟机中将其翻倍以获取位于栈中值的数量。
通过操作数，虚拟机可以从栈中取出正确数量的元素，构建 object.HashPairs 并构建一个*object.Hash，然后将其压栈。
编写测试
// compiler/compiler_test.go
func TestHashLiterals(t *testing.T) {
ts := []compilerTestCase{
{
input: "{}",
expectedConstants: []interface{}{},
expectedInstructions: []code.Instructions{
code.Make(code.OpHash, 0),
code.Make(code.OpPop),
},
},
{
input: "{1: 2, 3: 4, 5: 6}",
expectedConstants: []interface{}{1, 2, 3, 4, 5, 6},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpConstant, 2),
code.Make(code.OpConstant, 3),
code.Make(code.OpConstant, 4),
code.Make(code.OpConstant, 5),
code.Make(code.OpHash, 6),
code.Make(code.OpPop),
},
},
{
input: "{1: 2 + 3, 4: 5 * 6}",
expectedConstants: []interface{}{1, 2, 3, 4, 5, 6},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpConstant, 2),
code.Make(code.OpAdd),
code.Make(code.OpConstant, 3),
code.Make(code.OpConstant, 4),
code.Make(code.OpConstant, 5),
code.Make(code.OpMul),
code.Make(code.OpHash, 4),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
添加对*object.Hash 的编译
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.ArrayLiteral:
for _, el := range node.Elements {
err := c.Compile(el)
if err != nil {
return err
}
}
c.emit(code.OpArray, len(node.Elements))
case *ast.HashLiteral:
keys := []ast.Expression{}
for k := range node.Pairs {
keys = append(keys, k)
}
sort.Slice(keys, func(i, j int) bool {
return keys[i].String() < keys[j].String()
})
for _, k := range keys {
err := c.Compile(k)
if err != nil {
return err
}
err = c.Compile(node.Pairs[k])
if err != nil {
return err
}
}
c.emit(code.OpHash, len(node.Pairs)*2)
}
return nil
}
node.Pairs 是一个 map[ast.Expression]ast.Expression，而 Go 在遍历映射的键和值的时候不能保证一致的顺序，因此在编译前手动对键进行排序。否则，发出的指令将按随机顺序排序
这本身没问题，编译器和虚拟机可以在没有排序的情况下工作，但是随机顺序会导致测试出问题，测试给的期望是有顺序的，所以可能不匹配。
后面遍历键并编译，然后从 node.Pairs 中获取键对应的值并编译。先键后值的顺序很重要，因为需要在虚拟机中重建它。
接下来编写虚拟机的测试
// vm/vm_test.go
func testExpectedObject(
t *testing.T,
expected interface{},
actual object.Object,
) {
t.Helper()
switch expected := expected.(type) {
// ...
case map[object.HashKey]int64:
hash, ok := actual.(*object.Hash)
if !ok {
t.Errorf("object is not Hash. got=%T (%+v)", actual, actual)
return
}
if len(hash.Pairs) != len(expected) {
t.Errorf("hash has wrong number of Pairs. want=%d, got=%d", len(expected), len(hash.Pairs))
return
}
for expectedKey, expectedValue := range expected {
pair, ok := hash.Pairs[expectedKey]
if !ok {
t.Errorf("no pair for given key in Pairs")
}
err := testIntegerObject(expectedValue, pair.Value)
if err != nil {
t.Errorf("testIntegerObject failed: %s", err)
}
}
}
}
func TestHashLiterals(t *testing.T) {
ts := []vmTestCase{
{
"{}", map[object.HashKey]int64{},
},
{
"{1: 2, 2: 3}",
map[object.HashKey]int64{
(&object.Integer{Value: 1}).HashKey(): 2,
(&object.Integer{Value: 2}).HashKey(): 3,
},
},
{
"{1 + 1: 2 * 2, 3 + 3: 4 * 4}",
map[object.HashKey]int64{
(&object.Integer{Value: 2}).HashKey(): 4,
(&object.Integer{Value: 6}).HashKey(): 16,
},
},
}
runVmTests(t, ts)
}
实现处理 OpHash
// vm/vm.go
// 构建哈希表object.Hash
func (vm *VM) buildHash(startIndex, endIndex int) (object.Object, error) {
hashedPairs := make(map[object.HashKey]object.HashPair)
for i := startIndex; i < endIndex; i+=2 {
key := vm.stack[i]
value := vm.stack[i+1]
pair := object.HashPair{Key: key, Value: value}
hashKey, ok := key.(object.Hashable)
if !ok {
return nil, fmt.Errorf("unusable as hash key: %s", key.Type())
}
hashedPairs[hashKey.HashKey()] = pair
}
return &object.Hash{Pairs: hashedPairs}, nil
}
func (vm *VM) Run() error {
// 取指
for ip := 0; ip < len(vm.instructions); ip++ {
// 字节转换为操作码
op := code.Opcode(vm.instructions[ip])
// 解码
switch op {
// ...
case code.OpHash:
// OpHash操作数表示需要弹栈多少个元素
numElements := int(code.ReadUint16(vm.instructions[ip+1:]))
ip += 2
hash, err := vm.buildHash(vm.sp-numElements, vm.sp)
if err != nil {
return err
}
// 构建完，指针移动到栈中编译后的hash处
vm.sp = vm.sp - numElements
// hash压栈，ip++
err = vm.push(hash)
if err != nil {
return err
}
}
}
return nil
}
6.4 索引运算符
索引运算符用于从数组或哈希表中检索单个字符
索引运算符非常通用，虽然我们只想让它与数组和哈希表一起使用，但是它的语法形式还适用于更多情况
<表达式>[<表达式>]
被索引的数据结构和索引本身可以由任何表达式生成。而 Monkey 表达式可以生成任何 Monkey 对象，也就是说，从语义级别上，索引运算符可以将任何 object.Object 作为索引。
我们将构建通用索引运算符，而不是将索引运算符与特定数据结构相组合。第一步是定义新操作码
新操作码 OpIndex 没有操作数，需要栈顶提供两个值：被索引的对象和作为索引的对象。当虚拟机执行 OpIndex 的时候，将两者从栈中弹出，执行索引操作，并将结果返回原处。
// code/code.go
const (
OpIndex // 索引运算
)
// 操作码定义详细信息
var definitions = map[Opcode]*Definition{
OpIndex: {"OpIndex", []int{}},
}
编译器测试
//compiler/compiler_test.go
func TestIndexExpressions(t *testing.T) {
ts := []compilerTestCase{
{
input: "[1, 2, 3][1 + 1]",
expectedConstants: []interface{}{1, 2, 3, 1, 1},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpConstant, 2),
code.Make(code.OpArray, 3),
code.Make(code.OpConstant, 3),
code.Make(code.OpConstant, 4),
code.Make(code.OpAdd),
code.Make(code.OpIndex),
code.Make(code.OpPop),
},
},
{
input: "{1: 2}[2 - 1]",
expectedConstants: []interface{}{1, 2, 2, 1},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpHash, 2),
code.Make(code.OpConstant, 2),
code.Make(code.OpConstant, 3),
code.Make(code.OpSub),
code.Make(code.OpIndex),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
这里的重点是，编译器不必在于正在索引的内容、索引是什么或者整个操作是否有效。这些是虚拟机的工作，所以编译器没有关于空数组或不存在索引的测试用例。编译器要做的就是编译两个表达式并发出 OpIndex 指令
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.IndexExpression:
err := c.Compile(node.Left)
if err != nil {
return err
}
err = c.Compile(node.Index)
if err != nil {
return err
}
c.emit(code.OpIndex)
}
return nil
}
虚拟机测试
// vm/vm_test.go
func TestIndexExpressions(t *testing.T) {
ts := []vmTestCase{
{"[1, 2, 3][1]", 2},
{"[1, 2, 3][0 + 2]", 3},
{"[[1, 1, 1]][0][0]", 1},
{"[][0]", Null},
{"[1, 2, 3][99]", Null},
{"[1][-1]", Null},
{"{1: 1, 2: 2}[1]", 1},
{"{1: 1, 2: 2}[2]", 2},
{"{1: 1}[0]", Null},
{"{}[0]", Null},
}
runVmTests(t, ts)
}
测试里包含了：有效索引、无效索引、多维数组、空哈希表、空数组，对于有效的索引，应该将相应的元素压栈，对应无效的索引，应该替换为 vm.Null
// vm/vm.go
// 索引字符串
func (vm *VM) executeStringIndex(str, index object.Object) error {
strObject := str.(*object.String)
i := index.(*object.Integer).Value
max := int64(len(strObject.Value) - 1)
if i < 0 || i > max {
return vm.push(Null)
}
return vm.push(&object.String{Value: string(strObject.Value[i])})
}
// 索引哈希表
func (vm *VM) executeHashIndex(hash, index object.Object) error {
hashObject := hash.(*object.Hash)
key, ok := index.(object.Hashable)
if !ok {
return fmt.Errorf("unusable as hash key: %s", index.Type())
}
pair, ok := hashObject.Pairs[key.HashKey()]
if !ok {
return vm.push(Null)
}
return vm.push(pair.Value)
}
// 索引数组
func (vm *VM) executeArrayIndex(array, index object.Object) error {
arrayObejct := array.(*object.Array)
i := index.(*object.Integer).Value
max := int64(len(arrayObejct.Elements) - 1)
if i < 0 || i > max {
return vm.push(Null)
}
return vm.push(arrayObejct.Elements[i])
}
// 执行索引计算
func (vm *VM) executeIndexExpression(left, index object.Object) error {
switch {
case left.Type() == object.ARRAY_OBJ && index.Type() == object.INTEGER_OBJ:
return vm.executeArrayIndex(left, index)
case left.Type() == object.HASH_OBJ:
return vm.executeHashIndex(left, index)
// 自己加的，对字符串索引
case left.Type() == object.STRING_OBJ && index.Type() == object.INTEGER_OBJ:
return vm.executeStringIndex(left, index)
default:
return fmt.Errorf("index operator not supported: %s", left.Type())
}
}
func (vm *VM) Run() error {
// 取指
for ip := 0; ip < len(vm.instructions); ip++ {
// 字节转换为操作码
op := code.Opcode(vm.instructions[ip])
// 解码
switch op {
// ...
case code.OpIndex:
index := vm.pop()
left := vm.pop()
err := vm.executeIndexExpression(left, index)
if err != nil {
return err
}
}
}
return nil
}
7. 函数
本章将实现函数和函数调用，完成局部绑定并支持函数调用参数。
第一个问题是如何表示函数？简单地说，函数是一系列指令，但是在 Monkey 中，所有函数都是头等函数，可以在其他函数中传递和返回。那么如何表示一系列可以传递的指令？
还有控制流的问题。如何让虚拟机执行一个函数的指令？如何让它返回到之前执行的指令上？如何给函数传递参数？
7.1 一个简单的函数
本节目标
let fivePlusTen = fn() { 5 + 10 };
这个函数没有参数、没有局部绑定、没有参数调用、没有对全局绑定的访问
7.1.1 函数表示
我们需要将函数转为字节码，关键在于，Monkey 函数也是一种 Monkey 值，可以绑定给名称、从其他函数返回、作为参数传递给其他函数等等，也就是说，函数也是表达式，是函数字面量
函数字面量产生的值永远不会发生改变，这些值是常量，我们将它作为常量传递给虚拟机，编译成指令序列并添加到编译器的常量池中。
我们之前定义了 object.Funtion，他是一个 Monkey 对象，用来表示求值后函数的字面量，它自身也能被求值。现在，我们需要一个不同的版本：一个用来保存字节码而不是 AST 节点的函数对象
// object/object.go
const (
// ...
COMPILED_FUNCTION_OBJ = "COMPILED_FUNCTION_OBJ"
)
type CompiledFunction struct {
Instructions code.Instructions
}
func (cf *CompiledFunction) Type() ObjectType { return COMPILED_FUNCTION_OBJ }
func (cf *CompiledFunction) Inspect() string {
return fmt.Sprintf("CompiledFunction[%p]", cf)
}
object.CompiledFunction 可以保存从函数字面量编译中获得的 code.Instructions。并且是一个 object.Object，可以作为常量添加到 compiler.Bytecode 并加载到虚拟机中。
7.1.2 执行函数的操作码
面临一个新问题：是否需要新的操作码来实现编译和执行 Monkey 代码片段
函数字面量不需要新操作码，因为我们将它编译为*object.CompiledFunction 并视为常量，可以用 OpConstant 指令将它们加载到虚拟机栈中
我们需要为函数调用新建操作码，将调用表达式(*ast.CallExpression)，编译成一条指令，让虚拟机执行相关函数
现在需要定义新操作码：OpCall。它没有操作数
// code/code.go
const (
// ...
OpCall // 调用函数
)
// 操作码定义详细信息
var definitions = map[Opcode]*Definition{
// ...
OpCall: {"OpCall", []int{}},
}
OpCall 使用方式：首先使用 OpConstant 指令将想调用的函数压栈，随后发出 OpCall，让虚拟机执行栈顶的函数。
这个精简的 OpCall 指令规范就是所谓的调用约定。一旦添加对函数调用参数的支持，就必须改变。但是现在只需要两步：将想调用的函数压栈，以及发出 OpCall 指令
现在理论上可以将一个函数放到虚拟机的栈中并调用它。现在需要一种方法来让虚拟机从所调用的函数返回
具体地说，需要区分虚拟机从函数返回的两种情况，第一种是函数隐式或显式地返回了一些内容；第二种是函数执行结束但是没有返回任何内容。
第一种情况
let explicitReturn = fn() { return 5 + 10; };
let implicitReturn = fn() { 5 + 10; };
显式返回的值由 return 语句产生，该语句阻止执行函数的剩余部分，其返回的是 return 关键字后面表达式产生的值。
如果没有 return 语句，函数调用的求值结果是函数内部产生的最后一个值。这就是所谓的隐式返回
本书中，隐式返回将通过略微改变显式返回来实现。它们将编译为相同的字节码
它们将使用共同的操作码表示，OpReturnValue，用于让虚拟机从函数返回一个值
// code/code.go
const (
// ...
OpReturnValue // 函数返回
)
var definitions = map[Opcode]*Definition{
// ...
OpReturnValue: {"OpReturnValue", []int{}},
}
该操作数没有任何参数，因此要返回的值必须在栈顶
显式返回的情况下，编译 return 语句，返回值就会被压栈，然后发出 OpReturnValue。
实现隐式返回值需要更多工作，意味着需要返回表达式语句产生的值————如果它由函数体中最后执行的语句产生。但是前文为了确保表达式语句不会在栈中留下任何值，我们显式地发出 OpPop 指令清理栈。如果现在想返回值，就需要找到一种方法，将清理空栈的需求与对隐式返回的需求结合起来。
现在谈谈函数返回的第二种情况：函数不返回任何值
fn() { }
这个空函数体将编译为*object.CompiledFunction，可以被调用，只是函数体没有任何指令。另一个例子和局部绑定有关
fn() { let a = 1;}
一个不返回任何内容的函数并不常见，第一本书甚至没有处理它。我们认为这类函数也应该产生一个值。
我们让这类函数返回*object.Null，也就是说，如果函数末尾没有 OpReturnValue 指令，需要让虚拟机从函数返回 vm.Null，我们通过引入新操作码来实现
OpReturn 用于让虚拟机从当前函数返回有些信息（Null），并回到调用这个函数之前的逻辑
// code/code.go
const (
// ...
OpReturn // 函数没有返回值
)
// 操作码定义详细信息
var definitions = map[Opcode]*Definition{
// ...
OpReturn: {"OpReturn", []int{}},
}
7.1.3 编译函数字面量
- object.CompiledFunction 用来保存编译函数的指令，并将它们以常量的形式作为字节码的一部分从编译器传递给虚拟机
- code.OpCall 用来让虚拟机开始执行位于栈顶部的*object.CompiledFunction
- code.OpReturnValue 用来让虚拟机将栈顶的值返回到调用上下文并在此恢复执行
- code.OpReturn 与 code.OpReturnValue 类型，不同在于没有显式返回值，而是隐式返回 vm.Null
在编译函数调用前，先能编译函数字面量：
fn() { return 5 + 10 }
编写测试
// compiler/compiler_test.go
func TestFunctions(t *testing.T) {
ts := []compilerTestCase{
{
input: `fn() { return 5 + 10 }`,
expectedConstants: []interface{}{
5, 10,
// 编译后的函数字面量
[]code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpAdd),
code.Make(code.OpReturnValue),
},
},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 2),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
常量池中的[]code.Instructions 是*object.CompiledFunction 的 Instructions 字段，我们只对指令感兴趣，所以跳过外层，直接放 Instructions 进去，为了能够测试这个字段，我们需要改进测试的辅助函数
// compiler/compiler_test.go
func testConstants(
t *testing.T,
expected []interface{},
actual []object.Object,
) error {
if len(expected) != len(actual) {
return fmt.Errorf("wrong number of constants. got=%d, want %d", len(actual), len(expected))
}
// 遍历比较常量池
for i, constant := range expected {
// ...
case []code.Instructions:
fn, ok := actual[i].(*object.CompiledFunction)
if !ok {
return fmt.Errorf("constant %d - not a function: %T", i, actual[i])
}
err := testInstructions(constant, fn.Instructions)
if err != nil {
return fmt.Errorf("constant %d - testInstructions failed: %s", i, err)
}
}
}
return nil
}
如果直接用已有的*ast.FunctionLiteral 的主体调用编译器的 Compile 方法，最终会导致指令和主程序的指令纠缠在一起。解决方案是在编译器中引入作用域
1. 添加作用域
这意味着我们不再使用切片和两个单独的字段 lastInstruction 和 previousInstruction 追踪已发出的指令，而是将它们绑在一个编译作用域中，并使用该作用域的栈
// compiler/compiler.go
type CompilationScope struct {
instructions code.Instructions
lastInstruction EmittedInstruction
previousInstruction EmittedInstruction
}
type Compiler struct {
// ...
// 作用域
scopes []CompilationScope
scopeIndex int
}
在开始编译函数体（进入一个新的作用域）之前，我们将一个新的 CompilationScope 推送到 scopes 的栈中。在此作用域内编译时，编译器的 emit 方法只会修改当前 compilationScope 的字段。一旦完成了函数的编译，我们就会将它从 scopes 的栈中弹出并将指令放入一个新的*object.CompiledFunction，从而离开作用域
编写测试
// compiler/compiler_test.go
func TestCompilerScops(t *testing.T) {
compiler := New()
if compiler.scopeIndex != 0 {
t.Errorf("scopeIndex wrong. got=%d, want=%d", compiler.scopeIndex, 0)
}
compiler.emit(code.OpMul)
compiler.enterScope()
if compiler.scopeIndex != 1 {
t.Errorf("scopeIndex wrong. got=%d, want=%d", compiler.scopeIndex, 1)
}
compiler.emit(code.OpSub)
if len(compiler.scopes[compiler.scopeIndex].instructions) != 1 {
t.Errorf("instructions length wrong. got=%d", len(compiler.scopes[compiler.scopeIndex].instructions))
}
last := compiler.scopes[compiler.scopeIndex].lastInstruction
if last.Opcode != code.OpSub {
t.Errorf("lastInstruction.Opcode wrong. got=%d, want=%d", last.Opcode, code.OpSub)
}
compiler.leaveScope()
if compiler.scopeIndex != 0 {
t.Errorf("scopeIndex wrong. got=%d, want=%d", compiler.scopeIndex, 0)
}
compiler.emit(code.OpAdd)
if len(compiler.scopes[compiler.scopeIndex].instructions) != 2 {
t.Errorf("instructions.Opcode wrong. got=%d, want=%d", last.Opcode, code.OpAdd)
}
last = compiler.scopes[compiler.scopeIndex].lastInstruction
if last.Opcode != code.OpAdd {
t.Errorf("lastInstruction.Opcode wrong. got=%d, want=%d", last.Opcode, code.OpAdd)
}
previous := compiler.scopes[compiler.scopeIndex].previousInstruction
if previous.Opcode != code.OpMul {
t.Errorf("previousInstruction.Opcode wrong. got=%d, want=%d", previous.Opcode, code.OpMul)
}
}
这里测试了 enterScope 和 leaveScope 方法，它们的功能是通过在新的 scopes 栈中压入和弹出 CompilationScope 指令来改变 emit 的行为。该测试的主要思想是，在一个作用域内发出的指令不应对另一作用域内的指令产生影响
为了实现这两个方法，首先需要从编译器中删除 instructions、lastInstruction、previousInstruction 这 3 个字段，并在初始化新的*Compiler 时将这 3 个字段替换为 CompilationScope
// compiler/compiler.go
type Compiler struct {
// 常量池
constants []object.Object
// 符号表
symbolTable *SymbolTable
// 作用域
scopes []CompilationScope
scopeIndex int
}
func New() *Compiler {
mainScope := CompilationScope{
instructions: code.Instructions{},
lastInstruction: EmittedInstruction{},
previousInstruction: EmittedInstruction{},
}
return &Compiler{
constants: []object.Object{},
symbolTable: NewSymbolTable(),
scopes: []CompilationScope{mainScope},
scopeIndex: 0,
}
}
现在需要更新对已删除字段的每个引用，并将它们更改为使用当前作用域。这里添加一个新方法
// compiler/compiler.go
func (c *Compiler) currentInstructions() code.Instructions {
return c.scopes[c.scopeIndex].instructions
}
修改 addInstruction
// compiler/compiler.go
func (c *Compiler) addInstruction(ins []byte) int {
posNewInstruction := len(c.currentInstructions())
updatedInstructions := append(c.currentInstructions(), ins...)
c.scopes[c.scopeIndex].instructions = updatedInstructions
return posNewInstruction
}
在编译器的其他辅助方法中，还需要对栈进行遍历
// compiler/compiler.go
// 记录最后两条指令
// 移除最后一条指令OpPop
func (c *Compiler) removeLastPop() {
last := c.scopes[c.scopeIndex].lastInstruction
previous := c.scopes[c.scopeIndex].previousInstruction
old := c.currentInstructions()
new := old[:last.Position]
c.scopes[c.scopeIndex].instructions = new
c.scopes[c.scopeIndex].lastInstruction = previous
}
// 判断if最后一个指令是不是OpPop
func (c *Compiler) lastInstructionsIsPop() bool {
return c.scopes[c.scopeIndex].lastInstruction.Opcode == code.OpPop
}
func (c *Compiler) setLastInstruction(op code.Opcode, pos int) {
previous := c.scopes[c.scopeIndex].lastInstruction
last := EmittedInstruction{Opcode: op, Position: pos}
c.scopes[c.scopeIndex].previousInstruction = previous
c.scopes[c.scopeIndex].lastInstruction = last
}
// 替换instructions切片中任意偏移处的指令
func (c *Compiler) replaceInstruction(pos int, newInstruction []byte) {
ins := c.currentInstructions()
for i := 0; i < len(newInstruction); i++ {
ins[pos+i] = newInstruction[i]
}
}
// 替换指令的操作数
func (c *Compiler) changeOperand(opPos int, operand int) {
// 从编译器的指令s里找到要修改的指令
op := code.Opcode(c.currentInstructions()[opPos])
// 重新创建指令
newInstruction := code.Make(op, operand)
// 替换
c.replaceInstruction(opPos, newInstruction)
}
修改 Compile 方法
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.IfExpression:
// ...
afterConsequencePos := len(c.currentInstructions())
c.changeOperand(jumpNotTruthyPos, afterConsequencePos)
// ...
afterAlternativePos := len(c.currentInstructions())
c.changeOperand(jumpPos, afterAlternativePos)
// ...
}
return nil
}
当需要返回编译器生成的字节码时，还需要返回当前指令
// compiler/compiler.go
func (c *Compiler) Bytecode() *Bytecode {
return &Bytecode{
Instructions: c.currentInstructions(),
Constants: c.constants,
}
}
添加新的 enterScope 和 leaveScope 方法
// compiler/compiler.go
// 进入作用域
func (c *Compiler) enterScope() {
scope := CompilationScope{
instructions: code.Instructions{},
lastInstruction: EmittedInstruction{},
previousInstruction: EmittedInstruction{},
}
c.scopes = append(c.scopes, scope)
c.scopeIndex++
}
// 离开作用域
func (c *Compiler) leaveScope() code.Instructions {
instructions := c.currentInstructions()
c.scopes = c.scopes[:len(c.scopes)-1]
c.scopeIndex--
return instructions
}
2. 编译作用域
// compiler
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.FunctionLiteral:
c.enterScope()
err := c.Compile(node.Body)
if err != nil {
return err
}
instructions := c.leaveScope()
compiledFn := &object.CompiledFunction{Instructions: instructions}
c.emit(code.OpConstant, c.addConstant(compiledFn))
}
return nil
}
这段代码的中心思想是：在编译函数时更改发出指令的存储位置
因此，遇到*ast.FunctionLiteral 时，第一件事是通过 c.enterScope 进入一个新作用域。然后编译 node.Body，即构成函数主体的 AST 节点。之后通过调用 c.leaveScope 从 CompilationScope 的栈中取出刚刚填充的指令切片，创建一个新的*object.CompiledFunction 来保存这些指令，并将该函数添加到常量池中
此时可以编译函数字面量，但是不能编译*ast.ReturnStatement。
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.ReturnStatement:
err := c.Compile(node.ReturnValue)
if err != nil {
return err
}
c.emit(code.OpReturnValue)
}
return nil
}
将返回值表达式编译为值留在栈中，然后发出 OpReturValue 指令
接下来需要确保隐式返回与显式返回产生相同的字节码
// compiler/compiler_test.go
func TestFunctions(t *testing.T) {
ts := []compilerTestCase{
// ...
{
input: `fn() { 5 + 10 }`,
expectedConstants: []interface{}{
5, 10,
// 编译后的函数字面量
[]code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpAdd),
code.Make(code.OpReturnValue),
},
},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 2),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
为了通过这个用例，需要删除隐式返回值的 OpPop，但是也需要确保其他表达式的正常 OpPop
// compiler/compiler_test.go
func TestFunctions(t *testing.T) {
ts := []compilerTestCase{
// ...
{
input: `fn() { 1; 2 }`,
expectedConstants: []interface{}{
1, 2,
// 编译后的函数字面量
[]code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpPop),
code.Make(code.OpConstant, 1),
code.Make(code.OpReturnValue),
},
},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 2),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
第一个表达式语句，即字面量 1，后面应该跟一条 OpPop 指令，而第二个表达式，2，是隐式返回值，OpPop 指令必须替换为 OpReturnValue
可以看到，函数的最后一个表达式语句没有变成隐式返回值，仍然跟着 OpPop 指令
我们应该在函数体编译后和离开作用域之前，访问刚刚发出的指令，检查最后一条指令是不是 OpPop 指令，并在必要时将其转化为 OpReturnValue
为了让修改更容易，我们将现有的 lastInstructionIsPop 方法重构并更改为更通用的 lastInstructionIs，并添加了防御性检查
// compiler/compiler.go
// 最后的指令是否是op
func (c *Compiler) lastInstructionIs(op code.Opcode) bool {
if len(c.currentInstructions()) == 0 {
return false
}
return c.scopes[c.scopeIndex].lastInstruction.Opcode == op
}
修改之前调用 lastInstructionIsPop 的位置
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.IfExpression:
// ...
if c.lastInstructionIs(code.OpPop) {
c.removeLastPop()
}
// ...
if node.Alternative == nil {
// ...
} else {
// ...
// 去掉OpPop，保留fn内表达式值
if c.lastInstructionIs(code.OpPop) {
c.removeLastPop()
}
}
// ...
// ...
}
return nil
}
现在可以将隐式返回值的 OpPop 替换
// compiler/compiler.go
// 替换隐式返回值的OpPop
func (c *Compiler) replaceLastPopWithReturn() {
lastPos := c.scopes[c.scopeIndex].lastInstruction.Position
c.replaceInstruction(lastPos, code.Make(code.OpReturnValue))
c.scopes[c.scopeIndex].lastInstruction.Opcode = code.OpReturnValue
}
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.FunctionLiteral:
c.enterScope()
err := c.Compile(node.Body)
if err != nil {
return err
}
if c.lastInstructionIs(code.OpPop){
c.replaceLastPopWithReturn()
}
instructions := c.leaveScope()
compiledFn := &object.CompiledFunction{Instructions: instructions}
c.emit(code.OpConstant, c.addConstant(compiledFn))
}
return nil
}
为什么需要通用的 lastInstructionIs，因为存在‘没有主体的函数’这种边缘情况
编译器还需要能将一个空函数体转化为单条 OpReturn 指令
// compiler/compiler_test.go
func TestFunctionsWithoutReturnValue(t *testing.T) {
ts := []compilerTestCase{
{
input: `fn() { }`,
expectedConstants: []interface{}{
[]code.Instructions{
code.Make(code.OpReturn),
},
},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.FunctionLiteral:
// ...
if c.lastInstructionIs(code.OpPop) {
c.replaceLastPopWithReturn()
}
// 新加的语句
if !c.lastInstructionIs(code.OpReturnValue) {
c.emit(code.OpReturn)
}
// ...
}
return nil
}
将函数体中最后一条语句都转换为 OpReturnValue。因为它已经是一个显式的*ast.ReturnStatement 或我们已经转换了它
如果不能转换，意味着要么函数体中没有任何语句，要么只有不能转换成 OpReturnValue 指令的语句
7.1.4 编译函数调用
要实现函数调用，需要发出表示 Monkey 字节码调用约定的指令。
在本章开头，已经确定了函数调用约定，那就是将想调用的函数压栈。
如果是正在调用的函数字面量，就使用 OpConstant 指令：
fn() { 1 + 2 }()如果函数之前绑定给了一个名称，就使用 OpGetGlobal 指令:
let onePlueTwo = fn() { 1 + 2 }; onePlueTwo()
这两种情况最终会将我们期望调用的*object.CompiledFunction 放入栈中，为了能够执行指令，需要发出一条 OpCall 指令
虚拟机随后会执行该函数的指令，当执行结束时，如果有返回值，则将函数弹栈并用返回值替换它，如果没有返回值，则之间函数弹栈。
函数调用约定的整个部分，即虚拟机在函数执行结束后所做的事情，是隐式的：不需要发出 OpPop 指令来时函数弹栈。这是函数约定的一部分，我们会直接将其构建到虚拟机中。
// compiler/compiler_test.go
func TestFunctionCalls(t *testing.T) {
ts := []compilerTestCase{
{
input: `fn() { 24 }();`,
expectedConstants: []interface{}{
24,
[]code.Instructions{
code.Make(code.OpConstant, 0), // 字面量"24"
code.Make(code.OpReturnValue),
},
},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 1), // 被编译的函数
code.Make(code.OpCall),
code.Make(code.OpPop),
},
},
{
input: `
let noArg = fn() { 24 };
noArg();`,
expectedConstants: []interface{}{
24,
[]code.Instructions{
code.Make(code.OpConstant, 0), // 24
code.Make(code.OpReturnValue),
},
},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 1), // 被编译的函数
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpCall),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
编译器遇到*ast.CallExpression 时，编译所调用的函数并发出 OpCall 指令
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.CallExpression:
err := c.Compile(node.Function)
if err != nil {
return err
}
c.emit(code.OpCall)
}
return nil
}
7.1.5 虚拟机中的函数
字节码的 Constant 字段可以包含*object.CompiledFunction，当遇到 OpCall 指令时，需要执行位于栈顶的*object.CompiledFunction 指令，而遇到 OpReturnValue 或 OpReturn 时则不同。如果遇到 OpReturnValue，需要保留栈顶的值，即返回值。然后，必须从栈中删除刚刚执行的*object.CompiledFunction 并用保存的返回值（如果有）替换它
问题是如何执行函数的指令？
执行指令意味着虚拟机的主循环通过递增指令指针 ip 来遍历 vm.instructions 切片，并用它作为索引从 vm.instructions 获取下一个操作码。它还会从同一个切片中读取操作数。当遇到分支指令时，例如 OpJump，它会更改 ip 的值。
执行函数时，唯一要改变的是使用的数据：指令和指令指针。如果可以在虚拟机运行时修改它们，我们就可以执行函数。
不仅需要修改切片和整数，还需要将它们修改回来，当函数执行结束时，需要恢复旧的指令和 ip，并且不止一次。还需要处理函数的嵌套执行。
let one = fn() { 5 };
let two = fn() { one() };
let three = fn() { two() };
three()
当函数被调用，指令和指令指针都要被修改，当调用结束，需要将二者改回来，一切发生在栈中。
1. 添加栈帧
目前知道的是，函数调用是嵌套的，与执行相关的数据————指令和指令指针————以后进先出（LIFO）的方式被访问。处理两个独立的数据片段不是一件轻松的事，解决方案是将它们捆绑在一起，这就是“帧”。
帧是调用帧或者栈帧的简称，指 保存 与执行相关的信息 的数据结构。在编译器或解释器术语中，有时也称为活动记录
在物理机上，帧并不独立于栈存在，而是栈的特定部分。它是存储返回地址、当前函数的参数及其局部变量的地方。由于它在栈中，因此帧在函数执行结束后很容易弹栈。使用栈来保存调用帧能将其转换为调用栈。
在虚拟机上，不必使用栈来存储帧，比物理机有更多选择。使用 Go（高级语言）比使用汇编语言构建的虚拟机有更多选择，任何和执行相关的数据（包括帧）都可以保存在任何地方。
栈中保存的内容，不同虚拟机是不同的。有些将所有内容保存在栈中，有些只保存返回地址，还有些只保存局部变量和函数调用的参数。一切取决于所实现的语言、对并发性和性能的要求、宿主语言等。
我们已使用部分虚拟机的栈作为调用栈：在栈中保存了要调用的函数及其返回值。但是我们不打算将帧保存在此，而是有术语自己的栈。
// vm/frame.go
package vm
import (
"malang/code"
"malang/object"
)
type Frame struct {
fn *object.CompiledFunction
ip int
}
func NewFrame(fn *object.CompiledFunction) *Frame {
return &Frame{fn: fn, ip: -1}
}
func (f *Frame) Instructions() code.Instructions {
return f.fn.Instructions
}
每个帧有两个字段：fn 指向帧引用的已编译函数，ip 表示该帧的指令指针。这两个字段可以将虚拟机主循环中使用的所有数据集中在一起。当前执行的帧是位于调用栈顶部的帧
定义 Frame 后，有两种选择：一种是将虚拟机更改为仅在调用和执行函数时使用帧；我们选择另一种更高效的方法，即更改虚拟机，不仅将帧用于函数，而且将主程序 bytecode.Instructions 视为函数。
但是，当其更改为使用帧时，虚拟机应该保持现有的工作方式，也就是说，之前的测试用例应该还能成功。
// vm/vm.go
type VM struct {
// ...
frames []*Frame // 栈帧
framesIndex int
}
func (vm *VM) currentFrame() *Frame {
return vm.frames[vm.framesIndex-1]
}
func (vm *VM) pushFrame(f *Frame) {
vm.frames[vm.framesIndex] = f
vm.framesIndex++
}
func (vm *VM) popFrame() *Frame {
vm.framesIndex--
return vm.frames[vm.framesIndex]
}
为了提升性能，这里使用的不是附加控制切片的方式，而是采用预先分配的方式使用切片
现在，第一任务是分配切片并将最外层的“主栈帧”推送到它上面
// vm/vm.go
const MaxFrames = 1024
type VM struct {
// compiler生成的常量和指令
constants []object.Object
stack []object.Object
sp int // 始终指向栈中的下一个空闲槽。栈顶的值是stack[sp-1]
globals []object.Object
frames []*Frame // 栈帧
framesIndex int
}
func New(bytecode *compiler.Bytecode) *VM {
// 用传入的字节码创建栈帧
mainFn := &object.CompiledFunction{Instructions: bytecode.Instructions}
mainFrame := NewFrame(mainFn)
// 预先分配切片
frames := make([]*Frame, MaxFrames)
frames[0] = mainFrame
return &VM{
constants: bytecode.Constants,
stack: make([]object.Object, StackSize),
sp: 0,
globals: make([]object.Object, GlobalsSize),
frames: frames,
framesIndex: 1,
}
}
因为删除了 instructions 字段，所有需要改变访问指令和虚拟机内部指令指针的方式，并确保总是通过当前帧来访问它们
首先更改虚拟机主循环。ip 不能继续在循环中初始化，只能递增，将之前的 for 改为 Go 版本的 while 循环，并且需要在循环体里手动递增 ip
// vm/vm.go
func (vm *VM) Run() error {
var ip int
var ins code.Instructions
var op code.Opcode
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
vm.currentFrame().ip++
ip = vm.currentFrame().ip
ins = vm.currentFrame().Instructions()
op = code.Opcode(ins[ip])
// 解码
/// 注意下面的ip要替换成vm.currentFrame().ip!!!
switch op {
case code.OpConstant:
constIndex := code.ReadUint16(ins[ip+1:])
vm.currentFrame().ip += 2
err := vm.push(vm.constants[constIndex])
if err != nil {
return err
}
// ...
case code.OpJump:
pos := int(code.ReadUint16(ins[ip+1:]))
vm.currentFrame().ip = pos - 1
case code.OpJumpNotTruthy:
pos := int(code.ReadUint16(ins[ip+1:]))
// 跳过操作码的2字节
vm.currentFrame().ip += 2
condition := vm.pop()
if !isTruthy(condition) {
// 跳转
vm.currentFrame().ip = pos - 1
}
// ...
case code.OpSetGlobal:
globalIndex := code.ReadUint16(ins[ip+1:])
vm.currentFrame().ip += 2
vm.globals[globalIndex] = vm.pop()
case code.OpGetGlobal:
globalIndex := code.ReadUint16(ins[ip+1:])
vm.currentFrame().ip += 2
err := vm.push(vm.globals[globalIndex])
if err != nil {
return err
}
case code.OpArray:
numElements := int(code.ReadUint16(ins[ip+1:]))
vm.currentFrame().ip += 2
array := vm.buildArray(vm.sp-numElements, vm.sp)
vm.sp = vm.sp - numElements
err := vm.push(array)
if err != nil {
return err
}
case code.OpHash:
// OpHash操作数表示需要弹栈多少个元素
numElements := int(code.ReadUint16(ins[ip+1:]))
vm.currentFrame().ip += 2
hash, err := vm.buildHash(vm.sp-numElements, vm.sp)
if err != nil {
return err
}
// 构建完，指针移动到栈中编译后的hash处
vm.sp = vm.sp - numElements
// hash压栈，ip++
err = vm.push(hash)
if err != nil {
return err
}
// ...
}
}
return nil
}
2. 执行函数调用
// vm/vm_test.go
func TestCallingFunctionWithOutArguments(t *testing.T) {
ts := []vmTestCase{
{
input: `
let fivePlusTen = fn() { 5 + 10; };
fivePlusTen();
`,
expected: 15,
},
}
runVmTests(t, ts)
}
实现 OpCall
// vm/vm.go
func (vm *VM) Run() error {
var ip int
var ins code.Instructions
var op code.Opcode
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
vm.currentFrame().ip++
ip = vm.currentFrame().ip
ins = vm.currentFrame().Instructions()
op = code.Opcode(ins[ip])
// 解码
switch op {
// ...
case code.OpCall:
// 从当前栈帧取出函数字面量
fn, ok := vm.stack[vm.sp-1].(*object.CompiledFunction)
if !ok {
return fmt.Errorf("calling non-function")
}
// 进入函数栈帧
frame := NewFrame(fn)
vm.pushFrame(frame)
}
}
return nil
}
需要的是 15，返回的却是 10，因为此时还无法处理 OpReturnValue
// vm//vm.go
func (vm *VM) Run() error {
var ip int
var ins code.Instructions
var op code.Opcode
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
vm.currentFrame().ip++
ip = vm.currentFrame().ip
ins = vm.currentFrame().Instructions()
op = code.Opcode(ins[ip])
// 解码
switch op {
// ...
case code.OpReturnValue:
returnValue := vm.pop()
vm.popFrame()
vm.pop()
err := vm.push(returnValue)
if err != nil {
return err
}
}
}
return nil
}
先将返回值弹栈并将其放置一边。这是调用约定的第一部分：对于 OpReturnValue 指令，其返回值位于栈顶。然后从帧的栈中弹出刚刚执行的栈，以便虚拟机主循环下一次迭代继续在调用者上下文中执行
然后使用另一个 vm.Pop()，将*object.CompiledFunction 从栈帧弹出。这就是将执行的函数从栈中取出是虚拟机的隐式任务的含义
里程碑时刻。现在虚拟机可以执行多个函数————依次执行或执行嵌套函数
// vm/vm_test.go
func TestCallingFunctionWithOutArguments(t *testing.T) {
ts := []vmTestCase{
// ...
{
input: `
let one = fn() { 1; };
let two = fn() { 2; };
one() + two()
`,
expected: 3,
},
{
input: `
let a = fn() { 1; };
let b = fn() { a() + 1 };
let c = fn() { b() + 1 };
c();
`,
expected: 3,
},
}
runVmTests(t, ts)
}
// vm/vm_test.go
func TestCallingFunctionWithReturnStatement(t *testing.T) {
ts := []vmTestCase{
{
input: `
let earlyExit = fn() { return 99; 100; };
earlyExit();
`,
expected: 99,
},
{
input: `
let earlyExit = fn() { return 99; return 100; };
earlyExit();
`,
expected: 99,
},
}
runVmTests(t, ts)
}
3. 它只是 Null
需要处理 OpReturn 操作码。编译器已经能够确保将空函数编译为单个操作码：OpReturn。同时，调用这些函数时应该将 vm.Null 放在虚拟机栈中
// vm/vm_test.go
func TestCallingFunctionWithReturnStatement(t *testing.T) {
ts := []vmTestCase{
// ...
{
input: `
let noReturn = fn() { };
noReturn();
`,
expected: Null,
},
{
input: `
let noReturn = fn() { };
let noReturnTwo = fn() { };
noReturn();
noReturnTwo();
`,
expected: Null,
},
}
runVmTests(t, ts)
}
// vm/vm.go
func (vm *VM) Run() error {
var ip int
var ins code.Instructions
var op code.Opcode
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
vm.currentFrame().ip++
ip = vm.currentFrame().ip
ins = vm.currentFrame().Instructions()
op = code.Opcode(ins[ip])
// 解码
switch op {
// ...
case code.OpReturn:
vm.popFrame()
vm.pop()
err := vm.push(Null)
if err != nil {
return err
}
}
}
return nil
}
7.1.6 一点奖励
经过前面这些修改，我们实际上已经实现了头等函数
let returnsOne = fn() { 1; };
let returnsOneReturner = fn() { return returnsOne; };
returnsOneReturner()()
测试
// vm/vm_test.go
func TestFirstClassFunctions(t *testing.T) {
ts := []vmTestCase{
{
input: `
let returnsOne = fn() { 1; };
let returnsOneReturner = fn() { return returnsOne; };
returnsOneReturner()();
`,
expected: 1,
},
}
runVmTests(t, ts)
}
7.2 局部绑定
当前仅支持全局绑定，局部绑定尚不支持。局部绑定意味着它只在函数内部某个作用域可见和访问。这个细节将局部绑定的实现与函数的实现联系起来。
本章将实现以下 Monkey 代码
let globalSeed = 50;
let minusOne = fn() {
let num = 1;
globalSeed - num;
}
let minusTwo = fn() {
let num = 2;
globalSeed - num;
}
minusOne() + minusTwo()
这段代码中，globalSeed 是全局绑定，可以在嵌套的作用域中访问，如函数内部。num 是局部绑定，存在于以上两个函数中。num 的重要之处在于它不能在这些函数之外访问，并且每个函数中局部绑定的 num 都是唯一的，不会相互覆盖。
为了实现它们，首先，定义操作码，让虚拟机创建局部绑定并检索它们
然后扩展编译器，让它可以发出正确的新操作码。这意味着它需要区分局部绑定和全局绑定，以及不同函数中同名的局部绑定。
最后，在虚拟机中实现这些新指令和局部绑定。对于局部绑定而言，只需要在添加一个新的存储即可
7.2.1 局部绑定操作码
现在已经有两个全局绑定操作码，现在创建对应的新操作码：OpSetLocal、OpGetLocal
这两个字节码让虚拟机识别某绑定是当前正在执行的函数局部绑定，并且不用对全局绑定施加任何影响。局部绑定不应该覆盖全局绑定，也不应该被覆盖。
局部绑定的操作码将使用一字节的操作数，每个函数 256 个局部绑定对于普通的 Monkey 程序来说足够了。
// code/code.go
const (
// ...
OpGetLocal // 局部绑定get
OpSetLocal // 局部绑定set
)
// 操作码定义详细信息
var definitions = map[Opcode]*Definition{
// ...
OpGetLocal: {"OpGetLocal", []int{1}},
OpSetLocal: {"OpSetLocal", []int{1}},
}
测试
// code/code_test.go
func TestMake(t *testing.T) {
ts := []struct {
op Opcode
operands []int
expected []byte
}{
// ...
{OpGetLocal, []int{255}, []byte{byte(OpGetLocal), 255}},
}
// ...
}
// code/code.go
func Make(op Opcode, operands ...int) []byte {
// ...
// 第一位是操作码，已经放入
offset := 1
// 遍历操作数
for i, o := range operands {
width := def.OperandWidths[i]
switch width {
case 2:
// 操作数大端编码为uint16到instruction
binary.BigEndian.PutUint16(instruction[offset:], uint16(o))
case 1:
instruction[offset] = byte(o)
}
// 向后移动，继续遍历操作数
offset += width
}
return instruction
}
此时 Make 测试通过，可以生成单字节操作数指令，当目前无法对他们解码。为此，需要更新 ReadOperands 函数和 Instructions 上的调试方法 String()
// code/code_test.go
func TestReadOperands(t *testing.T) {
ts := []struct {
op Opcode
operands []int
bytesRead int
}{
// ...
{OpGetLocal, []int{255}, 1},
}
// ...
}
func TestInstructionsString(t *testing.T) {
instructions := []Instructions{
Make(OpAdd),
Make(OpGetLocal, 1),
Make(OpConstant, 2),
Make(OpConstant, 65535),
}
expected := `0000 OpAdd
0001 OpGetLocal 1
0003 OpConstant 2
0006 OpConstant 65535
`
// ...
}
我们创建一个 ReadUint8 函数并在 ReadOperands 中使用
// code/code.go
func ReadOperands(def *Definition, ins Instructions) ([]int, int) {
operands := make([]int, len(def.OperandWidths))
offset := 0
for i, width := range def.OperandWidths {
switch width {
case 2:
operands[i] = int(ReadUint16(ins[offset:]))
case 1:
operands[i] = int(ReadUint8(ins[offset:]))
}
offset += width
}
return operands, offset
}
func ReadUint8(ins Instructions) uint8 {
return uint8(ins[0])
}
读取一字节并将其转换为 uint8 无法是让编译器从现在开始，以这种方式处理单字节操作数。
7.2.2 编译局部绑定
对于局部绑定而言，“在哪”以及“如何”与全局绑定一样，只是作用域发生改变。这也是编译局部绑定的主要跳转：确定是为全局绑定还是为局部绑定发出指令。
测试
// compiler/compiler_test.go
func TestLetStatementScopes(t *testing.T) {
ts := []compilerTestCase{
{
input: `
let num = 55;
fn() { num }
`,
expectedConstants: []interface{}{
55,
[]code.Instructions{
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpReturnValue),
},
},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpPop),
},
},
{
input: `
fn(){
let num = 55;
num
}
`,
expectedConstants: []interface{}{
55,
[]code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpSetLocal, 0),
code.Make(code.OpGetLocal, 0),
code.Make(code.OpReturnValue),
},
},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 1),
code.Make(code.OpPop),
},
},
{
input: `
fn() {
let a = 55;
let b = 77;
a+b
}
`,
expectedConstants: []interface{}{
55,
77,
[]code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpSetLocal, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpSetLocal, 1),
code.Make(code.OpGetLocal, 0),
code.Make(code.OpGetLocal, 1),
code.Make(code.OpAdd),
code.Make(code.OpReturnValue),
},
},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 2),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
测试将失败，因为编译器将 let 语句创建的每个绑定都视为全局绑定。为了解决这个问题，必须扩展符号表。
1. 扩展符号表
符号表仅能识别全局作用域。现在需要扩展它，以便区分不同作用域，同时区分给定符号是在哪个作用域中定义。
进入或离开编译器作用域时，符号表应该追踪我们所在的作用域，并将其附加到我们在该作用域中定义的每个符号。随后，当需要解析符号时，符号表应该向我们反馈先前定义的符号所具有的唯一索引以及它是在哪个作用域内定义的。
一旦使 SymbolTable 实现递归，实现这个功能就不需要很多代码。
// compiler/symbol_table_test.go
func TestResolveLocal(t *testing.T) {
global := NewSymbolTable()
global.Define("a")
global.Define("b")
local := NewEnclosedSymbolTable(global)
local.Define("c")
local.Define("d")
expected := []Symbol{
Symbol{Name: "a", Scope: GlobalScope, Index: 0},
Symbol{Name: "b", Scope: GlobalScope, Index: 1},
Symbol{Name: "c", Scope: LocalScope, Index: 0},
Symbol{Name: "d", Scope: LocalScope, Index: 1},
}
for _, sym := range expected {
res, ok := local.Resolve(sym.Name)
if !ok {
t.Errorf("name %s not resolvable", sym.Name)
continue
}
if res != sym {
t.Errorf("expected %s to resolve to %+v, got=%+v", sym.Name, sym, res)
}
}
}
我们期望，在 local 上调用 Resolve 函数解析这 4 个符号时，返回的结果是这些符号的正确作用域和索引
还需要确保 SymbolTable 可以处理任意嵌套和封闭的符号表：
// compiler/compiler_test.go
func TestResolveNestedLocal(t *testing.T) {
global := NewSymbolTable()
global.Define("a")
global.Define("b")
firstLocal := NewEnclosedSymbolTable(global)
firstLocal.Define("c")
firstLocal.Define("d")
secondLocal := NewEnclosedSymbolTable(firstLocal)
secondLocal.Define("e")
secondLocal.Define("f")
ts := []struct {
table *SymbolTable
expectedSymbols []Symbol
}{
{
firstLocal,
[]Symbol{
Symbol{Name: "a", Scope: GlobalScope, Index: 0},
Symbol{Name: "b", Scope: GlobalScope, Index: 1},
Symbol{Name: "c", Scope: LocalScope, Index: 0},
Symbol{Name: "d", Scope: LocalScope, Index: 1},
},
},
{
secondLocal,
[]Symbol{
Symbol{Name: "a", Scope: GlobalScope, Index: 0},
Symbol{Name: "b", Scope: GlobalScope, Index: 1},
Symbol{Name: "e", Scope: LocalScope, Index: 0},
Symbol{Name: "f", Scope: LocalScope, Index: 1},
},
},
}
for _, tt := range ts {
for _, sym := range tt.expectedSymbols {
res, ok := tt.table.Resolve(sym.Name)
if !ok {
t.Errorf("name %s not resolvable", sym.Name)
continue
}
if res != sym {
t.Errorf("expected %s to resolve to %+v, god=%+v", sym.Name, sym, res)
}
}
}
}
我们期望全局符号表和两个局部符号表都定义了自己的符号，每个局部符号表定义符号不会干扰另一个符号表，并且嵌套符号表中的全局符号仍然能解析为正确的符号。最后，还要确保符号表定义的符号都是从 0 开始，这样这些索引值就可以用作 OpSetLocal 和 OpGetLocal 的操作数，无需绑定到其他作用域
符号表的嵌套对 SymbolTable 的 Define 方法有影响，所以需要更新现有的 TestDefine 测试
// compiler/symbol_table_test.go
func TestDefine(t *testing.T) {
expected := map[string]Symbol{
"a": Symbol{Name: "a", Scope: GlobalScope, Index: 0},
"b": Symbol{Name: "b", Scope: GlobalScope, Index: 1},
"c": Symbol{Name: "c", Scope: LocalScope, Index: 0},
"d": Symbol{Name: "d", Scope: LocalScope, Index: 1},
"e": Symbol{Name: "e", Scope: LocalScope, Index: 0},
"f": Symbol{Name: "f", Scope: LocalScope, Index: 1},
}
global := NewSymbolTable()
a := global.Define("a")
if a != expected["a"] {
t.Errorf("expected a=%+v, got=%+v", expected["a"], a)
}
b := global.Define("b")
if b != expected["b"] {
t.Errorf("expected b=%+v, got=%+v", expected["b"], b)
}
firstLocal := NewEnclosedSymbolTable(global)
c := firstLocal.Define("c")
if c != expected["c"] {
t.Errorf("expected c=%+v, got=%+v", expected["c"], c)
}
d := firstLocal.Define("d")
if d != expected["d"] {
t.Errorf("expected d=%+v, got=%+v", expected["d"], d)
}
secondLocal := NewEnclosedSymbolTable(firstLocal)
e := secondLocal.Define("e")
if e != expected["e"] {
t.Errorf("Expected e=%+v, got=%+v", expected["e"], e)
}
f := secondLocal.Define("f")
if f != expected["f"] {
t.Errorf("Expected f=%+v, got=%+v", expected["f"], f)
}
}
我们需要使 Define 和 Resolve 能在局部的符号表上运行。好在这两个方法本质上都属于同一实现：SymbolTable 的递归定义允许将一个符号表包含在其他符号表中。
给 SymbolTable 添加一个 Outer 字段
// compiler/symbol_table.go
type SymbolTable struct {
Outer *SymbolTable
store map[string]Symbol
numDefinitions int
}
此时可以实现 NewEnclosedSymbolTable 函数。该函数创建了一个带 Outer 符号表的*SymbolTable：
// compiler/symbol_table.go
func NewEnclosedSymbolTable(outer *SymbolTable) *SymbolTable {
s := NewSymbolTable()
s.Outer = outer
return s
}
定义 LocalScope 常量
// compiler/symbol_table.go
const (
LocalScope SymbolScope = "LOCAL"
GlobalScope SymbolScope = "GLOBAL"
)
接下来修改 Define 和 Resolve 方法，让它们可以使用 Outer 字段。如果被调用的 SymbolTable 没有包含在另一个 SymbalTable 中，即它没有设置 Outer 字段，那么它的作用域是全局的。如果是封闭的，则它的作用域是局部的。符号表中定义的每个符号都应该具有正确的作用域。
// compiler/symbol_table.go
func (s *SymbolTable) Define(name string) Symbol {
symbol := Symbol{Name: name, Index: s.numDefinitions}
if s.Outer == nil {
symbol.Scope = GlobalScope
} else {
symbol.Scope = LocalScope
}
s.store[name] = symbol
s.numDefinitions++
return symbol
}
Resolve 需要先从调用它的 SymbolTable 里找符号定义，找不到则调用 Outer 的 Resolve 来从 Outer 的作用域里找符号，如此循环递归，直到找到或遍历完没有发现符号定义。
// compiler/symbol_table.go
func (s *SymbolTable) Resolve(name string) (Symbol, bool) {
obj, ok := s.store[name]
if !ok && s.Outer != nil {
obj, ok = s.Outer.Resolve(name)
return obj, ok
}
return obj, ok
}
此时测试只剩下编译器的错误(TestLetStatementScopes)
可能你已经思考：“如果在局部作用域中定义一个符号，然后在深一层的作用域中解析它，该符号会拥有局部作用域吗（即时从最深层的角度看，它是定义在外部范围内的？），一旦实现了闭包，就能解决这个问题。
2. 编译作用域
在编译函数字面量时，它的 enterScope 函数和 leaveScope 函数会被调用，以确保发出的指令在所需的地方结束。现在需要扩展它们，让它们能支持包含和‘取消包含’符号表。
测试
// compiler/compiler_test.go
func TestCompilerScops(t *testing.T) {
compiler := New()
if compiler.scopeIndex != 0 {
t.Errorf("scopeIndex wrong. got=%d, want=%d", compiler.scopeIndex, 0)
}
//
globalSymbolTable := compiler.symbolTable
compiler.emit(code.OpMul)
compiler.enterScope()
if compiler.scopeIndex != 1 {
t.Errorf("scopeIndex wrong. got=%d, want=%d", compiler.scopeIndex, 1)
}
compiler.emit(code.OpSub)
if len(compiler.scopes[compiler.scopeIndex].instructions) != 1 {
t.Errorf("instructions length wrong. got=%d", len(compiler.scopes[compiler.scopeIndex].instructions))
}
last := compiler.scopes[compiler.scopeIndex].lastInstruction
if last.Opcode != code.OpSub {
t.Errorf("lastInstruction.Opcode wrong. got=%d, want=%d", last.Opcode, code.OpSub)
}
//
if compiler.symbolTable != globalSymbolTable {
t.Errorf("compiler did not enclose symbolTable")
}
compiler.leaveScope()
if compiler.scopeIndex != 0 {
t.Errorf("scopeIndex wrong. got=%d, want=%d", compiler.scopeIndex, 0)
}
//
if compiler.symbolTable.Outer != globalSymbolTable {
t.Errorf("compiler did not restore global symbol table")
}
if compiler.symbolTable.Outer != nil {
t.Errorf("compiler modifier global symbol table incorrectly")
}
compiler.emit(code.OpAdd)
if len(compiler.scopes[compiler.scopeIndex].instructions) != 2 {
t.Errorf("instructions.Opcode wrong. got=%d, want=%d", last.Opcode, code.OpAdd)
}
last = compiler.scopes[compiler.scopeIndex].lastInstruction
if last.Opcode != code.OpAdd {
t.Errorf("lastInstruction.Opcode wrong. got=%d, want=%d", last.Opcode, code.OpAdd)
}
previous := compiler.scopes[compiler.scopeIndex].previousInstruction
if previous.Opcode != code.OpMul {
t.Errorf("previousInstruction.Opcode wrong. got=%d, want=%d", previous.Opcode, code.OpMul)
}
}
为了让测试通过，每次进入作用域时，需要在全局表中包含一个符号表
// compiler/compiler.go
func (c *Compiler) enterScope() {
// ...
c.symbolTable = NewEnclosedSymbolTable(c.symbolTable)
}
这使得编译器在编译函数体时能够使用一个新的、封闭的符号表。然后需要在函数完全编译后再撤销它。
func (c *Compiler) leaveScope() code.Instructions {
// ...
c.symbolTable = c.symbolTable.Outer
return instructions
}
现在可以使用 Symbol 的作用域来发出正确的指令了
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
case *ast.LetStatement:
err := c.Compile(node.Value)
if err != nil {
return err
}
symbol := c.symbolTable.Define(node.Name.Value)
if symbol.Scope == GlobalScope {
c.emit(code.OpSetGlobal, symbol.Index)
} else {
c.emit(code.OpSetLocal, symbol.Index)
}
// ...
}
return nil
}
接下来是修改给解析符号的部分
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
case *ast.Identifier:
symbol, ok := c.symbolTable.Resolve(node.Value)
if !ok {
return fmt.Errorf("undefined variable %s", node.Value)
}
if symbol.Scope == GlobalScope {
c.emit(code.OpGetGlobal, symbol.Index)
} else {
c.emit(code.OpGetLocal, symbol.Index)
}
// ...
}
return nil
}
7.2.3 在虚拟机中实现局部绑定
这意味着需要在执行 OpSetLocal 指令时创建绑定，然后在执行 OpGetLocal 指令时解析所创建的绑定。而存储是局部的。
局部绑定的存储不仅是一个实现细节，而且可以在虚拟机的性能中发挥关键作用。最重要的是，它不应该关心虚拟机用户在哪里以及如何存储，而是能够按预期工作。
// vm/vm_test.go
func TestCallingFunctionWithBindings(t *testing.T) {
ts := []vmTestCase{
{
input: `
let one = fn() { let one = 1; one };
one();
`,
expected: 1,
},
{
input: `
let oneAndTwo = fn() { let one = 1; let two = 2; one + two; };
oneAndTwo();
`,
expected: 3,
},
{
input: `
let oneAndTwo = fn() { let one = 1; let two = 2; one + two; };
let threeAndFour = fn() { let three = 3; let four = 4; three + four; };
oneAndTwo() + threeAndFour();
`,
expected: 10,
},
{
input: `
let firstFoobar = fn() { let foobar = 50; foobar; };
let secondFoobar = fn() { let foobar = 100; foobar; };
firstFoobar() + secondFoobar();
`,
expected: 150,
},
{
input: `
let globalSeed = 50;
let minusOne = fn() {
let num = 1;
globalSeed - num;
}
let minusTwo = fn() {
let num = 2;
globalSeed - num;
}
minusOne() + minusTwo();
`,
expected: 97,
},
}
runVmTests(t, ts)
}
局部绑定像全局绑定一样，拥有唯一索引。也可以使用 OpSetLocal 指令的操作数，即唯一索引，作为数据结构的索引来存储和检索绑定到名称的值。
那么要索引到什么数据结构呢？这个数据结构在哪里？不能只使用存储在虚拟机上的 globals 切片，因为这首先就无法使用局部绑定。
现在有两个主要选项。
- 1.是动态分配局部绑定并将它们存储在其自己的数据结构中，例如，这个数据结构可能是一个切片，每调用一个函数，就分配一个空切片用于存储和检索局部绑定。
- 2.是复用已有的数据结构。在内存中有一个地方存储与当前正在调用的函数相关的数据，即栈。
在栈中存储局部绑定更有细节、更能学习编译器和虚拟机的知识、也更常见，但是比较复杂一点。
工作原理：在虚拟机中遇到 OpCall 指令时，先将栈指针放置到一边，以便后续使用。然后增加栈指针，添加的值是将要执行的函数所使用的局部绑定数量。结果是栈中会有一个“空缺”，在增加栈指针时，并没有往栈中推送任何值，由此导致栈中产生了一块没有任何值的区域。空缺的下方是函数调用之前压栈的所有值。空缺的上方是函数的工作区，它会将函数执行时需要的值压栈和弹栈。
栈中的空缺处就是要存储局部绑定的地方。我们不会使用局部绑定的唯一索引作为另一个数据结构的键，而是作为栈中空缺处的索引。
我们已经有了完成它的必要部分：执行函数之前栈指针的值，这是空缺的下边界；以及随局部绑定增加的索引。将这两部分加在一起可以计算出每个局部绑定的栈槽索引。以这种方式计算的每个索引都用作空缺的偏移量，并指向将存储局部绑定的插槽。
在一个函数指向完之后，由于先前将栈指针的值放在一边，因此可以直接将它压栈，从而“重置”栈。这样不仅删除了函数调用可能留在栈中的所有内容，还删除了保存在空缺处的局部绑定。
虚拟机不知道一个函数中会使用多少个局部绑定，但是在编译器中将这个信息传递给虚拟机很简单。
// object/object.go
type CompiledFunction struct {
Instructions code.Instructions
NumLocals int
}
NumLocals 记录了函数创建了多少个局部绑定。在编译器中，可以查询符号表在编译函数时定义了多少个符号，然后将该数字存入 NumLocals 中
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.FunctionLiteral:
// ...
numLocals := c.symbolTable.numDefinitions
instructions := c.leaveScope()
compiledFn := &object.CompiledFunction{
Instructions: instructions,
NumLocals: numLocals,
}
c.emit(code.OpConstant, c.addConstant(compiledFn))
}
return nil
}
需要做的另一件事，是在执行函数之前跟踪栈指针的值，在执行后恢复该值。也就是说，需要一个与函数调用一样长的临时存储。我们可以用 Frame 实现。
// vm/frame.go
type Frame struct {
fn *object.CompiledFunction
ip int
basePointer int
}
func NewFrame(fn *object.CompiledFunction, basePointer int) *Frame {
return &Frame{fn: fn, ip: -1, basePointer: basePointer}
}
“基指针”（basePointer），将这个名称赋予指向当前调用栈帧底部的指针是常见的做法。是函数执行时大量引用的基础，有时也称为“帧指针”。在压栈新帧之前，需要对其进行初始化。
// vm/vm.go
func New(bytecode *compiler.Bytecode) *VM {
// ...
mainFrame := NewFrame(mainFn, 0)
// ...
}
func (vm *VM) Run() error {
var ip int
var ins code.Instructions
var op code.Opcode
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
// ...
// 解码
switch op {
// ...
case code.OpCall:
// 从当前栈帧取出函数字面量
fn, ok := vm.stack[vm.sp-1].(*object.CompiledFunction)
if !ok {
return fmt.Errorf("calling non-function")
}
// 进入函数栈帧
frame := NewFrame(fn, vm.sp)
vm.pushFrame(frame)
// ...
}
}
return nil
}
现在有一个 basePointer（vm.sp 的当前值），并且知道一个函数会使用多少局部变量。这就留下了两个任务：在执行函数之前为栈中的局部绑定分配空间，也就是创建“空缺”；在虚拟机中实现 OpSetLocal 和 OpGetLocal 指令，以便使用。
“在栈中分配空间”就是指，在不将任何内容压栈的情况下增加 vm.sp 的值。由于在函数执行前已经将 vm.sp 的值放置在一边，因此有一个地方很适合完成这个任务
// vm/vm.go
func (vm *VM) Run() error {
var ip int
var ins code.Instructions
var op code.Opcode
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
// ...
// 解码
switch op {
// ...
case code.OpCall:
// 从当前栈帧取出函数字面量
fn, ok := vm.stack[vm.sp-1].(*object.CompiledFunction)
if !ok {
return fmt.Errorf("calling non-function")
}
// 进入函数栈帧
frame := NewFrame(fn, vm.sp)
vm.pushFrame(frame)
vm.sp = frame.basePointer + fn.NumLocals
// ...
}
}
return nil
}
vm.sp = frame.basePointer + fn.NumLocals 明确指出起点是 basePointer，并且在栈中预留 fn.NumLocals 个槽。这些槽可能不包含或包含旧值，但是不需要担心，这块区域依然可以用于局部绑定，而且栈的正常功能————临时变量压栈和弹栈————并不会受影响
接下来在虚拟机中实现 OpSetLocal 和 OpGetLocal
OpSetLocal: 我们需要读入操作数，将需要绑定的值从栈中弹出并存储。
// vm/vm.go
func (vm *VM) Run() error {
// ...
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
// ...
// 解码
switch op {
// ...
case code.OpSetLocal:
// 解码操作数
localIndex := code.ReadUint8(ins[ip+1:])
vm.currentFrame().ip += 1
frame := vm.currentFrame()
// 将栈顶值弹出并保存到 指定偏移量(basePointer+int(localIndex)) 的位置
vm.stack[frame.basePointer+int(localIndex)] = vm.pop()
}
}
return nil
}
OpGetLocal: 检索值而非赋值
// vm/vm.go
func (vm *VM) Run() error {
// ...
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
// ...
// 解码
switch op {
// ...
case code.OpGetLocal:
localIndex := code.ReadUint8(ins[ip+1:])
vm.currentFrame().ip += 1
frame := vm.currentFrame()
err := vm.push(vm.stack[frame.basePointer+int(localIndex)])
if err != nil {
return err
}
}
}
return nil
}
接下来需要在函数调用完后清理栈，执行时机是遇到 OpReturnValue 或 OpReturn 指令时，当前，我们只是将返回值和刚刚执行的函数从栈中弹出。现在需要摆脱局部绑定。最简单的方法就是将栈指针设置为帧的 basePointer，它保存了刚刚执行的函数。
// vm/vm.go
func (vm *VM) Run() error {
// ...
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
// ...
// 解码
switch op {
// ...
case code.OpReturnValue:
// 弹出返回值
returnValue := vm.pop()
frame := vm.popFrame()
// basePointer指向 函数call之后 local指令之前 的地址
vm.sp = frame.basePointer - 1
err := vm.push(returnValue)
if err != nil {
return err
}
case code.OpReturn:
frame := vm.popFrame()
vm.sp = frame.basePointer - 1
err := vm.push(Null)
if err != nil {
return err
}
}
return nil
}
当一个函数返回时，我们首先将帧从栈帧中取出。然后将 vm.sp 设置为 frame.basePointer-1，这是一种优化措施：通过将 vm.sp 设置为 frame.basePointer-1，sp 指针指向刚刚执行的函数之前，而不是刚好指向函数。就不需要再执行一次 vm.pop()来弹出。(之后产生的虚拟机字节码会覆盖之前后面的那些字节码)
而且，我们在没有明确着手的情况下，对头等函数的能将进行了升级。现在可以在另一个函数中将函数赋值给名称
// vm/vm_test.go
func TestFirstClassFunctions(t *testing.T) {
ts := []vmTestCase{
// ...
{
input: `
let returnsOneReturner = fn() {
let returnsOne = fn() { 1; };
returnsOne;
};
returnsOneReturner()();
`,
expected: 1,
},
}
runVmTests(t, ts)
}
7.3 参数
当函数执行时，传入的参数值会绑定给参数名称。由此可见，函数调用的参数是一种特殊的局部绑定。
它们唯一的不同是创建方式，局部绑定由用户使用 let 语句显式创建，最终会生成由编译器发出的 OpSetLocal 指令。参数则不同，它隐式绑定给名称，由虚拟机和编译器在幕后完成。
let globalNum = 10;
let sum = fn(a, b) {
let c = a + b;
c + globalNum
};
let outer = fn() {
sum(1, 2) + sum(3, 4) + globalNum;
};
outer() + globalNum
7.3.1 编译带参数的函数调用
当前的调用约定的主要内容是：将需要调用的函数压栈，发出 OpCall 指令。当前面临的问题是，在哪放置函数调用的参数————内存位置上的哪里，以及调用约定中的哪里
内存位置上可以使用栈。最简单的方法就是函数压栈后立即将参数压栈。
如果采用这种方案，则调用约定改为：将需要调用的函数压栈，紧接着将所有调用的参数压栈，随后发出 OpCall 指令
但是有个问题，就是虚拟机不知道栈顶有多少参数。
OpCall 指令，在推送一个新的帧之前，我们将要调用的函数从栈顶取出。对于新的调用约定，现在栈中的函数之上可能有零个或者多个参数。那么如何到达栈中的函数并执行它？
用于函数是普通的 object.Object，无法通过遍历栈的方式查找 object.CompiledFunction。
有一个简单完美的解决方案：给 OpCall 操作码一个操作数，用来表示函数参数的个数，操作数大小为一字节（可以表示 256 个数）
// code/code.go
var definitions = map[Opcode]*Definition{
// ...
OpCall: {"OpCall", []int{1}},
// ...
}
更新编译器测试
// compiler/compiler_test.go
func TestFunctionCalls(t *testing.T) {
ts := []compilerTestCase{
{
// ...
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 1), // 被编译的函数
code.Make(code.OpCall, 0),
code.Make(code.OpPop),
},
},
{
// ...
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 1), // 被编译的函数
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpCall,0),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
虚拟机受新操作数影响，在编写测试反馈真正需要的内容之前，直接跳过它。
// vm/vm.go
func (vm *VM) Run() error {
// ...
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
// ...
switch op {
// ...
case code.OpCall:
vm.currentFrame().ip += 1
// ...
}
}
return nil
}
为 TestFuntionCalls 添加新的测试用例来测试：通过发出将参数压栈的指令来确认编译器符号新调用约定。
// compiler/compiler_test.go
func TestFunctionCalls(t *testing.T) {
ts := []compilerTestCase{
// ...
{
input: `
let oneArg = fn(a) { };
oneArg(24)
`,
expectedConstants: []interface{}{
[]code.Instructions{
code.Make(code.OpReturn),
},
24,
},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpCall, 1),
code.Make(code.OpPop),
},
},
{
input: `
let manyArg = fn(a, b, c) { };
manyArg(24, 25, 26);
`,
expectedConstants: []interface{}{
[]code.Instructions{
code.Make(code.OpReturn),
},
24, 25, 26,
},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpConstant, 2),
code.Make(code.OpConstant, 3),
code.Make(code.OpCall, 3),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
更新编译器中的*ast.CallExpression 的 case 分支
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.CallExpression:
err := c.Compile(node.Function)
if err != nil {
return err
}
for _, a := range node.Arguments {
err := c.Compile(a)
if err != nil {
return err
}
}
c.emit(code.OpCall, len(node.Arguments))
}
return nil
}
现在，有了新的调用约定，只是第一步，我们还需要将函数调用的参数压栈。
我们通过循环按顺序编译参数来做到。每个参数都是*ast.Expression，会被编译成一条或多条将值压栈的指令。结果是参数位于需要调用的函数之上，而正是调用约定需要它们的位置。为了使虚拟机能够处理位于函数之上的参数，我们使用 len(node.Arguments)作为 OpCall 的参数
7.3.2 将引用解析为参数
在函数调用时，参数位于栈中，如何在函数执行时访问它们？
是否要添加新的操作码来将参数压栈？如果是，就需要在符号表中为参数提供它们自己的作用域和索引。否则，当遇到对参数的引用时，不知道应该发出哪个操作码。
如果目标是明确处理不同于局部绑定的参数，这会带来更多的灵活性，当是 Monkey 的函数的参数是一种特殊的局部绑定。唯一要做的就是将它们处理为局部绑定。
这意味着需要为每个函数参数的引用发出 OpGetLocal 指令。
// compiler/compiler_test.go
func TestFunctionCalls(t *testing.T) {
ts := []compilerTestCase{
// ...
{
input: `
let oneArg = fn(a) { a };
oneArg(24);
`,
expectedConstants: []interface{}{
[]code.Instructions{
code.Make(code.OpGetLocal, 0),
code.Make(code.OpReturnValue),
},
24,
},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpCall, 1),
code.Make(code.OpPop),
},
},
{
input: `
let manyArg = fn(a, b, c) { a; b; c };
manyArg(24, 25, 26);
`,
expectedConstants: []interface{}{
[]code.Instructions{
code.Make(code.OpGetLocal, 0),
code.Make(code.OpPop),
code.Make(code.OpGetLocal, 1),
code.Make(code.OpPop),
code.Make(code.OpGetLocal, 2),
code.Make(code.OpReturnValue),
},
24, 25, 26,
},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpConstant, 2),
code.Make(code.OpConstant, 3),
code.Make(code.OpCall, 3),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
现在需要将函数的参数定义为局部绑定。
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.FunctionLiteral:
c.enterScope()
for _, p := range node.Parameters {
c.symbolTable.Define(p.Value)
}
err := c.Compile(node.Body)
if err != nil {
return err
}
// ...
}
return nil
}
7.3.3 虚拟机中的参数
本章目标：
let globalNum = 10;
let sum = fn(a, b) {
let c = a + b;
c + globalNum;
};
let outer = fn() {
sum(1, 2) + sum(3, 4) + globalNum;
};
outer() + globalNum
测试
// vm/vm_test.go
func TestCallingFunctionWithArgumentsAndBindings(t *testing.T) {
ts := []vmTestCase{
{
input: `
let identity = fn(a) { a; };
identity(4);
`,
expected: 4,
},
{
input: `
let sum = fn(a, b) { a + b; };
sum(1, 2);
`,
expected: 3,
},
}
runVmTests(t, ts)
}
测试告诉我们虚拟机无法找到栈中的参数
虚拟机仍然认为函数在栈顶，这是根据旧的调用约定解析的。但是现在编译器更新了，发出的指令不仅将函数压栈，也将参数压栈，所以虚拟机显式它在调用非函数：它实际调用的是参数
解决方法是使用 OpCall 的操作数，它用于进一步向下访问栈以到达函数。
// vm/vm.go
func (vm *VM) Run() error {
// ...
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
// ...
switch op {
// ...
case code.OpCall:
numArgs := code.ReadUint8(ins[ip+1:])
vm.currentFrame().ip += 1
// 从当前栈帧取出函数字面量
fn, ok := vm.stack[vm.sp-1-int(numArgs)].(*object.CompiledFunction)
if !ok {
return fmt.Errorf("calling non-function")
}
// 进入函数栈帧
frame := NewFrame(fn, vm.sp)
vm.pushFrame(frame)
vm.sp = frame.basePointer + fn.NumLocals
}
}
return nil
}
这里显示从栈中弹出的值是 nil，也就是说，虚拟机没有在栈中找到参数。
参数位于栈顶，即被调用函数的上方，那是存储局部绑定的的地方。我们将参数视为局部绑定并计划用 OpGetLocal 检索它们，所以这是正确的位置。为什么虚拟机找不到呢？
因为栈指针太高。在设置新的帧时，将栈指针与 basePointer 一起初始化的方式已经过时。
Frame 的 basePointer 有两个用途。首先，作为一个“重置按钮”，它通过将 vm.sp 设置为 basePointer-1 可以清除刚刚执行的函数以及该函数滞留在栈中的所有内容。
其次，它可以作为局部绑定的引用。这是容易出错的地方，在执行一个函数之前，将 basePointer 设置为 vm.sp 的当前值，然后通过函数将使用的局部绑定的数量来增加 vm.sp，这就产生了“空缺”：栈中可以存储和检索局部绑定的 n 个插槽。
测试失败的原因是，在执行函数之前，栈中已经有了想用作局部变量的东西：调用的参数。我们希望使用与其他局部绑定相同的公式访问它们：basePointer 加上单独的局部绑定索引。问题是，现在初始化一个新的帧时，栈是这样的：
将参数压栈后，我们将 basePointer 设置为 vm.sp 的当前值。导致 basePointer 加上局部绑定的索引都指向空槽。虚拟机得到 nil，而不是想要的参数。
现在需要调整 basePointer = vm.sp - numArguments
// vm/vm.go
func (vm *VM) Run() error {
var ip int
var ins code.Instructions
var op code.Opcode
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
vm.currentFrame().ip++
ip = vm.currentFrame().ip
ins = vm.currentFrame().Instructions()
op = code.Opcode(ins[ip])
// 解码
switch op {
// ...
case code.OpCall:
numArgs := code.ReadUint8(ins[ip+1:])
vm.currentFrame().ip += 1
err := vm.callFuntion(int(numArgs))
if err != nil {
return err
}
}
}
return nil
}
func (vm *VM) callFuntion(numArgs int) error {
// 从当前栈帧取出函数字面量
fn, ok := vm.stack[vm.sp-1-numArgs].(*object.CompiledFunction)
if !ok {
return fmt.Errorf("calling non-function")
}
// 进入函数栈帧
frame := NewFrame(fn, vm.sp-numArgs)
vm.pushFrame(frame)
vm.sp = frame.basePointer + fn.NumLocals
return nil
}
测试
// vm/vm_test.go
func TestCallingFunctionWithArgumentsAndBindings(t *testing.T) {
ts := []vmTestCase{
// ...
{
input: `
let sum = fn(a, b) {
let c = a + b;
c;
};
sum(1, 2);
`,
expected: 3,
},
{
input: `
let sum = fn(a, b) {
let c = a + b;
c;
};
sum(1, 2) + sum(3, 4);
`,
expected: 10,
},
{
input: `
let sum = fn(a, b) {
let c = a + b;
c;
};
let outer = fn() {
sum(1, 2) + sum(3, 4);
};
outer();
`,
expected: 10,
},
}
runVmTests(t, ts)
}
这些测试用例确保手动创建的局部绑定与参数可以混用：在一个函数中，多次调用的同一个函数中，以及在另一个函数中多次调用的一个函数中。
新测试
// vm/vm_test.go
func TestCallingFunctionWithArgumentsAndBindings(t *testing.T) {
ts := []vmTestCase{
// ...
{
input: `
let globalNum = 10;
let sum = fn(a, b) {
let c = a + b;
c + globalNum;
};
let outer = fn() {
sum(1, 2) + sum(3, 4) + globalNum;
};
outer() + globalNum;
`,
expected: 50,
},
}
runVmTests(t, ts)
}
接下来需要确保使用错误数量的参数调用函数时，栈不会崩溃。
// vm/vm_test.go
func TestCallingFunctionWithWrongArguments(t *testing.T) {
ts := []vmTestCase{
{
input: `fn() { 1; }(1);`,
expected: `wrong number of arguments: want=0, got=1`,
},
{
input: `fn(a) { a; }();`,
expected: `wrong number of arguments: want=1, got=0`,
},
{
input: `fn(a, b) { a + b; }(1);`,
expected: `wrong number of arguments: want=2, got=1`,
},
}
for _, tt := range ts {
program := parse(tt.input)
comp := compiler.New()
err := comp.Compile(program)
if err != nil {
t.Fatalf("compiler error: %s", err)
}
vm := New(comp.Bytecode())
err = vm.Run()
if err == nil {
t.Fatalf("expected VM error but resulted in none.")
}
if err.Error() != tt.expected {
t.Fatalf("wrong VM error: want=%q, got=%q", tt.expected, err)
}
}
}
我们期望一条错误信息，但是没有。为了解决这个问题，进行修改
// object/object.go
type CompiledFunction struct {
Instructions code.Instructions
NumLocals int
NumParameters int
}
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.FunctionLiteral:
// ...
compiledFn := &object.CompiledFunction{
Instructions: instructions,
NumLocals: numLocals,
NumParameters: len(node.Parameters),
}
c.emit(code.OpConstant, c.addConstant(compiledFn))
}
return nil
}
// vm/vm.go
func (vm *VM) callFuntion(numArgs int) error {
// 从当前栈帧取出函数字面量
fn, ok := vm.stack[vm.sp-1-numArgs].(*object.CompiledFunction)
if !ok {
return fmt.Errorf("calling non-function")
}
if numArgs != fn.NumParameters {
return fmt.Errorf("wrong number of arguments: want=%d, got=%d", fn.NumParameters, numArgs)
}
// ...
}
8. 内置函数
本章目标是将内置函数构建到字节码编译器和虚拟机中
len([1, 2, 3]) // 3
first([1, 2, 3]) // 1
last([1, 2, 3]) // 3
rest([1, 2, 3]) // [2,3]
push([1, 2, 3], 4) // [1,2,3,4]
puts("hello world")
我们最早将内置函数定义为私有，使用内部引用和私有的辅助函数，但是在 compiler 和 vm 包中，不方便使用
我们需要改变之前的代码
将私有函数变成公共的，将内置函数移动到 object 包中。
8.1 使修改变得简单
第一个任务是将内置函数移除 evaluator 包，同时保持求值器正常工作。附带任务：在移动时，定义内置函数，以便使用索引来访问单个函数并以稳定的形式遍历它们。
为了使*object.Builtin 与其名称配对，我们将使用结构体切片而不是 map，这能提供稳定的迭代，并有一个小型辅助函数允许我们按名称获取单个函数
从 len 开始，它返回数组或字符串的长度。
// object/builtins.go
package object
import "fmt"
var Builtins = []struct {
Name string
Builtin *Builtin
}{
{
"len",
&Builtin{Fn: func(args ...Object) Object {
if len(args) != 1 {
return newError("wrong number of arguments. got=%d, want=1", len(args))
}
switch arg := args[0].(type) {
case *Array:
return &Integer{Value: int64(len(arg.Elements))}
case *String:
return &Integer{Value: int64(len(arg.Value))}
default:
return newError("argument to `len` not supported, got %s", args[0].Type())
}
},
},
},
}
func newError(format string, a ...interface{}) *Error {
return &Error{Message: fmt.Sprintf(format, a...)}
}
添加辅助函数
// object/builtins.go
func GetBuiltinByName(name string) *Builtin {
for _, def := range Builtins {
if def.Name == name {
return def.Builtin
}
}
return nil
}
现在可以修改 evaluator 包中，对 len 的定义
// evaluator/builtins.go
var builtins = map[string]*object.Builtin{
// 传入字符串或数组,求长度
"len": object.GetBuiltinByName("len"),
// ...
}
测试通过，接下来是 puts
// object/evaluator.go
var Builtins = []struct {
Name string
Builtin *Builtin
}{
// ...
{
"puts",
&Builtin{Fn: func(args ...Object) Object {
for _, arg := range args {
fmt.Println(arg.Inspect())
}
return nil
},
},
},
}
这里没有返回 evaluator.NULL，因为如果返回 evaluator.NULL，则虚拟机要处理两个*object.NULL 实例。
在虚拟机中，用 vm.NULL 替换 nil 很容易，在求值器中，也需要将 nil 替换成 NULL，所以要修改代码。
// evaluator/evaluator.go
func applyFunction(fn object.Object, args []object.Object) object.Object {
switch fn := fn.(type) {
// ...
case *object.Builtin:
if result:=fn.Fn(args...);result!=nil{
return result
}
return NULL
default:
return newError("not a function: %s", fn.Type())
}
}
接下来移动 first，它返回数组的第一个元素(我稍加修改，多了对字符串的 first 操作)
// object/builtin.go
var Builtins = []struct {
Name string
Builtin *Builtin
}{
// ...
{
"first",
&Builtin{Fn: func(args ...Object) Object {
if len(args) != 1 {
return newError("wrong number of arguments. got=%d, want=1", len(args))
}
if args[0].Type() != ARRAY_OBJ && args[0].Type() != STRING_OBJ {
return newError("argument to `first` must ARRAY or STRING. got %s", args[0].Type())
}
switch args[0].Type() {
case ARRAY_OBJ:
arr := args[0].(*Array)
if len(arr.Elements) > 0 {
return arr.Elements[0]
}
case STRING_OBJ:
str := args[0].(*String)
if len(str.Value) > 0 {
return &String{Value: string(str.Value[0])}
}
}
return nil
},
},
},
}
接下来是 last
// object/evaluator.go
var Builtins = []struct {
Name string
Builtin *Builtin
}{
// ...
{
"last",
&Builtin{Fn: func(args ...Object) Object {
if len(args) != 1 {
return newError("wrong number of arguments. got=%d, want=1", len(args))
}
if args[0].Type() != ARRAY_OBJ && args[0].Type() != STRING_OBJ {
return newError("argument to `last` must ARRAY or STRING. got %s", args[0].Type())
}
switch args[0].Type() {
case ARRAY_OBJ:
arr := args[0].(*Array)
length := len(arr.Elements)
if len(arr.Elements) > 0 {
return arr.Elements[length-1]
}
case STRING_OBJ:
str := args[0].(*String)
length := len(str.Value)
if len(str.Value) > 0 {
return &String{Value: string(str.Value[length-1])}
}
}
return nil
},
},
},
}
接下来是 rest，获取除了第一个元素的其他元素
// object/builtins.go
var Builtins = []struct {
Name string
Builtin *Builtin
}{
// ...
{
"rest",
&Builtin{
Fn: func(args ...Object) Object {
if len(args) != 1 {
return newError("wrong number of arguments. got=%d, want=1", len(args))
}
if args[0].Type() != ARRAY_OBJ && args[0].Type() != STRING_OBJ {
return newError("argument to `rest` must ARRAY or STRING. got %s", args[0].Type())
}
switch args[0].Type() {
case ARRAY_OBJ:
arr := args[0].(*Array)
length := len(arr.Elements)
if length > 0 {
newElements := make([]Object, length-1, length-1)
copy(newElements, arr.Elements[1:length])
return &Array{Elements: newElements}
}
case STRING_OBJ:
str := args[0].(*String)
length := len(str.Value)
if len(str.Value) > 0 {
return &String{Value: string(str.Value[1:length])}
}
}
return nil
},
},
},
}
push，保持原数组不变，并分配一个新数组
// object/builtins.go
var Builtins = []struct {
Name string
Builtin *Builtin
}{
// ...
{
"push",
&Builtin{
Fn: func(args ...Object) Object {
if len(args) != 2 {
return newError("wrong number of arguments. got=%d, want=2", len(args))
}
if args[0].Type() != ARRAY_OBJ {
return newError("argument to `push` must be ARRAY. got %s", args[0].Type())
}
arr := args[0].(*Array)
length := len(arr.Elements)
newElements := make([]Object, length+1, length+1)
copy(newElements, arr.Elements)
newElements[length] = args[1]
return &Array{Elements: newElements}
},
},
},
}
此时的 evaluator 内置函数
// evaluator/builtins.go
var builtins = map[string]*object.Builtin{
// 传入字符串或数组,求长度
"len": object.GetBuiltinByName("len"),
// 输出内容
"puts": object.GetBuiltinByName("puts"),
// 传入数组,返回第一个元素
"first": object.GetBuiltinByName("first"),
// 传入数组,返回最后一个元素
"last": object.GetBuiltinByName("last"),
// 传入数组,返回除了第一个元素以外的所有元素,返回的是新分配的数组
"rest": object.GetBuiltinByName("rest"),
// 向数组末尾添加新元素,返回一个新数组
"push": object.GetBuiltinByName("push"),
// todo: 文件读写 网络编程 数据库(用原生的"database/sql")
}
8.2 做出改变：计划
希望保持现有的调用约定，将内置函数和调用的参数压栈，然后使用 OpCall 指令调用该函数。
从编译器的角度看，编译内置函数的调用表达式时，唯一不同的是函数最终在栈中的存在方式。
内置函数的定义不在全局和局部作用域内。有自己的作用域，我们需要将该作用域引入编译器及其符号表，以便正确解析对内置函数的引用
我们把这个作用域称为 BuiltinScope，其中会定义刚刚移到 object.Builtins 定义片段中的所有内置函数，并且按照原始顺序
当编译器（在符号表的帮助下）检测到对内置函数的引用时，将发出 OpGetBuiltin 指令。操作数是 object.Builtins 中所引用函数的索引
object.Bulitins 也可由虚拟机访问，可以使用指令的操作数从 object.Builtins 中获取正确的函数并将其推送到栈中，然后在那里调用该函数。
8.3 内置函数作用域
定义操作码
// code/code.go
const (
// ...
OpGetBuiltin // 获取内置函数
)
var definitions = map[Opcode]*Definition{
// ...
OpGetBuiltin: {"OpGetBuiltin", []int{1}},
}
测试
// compiler/compiler_test.go
func TestBuiltins(t *testing.T) {
ts := []compilerTestCase{
{
input: `
len([]);
push([],1);
`,
expectedConstants: []interface{}{1},
expectedInstructions: []code.Instructions{
code.Make(code.OpGetBuiltin, 0),
code.Make(code.OpArray, 0),
code.Make(code.OpCall, 1),
code.Make(code.OpPop),
code.Make(code.OpGetBuiltin, 5),
code.Make(code.OpArray, 0),
code.Make(code.OpConstant, 0),
code.Make(code.OpCall, 2),
code.Make(code.OpPop),
},
},
{
input: `fn() { len([]) }`,
expectedConstants: []interface{}{
[]code.Instructions{
code.Make(code.OpGetBuiltin, 0),
code.Make(code.OpArray, 0),
code.Make(code.OpCall, 1),
code.Make(code.OpReturnValue),
},
},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
测试内置函数总数能解析 BuiltinScope 中的某个符号，无论该符号表被另一个符号表内嵌多少次
// compiler/symbol_table_test.go
func TestDefineResolveBuiltins(t *testing.T) {
global := NewSymbolTable()
firstLocal := NewEnclosedSymbolTable(global)
secondLocal := NewEnclosedSymbolTable(firstLocal)
expected := []Symbol{
Symbol{Name: "a", Scope: BuiltinScope, Index: 0},
Symbol{Name: "c", Scope: BuiltinScope, Index: 1},
Symbol{Name: "e", Scope: BuiltinScope, Index: 2},
Symbol{Name: "f", Scope: BuiltinScope, Index: 3},
}
for i, v := range expected {
global.DefineBuiltin(i, v.Name)
}
for _, table := range []*SymbolTable{global, firstLocal, secondLocal} {
for _, sym := range expected {
res, ok := table.Resolve(sym.Name)
if !ok {
t.Errorf("name %s not resolvable", sym.Name)
continue
}
if res != sym {
t.Errorf("expected %s to resolve to %+v, got=%+v", sym.Name, sym, res)
}
}
}
}
修改 symbol_table.go
// compiler/symbol_table.go
const (
// ...
BuiltinScope SymbolScope = "BUILTIN"
)
func (s *SymbolTable) DefineBuiltin(index int, name string) Symbol {
symbol := Symbol{Name: name, Index: index, Scope: BuiltinScope}
s.store[name] = symbol
return symbol
}
修改编译器
// compiler/compiler.go
func New() *Compiler {
// ...
symbolTable := NewSymbolTable()
for i, v := range object.Builtins {
symbolTable.DefineBuiltin(i, v.Name)
}
return &Compiler{
// ...
symbolTable: symbolTable,
// ...
}
}
编译器忽略了符号表中的一半内容。使用符号表解析名称后，编译器仅检查符号的作用域是否为 GlobalScope，但是现在不能再使用 if-else 检查了
现在有了第三个作用域，必须清除符号表实际表达的内容
// compiler/compiler.go
func (c *Compiler) loadSymbol(s Symbol) {
switch s.Scope {
case GlobalScope:
c.emit(code.OpGetGlobal, s.Index)
case LocalScope:
c.emit(code.OpGetLocal, s.Index)
case BuiltinScope:
c.emit(code.OpGetBuiltin, s.Index)
}
}
使用 loadSymbol 编译*ast.Identifier
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.Identifier:
symbol, ok := c.symbolTable.Resolve(node.Value)
if !ok {
return fmt.Errorf("undefined variable %s", node.Value)
}
c.loadSymbol(symbol)
}
return nil
}
8.4 执行内置函数
// vm/vm_test.go
func testExpectedObject(
t *testing.T,
expected interface{},
actual object.Object,
) {
t.Helper()
switch expected := expected.(type) {
// ...
case *object.Error:
errObj, ok := actual.(*object.Error)
if !ok {
t.Errorf("object is not Error: %T (%+v)", actual, actual)
return
}
if errObj.Message != expected.Message {
t.Errorf("wrong error message. expected=%q, got=%q", expected.Message, errObj.Message)
}
}
}
func TestBuiltinFunctions(t *testing.T) {
ts := []vmTestCase{
{`len("")`, 0},
{`len("four")`, 4},
{`len("hello world")`, 11},
{
`len(1)`,
&object.Error{
Message: "argument to `len` not supported, got INTEGER",
},
},
{
`len("one","two")`,
&object.Error{
Message: "wrong number of arguments. got=2, want=1",
},
},
{`len([1, 2, 3])`, 3},
{`len([])`, 0},
{`puts("hello", "world!")`, Null},
{`first([1, 2, 3])`, 1},
{`first([])`, Null},
{
`first(1)`,
&object.Error{
Message: "argument to `first` must ARRAY or STRING. got INTEGER",
},
},
{`last([1, 2, 3])`, 3},
{`last([])`, Null},
{
`last(1)`,
&object.Error{
Message: "argument to `last` must ARRAY or STRING. got INTEGER",
},
},
{`rest([1, 2, 3])`, []int{2, 3}},
{`rest([])`, Null},
{`push([], 1)`, []int{1}},
{
`push(1, 1)`,
&object.Error{
Message: "argument to `push` must be ARRAY. got INTEGER",
},
},
}
runVmTests(t, ts)
}
让虚拟机解析 OpGetBuiltin 指令
// vm/vm.go
func (vm *VM) Run() error {
// ...
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
// ...
// 解码
switch op {
// ...
case code.OpGetBuiltin:
builtinIndex := code.ReadUint8(ins[ip+1:])
vm.currentFrame().ip += 1
definition := object.Builtins[builtinIndex]
err := vm.push(definition.Builtin)
if err != nil {
return err
}
}
}
return nil
}
虚拟机提示，只能执行用户定义的函数，所以我们要改变 OpCall 指令的执行方式。先检查调用的是什么方法，然后再调用适当的方法
// vm/vm.go
func (vm *VM) callFuntion(fn *object.CompiledFunction, numArgs int) error {
if numArgs != fn.NumParameters {
return fmt.Errorf("wrong number of arguments: want=%d, got=%d", fn.NumParameters, numArgs)
}
// 进入函数栈帧
frame := NewFrame(fn, vm.sp-numArgs)
vm.pushFrame(frame)
vm.sp = frame.basePointer + fn.NumLocals
return nil
}
// 调用函数
func (vm *VM) executeCall(numArgs int) error {
callee := vm.stack[vm.sp-1-numArgs]
switch callee := callee.(type) {
case *object.CompiledFunction:
return vm.callFuntion(callee, numArgs)
case *object.Builtin:
return vm.callBuiltin(callee, numArgs)
default:
return fmt.Errorf("calling non-function and non-built-in")
}
}
func (vm *VM) Run() error {
// ...
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
// ...
// 解码
switch op {
// ...
case code.OpCall:
numArgs := code.ReadUint8(ins[ip+1:])
vm.currentFrame().ip += 1
err := vm.executeCall(int(numArgs))
if err != nil {
return err
}
}
}
return nil
}
新增加对 builtin 的处理
// vm/vm.go
func (vm *VM) callBuiltin(builtin *object.Builtin, numArgs int) error {
args := vm.stack[vm.sp-numArgs : vm.sp]
result := builtin.Fn(args...)
vm.sp = vm.sp - numArgs - 1
if result != nil {
vm.push(result)
} else {
vm.push(Null)
}
return nil
}
接下来需要处理 REPL，因为 REPL 使用的不是 compiler.New 而是 compiler.NewWithState，里面没有定义内置函数
// repl/repl.go
func Start(in io.Reader, out io.Writer) {
// ...
symbolTable := compiler.NewSymbolTable()
for i, v := range object.Builtins {
symbolTable.DefineBuiltin(i, v.Name)
}
for {
// ...
}
}
9. 闭包
let newAddr = fn(a) {
let adder = fn(b) { a + b; };
return adder;
};
let addTwo = newAddr(2);
addTwo(3);
之前解释器实现闭包的思路：
第一步，将 Env 字段添加到 object.Function，以便存储*object.Environment，即之前用来存储全局绑定和局部绑定的地方。当对*ast.FuntionLiteral 进行求值并将其转换为*object.Function 时，我们在新函数的 Env 字段中放置了一个指向当前环境的指针。
当函数被调用时，需要在已存入 Env 字段的当前环境中对函数体进行求值。带来的实际效果是，函数可以访问该环境中定义的绑定，甚至在以后的任何时间、任何地方也是如此。这是闭包的功能，及其区别于常规函数的地方。
我们构想闭包是：在定义时“跳出”环境的函数，可以被封装并随包携带，就像指向 Env 字段中的*object.Environment 的指针一样
9.1 问题
我们仍然需要将*ast.FunctionLiteral 转换为 object.Object，它们必须可调用且可执行。
改变的是创建闭包的时间和地点
旧的解释器中，将函数字面量转换为 object.Function 和跳出环境（在 object.Function 上设置 Env 字段）同时发生，甚至发生在同一代码块中。
在新的 Monkey 实现中，这不仅发生在不同时间，而且发生在不同的代码包：在编译器中编译函数字面量，在虚拟机中构建环境。结果是在编译函数时无法跳出环境，因为此时还没有构建环境。
所以我们需要改变策略
首先是编译。将 newAdder 和 adder 这两个函数转换成一系列指令并添加到常量池中。之后，发出 OpConstant 指令让虚拟机将函数加载到栈中。此时编译完成，没人知道 a 将具有哪个值。
然而，在虚拟机中，一旦执行 newAdder，a 的值就知道了。addr 被编译后，它的指令将直接加载到栈中。此时 adder 包含在*object.CompiledFunction 中，并从 newAdder 返回————没有任何机会跳过 a
挑战是：在虚拟机中，我们需要在 newAdder 返回 adder 之前将 a 的值放入已编译的 adder 函数中，为了方便后续 adder 访问该值。
这意味着当 adder 引用 a 时，编译器必须事先发出将 a 压栈的指令。当 a 既不是局部绑定也不是全局绑定，并且它的“位置”在执行 newAdder 和调用返回的 adder 函数时会发生变化。它先在作用域内，然后必须在 adder 仍然可以访问到的地方。
也就是说，需要让已编译的函数能够保存只在运行时创建的绑定，并且它们的指令必须已经引用了这些绑定。然后，在运行时，需要引导虚拟机在合适的时机将这些绑定提供给函数。
还有一个问题，嵌套局部绑定。
9.2 计划
有很多方法来实现闭包，但不是所有方法都有公开的文档记录，大部分只有代码实现（通常是经过优化的）
作者发现了最容易访问和转移到 Monkey 的资源和代码库，这里主要基于 GNU Guile，这是一个具有惊人调试工具的实现方案，其后是 lua 的多种实现和 Wren 的代码库，也是《用 Go 语言自制解释器》写作灵感的来源。Matt Might 关于编译闭包主题的文章也非常宝贵
引入一个新术语：自由变量
let newAddr = fn(a) {
let adder = fn(b) { a + b; };
return adder;
};
从 adder 的角度看，a 是一个自由变量。自由变量既不是当前局部作用域中定义的变量，也不是当前函数的参数。用于不受当前作用域的约束，因此它们是自由的。另一种解释是，自由变量是那些在局部使用，但在封闭作用域内定义的变量
基于编译器和虚拟机实现闭包将围绕自由变量展开。编译器需要检测对他们的引用并发出将它们压栈的指令，甚至在它们已经超出作用域时也是如此。在对象系统中，编译后的函数必须能够携带自由变量。而虚拟机不仅需要正确解析对自由变量的引用，还需要将它们存储在已编译的函数中。
如何实现：把每一个函数都变成闭包。这会影响性能，但是比较简单
首先在 object 包中定义一个对象，Closure。它有一个指向*object.CompiledFunction 的指针和一个存储它的引用及所携带自由变量的位置
函数本身的编译不会改变
但是在编译函数体时，需要检测解析的每个符号，以确定它有对自由变量的引用。如果有，我们不会发出 OpGetLocal 或 OpGetGlobal，而是发出新的操作码，从 object.Closure 的“自由变量存储”部分加载值。这就需要扩展 SymbolTable
编译完函数体并将其作用域留在编译器后，将检查它是否引用了任何自由变量。修改后的 SymbolTable 会显示引用了多少自由变量以及它们最初定义在哪个作用域内。最后一个属性特别重要，因为下一步是在运行时将这些自由变量传递给编译函数。为此，必须先发出指令，将引用的自由变量放到栈中。这就需要知道绑定是在哪个作用域内创建的，否则无法判定要发出哪些指令。
随后，发出另一个新操作码，让虚拟机从常量池中获取指定的函数，将刚刚推送的自由变量从栈中取出，并传给已编译的函数。这一步是将*object.CompiledFunction 转为*object.Closure 并将其压入栈中。在栈中时，它可以像之前的*object.CompiledFunction 一样被调用，而且它现在可以访问其指令引用的自由变量，他已经变成了一个闭包。
主要步骤：在编译函数时检测对自由变量的引用，将引用的值放到栈中，将值和编译后的函数合并到一个闭包中，并将其留在栈中，以便随后在那里调用它。
9.3 将一切视为闭包
新对象，Closure。
// object/object.go
const (
// ...
CLOSURE_OBJ = "CLOSURE_OBJ"
)
type Closure struct {
Fn *CompiledFunction
Free []Object
}
func (c *Closure) Type() ObjectType { return CLOSURE_OBJ }
func (c *Closure) Inspect() string { return fmt.Sprintf("Closure[%p]", c) }
它有一个指向它所封装函数的指针 Fn，以及一个用来保存它所携带自由变量的内存 Free，从语义上讲，后者相对于 Env 字段。
闭包是运行时创建的，所以不能在编译器使用，而是要让编译器发出 OpClosure 操作码，让虚拟机将指定的*object.CompiledFunction 封装在*object.Closure 中。
// code/code.go
const (
// ...
OpClosure // 闭包
)
// 操作码定义详细信息
var definitions = map[Opcode]*Definition{
// ...
OpClosure: {"OpClosure", []int{2, 1}},
}
OpClosure 有两个操作数。
第一个操作数是常量索引，用于指定在常量池中的哪个位置找到要转换为闭包的 CompiledFunction，为了防止索引太大而无法加载函数，所以设定为两字节宽（和 OpConstant 的操作数一样大）
第二个操作数用于指定栈中有多少自由变量需要转移到即将创建的闭包中。
// code/code_test.go
func TestMake(t *testing.T) {
ts := []struct {
op Opcode
operands []int
expected []byte
}{
// ...
{OpClosure, []int{65534, 255}, []byte{byte(OpClosure), 255, 254, 255}},
}
// ...
}
func TestInstructionsString(t *testing.T) {
instructions := []Instructions{
Make(OpAdd),
Make(OpGetLocal, 1),
Make(OpConstant, 2),
Make(OpConstant, 65535),
Make(OpClosure, 65535, 255),
}
expected := `0000 OpAdd
0001 OpGetLocal 1
0003 OpConstant 2
0006 OpConstant 65535
0009 OpClosure 65535 255
`
// ...
}
修复 Instructions 上的 fmtInstruction 方法
// code/code.go
func (ins Instructions) fmtInstruction(def *Definition, operands []int) string {
// ...
switch operandCount {
// ...
case 2:
return fmt.Sprintf("%s %d %d", def.Name, operands[0], operands[1])
}
return fmt.Sprintf("ERROR: unhandled operandCount for %s\n", def.Name)
}
从编译器来看，我们将发出 OpClosure 指令而不是 OpConstant 指令来获取栈中的函数。其他保持不变。如果直接把 OpConstant 指令替换为 OpClosure 指令，会导致出现测试大量意外失败的情况。我们需要在所有函数加载到栈的位置上，将 OpConstant 更改为 OpClosure
// compiler/compiler_test.go
func TestFunctions(t *testing.T) {
ts := []compilerTestCase{
{
input: `fn() { return 5 + 10 }`,
expectedConstants: []interface{}{
// ...
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 2, 0),
code.Make(code.OpPop),
},
},
{
input: `fn() { 5 + 10 }`,
expectedConstants: []interface{}{
// ...
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 2, 0),
code.Make(code.OpPop),
},
},
{
input: `fn() { 1; 2 }`,
expectedConstants: []interface{}{
// ...
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 2, 0),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
这里就是在每个测试用例的 expectedInstructions 中，将之前的 OpConstant 更改为 OpClosure，并添加第二个操作数 0
// compiler/compiler_test.go
func TestFunctionsWithoutReturnValue(t *testing.T) {
ts := []compilerTestCase{
{
input: `fn() { }`,
expectedConstants: []interface{}{
// ...
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 0, 0),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
func TestFunctionCalls(t *testing.T) {
ts := []compilerTestCase{
{
input: `fn() { 24 }();`,
expectedConstants: []interface{}{
// ...
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 1, 0), // 被编译的函数
code.Make(code.OpCall, 0),
code.Make(code.OpPop),
},
},
{
input: `
let noArg = fn() { 24 };
noArg();`,
expectedConstants: []interface{}{
// ...
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 1, 0), // 被编译的函数
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpCall, 0),
code.Make(code.OpPop),
},
},
{
input: `
let oneArg = fn(a) { };
oneArg(24)
`,
expectedConstants: []interface{}{
// ...
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 0, 0),
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpCall, 1),
code.Make(code.OpPop),
},
},
{
input: `
let manyArg = fn(a, b, c) { };
manyArg(24, 25, 26);
`,
expectedConstants: []interface{}{
// ...
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 0, 0),
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpConstant, 2),
code.Make(code.OpConstant, 3),
code.Make(code.OpCall, 3),
code.Make(code.OpPop),
},
},
{
input: `
let oneArg = fn(a) { a };
oneArg(24);
`,
expectedConstants: []interface{}{
// ...
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 0, 0),
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpCall, 1),
code.Make(code.OpPop),
},
},
{
input: `
let manyArg = fn(a, b, c) { a; b; c };
manyArg(24, 25, 26);
`,
expectedConstants: []interface{}{
// ...
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 0, 0),
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpConstant, 2),
code.Make(code.OpConstant, 3),
code.Make(code.OpCall, 3),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
func TestLetStatementScopes(t *testing.T) {
ts := []compilerTestCase{
{
input: `
let num = 55;
fn() { num }
`,
expectedConstants: []interface{}{
// ...
},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpClosure, 1, 0),
code.Make(code.OpPop),
},
},
{
input: `
fn(){
let num = 55;
num
}
`,
expectedConstants: []interface{}{
// ...
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 1, 0),
code.Make(code.OpPop),
},
},
{
input: `
fn() {
let a = 55;
let b = 77;
a+b
}
`,
expectedConstants: []interface{}{
55,
77,
[]code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpSetLocal, 0),
code.Make(code.OpConstant, 1),
code.Make(code.OpSetLocal, 1),
code.Make(code.OpGetLocal, 0),
code.Make(code.OpGetLocal, 1),
code.Make(code.OpAdd),
code.Make(code.OpReturnValue),
},
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 2, 0),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
func TestBuiltins(t *testing.T) {
ts := []compilerTestCase{
// ...
{
input: `fn() { len([]) }`,
expectedConstants: []interface{}{
// ...
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 0, 0),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
修改编译器
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.FunctionLiteral:
// ...
fnIndex := c.addConstant(compiledFn)
c.emit(code.OpClosure, fnIndex, 0)
}
return nil
}
接下来更改虚拟机，第一步，将正在执行的 mainFn 封装在一个闭包中并更新虚拟机的初始化代码
// vm/vm.go
func New(bytecode *compiler.Bytecode) *VM {
mainFn := &object.CompiledFunction{Instructions: bytecode.Instructions}
mainClosure := &object.Closure{Fn: mainFn}
mainFrame := NewFrame(mainClosure, 0)
// ...
}
NewFrame 和底层的 Frame 还不能处理闭包。需要让 Frame 保持对*object.Closure 的引用
// vm/frame.go
type Frame struct {
cl *object.Closure
ip int
basePointer int
}
func NewFrame(cl *object.Closure, basePointer int) *Frame {
return &Frame{cl: cl, ip: -1, basePointer: basePointer}
}
func (f *Frame) Instructions() code.Instructions {
return f.cl.Fn.Instructions
}
如果这些帧必须有闭包才能工作，那么需要在其初始化和加入栈帧的时候给予其闭包。在这之前，这些帧已经在虚拟机的 callFunction 方法中初始化。现在将方法重命名为 callClosure 并用闭包来初始化帧
// vm/vm.go
func (vm *VM) executeCall(numArgs int) error {
callee := vm.stack[vm.sp-1-numArgs]
switch callee := callee.(type) {
case *object.Closure:
return vm.callClosure(callee, numArgs)
case *object.Builtin:
return vm.callBuiltin(callee, numArgs)
default:
return fmt.Errorf("calling non-function and non-built-in")
}
}
func (vm *VM) callClosure(cl *object.Closure, numArgs int) error {
if numArgs != cl.Fn.NumParameters {
return fmt.Errorf("wrong number of arguments: want=%d, got=%d", cl.Fn.NumParameters, numArgs)
}
// 进入函数栈帧
frame := NewFrame(cl, vm.sp-numArgs)
vm.pushFrame(frame)
vm.sp = frame.basePointer + cl.Fn.NumLocals
return nil
}
处理 OpClosure，它让虚拟机从常量池中获取函数，将它们封装在一个闭包中，并将其压栈。
// vm/vm.go
unc (vm *VM) Run() error {
// ...
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
// ...
switch op {
// ...
case code.OpClosure:
constIndex := code.ReadUint16(ins[ip+1:])
_ = code.ReadUint8(ins[ip+3:])
vm.currentFrame().ip += 3
err := vm.pushClosure(int(constIndex))
if err != nil {
return err
}
}
}
return nil
}
func (vm *VM) pushClosure(constIndex int) error {
constant := vm.constants[constIndex]
function, ok := constant.(*object.CompiledFunction)
if !ok {
return fmt.Errorf("not a function: %+v", constant)
}
closure := &object.Closure{Fn: function}
return vm.push(closure)
}
第二个操作数被读取但是没有使用，后续会进行处理
9.4 编译和解析自由变量
定义一个操作码来检索 Free 字段中的值，并将它压栈
// code/code.go
const (
// ...
OpGetFree // 获取自由变量
)
var definitions = map[Opcode]*Definition{
// ...
OpGetFree: {"OpGetFree", []int{1}},
}
测试
// compiler/compiler_test.go
func TestClosure(t *testing.T) {
ts := []compilerTestCase{
{
input: `
fn(a) {
fn(b) {
a+b
}
}
`,
expectedConstants: []interface{}{
[]code.Instructions{
code.Make(code.OpGetFree, 0),
code.Make(code.OpGetLocal, 0),
code.Make(code.OpAdd),
code.Make(code.OpReturnValue),
},
[]code.Instructions{
code.Make(code.OpGetLocal, 0),
code.Make(code.OpClosure, 0, 1),
code.Make(code.OpReturnValue),
},
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 1, 0),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
测试用例中最内层的函数，即带有参数 b 的函数，是一个真正的闭包：不仅引用了局部变量 b，还引用了在封装作用域中定义的 a，a 是一个自由变量，我们希望编译器发出 OpGetFree 将其压栈。b 通过普通的 OpGetLocal 推送到栈中。
外部函数中，应该使用 OpGetLocal 将 a 压栈，不过函数本身没有引用它，但由于它被内部函数引用，因此必须在虚拟机的下一条指令 OpClosure 前将 a 压栈。
OpClosure 的第二个操作数现在已经投入使用，其值为 1，因为已经有一个自由变量 a 位于栈中。此时 a 在等待被保持到 object.Closure 的 Free 字段中。
编写深层嵌套的闭包测试
// compiler/compiler_test.go
func TestClosure(t *testing.T) {
ts := []compilerTestCase{
// ...
{
input: `
fn(a) {
fn(b) {
fn(c) {
a + b + c
}
}
}
`,
expectedConstants: []interface{}{
[]code.Instructions{
code.Make(code.OpGetFree, 0),
code.Make(code.OpGetFree, 1),
code.Make(code.OpAdd),
code.Make(code.OpGetLocal, 0),
code.Make(code.OpAdd),
code.Make(code.OpReturnValue),
},
[]code.Instructions{
code.Make(code.OpGetFree, 0),
code.Make(code.OpGetLocal, 0),
code.Make(code.OpClosure, 0, 2),
code.Make(code.OpReturnValue),
},
[]code.Instructions{
code.Make(code.OpGetLocal, 0),
code.Make(code.OpClosure, 1, 1),
code.Make(code.OpReturnValue),
},
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 2, 0),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
这里有 3 个嵌套函数，最里面的函数是带参数 c 的函数，它引用了两个自由变量：a 和 b。b 在封闭作用域中定义，而 a 在最外层函数中定义。
中间函数应该包含一条 OpClosure 指令，它将最里面的函数变成一个闭包。由于第二个操作数是 2，因此当虚拟机执行它时，栈中应该有两个自由变量，它们是如何压栈的？b 的 OpGetLocal 指令和外部 a 的 OpGetFree 指令。
为什么选择 OpGetFree？因为从中间函数的角度看，a 也是一个自由变量：它既不在作用域中定义，也不作为参数定义。。由于需要将 a 压栈，因此可以将其转移到最内层函数的 Free 字段，以期得到 OpGetFree 指令。
这就是函数从外部作用域访问局部绑定的方式，也是通过实现闭包来实现嵌套局部绑定的方式。我们将每个非局部、非全局、非内置的绑定都视为自由变量。
// compiler/compiler_test.go
func TestClosure(t *testing.T) {
ts := []compilerTestCase{
// ...
{
input: `
let global = 55;
fn(){
let a = 66;
fn() {
let b = 77;
fn() {
let c = 88;
global + a + b + c;
}
}
}
`,
expectedConstants: []interface{}{
55, 66, 77, 88,
[]code.Instructions{
code.Make(code.OpConstant, 3),
code.Make(code.OpSetLocal, 0),
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpGetFree, 0),
code.Make(code.OpAdd),
code.Make(code.OpGetFree, 1),
code.Make(code.OpAdd),
code.Make(code.OpGetLocal, 0),
code.Make(code.OpAdd),
code.Make(code.OpReturnValue),
},
[]code.Instructions{
code.Make(code.OpConstant, 2),
code.Make(code.OpSetLocal, 0),
code.Make(code.OpGetFree, 0),
code.Make(code.OpGetLocal, 0),
code.Make(code.OpClosure, 4, 2),
code.Make(code.OpReturnValue),
},
[]code.Instructions{
code.Make(code.OpConstant, 1),
code.Make(code.OpSetLocal, 0),
code.Make(code.OpGetLocal, 0),
code.Make(code.OpClosure, 5, 1),
code.Make(code.OpReturnValue),
},
},
expectedInstructions: []code.Instructions{
code.Make(code.OpConstant, 0),
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpClosure, 6, 0),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
我们得到的是 OpGetLocal，因为现在编译器将每个非全局绑定都视为局部绑定。
检测和解析自由变量。可以借助符号表
从最简单的修改开始，引入一个新作用域
// compiler/symbol_table.go
const (
// ...
FreeScope SymbolScope = "FREE"
)
为符号表编写测试
// compiler/symbol_table_test.go
func TestResolveFree(t *testing.T) {
global := NewSymbolTable()
global.Define("a")
global.Define("b")
firstLocal := NewEnclosedSymbolTable(global)
firstLocal.Define("c")
firstLocal.Define("d")
secondLocal := NewEnclosedSymbolTable(firstLocal)
secondLocal.Define("e")
secondLocal.Define("f")
ts := []struct {
table *SymbolTable
expectedSymbols []Symbol
expectedFreeSymbols []Symbol
}{
{
firstLocal,
[]Symbol{
Symbol{Name: "a", Scope: GlobalScope, Index: 0},
Symbol{Name: "b", Scope: GlobalScope, Index: 1},
Symbol{Name: "c", Scope: LocalScope, Index: 0},
Symbol{Name: "d", Scope: LocalScope, Index: 1},
},
[]Symbol{},
},
{
secondLocal,
[]Symbol{
Symbol{Name: "a", Scope: GlobalScope, Index: 0},
Symbol{Name: "b", Scope: GlobalScope, Index: 1},
Symbol{Name: "c", Scope: FreeScope, Index: 0},
Symbol{Name: "d", Scope: FreeScope, Index: 1},
Symbol{Name: "e", Scope: LocalScope, Index: 0},
Symbol{Name: "f", Scope: LocalScope, Index: 1},
},
[]Symbol{
Symbol{Name: "c", Scope: LocalScope, Index: 0},
Symbol{Name: "d", Scope: LocalScope, Index: 1},
},
},
}
for _, tt := range ts {
for _, sym := range tt.expectedSymbols {
res, ok := tt.table.Resolve(sym.Name)
if !ok {
t.Errorf("name %s not resolvable", sym.Name)
continue
}
if res != sym {
t.Errorf("expected %s to resolve to %+v, got=%+v", sym.Name, sym, res)
}
}
if len(tt.table.FreeSymbols) != len(tt.expectedFreeSymbols) {
t.Errorf("wrong number of free symbols. got=%d want=%d", len(tt.table.FreeSymbols), len(tt.expectedFreeSymbols))
continue
}
for i, sym := range tt.expectedFreeSymbols {
res := tt.table.FreeSymbols[i]
if res != sym {
t.Errorf("wrong free symbol. got=%+v, want=%+v", res, sym)
}
}
}
}
期望能够识别自由变量并将它们的作用域设置为 FreeScope，并且哪些符号被解析为自由变量也需要跟踪。
FreeSymbols 应包含封闭作用域的原始符号。例如，在 secondLocal 在让符号表解析 c 和 d 时，我们期望用 FreeScope 取回符号。但同时，定义名称时创建的原始符号应添加到 FreeSymbols 中。
这样做是因为，自由变量是一个相对术语。当前作用域中的自由变量可以用作封闭作用域中的局部绑定。因为希望在函数编译后将自由变量压栈，也就是发出 OpClosure 指令并离开函数的作用域是，所以需要知道在封闭作用域中如何访问这些符号。
解析来还有一些测试，保证在符号无法解析时，符号表不会自动将其标记为自由变量
// compiler/symbol_table_test.go
func TestResolveUnresolvableFree(t *testing.T) {
global := NewSymbolTable()
global.Define("a")
firstLocal := NewEnclosedSymbolTable(global)
firstLocal.Define("c")
secondLocal := NewEnclosedSymbolTable(firstLocal)
secondLocal.Define("e")
secondLocal.Define("f")
expected := []Symbol{
Symbol{Name: "a", Scope: GlobalScope, Index: 0},
Symbol{Name: "c", Scope: FreeScope, Index: 0},
Symbol{Name: "e", Scope: LocalScope, Index: 0},
Symbol{Name: "f", Scope: LocalScope, Index: 1},
}
for _, sym := range expected {
res, ok := secondLocal.Resolve(sym.Name)
if !ok {
t.Errorf("name %s not resolvable", sym.Name)
continue
}
if res != sym {
t.Errorf("expected %s to resolve to %+v got=%+v", sym.Name, sym, res)
}
}
expectedUnresolvable := []string{
"b", "d",
}
for _, name := range expectedUnresolvable {
_, ok := secondLocal.Resolve(name)
if ok {
t.Errorf("name %s resolved, but was expected not to", name)
}
}
}
FreeSymbols 字段
// compiler/symbol_table.go
type SymbolTable struct {
// ...
FreeSymbols []Symbol
}
func NewSymbolTable() *SymbolTable {
s := make(map[string]Symbol)
free := []Symbol{}
return &SymbolTable{store: s, FreeSymbols: free}
}
期望 free 获得的却是 local
定义一个将 Symbol 添加到 FreeSymbols 并返回 FreeScope 版本的符号的辅助方法。
// compiler/symbol_table.go
func (s *SymbolTable) defineFree(original Symbol) Symbol {
s.FreeSymbols = append(s.FreeSymbols, original)
symbol := Symbol{Name: original.Name, Index: len(s.FreeSymbols) - 1}
symbol.Scope = FreeScope
s.store[original.Name] = symbol
return symbol
}
Resolve 要做的事就是检查，比如：名称是否在该作用域内定义？是否在该符号表中定义？如果不是，那它是一个全局绑定还是一个内置函数？都不是？意味着它被定义在封闭作用域内的局部变量。在这种情况下，从作用域的角度来看，它应该被解析为一个自由变量。
最后，要用 defineFree 方法返回一个符号，将 Scope 设置为 FreeScope
// compiler/symbol_table.go
func (s *SymbolTable) Resolve(name string) (Symbol, bool) {
obj, ok := s.store[name]
if !ok && s.Outer != nil {
obj, ok = s.Outer.Resolve(name)
if !ok {
return obj, ok
}
if obj.Scope == GlobalScope || obj.Scope == BuiltinScope {
return obj, ok
}
free := s.defineFree(obj)
return free, true
}
return obj, ok
}
现在，我们已经完成闭包的第一部分：一个能识别并处理自由变量的符号表。
现在只需要修改 loadSymbol 方法就能通过这个测试
// compiler/compiler.go
func (c *Compiler) loadSymbol(s Symbol) {
switch s.Scope {
case GlobalScope:
c.emit(code.OpGetGlobal, s.Index)
case LocalScope:
c.emit(code.OpGetLocal, s.Index)
case BuiltinScope:
c.emit(code.OpGetBuiltin, s.Index)
case FreeScope:
c.emit(code.OpGetFree, s.Index)
}
}
此时编译依然不会把自由变量压栈，而且 OpClosure 指令的第二个操作数依然是硬编码的 0
在编译函数体之后，要做的就是遍历刚刚在 SymbolTable 中“留下”的 FreeSymbols，并对它们调用 loadSymbol，这会在封闭作用域中生成将自由变量压栈的指令
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.FunctionLiteral:
// ...
if !c.lastInstructionIs(code.OpReturnValue) {
c.emit(code.OpReturn)
}
freeSymbols := c.symbolTable.FreeSymbols
numLocals := c.symbolTable.numDefinitions
instructions := c.leaveScope()
for _, s := range freeSymbols {
c.loadSymbol(s)
}
compiledFn := &object.CompiledFunction{
Instructions: instructions,
NumLocals: numLocals,
NumParameters: len(node.Parameters),
}
fnIndex := c.addConstant(compiledFn)
c.emit(code.OpClosure, fnIndex, len(freeSymbols))
}
return nil
}
9.5 运行时创建闭包
现在虚拟机已经在闭包上运行。它不再执行*object.CompiledFunction，而是执行 OpClosure 指令时将*object.Closure 中，随后调用并执行它们
当前缺少的是能创建“真正” 闭包的部分：将自由变量转移到这些闭包并执行将它们压栈的 OpGetFree 指令。
测试
// vm/vm_test.go
func TestClosures(t *testing.T) {
ts := []vmTestCase{
{
input: `
let newClosure = fn(a) {
fn() { a; };
};
let closure = newClosure(99);
closure();
`,
expected: 99,
},
}
runVmTests(t, ts)
}
我们要做的第一件事是利用 OpClosure 的第二个操作数。它可以决定虚拟机将自由变量转移到指定闭包的数量。
// vm/vm.go
func (vm *VM) Run() error {
// ...
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
// ...
switch op {
// ...
case code.OpClosure:
constIndex := code.ReadUint16(ins[ip+1:])
numFree := code.ReadUint8(ins[ip+3:])
vm.currentFrame().ip += 3
err := vm.pushClosure(int(constIndex), int(numFree))
if err != nil {
return err
}
}
}
return nil
}
func (vm *VM) pushClosure(constIndex int, numFree int) error {
constant := vm.constants[constIndex]
function, ok := constant.(*object.CompiledFunction)
if !ok {
return fmt.Errorf("not a function: %+v", constant)
}
free := make([]object.Object, numFree)
for i := 0; i < numFree; i++ {
free[i] = vm.stack[vm.sp-numFree+i]
}
vm.sp = vm.sp - numFree
closure := &object.Closure{Fn: function, Free: free}
return vm.push(closure)
}
新内容是中间部分。我们利用第二个参数 numFree 构造了一个切片 free。然后，从栈中最低的位置开始，逐个获取自由变量并将其复制到 free。随后手动递减 vm.sp 来清理栈。（复制的顺序很重要）
下一步实现处理 OpGetFree
// vm/vm.go
func (vm *VM) Run() error {
// ...
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
// ...
switch op {
// ...
case code.OpGetFree:
freeIndex := code.ReadUint8(ins[ip+1:])
vm.currentFrame().ip += 1
currentClosure := vm.currentFrame().cl
err := vm.push(currentClosure.Free[freeIndex])
if err != nil {
return err
}
}
}
return nil
}
更多测试
// vm/vm_test.go
func TestClosures(t *testing.T) {
ts := []vmTestCase{
// ...
{
input: `
let newAdder = fn(a, b) {
fn(c) { a + b + c };
};
let adder = newAdder(1, 2);
adder(8);
`,
expected: 11,
},
{
input: `
let newAdderOuter = fn(a, b) {
let c = a + b;
fn(d) {
let e = d + c;
fn(f) { e + f; };
};
};
let newAdderInner = newAdderOuter(1, 2);
let adder = newAdderInner(3);
adder(8);
`,
expected: 14,
},
{
input: `
let a = 1;
let newAdderOuter = fn(b) {
fn(c) {
fn(d) { a + b + c + d; };
};
};
let newAdderInner = newAdderOuter(2)
let adder = newAdderInner(3);
adder(8);
`,
expected: 14,
},
{
input: `
let newClosure = fn(a, b) {
let one = fn() { a; };
let two = fn() { b; };
fn() { one() + two(); };
};
let closure = newClosure(9, 90);
closure();
`,
expected: 99,
},
}
runVmTests(t, ts)
}
9.6 递归闭包
// vm/vm_test.go
func TestRecursiveFunctions(t *testing.T) {
ts := []vmTestCase{
{
input: `
let countDown = fn(x) {
if (x == 0) {
return 0;
} else {
countDown(x - 1);
}
};
countDown(1);
`,
expected: 0,
},
}
runVmTests(t, ts)
}
递归闭包找不到自身
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.LetStatement:
symbol := c.symbolTable.Define(node.Name.Value)
err := c.Compile(node.Value)
if err != nil {
return err
}
// symbol := c.symbolTable.Define(node.Name.Value)
if symbol.Scope == GlobalScope {
c.emit(code.OpSetGlobal, symbol.Index)
} else {
c.emit(code.OpSetLocal, symbol.Index)
}
}
return nil
}
这里将一行语句移动了。现在所做的是在编译函数体之前，在符号表中定义函数即将绑定的名称从而允许函数体引用此函数名。
// vm/vm_test.go
func TestRecursiveFunctions(t *testing.T) {
ts := []vmTestCase{
// ...
{
input: `
let countDown = fn(x) {
if (x == 0) {
return 0;
} else {
countDown(x - 1);
}
};
let wrapper = fn() {
countDown(1);
};
wrapper();
`,
expected: 0,
},
}
runVmTests(t, ts)
}
新用例，在一个函数中定义一个递归函数并在另一个函数中调用
// vm/vm_test.go
func TestRecursiveFunctions(t *testing.T) {
ts := []vmTestCase{
// ...
// 结合以上两个用例
// 在一个函数中定义一个递归函数并在另一个函数中调用它
{
input: `
let wrapper = fn() {
let countDown = fn(x) {
if (x == 0) {
return 0;
} else {
countDown(x - 1);
}
};
countDown(1);
};
wrapper();
`,
expected: 0,
},
}
runVmTests(t, ts)
}
该用例是以下代码的简化形式：
let map = fn(arr, f) {
let iter = fn(arr, accumulated) {
if (len(arr) == 0) {
accumulated
} else {
iter(rest(arr), push(accumulated, f(first(arr))));
}
};
iter(arr, []);
};
报错原因是封装函数？
为了查看编译的 wrapper 的内容，修改 runVmTests
// vm/vm_test.go
func runVmTests(t *testing.T, ts []vmTestCase) {
t.Helper()
for _, tt := range ts {
program := parse(tt.input)
comp := compiler.New()
err := comp.Compile(program)
if err != nil {
t.Fatalf("compiler error: %s", err)
}
for i, constant := range comp.Bytecode().Constants {
fmt.Printf("CONSTANT %d %p (%T):\n", i, constant, constant)
switch constant := constant.(type) {
case *object.CompiledFunction:
fmt.Printf(" Instructions:\n%s", constant.Instructions)
case *object.Integer:
fmt.Printf(" Value: %d\n", constant.Value)
}
fmt.Printf("\n")
}
vm := New(comp.Bytecode())
// ...
}
}
问题出在指令的顺序：wrapper 的第一条指令 OpGetLocal 0，位于 OpSetLocal 0 之前。
解析：在编译 countDown 主体时，编译器遇到了对 countDown 的引用，并需要对符号表进行解析。而符号表注意到，在当前作用域没有定义该符号，所以将其标记为自由变量。
在编译 countDown 主体后，发出 OpClosure 以将 countDown 转换为闭包之前，编译器对标记为自由变量的符号进行迭代并发出必要的加载指令以将它们压栈。
虚拟机中断的原因是索引为 0 的局部变量没有保存。但虚拟机加载它时，却从栈中得到 nil。导致虚拟机错误的原因：调用非闭包和非内置函数。
为什么没保存？因为索引 0 的插槽是闭包本身应该结束的地方。
也就是说，为了将 countDown 引用的单个自由变量（其自身压栈），我们发出了正确的 OpGetLocal 0，但这是在 countDown 变成闭包并使用 OpSetLocal 0 保存之前执行的操作。在 countDown 出现之前，我们尝试创建对 countDown 的引用并将其保存为自身。
我们需要在编译器中检测这些自引用，然后发出一个新的操作码，而不是将符号标记为“自由变量“并发出 OpGetFree
新操作码是 OpCurrentClosure，用来指示虚拟机将其当前正在执行的闭包加载到栈中。
// code/code.go
const (
// ...
OpCurrentClosure // 加载正在执行的闭包
)
var definitions = map[Opcode]*Definition{
// ...
OpCurrentClosure: {"OpCurrentClosure", []int{}},
}
测试
// compiler/compiler_test.go
func TestRecursiveFunctions(t *testing.T) {
ts := []compilerTestCase{
{
input: `
let countDown = fn(x) { countDown(x - 1); };
countDown(1);
`,
expectedConstants: []interface{}{
1,
[]code.Instructions{
code.Make(code.OpCurrentClosure),
code.Make(code.OpGetLocal, 0),
code.Make(code.OpConstant, 0),
code.Make(code.OpSub),
code.Make(code.OpCall, 1),
code.Make(code.OpReturnValue),
},
1,
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 1, 0),
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpConstant, 2),
code.Make(code.OpCall, 1),
code.Make(code.OpPop),
},
},
{
input: `
let wrapper = fn() {
let countDown = fn(x) { countDown(x - 1); };
countDown(1);
};
wrapper();
`,
expectedConstants: []interface{}{
1,
[]code.Instructions{
code.Make(code.OpCurrentClosure),
code.Make(code.OpGetLocal, 0),
code.Make(code.OpConstant, 0),
code.Make(code.OpSub),
code.Make(code.OpCall, 1),
code.Make(code.OpReturnValue),
},
1,
[]code.Instructions{
code.Make(code.OpClosure, 1, 0),
code.Make(code.OpSetLocal, 0),
code.Make(code.OpGetLocal, 0),
code.Make(code.OpConstant, 2),
code.Make(code.OpCall, 1),
code.Make(code.OpReturnValue),
},
},
expectedInstructions: []code.Instructions{
code.Make(code.OpClosure, 3, 0),
code.Make(code.OpSetGlobal, 0),
code.Make(code.OpGetGlobal, 0),
code.Make(code.OpCall, 0),
code.Make(code.OpPop),
},
},
}
runCompilerTests(t, ts)
}
为了检测编译器中的自引用，需要关键信息：当前正在编译的函数名。
我们可以通过语法分析器，判定 let 语句是否将函数字面量绑定到某个名称，如果是，则将绑定的名称保存到函数字面量中。
第一步，在 ast.FunctionLiteral 定义中添加一个 Name 字段
// ast/ast.go
type FunctionLiteral struct {
// ...
Name string
}
func (fl *FunctionLiteral) String() string {
// ...
out.WriteString((fl.TokenLiteral()))
if fl.Name != "" {
out.WriteString(fmt.Sprintf("<%s>", fl.Name))
}
// ...
}
编写语法分析器测试
// parser/parser_test.go
func TestFunctionLiteralWithName(t *testing.T) {
input := `let myFunction = fn() { };`
l := lexer.New(input)
p := New(l)
program := p.ParseProgram()
checkParserErrors(t, p)
if len(program.Statements) != 1 {
t.Fatalf("program.Body does not contain %d statements. got=%d\n", 1, len(program.Statements))
}
stmt, ok := program.Statements[0].(*ast.LetStatement)
if !ok {
t.Fatalf("program.Statements[0] is not ast.LetStatement. got=%T", program.Statements[0])
}
function, ok := stmt.Value.(*ast.FunctionLiteral)
if !ok {
t.Fatalf("stmt.Value is not ast.FunctionLiteral. got=%T", stmt.Value)
}
if function.Name != "myFunction" {
t.Fatalf("function literal name wrong. wnat 'myFunction', got=%q\n", function.Name)
}
}
修改语法分析器
// parser/parser.go
func (p *Parser) parseLetStatement() *ast.LetStatement {
// ...
stmt.Value = p.parseExpression(LOWEST)
if fl, ok := stmt.Value.(*ast.FunctionLiteral); ok {
fl.Name = stmt.Name.Value
}
// ...
}
我们在符号表中检测自引用
在符号表中添加一个新作用域：FunctionScope。我们将为每个符号表定义一个具有该作用域的符号：当前正在编译的函数名。当对一个名称进行语法分析并使用 FunctionScope 返回一个符号时，我们就知道它是当前的函数名，因此它是自引用。
// compiler/symbol_table.go
const (
// ...
FunctionScope SymbolScope = "FUNCTION"
)
添加测试
// compiler/symbol_table_test.go
func TestDefineAndResolveFunctionName(t *testing.T) {
global := NewSymbolTable()
global.DefineFunctionName("a")
expected := Symbol{Name: "a", Scope: FunctionScope, Index: 0}
res, ok := global.Resolve(expected.Name)
if !ok {
t.Fatalf("function name %s not resolvable", expected.Name)
}
if res != expected {
t.Errorf("expected %s to resolve to %+v, got=%+v", expected.Name, expected, res)
}
}
我们希望隐藏函数名后，测试仍然能正常工作。
let foobar = fn() {
let foobar = 1;
foobar;
}
// compiler/symbol_table_test.go
func TestShadowingFunctionName(t *testing.T) {
global := NewSymbolTable()
global.DefineFunctionName("a")
global.Define("a")
expected := Symbol{Name: "a", Scope: FunctionScope, Index: 0}
res, ok := global.Resolve(expected.Name)
if !ok {
t.Fatalf("function name %s not resolvable", expected.Name)
}
if res != expected {
t.Errorf("expected %s to resolve to %+v, got=%+v", expected.Name, expected, res)
}
}
实现 DefineFunctionName
// compiler/compiler.go
func (s *SymbolTable) DefineFunctionName(name string) Symbol {
symbol := Symbol{Name: name, Index: 0, Scope: FunctionScope}
s.store[name] = symbol
return symbol
}
修改编译器
// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
switch node := node.(type) {
// ...
case *ast.FunctionLiteral:
c.enterScope()
if node.Name != "" {
c.symbolTable.DefineFunctionName(node.Name)
}
}
return nil
}
func (c *Compiler) loadSymbol(s Symbol) {
switch s.Scope {
// ...
case FunctionScope:
c.emit(code.OpCurrentClosure)
}
}
在虚拟机中实现 OpCurrentClosure
func (vm *VM) Run() error {
// ...
for vm.currentFrame().ip < len(vm.currentFrame().Instructions())-1 {
// ...
switch op {
// ...
case code.OpCurrentClosure:
currentClosure := vm.currentFrame().cl
err := vm.push(currentClosure)
if err != nil {
return err
}
}
}
return nil
}
10. 最后的测试
// vm/vm_test.go
func TestRecursiveFibonacci(t *testing.T){
ts:=[]vmTestCase{
{
input:`
let fibonacci = fn(x) {
if (x == 0) {
return 0;
} else {
if (x == 1) {
return 1;
} else {
fibonacci(x - 1) + fibonacci(x - 2);
}
}
};
fibonacci(15);
`,
expected: 610,
},
}
runVmTests(t,ts)
}
新建 benchmark 文件夹，然后创建 main.go 文件，比较解释器和编译器的性能差距
package main
import (
"flag"
"fmt"
"time"
"malang/compiler"
"malang/evaluator"
"malang/lexer"
"malang/object"
"malang/parser"
"malang/vm"
)
var engine = flag.String("engine", "vm", "use 'vm' or 'eval'")
var input = `
let fibonacci = fn(x) {
if (x == 0) {
return 0;
} else {
if (x == 1) {
return 1;
} else {
fibonacci(x - 1) + fibonacci(x - 2);
}
}
};
fibonacci(35);
`
func main() {
flag.Parse()
var duration time.Duration
var res object.Object
l := lexer.New(input)
p := parser.New(l)
program := p.ParseProgram()
if *engine == "vm" {
comp := compiler.New()
err := comp.Compile(program)
if err != nil {
fmt.Printf("compiler error: %s", err)
return
}
machine := vm.New(comp.Bytecode())
start := time.Now()
err = machine.Run()
if err != nil {
fmt.Printf("vm error: %s", err)
return
}
duration = time.Since(start)
res = machine.LastPoppedStackElem()
} else {
env := object.NewEnvironment()
start := time.Now()
res = evaluator.Eval(program, env)
duration = time.Since(start)
}
fmt.Printf(
"engine=%s, res=%s, duration=%s\n",
*engine,res.Inspect(),duration,
)
}
go build -o fibonacci ./benchmark
