4

http://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_needは、次
のように述べています。 [...] Haskellは、必要に応じた評価を使用する最もよく知られた言語です。」

ただし、計算の値は、アクセスを高速化するために常に保存されるとは限りません(たとえば、フィボナッチ数の再帰的定義を検討してください)。#haskellで誰かに聞いたところ、このメモ化は自動的に行われるというものでした。たとえば、「let foo = bar baz」がある場合、fooは1回評価されます」。

私の質問は次のとおりです。インスタンスは正確にはどういう意味ですか、メモ化が自動的に行われるようにする以外の場合はありますか?

4

3 に答える 3

7

この動作を「メモ化」と説明するのは誤解を招く恐れがあります。「必要に応じて呼び出す」とは、関数への特定の入力が0〜1回評価され、2回以上評価されないことを意味します。(部分的に評価することもできます。つまり、関数はその入力の一部のみを必要とします。)対照的に、「名前による呼び出し」は単なる式の置換です。つまり2 + 3、関数への入力として式を指定すると、次のようになります。入力が複数回使用される場合は、複数回評価されます。必要による呼び出しと名前による呼び出しはどちらも厳密ではありません。入力が使用されない場合、評価されることはありません。ほとんどのプログラミング言語は厳密であり、「"アプローチ。つまり、入力が使用されているかどうかに関係なく、関数の評価を開始する前にすべての入力が評価されます。これはすべて、let式とは関係ありません。

Haskellは自動メモ化を実行しません。式はメモ化の例ではありません。ただし、ほとんどのコンパイラは、必要に応じて呼び出す方法でletバインディングを評価します。let式を関数としてモデル化する場合、「必要に応じて呼び出す」という考え方適用されます。

let foo = expression one in expression two that uses foo
==>
(\foo -> expression two that uses foo) (expression one)

これは再帰的バインディングを正しくモデル化しませんが、あなたはその考えを理解します。

于 2012-04-28T11:45:26.303 に答える
6

haskell言語の定義では、コードがいつ、どのくらいの頻度で呼び出されるかは定義されていません。無限ループは、エラー状態を表す値(すべてのタイプに存在する)である「最下部」(⊥と表記)で定義されます。プログラム(および無限ループを含むエラー条件の有無!)が仕様に従って動作する限り、コンパイラーは、いつ、どのくらいの頻度で評価するかを自由に決定できます。

とは言うものの、これを行う通常の方法は、ほとんどの式が「サンク」を生成することです。基本的には、いくつかのコードといくつかのコンテキストデータへのポインターです。式の結果を初めて調べるとき(つまり、パターンがそれに一致するとき)、サンクは「強制」されます。ポイントされたコードが実行され、サンクが実際のデータで上書きされます。これにより、他のサンクを再帰的に評価できます。

もちろん、これを常に行うのは遅いので、コンパイラは通常、とにかくサンクを強制することになったとき(つまり、問題の値に「厳密」なものがあるとき)、およびそれが見つかったかどうかを分析しようとしますこれにより、サンク全体がスキップされ、すぐにコードが呼び出されます。これを証明できない場合でも、サンクをすぐに実行するとクラッシュしたり、無限ループが発生したりしないようにする(またはこれらの条件を何らかの方法で処理する)限り、この最適化を行うことができます。

于 2012-04-28T09:13:53.810 に答える
0

これについてあまり技術的になりたくない場合、重要な点は、のような式がある場合some_expensive_computation of all these arguments、それを使って好きなことを行うことができるということです。データ構造に保存し、53のコピーのリストを作成し、他の6つの関数などに渡します。さらに、呼び出し元に返して、呼び出し元がやりたいことを実行できるようにします。

Haskellが(ほとんど)行うことは、せいぜい一度だけそれを評価することです。プログラムが決定を下すためにその式が何を返したかについて何かを知る必要がある場合、それは評価されます(少なくとも決定がどちらの方向に進むべきかを知るのに十分です)。その評価は、プログラム全体でデータ構造や他のまだ評価されていない式に散在している場合でも、同じ式への他のすべての参照に影響します。

于 2012-04-28T09:56:16.850 に答える