2016-08-05 26 views
3

在講座期間,我給出了tail調用的定義,它是在尾部環境中發生的調用表達式。我擡頭尾上下文的定義中The Revised Report on the Algorithmic Language Scheme函數的尾部上下文是什麼?

尾呼叫是發生在一個尾上下文一個過程調用。尾部上下文是歸納定義的。請注意,尾部上下文始終是針對特定的lambda表達式確定的。

我不覺得這其中的任何一個實際上已經清楚地確定了尾巴背景是什麼,有人可以給出一個解釋,這可能會讓初學者更容易理解嗎?

回答

1

尾部是 動物 功能的最後部分。直觀地說,如果函數除了將評估結果返回給調用者,它將不再做任何事情,而是在尾部上下文中進行評估。

關於尾部上下文的關鍵觀察是,在調用幀中不需要任何東西(除了對調用者的引用),從而允許調用幀被尾部上下文中執行的調用重用。這樣做可以將某些遞歸算法的空間需求從O(N)更改爲O(1),或者O(log N)在像快速排序那樣的算法中執行不完全分區。

程序流分析可以識別回收調用幀的其他可能機會,但在許多語言中,尾部上下文可以通過簡單的語法分析來識別。在計劃的情況下,程序在原始文章中鏈接的語言文件中指定。 Scheme要求如果可以用這種方式識別尾部呼叫,則優化尾部呼叫。

在許多其他語言中,tail call優化不是必需的,在某些情況下甚至不可能。例如,在C++中,可能存在隱式析構函數,需要在最後一次調用之後和返回之前運行;此外,返回的值可能需要轉換爲不同的類型。在調用框架可用於內省的語言(例如Javascript)中,調用框架回收將修改可觀察程序的行爲。