Warum ist das Schreiben eines Compilers in einer funktionalen Sprache einfacher? [geschlossen]

88

Ich habe sehr lange über diese Frage nachgedacht, konnte aber die Antwort bei Google und eine ähnliche Frage bei Stackoverflow wirklich nicht finden. Wenn es ein Duplikat gibt, tut mir das leid.

Viele Leute scheinen zu sagen, dass das Schreiben von Compilern und anderen Sprachwerkzeugen in funktionalen Sprachen wie OCaml und Haskell viel effizienter und einfacher ist als das Schreiben in imperativen Sprachen.

Ist das wahr? Und wenn ja - warum ist es so effizient und einfach, sie in funktionalen Sprachen anstatt in einer imperativen Sprache wie C zu schreiben? Auch - ist ein Sprachwerkzeug in einer funktionalen Sprache nicht langsamer als in einer einfachen Sprache wie C?

compiler-construction haskell ocaml functional-programming wvd
quelle
5
Ich würde nicht sagen, dass es einfacher ist. Aber die funktionale Natur des Kompilierens von Aufgaben wie dem Parsen eignet sich wahrscheinlich ganz natürlich für die funktionale Programmierung. Funktionale Sprachen wie OCaml können extrem schnell sein und mit der Geschwindigkeit von C
Robert Harvey
17
Leute, ist das wirklich argumentativ? Sicher hat jemand einen Einblick. Ich würde mich gerne kennenlernen.
Robert Harvey
Ich denke, es sollte zumindest einige gute Gründe geben, eine funktionale Sprache gegenüber einer zwingenden zu verwenden. Ich habe einen Artikel gefunden, der im Grunde darauf zurückzuführen ist, dass funktionale Sprachen keine Nebenwirkungen haben und so weiter. Aber es war überhaupt nicht klar. Wenn dies jedoch argumentativ ist, ist es möglicherweise besser, es zu schließen oder die Frage neu zu formulieren.
wvd
12
Ist es wirklich argumentativ anzuerkennen, dass einige Nischen besser für einen bestimmten Sprachstil geeignet sind? "Warum ist C besser als Javascript zum Schreiben von Gerätetreibern" wäre nicht umstritten, würde ich denken ...
CA McCann
1
Ich dachte, es wäre das Gegenteil. Ich lese "super tiny compiler" und es verwendet überall variable Mutationen.
Rolf

Antworten:

101

Oft arbeitet ein Compiler viel mit Bäumen. Der Quellcode wird in einen Syntaxbaum analysiert. Dieser Baum kann dann in einen anderen Baum mit Typanmerkungen umgewandelt werden, um eine Typprüfung durchzuführen. Jetzt können Sie diesen Baum in einen Baum konvertieren, der nur Elemente der Kernsprache enthält (syntaktische zuckerähnliche Notationen in eine nicht empfohlene Form konvertieren). Jetzt können Sie verschiedene Optimierungen durchführen, bei denen es sich im Grunde um Transformationen des Baums handelt. Danach würden Sie wahrscheinlich einen Baum in einer normalen Form erstellen und dann über diesen Baum iterieren, um den Zielcode (Assemblycode) zu erstellen.

Die funktionale Sprache verfügt über Funktionen wie Pattern Matching und eine gute Unterstützung für eine effiziente Rekursion, die das Arbeiten mit Bäumen vereinfachen. Deshalb gelten sie im Allgemeinen als gute Sprachen zum Schreiben von Compilern.

sepp2k
quelle
Bisher vollständigste Antwort, ich werde dies als akzeptierte Antwort markieren, aber ich denke, Pete Kirkhams Antwort ist auch gut.
wvd
1
Was ist mit "Korrektheit beweisen", da die Korrektheit eines Compilers ein wichtiges Attribut ist, habe ich oft gehört, dass Fans funktionaler Sprachen irgendwie einen "Korrektheitsnachweis" in ihren Workflow integrieren. Ich habe keine Ahnung, was das in der Praxis wirklich bedeutet, aber da die Zuverlässigkeit des Compilers wichtig ist, scheint dies sinnvoll zu sein.
Warren P
3
@WarrenP: Das Konzept des "Proof-Carry-Codes" stammt aus statisch typisierten Funktionssprachen. Die Idee ist, dass Sie das Typsystem so verwenden, dass eine Funktion nur dann tippen kann, wenn sie korrekt ist. Die Tatsache, dass der Code kompiliert wird, ist also der Beweis für die Richtigkeit. Natürlich ist dies nicht vollständig möglich, während die Sprache vollständig und die Typüberprüfung entscheidbar bleibt. Aber je stärker das Typsystem ist, desto näher kann man diesem Ziel kommen.
sepp2k
3
Der Grund, warum dieses Konzept hauptsächlich in der Funktionsgemeinschaft beliebt ist, besteht darin, dass Sie in Sprachen mit veränderlichem Status auch Informationen darüber codieren müssen, wann und wo Statusänderungen in den Typen auftreten. In Sprachen, in denen Sie wissen, dass das Ergebnis einer Funktion nur von ihren Argumenten abhängt, ist es viel einfacher, einen Beweis in den Typen zu codieren (es ist auch viel einfacher, die Korrektheit des Codes manuell zu prüfen, da Sie nicht berücksichtigen müssen, welcher globale Status vorliegt möglich und wie sich dies auf das Verhalten der Funktion auswirkt). Nichts davon bezieht sich jedoch speziell auf Compiler.
sepp2k
3
Das wichtigste Merkmal ist meiner Meinung nach der Mustervergleich. Das Optimieren eines abstrakten Syntaxbaums mit Mustervergleich ist blöd einfach. Es ist oft frustrierend schwierig, es ohne Mustervergleich zu machen.
Bob Aman
38

Viele Compiler-Aufgaben sind Mustervergleiche in Baumstrukturen.

Sowohl OCaml als auch Haskell verfügen über leistungsstarke und präzise Mustervergleichsfunktionen.

Es ist schwieriger, den imperativen Sprachen einen Mustervergleich hinzuzufügen, da jeder Wert, der ausgewertet oder extrahiert wird, um das Muster abzugleichen, nebenwirkungsfrei sein muss.

Pete Kirkham
quelle
Klingt nach einer vernünftigen Antwort, aber ist das das einzige? zB würden auch dinge wie schwanzrekursion eine rolle spielen?
wvd
Dies scheint darauf hinzudeuten, dass es sich eher um ein Problem des Typsystems als um das tatsächliche Ausführungsmodell handelt. Etwas, das auf einer imperativen Programmierung mit unveränderlichen Werten über Strukturtypen basiert, könnte in Ordnung sein.
Donal Fellows
@wvd: Die Endrekursionsoptimierung ist ein Implementierungsdetail und kein Sprachmerkmal als solches, das lineare rekursive Funktionen einer iterativen Schleife entspricht. Eine rekursive Funktion zum Durchlaufen einer verknüpften Liste in C würde genauso davon profitieren wie das Rekursieren in einer Liste in Schema.
CA McCann
@wvd gcc C hat Tail Call Elimination, wie auch andere veränderbare Staatssprachen
Pete Kirkham
3
@camccann: Wenn der Sprachstandard tco garantiert (oder zumindest garantiert, dass rekursive Funktionen einer bestimmten Form niemals einen Stapelüberlauf oder ein lineares Wachstum des Speicherverbrauchs verursachen), würde ich dies als Sprachfunktion betrachten. Wenn der Standard dies nicht garantiert, der Compiler es jedoch trotzdem tut, handelt es sich um eine Compilerfunktion.
sepp2k
15

Ein wichtiger Faktor ist, dass ein großer Teil jedes Compiler-Projekts darin besteht, dass Sie den Compiler selbst hosten und "Ihr eigenes Hundefutter essen" können. Aus diesem Grund bieten Sprachen wie OCaml, in denen sie für die Sprachforschung entwickelt wurden, in der Regel hervorragende Funktionen für Probleme vom Typ Compiler.

In meinem letzten compilerähnlichen Job haben wir OCaml aus genau diesem Grund verwendet, während wir C-Code manipulierten. Es war einfach das beste Werkzeug für diese Aufgabe. Wenn die Leute von INRIA OCaml mit unterschiedlichen Prioritäten gebaut hätten, wäre es vielleicht nicht so gut gewesen.

Das heißt, funktionale Sprachen sind das beste Werkzeug zur Lösung eines Problems, daher folgt logischerweise, dass sie das beste Werkzeug zur Lösung dieses speziellen Problems sind. QED.

/ me: kriecht etwas weniger freudig zu meinen Java-Aufgaben zurück ...

Ukko
quelle
4
-1 für "funktionale Sprachen sind das beste Werkzeug zur Lösung eines Problems." Wenn dies wahr wäre, würden wir sie alle überall verwenden. ;)
Andrei Krotkov
15
@Andrei Krotkov: Das heutige Wort des Tages ist fehlerhaft Aussprache: \ fə-ˈsē-shəs \ Funktion: Adjektiv Etymologie: Mittelfranzösischer Facetieux, aus Facettenscherz, aus lateinischen Facetten Datum: 1599 1: Scherzen oder Scherzen oft unangemessen : waggish <nur scherzhaft sein> 2: soll humorvoll oder lustig sein: nicht ernst <a scherzhafte Bemerkung> Synonyme sehen witzig Abgesehen davon, dass Sie den Witz verpasst haben, ist Ihre Logik immer noch fehlerhaft. Sie gehen davon aus, dass alle Menschen rationale Akteure sind und dass ich befürchte, dass dies keine faire Annahme ist.
Ukko
5
Ich glaube, ich habe den Witz verpasst, da ich Leute im wirklichen Leben kenne, die so ziemlich genau das sagen würden, außer ganz ernst. Poes Gesetz, denke ich.tvtropes.org/pmwiki/pmwiki.php/Main/PoesLaw
Andrei Krotkov
13
@Andrei: Verwenden Sie Ihr argumentum ad populum : "Wenn die Vernunft besser ist als emotionale Ignoranz, würden wir sie alle überall verwenden."
Tim Schaeffer
9

Grundsätzlich ist ein Compiler eine Transformation von einem Codesatz zu einem anderen - von Quelle zu IR, von IR zu optimiertem IR, von IR zu Assembly usw. Genau dafür sind funktionale Sprachen konzipiert - eine reine Funktion ist nur eine Transformation von einer Sache zur anderen. Imperative Funktionen haben diese Qualität nicht. Obwohl Sie diese Art von Code in einer zwingenden Sprache schreiben können, sind funktionale Sprachen darauf spezialisiert.

Futter
quelle
6

Siehe auch

F # Designmuster

FP gruppiert Dinge 'nach Operation', während OO Dinge 'nach Typ' gruppiert und 'nach Operation' für einen Compiler / Interpreter natürlicher ist.

Brian
quelle
3
Dies bezieht sich auf das, was in einigen Kreisen der Programmiersprachtheorie als "Ausdrucksproblem" bezeichnet wird. Siehe zum Beispiel diese Frage , in der ich einen wirklich schrecklichen Haskell-Code demonstriere, der Dinge auf die Art "erweiterbarer Typen" macht. Im Gegensatz dazu motiviert das Erzwingen einer OOP-Sprache in den Stil "erweiterbare Operationen" das Besuchermuster.
CA McCann
6

Eine Möglichkeit besteht darin, dass ein Compiler dazu neigt, sehr sorgfältig mit einer ganzen Reihe von Eckfällen umzugehen. Die Richtigkeit des Codes wird häufig durch die Verwendung von Entwurfsmustern erleichtert, die die Implementierung so strukturieren, dass sie den implementierten Regeln entsprechen. Oft ist dies eher ein deklaratives (Mustervergleich, "wo") als ein imperatives (Sequenzierung, "wann") Design und daher einfacher in einer deklarativen Sprache zu implementieren (und die meisten von ihnen sind funktional).

BCS
quelle
4

Scheint, als hätten alle einen anderen wichtigen Grund verpasst. Es ist ziemlich einfach, eine eingebettete domänenspezifische Sprache (EDSL) für Parser zu schreiben, die (E) BNF im normalen Code sehr ähnlich sehen. Parser-Kombinatoren wie Parsec lassen sich mit Funktionen höherer Ordnung und Funktionszusammensetzung recht einfach in funktionalen Sprachen schreiben. Nicht nur einfacher, sondern auch sehr elegant.

Grundsätzlich stellen Sie nur den einfachsten generic - Parser als nur Funktionen und Sie haben spezielle Operationen ( in der Regel Funktionen höhere Ordnung) , die können Sie komponieren , diese primitiven Parser in kompliziertem, spezifischen Parser für die Grammatik.

Dies ist natürlich nicht die einzige Möglichkeit, Parer-Frameworks zu erstellen.

snk_kid
quelle