Verwenden alle funktionalen Sprachen die Garbage Collection?

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

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.

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

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.