0

如何在自定义虚拟机中实现尾调用？

我知道我需要弹出原始函数的本地堆栈，然后是参数，然后推送新参数。但是，如果我弹出函数的本地堆栈，我应该如何推送新参数？他们刚刚从堆栈中弹出。

4

2 回答 2

4

我想当然地认为我们在这里讨论的是传统的“基于堆栈”的虚拟机。

您弹出当前函数的本地堆栈，保留非堆栈“寄存器”中仍然相关的部分（其中“相关部分”显然是即将到来的递归尾调用的参数），然后（一旦所有函数的本地堆栈和参数被清理）你推送递归调用的参数。例如，假设您正在优化的功能类似于：

def aux(n, tot):
  if n <= 1: return tot
  return aux(n-1, tot * n)

如果没有优化，它可能会产生象征性的字节码，如：

AUX:   LOAD_VAR   N
       LOAD_CONST 1
       COMPARE
       JUMPIF_GT  LAB
       LOAD_VAR   TOT
       RETURN_VAL
LAB:   LOAD_VAR   N
       LOAD_CONST 1
       SUBTRACT
       LOAD_VAR   TOT
       LOAD_VAR   N
       MULTIPLY
       CALL_FUN2  AUX
       RETURN_VAL

CALL_FUN2 的意思是“调用带有两个参数的函数”。通过优化，它可能会变成这样：

   POP_KEEP     2
   POP_DISCARD  2
   PUSH_KEPT    2
   JUMP         AUX

当然，我正在编写我的符号字节码，但我希望意图很明确：POP_DISCARD n是普通的弹出，它只是丢弃n堆栈中的顶部条目，但POP_KEEP n它是一种将它们保持在“某处”的变体（例如一个辅助堆栈不能被应用程序直接访问，而只能被虚拟机自己的机器访问——在讨论虚拟机实现时，具有这样一个字符的存储有时被称为“寄存器”）和一个匹配PUSH_KEPT n，它将“寄存器”清空回虚拟机的正常堆栈.

于 2010-05-13T14:33:00.167 回答
1

我认为您以错误的方式看待这个问题。不要将旧变量从堆栈中弹出然后推送新变量，只需重新分配已经存在的变量（小心地）。如果您将代码重写为等效的迭代算法，这与将发生的优化大致相同。

对于此代码：

 int fact(int x, int total=1) {
     if (x == 1)
         return total;
     return fact(x-1, total*x);
 }

将会

 fact:
   jmpne x, 1, fact_cont  # if x!=1 jump to multiply
   retrn total            # return total
 fact_cont:               # update variables for "recursion
   mul total,x,total      # total=total*x
   sub x,1,x              # x=x-1
   jmp fact               #"recurse"

无需在堆栈上弹出或推送任何内容，只需重新分配即可。
显然，这可以进一步优化，通过将退出条件放在第二位，允许我们跳过一个跳转，从而减少操作。

 fact_cont:               # update variables for "recursion
   mul total,x,total      # total=total*x
   sub x,1,x              # x=x-1
 fact:
   jmpne x, 1, fact_cont  # if x!=1 jump to multiply
   retrn total            # return total

再看一遍，这个“程序集”更好地反映了这个 C++，它显然避免了递归调用

int fact(int x, int total=1)
    for( ; x>1; --x)
        total*=x;
    return total;
}
于 2013-06-25T23:24:07.693 回答