31

副作用のない、参照透過的な関数型プログラミングの約束の 1 つは、そのようなコードを広範囲に最適化できることです。ウィキペディアを引用するには：

多くの場合、データの不変性は、コンパイラが命令型言語で安全でない仮定を行うことを可能にすることで、実行効率につながり、インライン展開の機会を増やします。

より最適化されたコードを生成することで、関数型言語コンパイラが命令型コンパイラよりも優れている例を見たいと思います。

編集:特定のシナリオを提示しようとしましたが、どうやらそれは良い考えではありませんでした。なので、別の方法で説明しようと思います。

プログラマーはアイデア (アルゴリズム) を機械が理解できる言語に翻訳します。同時に、翻訳の最も重要な側面の 1 つは、人間も結果のコードを理解できることです。残念ながら、多くの場合、トレードオフがあります。簡潔で読みやすいコードは、パフォーマンスが低下し、手動で最適化する必要があります。これはエラーが発生しやすく、時間がかかり、コードが読みにくくなります (完全に読みにくくなります)。

不変性や参照透過性などの関数型言語の基盤により、コンパイラは広範な最適化を実行できます。これにより、コードの手動最適化が置き換えられ、プログラマはこのトレードオフから解放される可能性があります。次のようなアイデア（アルゴリズム）とその実装の例を探しています。

  1. (機能的な) 実装が元のアイデアに近く、理解しやすい。
  2. 言語のコンパイラによって広範囲に最適化されています。
  3. 簡潔さと可読性を低下させる手動の最適化なしでは、命令型言語で同様に効率的なコードを書くことは困難 (または不可能) です。

少し曖昧で申し訳ありませんが、アイデアが明確になることを願っています。回答に不必要な制限を加えたくありません。誰かがそれをよりよく表現する方法を知っていれば、私は提案を受け入れます。

私の興味は理論的なことだけではありません。このような例を (とりわけ) 使用して、学生が関数型プログラミングに興味を持つように動機付けたいと思います。

最初は、コメントで提案されたいくつかの例に満足できませんでした。考え直して、私は反対意見を撤回します。これらは良い例です。人々がコメントして投票できるように、自由に完全な回答に拡張してください。

(そのような例の 1 つのクラスは、複数の CPU コアを利用できる並列化されたコードである可能性が最も高いでしょう。多くの場合、関数型言語では、コードの単純さを犠牲にすることなく、これを簡単に実行できます (適切な場所に追加することにより、Haskell のように) par。pseqそのような例にも興味がありますが、他の非並列例にも興味があります。)

4

4 に答える 4

23

同じアルゴリズムが純粋なコンテキストでより適切に最適化される場合があります。具体的には、ストリームフュージョンにより、マップ、フィルター、フォールド、アンフォールドなど、さまざまな形式のループのシーケンスで構成されるアルゴリズムを1つのループに構成できます。

ループ内の可変データを使用する従来の命令設定での同等の最適化は、完全な効果分析を達成する必要がありますが、これは誰も行いません。

したがって、少なくともシーケンスのアナモルフィズムとカタモルフィズムのパイプラインとして実装されるアルゴリズムのクラスでは、命令型の設定では不可能な最適化結果を保証できます。

于 2013-01-16T14:30:09.517 に答える
8

Geoff Mainland、Simon Peyton Jones、Simon Marlow、Roman Leshchinskiy によるごく最近の論文Haskell Beats C using generalized stream fusion (ICFP 2013 に提出) は、そのような例を説明しています。アブストラクト (興味深い部分は太字):

ストリーム フュージョン [6] は、高レベルのシーケンス処理関数を効率的な実装に自動的に変換するための強力な手法です。バイト配列、Unicode テキスト、ボックス化されていないベクトルを操作するために、Haskell ライブラリで非常に効果的に使用されています。ただし、ベクトル追加などの一部の操作は、標準のストリーム フュージョン フレームワーク内ではまだうまく機能しません。最新の x86 チップで利用可能な SSE および AVX 命令を使用した SIMD 計算のようなその他のものは、フレームワークにまったく適合しないようです。

このホワイト ペーパーでは、これらの問題を解決する一般化されたストリーム フュージョンを紹介します。重要な洞察は、複数のストリーム表現をまとめてバンドルし、それぞれを特定のクラスのストリーム コンシューマーに合わせて調整することです。また、SSE 命令による効率的な計算に適したストリーム表現についても説明します。私たちのアイデアは、修正されたバージョンの GHC コンパイラとvectorライブラリに実装されています。 ベンチマークは、当社のコンパイラーとライブラリーを使用して記述された高レベルの Haskell コードが、コンパイラーおよび手動でベクトル化された C の両方よりも高速なコードを生成できることを示しています。

于 2013-04-11T09:52:09.493 に答える
3

これは単なるメモであり、答えではありません。 には、純度を考慮することができることを示唆する属性がありますgcc。明らかな理由は、こちらpureのマニュアルに記載されています。

「静的な単一の割り当て」は純粋さの形を課すと思います-http://lambda-the-ultimate.org/node/2860のリンクまたはウィキペディアの記事を参照してください。

于 2013-01-28T19:06:59.800 に答える
0

make およびさまざまなビルド システムは、さまざまなビルド ステップが参照透過的であると想定することで、大規模なプロジェクトのパフォーマンスを向上させます。そのため、入力が変更されたステップのみを再実行する必要があります。

小規模から中規模の変更の場合、これは最初から構築するよりもはるかに高速です。

于 2013-01-30T21:15:37.987 に答える