Loading article…
プログラミング言語理論では、遅延評価、または必要に応じて呼び出す[ 1 ]は、式の評価をその値が必要になるまで遅らせ（非厳密評価）、繰り返し評価を回避する（共有の使用による）評価戦略である[ 2 ] [ 3 ] 。
遅延評価の利点は以下のとおりです。
遅延評価は、 Jon BentleyのWriting Efficient Programs [ 4 ]で説明されているように、メモ化と組み合わせて使用されることが多い。関数の値が特定のパラメータまたはパラメータセットに対して計算された後、結果はそれらのパラメータの値によってインデックス付けされたルックアップ テーブルに格納される。次にその関数が呼び出されると、テーブルが参照され、そのパラメータ値の組み合わせに対する結果が既に利用可能かどうかが判断される。利用可能であれば、格納された結果がそのまま返される。利用できない場合は、関数が評価され、再利用のために別のエントリがルックアップ テーブルに追加される。
遅延評価は、例外処理や入出力といった命令型プログラミングの機能と組み合わせるのが難しい。なぜなら、操作の順序が不確定になるからである。
遅延評価の反対は、厳密評価とも呼ばれる積極評価です。積極評価は、ほとんどのプログラミング言語で採用されている評価戦略です。
遅延評価はクリストファー・ワズワースによってラムダ計算に導入されました。[ 5 ]プログラミング言語については、ピーター・ヘンダーソンとジェームズ・H・モリス[ 6 ]、およびダニエル・P・フリードマンとデビッド・S・ワイズ[ 7 ] [ 8 ]によってそれぞれ独立に導入されました。
遅延評価は、特に関数型プログラミング言語で使用されます。遅延評価を使用する場合、式は変数に束縛された直後に評価されるのではなく、評価器が式の値を生成することを強制されたときに評価されます。つまり、x = expression;(式の結果を変数に代入する) のようなステートメントは、明らかに式を評価し、結果を に格納することを要求しますxが、実際に に何が入っているかは、後続の式xで への参照を介してその値が必要になるまで関係ありません。xその式自体の評価は遅延される可能性がありますが、最終的には急速に増大する依存関係のツリーが剪定され、外部から見える別のシンボルではなく、あるシンボルが生成されます。[ 9 ]
遅延評価は、 Apache Sparkなどのビッグデータフレームワークにおいて基本となるもので、分散データセットに対する計算は結果が明示的に必要になるまで遅延され、実行の最適化と不要な処理の削減が可能になります。[ 10 ]
遅延評価により、制御構造をプリミティブやコンパイル時テクニックとしてではなく、通常どおり定義できます。たとえば、if-then-elseや短絡評価演算子を定義できます。[ 11 ] [ 12 ]
ifThenElse True b c = b ifThenElse False b c = c-- またはTrue || b = True False || b = b-- そしてTrue && b = b False && b = Falseこれらは通常の意味を持ちます。つまり、(a) を評価し、(a) が真と評価された場合に限り (b) を評価し、そうでない場合は (c) を評価します。つまり、(b) または (c) のどちらか一方のみが評価されます。同様に、 の場合、簡単な部分でTrue が返された場合、多くの作業を伴う式は回避できます。最後に、 を評価する際にSafeToTryがfalseの場合、式の評価は試みられません。ifThenElseabcEasilyComputed||LotsOfWorkSafeToTry&&Expression
逆に、即時評価言語では、上記の定義は(a) の値に関係なく (a)、(b)、(c) を評価します。これは望ましい動作ではありません。(b) または (c) は副作用があったり、計算に時間がかかったり、エラーが発生したりする可能性があるためです。通常、即時評価言語では、ユーザー定義の遅延制御構造を関数として導入できますが、即時評価のための言語の構文から逸脱する場合があります。多くの場合、関連するコード本体を関数値でラップして、呼び出されたときにのみ実行されるようにする必要があります。ifThenElseabc
遅延評価の利点は、無限ループやサイズの問題が計算を妨げることなく、計算可能な無限リストを作成できることです。実際の値は必要なときにのみ計算されます。たとえば、フィボナッチ数の無限リスト（ストリームと呼ばれることが多い）を作成する関数を作成できます。n番目のフィボナッチ数の計算は、無限リストからその要素を抽出するだけであり、リストの最初の n 個の要素のみを評価することになります。[ 13 ] [ 14 ]
例えば、Haskellで書かれたこの簡単なプログラムを見てみましょう。
numberFromInfiniteList :: Int -> Int numberFromInfiniteList n = infinity !! n - 1 where infinity = [ 1 .. ]main = print $ numberFromInfiniteList 4関数numberFromInfiniteListでは、 infinityの値は無限の範囲を表しますが、実際の値 (より具体的には、特定のインデックスの特定の値) が必要になるまではリストは評価されず、必要な場合にのみ (つまり、目的のインデックスまで) 評価されます。プログラマが注意していれば、プログラムは正常に完了します。ただし、特定の計算では、プログラムが無限個の要素を評価しようとする可能性があります。たとえば、リストの長さを要求したり、fold 演算を使用してリストの要素を合計しようとすると、プログラムが終了しないか、メモリ不足になる可能性があります。
別の例として、すべてのフィボナッチ数のリストは、プログラミング言語Haskellで次のように記述できます。[ 14 ]
fibs = 0 : 1 : zipWith ( + ) fibs ( tail fibs )Haskell構文では、「:」はリストの先頭に要素を追加し、tail最初の要素を除いたリストを返し、zipWith指定された関数（この場合は加算）を使用して2つのリストの対応する要素を結合して3番目のリストを生成します。[ 13 ]
コンピュータのウィンドウシステムでは、画面への情報の描画は、可能な限り最後の瞬間に表示コードを駆動するexposeイベントによって行われます。このようにすることで、ウィンドウシステムは不要な表示コンテンツの更新の計算を回避します。[ 15 ]
現代のコンピュータシステムにおける怠惰のもう1つの例は、コピーオンライトページ割り当てまたはデマンドページングであり、メモリに格納されている値が変更されたときにのみメモリが割り当てられます。[ 15 ]
遅延評価は、高性能なシナリオにおいて役立つ場合があります。例えば、Unixのmmap関数は、ディスクからのページ読み込みをオンデマンドで行うため、実際にアクセスされたページのみがメモリにロードされ、不要なメモリが割り当てられません。
MATLAB はコピーオン編集を実装しており、コピーされた配列は内容が変更されたときにのみ実際のメモリ領域が複製されるため、コピー操作中ではなく、その後で要素を更新したときにメモリ不足エラーが発生する可能性があります。 [ 16 ]
必要に応じて呼び出すことでラムダ項を縮約するために必要なベータ縮約の数は、値渡しまたは名前渡しによる縮約に必要な数よりも多くはありません。[ 17 ] [ 18 ]特定のプログラムでは、ステップ数がはるかに少なくなる場合があります。たとえば、チャーチ数を使用する特定のラムダ項のファミリーは、値渡しでは無限のステップ数（つまり、決して完了しない）、名前渡しでは指数関数的なステップ数、必要に応じて呼び出すことで多項式的なステップ数しか必要としません。必要に応じて呼び出すことで、2 つの最適化が実現されます。作業を繰り返しません（値渡しと同様）、および不要な作業を実行しません（名前渡しと同様）。[ 19 ]遅延評価は、必要に応じて値が作成されるため、メモリ使用量 の削減にもつながります。[ 20 ]
実際には、遅延評価は即時評価に比べて重大なパフォーマンスの問題を引き起こす可能性があります。たとえば、最新のコンピュータアーキテクチャでは、計算を遅延させて後で実行する方が、すぐに実行するよりも遅くなります。これは厳密性分析によって軽減できます。[ 19 ]遅延評価は、未評価の式のためにメモリリークを引き起こす可能性もあります。 [ 21 ] [ 22 ]
プログラミング言語の中には、デフォルトで式の評価を遅延させるものもあれば、評価を遅延させるための関数や特別な構文を提供するものもあります。KRC 、Miranda、Haskellでは、関数の引数の評価はデフォルトで遅延されます。他の多くの言語では、特別な構文 ( Scheme の"と " 、OCamlの" と " など) を使用して計算を明示的に中断するか、より一般的には、式をthunkでラップすることによって評価を遅延させることができます。このような明示的に遅延された評価を表すオブジェクトは、遅延フューチャーと呼ばれます。Rakuはリストの遅延評価を使用するため、無限リストを変数に代入して関数の引数として使用できますが、Haskell や Miranda とは異なり、Raku はデフォルトでは算術演算子や関数の遅延評価を使用しません。[ 9 ]delayforcelazyLazy.force
Haskellのような遅延評価プログラミング言語では、デフォルトでは式は要求されたときにのみ評価されますが、場合によってはコードをより積極的に評価したり、逆に、より積極的に評価した後に再びより遅延評価にしたりすることが可能になります。これは、評価を強制するコードを明示的に記述する（これによりコードがより積極的になる可能性がある）か、そのようなコードを避ける（これによりコードがより遅延評価になる可能性がある）ことによって実現できます。厳密な評価は通常、積極的な評価を意味しますが、これらは技術的には異なる概念です。
しかし、一部のコンパイラには厳密性解析と呼ばれる最適化機能が実装されており、場合によっては、コンパイラが特定の値が常に使用されることを推論できます。このような場合、厳密性解析によって厳密な評価が強制されるため、プログラマがその特定の値を強制するかどうかの選択は無意味になる可能性があります。
Haskell では、コンストラクタフィールドを strict とマークすると、その値は常に即座に要求されます。seq関数を使用すると、値を即座に要求してから渡すこともできます。これは、コンストラクタ フィールドが一般的に遅延評価されるべき場合に便利です。ただし、これらの手法のいずれも再帰的な厳密性を実装していません。再帰的な厳密性を実現するために、という関数がdeepSeq考案されました。
また、 Haskell 98 のパターンマッチングはデフォルトでは厳密なので、~遅延評価にするには修飾子を使用する必要があります。[ 23 ]
C++では、std::rangesライブラリは遅延レンジアダプタを使用します。[ 24 ]
import std ;using std :: vector ; using std :: ranges :: to ; using std :: views :: filter ; using std :: views :: iota ; using std :: views :: transform ;vector < int > v = iota ( 1 , 1'000'000 ) // 1 から 1,000,000 までの整数を遅延生成| filter ([]( int x ) -> bool { return x % 2 == 0 ; }) // 奇数を除外し、偶数を残す| transform ([]( int x ) -> int { return x * x ; }) // 各値を二乗| to < vector > (); // 範囲を vector<int> に変換Javaでは、値が必要になったときに評価するメソッドを持つオブジェクトを使用することで、遅延評価を行うことができます。このメソッドの本体には、この評価を実行するために必要なコードが含まれている必要があります。Java SE8 でラムダ式が導入されて以来、Java はこのための簡潔な表記法をサポートしています。次の例の汎用インターフェースは、遅延評価のフレームワークを提供します。[ 25 ] [ 26 ]
interface Lazy < T > { T eval (); }Lazyそのメソッドを持つインターフェースは、ライブラリ内のそのメソッドを持つインターフェースeval()と同等である。[ 27 ] [ 28 ] : 200Supplierget()java.util.function
インターフェースを実装する各クラスはメソッドLazyを提供する必要があり、クラスのインスタンスは、遅延評価を実行するためにメソッドが必要とする任意の値を保持できます。たとえば、次のコードを使用して 2 10evalを遅延計算して出力します。
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メソッドを持つ匿名クラスの新しいインスタンスを構築することに似ています。() -> 1Lazy<Integer>
ループの各イテレーションでは、ループ内のラムダ式を評価することによって作成される新しいオブジェクトにa がリンクされます。これらのオブジェクトはそれぞれ、別の遅延オブジェクトbへの参照を保持し、 2 回呼び出して合計を返すevalメソッドを持っています。ここで変数bが必要なのは、ラムダ式内から参照される変数は実質的に final でなければならないという Java の要件を満たすためです。b.eval()
このプログラムは、遅延整数の実装において、以前のeval呼び出しの結果をメモ化しないため、非効率的です。また、かなりのオートボクシングとアンボクシングが発生します。分かりにくいかもしれませんが、ループの最後に、プログラムは11 個のオブジェクトのリンク リストを構築し、結果の計算に関わる実際の加算はすべて、コードの最終行にある呼び出しに応じて実行されます。この呼び出しは、リストを再帰的に走査して必要な加算を実行します。a.eval()
遅延オブジェクトをメモ化する Java クラスは次のように構築できます。[ 25 ] [ 26 ]
class Memo < T > implements Lazy < T > { private Lazy < T > lazy ; // 遅延式、eval で null に設定private T memo ; // 前の値のメモランダムpublic 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 . printf ( "a = %s%n" , a . eval ());Java のラムダ式は単なる構文糖衣です。ラムダ式で記述できるものはすべて、インターフェース[ a ]を実装する匿名内部クラスのインスタンスを構築する呼び出しとして書き換えることができ、匿名内部クラスの使用はすべて名前付き内部クラスを使用して書き換えることができ、名前付き内部クラスは最も外側のネストレベルに移動できます。
JavaScriptでは、ジェネレーターを使用することで遅延評価をシミュレートできます。例えば、メモ化を使用して、すべてのフィボナッチ数のストリームを次のTypeScriptコードで記述できます。
/** * ジェネレーター関数は、遅延評価を具体化したジェネレーターオブジェクトを返します。* @return {!Generator<bigint>} null でない整数のジェネレーター。*/ function * fibonacciNumbers () : Generator < bigint , never , unknown > { let memo : [ bigint , bigint ] = [ 1n , - 1n ]; // 初期状態を作成します (たとえば、「負のフィボナッチ」数のベクトル) while ( true ) { // 無限に繰り返しますmemo = [ memo [ 0 ] + memo [ 1 ], memo [ 0 ]]; // 各評価で状態を更新しますyield memo [ 0 ]; // 次の値をyieldし、再開されるまで実行を中断します} }const stream : Generator < bigint , never , unknown > = fibonacciNumbers (); //遅延評価される数値ストリームを作成しますconst first10 : bigint [] = Array.from ( new Array ( 10 ), () => stream.next ( ) . value ) ; // 最初の10個の数値のみを評価しますconsole.log(first10 ) ; //出力は[0n, 1n, 1n, 2n, 3n, 5n, 8n, 13n, 21n, 34n] ですKotlinでは、次のような句を使用して委譲プロパティ[ 30 ]を初期化する[ 29 ]関数を使用して、変数を遅延初期化できます。lazy{}by
var flipped = trueval pizzaReady : Boolean by lazy { println ( "ピザが今できているか確認します。" ) // これが複数回実行されると false が出力されます。flipped = ! flipped ! flipped }fun main () { println ( "ピザはできましたか？" ) assert ( pizzaReady ) // クラッシュしないprintln ( "まだできていますか？" ) assert ( pizzaReady ) // やはりクラッシュしない}Kotlin Playgroundにアクセスすれば、この例を自分で実行できます。
プログラムがisThePizzaReady事前に初期化されるのではなく、遅延ロードされたことを確認するには、プログラムの出力をチェックする必要があります。
ピザはできましたか？今すぐピザができたかどうか確認します。まだできていますか？プログラムが読み込むと、 4行目isThePizzaReadyの遅延コードブロック内に記述したステートメントが出力されることがわかります。また、遅延ブロックが2回実行されず、以前の出力が再利用されたことは、以下の事実から確認できます。
Python 2.xでは、range()関数[ 32 ]は整数のリストを計算します。最初の代入文が評価されるとリスト全体がメモリに格納されるため、これは即時評価の例です。
r = range ( 10 ) print r # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] と出力print r [ 3 ] # 3 と出力Python 3.x では、range()関数[ 33 ]は、必要に応じてリストの要素を計算するジェネレーターを返します。要素は必要なときにのみ生成されるため (たとえば、print(r[3])次の例で評価されるとき)、これは遅延評価または遅延評価の例です。
r : Iterator [ int ] = range ( 10 ) print ( r ) # range(0, 10) と出力print ( r [ 3 ]) # 3 と出力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] と出力しますPythonはバージョン2.2以降、タプルやリストのシーケンスとは異なり、イテレータ（遅延シーケンス）を実装することで遅延評価を実現しています。例えば（Python 2）：
numbers : Iterator [ int ] = range ( 10 ) iterator : Iterator [ int ] = iter ( numbers ) print ( numbers ) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] と出力print ( iterator ) # <listiterator object at 0xf7e8dd4c> と出力print ( iterator.next ( )) # 0 と出力.NETフレームワークでは、クラスを使用して遅延評価を行うことができます。[ 34 ]クラスは、キーワードを使用してF#で簡単に利用できますが、メソッドは評価を強制します。遅延評価を組み込みでサポートするなどの特殊なコレクションもあります。System.Lazy<T>lazyforceMicrosoft.FSharp.Collections.Seq
let fibonacci = Seq.unfold ( fun ( x , y ) - > Some ( x , ( y , x + y ) ) ) ( 0I , 1I ) fibonacci | > Seq.nth 1000C#とVB.NETでは、このクラスが直接使用されます。System.Lazy<T>
Systemを使用します。public int Sum ( ) { int a = 0 ; int b = 0 ; Lazy <int> x = new (() = > a + b ) ; a = 3 ; b = 5 ; return x.Value ; // 8 を返す}あるいは、より具体的な例を挙げると：
Systemを使用します。// 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 (() => 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。
System.Collections.Genericを使用します。// 即時評価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 ; } }