関数プログラミング言語の実装で共有が参照するもの

Question

共有は、複数回使用すると一時データが保存されることを意味します。つまり、関数は引数を1回だけ評価します。例は次のようになります。を共有に貢献し、それらがどのようにIOを実行するための実践的なプログラムの必要性と相互作用する他のどのような機能

let x = sin x in x * x 

？

Answer 1

関数プログラミングでの共有の最も明白な例は、グラフの書き換えに基づくCleanからです。そこでは、計算はDAGを参照するので、私たちは(sin x) * (sin x)

として

(*) 
/ \ 
sin x sin x 

グラフ書換え系は、共有の明示的な概念を持っている表現を表示することができますので、我々は

(*) 
/\ 
    \/
    sin x 

指しとしてその計算を表現できます乗算ノードを同じノードに割り当てることにより、sin xの計算を共有する。用語書き換えシステムは、共有の概念をあまり明確にしていませんが、最適化は依然として関連しています。 GHCでは、ローカル変数との共有を表現することがあります。

f x = sinx * sinx 
    where sinx = sin x 

に

f x = (sin x) * (sin x) 

を書き換えるが、2つの意味的に等価であるため、コンパイラは、または共有することなく、両方同じ方法を実施して自由です。私の理解では、GHCは一般的にローカル変数で導入された共有を保持し、時にそれを導入する（最初に共有を追加する）が、書き換えシステムの共有を正式に表現することは実装依存である（telのコメントと回答を参照）。

副作用の値を共有できないため、共有はIOに接触します。我々は不純な言語を考慮した場合、最初は、ユーザーからの2行を要求し、それらを追加し、二回IOアクションを実行

(string-append (read-line) 
       (read-line)) 

と

(let ((s (read-line))) 
    (string-append s s)) 

違いがあります。 2つ目はIOアクションを「共有」し、1回実行してそれをそれ自身に追加します。一般に、純粋な計算を共有することで、プログラムの結果を変更することなく実行時間が短縮され、副作用の値（時間の経過とともに変化する、またはユーザーとやりとりする）が結果を変更します。コンパイラが自動的に計算を共有するためには、それらが純粋であることを知る必要があるため、評価の数を減らすことは重要ではありません。クリーンは一意性の型でこれを行います。 IOアクションにはUNQという型属性があり、コンパイラには共有されてはならないことが通知されます。ハスケルはIOモナドとやや異なっている。

Answer 2

共有は、ほぼ同種のものです。ポインタの平等。ハスケルの価値のある土地（意味論的解釈）には、共有というものはありません。値がEqのインスタンスを持ち、「等価」が2進関係(==)と定義されている場合にのみ、値は等しくなります。

共有は、セマンティクスではなく実装のために存在するこの根本的なポインタの等価性を参照することによって意味解釈をエスケープします。しかし、時にはこれは有用な副作用です。残念ながら、Haskellはそのセマンティック解釈によって定義されているので、共有の使用は未定義の動作です。それは特定の実装に結びついています。いくつかの図書館は共有を利用しており、GHCに関連した行動をとっています。

ただし、1つの組み込みの共有メカニズムがあります。これは、StableNameインターフェイスによって公開されています。我々は、makeStableName :: a -> IO (StableName a)を使用してStableName aオブジェクトを生成し、instance Eq (StableName a)を持っています。StableNameは、任意のタイプに対して何らかの同等性を導入します。

StableName等価は、ほぼと等しいポインタです。 sn1 :: StableNameとsn2 :: StableNameとsn1 == sn2、その後sn1とsn2場合ハドックのドキュメント

を引用するには、同じオブジェクトのmakeStableNameへの呼び出しによって作成されました。これはちょうど if文ではなく、場合にのみ場合であることを

注意。 2つのものが "ポインタ同等"であるが、安定した名前が異なるという事実は、（a）ハスケルがGCに残す柔軟性と、（b）StableNameがハスケルの実装に存在しても存在することを可能にする抜け穴実装では「ポインタの平等」というものはまったくありません。

これらのStableNameはまだ意味がありませんが、「OK」のIOモナドに導入されているためです。代わりに、どのようなタイプでも可能な最小の（最も具体的な）等価関係の（皮肉的に）不安定なサブセットを実装すると言われるかもしれません。

Answer 3

あなたの例は、共有の例ではありません。値は単なる値ではなく、元の値を離れてしまいます。

共有は、大きなデータ構造または異なるデータ構造でデータ構造の一部が2回発生する場合です。例：

p = (1, 2) 
pp = (p, p) -- p is shared between the first and second component of pp 

xs = [1, 2, 3] 
ys = 0::1::xs 
zs = 5::xs -- ys and zs share the same tail 

メモリ内では、このような共有はDAG構造になります。