求值策略

在計算機科學中，求值策略(Evaluation strategy)是確定程式語言中表達式的求值的一組（通常確定性的）規則。重點典型的位於函式或運算元上——求值策略定義何時和以何種次序求值給函式的實際參數，什麼時候把它們代換入函式，和代換以何種形式發生。經常使用用來研究函式的形式系統λ演算來建模求值策略，這裡它們通常叫做歸約策略。求值策略分為兩大基本類，嚴格的和非嚴格的，基於如何處理給函式的實際參數。一個語言可以組合多種求值策略；例如C++組合了傳值調用和傳引用調用。多數語言對布爾表達式和if語句使用某種形式的非嚴格求值。

基本介紹

• 中文名：求值策略
• 外文名：Evaluation strategy

嚴格求值

在“嚴格求值”中，給函式的實際參數總是在套用這個函式之前求值。

在邱奇編碼下，運算元的熱情求值映射到了函式的嚴格求值；為此嚴格求值有時叫做“熱情求值”。多數現存程式語言對函式使用嚴格求值。

套用次序

“套用次序”(或“最左最內”)求值稱呼函式的實際參數按可歸約表達式的後序遍歷從左至右的求值的策略。不像傳值調用，套用次序求值儘可能的在套用函式之前歸約函式體內的項。

傳值調用

“傳值調用”求值是最常見的求值策略，C和Scheme這樣差異巨大的語言都在使用。在傳值調用中實際參數被求值，其值被綁定到函式中對應的變數上（通常是把值複製到新記憶體區域）。如果函式或過程能把值賦給它的形式參數，則被賦值的只是局部拷貝 -- 就是說，在函式返回後調用者作用域裡的曾傳給函式的任何東西都不會變。

傳值調用不是一個單一的求值策略，而是指一類函式的實參在被傳給函式之前就被求值的求值策略。儘管很多使用傳值調用的程式語言（如Common Lisp、Eiffel、Java）從左至右的求值函式的實際參數，某些語言（比如OCaml）從右至左的求值函式和它們的實際參數，而另一些語言（比如 Scheme 和 C）未指定這種次序(儘管它們保證順序一致性)。

傳引用調用 (

在“傳引用調用”求值中，傳遞給函式的是它的實際參數的隱式引用而不是實參的拷貝。通常函式能夠修改這些參數（比如賦值），而且改變對於調用者是可見的。因此傳引用調用提供了一種調用者和函式交換數據的方法。傳引用調用的語言中追蹤函式調用的副作用比較難，易產生不易察覺的bug。

很多語言支持某種形式的傳引用調用，但是很少有語言默認使用它。FORTRAN II是一種早期的傳引用調用語言。一些語言如C++,PHP,Visual Basic .NET,C#和REALbasic默認使用傳值調用，但是提供一種傳引用的特別語法。

在那些使用傳值調用又不支持傳引用調用的語言裡，可以用引用（引用其他對象的對象），比如指針（表示其他對象的記憶體地址的對象）來模擬。C和ML就用了這種方法。這不是一種不同的求值策略（語言本身還是傳值調用）。它有時被叫做“傳地址調用” （call by address）。 這可能讓人不易理解。在C之類不安全的語言裡會引發解引用空指針之類的錯誤。但ML 的引用是類型安全和記憶體安全的。

類似的效果可由傳共享對象調用（傳遞一個可變對象）實現。比如Python、Ruby。

傳共享對象調用

此方式由 Barbara Liskov 命名，並被 Python、Java（對象類型）、JavaScript、Scheme、OCaml 等語言使用。

與傳引用調用不同，對於調用者而言在被調用函數裡修改參數是沒有影響的。如果要達成傳引用調用的效果就需要傳一個共享對象，一旦被調用者修改了對象，調用者就可以看到變化（因為對象是共享的，沒有拷貝）。比如這段Python代碼：

def f(l):    l.append(1)    l = [2]m = []f(m)print(m)

會輸出[1]而不是[2]。因為列表是可變的，append方法改變了m。而賦值局部變數l的行為對外面作用域沒有影響（在這類語言中賦值是給變數綁定一個新對象，而不是改變對象）。

使用C/C++語言的程式設計師可能因不能用指針等使函式返回多個值而感到不便，但是像Python這樣的語言提供了替代方案：函式能方便的返回多個值，比C++11的std::tie更加簡單。

傳復件-恢復調用

“傳復件-恢復調用”、“傳值-結果調用”或“傳值-返回調用”(在Fortran社區中的術語)是傳引用調用的特殊情況，即在傳引用調用時，向被叫進程所傳遞的引用並非調用進程原有的引用，而是一個原有引用的複製，即被傳遞的引用與調用進程沒有關係。傳復件-恢復調用在這種情況下很重要：如果函式調用的一個形式參數，是可能被其他執行執行緒同時訪問的引用。那么就把這個引用的內容複製到一個新創建的引用中，再將這個新創建的、與調用進程無關的引用傳遞給被叫進程。當被叫進程執行結束、調用返回的時候，再把這個新引用中更新過的內容複製回調叫進程原來的引用中（“恢復”）。

傳值-返回調用的語義在兩個或更多實際參數相互是別名的時候也不同於傳引用調用，就是說它們都指向了在調用者環境中的同一個變數。在傳引用調用下，寫其中一個會影響另一個；傳值-返回調用通過給函式以獨自的復件來避免了這種情況，但沒有規定在調用者環境中的結果(依賴於哪個別名實際參數首先被複製回去)。

當引用未初始化就傳遞給被調用者的時候，這種求值策略可以叫“傳結果調用”。

部分求值

更多信息：柯里化

在“部分求值”中，求值可以延續到仍未被套用的函式體之內。求值不包含未綁定變數的任何子表達式，並且歸約其實際參數值是已知的函式套用。在有副作用存在的時候，完全部分求值可能產生未預期的結果，支持部分求值的系統趨向只把它用於函式內“純”表達式(沒有副作用的表達式)。

非嚴格求值

在“非嚴格求值”中，不求值給函式的實際參數，除非它們在函式體內實際上被用到了。

在邱奇編碼下，運算元的惰性求值映射到了函式的非嚴格求值；為此，非嚴格求值有時也叫做“惰性求值”。布爾表達式在很多語言中使用惰性求值；在這種上下文中它通常叫做短路求值。條件表達式也通常使用惰性求值，但出於不同的原因。

正常次序 (Normal order)

“正常次序”(或“最左最外”)求值是總是歸約的最外可歸約式，在求值函式的實際參數之前套用函式的求值策略。它不同於傳名調用，傳名調用不進入未套用的函式體內求值。

傳名調用 (Call by name)

在“傳名調用”求值中，根本就不求值給函式的實際參數 — 而是使用避免捕獲代換把函式的實際參數直接代換入函式體內。如果實際參數在函式的求值中未被用到，則它永不被求值；如果這個實際參數使用多次，則它每次都被重新求值。(參見Jensen設備。)

傳名調用求值超過傳值調用求值的優點是傳名調用求值在一個值存在的時候總是生成這個值，而傳名調用可能不終止如果這個函式的實際參數是求值這個函式所不需要的不終止計算。反過來說，在函式的實際參數會用到的時候傳名調用就非常慢了，這是因為實踐中幾乎總是要使用如thunk這樣的機制。

傳名調用求值很少直接實現，但是經常用於程式和程式語言的理論性質的思考中。帶有傳名調用語義的現實世界中的語言趨向使用傳需求調用求值。傳名調用是ALGOL 60中的預設求值。

傳需求調用 (Call by need)

“傳需求調用”是傳名調用的記憶化版本，如果“函式的實際參數被求值了”，這個值被存儲起來已備後續使用。在“純”(無副作用)設定下，這產生同傳名調用一樣的結果；當函式實際參數被使用兩次或更多次的時候，傳需求調用總是更快。

因為表達式的求值可能出現在計算內任意遠的地方，使用傳需求調用的語言一般不支持計算效果(比如mutation)除非通過使用Monad。這消除了其值變更先於它們的延遲求值的變數的任何未預期行為。

Haskell是最周知的使用傳需求調用求值的語言。

傳宏展開調用

“傳宏展開調用”類似於傳名調用，但是使用了文本代換而不是避免捕獲代換。如果不小心的使用，宏代換可能導致變數捕獲並導致不希望的行為。衛生宏通過檢查並替換不是形式參數的陰影變數避免了這個問題。

非確定性策略

完全 β-歸約

在“完全 β-歸約”下，任何函式套用都可以在任何時候歸約(是避免捕獲代換把函式的實際參數代換如函式內)。這甚至可以在未套用的函式體內進行。

傳預期調用

“傳預期調用”(或“並行傳名調用”)類似於傳名調用，除了這個函式的實際參數的求值可能並行於函式體的求值(而非只在用到的時候)。兩個執行執行緒在函式體的求值中需要這個實際參數的時候同步；如果這個實際參數永不用到，實際參數的執行緒可以殺死。

最優求值

“最優求值”是傳需求調用的另一個變體，在其中函式的實際參數部分的求值一段時間(這可在運行時間調整)，此後求值退出使用傳需求調用套用函式。這種方式避免了傳需求調用的某些運行時間代價，而仍保持了想要的終止特徵。

參見

• Beta範式
• Lambda 演算
• 參數 (計算機科學)