Warum gehst du nicht rein funktionalen Sprachen verwenden Referenzzählung?

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

Frage

In rein funktionalen Sprachen, Daten unveränderlich ist. Mit Referenzzählung, erfordert einen Referenzzyklus Erstellung bereits erstellten Daten zu ändern. Es scheint, wie rein funktionalen Sprachen Referenzzählung, ohne sich Gedanken über die Möglichkeit der Zyklen nutzen könnten. Am ist richtig? Wenn ja, warum nicht wahr?

Ich verstehe, dass die Referenzzählung langsamer als GC ist in vielen Fällen, aber zumindest reduziert mal pausieren. Es wäre schön, die Möglichkeit zu haben, Referenzzählung in Fällen zu verwenden, wo Pausenzeiten sind schlecht.

War es hilfreich?

Lösung

Ihre Frage auf einer fehlerhaften Annahme beruht. Es ist durchaus möglich, zirkuläre Referenzen und unveränderliche Daten zu haben. Betrachten Sie das folgende Beispiel C #, die unveränderlichen Daten verwendet einen zirkulären Verweis zu erstellen. 

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

Diese Art von Trick kann in vielen funktionalen Sprachen und daher ist jeder Sammelmechanismus muss mit der Möglichkeit der zirkulären Referenzen befassen erfolgen. Ich sage nicht, ein ref Zählmechanismus mit einer kreisförmigen Referenz unmöglich ist, nur, dass es behandelt werden muss.

Bearbeiten von ephemient

Als Reaktion auf den Kommentar ... das ist trivial in Haskell 

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

und kaum mehr Mühe in SML. 

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

Keine Mutation erforderlich.

Andere Tipps

Im Vergleich zu anderen verwalteten Sprachen wie Java und C #, rein funktionale Sprachen zuteilen wie verrückt . Sie verteilen auch Objekte unterschiedlicher Größe. Die schnellste bekannte Zuweisungsstrategie ist von zusammenhängenden freien Speicherplatz (manchmal auch als „Kindergarten“ genannt) zuzuweisen und ein Hardware-Register zu reservieren, um den nächsten verfügbaren freien Raum zu zeigen. Zuweisung aus dem Haufen so schnell wie Zuweisung von einem Stapel wird.

Referenzzählung ist grundsätzlich unvereinbar mit dieser Allokationsstrategie. Ref Zählen stellt Objekte auf freien Listen und nimmt sie wieder ab. Ref Zählen haben auch erheblich Gemeinkosten für die Aktualisierung ref Zählungen erforderlich als neue Objekte erstellt werden (die, wie oben, rein funktionale Sprachen zu tun wie verrückt vermerkt).

Referenzzählung neigt dazu, in Situationen wie diese wirklich gut zu tun:

  • Fast alle Heap-Speicher wird verwendet, Live-Objekte zu halten.
  • Allocation und Zeigerzuweisung ist selten im Vergleich zu anderen Operationen.
  • können Referenzen auf einem anderen Prozessor oder Computer verwaltet werden.

Um zu verstehen, wie die besten High-Performance-ref-Zählsysteme heute arbeiten, sieht die Arbeit von David Bacon und Erez Petrank .

Es gibt ein paar Dinge, glaube ich.

  • Es ist Zyklen : "let rec" in vielen Sprachen erlaubt "circular" Strukturen geschaffen werden. Davon abgesehen, ist Unveränderlichkeit in der Regel keine Zyklen bedeuten, aber das bricht die Regel.
  • Ref-Zählungen bei Listen sind schlecht : Ich weiß es nicht, dass die Referenzzählung Sammlung funktioniert gut mit z.B. lange einfach verknüpften Liste Strukturen, die Sie häufig in FP finden (zum Beispiel langsam, müssen tail-rekursive, um sicherzustellen, ...)
  • Andere Strategien haben Vorteile : Wie Sie verweisen auf andere GC-Strategien sind nach wie vor in der Regel besser für Speicherlokalizität

(Es war einmal eine Zeit, die ich denke, dass ich vielleicht wirklich diese ‚wusste‘, aber jetzt versuche ich, daran zu erinnern, / zu spekulieren, so nehmen Sie dies nicht als eine Behörde.)

diese Allegorie über David Mond , ein Erfinder der Lisp-Maschine :

  

Eines Tages kam ein Student kam zu Mond und sagte: „Ich verstehe, wie eine bessere Garbage Collector machen wir einen Referenzzähler der Zeiger auf jede Nachteile halten müssen.“

     

Mond geduldig erzählte den Studenten die folgende Geschichte:

     
    

"Ein Tag kommt ein Student kam zu Mond und sagte:‚Ich verstehe, wie eine bessere Garbage Collector machen ...

  
  

Am ist richtig?

Nicht ganz. Sie können durch die Definition für beide Seiten rekursiven Werte zugleich mit rein funktionalen Programmierung einfach zyklische Datenstrukturen erstellen. Zum Beispiel in OCaml: 

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

Es ist jedoch möglich, Sprachen zu definieren, die es unmöglich machen, durch Design zyklische Strukturen zu schaffen. Das Ergebnis wird als a unidirektionalen heap und sein Hauptvorteil ist, dass die Garbage Collection als Referenzzählung so einfach sein kann.

  

Wenn ja, warum nicht wahr?

Einige Sprachen werden Zyklen verbieten und Referenzzählung verwenden. Erlang und Mathematica sind Beispiele.

Zum Beispiel in Mathematica, wenn Sie Referenz ein Wert, den Sie eine tiefe Kopie machen es so die ursprünglichen mutiert mutiert nicht die Kopie: 

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}

Referenzzählung ist viel langsamer als GC, weil es für die CPU nicht gut ist. Und GC die meiste Zeit für Leerlaufzeit warten und kann auch GC gleichzeitig sein (auf einem anderen Thread). Also das ist das Problem -. GC ist am wenigsten schlecht und viele Versuche gezeigt, dass

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top