なぜ純粋関数型言語は参照カウントを使用しないのでしょうか?

StackOverflow https://stackoverflow.com/questions/791437

質問

純粋関数型言語では、データは不変です。参照カウントの場合、参照サイクルを作成するには、すでに作成されているデータを変更する必要があります。純粋な関数型言語では、循環の可能性を気にせずに参照カウントを使用できるようです。アムは正しいですか？もしそうなら、なぜそうしないのでしょうか？

多くの場合、参照カウントは GC よりも遅いことは理解していますが、少なくとも一時停止時間が短縮されます。一時停止時間が遅い場合に参照カウントを使用するオプションがあると便利です。

役に立ちましたか？

解決

あなたの質問は、障害のある仮定に基づいています。これは、循環参照と不変のデータを持っていることは完全に可能です。循環参照を作成するために、不変のデータを使用し、次のC＃の例を考えます。 

class Node { 
  public readonly Node other;
  public Node() { 
    other = new Node(this);
  }
  public Node(Node node) {
    other = node;
  }
}

トリックのこのタイプは、多くの関数型言語で行うことができますので、任意の収集メカニズムは、循環参照の可能性に対処しなければなりません。私は、参照カウントメカニズムは、それが対処されなければならないだけであること、循環参照を持つことは不可能であるとは言いませんよ。

ephemientする

によって編集

コメントに応えて...これはHaskellで簡単です。

data Node a = Node { other :: Node a }
recursiveNode = Node { other = recursiveNode }

とSMLでかろうじて任意のより多くの努力ます。

datatype 'a node = NODE of unit -> 'a node
val recursiveNode : unit node =
    let fun mkRecursiveNode () = NODE mkRecursiveNode
    in mkRecursiveNode () end

いいえ変異は必要ありません。

他のヒント

相対的にその他の言語のようなJavaとC#, 純粋な機能的な言語で配分のような狂気.うに配置物がくっきりと水面に見てとれる。最速の既知の配分戦略への配分からの連続したフリースペースとも呼ばれる"保育士"の予約、ハードウェア登録の次のご利用が無料。配分からのヒープなどの配分からのスタックです。

リファレンスカウンターでは根本的に対応していないこ配分戦略です。参考計数をオブジェフリーリストかかっています。参考計数も大幅にオーバーヘッドに必要な更新するための参考計数として新たなオブジェクトを作成する（上述したように、純粋な機能的言語のようなクレイジ).

リファレンスカウンターがやりがちなんでもそのような場合:

  • ほぼすべてのヒープメモリ使用されるライブオブジェクト。
  • 配分およびのポインタ配は少またはその他の事業です。
  • 参考文献管理することができ他のプロセッサやコンピュータ.

からの最高性能ref-計数システムの仕組みは今日、生産性の向上をもたらし、作業の デビッド-ベーコン や Erez Petrank.

あ、と思っています。

  • あり は サイクル:ましょう"rec"多くの言語ができるように環状構造を作成します。これとは別に、不変性は通常係ないサイクルがこの休憩に。
  • Ref-カウントに対する悪いでリスト:わからないことを参考カウン回収作業にかかるなどの長単独-連リストの構造をよく見FP例遅めに必要なテール-recursive,...)
  • その他の戦略特典:まallude、その他のGC戦略についても通常より良いメモリの産地

(昔と思いつも本当に'を知っていた'ここでは、今は"覚えようとすると/と推測さいここにします。)

考慮する この寓話 について話しました デビッド・ムーン, の発明者。 Lispマシン:

ある日、学生がムーンのところに来てこう言いました。「より優れたガベージ コレクターを作成する方法を理解しました。それぞれの短所へのポインタの参照カウントを保持する必要があります。」

文氏は根気よく生徒に次の話をした。

「ある日、学生がムーンのところに来てこう言いました。「より優れたガベージ コレクターを作成する方法は理解しました...

  

アムが正しい？

未かなり。あなたは、単に同時に相互再帰的な値を定義することにより、純粋関数型プログラミングを使用してサイクリックデータ構造を作成することができます。例えば、OCamlのでます：

let rec xs = 0::ys and ys = 1::xs

しかし、不可能な設計により環状構造を作成することができます言語を定義することが可能です。結果は以下のように知られているの一方向ヒープおよびその主な利点は、ガベージコレクションが参照カウントのように単純であることができるということである。

  

もしそうなら、なぜ彼らはないのですか？

一部の言語ではサイクルを禁止し、参照カウントを使用します。アーランとMathematicaがその例である。

あなたが値を参照するとき、

たとえば、Mathematicaであなたはとてもオリジナルのコピーを変異させていない変異それの深いコピーを作成します：

In[1] := xs = {1, 2, 3}
Out[1] = {1, 2, 3}

In[2] := ys = xs
Out[2] = {1, 2, 3}

In[3] := xs[[1]] = 5
Out[3] = 5

In[4] := xs
Out[4] = {5, 2, 3}

In[5] := ys
Out[5] = {1, 2, 3}
それはCPUのために良いではありませんので、

参照カウントはGCよりもはるかに遅いです。そしてGC時間のほとんどは、アイドル時間を待つことができ、また、GCは、（別のスレッド上で）同時することができます。だから、それが問題だ - GCは少なくとも悪であるとことが示さしようとたくさんの

。
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top