从0到1构建计算机(7/10)--实现一个虚拟机
计算机工作的本质就是对内存中的数据进行操作，因此只需要具备两种能力即可：(1)对内存的读和写；(2)用对数据进行算数逻辑运算。此外，支持指令跳转能大大提高计算机的可编程能力。直观上看，Hack具备了以上三项能力，我们上一篇也举例了如何实现1+2+…+100。但Hack和我们常用的CPU具备几百条指令集的能力还相去甚远，例如支持四则运算，对栈的操作，指针寄存器的使用，支持函数调用，处理入参和回参等。如何解决这些问题呢？我们需要在简单的Hack之上，再构建一个更加复杂，能力更强的虚拟计算机，这个虚拟机向上提供了一套新的操作指令，即虚拟机的字节码（在Hack中这套字节码更接近我们常用的CPU指令集），其中每条虚拟机指令都是通过封装汇编层一系列的汇编指令来实现的，在本篇中我们会再一次看到在计算机科学中“封装”的强大力量。
虚拟机可能有多种解释，我们要实现的虚拟机是一种程序虚拟机（类似于Java虚拟机），主要是用来支持运行平台无关的计算机程序。其他概念的虚拟机还有系统虚拟机，完全虚拟一个操作系统出来，例如VMWare，iOS模拟器等。
一个C程序
我们来写一个简单的C程序：add。然后思考一下，如何把这段程序翻译成Hack上的汇编语言呢？如果仅仅是翻译这一个程序，貌似是可行的，但如果想要直接翻译一个复杂的C程序则是相当困难的，所以我们需要对Hack再进行一些扩展。
int add(int a, int b) {
int result;
result = a + b;
return result;
}
int main(int argc, char *argv[]) {
int a,b,result;
a = 1;
b = 2;
result = add(a,b);
return 0;
}
我们把上面的C程序在Mac上编译成可执行文件，然后看一下这个它在x86_64架构下的汇编代码。我们看到它的汇编代码并不复杂，它被编译成了两个函数，然后通过一些的push, pop, mov, add, call, return等指令完成。这些指令就是Hack的虚拟机需要参考和实现的。从这一点上来看，Hack的虚拟机更接近我们常用的CPU。
Stack
无论是x86_64架构下的汇编指令，还是我们需要实现的Hack虚拟机，都需要支持四种基本操作：算数逻辑操作，内存访问操作，程序流程控制，函数调用。想要方便的实现这些操作，我们需要借助一种常用的数据结构：堆栈（stack）。经证明，通过堆栈操作，能够实现任何数学或逻辑表达式；任何程序，无论用什么语言编写，都能够被翻译成等价的堆栈机语言。
Push & Pop
既然是栈的使用，那肯定少不了Push和Pop操作。SP（Stack Pointer）指针是这两项操作的关键，SP指针实时地指向栈顶：Push操作把一个数（可以是内存中的某个数）压入栈顶，然后SP加1（如果栈从上向下生长就减1）；Pop操作把栈顶的数弹出（可以弹出到某个内存地址），然后SP减1。
内存划分
内存划分是Hack虚拟机中另一个重要主题。Hack的内存由32K的16位字组成，其中前16K是通用内存，后16K是I/O设备的内存映像。
0-15：16个虚拟寄存器(Hack寄存器不够用了)
16-255：静态变量区
256-2047：栈
2048-16383：堆
16384-24575：I/O内存映像
0-15位内存和寄存器的映射关系如下：
"SP"=>"000000000000000", "LCL"=>"000000000000001", "ARG"=>"000000000000010", "THIS"=>"000000000000011", "THAT"=>"000000000000100",
"R0"=>"000000000000000", "R1"=>"000000000000001", "R2"=>"000000000000010", "R3"=>"000000000000011",
"R4"=>"000000000000100", "R5"=>"000000000000101", "R6"=>"000000000000110", "R7"=>"000000000000111",
"R8"=>"000000000001000", "R9"=>"000000000001001", "R10"=>"000000000001010", "R11"=>"000000000001011",
"R12"=>"000000000001100", "R13"=>"000000000001101", "R14"=>"000000000001110", "R15"=>"000000000001111",
"SCREEN"=>"100000000000000", "KBD"=>"110000000000000"
虚拟机操纵8个独立的虚拟内存段。在这里虚拟内存是一个很重要的技巧，内存段都有各自的用途，在程序执行过程中，每个函数都可以通过固定的几个指针（R0-R15）来访问这些内存段，看上去每个内存段都是它们独享的（有些是共享的），而不必关心他们的物理地址在哪里，是否会和其他函数冲突等。这本质上也是一种封装，这种封装向上提供一种标准的内存访问方式，向下了实现虚拟内存和物理内存的映射和管理（类似于操作系统中进程地址空间的映射）。这大大降低了虚拟机使用者的难度，把复杂的工作交给了虚拟机本身。
我们来看一下代码和内存段的关系。一个类被编译成一个.VM文件，其中包含了若干个函数实现f1, f2, f3。temp和const段是进程级别共享的；static段是类级别共享的；argument、local、this、that、pointer是函数级别的独享的，每个函数都有自己的这5个内存段，但每个函数访问它们的方式却是一致的（即通过R1-R5指针）
内存访问命令
所有的内存段访问都通过2条命令实现：
- push segement index 将segement[index]的值压入堆栈
- pop segement index 将栈顶元素弹出，然后存入segement[index]
push locol 0 #把locol段第一个位置的值压入堆栈
push constant 123 #把常数123压入堆栈
pop static 1 #把栈顶元素弹出，存入static的第二个位置
实现
push和pop指令的作用就是在栈顶内存和段内存之间互相搬运数值。SP指针用于标识栈顶内存，segement基地址+偏移量用于标识段内存，然后通过一系列寄存器和内存操作（利用A寄存器定位内存地址，D寄存器暂存数值等操作）实现这两个命令。
def writePushPop(command, segment, index) #实现push, pop命令
asm_cmd = ''
segment = @table["#{segment}"]
if command == 'C_PUSH' && segment =='constant' #push const
asm_cmd << pushConstant(index)
elsif command == 'C_PUSH'
asm_cmd << passArgsAddressToA(segment, index) #A=段地址+偏移地址
asm_cmd << "D=M" << "\n" #段内存的值存到D
asm_cmd << pushDtoStack() #push D到栈顶，sp+1
elsif command == 'C_POP'
asm_cmd << passArgsAddressToA(segment, index) #A=段地址+偏移地址
asm_cmd << getStackTopToD() #栈顶的值存到D
asm_cmd << "M=D"<< "\n" #pop D到段内存
asm_cmd << "@SP"<< "\n"
asm_cmd << "M=M-1"<< "\n" #sp减1
end
if asm_cmd.length > 0
@sam_file.write(asm_cmd)
end
end
def pushConstant(const) #实现简单的push const
asm_cmd = "@#{const}\n"
asm_cmd << "D=A"<< "\n"
asm_cmd << pushDtoStack()
return asm_cmd
end
def pushDtoStack #把D寄存器的值push到栈顶，sp+1
asm_cmd = "@SP"<< "\n"
asm_cmd << "A=M"<< "\n"
asm_cmd << "M=D"<< "\n"
asm_cmd << "@SP"<< "\n"
asm_cmd << "M=M+1"<< "\n"
return asm_cmd
end
def getStackTopToD #把栈顶的值存到D寄存器，sp不变
asm_cmd = "D=A"<< "\n"
asm_cmd << "@R13"<< "\n"
asm_cmd << "M=D"<< "\n" #先把A的值暂存到R13，后面在还原A寄存器（保存现场）
asm_cmd << "@SP"<< "\n"
asm_cmd << "A=M-1"<< "\n"
asm_cmd << "D=M"<< "\n" #取出值放入D
asm_cmd << "@R13"<< "\n"
asm_cmd << "A=M"<< "\n" #恢复A
return asm_cmd
end
def passArgsAddressToA(segment, index) #把内存地址存到A
asm_cmd = ''
if segment == "static"
asm_cmd << "@#{@source_file_name}.#{index}"<< "\n" #文件名+index作为static的符号
return asm_cmd
end
asm_cmd << "@#{index}"<< "\n"
asm_cmd << "D=A"<< "\n" #D=index偏移量
if segment == "temp"
asm_cmd << "@R5"<< "\n"
asm_cmd << "A=A+D"<< "\n" #A=temp地址+偏移量
puts "执行了#{segment}"
elsif segment == "pointer"
asm_cmd << "@THIS"<< "\n"
asm_cmd << "A=A+D"<< "\n" #A=THIS+偏移量
else
asm_cmd << "@#{segment}"<< "\n"
asm_cmd << "A=M+D"<< "\n" #A=段内存指针指向的段基地址+偏移量
end
return asm_cmd
end
算数逻辑运算命令
我们还需要实现若干一元或二元的算数&逻辑运算命令，包括二元加减法，两个数的比较，与或非，取反操作。在这里我们没有实现浮点数操作，也没有实现乘除法（后面我们会在软件的层面实现乘除法）。
我们以下面的伪命令为例，看下如何利用栈来进行算数逻辑运算。运算x+y时，是一种以后缀表达式形式的运算：先把x入栈，sp+1；然后把y入栈，sp+1，然后计算加法，把结果值存入当前x的位置，sp-2。一元运算则更简单，运算-x时：先把x入栈，sp=1，然后取反，把结果值存入当前x的位置，sp-1。
// d=(2-x)*(y+5)
push 2
push x
sub
push y
push 5
add
mult
pop d
实现
在实现上主要思路是利用D寄存器配合SP指针，例如x+y：把y赋值给D，然后SP指向x，然后D=D+M，最后把D再赋值给SP指向的内存。
def arithmetic(cmd)
asm_cmd = ""
if cmd == 'add'
asm_cmd << passYtoD() #D=y
asm_cmd << "A=A-1"<< "\n"
asm_cmd << "D=D+M"<< "\n" #D=x+y
asm_cmd << "M=D"<< "\n"
asm_cmd << resetSP() #sp重置
elsif cmd == 'sub'
asm_cmd << passYtoD()
asm_cmd << "A=A-1"<< "\n"
asm_cmd << "D=M-D"<< "\n" #D=x-y
asm_cmd << "M=D"<< "\n"
asm_cmd << resetSP()
elsif cmd == 'neg'
asm_cmd << passYtoD()
asm_cmd << "M=-D"<< "\n" #M=-D
asm_cmd << resetSP()
elsif cmd == 'eq'
asm_cmd << passYtoD()
asm_cmd << compare("JEQ")
asm_cmd << resetSP()
elsif cmd == 'gt'
asm_cmd << passYtoD()
asm_cmd << compare("JGT")
asm_cmd << resetSP()
elsif cmd == 'lt'
asm_cmd << passYtoD()
asm_cmd << compare("JLT")
asm_cmd << resetSP()
elsif cmd == 'and'
asm_cmd << passYtoD()
asm_cmd << "A=A-1"<< "\n"
asm_cmd << "D=D&M"<< "\n" #D=x&y
asm_cmd << "M=D"<< "\n"
asm_cmd << resetSP()
elsif cmd == 'or'
asm_cmd << passYtoD()
asm_cmd << "A=A-1"<< "\n"
asm_cmd << "D=D|M"<< "\n" #D=x|y
asm_cmd << "M=D"<< "\n"
asm_cmd << resetSP()
elsif cmd == 'not'
asm_cmd << passYtoD()
asm_cmd << "M=!D"<< "\n"
end
return asm_cmd
end
def passYtoD #y赋值给D寄存器
asm_cmd = "@SP"<< "\n"
asm_cmd << "A=M"<< "\n"
asm_cmd << "A=A-1"<< "\n" #sp-1后指向y
asm_cmd << "D=M"<< "\n" #D=y
return asm_cmd
end
def resetSP
asm_cmd = "D=A"<< "\n"
asm_cmd << "@SP"<< "\n"
asm_cmd << "M=D+1"<< "\n" #SP指针重置
return asm_cmd
end
def compare(cmd) #xy大小比较。
asm_cmd = "A=A-1"<< "\n"
asm_cmd << "D=M-D"<< "\n" #D=x-y
asm_cmd << "@branchLabel_#{@branchIndex}"<< "\n"
asm_cmd << "D;#{cmd}"<< "\n"
asm_cmd << "D=0"<< "\n" #0(0x0000)代表false
asm_cmd << "@mergeLabel_#{@mergeIndex}"<< "\n"
asm_cmd << "0;JMP"<< "\n"
asm_cmd << "(branchLabel_#{@branchIndex})"<< "\n"
asm_cmd << "D=-1"<< "\n" #-1(0xFFFF)代表true
asm_cmd << "(mergeLabel_#{@mergeIndex})"<< "\n"
asm_cmd << "@SP"<< "\n"
asm_cmd << "A=M-1"<< "\n"
asm_cmd << "A=A-1"<< "\n"
asm_cmd << "M=D"<< "\n"
@branchIndex = @branchIndex + 1
@mergeIndex = @mergeIndex + 1
return asm_cmd
end
程序流程控制命令
计算机默认的执行顺序是线性的，程序流程控制这一节我们需要实现跳转功能和分支功能，即以下三个指令：
label：用于标识指令地址
goto label：无条件跳转到指令地址
if_goto label：先弹出并判断栈顶值，非0时跳转，否则线性执行
实现
这三条指令的实现非常简单。原因是这里label扮演了重要的功能，由于下层的汇编器支持把label识别成指令地址，所以这里我们就不必再关心需要跳转的具体地址，省去了很多工作。这里我们看到只要下层设计封装的好，就会大大降低上层的实现难度。
def writeLabel(label)
asm_cmd = "(#{label})"<< "\n"
@sam_file.write(asm_cmd)
end
def writeGoto(label)
asm_cmd = "@#{label}"<< "\n"
asm_cmd << "0;JMP"<< "\n" #无条件跳转
@sam_file.write(asm_cmd)
end
def writeIf(label)
asm_cmd = "@SP"<< "\n"
asm_cmd << "A=M"<< "\n"
asm_cmd << "A=A-1"<< "\n"
asm_cmd << "D=M"<< "\n" #栈顶值存到D
asm_cmd << "@SP"<< "\n"
asm_cmd << "M=M-1"<< "\n" #指针减1
asm_cmd << "@#{label}"<< "\n"
asm_cmd << "D;JNE"<< "\n" #D非0时跳转
@sam_file.write(asm_cmd)
end
函数调用命令
函数调用是Hack虚拟机实现最复杂的一节。程序的执行过程就是一系列函数的调用过程，每个函数执行若干指令，操作函数中的参数变量、本地变量、静态变量三种变量。如果程序只有一个函数，那么这个工作并不复杂，因为参数变量、本地变量、静态变量都是静态的，提前分配好的，直接去使用就行了；但是如果程序是由多个函数组成的，那么这些变量在栈上就是动态的（参数变量、本地变量是动态的，静态变量还是静态的），它们的个数，分配的位置都是在动态变化的，处理起来就非常复杂。Hack虚拟机中函数调用部分的任务就是把这种动态再转变成静态：当函数被调用时，为它构建一个私有空间（frame），把它封闭在一个“与世隔绝的自我世界”（该世界只包括已经初始化的参数变量、本地变量和一个空的栈空间），然后该函数在这个私有空间内直接自己的命令。从该函数的角度来看，它不感知其他函数的存在，就好像程序只有一个函数一样，又变成了静态。
这一节我们需要实现以下3个指令：
function f n：下面是一段函数名为f的代码，该函数有n个参数
call f m：调用函数f，且调用前已将m个参数压入栈
return：返回到调用者
函数的调用也是通过栈实现的，调用一个函数的时候，虚拟机为函数分配一块新的内存（frame），函数结束时，则回收这块内存。函数调用每加深一层，frame增长一块，每return一层，frame缩减一块，因此无限递归的函数会消耗无限的frame，导致栈内存溢出。
一个函数的调用和返回过程大致如下如下：
1.调用函数将参数传递给被调用函数
2.保存调用函数的当前状态
3.跳转至被调用函数
4.为被调用函数分配局部变量空间并初始化
5.执行被调用函数指令序列
6.被调用函数将回参传递给调用函数
7.恢复调用函数的状态
8.回收被调用函数使用的内存空间
9.返回到之前调用函数的下一条指令执行
在函数调用时，栈上的内存使用和寄存器状态如下图。调用者在把函数入参push到栈上后，argument指针指向第一个参数；然后把函数的返回指令地址入栈；然后保存调用者的local、argument、this、that指针；然后根据被调用者局部变量数量为其分配内存空间，并把Local指针指向第一个局部变量；最后把SP指针指向栈顶，栈顶后面的内存空间都是被调用者的工作区。
被调用者执行完毕后，把返回值pop到第一个入参的位置（如果返回类型为void，就再丢弃这个返回值）；恢复调用者的各种寄存器指针；然后通过重置SP指针来回收被调用者的内存（并没有修改被调用者frame内存的数据，只是重置了栈顶的位置，后面它们将会被新的函数覆盖）。
实现
call指令
实现call指令，首先需要push调用者的返回地址，返回地址用“符号名+index”的方式标识，index的目的是防止返回地址重名，每翻译一次call指令后index需要+1；然后保存几个寄存器的状态；然后更新ARG和LCL，其中ARG=SP-n-5（参考上面的内存分布图），LCL = SP；最后执行goto跳转指令。因为调用函数return后还要返回goto指令的下一条指令标继续执行，所以需要在最后补充一个返回地址label。
call f n 伪代码
--------------------
push return-address //返回地址入栈
push LCL //保存寄存器指针
push ARG
push THIS
push THAT
ARG = SP-n-5 //重置ARG，第一个入参的位置是当前SP指针减n再减5
LCL = SP //重置LCL，第一个局部变量的位置是当前SP的位置
goto f //跳转到f
(return-address) //label标识，return后返回这里执行
def writeCall(functionName, numArgs)
writePushPop("C_PUSH", "constant", "callLabel#{@callIndex}")
saveSegment("LCL")
saveSegment("ARG")
saveSegment("THIS")
saveSegment("THAT")
resetARG(5+numArgs.to_i)
resetLCL()
callJump(functionName, "callLabel#{@callIndex}")
@callIndex = @callIndex + 1
end
# 保存寄存器的值
def saveSegment(segment)
asm_cmd = "@#{segment}"<< "\n"
asm_cmd << "D=M"<< "\n"
asm_cmd << pushDtoStack()
@sam_file.write(asm_cmd)
end
# ARG设置为SP指针向前移动step步
def resetARG(steps)
asm_cmd = "@SP"<< "\n"
asm_cmd << "D=M"<< "\n"
asm_cmd << "@#{steps}"<< "\n"
asm_cmd << "D=D-A"<< "\n"
asm_cmd << "@ARG"<< "\n"
asm_cmd << "M=D"<< "\n"
@sam_file.write(asm_cmd)
end
# 重置LCL，第一个局部变量的位置是当前SP的位置
def resetLCL()
asm_cmd = "@SP"<< "\n"
asm_cmd << "D=M"<< "\n"
asm_cmd << "@LCL"<< "\n"
asm_cmd << "M=D"<< "\n"
@sam_file.write(asm_cmd)
end
# 跳转执行
def callJump(functionName, returnLabel)
asm_cmd = "@#{functionName}"<< "\n"
asm_cmd << "0;JMP"<< "\n"
asm_cmd << "(#{returnLabel})"<< "\n"
@sam_file.write(asm_cmd)
end
function指令
function f m 指令比较简单。m 代表函数 f 中有 m 个局部变量，所以只需要连续push m 次0即可：开辟了 m 个内存空间，并将其初始化为0（我们日常使用的高级语言中，不同类型的变量占的字节数可能不同。Hack进行了简化，所有基本类型的变量都占用一个字的内存）。
def writeFunction(funtionName, numArgs)
asm_cmd = "(#{funtionName})"<< "\n" #首先用（funtionName）来标识函数地址
@sam_file.write(asm_cmd)
index = 0
while index < numArgs.to_i
writePushPop("C_PUSH", "constant", "0")
index = index + 1
end
end
return指令
return指令首先需要把返回值pop到argument 0，即调用者的栈顶；然后重置一系列寄存器指针；最后跳转到返回地址。这里比较复杂的地方是如何安排各个数值的恢复顺序，因为顺序不当可能导致一些值被破坏。例如途中LCL被恢复了，导致最后取不到return的地址，我在这里的解决方案是先把return地址寄存到一个通用寄存器，后面再取出来。
return 伪代码
--------------------
pop argument 0 //pop返回值到argument 0
SP = ARG + 1 //重置SP指针
restore THAT //恢复寄存器指针
restore THIS
restore ARG
restore LCL
goto RET //跳转到返回地址
def writeReturn
saveReturnAddress()
writePushPop("C_POP", "argument", "0")
restoreSP()
restoreSegement("THAT")
restoreSegement("THIS")
restoreSegement("ARG")
restoreSegement("LCL")
gotoReturnAddress()
end
# 暂存return地址到R14（最后取return地址时需要用LCL-5来定位，而途中LCL会被修改，所以需要先把return地址暂存起来，R13被getStackTopToD占用了）
def saveReturnAddress()
asm_cmd = "@5"<< "\n"
asm_cmd << "D=A"<< "\n"
asm_cmd << "@LCL"<< "\n"
asm_cmd << "A=M-D"<< "\n"
asm_cmd << "D=M"<< "\n"
asm_cmd << "@R14"<< "\n"
asm_cmd << "M=D"<< "\n"
@sam_file.write(asm_cmd)
end
# 重置SP指针
def restoreSP()
asm_cmd = "@ARG"<< "\n"
asm_cmd << "D=M+1"<< "\n"
asm_cmd << "@SP"<< "\n"
asm_cmd << "M=D"<< "\n"
@sam_file.write(asm_cmd)
end
# 恢复寄存器指针
def restoreSegement(segment)
table = {"THAT"=>"1", "THIS"=>"2", "ARG"=>"3", "LCL"=>"4"}
asm_cmd = "@#{table[segment]}"<< "\n"
asm_cmd << "D=A"<< "\n"
asm_cmd << "@LCL"<< "\n"
asm_cmd << "A=M-D"<< "\n"
asm_cmd << "D=M"<< "\n"
asm_cmd << "@#{segment}"<< "\n"
asm_cmd << "M=D"<< "\n"
@sam_file.write(asm_cmd)
end
# return到上一级函数继续执行
def gotoReturnAddress()
asm_cmd = "@R14"<< "\n"
asm_cmd << "A=M"<< "\n" # 从R14取出缓存的return地址
asm_cmd << "0;JMP"<< "\n"
@sam_file.write(asm_cmd)
end
从中学到什么
通过本篇的实践，我们掌握了CPU在栈上的工作方式，尤其是了解了栈对函数调用的支持。这些指令和我们常用的CPU汇编指令更加接近（包括某些寄存器的作用），对我们进一步学习理解x86或ARM汇编指令，甚至C语言等高级语言会有很大帮助。
我们看到了程序虚拟机的工作方式，它本质上是一个翻译机：向上提供一种新的语言接口，然后把虚拟机语言翻译成所在平台的计算机语言，因此我们也可以在其它平台上实现Hack虚拟机，只不过翻译的实现细节会发生改变。Hack虚拟机和Java虚拟机本质上相同的，Hack虚拟机是一个纯的静态翻译器，而Java虚拟机作为一个进程运行，是动态翻译的，此外Java虚拟机还有类加载器，内存回收等强大功能。
我们也学到了一些重要的编程思想：如果在本层实现逻辑过于复杂，可以考虑把一些复杂的逻辑抽象出来，交给下层来实现，即把复杂的问题分层化。尽量让动态的，变化的，需要被编程的，面向程序员的部分变得标准和简单，把复杂的逻辑封装在静态的，底层的，不面向程序员的地方。目的是让开发者能把主要精力放在解决问题的算法之上，而不用考虑让人头疼的底层的实现细节。这是一个程序员的重要基本功。
NEXT
Hack虚拟机更加接近一个真实的计算机了，它可以支持一系列函数在虚拟机上的运算和互相调用。下一篇我们将设计一门简洁的面向对象语言，并实现它的编译器，然后我们终于可以使用高级语言在Hack上编写程序了。
本篇完整实现放在了:github