Brauchte 1+1, baute eine funktionale Programmiersprache
Needed 1+1, built a functional programming language
Aus einer einfachen Data-Structures-Aufgabe – einen arithmetischen Ausdruck in einen Binärbaum umzuwandeln – wurde ein komplettes Sprachprojekt. Der Autor implementierte in C einen Evaluator, Closures, einen Garbage Collector, einen Arena- und Chunk-Allocator, ein REPL und ein FFI. Der Artikel beschreibt die Reise von einem naiven Tagged-Union-Node über Speicherprobleme (fib(40) verbrauchte 12+ GB) bis hin zu einem funktionierenden Interpreter namens graphLang.
Fib(40) brauchte buchstäblich über 12 Gigabyte, bevor es einen OOM-Fehler bekam und abstürzte.
- CodesInChaos
Greenspuns zehnte Regel der Programmierung:
> Jedes ausreichend komplizierte C- oder Fortran-Programm enthält eine ad-hoc, informell spezifizierte, von Fehlern durchsetzte, langsame Implementierung von halb Common Lisp.
- tromp
> Insgesamt habe ich eine Graph Reduction engine gebaut
Ich habe dasselbe für meine performante Implementierung der rein funktionalen Programmiersprache BLC/BLC2 gemacht,
die in über 400 Zeilen eine Graph Reduction engine für Kombinatorische Logik enthält, in die die Lambda-Kalkül-Programme durch Kiselyovs Bracket-Abstraktionsalgorithmus umgewandelt werden.
- heronbank
Nachvollziehbar. Habe eine Woche damit verbracht, eine Abfrage zu optimieren, die zweimal im Jahr für einen Bericht läuft, den niemand liest. Der Kaninchenbau ist real.
- gnarlouse
Das erinnert mich an Jahrzehnte vor ... Moment, ich habe noch vor etwa drei Jahren Code wie diesen geschrieben.
- Joker_vD
> Die Sache ist die: Alle unsere Knoten zeigen innerhalb dieses Speicherblocks aufeinander. Wenn wir ihn mit vergrößerter Größe reallokieren, könnte er an eine neue Speicheradresse verschoben werden. Das bricht komplett alle unsere Zeiger und verursacht einen Segfault! Wie gehen wir dieses Problem an?
Indizes in das Arena-Array speichern? Du könntest wahrscheinlich sogar 4-Byte-Indizes verwenden und den Speicherverbrauch senken...
> Fib(40) brauchte buchstäblich 12+ GIGABYTE, bevor es einen OOM erreichte und abstürzte. Warum? Weil es ungefähr 1,3 Milliarden Knoten erzeugt.
Okay, vielleicht kannst du 8-Byte-Indizes behalten.
> Der Mark-and-Sweep-Garbage-Collector, den wir gerade fertiggestellt haben, ist ein Stop-the-World-Garbage-Collector. Und der Algorithmus, den wir ausführen, ist inhärent exponentiell.
Wie wäre es dann mit einem Copying-Collector? Das rekursive Fibonacci erzeugt viel Müll, aber IIRC ist sein Live-Set zu jedem einzelnen Zeitpunkt tatsächlich ziemlich klein. Wenn du einen Benchmark für GC brauchst, wenn deine Funktion tatsächlich ein riesiges Live-Set hat, dann sollte etwas wie
def garbage(n):
if n == 0:
return None
return (garbage(n-1), garbage(n-1))
den Trick tun; wenn du keine richtige Datenstruktur hast, kannst du das mit Closures ziemlich trivial simulieren.
> Und wir können etwas daran ändern, wie wir fib selbst auswerten
Du meinst "vom rekursiven Durchlaufen des AST wechseln" oder "ein nicht-exponentielles Fibonacci schreiben"?