子程序、栈与递归

上节课我们构建了迭代求解最大公约数的寄存器机器，本节我们将为寄存器机器新增两个组件子程序 (subroutine) 和栈 (stack)。本节要点：

  • 每个程序与子程序之间需要遵守规定的契约

  • 栈是实现递归算法的基石

子程序

顾名思义，子程序就是一系列固定的指令：

  • 以一个标记 (label) 为起点，进入子程序，结束后可以跳转回父程序继续执行

  • 可以从许多地方进入子程序，从而达到复用的目的

为支持子程序，register machine 需要新增两个指令

  • **(assign continue (label after-call-1)): **将父程序中，执行完子程序后的命令地址的标记 (label (after-call-1)) 记录到 continue 寄存器中

  • (goto (reg continue)): 将寄存器 PC 的值修改成之前存储在 continue 当中标记指向的指令地址，从而达到返回父程序的目的

例子：increment

(controller
  (assign sum (const 0))
  (assign continue (label after-call-1))       ; 1
  (goto (label increment))                     ; 2
after-call-1
  (assign continue (label after-call-2))       ; 4
  (goto (label increment))                     ; 5
after-call-2
  (goto (label done))                          ; 6
increment
  (assign sum (op +) (reg sum) (const 1))
  (goto (reg continue))                        ; 3
done)                                          ; 7

  1. 主程序将调用子程序 increment 结束后的指令地址标记 after-call-1 存入 continue 寄存器中

  2. 主程序调用子程序 increment

  3. 子程序 increment 执行完自增操作后，返回 continue 寄存器中存储的标记指向的返回地址

  4. 主程序将调用子程序 increment 结束后的指令地址标记 after-call-2 存入 continue 寄存器中

  5. 主程序调用子程序 increment

  6. 子程序 increment 执行完自增操作后，返回 continue 寄存器中存储的标记指向的返回地址

  7. 主程序继续执行 (goto (label done)) 后，程序运行结束

子程序与父程序的契约包括：

  • 存储子程序输入参数以及返回地址的寄存器

  • 存储子程序输出返回值的寄存器

  • 除了返回值所在的寄存器，其它可能被修改的寄存器

如果这些契约没有被遵守，子程序调用就会失效，甚至可能造成程序崩溃。

如，increment 子程序与父程序之间的契约：

  • 输入参数和返回地址的寄存器: sum, continue

  • 返回值寄存器: sum

  • 其它寄存器：无

为什么需要子程序？

  • 复用程序段

  • 提高程序可读性

  • 支持递归

栈

Stack 支持两种操作，save 和 restore，对应 push 和 pop，它支持存储多个数值，且最后一个进栈的元素将第一个出栈 (Last In First Out)，举例如下：

(controller
  (assign a (const 0))
  (assign b (const 5))
  (save a)
  (save b)
  (restore a)
  (restore b))

上面这段指令就是利用栈的 LIFO 特点，交换 a、b 寄存器中的数值。

栈深 (stack depth)

栈的深度就是任意时刻，栈中所含元素的数量。

stack depth = (# of saves) - (# of restores)

而最大栈深 (max stack depth) 指的是某程序在执行时，所需栈深的最大值。栈深最小值为 0，最大值与所能获取的最大内存相等。

栈与父子程序之间的契约

有了栈以后，父子程序之间的契约还应该包括栈相关的信息：

标准契约

一般情况下，子程序在被调用期间不会修改栈信息，以 increment 为例：

  • 输入参数和返回地址的寄存器: sum, continue

  • 返回值寄存器: sum

  • 其它寄存器：无

  • 栈：不变

非标准契约

特殊情况下，子程序可以在被调用期间修改栈信息，举例如下：

strange
  (assign val (op *) (reg val) (const 2))
  (restore continue)
  (goto (reg continue))

  • 输入参数和返回地址的寄存器： val, return point on top of stack

  • 返回值寄存器：val

  • 其它寄存器：continue

  • 栈：栈顶的元素出栈

该契约将原本存储在 continue 中的信息压入栈中，子程序通过出栈操作获取调用返回地址。

尾递归优化

通常递归需要占用和递归深度一致的空间，但如果递归的返回值并不需要额外后处理的话，我们可以更机智地使用栈，将递归的过程优化成迭代的过程，从而使得空间占用达到常数级别，但依然可以保持递归程序的可读性。由于尚未介绍递归，这里暂不举例。

递归

以阶乘为例：

(define (fact n)
  (if (= n 1) 1
      (* n (fact (- n 1)))))

利用替代模型，我们可以看到 (fact 3) 的执行过程：

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 1))
(* 3 2)
6

要完成这个过程，register machine 需要：

  • 记住每次递归调用的返回地址

  • 记住每个中间结果

正好子程序和栈可以帮助 register machine 做到：

(controller
  (assign continue (label halt))
fact
  (test (op =) (reg n) (const 1))
  (branch (label b-case))
  (save continue)
  (save n)
  (assign n (op -) (reg n) (const 1))
  (assign continue (label r-done))
  (goto (label fact))
r-done
  (restore n)
  (restore continue)
  (assign val (op *) (reg n) (reg val))
  (goto (reg continue))
b-case 
  (assign val (const 1))
  (goto (reg continue))
halt)

base case:

;...
(if (= n 1) 1
   ; ...

对应 register machine instructions:

;...
fact
  (test (op =) (reg n) (const 1))
  (branch (label b-case))
;...
b-case
  (assign val (const 1))
 (goto (reg continue))

从中，我们也可以看出 fact 与父程序间的部分契约：

  • 输入参数寄存器: n

  • 返回地址寄存器: continue

  • 返回值寄存器: val

recursive case:

(define (fact n)
  ; ...
      (fact (- n 1))
  ; ...)

对应 register machine instructions:

    ;...
    (assign n (op -) (reg n) (const 1))
    (assign continue (label r-done))
    (goto (label fact))
r-done
    (assign val (op *) (reg n) (reg val))
    (goto (reg continue))

与 base case 中提到的契约一样，这里在递归调用 fact 之前，按照契约，把参数 n 和返回标记 (label r-done) 放到对应的寄存器中。在执行完递归调用的 fact 后，再把 val 与当前的 n 相乘，结果存入 val 寄存器中作为结果输出。

但是，在上述过程中，我们多次覆盖寄存器 n 与 continue 中存储的数值，因此在覆盖之前，我们要将会被覆盖的寄存器的值压入栈中，然后在需要的时候从栈中弹出。具体体现在了 save 和 restore 命令中。

fact 与父程序间的完整契约：

  • 输入参数与返回地址寄存器：n, continue

  • 返回值寄存器：val

  • 其它被修改的寄存器：无

  • 栈：不变

明明修改了 n 和 continue，为什么说没有其它被修改的寄存器？

因为虽然 fact 中修改了 n 和 continue，但是由于父程序在调用 fact 之前已经将原先的 n 和 continue 压入栈中，待子程序返回时从栈中弹出，从整个过程来看，fact 并没有真正修改 n 和 continue。

明明有出入栈的操作，为什么 stack 不变？

因为在 fact 递归调用前入栈的信息，在调用完成后全部出栈，整个过程来看栈并没有发生变化。

小结

子程序和栈的出现，让我们得以复用代码、提高代码可读性以及利用递归解决问题。对于人来说，递归比迭代代码更好理解；对于机器来说，递归比迭代更耗费空间。我们在写生产代码时，时间复杂度、空间复杂度、可读性三者都需要充分权衡。

参考

Previous寄存器机器Next在寄存器机器中执行

Last updated