如何使用遞歸內聯？

Question

從Programming Language Pragmatics, by Scott，關於在襯裏和遞歸：

直列擴展也沒有針對 遞歸子程序一般情況下一個選項。對於可能的遞歸調用 但不太可能的偶爾情況，可能希望生成真正的遞歸子例程，但是要在處以的順序擴展該例程的一級 。

作爲一個簡單的例子，考慮一個葉子包含 字符串的二叉樹。例行返回此樹（在其葉子值的 左到右連接）的邊緣看起來 這樣在C++：

string fringe(bin_tree *t) { 
    // assume both children are nil or neither is 
    if (t->left == 0) return t->val; 
    return fringe(t->left) + fringe(t->right); 
} 

編譯器可以擴大在線驗證碼如果它使每個嵌套調用一個真子程序調用。由於二進制 樹中的一半節點是樹葉，因此此擴展在運行時將消除一半的動態調用 。

如果我們擴大不僅僅是根通話，但也真正的子程序版本內的兩個 電話（一個級別），只有 原有動態調用的四分之一將保留。

我無法理解下面的句子：如果它讓每個

• 「擴大在每次調用點在線，常規的一平」
• 「拓展在線驗證碼嵌套調用一個真正的子程序調用。「
• 「擴大不僅僅是根通話，但也真實子程序版本中的兩個電話（一平）」

什麼實際上他們的意思？你可以用給出的例子來解釋它們嗎，例如，在採取每個句子的動作之後，顯示代碼是什麼樣的？

謝謝。

Answer 1

一些編譯器可以擴展和嵌入相當嵌套的遞歸調用。通過GCC 7.2（在Linux/Debian的/ SID上的x86-64）到

static int fact(int n) { 
    if (n<=1) return 1; 
    else return n* fact(n-1); 
} 

extern "C" int f5(); 
int f5() { 
    return fact(5); 
}  

時（使用g++ -O2 -fverbose-asm -S）編譯：

例如下面的代碼（在這裏我沒有使用inline關鍵字！）一個簡單的函數返回120：

  .text 
     .p2align 4,,15 
     .globl f5 
     .type f5, @function 
f5: 
.LFB1: 
     .cfi_startproc 
# e.cc:10: }; 
     movl $120, %eax  #, 
     ret 
     .cfi_endproc 
.LFE1: 
     .size f5, .-f5 
     .ident "GCC: (Debian 7.2.0-1) 7.2.0" 
     .section  .note.GNU-stack,"",@progbits 

注意fact已經完全內聯和不會出現在所生成的彙編代碼。

「擴大在每次調用點在線，常規的一平」

這將意味着f5會被編譯成

int f5() { return 5*fact(4); } 

相當於用fact出現在生成的代碼中編譯成遞歸（機器代碼）函數（消耗調用堆棧）。

Answer 2

到目前爲止，瞭解這一點的最簡單方法是將內聯視爲創建替代二進制表示。例如。除了創建基本的string fringe(bin_tree *t)之外，編譯器還可能決定創建string fringe__inlined(bin_tree *t)。並且在fringe__inlined中，實際內聯函數將是fringe的一個或兩個副本。

甚至有可能以這種方式創建fringe__inlined__inlined（如上所述的兩個級別）。

Answer 3

你能與給定的例子來解釋它們，例如，顯示代碼是什麼樣的

注：編譯器/優化器不會做，你寫在C這些動作++代碼，但在一些內部表示。可以用C++來展示這個想法，但由於語法和可讀性問題，我們可能需要引入其他更改，例如臨時變量。

在每個呼叫站點上在線擴展該例程的一個級別。

result = fringe(t); 

成爲

if (t->left == 0) result = t->val; 
else result = fringe(t->left) + fringe(t->right); 

擴大不僅僅是根通話，但也真子程序版本

if (t->left == 0) result = t->val; 
else { 
    string left, right; 

    // one level of expansion for left subtree 
    if (t->left->left == 0) left = t->left->val; 
    else left = fringe(t->left->left) + fringe(t->left->right); 

    // one level of expansion for right subtree 
    if (t->right->left == 0) right = t->right->val; 
    else right = fringe(t->right->left) + fringe(t->right->right); 

    result = left + right; 
}