惰性求值

在程式語言理論中,惰性求值(英語:Lazy Evaluation),又譯為惰性計算、懶惰求值,也稱為傳需求調用(call-by-need),是一個計算機編程中的一個概念,它的目的是要最小化計算機要做的工作。它有兩個相關而又有區別的含意,可以表示為“延遲求值”和“最小化求值”,本條目專注前者,後者請參見最小化計算條目。除可以得到性能的提升外,惰性計算的最重要的好處是它可以構造一個無限的數據類型。

簡介

在程式語言理論中, 惰性求值(英語:Lazy Evaluation),又譯為 惰性計算懶惰求值,也稱為 傳需求調用(call-by-need),是一個計算機編程中的一個概念,它的目的是要最小化計算機要做的工作。它有兩個相關而又有區別的含意,可以表示為“延遲求值”和“最小化求值”,本條目專注前者,後者請參見最小化計算條目。除可以得到性能的提升外,惰性計算的最重要的好處是它可以構造一個無限的數據類型。

惰性求值的相反是及早求值,這是一個大多數程式語言所擁有的普通計算方式。

延遲求值

延遲求值特別用於函式式程式語言中。在使用延遲求值的時候,表達式不在它被綁定到變數之後就立即求值,而是在該值被取用的時候求值,也就是說,語句如 x:=expression;(把一個表達式的結果賦值給一個變數)明顯的調用這個表達式被計算並把結果放置到 x中,但是先不管實際在 x中的是什麼,直到通過後面的表達式中到 x的引用而有了對它的值的需求的時候,而後面表達式自身的求值也可以被延遲,最終為了生成讓外界看到的某個符號而計算這個快速增長的依賴樹。

某些程式語言默認進行惰性求值(如Miranda和Haskell),另一些語言提供函式或特殊語法來延遲求值(如Scheme的delay或force)。

延遲求值的一個好處是能夠建立可計算的無限列表而沒有妨礙計算的無限循環或大小問題。例如,可以建立生成無限斐波那契數列表的函式(經常叫做“流”)。第 n個斐波那契數的計算僅是從這個無限列表上提取出這個元素,它只要求計算這個列表的前n個成員。

例如,在Haskell中,斐波納契數的列表可以寫為

在Haskell語法中,":"向列表頭部添加一個元素,tail返回去掉第一個元素的一個列表,而zipWith使用指定的函式(這裡是加法)來組合兩個列表的對應元素生成第三個列表。

假定編程者是仔細的,只有生成特定結果所需要的值才被求值。但是特定計算可能導致程式嘗試對無限數目個元素進行求值;例如,求列表的長度或使用fold運算對列表的元素求和將導致程式不能終止或耗盡記憶體。

語言實現

C++

在典型的大規模計算(如矩陣運算)中,並不是所有的結果值都是必須求出的,很多結果值並沒有被用到。因此,C++中實現延遲求值也是現實需求。一般把運算符函式函式重載,返回一個對象保存了計算所需的各種信息(如實參)等。例如,對矩陣加法的延遲求值:

參見

•組合子邏輯

•柯里化

•λ演算

•極小化求值

•求值策略

相關詞條

熱門詞條

聯絡我們