如何在自定义虚拟机中实现尾部呼叫

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

2010-05-13 Puppy

我认为我们正在讨论传统的“基于堆栈”的虚拟机。

您弹出当前函数的本地堆栈保留非堆栈“寄存器”中的相关部分（其中“相关部分”显然是即将进行的递归尾部调用的参数），则一旦清除了函数的所有本地堆栈和参数），就会为递归调用推送参数。例如，假设您正在优化的功能是一样的东西：

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是一个让它们“在某个地方”的变体（例如，在辅助堆栈中，不能直接访问应用程序，但只能访问VM自己的机器 - 具有这种字符的存储有时称为“寄存器”当讨论虚拟机的实现时）以及将“注册”清空回虚拟机正常堆栈的相匹配的PUSH_KEPT n。

来源

2010-05-13 14:33:00

与麻烦的是，问题的类型（和它们的大小）是完全未知。我可以转移到内部堆栈，但这会限制总参数大小。我猜如果我做了200字节的话，那么这比任何理智的人都想要转移更多。干杯。 – Puppy 2010-05-13 15:49:35

@DeadMG，处理在编译时未知的任意类型，通常的做法是传递_pointers_（例如，在CPython VM中，指向'PyObject'的指针） - 或等价地引用，如果您的实现语言不使用指针。然后，堆栈上下的大小是众所周知的 - “sizeof（whatever *）”，例如，32位机器中的每个对象4个字节。 – 2010-05-13 16:23:44

如果我只在栈上存储指针，我到底在哪里放置它们指向的内容？ – Puppy 2010-05-13 21:16:12

我认为你看着这个错误的方式。不要将旧的变量从堆栈中弹出，然后推入新的变量，只需重新分配已经存在的那些（仔细）。如果将代码重新编写为等效的迭代算法，这与优化大致相同。

对于此代码：

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-25 23:24:07

如何在自定义虚拟机中实现尾部呼叫

回答

相关问题