Wie funktioniert ein Haskell-Compiler?

Question

Wo kann ich etwas Papier/Dokument/was auch immer bekommen, das beschreibt, wie ein Haskell-Compiler tatsächlich funktioniert? Ich habe einige der Dokumente von GHC gelesen, aber nach Kopfschmerzen gestoppt. Also, etwas, das keine Doktorarbeit benötigt, um es zu verstehen und nicht in dem Du-soll-schon-schon-vertraut-mit-ihr-Stil geschrieben wäre, wäre vorzuziehen. Es ist kein Problem, wenn es wirklich lang ist und einige Zeit braucht, um es zu verstehen.

PS: Am interessantesten wäre etwas über GHC, aber alles ist in Ordnung.

Answer 1

Sie können eine Antwort vom Maul des Pferdes bekommen! Simon Peyton Jones (GHC-Assistent) hat ein Buch geschrieben, in dem erklärt wird, wie funktionale Programmiersprachen implementiert werden können. Es ist kostenlos online verfügbar, da es jetzt vergriffen ist: http://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/

Natürlich ist GHC weitergegangen, seit das Buch geschrieben wurde, aber es ist immer noch sehr relevant.

Answer 2

Leider vermute ich, dass das, was Sie suchen, nicht existiert. Compiler-Theorie und formale Sprachtheorie sind ziemlich komplexe Themen in der Informatik, und Haskell ist keineswegs ein Ausgangspunkt.

Zuerst sollten Sie wahrscheinlich eine gute Erdung in erhalten:

• Lexical Analyse: http://en.wikipedia.org/wiki/Lexical_analysis
• Parsing: http://en.wikipedia.org/wiki/Parsing#Programming_languages
  • Context Free (und andere) Grammar Systeme (CFG, BNF)
• Codegenerierung: http://en.wikipedia.org/wiki/Code_generation_(compiler)

Ich würde vermuten, dass alles, was etwas über die Interna von Haskell erklärt, ein wesentlich besseres Verständnis der oben genannten Themen erfordern würde, als C sagen würde.

Ich habe bisher einen einzigen Kurs zu diesem Thema gemacht, daher habe ich keine formelle Literatur zu empfehlen, aber ich bin mir sicher, dass es viele gute Quellen gibt.

Answer 3

Compiler sind ein riesiges Thema und es wäre unmöglich, sie hier vollständig zu erklären. Aber hier ist eine Übersicht für einen allgemeinen Compiler. Hoffentlich wird dies Ihnen ein Verständnis geben, das das Lesen von Dingen über GHC etwas leichter verständlich macht.

Compiler arbeiten in der Regel durch eine Reihe von Transformationen in 2 Teilen, dem Front-End und Back-End.

Die erste Umwandlung verwandelt Klartext in etwas leichter zu durchqueren. Dies selbst ist normalerweise in zwei Teile aufgeteilt:

Lexical Analysis or Tokenization - Die Handlung der Umwandlung von Klartext in kleine Stücke (in der Regel Operatoren, Bezeichner, Literale usw.).

Syntactic Analysis or Parsing - Diese kleinen Brocken in eine Baumstruktur verwandeln. (typischerweise ein AST, an Abstract Syntax Tree)

Die nächste Stufe ist semantische Analyse. In dieser Phase fügt ein Compiler normalerweise Informationen zum AST hinzu (wie Typinformationen) und erstellt eine Symboltabelle. Damit ist das Frontend abgeschlossen.

Die nächste Umwandlung wandelt den AST in einen IR, an Intermediate Representation um. Dies ist in der Regel heute an SSA form, a Single Static Assignment.

Dies wird dann optimiert, über Konstantenpropagation Dead Code Analyse, Vektorisierung usw.

Die letzte Transformation Codegenerierung. Transformieren der IR in Maschinencode. Dies kann sehr kompliziert sein. Es wird manchmal auch als Absenkung bezeichnet.

Für weitere Informationen empfehle ich this wikipedia page.

Answer 4

Sind Sie auf der Suche nach Details speziell zum Kompilieren von Lazy-Evaluation? Es Simon Peyton-Jones ist Buch von Max Bolingbroke erwähnt, auch das Buch Saubere Implementierung Detaillierung ist online:

http://wiki.clean.cs.ru.nl/Functional_Programming_and_Parallel_Graph_Rewriting

Wenn Sie eine Hochschulzugehörigkeit haben und wollen etwas kleiner Sie könnten versuchen, diese Bücher zu bekommen (Henderson & Diller sind sicherlich vergriffen):

Antoni Diller "Übersetzen Funktion Sprachen" ISBN 0 471 92027 4

Peter Henderson "Functional Programming Anwendung und Implementation" ISBN 0-13-331579-7

AJT Davie "Eine Einführung in die funktionale Programmierung Systeme mit Haskell" ISBN 0 521 27724 8

Diller hat einen vollen Compiler für einen faulen Sprache (implementiert in Pascal) über combinator Reduktion. Dies war die von David Turner für SASL erfundene Implementierungstechnik. Henderson hat viele Teile eines Compilers für LISPkit, eine faule Variante von Lisp. Davie stellt ziemlich viel von der Maschinerie zur Verfügung, um eine faule Sprache zu kompilieren, zum Beispiel gibt es eine Beschreibung der STG, die viel kürzer ist als das Buch von Simon Peyton-Jones (die STG ist die abstrakte Maschine SPJ, die für Haskell verwendet wird).

Die Clean-Entwickler haben ziemlich viel Informationen über die Umsetzung SAPL (eine einfache Applicative Language), wenn Sie ihre Publikationsliste durchsehen:

http://www.st.cs.ru.nl/Onderzoek/Publicaties/publicaties.html

schließlich eine ganze Reihe von Papieren gibt es dokumentieren Aspekte der Utrecht Haskell Compiler UHC (und EHC). Ich denke, die meisten Informationen sind, wie der Compiler organisiert ist (mit Attributgrammatiken und "Shuffle") und wie die Typsysteme (es gibt verschiedene Ebenen des Typsystems in EHC) implementiert sind, anstatt wie die Backend-Kompilierung funktioniert.

Answer 5

Wikipedia hat einen guten - lesbar - Überblick über die Interna des GHC (ähnlich @ dan_waterworth Erklärung, aber spezifisch für Haskell und die GHC):

http://en.wikipedia.org/wiki/Glasgow_Haskell_Compiler#Architecture