Eager対Lazy Haskell。 Eagerの言語で無限のリストが可能ですか？

Question

Haskellを実装して、言語のセマンティクスを全く変更せずに熱心に評価できるように見えることは明らかです。それが当てはまる場合、無限のデータ構造はどのように処理されますか？

http://csg.csail.mit.edu/pubs/haskell.html

ため、多大な時間を作成し、計算（サンク）の中断部分を破壊費やされています。あまりにも頻繁に、これらの計算は単純であるため、代わりにそれらを評価するのと同じくらい簡単です。 Faxenらは静的分析を使用して、そのような機会を熱心に暴露してきました。私たちは、プログラムがあまりにも熱心であれば、私たちが回復することを可能にするメカニズムを使用しながら、あらゆるところで熱心を使用することを提案します。

「私たちのプログラムがあまりにも熱心であれば回復するためのメカニズムがあります」という重要なことがあります。これらのメカニズムは何ですか？彼らは無限のデータ構造をどのように許しているのですか、私が熱心な言語では不可能だと信じられてきた遅延評価の他の側面はありますか？

Answer 1

実際にはそうではありません。が分岐しないことを証明できれば、ハスケルの言葉を熱心に評価することができます。

例えば、あなたがf xを見たときには、最初X（もしWHNF（弱頭部正規形）またはエラーに達した場合に停止）1000のステップまで実行することができ、その後 F に渡します - セマンティクスは保持されますが、xが評価されると思う場合は、最適化としてこれを事前に実行するように調整できます。

x = fix idの場合は、何も進んでいない1,000歩後にあきらめます。 x = undefinedの場合、エラーが発生し、元のサンクを復元してfに渡します。等々。

x = [1..]場合、それは、1 : 2 : 3 : ... : 999 : 1000 : [1001..]にそれを減らしてしまう限界に達し、そしてそこに停止し、Fに結果を渡すかもしれません。

基本的には、式が発散できないことを証明するか、または評価が境界に達しても終了するように評価を制限することによって行います。セマンティクスに変更はなく、おそらくパフォーマンスの大幅な改善になります。もちろん

、マイナス面は、xが F が唯一の半分を使用していることをいくつかの本当に高価計算であることが判明した場合、あなたは時間を無駄に千の削減ステップを費やすことです。 [1..]の場合、多くのメモリを使用してリストを保存することになります。 fが一度に1つの要素を処理し、毎回頭を捨てると、メモリが浪費されます。そのため、それは難しいです:)

最初にリンクしたページは、使用されている特定のテクニックについてさらに詳しく説明しています。