第七章虚拟机（上）

导读

在前六章中，我们从逻辑门开始，逐步构建了完整的计算机硬件系统，并学习了机器语言和汇编语言。然而，这些语言都紧密绑定于特定的硬件架构，缺乏可移植性。本章开始，我们将进入软件抽象的新层次——虚拟机。

虚拟机(Virtual Machine, VM)是一种抽象的计算设备，提供了独立于底层硬件的编程环境。通过虚拟机，我们可以编写一次程序，在不同的硬件平台上运行。这种抽象是现代软件开发的基础，Java、.NET、Python等现代技术栈都依赖于虚拟机技术。

本章将介绍Stack VM——一种基于栈的虚拟机架构。你将学习虚拟机的指令集、栈操作、算术运算和内存访问，为后续实现虚拟机翻译器奠定基础。

核心概念详解

7.1 虚拟机概念

虚拟机是真实计算机的软件模拟，提供了抽象的计算环境。

虚拟机的优势

可移植性：VM程序可以在任何实现了VM的平台上运行

安全性：VM提供了沙箱环境，隔离了程序与底层系统

抽象性：提供了更高级的编程抽象

优化空间：VM可以在运行时进行优化

虚拟机的类型

基于栈的VM：

使用栈来存储操作数和中间结果
指令简短，易于实现
例如：Java bytecode、.NET CIL、Stack VM

基于寄存器的VM：

使用虚拟寄存器来存储数据
执行效率更高
例如：Dalvik VM、Lua VM

7.2 Stack VM架构

Stack VM是Nand2Tetris课程中使用的虚拟机，采用基于栈的架构。

核心特性

栈操作：所有运算都通过栈进行

16位数据：所有数据都是16位整数

多段内存：支持多种内存段

函数调用：支持函数定义和调用

栈的工作原理

栈是一种后进先出(LIFO)的数据结构：

push 5    -> 栈: [5]
push 3    -> 栈: [5, 3]
add       -> 栈: [8]     (5+3=8)
push 2    -> 栈: [8, 2]
sub       -> 栈: [6]     (8-2=6)

7.3 VM指令集

Stack VM的指令分为几大类：

栈操作指令

push segment index：将指定段中索引处的值压入栈

push local 0     // 将local[0]压入栈
push argument 2  // 将argument[2]压入栈
push constant 5  // 将常量5压入栈

pop segment index：弹出栈顶值并存入指定段的索引处

pop local 0      // 弹出栈顶值存入local[0]
pop argument 2   // 弹出栈顶值存入argument[2]

算术运算指令

add：弹出两个值，计算和，压入结果

栈: [a, b] -> add -> 栈: [a+b]

sub：弹出两个值，计算差，压入结果

栈: [a, b] -> sub -> 栈: [a-b]  (注意顺序：先弹出的是b)

neg：弹出栈顶值，取负，压入结果

栈: [a] -> neg -> 栈: [-a]

逻辑运算指令

and：弹出两个值，计算逻辑与，压入结果

栈: [a, b] -> and -> 栈: [a AND b]

or：弹出两个值，计算逻辑或，压入结果

栈: [a, b] -> or -> 栈: [a OR b]

not：弹出栈顶值，取反，压入结果

栈: [a] -> not -> 栈: [NOT a]

比较指令

eq：弹出两个值，比较相等，压入布尔结果

栈: [a, b] -> eq -> 栈: [a==b ? -1 : 0]

gt：弹出两个值，比较大于，压入布尔结果

栈: [a, b] -> gt -> 栈: [a>b ? -1 : 0]

lt：弹出两个值，比较小于，压入布尔结果

栈: [a, b] -> lt -> 栈: [a<b ? -1 : 0]

注意：VM中布尔值true表示为-1(全1)，false表示为0。

程序流指令

label labelName：定义标签

label LOOP_START

goto labelName：无条件跳转

goto LOOP_START

if-goto labelName：条件跳转(弹出栈顶值，非零则跳转)

if-goto LOOP_START

函数调用指令

function functionName nLocals：定义函数

function factorial 2    // 定义factorial函数，有2个局部变量

call functionName nArgs：调用函数

call factorial 1        // 调用factorial，传递1个参数

return：从函数返回

return

7.4 内存段

Stack VM支持多种内存段，每个段有不同的用途。

虚拟内存段

constant：常量段

存储常量值
只能push，不能pop
例如：push constant 5

local：局部变量段

存储当前函数的局部变量
每个函数有自己的local段
例如：push local 0, pop local 1

argument：参数段

存储传递给函数的参数
每个函数调用有自己的argument段
例如：push argument 0

this：this段

存储对象的实例变量
在面向对象编程中使用
例如：push this 2

that：that段

存储数组元素
用于数组访问
例如：push that 3

指针段

pointer：指针段

包含两个特殊指针：pointer[0]和pointer[1]
pointer[0]指向this段的基地址
pointer[1]指向that段的基地址
例如：push pointer 0

temp：临时段

包含8个临时变量(temp[0]-temp[7])
用于编译器生成的临时值
例如：push temp 3

7.5 函数调用机制

函数调用是VM的核心功能之一。

函数调用过程

调用函数时需要：

保存调用者的状态(返回地址、栈指针等)

为被调用函数分配新的栈帧

传递参数

跳转到函数入口

栈帧结构

每个函数调用都有一个栈帧，包含：

高地址
+------------------+
| 参数n-1          |
| ...              |
| 参数0            |
+------------------+
| 返回地址         |
| 旧local指针      |
| 旧this指针      |
| 旧that指针      |
+------------------+ <- local基地址
| 局部变量0        |
| 局部变量1        |
| ...              |
+------------------+ <- 栈顶
低地址

函数返回过程

函数返回时需要：

将返回值放在栈顶

恢复调用者的状态

清理栈帧

跳转回返回地址

7.6 VM程序结构

VM程序由一个或多个.vm文件组成。

文件组织

Main.vm        // 主类
Math.vm        // 数学库
String.vm      // 字符串库

函数定义

function Main.factorial 0
  push argument 0
  push constant 1
  eq
  if-goto BASE_CASE
  push argument 0
  push argument 0
  push constant 1
  sub
  call Main.factorial 1
  call Math.multiply 2
  return
label BASE_CASE
  push constant 1
  return

7.7 示例程序

示例1：简单算术

// 计算 (5 + 3) * 2
push constant 5
push constant 3
add
push constant 2
call Math.multiply 2

示例2：数组操作

// 创建数组并赋值
push constant 10
call Array.new 1
pop pointer 1        // that = 新数组
push constant 42
push that 0
pop that 0           // arr[0] = 42
push that 0          // 读取arr[0]

示例3：条件分支

// if (x > 0) y = 1; else y = 2;
push local 0         // 推入x
push constant 0
gt                   // x > 0 ?
if-goto THEN
push constant 2
pop local 1          // y = 2
goto END
label THEN
push constant 1
pop local 1          // y = 1
label END

示例4：循环

// while (x > 0) x--;
label LOOP
push local 0         // 推入x
push constant 0
gt                   // x > 0 ?
not                  // !(x > 0)
if-goto END          // 如果条件为假，退出
push local 0         // x
push constant 1
sub                  // x - 1
pop local 0          // x = x - 1
goto LOOP
label END

7.8 VM实现策略

将VM指令映射到Hack汇编语言需要仔细设计。

栈实现

VM栈可以使用Hack RAM实现：

使用SP(栈指针)寄存器跟踪栈顶位置
SP指向下一个可用位置
push：在SP位置写入值，SP++
pop：SP--，从SP位置读取值

内存段映射

各内存段映射到Hack RAM：

local：由LCL寄存器指向
argument：由ARG寄存器指向
this：由THIS寄存器指向
that：由THAT寄存器指向
pointer：RAM[3]-RAM[4]
temp：RAM[5]-RAM[12]
constant：立即数

算术指令实现

// add指令的汇编实现
@SP
A=M-1        // 指向栈顶
D=M          // D = 栈顶值
@SP
A=M-2        // 指向第二个栈顶
M=D+M        // 第二个栈顶 = 栈顶 + 第二个栈顶
@SP
M=M-1        // SP--

重要知识点

知识点1：栈式VM vs 寄存器式VM

栈式VM：

优点：指令简短，易于编译，可移植性好
缺点：需要更多指令，执行较慢
代表：Java bytecode, .NET CIL

寄存器式VM：

优点：指令更少，执行更快
缺点：指令更长，编译更复杂
代表：Dalvik, Lua VM

知识点2：调用约定

调用约定定义了函数调用时参数传递和状态保存的规则：

参数传递方式(栈、寄存器、混合)
返回值位置
调用者和被调用者的责任

知识点3：尾调用优化

尾调用优化是一种重要的优化技术：

当函数调用的返回值直接作为当前函数的返回值时
可以重用当前栈帧，避免栈溢出
对于递归函数特别重要

知识点4：垃圾回收

VM可能需要实现垃圾回收：

自动管理内存
回收不再使用的对象
常见的算法：引用计数、标记-清除、分代回收

知识点5：即时编译(JIT)

JIT编译是一种运行时优化技术：

在运行时将VM代码编译为本地代码
可以根据运行时信息进行优化
显著提高执行速度

常见误区

误区1：混淆VM和汇编语言

VM是更高层次的抽象。VM指令不是直接对应机器指令，而是需要通过VM翻译器转换为汇编或机器代码。

误区2：忽视栈帧管理

栈帧管理是函数调用的核心。错误的栈帧管理会导致栈溢出、内存泄漏等问题。

误区3：不理解内存段的作用

每个内存段都有特定的用途。理解这些用途对于正确编写VM程序至关重要。

误区4：认为VM效率低下

虽然VM增加了一层抽象，但通过优化技术(JIT、AOT编译等)，VM可以达到接近本地代码的性能。

误区5：忽视错误处理

VM程序需要处理各种错误：栈溢出、除零、空指针等。良好的错误处理机制对于程序的健壮性至关重要。

实践应用

实践1：实现push指令

push constant n的实现：

asm

// push constant n
@n
D=A
@SP
A=M
M=D
@SP
M=M+1

push local i的实现：

asm

// push local i
@LCL
D=M
@i
A=D+A
D=M
@SP
A=M
M=D
@SP
M=M+1

实践2：实现pop指令

pop local i的实现：

asm

// pop local i
@SP
M=M-1
A=M
D=M
@LCL
A=M
@i
A=A+A  // 这里需要正确的偏移计算
M=D

实践3：实现算术指令

add指令的实现：

asm

// add
@SP
A=M-1
D=M
@SP
A=M-2
M=D+M
@SP
M=M-1

neg指令的实现：

asm

// neg
@SP
A=M-1
M=-M

实践4：实现比较指令

eq指令的实现：

asm

// eq
@SP
A=M-1
D=M
@SP
A=M-2
D=M-D
@TRUE_EQ
JEQ
@SP
A=M-2
A=M
M=0
@END_EQ
JMP
(TRUE_EQ)
@SP
A=M-2
A=M
M=-1
(END_EQ)
@SP
M=M-1

实践5：实现程序流指令

label指令的实现：

asm

// label LOOP
(LOOP)

goto指令的实现：

asm

// goto LOOP
@LOOP
A=M
JMP

if-goto指令的实现：

asm

// if-goto LOOP
@SP
A=M-1
D=M
@SP
M=M-1
@LOOP
D;JNE

实践6：编写VM程序

编写一个计算斐波那契数列的VM程序：

function Main.fibonacci 0
  push argument 0
  push constant 2
  lt
  if-goto BASE_CASE
  push argument 0
  push constant 1
  sub
  call Main.fibonacci 1
  push argument 0
  push constant 2
  sub
  call Main.fibonacci 1
  add
  return
label BASE_CASE
  push argument 0
  return

本章小结

本章我们深入学习了Stack VM的架构和指令集。

核心要点回顾

虚拟机概念：提供独立于硬件的抽象计算环境。

Stack VM架构：基于栈的虚拟机，使用栈进行所有运算。

指令集：包括栈操作、算术运算、逻辑运算、比较、程序流和函数调用指令。

内存段：支持constant、local、argument、this、that、pointer、temp等内存段。

函数调用：通过栈帧管理实现函数调用和返回。

实现策略：VM指令需要映射到Hack汇编语言实现。

关键技能掌握

理解栈式VM的工作原理
掌握VM指令集的使用方法
能够编写VM程序
理解函数调用机制
了解VM实现的基本策略

与后续章节的联系

本章学习的VM知识是后续章节的基础：

第八章将继续介绍函数调用和面向对象的实现
第十章和第十一章将构建编译器，将高级语言编译为VM代码
第十二章将实现操作系统，为VM提供运行时支持

学习建议

理解栈操作：栈是VM的核心，必须深入理解

动手实践：亲手编写和测试VM程序

思考映射：思考如何将VM指令映射到汇编语言

循序渐进：从简单指令开始，逐步处理复杂功能

通过本章的学习，你已经掌握了虚拟机的核心知识。虚拟机是现代软件技术的基础，理解其工作原理对于理解Java、.NET、Python等技术栈至关重要。从硬件到虚拟机，我们完成了一次重要的抽象跃迁，为构建更复杂的软件系统奠定了基础。

第七章 虚拟机（上）

导读