Verwenden alle funktionalen Sprachen die Garbage Collection?

32

Gibt es eine funktionale Sprache, die die Verwendung der Stapelsemantik ermöglicht - automatische deterministische Zerstörung am Ende des Gültigkeitsbereichs?

user467799
quelle
Deterministische Zerstörung ist wirklich nur bei Nebenwirkungen hilfreich. Im Kontext der reinen funktionalen Programmierung bedeutet dies nur, sicherzustellen, dass bestimmte (monadische) Aktionen immer am Ende einer Sequenz ablaufen. Abgesehen davon ist es einfach, eine funktionale verkettete Sprache zu schreiben , die keine Garbage Collection benötigt.
Jon Purdy
Ich interessiere mich für den Zusammenhang der Frage, was hat man mit dem otehr zu tun?
Mattnz
1
In einer funktionalen Sprache ohne Garbage Collection sehe ich nicht, wie strukturelles Teilen von unveränderlichen Datenstrukturen möglich ist. Es mag möglich sein, eine solche Sprache zu erstellen, aber ich würde sie nicht verwenden.
Dan_waterworth
Rust hat eine Reihe von Merkmalen, die gemeinhin als "funktional" eingestuft werden (zumindest werden sie gemeinhin in nicht-funktionalen Merkmalen als "funktional" bezeichnet). Ich bin gespannt, was da noch fehlt. Standardmäßig immut, Closures, func passing, prinzipielle Überladung, ADTs (noch keine GADTs), Pattern Matching, alles ohne GC. Was sonst?
Noein

Antworten:

10

Nicht, dass ich wüsste, obwohl ich kein Experte für funktionale Programmierung bin.

Dies scheint im Prinzip ziemlich schwierig zu sein, da Werte, die von Funktionen zurückgegeben werden, Verweise auf andere Werte enthalten können, die innerhalb derselben Funktion (auf dem Stack) erstellt wurden oder genauso einfach wie ein Parameter übergeben wurden oder auf die von einer übergebenen Funktion verwiesen wird als Parameter. In C wird dieses Problem dadurch behoben, dass baumelnde Zeiger (oder genauer gesagt undefiniertes Verhalten) auftreten können, wenn der Programmierer die Dinge nicht richtig ausführt. Das ist nicht die Art von Lösung, die funktionale Sprachdesigner befürworten.

Es gibt jedoch mögliche Lösungen. Eine Idee besteht darin, die Lebensdauer des Werts zusammen mit Verweisen auf den Werttyp zu einem Teil zu machen und typbasierte Regeln zu definieren, die verhindern, dass vom Stapel zugewiesene Werte von einem zurückgegebenen Wert zurückgegeben werden oder auf den von einem zurückgegebenen Wert verwiesen wird Funktion. Ich habe die Implikationen nicht durchgearbeitet, aber ich vermute, es wäre schrecklich.

Für monadischen Code gibt es eine andere Lösung, die (tatsächlich oder fast) monadisch ist und eine Art automatisch deterministisch zerstörtes IORef ergeben könnte. Das Prinzip ist, "Verschachtelungs" -Aktionen zu definieren. In Kombination (unter Verwendung eines assoziativen Operators) definieren diese einen Steuerungsfluss für die Verschachtelung - ich denke "XML-Element", wobei der äußerste linke Teil der Werte das äußere Paar aus Anfang und Ende des Tags darstellt. Diese "XML-Tags" definieren lediglich die Reihenfolge monadischer Aktionen auf einer anderen Abstraktionsebene.

Irgendwann (auf der rechten Seite der Kette der assoziativen Komposition) brauchen Sie eine Art Abschlusszeichen, um die Verschachtelung zu beenden - etwas, um das Loch in der Mitte auszufüllen. Das Erfordernis eines Abschlusszeichens bedeutet wahrscheinlich, dass der Operator für die Verschachtelungskomposition nicht monadisch ist, auch hier bin ich mir nicht ganz sicher, da ich die Details nicht durchgearbeitet habe. Da das Anwenden des Terminators lediglich eine Verschachtelungsaktion in eine komponierte normale monadische Aktion umwandelt, hat dies möglicherweise keine Auswirkungen auf den Operator für die Verschachtelungskomposition.

Viele dieser Sonderaktionen hätten einen Null-Schritt "End-Tag" und würden den Schritt "Start-Tag" mit einer einfachen monadischen Aktion gleichsetzen. Einige würden jedoch variable Deklarationen darstellen. Diese repräsentieren den Konstruktor mit dem Starttag und den Destruktor mit dem Endtag. So bekommt man so etwas wie ...

act = terminate ((def-var "hello" ) >>>= \h ->
                 (def-var " world") >>>= \w ->
                 (use-val ((get h) ++ (get w)))
                )

Übersetzen in eine monadische Komposition mit der folgenden Ausführungsreihenfolge, wobei jedes Tag (nicht Element) zu einer normalen monadischen Aktion wird ...

<def-var val="hello">  --  construction
  <def-var val=" world>  --  construction
    <use-val ...>
      <terminator/>
    </use-val>  --  do nothing
  </def-val>  --  destruction
</def-val>  --  destruction

Regeln wie diese könnten die Implementierung von RAII im C ++ - Stil ermöglichen. Die IORef-ähnlichen Verweise können sich aus ähnlichen Gründen wie normale IORefs der Monade nicht entziehen - die Regeln der assoziativen Komposition bieten keine Möglichkeit, dass der Verweis entkommt.

BEARBEITEN - ich hätte fast vergessen zu sagen - es gibt einen bestimmten Bereich, über den ich mir nicht sicher bin. Es ist wichtig sicherzustellen, dass eine äußere Variable grundsätzlich nicht auf eine innere Variable verweisen kann. Daher muss es Einschränkungen geben, was Sie mit diesen IORef-ähnlichen Referenzen tun können. Auch hier habe ich nicht alle Details durchgearbeitet.

Daher könnte Konstruktion zB eine Datei öffnen, deren Zerstörung sich schließt. Bauarbeiten könnten eine Steckdose öffnen, die Zerstörung verschließt. Grundsätzlich werden die Variablen wie in C ++ zu Ressourcenmanagern. Im Gegensatz zu C ++ gibt es jedoch keine Heap-zugewiesenen Objekte, die nicht automatisch zerstört werden können.

Obwohl diese Struktur RAII unterstützt, benötigen Sie noch einen Garbage Collector. Obwohl eine Verschachtelungsaktion Speicher zuordnen und freigeben kann und ihn als Ressource behandelt, gibt es immer noch alle Verweise auf (möglicherweise gemeinsam genutzte) Funktionswerte innerhalb dieses Speicherbereichs und an anderer Stelle. Angesichts der Tatsache, dass der Speicher einfach auf dem Stack zugewiesen werden kann, ohne dass ein Heap-Free erforderlich ist, ist die eigentliche Bedeutung (sofern vorhanden) für andere Arten der Ressourcenverwaltung.

Dies führt also dazu, dass die Ressourcenverwaltung im RAII-Stil von der Speicherverwaltung getrennt wird, zumindest in dem Fall, in dem RAII auf einem einfachen Verschachtelungsbereich basiert. Sie benötigen weiterhin einen Garbage Collector für die Speicherverwaltung, erhalten jedoch eine sichere und zeitnahe automatische deterministische Bereinigung anderer Ressourcen.

Steve314
quelle
Ich verstehe nicht, warum ein GC in allen funktionalen Sprachen erforderlich ist. Wenn Sie über ein RAII-Framework im C ++ - Stil verfügen, kann der Compiler diesen Mechanismus ebenfalls verwenden. Gemeinsame Werte sind für RAII-Frameworks kein Problem (siehe C ++ shared_ptr<>), Sie behalten jedoch die deterministische Zerstörung bei. Die eine Sache, die für RAII schwierig ist, sind zyklische Referenzen; RAII funktioniert einwandfrei, wenn es sich bei dem Besitzdiagramm um ein gerichtetes azyklisches Diagramm handelt.
MSalters
Die Sache ist, funktionaler Programmierstil basiert praktisch auf Closures / Lambdas / anonymen Funktionen. Ohne GC haben Sie nicht die gleiche Freiheit, Ihre Verschlüsse zu verwenden, sodass Ihre Sprache erheblich an Funktionalität verliert.
Kommensturm
@comingstorm - C ++ hat Lambdas (ab C ++ 11), aber keinen Standard-Garbage Collector. Die Lambdas tragen ihre Umgebung auch in einem Verschluss - und Elemente in dieser Umgebung können als Referenz übergeben werden, ebenso wie die Möglichkeit, dass Zeiger als Wert übergeben werden. Aber wie ich in meinem zweiten Absatz geschrieben habe, bietet C ++ die Möglichkeit, Zeiger baumeln zu lassen - es liegt in der Verantwortung der Programmierer (und nicht der Compiler oder Laufzeitumgebungen), sicherzustellen, dass dies niemals geschieht.
Steve314
@MSalters - Es ist mit Kosten verbunden, um sicherzustellen, dass niemals Referenzzyklen erstellt werden können. Es ist daher zumindest nicht trivial, die Sprache für diese Einschränkung verantwortlich zu machen. Das Zuweisen zu einem Zeiger wird wahrscheinlich zu einer zeitlich nicht konstanten Operation. In manchen Fällen ist dies jedoch immer noch die beste Option. Garbage Collection vermeidet dieses Problem mit unterschiedlichen Kosten. Den Programmierer verantwortlich zu machen, ist eine andere Sache. Es gibt keinen triftigen Grund, warum baumelnde Zeiger in imperativen, aber nicht funktionalen Sprachen in Ordnung sein sollten, aber ich empfehle trotzdem nicht, Zeiger-baumelnde-Haskell zu schreiben.
Steve314
Ich würde argumentieren, dass die manuelle Speicherverwaltung bedeutet, dass Sie nicht die gleiche Freiheit haben, C ++ 11-Verschlüsse zu verwenden wie Lisp- oder Haskell-Verschlüsse. (Eigentlich bin ich sehr daran interessiert, die Details dieses Kompromisses zu verstehen, da ich eine Programmiersprache für funktionale Systeme schreiben möchte ...)
comingstorm
3

Wenn Sie C ++ als funktionale Sprache betrachten (es hat Lambdas), dann ist dies ein Beispiel für eine Sprache, die keine Garbage Collection verwendet.

BЈовић
quelle
8
Was ist, wenn Sie C ++ nicht als funktionale Sprache betrachten (IMHO ist dies nicht der Fall, obwohl Sie ein funktionales Programm damit schreiben können, können Sie auch einige extrem nicht-funktionale (funktionierende ...) Programme damit schreiben)?
Mattnz
@mattnz Dann trifft die Antwort wohl nicht zu. Ich bin nicht sicher, was in anderen Sprachen passiert (wie zum Beispiel haskel)
BЈовић
9
Zu sagen, dass C ++ funktioniert, ist wie zu sagen, dass Perl objektorientiert ist ...
Dynamisch
Zumindest C ++ - Compiler können auf Nebenwirkungen prüfen. (via const)
tp1
@ tp1 - (1) Ich hoffe, dass dies nicht in die beste Sprache zurückgeht, und (2) das ist nicht wirklich wahr. Erstens sind die wirklich wichtigen Effekte meistens E / A. Zweitens blockiert const sie nicht, auch nicht bei Effekten auf das veränderbare Gedächtnis. Auch wenn Sie davon ausgehen, dass es keine Möglichkeit gibt, das Typensystem zu untergraben (in C ++ im Allgemeinen sinnvoll), gibt es das Problem der logischen Konstanz und des "veränderlichen" C ++ - Schlüsselworts. Grundsätzlich können Sie trotz const noch Mutationen haben. Es wird erwartet, dass Sie sicherstellen, dass das Ergebnis immer noch "logisch" identisch ist, jedoch nicht unbedingt dieselbe Darstellung.
Steve314
2

Ich muss sagen, dass die Frage ein bisschen unklar ist, weil davon ausgegangen wird, dass es eine Standardkollektion von "funktionalen Sprachen" gibt. Fast jede Programmiersprache unterstützt ein gewisses Maß an funktionaler Programmierung. Und fast jede Programmiersprache unterstützt ein gewisses Maß an Imperativ-Programmierung. Wo zieht man die Grenze, um zu sagen, welche eine funktionale Sprache und welche eine imperative Sprache ist, die sich nicht an kulturellen Vorurteilen und populären Dogmen orientiert?

Ein besserer Weg, die Frage zu formulieren, wäre: "Ist es möglich, funktionale Programmierung in einem Stapelspeicher zu unterstützen?". Die Antwort ist, wie bereits erwähnt, sehr schwierig. Ein funktionaler Programmierstil fördert die Zuordnung von rekursiven Datenstrukturen nach Belieben, was einen Heap-Speicher erfordert (unabhängig davon, ob Müll gesammelt oder Referenz gezählt wurde). Es gibt jedoch eine ziemlich ausgefeilte Compiler-Analysetechnik, die als bereichsbasierte Speicheranalyse bezeichnet wird und mit der der Compiler den Heap in große Blöcke aufteilen kann, die auf ähnliche Weise wie die Stapelzuweisung automatisch zugewiesen und freigegeben werden können. Die Wikipedia-Seite listet verschiedene Implementierungen der Technik auf, sowohl für "funktionale" als auch für "imperative" Sprachen.

Uday Reddy
quelle
1
IMO-Referenzzählung ist Garbage Collection, und ein Heap bedeutet nicht, dass dies ohnehin die einzigen Optionen sind. C mallocs und mfrees verwenden einen Heap, haben aber keinen (Standard-) Garbage Collector und nur Referenzzählungen, wenn Sie den Code dafür schreiben. C ++ ist fast dasselbe - es hat (in C ++ 11 standardmäßig) intelligente Zeiger mit eingebauter Referenzzählung, aber Sie können immer noch manuell neu erstellen und löschen, wenn Sie es wirklich brauchen.
Steve314
Ein häufiger Grund für die Behauptung, dass die Referenzzählung keine Garbage Collection ist, besteht darin, dass keine Referenzzyklen erfasst werden. Das gilt sicherlich für einfache Implementierungen (wahrscheinlich einschließlich intelligenter C ++ - Zeiger - ich habe es nicht überprüft), aber es ist nicht immer der Fall. Mindestens eine Java Virtual Machine (von IBM, IIRC) verwendete die Referenzzählung als Grundlage für die Garbage Collection.
Steve314