求值策略

本頁使用了標題或全文手工轉換
維基百科，自由的百科全書
求值策略

在計算機科學中，求值策略（英語：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=81224673」