[科普中國(guó)]-求值策略

在計(jì)算機(jī)科學(xué)中，求值策略(Evaluation strategy)是確定編程語(yǔ)言中表達(dá)式的求值的一組（通常確定性的）規(guī)則。重點(diǎn)典型的位于函數(shù)或算子上——求值策略定義何時(shí)和以何種次序求值給函數(shù)的實(shí)際參數(shù)，什么時(shí)候把它們代換入函數(shù)，和代換以何種形式發(fā)生。經(jīng)常使用用來(lái)研究函數(shù)的形式系統(tǒng)λ演算來(lái)建模求值策略，這里它們通常叫做歸約策略。求值策略分為兩大基本類，嚴(yán)格的和非嚴(yán)格的，基于如何處理給函數(shù)的實(shí)際參數(shù)。一個(gè)語(yǔ)言可以組合多種求值策略；例如C++組合了傳值調(diào)用和傳引用調(diào)用。多數(shù)語(yǔ)言對(duì)布爾表達(dá)式和if語(yǔ)句使用某種形式的非嚴(yán)格求值。

嚴(yán)格求值在“嚴(yán)格求值”中，給函數(shù)的實(shí)際參數(shù)總是在應(yīng)用這個(gè)函數(shù)之前求值。

在邱奇編碼下，算子的熱情求值映射到了函數(shù)的嚴(yán)格求值；為此嚴(yán)格求值有時(shí)叫做“熱情求值”。多數(shù)現(xiàn)存編程語(yǔ)言對(duì)函數(shù)使用嚴(yán)格求值。

應(yīng)用次序“應(yīng)用次序”(或“最左最內(nèi)”)求值稱呼函數(shù)的實(shí)際參數(shù)按可歸約表達(dá)式的后序遍歷從左至右的求值的策略。不像傳值調(diào)用，應(yīng)用次序求值盡可能的在應(yīng)用函數(shù)之前歸約函數(shù)體內(nèi)的項(xiàng)。

傳值調(diào)用“傳值調(diào)用”求值是最常見(jiàn)的求值策略，C和Scheme這樣差異巨大的語(yǔ)言都在使用。在傳值調(diào)用中實(shí)際參數(shù)被求值，其值被綁定到函數(shù)中對(duì)應(yīng)的變量上（通常是把值復(fù)制到新內(nèi)存區(qū)域）。如果函數(shù)或過(guò)程能把值賦給它的形式參數(shù)，則被賦值的只是局部拷貝 -- 就是說(shuō)，在函數(shù)返回后調(diào)用者作用域里的曾傳給函數(shù)的任何東西都不會(huì)變。

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

傳引用調(diào)用 (在“傳引用調(diào)用”求值中，傳遞給函數(shù)的是它的實(shí)際參數(shù)的隱式引用而不是實(shí)參的拷貝。通常函數(shù)能夠修改這些參數(shù)（比如賦值），而且改變對(duì)于調(diào)用者是可見(jiàn)的。因此傳引用調(diào)用提供了一種調(diào)用者和函數(shù)交換數(shù)據(jù)的方法。傳引用調(diào)用的語(yǔ)言中追蹤函數(shù)調(diào)用的副作用比較難，易產(chǎn)生不易察覺(jué)的bug。

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

在那些使用傳值調(diào)用又不支持傳引用調(diào)用的語(yǔ)言里，可以用引用（引用其他對(duì)象的對(duì)象），比如指針（表示其他對(duì)象的內(nèi)存地址的對(duì)象）來(lái)模擬。C和ML就用了這種方法。這不是一種不同的求值策略（語(yǔ)言本身還是傳值調(diào)用）。它有時(shí)被叫做“傳地址調(diào)用” （call by address）。 這可能讓人不易理解。在C之類不安全的語(yǔ)言里會(huì)引發(fā)解引用空指針之類的錯(cuò)誤。但ML 的引用是類型安全和內(nèi)存安全的。

類似的效果可由傳共享對(duì)象調(diào)用（傳遞一個(gè)可變對(duì)象）實(shí)現(xiàn)。比如Python、Ruby。

傳共享對(duì)象調(diào)用此方式由 Barbara Liskov 命名，并被 Python、Java（對(duì)象類型）、JavaScript、Scheme、OCaml 等語(yǔ)言使用。

與傳引用調(diào)用不同，對(duì)于調(diào)用者而言在被調(diào)用函數(shù)里修改參數(shù)是沒(méi)有影響的。如果要達(dá)成傳引用調(diào)用的效果就需要傳一個(gè)共享對(duì)象，一旦被調(diào)用者修改了對(duì)象，調(diào)用者就可以看到變化（因?yàn)閷?duì)象是共享的，沒(méi)有拷貝）。比如這段Python代碼：

def f(l): l.append(1) l = [2]m = []f(m)print(m)會(huì)輸出[1]而不是[2]。因?yàn)榱斜硎强勺兊?，append方法改變了m。而賦值局部變量l的行為對(duì)外面作用域沒(méi)有影響（在這類語(yǔ)言中賦值是給變量綁定一個(gè)新對(duì)象，而不是改變對(duì)象）。

使用C/C++語(yǔ)言的程序員可能因不能用指針等使函數(shù)返回多個(gè)值而感到不便，但是像Python這樣的語(yǔ)言提供了替代方案：函數(shù)能方便的返回多個(gè)值，比C++11的std::tie更加簡(jiǎn)單。

傳復(fù)件-恢復(fù)調(diào)用“傳復(fù)件-恢復(fù)調(diào)用”、“傳值-結(jié)果調(diào)用”或“傳值-返回調(diào)用”(在Fortran社區(qū)中的術(shù)語(yǔ))是傳引用調(diào)用的特殊情況，即在傳引用調(diào)用時(shí)，向被叫進(jìn)程所傳遞的引用并非調(diào)用進(jìn)程原有的引用，而是一個(gè)原有引用的復(fù)制，即被傳遞的引用與調(diào)用進(jìn)程沒(méi)有關(guān)系。傳復(fù)件-恢復(fù)調(diào)用在這種情況下很重要：如果函數(shù)調(diào)用的一個(gè)形式參數(shù)，是可能被其他執(zhí)行線程同時(shí)訪問(wèn)的引用。那么就把這個(gè)引用的內(nèi)容復(fù)制到一個(gè)新創(chuàng)建的引用中，再將這個(gè)新創(chuàng)建的、與調(diào)用進(jìn)程無(wú)關(guān)的引用傳遞給被叫進(jìn)程。當(dāng)被叫進(jìn)程執(zhí)行結(jié)束、調(diào)用返回的時(shí)候，再把這個(gè)新引用中更新過(guò)的內(nèi)容復(fù)制回調(diào)叫進(jìn)程原來(lái)的引用中（“恢復(fù)”）。

傳值-返回調(diào)用的語(yǔ)義在兩個(gè)或更多實(shí)際參數(shù)相互是別名的時(shí)候也不同于傳引用調(diào)用，就是說(shuō)它們都指向了在調(diào)用者環(huán)境中的同一個(gè)變量。在傳引用調(diào)用下，寫其中一個(gè)會(huì)影響另一個(gè)；傳值-返回調(diào)用通過(guò)給函數(shù)以獨(dú)自的復(fù)件來(lái)避免了這種情況，但沒(méi)有規(guī)定在調(diào)用者環(huán)境中的結(jié)果(依賴于哪個(gè)別名實(shí)際參數(shù)首先被復(fù)制回去)。

當(dāng)引用未初始化就傳遞給被調(diào)用者的時(shí)候，這種求值策略可以叫“傳結(jié)果調(diào)用”。

部分求值更多信息：柯里化

在“部分求值”中，求值可以延續(xù)到仍未被應(yīng)用的函數(shù)體之內(nèi)。求值不包含未綁定變量的任何子表達(dá)式，并且歸約其實(shí)際參數(shù)值是已知的函數(shù)應(yīng)用。在有副作用存在的時(shí)候，完全部分求值可能產(chǎn)生未預(yù)期的結(jié)果，支持部分求值的系統(tǒng)趨向只把它用于函數(shù)內(nèi)“純”表達(dá)式(沒(méi)有副作用的表達(dá)式)。

非嚴(yán)格求值在“非嚴(yán)格求值”中，不求值給函數(shù)的實(shí)際參數(shù)，除非它們?cè)诤瘮?shù)體內(nèi)實(shí)際上被用到了。

在邱奇編碼下，算子的惰性求值映射到了函數(shù)的非嚴(yán)格求值；為此，非嚴(yán)格求值有時(shí)也叫做“惰性求值”。布爾表達(dá)式在很多語(yǔ)言中使用惰性求值；在這種上下文中它通常叫做短路求值。條件表達(dá)式也通常使用惰性求值，但出于不同的原因。

正常次序 (Normal order)“正常次序”(或“最左最外”)求值是總是歸約的最外可歸約式，在求值函數(shù)的實(shí)際參數(shù)之前應(yīng)用函數(shù)的求值策略。它不同于傳名調(diào)用，傳名調(diào)用不進(jìn)入未應(yīng)用的函數(shù)體內(nèi)求值。

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

傳名調(diào)用求值超過(guò)傳值調(diào)用求值的優(yōu)點(diǎn)是傳名調(diào)用求值在一個(gè)值存在的時(shí)候總是生成這個(gè)值，而傳名調(diào)用可能不終止如果這個(gè)函數(shù)的實(shí)際參數(shù)是求值這個(gè)函數(shù)所不需要的不終止計(jì)算。反過(guò)來(lái)說(shuō)，在函數(shù)的實(shí)際參數(shù)會(huì)用到的時(shí)候傳名調(diào)用就非常慢了，這是因?yàn)閷?shí)踐中幾乎總是要使用如thunk這樣的機(jī)制。

傳名調(diào)用求值很少直接實(shí)現(xiàn)，但是經(jīng)常用于程序和編程語(yǔ)言的理論性質(zhì)的思考中。帶有傳名調(diào)用語(yǔ)義的現(xiàn)實(shí)世界中的語(yǔ)言趨向使用傳需求調(diào)用求值。傳名調(diào)用是ALGOL 60中的缺省求值。

傳需求調(diào)用 (Call by need)“傳需求調(diào)用”是傳名調(diào)用的記憶化版本，如果“函數(shù)的實(shí)際參數(shù)被求值了”，這個(gè)值被存儲(chǔ)起來(lái)已備后續(xù)使用。在“純”(無(wú)副作用)設(shè)置下，這產(chǎn)生同傳名調(diào)用一樣的結(jié)果；當(dāng)函數(shù)實(shí)際參數(shù)被使用兩次或更多次的時(shí)候，傳需求調(diào)用總是更快。

因?yàn)楸磉_(dá)式的求值可能出現(xiàn)在計(jì)算內(nèi)任意遠(yuǎn)的地方，使用傳需求調(diào)用的語(yǔ)言一般不支持計(jì)算效果(比如mutation)除非通過(guò)使用Monad。這消除了其值變更先于它們的延遲求值的變量的任何未預(yù)期行為。

Haskell是最周知的使用傳需求調(diào)用求值的語(yǔ)言。

傳宏展開(kāi)調(diào)用“傳宏展開(kāi)調(diào)用”類似于傳名調(diào)用，但是使用了文本代換而不是避免捕獲代換。如果不小心的使用，宏代換可能導(dǎo)致變量捕獲并導(dǎo)致不希望的行為。衛(wèi)生宏通過(guò)檢查并替換不是形式參數(shù)的陰影變量避免了這個(gè)問(wèn)題。

非確定性策略完全 β-歸約在“完全 β-歸約”下，任何函數(shù)應(yīng)用都可以在任何時(shí)候歸約(是避免捕獲代換把函數(shù)的實(shí)際參數(shù)代換如函數(shù)內(nèi))。這甚至可以在未應(yīng)用的函數(shù)體內(nèi)進(jìn)行。

傳預(yù)期調(diào)用“傳預(yù)期調(diào)用”(或“并行傳名調(diào)用”)類似于傳名調(diào)用，除了這個(gè)函數(shù)的實(shí)際參數(shù)的求值可能并行于函數(shù)體的求值(而非只在用到的時(shí)候)。兩個(gè)執(zhí)行線程在函數(shù)體的求值中需要這個(gè)實(shí)際參數(shù)的時(shí)候同步；如果這個(gè)實(shí)際參數(shù)永不用到，實(shí)際參數(shù)的線程可以殺死1。

最優(yōu)求值“最優(yōu)求值”是傳需求調(diào)用的另一個(gè)變體，在其中函數(shù)的實(shí)際參數(shù)部分的求值一段時(shí)間(這可在運(yùn)行時(shí)間調(diào)整)，此后求值退出使用傳需求調(diào)用應(yīng)用函數(shù)。這種方式避免了傳需求調(diào)用的某些運(yùn)行時(shí)間代價(jià)，而仍保持了想要的終止特征。

參見(jiàn)Beta范式

Lambda 演算

參數(shù) (計(jì)算機(jī)科學(xué))

本詞條內(nèi)容貢獻(xiàn)者為:

李嘉騫 - 博士 - 同濟(jì)大學(xué)