Warum erfordern funktionale Programmiersprachen die Garbage Collection?

14

Was hindert ghc daran, Haskell in eine verkettete Programmiersprache wie kombinatorische Logik zu übersetzen und dann einfach die Stapelzuweisung für alles zu verwenden? Laut Wikipedia ist die Übersetzung von Lambda-Kalkül in kombinatorische Logik trivial, und auch verkettete Programmiersprachen können sich bei der Speicherzuweisung ausschließlich auf einen Stapel stützen. Ist es möglich, diese Übersetzung zu machen und so die Garbage Collection für Sprachen wie Haskell und ocaml zu eliminieren? Gibt es Nachteile dabei?

BEARBEITEN: hierher verschoben /programming/39440412/why-do-functional-programming-languages-require-garbage-collection

functional-programming haskell Nicholas Grasevski
quelle
Die Cat-Programmiersprache sieht aus wie ein Beispiel für eine funktionsbasierte Stack-Sprache.
Petr Pudlák
1
Dies ist keine Frage auf Forschungsebene, da die Speicherbereinigung in Grundkursen zu Programmiersprachen (und deren Notwendigkeit) behandelt wird. Bitte gehen Sie zu cs.stackexchange.com
Andrej Bauer
Mein Fehler. Kennen Sie die Antwort auf meine Frage?
Nicholas Grasevski
5
Ich denke, es gibt eine Antwort auf Forschungsniveau auf diese Frage, da ich mich daran erinnere, dass ich während meiner Studienjahre damit gekämpft habe: Alles in einer Sprache wie Haskell sieht aus wie eine Funktionsanwendung, die auf dem Stapel lebt. Ich denke zu erklären, warum Verschlüsse notwendig sind, warum sie auf dem Haufen leben und was "Daten, die dem Funktionsumfang entgehen", damit zu tun haben, wäre eine sehr informative Antwort (die ich nicht unbedingt geben kann, Unglücklicherweise).
Cody
2
λ

Antworten:

16

Alle folgenden Kommentare basieren auf der Wahl einer Standardimplementierungsstrategie unter Verwendung von Closures zur Darstellung von Funktionswerten und einer Call-by-Value-Evaluierungsreihenfolge:

  1. Für die reine Lambda-Rechnung ist keine Speicherbereinigung erforderlich. Dies liegt daran, dass es nicht möglich ist, Zyklen im Heap zu bilden: Jeder neu zugewiesene Wert kann nur Verweise auf zuvor zugewiesene Werte enthalten. Daher bildet der Speichergraph eine DAG. Die Referenzzählung ist also ausreichend, um den Speicher zu verwalten.

  2. Die meisten Implementierungen verwenden aus zwei Gründen keine Referenzzählung.

    1. Sie unterstützen eine Form von Zeigertyp ( zum Beispiel des refTypkonstruktor in ml) gelöst und so wahr Zyklen in dem Haufen gebildet werden.
    2. Die Referenzzählung ist viel weniger effizient als die Speicherbereinigung, da
      • Es erfordert viel zusätzlichen Platz, um die Referenzzählungen beizubehalten
      • das Aktualisieren der Zählungen ist normalerweise vergeudete Arbeit, und
      • Die Aktualisierungen der Zählungen erzeugen eine Reihe von Schreibkonflikten, die die parallele Leistung beeinträchtigen.

  3. Durch linear getippte Sprachen kann die Referenzanzahl eliminiert werden (im Wesentlichen, weil die Anzahl 0-1 beträgt: Entweder hat der Wert eine einzige Referenz oder er ist tot und kann freigegeben werden).

  4. Die Stapelzuordnung reicht jedoch immer noch nicht aus. Dies liegt daran, dass es möglich ist, Funktionswerte zu bilden, die sich auf freie Variablen beziehen (dh, wir müssen Funktionsabschlüsse implementieren). Wenn Sie Dinge auf dem Stapel zuordnen, können Live-Werte mit toten Werten verschachtelt werden, was zu einer falschen asymptotischen Wirkung führt Raumnutzung.

  5. Sie können die richtige Asymptotik erzielen, indem Sie einen Stapel durch einen "Spaghetti-Stapel" ersetzen (dh den Stapel als verknüpfte Liste im Heap implementieren, sodass Sie bei Bedarf tote Rahmen ausschneiden können).

  6. Wenn Sie eine echte Stapeldisziplin wünschen, können Sie Typsysteme verwenden, die auf "geordneter Logik" basieren (im Wesentlichen lineare Typen minus Austausch).

Neel Krishnaswami
quelle
2
Ist nicht der grundlegendere Grund für (2), dass Implementierungen - auch ohne beobachtbare Nebenwirkungen - einen effizienten Operator für (gegenseitige) Rekursion haben möchten, dh einen, der tatsächlich einen Zyklus im Haufen bildet?
Andreas Rossberg
@andreasrossberg: Ich habe darüber nachgedacht, dies zu erwähnen, habe es jedoch weggelassen, da Sie den y-Kombinator für die Rekursion verwenden können.
Neel Krishnaswami