遅延評価

プログラミング言語理論において、遅延評価またはcall-by-need [ ^1]とは、式の評価をその値が必要になるまで遅延させ（非厳密な評価）、また繰り返し評価を回避する（共有の使用により）評価戦略である。^{[2] [3]}

遅延評価の利点は次のとおりです。

• 制御フロー(構造) をプリミティブではなく抽象として定義する機能。
• 潜在的に無限の データ構造を定義する機能。これにより、一部のアルゴリズムをより簡単に実装できます。
• 一部の要素がエラーである部分的に定義されたデータ構造を定義する機能。これにより、迅速なプロトタイピングが可能になります。

遅延評価は、 Jon BentleyのWriting Efficient Programsで説明されているように、メモ化と組み合わせられることがよくあります。^[4]関数の値が特定のパラメーターまたはパラメーター セットに対して計算された後、その結果はそれらのパラメーターの値でインデックス付けされたルックアップ テーブルに格納されます。次に関数が呼び出されると、テーブルが参照され、そのパラメーター値の組み合わせの結果がすでに利用可能かどうかが判断されます。利用可能であれば、格納された結果がそのまま返されます。そうでない場合は、関数が評価され、再利用のために別のエントリがルックアップ テーブルに追加されます。

遅延評価は、演算の順序が不確定になるため、例外処理や入出力などの命令型機能と組み合わせるのが困難です。

遅延評価の反対は、積極的評価であり、厳密な評価とも呼ばれます。積極的評価は、ほとんどの^[定量化] プログラミング言語で採用されている評価戦略です。

遅延評価は、クリストファー・ワズワースによってラムダ計算に導入されました。 ^[5]プログラミング言語では、ピーター・ヘンダーソンとジェームズ・H・モリス^[6]、ダニエル・P・フリードマンとデビッド・S・ワイズ[ ^7]によって独立に導入されました。^[8]

遅延評価は、特に関数型プログラミング言語で使用されます。遅延評価を使用する場合、式は変数にバインドされるとすぐに評価されるのではなく、評価者が式の値を生成するよう強制されたときに評価されます。つまり、 などの文x = expression;(つまり、式の結果を変数に割り当てる) は、明らかに式を評価して結果を に格納することを要求しますxが、 に実際に何が入っているかは、評価自体を延期できる後の式でxへの参照を介してその値が必要になるまで無関係ですx。ただし、最終的には、急速に成長する依存関係のツリーが整理され、外部から見える別のシンボルではなく、あるシンボルが生成されます。^[9]

遅延評価では、制御構造をプリミティブやコンパイル時のテクニックとしてではなく、通常通りに定義することができます。たとえば、if-then-elseや短絡評価演算子を定義できます。^{[10] [11]}

ifThenElse真b c = b ifThenElse偽b c = c     
     

-- または
True || b = True False || b = b    
    

-- そして
True && b = b False && b = False    
    

これらは通常のセマンティクスを持ちます。つまり、 は(a) を評価し、(a) が true と評価された場合に限り (b) を評価し、そうでない場合は (c) を評価します。つまり、(b) または (c) のどちらか 1 つが評価されます。同様に、 については、簡単な部分がTrue を返す場合、多くの作業式を回避できます。最後に、 を評価するときにSafeToTryがfalseの場合、Expressionの評価は試行されません。 ifThenElse a b cEasilyComputed || LotsOfWorkSafeToTry && Expression

逆に、熱心な言語では、上記の の定義は、(a) の値に関係なく、(a)、(b)、(c) を評価します。これは、(b) または (c)に副作用があったり、計算に時間がかかったり、エラーが発生したりするため、望ましい動作ではありません。熱心な言語では、ユーザー定義の遅延制御構造を関数として導入することが通常可能ですが、熱心な評価のための言語の構文から逸脱する可能性があります。多くの場合、関係するコード本体は、呼び出されたときにのみ実行されるように、関数値でラップする必要があります。 ifThenElse a b c

遅延評価の利点は、無限ループや計算に干渉するサイズの問題なしに計算可能な無限リストを作成できる点です。実際の値は必要なときにのみ計算されます。たとえば、フィボナッチ数列の無限リスト（ストリームと呼ばれることが多い）を作成する関数を作成できます。n番目のフィボナッチ数の計算は、無限リストからその要素を抽出するだけであり、リストの最初のnメンバーのみの評価を強制します。^{[12] [13]}

たとえば、Haskellの次の簡単なプログラムを見てみましょう。

numberFromInfiniteList :: Int -> Int numberFromInfiniteList n =無限大!! n - 1ただし無限大= [ 1 .. ]    
        
       

main = $ numberFromInfiniteList 4を印刷     

関数numberFromInfiniteListでは、 infinityの値は無限の範囲ですが、実際の値 (より具体的には、特定のインデックスの特定の値) が必要になるまでリストは評価されず、必要な場合 (つまり、目的のインデックスまで) のみ評価されます。プログラマが注意していれば、プログラムは正常に完了します。ただし、特定の計算では、プログラムが無限の数の要素を評価しようとする場合があります。たとえば、リストの長さを要求したり、リストの要素をfold 操作で合計しようとすると、プログラムが終了しないか、メモリ不足になります。

別の例として、すべてのフィボナッチ数のリストはプログラミング言語Haskellで次のように記述できます。^[13]

 fibs = 0 : 1 : zipWith ( + ) fibs (末尾のfibs )          

Haskellの構文では、" :"はリストの先頭に要素を追加し、tail最初の要素のないリストを返し、zipWith指定された関数（この場合は加算）を使用して2つのリストの対応する要素を結合して3番目のリストを生成します。^[12]

コンピュータのウィンドウシステムでは、画面への情報の描画は、可能な限り最後の瞬間に表示コードを駆動する公開イベントによって駆動されます。これにより、ウィンドウシステムは不必要な表示コンテンツの更新の計算を回避します。^[14]

現代のコンピュータシステムにおける怠惰のもう一つの例は、コピーオンライトページ割り当てまたはデマンドページングであり、メモリに格納された値が変更されたときにのみメモリが割り当てられます。^[14]

遅延は、高パフォーマンスのシナリオで役立ちます。例としては、Unix mmap関数があります。これは、ディスクからのページを要求に応じてロードする機能を提供し、実際にアクセスされたページのみがメモリにロードされ、不要なメモリは割り当てられません。

MATLABはコピーオンエディットを実装しており、コピーされた配列は内容が変更された場合にのみ実際のメモリストレージが複製されるため、コピー操作中ではなく後で要素を更新するとメモリ不足エラーが発生する可能性があります。^[15]

必要時呼び出しでラムダ項を縮小するためのベータ縮小の数は、値呼び出しまたは名前呼び出しの縮小に必要な数より大きくはなりません。^{[16] [17]}また、特定のプログラムではステップ数がはるかに少なくなる場合があります。たとえば、チャーチ数値を使用する特定のラムダ項ファミリでは、値呼び出しでは無限のステップ数（つまり、完了しない）が必要で、名前呼び出しでは指数関数的なステップ数が必要ですが、必要時呼び出しでは多項式数しか必要ありません。必要時呼び出しには、作業を繰り返さない（値呼び出しと同様）、不必要な作業をしない（名前呼び出しと同様）という 2 つの最適化があります。^[18]遅延評価では、必要なときに値が作成されるため、メモリ フットプリント の削減にもつながります。 ^[19]

実際には、遅延評価は、積極的評価と比較して、重大なパフォーマンスの問題を引き起こす可能性があります。たとえば、現代のコンピュータアーキテクチャでは、計算を遅らせて後で実行すると、すぐに実行するよりも遅くなります。これは、厳密性分析によって軽減できます。^[18]遅延評価は、評価されていない式によるメモリリークを引き起こす可能性もあります。 ^{[20] [21]}

プログラミング言語の中には、式の評価をデフォルトで遅延させるものもあれば、評価を遅延させる関数や特別な構文を提供するものもあります。MirandaとHaskellでは、関数の引数の評価はデフォルトで遅延されます。他の多くの言語では、特別な構文 (Scheme の " " と " "、OCaml の " " と " " など) を使用して計算を明示的に中断するか、より一般的には、式をthunkでラップすることで、評価を遅延させることができます。このように明示的に遅延された評価を表すオブジェクトは、遅延フューチャーと呼ばれます。Rakuはリストの遅延評価を使用するため、無限リストを変数に割り当てて関数の引数として使用することができますが、Haskell や Miranda とは異なり、Raku は算術演算子と関数の遅延評価をデフォルトで使用しません。^[9]delayforcelazyLazy.force

Haskell などの遅延プログラミング言語では、デフォルトでは要求されたときだけ式を評価しますが、場合によってはコードをより積極的に評価したり、逆に、より積極的に評価した後に再びより遅延評価にしたりすることができます。これは、評価を強制する何かを明示的にコーディングする (これにより、コードがより積極的に評価される可能性があります) か、そのようなコードを避ける (これにより、コードがより遅延評価される可能性があります) ことによって実行できます。厳密な評価は通常、積極的に評価されることを意味しますが、技術的にはこれらは異なる概念です。

ただし、一部のコンパイラには、厳密性分析と呼ばれる最適化が実装されており、場合によっては、コンパイラが値が常に使用されると推測できます。このような場合、厳密性分析によって厳密な評価が強制されるため、特定の値を強制するかどうかのプログラマの選択は無関係になる可能性があります。

Haskell では、コンストラクタフィールドを厳格としてマークすると、その値が常に即時に要求されることになります。seq関数は、値を即時に要求してそれを渡すためにも使用できます。これは、コンストラクタ フィールドを通常遅延させる必要がある場合に便利です。ただし、これらのテクニックはどちらも再帰的な厳格性を実装していません。そのために、と呼ばれる関数がdeepSeq考案されました。

また、 Haskell 98のパターンマッチングはデフォルトで厳密なので、~それを遅延させるには修飾子を使用する必要があります。^[22]

Javaでは、値が必要なときに評価するメソッドを持つオブジェクトを使用することで遅延評価を行うことができます。このメソッドの本体には、この評価を実行するために必要なコードが含まれている必要があります。Java SE8でラムダ式が導入されて以来、Javaはこれに対するコンパクトな表記法をサポートしています。次の例のジェネリックインターフェースは、遅延評価のフレームワークを提供します。^{[23] [24]}

インターフェース Lazy < T > { T eval (); } 
     

Lazyそのメソッドを持つインターフェースは、ライブラリ内のそのメソッドを持つインターフェースeval()と同等である。^{[25] [26] : 200}Supplierget()java.util.function

インターフェースを実装する各クラスはメソッドLazyを提供する必要があり、クラスのインスタンスはメソッドが遅延評価を実行するために必要な任意の値を保持できます。たとえば、 2 ¹⁰evalを遅延計算して出力する次のコードを考えてみます。

Lazy < Integer > a = () -> 1 ; for ( int i = 0 ; i < 10 ; i ++ ) { Lazy < Integer > b = a ; a = () - > b.eval ( ) + b.eval ( ) ; } System.out.println ( " a = " + a.eval ( ) ) ;     
         
       
          

  

上記では、変数aは最初、ラムダ式によって作成された遅延整数オブジェクトを参照します。このラムダ式を評価することは、1を返すevalメソッドを実装する匿名クラスの新しいインスタンスを構築することに似ています^[a]。 () -> 1Lazy<Integer>

ループの各反復は、ループ内のラムダ式を評価することによって作成された新しいオブジェクトにa をリンクします。これらの各オブジェクトは、別の遅延オブジェクトbへの参照を保持し、 2 回呼び出して合計を返すevalメソッドを持ちます。変数bは、ラムダ式内から参照される変数が事実上 final であるという Java の要件を満たすためにここで必要です。 b.eval()

これは、遅延整数の実装では、以前のeval呼び出しの結果をメモ化しないため、非効率的なプログラムです。また、かなりの自動ボックス化とアンボックス化も伴います。明らかでないかもしれませんが、ループの最後で、プログラムは11 個のオブジェクトのリンク リストを構築し、結果の計算に含まれる実際の追加はすべて、コードの最終行の の呼び出しに応じて行われます。この呼び出しは、必要な追加を実行するためにリスト を再帰的に走査します。a.eval()

遅延オブジェクトをメモ化するJavaクラスは次のように構築できます。^{[23] [24]}

class  Memo < T > implements Lazy < T > { private Lazy < T > lazy ; // 遅延式、eval により null に設定されるprivate T memo ; // 前の値のメモ   
        
       

    パブリックMemo ( Lazy < T > lazy ) { this . lazy = lazy ; }   
          
    

    public T eval () { if ( lazy != null ) { memo = lazy . eval (); lazy = null ; } return memo ; } }   
            
              
              
        
         
    

これにより、前の例をはるかに効率的に書き直すことができます。元の例は反復回数の指数関数的な時間で実行されましたが、メモ化されたバージョンは線形時間で実行されます。

Lazy < Integer > a = () -> 1 ; for ( int i = 0 ; i < 10 ; i ++ ) { Lazy < Integer > b = a ; a = new Memo < Integer > ( () - > b.eval ( ) + b.eval ( ) ); } System.out.println ( " a = " + a.eval ( ) ) ;     
         
       
           

  

Java のラムダ式は単なる構文上の糖衣です。ラムダ式で記述できるものはすべて、インターフェースを実装する匿名内部クラスのインスタンスを作成するための呼び出しとして書き直すことができます。 ^[a]また、匿名内部クラスの使用はすべて、名前付き内部クラスを使用して書き直すことができ、名前付き内部クラスは最も外側のネスト レベルに移動できます。

JavaScriptでは、ジェネレーターを使用して遅延評価をシミュレートできます。たとえば、すべてのフィボナッチ数のストリームは、メモ化を使用して次のように記述できます。

/** 
* ジェネレータ関数は、遅延評価を具体化するジェネレータ オブジェクトを返します。
* @return {!Generator<bigint>} 整数の非 null ジェネレータ。
*/ 
function * fibonacciNumbers () { let memo = [ 1n , - 1n ]; // 初期状態を作成します (例: 「negafibonacci」数のベクトル) while ( true ) { // 無限に繰り返しますmemo = [ memo [ 0 ] + memo [ 1 ], memo [ 0 ]]; // 評価ごとに状態を更新しますyield memo [ 0 ]; // 次の値を生成し、再開されるまで実行を一時停止します} }  
         
       
              
          
    


let stream = fibonacciNumbers (); // 遅延評価された数値ストリームを作成します。let first10 = Array . from ( new Array ( 10 ), () => stream . next (). value ); // 最初の 10 個の数値のみを評価します。console . log ( first10 ); // 出力は [0n, 1n, 1n, 2n, 3n, 5n, 8n, 13n, 21n, 34n] です。    
        
 

Python 2.xではrange()関数^[27]は整数のリストを計算します。最初の代入文が評価されたときにリスト全体がメモリに保存されるので、これは即時評価の例です。

>>> r  =  range ( 10 ) 
>>> print  r 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 
>>> print  r [ 3 ] 
3

Python 3.xではrange()関数^[28]はリストの要素を必要に応じて計算するジェネレータを返します。要素は必要なときだけ生成されます（例えば、print(r[3])次の例でが評価されるとき）。したがって、これは遅延評価または延期評価の例です。

>>> r  =  range ( 10 ) 
>>> print ( r ) 
range(0, 10) 
>>> print ( r [ 3 ]) 
3

この遅延評価への変更により、完全に参照されることのない大きな範囲の実行時間が節約され、一度に 1 つまたは少数の要素のみが必要となる大きな範囲のメモリ使用量が節約されます。

xrange()Python 2.x では、要求に応じて範囲内の数値を生成するオブジェクトを返す という関数を使用できます。 の利点はxrange、生成されたオブジェクトが常に同じ量のメモリを占有することです。

>>> r  =  xrange ( 10 ) 
>>> print ( r ) 
xrange(10) 
>>> lst  =  [ x  for  x  in  r ] 
>>> print ( lst ) 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

バージョン 2.2 以降、Python はタプルやリストのシーケンスとは異なり、イテレータ (遅延シーケンス) を実装することで遅延評価を実現します。たとえば (Python 2):

>>> numbers  =  range ( 10 ) 
>>> iterator  =  iter ( numbers ) 
>>> numbers [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]を出力>>>  iterator < 0xf7e8dd4c の listiterator オブジェクト>を出力>>> iterator . next () 0 を出力

 

 

上記の例では、リストは呼び出されたときに評価されますが、反復子の場合は、必要に応じて最初の要素「0」が印刷されます。

.NETフレームワークでは、クラスを使用して遅延評価を行うことができます。^[29] F#では、キーワードを使用してクラスを簡単に利用できますが、メソッドは評価を強制します。遅延評価の組み込みサポートを提供する ような特殊なコレクションもあります。System.Lazy<T>lazyforceMicrosoft.FSharp.Collections.Seq

fibonacci = Seq . unfold ( fun ( x , y ) -> Some ( x , ( y , x + y ))) ( 0I , 1I ) fibonacci |> Seq . nth 1000とします。             
   

C# および VB.NET では、クラスが直接使用されます。 System.Lazy<T>

public int Sum () { int a = 0 ; int b = 0 ; Lazy < int > x = new Lazy < int > (() => a + b ) ; a = 3 ; b = 5 ; return x.Value ; // 8を返す}  

       
        
            
      
      
      

あるいは、より実用的な例を挙げてみましょう。

// n 番目のフィボナッチ数の再帰計算
public int Fib ( int n ) { return ( n == 1 ) ? 1 : ( n == 2 ) ? 1 : Fib ( n - 1 ) + Fib ( n - 2 ); }   

                


public void Main () { Console.WriteLine ( "どのフィボナッチ数を計算しますか?" ); int n = Int32.Parse ( Console.ReadLine ( ) ); Lazy < int > fib = new Lazy < int > ( () = > Fib ( n )); // 関数は準備されていますが、実行されていません bool execute; if ( n > 100) { Console.WriteLine ( "これには時間がかかる場合があります。この大きな数を本当に計算しますか? [y/n]" ); execute = ( Console.ReadLine () == "y" ); } else execute = true ; if ( execute ) Console.WriteLine ( fib.Value ) ; //数は必要な場合にのみ計算されます}  

    
        
           
      
       
    
        
             
    
       
    
       

別の方法としては、次のyieldキーワードを使用します。

// 積極的な評価
public IEnumerable < int > Fibonacci ( int x ) { IList < int > fibs = new List < int > ();   

        

    int prev = - 1 ; int next = 1 ; for ( int i = 0 ; i < x ; i ++ ) { int sum = prev + next ; prev = next ; next = sum ; fibs.Add ( sum ) ; } return fibs ; }​   
       
            
    
             
          
          
         
    
     


// 遅延評価
public IEnumerable < int > LazyFibonacci ( int x ) { int prev = - 1 ; int next = 1 ; for ( int i = 0 ; i < x ; i ++ ) { int sum = prev + next ; prev = next ; next = sum ; yield return sum ; } }   

       
       
            
    
             
          
          
          
    

• 組み合わせ論理
• カレー作り
• データフロー
• 熱心な評価
• 関数型プログラミング
• 未来と約束
• ジェネレータ（コンピュータプログラミング）
• グラフ縮小
• インクリメンタル コンピューティング- 入力が変更された場合にのみ計算が繰り返される関連概念。遅延評価と組み合わせることができます。
• ラムダ計算
• 遅延初期化
• 先読み
• 非厳密なプログラミング言語
• 通常の注文評価
• 短絡評価（最小限）

• Friedman, DP ; Wise, David S. (1976)。S. Michaelson、R. Milner (編)。「Cons は引数を評価してはならない」(PDF)。オートマトン言語とプログラミング第 3 回国際コロキウム。エディンバラ大学出版局。
• Henderson, Peter; Morris, James H. (1976)。 「怠惰な評価者」。プログラミング言語の原則に関する第 3 回 ACM SIGACT-SIGPLAN シンポジウム議事録 - POPL '76。pp.  95– 103。doi :10.1145/800168.811543。S2CID 1228296  。
• Hudak , Paul (1989 年 9 月)。 「関数型プログラミング言語の概念、進化、および応用」。ACMコンピューティング調査。21 (3): 383– 385。doi :10.1145/72551.72554。S2CID  207637854。
• Launchbury, John (1993)。 「遅延評価のための自然なセマンティクス」。プログラミング言語の原理に関する第 20 回 ACM SIGPLAN-SIGACT シンポジウム議事録 - POPL '93。pp.  144– 154。doi : 10.1145 /158511.158618。ISBN 0897915607. S2CID  14945994。
• レイノルズ、ジョン C. (1998)。プログラミング言語の理論。ケンブリッジ大学出版局。ISBN 9780521594141. 2016年2月23日閲覧。
• Wadsworth, Christopher P. (1971)。ラムダ計算の意味論と語用論（博士論文）。オックスフォード大学。

• Nemerleの遅延評価マクロ
• C++言語のBoostライブラリにおけるラムダ計算
• クラスを使用して関数クロージャを実装するスタイルでコードを記述することにより、ANSI C++で遅延評価を実行します。