跳至內容

惰性求值

維基百科,自由的百科全書

程式語言理論中,惰性求值(英語:Lazy Evaluation),又譯為惰性計算懶惰求值,也稱為傳需求調用(call-by-need),是計算機編程中的一個概念,目的是要最小化計算機要做的工作。惰性計算的最重要的好處是它可以在空間複雜度上得到極大的優化,從而可以輕易構造一個無限大的數據類型

惰性求值的相反是及早求值,這是一個大多數編程語言,如C語言,所使用的缺省計算方式。

由於翻譯問題,該詞在不同語境下有兩個相關而又有區別的含意,可以表示為「延遲求值」和「最小化求值」,本條目主要內容為延遲求值,後者請參見最小化計算條目。

延遲求值

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

某些編程語言默認進行惰性求值(如MirandaHaskell),另一些語言提供函數或特殊語法來延遲求值(如Schemedelayforce)。

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

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

  fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

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

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

語言實現

C++

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

struct matrix{
    double values[100][100]  ;
    double* operator[](int i){return values[i];}
};

struct matrix_add {
   mutable struct rowEntry{ 
       double operator [](int k){
           matrix_add* pthis=(matrix_add*)this;
           return (pthis->a)[_currentRow][k]+(pthis->b)[_currentRow][k];
        }
       void setRow(int v){_currentRow=v;}
   private:
       int _currentRow;
   } _rowEntry;
   matrix_add(matrix & a, matrix & b) : a(a), b(b) { }
   rowEntry& operator[](int i)const {
       _rowEntry.setRow(i); 
       return _rowEntry;
    }
private:
    matrix & a;
    matrix  & b;
};

matrix_add operator +(matrix & a, matrix & b) {
    return matrix_add(a, b);
}

int main ()
{
    matrix A,B;
    A[3][4]=101; B[3][4]=102;
    matrix_add R=A+B;
    int result = R[3][4];
    return 0;
}

參閲

外部連結