18

怠惰なセマンティクスを持つ純粋な関数型言語（Haskellなど）では、計算結果がメモ化されるため、同じ入力を持つ関数をさらに評価しても、値は再計算されず、メモ化された値のキャッシュから直接取得されます。

これらのメモ化された値は、ある時点でリサイクルされるのでしょうか。

  1. もしそうなら、それはメモ化された値が後で再計算されなければならないことを意味し、メモ化の利点は私見からそれほど離れていません。
  2. そうでない場合は、OK、これはすべてをキャッシュするのに賢いです...しかし、プログラムが-十分に長い期間実行された場合-常により多くのメモリを消費することを意味しますか？

集中的な数値解析を実行するプログラムを想像してみてください。たとえば、二分法アルゴリズムを使用して、数十万の数学関数のリストの根を見つけます。

プログラムが特定の実数で数学関数を評価するたびに、結果はメモ化されます。ただし、アルゴリズム中にまったく同じ実数が再び表示され、メモリリーク（または少なくとも非常に悪い使用法）が発生する可能性は非常に低いです。

私の考えでは、メモ化された値は、プログラム内の何か（たとえば、現在の継続、呼び出しスタックなど）に単純に「スコープ」されますが、この主題に関して実用的なものを見つけることができませんでした。

Haskellコンパイラの実装を深く調べていないことは認めますが（怠惰ですか？）、実際にどのように機能するかを誰かに説明してもらえますか？

編集：わかりました、最初のいくつかの答えから私の間違いを理解しています：純粋なセマンティクスは参照透過性を意味します。これは自動メモ化を意味しませんが、問題がないことを保証するだけです。

初心者の観点からは、暗黙のメモ化が可能であるため、参照透過性プロパティは非常に優れているように思われるため、Web上のいくつかの記事はこれについて誤解を招くと思います。

4

2 に答える 2

20

Haskell は、関数呼び出しを自動的にメモ化しません。これは、大量のメモリをすぐに消費するためです。メモ化を自分で行う場合、関数をメモ化するスコープを選択できます。たとえば、次のように定義されたフィボナッチ関数があるとします。

fib n = fibs !! n
    where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

ここでは、メモ化は への 1 回の呼び出し内でのみ行われますが、最上位レベルで終了したfib場合はfibs

fib n = fibs !! n

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

fibsその後、メモ化されたリストは、ガベージ コレクターがプログラムのどの部分からも到達する方法がないと判断できるまで保持されます。

于 2011-05-05T13:23:42.030 に答える
5

私の考えでは、メモ化された値は単にプログラム内の何か (たとえば、現在の継続、呼び出しスタックなど) に「スコープ」されている可能性がありますが、この件に関して実用的なものを見つけることができませんでした。

正解です。具体的には、次のようなものが表示された場合:

fun x y = let
    a = .....
    b = ....
    c = ....
in ....

または同等の where 句の場合、値 a、b、および c は実際に使用されるまで計算されない場合があります (または、いずれにしても値が後で評価されることを厳密性アナライザーが証明できるため、すぐに計算される場合があります)。しかし、これらの値が現在の関数パラメーター (ここでは x と y) に依存している場合、ランタイムは x と y のすべての組み合わせと結果の a、b、c を覚えているとは限りません。

また、純粋な言語では、値をまったく記憶しなくても問題ないことに注意してください。これは、メモリが CPU 時間よりも安価である場合にのみ実用的です。

したがって、あなたの質問に対する答えは次のとおりです。言えることは、評価された値は必要なときにそこにあるということだけです。

于 2011-05-05T13:24:21.967 に答える