求值策略中惰性求值的應用

《求值策略中惰性求值的應用》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、求值策略中惰性求值的應用摘要：求值策略有很多種，本文先對每種求值策略加以簡述，然后針對惰性求值進行詳細分析，并通過9個實例來說明惰性求值的使用特點，最后總結(jié)其優(yōu)缺點，分析實用性。關鍵字：求值策略;惰性求值;函數(shù)式編程;在計算機科學中，求值策略(Evaluationstrategy)是確定編程語言中表達式求值的一組（通常確定性的）規(guī)則。重點的位于函數(shù)或算子上——求值策略定義何時和以何種次序為函數(shù)的實際參數(shù)求值，什么時候把它們代換入函數(shù)，和代換以何種形式發(fā)生。經(jīng)常用研究函數(shù)的形式系統(tǒng)λ演算來建模求值策略，這里它們通常叫做歸約策略。求值策略分為兩大基本類，基于如何處理函數(shù)的實際參數(shù)，

2、分為嚴格的和非嚴格的。一個語言可以組合多種求值策略，例如C++組合了傳值調(diào)用和傳引用調(diào)用。多數(shù)語言對布爾表達式和if語句使用某種形式的非嚴格求值。1各種求值策略簡介首先，求值策略分三大部分，嚴格求值、非嚴格求值和非確定性策略。其中嚴格求值包括應用次序、傳值調(diào)用、傳引用調(diào)用和傳復件-恢復調(diào)用，非嚴格求值包括正常次序、傳名調(diào)用、傳需求調(diào)用、傳宏展開調(diào)用，非確定性策略包括完全β-歸約、傳預期調(diào)用、最優(yōu)求值。1.1嚴格求值(Strictevaluation)在“嚴格求值”中，給函數(shù)的實際參數(shù)總是在應用這個函數(shù)之前求值。在邱奇編碼下，算子的熱情求值映射到了函數(shù)的嚴格求值；為此嚴格求值有時

3、叫做“熱情求值”。多數(shù)現(xiàn)存編程語言對函數(shù)使用嚴格求值。1.1.1?應用次序(Applicativeorder)“應用次序”(或“最左最內(nèi)”)求值稱呼函數(shù)的實際參數(shù)按可歸約表達式的后序遍歷從左至右的求值的策略。不像傳值調(diào)用，應用次序求值盡可能的在應用函數(shù)之前歸約函數(shù)體內(nèi)的項。1.1.2傳值調(diào)用(Callbyvalue)“傳值調(diào)用”求值是最常見的求值策略，用于廣泛使用的語言如?C?和?Scheme?中。在傳值調(diào)用中，求值實際參數(shù)表達式，并把結(jié)果值綁定到在函數(shù)中對應的變量上(20/20通常通過避免捕獲代換，或把值復制到新的內(nèi)存區(qū)域中)。如果函數(shù)或過程能夠把值賦到它的形式參數(shù)，則被賦值

4、的只是局部復件，就是說，在調(diào)用者轄域內(nèi)的傳遞入函數(shù)調(diào)用的任何東西在函數(shù)返回的時候都是未變更的。傳值調(diào)用不是一個單一的求值策略，而是函數(shù)的實際參數(shù)在被傳遞給函數(shù)之前就被求值的求值策略家族。盡管使用傳值調(diào)用的多數(shù)編程語言從左至右的求值函數(shù)的實際參數(shù)，某些語言(比如?OCaml)從右至左的求值函數(shù)和它們的實際參數(shù)，而另一些語言(比如Scheme和C)未指定這種次序(盡管它們保證順序一致性)。1.1.1傳引用調(diào)用(Callbyreference)在“傳引用調(diào)用”求值中，傳遞給函數(shù)的是到它的實際參數(shù)的隱式引用而不是實際參數(shù)值自身。如果函數(shù)能夠修改這樣的形式參數(shù)，則任何改變對于調(diào)用者也是可

5、見的。如果實際參數(shù)表達式是左值(L-value)，則使用它的地址。否則調(diào)用者構(gòu)造一個臨時對象并傳遞到這個對象的引用；在函數(shù)返回的時候丟棄這個對象。某些語言包含引用作為一級值的概念。例如?ML?語言有“ref”構(gòu)造子；C++中的引用也顯式的創(chuàng)建。在這些語言中，“傳引用調(diào)用”可以用來傳遞一個引用值作為給函數(shù)的實際參數(shù)。在包含無限制指針替代或補充引用的語言(比如C)中，“傳地址調(diào)用”是傳引用調(diào)用的變體，這里的引用是無限制指針。1.1.2傳復件-恢復調(diào)用(Callbycopy-restore)“傳復件-恢復調(diào)用”、“傳值-結(jié)果調(diào)用”或“傳值-返回調(diào)用”(在?Fortran?社區(qū)中的術(shù)語

6、)是傳引用調(diào)用的特殊情況，即在傳引用調(diào)用時，向被叫進程所傳遞的引用并非調(diào)用進程原有的引用，而是一個原有引用的復制，即被傳遞的引用與調(diào)用進程沒有關系。傳復件-恢復調(diào)用在這種情況下很重要：如果函數(shù)調(diào)用的一個形式參數(shù)，是可能被其他執(zhí)行線程同時訪問的引用。那么就把這個引用的內(nèi)容復制到一個新創(chuàng)建的引用中，再將這個新創(chuàng)建的、與調(diào)用進程無關的引用傳遞給被叫進程。當被叫進程執(zhí)行結(jié)束、調(diào)用返回的時候，再把這個新引用中更新過的內(nèi)容復制回調(diào)用進程原來的引用中（“恢復”）。傳值-返回調(diào)用的語義在兩個或更多實際參數(shù)相互為別名的時候，也不同于傳引用調(diào)用，就是說它們都指向了調(diào)用者環(huán)境中的同一個變量。在傳引用

7、調(diào)用下，寫其中一個會影響另一個；傳值-返回調(diào)用通過給函數(shù)以獨自的復件來避免了這種情況，但沒有規(guī)定調(diào)用者環(huán)境中的結(jié)果(依賴于哪個別名實際參數(shù)首先被復制回去)。20/20當引用未初始化就傳遞給被調(diào)用者的時候，這種求值策略可以叫“傳結(jié)果調(diào)用”。1.1.1?部分求值(Partialevaluation)在“部分求值”中，求值可以延續(xù)到仍未被應用的函數(shù)體之內(nèi)。求值不包含未綁定變量的任何子表達式，并且歸約其實際參數(shù)值是已知的函數(shù)應用。在有副作用存在的時候，完全部分求值可能產(chǎn)生未預期的結(jié)果，支持部分求值的