維基百科

求值策略

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

嚴格求值

編輯

在「嚴格求值」（Strict evaluation）中，給函數的實際參數總是在應用這個函數之前求值。

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

應用次序

編輯

「應用次序」（Applicative order）（或「最左最內」）求值稱呼函數的實際參數按可歸約表達式的後序遍歷從左至右的求值的策略。不像傳值呼叫，應用次序求值儘可能的在應用函數之前歸約函數體內的項。

傳值呼叫

編輯

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

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

傳參照呼叫

編輯

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

很多語言支援某種形式的傳參照呼叫，但是很少有語言預設使用它。FORTRAN II 是一種早期的傳參照呼叫語言。一些語言如C++、PHP、Visual Basic .NET、C#和REALbasic預設使用傳值呼叫，但是提供一種傳參照的特別語法。

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

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

例：C用指標模擬的傳參照呼叫 

void modify(int p, int* q, int* r) {
    p = 27; // passed by value: only the local parameter is modified
    *q = 27; // passed by value or reference, check call site to determine which
    *r = 27; // passed by value or reference, check call site to determine which
}

int main() {
    int a = 1;
    int b = 1;
    int x = 1;
    int* c = &x;
    modify(a, &b, c); // a is passed by value, b is passed by reference by creating a pointer,
                    // c is a pointer passed by value
                    // b and x are changed
    return 0;
}

傳共用對象呼叫

編輯

傳共用對象呼叫（Call by sharing）的方式由Barbara Liskov命名[1]，並被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更加簡單。

傳復件-恢復呼叫

編輯

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

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

當參照未初始化就傳遞給被呼叫者的時候，這種求值策略可以叫「傳結果呼叫」。

部分求值

編輯

更多資訊：柯里化

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

非嚴格求值

編輯

在「非嚴格求值」（Non-strict evaluation）中，不求值給函數的實際參數，除非它們在函數體內實際上被用到了。

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

正常次序

編輯

「正常次序」（Normal order）（或「最左最外」）求值是總是歸約的最外可歸約式，在求值函數的實際參數之前應用函數的求值策略。它不同於傳名呼叫，傳名呼叫不進入未應用的函數體內求值。

傳名呼叫

編輯

在「傳名呼叫」（Call by name）求值中，根本就不求值給函數的實際參數——而是使用避免擷取代換把函數的實際參數直接代換入函數體內。如果實際參數在函數的求值中未被用到，則它永不被求值；如果這個實際參數使用多次，則它每次都被重新求值。（參見Jensen裝置。）

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

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

傳需求呼叫

編輯

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

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

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

傳巨集展開呼叫

編輯

「傳巨集展開呼叫」（Call by macro expansion）類似於傳名呼叫，但是使用了文字代換而不是避免擷取代換。如果不小心的使用，巨集代換可能導致變數擷取並導致不希望的行為。衛生巨集通過檢查並替換不是形式參數的陰影變數避免了這個問題。

非確定性策略

編輯

非確定性策略（Nondeterministic strategies）包括：

完全β歸約

編輯

在「完全β歸約」（Full β-reduction）下，任何函數應用都可以在任何時候歸約（是避免擷取代換把函數的實際參數代換如函數內）。這甚至可以在未應用的函數體內進行。

傳預期呼叫

編輯

「傳預期呼叫」（Call by future）（或「並列傳名呼叫」）類似於傳名呼叫，除了這個函數的實際參數的求值可能並列於函數體的求值（而非只在用到的時候）。兩個執行線程在函數體的求值中需要這個實際參數的時候同步；如果這個實際參數永不用到，實際參數的線程可以殺死。

最佳求值

編輯

「最佳求值」（Optimistic evaluation）是傳需求呼叫的另一個變體，在其中函數的實際參數部分的求值一段時間（這可在執行時間調整），此後求值退出使用傳需求呼叫應用函數。這種方式避免了傳需求呼叫的某些執行時間代價，而仍保持了想要的終止特徵。

參見

編輯

參照

編輯
  1. ^ Liskov, Barbara; Atkinson, Russ; Bloom, Toby; Moss, Eliot; Schaffert, Craig; Scheifler, Craig; Snyder, Alan. CLU Reference Manual (PDF). Laboratory for Computer Science. Massachusetts Institute of Technology. October 1979 [2011-05-19]. （原始內容 (PDF)存檔於2006-09-22）. 

外部連結

編輯
取自 "https://zh.wikipedia.org/w/index.php?title=求值策略&oldid=82783017"