Compiler-Backend für eine funktionale Sprache

Question

Ich habe einen Interpreter für eine funktionale Sprache geschrieben, die ich versuche, mit einem Compiler bootstrap. Die Sprache hat ein dynamisches System und verwendet Listen, Zahlen und Strings. Es ist auch funktional und eine Funktion nimmt ihre Argumenta als Liste (wie perls @_ oder js Argumente). Funktionen sind erste Klasse und können geschachtelt werden. Welche Sprache soll ich mit dem Compiler ansprechen, btw. Ich denke, eine statische typisierte Imperativsprache anzusprechen, wie C wäre schwierig. Die Sprache sollte dynamische Typisierung und funktionale Programmierung unterstützen (js wäre nicht nett - die Sprache sollte einen Compiler selbst haben, wie geläufiges Lisp)

Answer 1

Sie benötigen keine spezielle Unterstützung von Ihrer Zielsprache. Der dynamische Versand kann mit generischen Versionen Ihrer Funktionen gelöst werden (aber überlegen Sie, ob Sie die Typen sicher ableiten können), z. B. für a + b können Sie einen Code wie generic_add(a, b) generieren, wobei generic_add eine Funktion ist, die eine geeignete Implementierung auswählt Informationen zum Laufzeittyp.

Für den funktionellen Teil ist es einfach, ihn durch Lambda-Lifting zu eliminieren. Für letzteres müssen Sie einfach Listen von freien und gebundenen Variablen für jeden AST-Knoten erstellen: Eine Liste freier Variablen wird von den Blättern zum Stamm erstellt, und eine gebundene Liste wird in der entgegengesetzten Richtung aufgebaut. Für jeden Lambda-Knoten subtrahieren Sie frei von der Grenze und erstellen eine neue Funktion der obersten Ebene, die sowohl explizite Lambda-Argumente als auch diese Differenz (d. H. Die erfassten Variablen) annimmt.

Wenn Sie Optimierungen durchführen möchten oder wenn Ihre Sprache Fortsetzungen unterstützen soll, sollten Sie eine CPS-Transformation verwenden.

Answer 2

Das Targeting von Low-Level-Sprachen wie LLVM und C ist in Ordnung, solange Sie bereit sind, dynamischen Versand, Schließungen usw. selbst zu implementieren. Da Sie jedoch JavaScript als mögliches Ziel angeben (außer dem Mangel an Compilern, obwohl selbst JS in heutigen Hauptbrowsern JIT-kompiliert wird), wie wäre es mit Scheme? Es ist eine dynamisch typisierte, funktionale Sprache höherer Ordnung und hat bereits native Code-Compiler: http://community.schemewiki.org/?scheme-faq-standards#implementations Das einzige Problem könnte sein, dass es zu nah an Ihrer Ausgangssprache ist und Ihr Compiler (oder "Übersetzer", könnte ich sagen) wäre auch vielleicht einfach :-)

Wenn Sie bereit sind, C, ein guter Ausgangspunkt zum Ziel kann Marc Feeley Tutorial "das 90 Minuten Schema zu C-Compiler" sein. http://churchturing.org/y/90-min-scc.pdf