如何在自定義虛擬機中實現尾部呼叫

我知道我需要彈出原始函數的本地堆棧，然後它是參數，然後推入新的參數。但是，如果我彈出函數的本地堆棧，我該如何推動新的參數？他們剛剛從堆棧中彈出。

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

如何在自定義虛擬機中實現尾部呼叫

回答

相關問題