5

SICPのストリーム 2 ビデオで、Abelson はアナログ コンピューターを使用して微分方程式を解く例を示しています。次に、これをSchemeでプログラムし、遅延評価を使用して循環定義依存を回避します。

この手法の問題点は、より複雑なプログラムを設計すると、どこでも式が遅れてしまい、理解が困難になることだと彼は言います。問題をエレガントに解決するには、表現力をいくらか犠牲にして、言語全体を遅延させる必要があります。つまり、尻尾を引きずる問題です。

これはMirandaとHaskellが取ったアプローチです。Haskell では、Big Oの複雑さを理解するのは難しく、メモリと時間を大量に消費するプログラムを簡単に作成できることがわかりました。

私はかつてこの問題についてRobert Harperと話しましたが、彼は、言語をエレガントにするには言語全体を遅延させる必要があり、これは Haskell の設計上の欠陥であることに同意しませんでした。この問題を解決するために言語を部分的に遅延させるには、具体的にどのようにすればよいでしょうか? そのような言語の例はありますか? 関数型言語についてもっと学びたいのですが、I/O を含むすべての場所で副作用と熱心な評価を禁止すると、物事が少し… 直感に反します。

4

1 に答える 1

8

Big O の複雑さについて推論するのは難しくありません。怠惰な言語では違います。これに関する古典的な参考文献は、複雑さを説明するための銀行家の方法(第 3 章を参照) を説明する岡崎の論文(およびその後の本) です。

一般に、遅延動作と厳密動作の混合が必要です。一部のデータ構造では、「スパイン」では厳密で要素では遅延が必要になる場合があります。他のデータ構造では、要素が厳密である必要があるかもしれませんが、スパインで選択的遅延が発生する可能性があるため、たとえば、構造ベクトルが無限になる可能性があります。Haskell は、データ コンストラクターの定義を直接含めて、選択的厳密性を備えた遅延性を提供します。他の言語は、選択的怠惰を伴う厳密性を提供します。一般に、Haskell のデフォルトの遅延動作には、特に新しい制御構造の定義に関して、特定の利点があることがわかります。たとえば、ここを参照してください(実際には、Harper に応じて書かれています)。

于 2013-06-28T19:15:35.733 に答える