虚拟机 2：程序控制

在计算机科学领域的竞赛中，堆栈处理（stack processing）绝对是进入决赛的强大选手。前面的章节已介绍算术表达式和布尔表达式是如何利用基本堆栈操作来进行计算的。本章将继续介绍这个简单的数据结构如何支持像嵌套子程序调用、参数传递、递归和内存分配技术这样的复杂任务。大多数程序员不希望在这些功能上花功夫，而指望编译器来帮他们实现。现在我们就打开这个黑盒子，揭示这些基本编程机制是如何被基于堆栈的虚拟机实现的。

背景知识

当我们在高级语言中调用一个简单的函数时，在底层有很多细节需要处理：

将参数从调用者（caller）传递给被调用者（called subroutine）
在跳转并执行被调用者之前，先保存调用者的状态
为被调用者使用的局部变量分配空间
跳转并执行被调用者
将被调用者的运行结果返回给调用者
在从被调用者返回之前，回收其使用的内存空间
恢复调用者的状态
返回到调用语句之后的下一条语句继续执行

要考虑这些琐碎的事情是很头疼的，好在编译器把高级语言程序员从中解脱出来。那么编译器是如何做到这些的呢？如果我们用堆栈机（stack machine）来完成底层操作，那么以上工作的处理就很简单了，事实上堆栈结构本身的优势就在于处理这种类似任务。

本节剩余的内容将描述程序控制流（program flow）命令和子程序调用（subroutinecalling）命令是如何在堆栈机上实现的。

子程序调用

在cal1 xxx 操作的底层实现中，先将调用者的帧保存到堆栈中，然后为子程序（xxx）的局部变量分配堆栈空间，最后跳到子程序 xxx开始执行其代码。

最后一步“大跳转”并不难实现。因为目标子程序的名字在 ca11 命令中已经被指定了，这样在调用过程中可以将这个目标程序名解析成一个内存地址，然后跳转到以该内存地址为基址的代码段（该代码段就是子程序的代码段）开始执行。

而通过 return 命令从子程序中返回的过程却暗藏玄机，因为命令中并未指定返回地址。事实上，在所有调用子程序的过程中，调用者的返回地址都没有显式地给出。比如，因为像 power（x, y）或sqzt（x）这样的子程序可以被任何调用者调用，那么它们的代码中就不可能给出具体的返回地址。所以，return 命令应该按如下方式来解释：它将程序的执行重定向到调用语句ca11 命令的下一条命令所在的内存地址（不论这条命令的内存位置具体在哪），即称为返回地址（return address）。

我们用 ca11 xxx指令执行调用操作时，应该知道准确的返回地址：指令ca11 xxx 的下一条指令的内存地址。因此，我们将该指令内存地址作为返回地址压入堆栈保存，然后去执行子程序。当我们最终遇到return命令时，我们就将先前保存在堆栈中的返回地址弹出来，然后只用简单的goto 命令跳转到这个地址就可以了。换句话说就是返回地址也可以保存在调用者的帧里面。

VM 规范详述（第二部分）

程序控制流命令

VM 语言有三种形式的程序控制流命令： - label：该命令标记程序中某条指令的位置，在程序中的跳转指令只能跳转到被 label label 命令所标示的位置 - goto label：该命令执行无条件跳转操作，使得程序跳转到label label 命令标示的位置那里继续执行。跳转的目的地址必须位于同一个程序之内。 - if-goto label：该命令执行条件跳转操作。首先，将布尔表达式的运算结果从堆栈顶端弹出，如果该值非 0，那么程序就跳转到label 标示的位置继续执行；否则，继续执行程序中的下一条命令。跳转的目的地址必须位于同一个函数内。

函数调用命令

VM语言有三种函数相关的命令：

function f n：一段函数名为f的代码，该函数有n个参数；
call f m: 调用函数f，其m个参数已经被调用者压入堆栈：
return: 返回到调用者。

函数调用协议

实现

Hack 平台上的标准 VM 映射

全局堆栈：VM 的内存资源是通过维护一个全局的堆栈来得到的。每当调用一个函数时，该函数对应的帧（frame）就被压入全局堆栈。该帧包括被调用函数（called function）将要使用的参数：一组用于保存调用者状态的指针（pointers）：被调用函数的局部变量（被初始化为0）：以及一个被调用函数将要使用的工作堆栈（当前为空）。