第八章虚拟机（下）

导读

在第七章中，我们学习了Stack VM的基本指令集和栈操作。本章将深入探讨更复杂的VM功能：函数调用、程序流控制和面向对象编程支持。

函数调用是编程语言的核心功能之一，它支持代码的模块化和重用。程序流控制(条件分支和循环)使程序能够根据不同情况执行不同的操作。面向对象编程支持则使VM能够处理类和对象。

通过本章的学习，你将理解VM如何支持这些高级功能，掌握函数调用约定和栈帧管理，并为实现完整的VM翻译器奠定基础。

核心概念详解

8.1 函数调用详解

函数调用是VM最复杂的功能之一，涉及栈帧管理、参数传递和返回值处理。

调用约定

Stack VM使用以下调用约定：

调用者责任：

将参数压入栈

执行call指令

使用返回值(在栈顶)

被调用者责任：

保存必要的状态

执行函数体

将返回值压入栈

执行return指令

栈帧布局

函数调用时的栈帧布局：

高地址
+------------------+ <- 调用前的SP
| arg[n-1]         |
| ...              |
| arg[0]           |
+------------------+ <- call指令后
| ret_addr         |  <- 返回地址
+------------------+
| old LCL          |  <- 保存的LCL
| old ARG          |  <- 保存的ARG (新ARG指向这里)
| old THIS         |  <- 保存的THIS
| old THAT         |  <- 保存的THAT
+------------------+ <- 新LCL指向这里
| local[0]         |
| local[1]         |
| ...              |
| 工作栈           |
+------------------+ <- 新SP
低地址

call指令实现

call functionName nArgs的实现步骤：

将返回地址压入栈

保存LCL、ARG、THIS、THAT

重新定位ARG指向参数

重新定位LCL指向新栈帧

跳转到函数入口

asm

// call functionName nArgs
// 1. push返回地址
@ret_addr
D=A
@SP
A=M
M=D
@SP
M=M+1

// 2. 保存LCL, ARG, THIS, THAT
@LCL
D=M
@SP
A=M
M=D
@SP
M=M+1

@ARG
D=M
@SP
A=M
M=D
@SP
M=M+1

@THIS
D=M
@SP
A=M
M=D
@SP
M=M+1

@THAT
D=M
@SP
A=M
M=D
@SP
M=M+1

// 3. ARG = SP - nArgs - 5
@SP
D=M
@nArgs
D=D-A
@5
D=D-A
@ARG
M=D

// 4. LCL = SP
@SP
M=D  // 这里需要修正，应该是LCL=SP
@LCL
M=D  // 修正

// 5. goto functionName
@functionName
A=M
JMP

return指令实现

return指令的实现步骤：

保存返回值

恢复调用者的状态

重新定位SP

跳转回返回地址

asm

// return
// FRAME = LCL
@LCL
D=M
@FRAME
M=D

// RET = *(FRAME-5)
@FRAME
D=M
@5
A=D-A
D=M
@RET
M=D

// *ARG = pop()
@SP
A=M-1
D=M
@ARG
A=M
M=D

// SP = ARG + 1
@ARG
D=M+1
@SP
M=D

// THAT = *(FRAME-1)
@FRAME
D=M
@1
A=D-A
D=M
@THAT
M=D

// THIS = *(FRAME-2)
@FRAME
D=M
@2
A=D-A
D=M
@THIS
M=D

// ARG = *(FRAME-3)
@FRAME
D=M
@3
A=D-A
D=M
@ARG
M=D

// LCL = *(FRAME-4)
@FRAME
D=M
@4
A=D-A
D=M
@LCL
M=D

// goto RET
@RET
A=M
JMP

8.2 程序流控制

程序流控制包括条件分支和循环。

标签定义

label指令定义一个跳转目标：

label LOOP_START

在汇编语言中，标签转换为地址标记：

asm

(LOOP_START)

无条件跳转

goto指令无条件跳转到标签：

goto LOOP_START

汇编实现：

asm

@LOOP_START
A=M
JMP

条件跳转

if-goto指令在栈顶值非零时跳转：

if-goto LOOP_START

汇编实现：

asm

@SP
A=M-1
D=M      // D = 栈顶值
@SP
M=M-1    // SP--
@LOOP_START
D;JNE    // 如果D!=0，跳转

8.3 布尔运算

VM中的布尔值使用16位表示：

true = -1 (0xFFFF, 全1)
false = 0 (0x0000, 全0)

eq指令实现

asm

// eq: 如果栈顶两个值相等，推入-1，否则推入0
@SP
A=M-1
D=M      // D = y
@SP
A=M-2
D=M-D    // D = x - y
@EQ_TRUE
JEQ      // 如果x-y=0，跳转
@SP
A=M-2
M=0      // false
@EQ_END
JMP
(EQ_TRUE)
@SP
A=M-2
M=-1     // true
(EQ_END)
@SP
M=M-1

gt指令实现

asm

// gt: 如果x > y，推入-1，否则推入0
@SP
A=M-1
D=M      // D = y
@SP
A=M-2
D=M-D    // D = x - y
// 需要处理溢出
@GT_CHECK_OVERFLOW
D;JLT    // 如果x-y<0(可能是溢出)，检查
@GT_TRUE
JGT      // 如果x-y>0，跳转
@GT_FALSE
JMP
(GT_CHECK_OVERFLOW)
// 溢出处理：如果x正y负但结果负，说明溢出，应为true
// 如果x负y正但结果正，说明溢出，应为false
// 这里需要更复杂的逻辑
(GT_TRUE)
@SP
A=M-2
M=-1
@GT_END
JMP
(GT_FALSE)
@SP
A=M-2
M=0
(GT_END)
@SP
M=M-1

8.4 内存访问

VM支持多种内存段的访问。

this和that段

this和that段用于面向对象编程：

this指向当前对象的基地址
that指向数组的基地址

访问this[i]：

asm

@THIS
D=M
@i
A=D+A
D=M
@SP
A=M
M=D
@SP
M=M+1

pointer段

pointer段包含两个特殊指针：

pointer[0] = THIS
pointer[1] = THAT

设置pointer[0]：

asm

// pop pointer 0
@SP
A=M-1
D=M
@THIS
M=D
@SP
M=M-1

8.5 面向对象编程支持

VM为面向对象编程提供基础支持。

类的实现

类在VM中通过以下方式实现：

每个类对应一个命名空间
类方法通过类名前缀区分
实例变量通过this指针访问

示例：

// Point类的构造函数
function Point.new 0
  push constant 2
  call Memory.alloc 1
  pop pointer 0      // this = 新分配的对象
  push argument 0
  pop this 0         // this.x = x
  push argument 1
  pop this 1         // this.y = y
  push pointer 0
  return

方法调用

方法调用需要传递this指针作为隐含的第一个参数：

// obj.method(arg1, arg2)
// 转换为：
push obj             // 推入this
push arg1            // 推入参数1
push arg2            // 推入参数2
call Class.method 3  // 调用方法

8.6 数组处理

数组在VM中通过that段访问。

数组创建

// 创建大小为10的数组
push constant 10
call Array.new 1
pop pointer 1        // that = 新数组

数组访问

// arr[i] = value
push value
push i
add                  // 计算地址
pop that 0           // 这里需要修正

// 正确的数组访问
push pointer 1       // that = 数组基地址
D=M
@i
A=D+A                // 地址 = 基地址 + i
D=A                  // 这里需要修正

正确的数组元素访问：

asm

// arr[i] = value
@pointer
D=M                  // D = that
@1
A=D-A                // 这里需要修正

实际上，数组访问需要：

asm

// 设置that为数组基地址
push arrayBase
pop pointer 1        // that = arrayBase

// 访问arr[i]
push i
pop pointer 1        // that = arrayBase (重新设置)
// 然后使用that[i]

8.7 字符串处理

字符串在VM中作为字符数组处理。

字符串常量

字符串常量需要特殊处理：

// "Hello"
push constant 72     // 'H'
push constant 101    // 'e'
push constant 108    // 'l'
push constant 108    // 'l'
push constant 111    // 'o'
call String.new 5

8.8 异常处理

虽然基本VM不支持异常，但可以扩展支持。

异常处理机制

try {
  // 可能抛出异常的代码
} catch (Exception e) {
  // 异常处理代码
}

VM翻译需要：

维护异常处理栈

在异常发生时查找处理程序

展开栈帧到处理程序位置

重要知识点

知识点1：调用约定的重要性

调用约定是函数调用的契约。不同的调用约定影响：

参数传递方式
栈帧管理责任
寄存器保存责任

统一的调用约定确保不同模块之间的互操作性。

知识点2：栈帧展开

栈帧展开(Stack unwinding)是异常处理的关键：

在异常发生时，需要清理栈帧
调用析构函数或finally块
恢复到异常处理程序的位置

知识点3：尾调用优化

尾调用优化可以避免栈溢出：

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

知识点4：内联缓存

内联缓存是VM优化的重要技术：

缓存方法调用的目标地址
减少方法查找开销
对于动态类型语言特别有效

知识点5：垃圾回收策略

VM中的垃圾回收策略：

引用计数：跟踪每个对象的引用数
标记-清除：标记活动对象，清除未标记对象
分代回收：根据对象生命周期分代处理

常见误区

误区1：不理解栈帧布局

栈帧布局是函数调用的核心。错误的栈帧布局会导致参数访问错误、返回值丢失等问题。

误区2：忽视返回地址的保存

返回地址必须在调用函数前保存，否则无法正确返回。这是函数调用中最容易出错的地方之一。

误区3：混淆this和that

this指向当前对象，that指向数组。在方法调用中，this必须正确设置。

误区4：不理解布尔值表示

VM中true是-1(全1)，false是0(全0)。这种表示使得位运算和逻辑运算一致。

误区5：忽视溢出处理

在比较指令(gt, lt)中，减法可能溢出。必须正确处理溢出情况。

实践应用

实践1：实现完整的call指令

python

def translate_call(function_name, n_args):
    return_label = f"RETURN_{function_name}_{unique_id()}"
    
    asm = []
    # push返回地址
    asm.append(f"@{return_label}")
    asm.append("D=A")
    asm.append("@SP")
    asm.append("A=M")
    asm.append("M=D")
    asm.append("@SP")
    asm.append("M=M+1")
    
    # 保存LCL, ARG, THIS, THAT
    for segment in ["LCL", "ARG", "THIS", "THAT"]:
        asm.append(f"@{segment}")
        asm.append("D=M")
        asm.append("@SP")
        asm.append("A=M")
        asm.append("M=D")
        asm.append("@SP")
        asm.append("M=M+1")
    
    # ARG = SP - nArgs - 5
    asm.append("@SP")
    asm.append("D=M")
    asm.append(f"@{n_args + 5}")
    asm.append("D=D-A")
    asm.append("@ARG")
    asm.append("M=D")
    
    # LCL = SP
    asm.append("@SP")
    asm.append("M=D")  # 这里需要修正
    asm.append("@LCL")
    asm.append("M=D")  # 修正
    
    # goto function
    asm.append(f"@{function_name}")
    asm.append("A=M")
    asm.append("JMP")
    
    # 返回地址标签
    asm.append(f"({return_label})")
    
    return asm

实践2：实现完整的return指令

python

def translate_return():
    asm = []
    
    # FRAME = LCL
    asm.append("@LCL")
    asm.append("D=M")
    asm.append("@R13")  # FRAME临时变量
    asm.append("M=D")
    
    # RET = *(FRAME-5)
    asm.append("@R13")
    asm.append("D=M")
    asm.append("@5")
    asm.append("A=D-A")
    asm.append("D=M")
    asm.append("@R14")  # RET临时变量
    asm.append("M=D")
    
    # *ARG = pop()
    asm.append("@SP")
    asm.append("A=M-1")
    asm.append("D=M")
    asm.append("@ARG")
    asm.append("A=M")
    asm.append("M=D")
    
    # SP = ARG + 1
    asm.append("@ARG")
    asm.append("D=M+1")
    asm.append("@SP")
    asm.append("M=D")
    
    # 恢复THAT, THIS, ARG, LCL
    for i, segment in enumerate(["THAT", "THIS", "ARG", "LCL"]):
        asm.append("@R13")
        asm.append("D=M")
        asm.append(f"@{i+1}")
        asm.append("A=D-A")
        asm.append("D=M")
        asm.append(f"@{segment}")
        asm.append("M=D")
    
    # goto RET
    asm.append("@R14")
    asm.append("A=M")
    asm.append("JMP")
    
    return asm

实践3：实现比较指令

python

def translate_eq():
    label_true = f"EQ_TRUE_{unique_id()}"
    label_end = f"EQ_END_{unique_id()}"
    
    asm = []
    asm.append("@SP")
    asm.append("A=M-1")
    asm.append("D=M")
    asm.append("@SP")
    asm.append("A=M-2")
    asm.append("D=M-D")
    asm.append(f"@{label_true}")
    asm.append("JEQ")
    asm.append("@SP")
    asm.append("A=M-2")
    asm.append("M=0")
    asm.append(f"@{label_end}")
    asm.append("JMP")
    asm.append(f"({label_true})")
    asm.append("@SP")
    asm.append("A=M-2")
    asm.append("M=-1")
    asm.append(f"({label_end})")
    asm.append("@SP")
    asm.append("M=M-1")
    
    return asm

实践4：实现数组访问

python

def translate_array_access(array_var, index):
    asm = []
    
    # 加载数组基地址
    asm.append(f"@{array_var}")
    asm.append("D=M")
    
    # 加上索引
    asm.append(f"@{index}")
    asm.append("A=D+A")
    
    # 访问元素
    asm.append("D=M")
    
    # 压入栈
    asm.append("@SP")
    asm.append("A=M")
    asm.append("M=D")
    asm.append("@SP")
    asm.append("M=M+1")
    
    return asm

实践5：实现方法调用

python

def translate_method_call(class_name, method_name, n_args):
    # 方法名格式：ClassName.methodName
    full_name = f"{class_name}.{method_name}"
    
    # 参数已经在栈上，包括this
    return translate_call(full_name, n_args)

实践6：编写完整的VM程序

编写一个完整的VM程序示例：

// Main.vm - 计算阶乘
function Main.factorial 0
  push argument 0
  push constant 2
  lt
  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

// Sys.vm - 程序入口
function Sys.init 0
  push constant 5
  call Main.factorial 1
  label END
  goto END

本章小结

本章我们深入学习了VM的高级功能：函数调用、程序流控制和面向对象支持。

核心要点回顾

函数调用：通过栈帧管理实现，涉及参数传递、状态保存和返回值处理。

程序流控制：通过label、goto和if-goto指令实现条件分支和循环。

布尔运算：使用-1表示true，0表示false，确保位运算和逻辑运算一致。

内存访问：支持this、that、pointer等内存段，为面向对象编程提供基础。

面向对象支持：通过this指针和类命名空间实现类和方法。

数组处理：通过that段和指针运算实现数组访问。

关键技能掌握

理解函数调用的完整过程
掌握栈帧布局和管理的细节
能够实现call和return指令
理解程序流控制的实现
掌握面向对象编程的VM支持

与后续章节的联系

本章完成的VM知识是后续章节的基础：

第九章将介绍高级语言Jack
第十章和第十一章将构建Jack编译器，将Jack代码编译为VM代码
第十二章将实现操作系统，为VM程序提供运行时支持

学习建议

理解调用约定：这是函数调用的核心，必须深入理解

关注细节：栈帧管理涉及很多细节，需要仔细处理

动手实践：亲手实现VM翻译器的各个部分

测试验证：使用各种测试程序验证实现的正确性

通过本章的学习，你已经掌握了VM的完整知识。从基本的栈操作到复杂的函数调用，VM提供了丰富的抽象，使编程变得更加容易。理解VM的工作原理，对于理解Java、.NET、Python等现代技术栈至关重要。现在，我们有了完整的VM，下一步是构建编译器，将高级语言转换为VM代码。

第八章 虚拟机（下）

导读

核心概念详解

8.1 函数调用详解

调用约定

栈帧布局

call指令实现

return指令实现

8.2 程序流控制

标签定义

无条件跳转

条件跳转

8.3 布尔运算

eq指令实现

gt指令实现

8.4 内存访问

this和that段

pointer段

8.5 面向对象编程支持

类的实现

方法调用

8.6 数组处理

数组创建

数组访问

8.7 字符串处理

字符串常量

8.8 异常处理

异常处理机制

重要知识点

知识点1：调用约定的重要性

知识点2：栈帧展开

知识点3：尾调用优化

知识点4：内联缓存

知识点5：垃圾回收策略

常见误区

误区1：不理解栈帧布局

误区2：忽视返回地址的保存

误区3：混淆this和that

误区4：不理解布尔值表示

误区5：忽视溢出处理

实践应用

实践1：实现完整的call指令

实践2：实现完整的return指令

实践3：实现比较指令

实践4：实现数组访问

实践5：实现方法调用

实践6：编写完整的VM程序

本章小结

核心要点回顾

关键技能掌握

与后续章节的联系

学习建议

第八章虚拟机（下）