7

以下は、コースの講義ノートから直接、修了したばかりのプログラムの設計方法 (簡略化されたラケット) コースから得られる 2 つの最大のもののようです。

1) 末尾呼び出しの最適化、および非関数型言語でのその欠如:

残念ながら、他のほとんどの言語は TAIL CALL OPTIMIZATION をサポートしていません。別の言い方をすれば、テールコールでもスタックを構築します。

テール コールの最適化は、ほとんどの言語の主要な要素が開発されてからずっと後の 70 年代半ばに発明されました。テール コールの最適化がないため、これらの言語は、任意のサイズのデータ​​をトラバースできるようにする固定の LOOPING CONSTRUCTS セットを提供します。

a) この種の最適化を特徴としない手続き型言語で、このタイプの最適化に相当するものは何ですか? b) これらの等価物を使用することは、スタックを持たない言語で同様の状況でスタックを構築することを避けることを意味しますか?

2) 変異とマルチコア プロセッサ

このメカニズムは、プログラミングで使用する他のほとんどすべての言語の基本です。いくつかの理由により、これまで導入を遅らせてきました。

  • 基本的であるにもかかわらず、驚くほど複雑です

  • これを使いすぎると、プログラムが並列化 (複数のプロセッサで実行) に対応できなくなります。マルチコア コンピューターが一般的になった現在、必要なときにのみミューテーションを使用する機能がますます重要になっています。

  • ミューテーションを使いすぎると、プログラムを理解するのが難しくなり、プログラムをうまくテストするのが難しくなります。

しかし、可変変数は重要であり、このメカニズムを学ぶことで、Java、Python、および他の多くの言語を使用する準備が整います。そのような言語でも、「ほぼ関数型プログラミング」というスタイルを使いたいものです。

このコースを受講する前に、Java、Python、および C++ をいくつか学んだので、突然変異を当然のことと考えるようになりました。今、それはすべて上記の声明によって空中に放り出されました. 私の質問は次のとおりです。

a) 2 番目の箇条書きで提案されていること、およびそれに対して何をすべきかについて、より詳細な情報をどこで見つけることができますか? b) より不注意なスタイルとは対照的に、「ほとんど関数型プログラミング」スタイルからどのような種類のパターンが出現するかこのコースを受講する代わりに、他の言語を続けていればよかったのではないでしょうか?

4

3 に答える 3

9

Leppie が指摘しているように、ループ構成体は、サポートする特定の種類のループに対して、適切な末尾呼び出しのスペース節約をなんとか回復します。ループ構成の唯一の問題は、ユーザーのコートにボールを投げてスタックを明示的にモデル化するように強制しない限り、手持ちの構成では決して十分ではないということです。

例を挙げると、ループを使用して二分木をトラバースしているとします。それは機能します...しかし、「戻ってくるもの」を明示的に追跡する必要があります。末尾呼び出し言語での再帰的トラバーサルにより、不要なときにスペースを無駄にせず、自分でスタックを追跡する必要がないため、ケーキを持って食べることもできます。

並列処理と並行処理に関するあなたの質問は、はるかに広く開かれています。最良の指針は、おそらく既存のソリューションではなく、研究分野に関するものです。コンピューティングの世界で危機が進行していることにはほとんどの人が同意すると思います。ミューテーションを多用するプログラミング スキルを新しいマルチコアの世界に適応させるにはどうすればよいでしょうか。

ここでも、単に機能的なパラダイムに切り替えるだけでは特効薬ではありません。高水準のコードを記述し、非常に高速で変更のない同時実行コードを生成する方法はまだわかっていません。しかし、多くの人々がこれに取り組んでいます！

于 2011-12-15T08:37:43.760 に答える
4

「可変性により並列処理が困難になる」という概念を拡張するには、複数のコアを使用する場合、1つのコアから何かを変更し、他のすべてのコアで一貫して表示されるようにするには、同期を使用する必要があります。

同期を正しく行うのは難しいです。同期しすぎると、デッドロック、パフォーマンスの低下（並列ではなくシリアル）などが発生します。同期が不十分な場合、変更が部分的に観察されます（別のコアは、別のコアから行った変更の一部のみを認識します）。 ）、オブジェクトを無効な「途中変更」状態で監視したままにします。

そのため、多くの関数型プログラミング言語では、共有状態の概念ではなく、メッセージキューの概念が推奨されています。その場合、唯一の共有状態はメッセージキューであり、メッセージキューでの同期の管理は解決された問題です。

于 2011-12-15T15:06:32.163 に答える
0

a）それを備えていない手続き型言語でのこのタイプの最適化に相当するものは何ですか？b）これらの同等物を使用することは、スタックがない言語で同様の状況でスタックを構築することを回避することを意味しますか？

末尾呼び出しの重要性は、呼び出しスタックに追加せずに別の関数を評価できることです。そのため、スタックを構築するものは、実際には同等とは言えません。

末尾呼び出しは、関数呼び出しの言語トラップとすべての適切な詳細管理を使用して、基本的に新しいコードへのジャンプのように動作します。したがって、この最適化のない言語では、単一の関数内でジャンプを使用します。ループ、条件付きブロック、またはgoto他に何も機能しない場合は任意のステートメント。

a）2番目の箇条書きで提案されていること、およびそれに対して何をすべきかに関するより詳細な情報はどこにありますか？

2番目の箇条書きは単純化しすぎのように聞こえます。並列化を必要以上に困難にする方法はたくさんあり、ミューテーションの乱用は1つにすぎません。

ただし、並列化（タスクを同時に実行できる部分に分割する）は、並行性（相互作用する可能性のある複数のタスクを同時に実行する）と完全に同じではないことに注意してください。ただし、確かに重複しています。不変のデータは、他の方法では可能である多くの競合状態やリソースの競合を回避するため、ミューテーションを回避することは、並行プログラムを作成する際に非常に役立ちます。

b）このコースを受講する代わりに他の言語を続けていたとしたら、おそらくもっと不注意なスタイルとは対照的に、「ほとんど関数型プログラミング」スタイルからどのようなパターンが現れるでしょうか。

HaskellやClojureを見たことがありますか？どちらも、制御された突然変異を強調する非常に機能的なスタイルに強く傾いています。Haskellはそれについてより厳密ですが、限られた形式の可変性を操作するための多くのツールを備えています。一方、Clojureはもう少し非公式であり、別のLisp方言であるためより馴染みがあるかもしれません。

于 2011-12-15T15:19:19.163 に答える