Wie kommen rein funktionale Compiler zum AST mit Typinfo?

Wie beim Umgang mit relationalen Datenbanken ist es in der funktionalen Programmierung oft sinnvoll, nicht alles in eine einzige Datenstruktur zu bringen.

Insbesondere gibt es möglicherweise keine Datenstruktur, die "der AST" ist.

Sehr wahrscheinlich gibt es Datenstrukturen, die geparste Ausdrücke darstellen. Ein möglicher Weg, mit Typinformation umzugehen, besteht darin, jedem Knoten des Baumes bereits während der Analyse einen eindeutigen Identifizierer (wie eine ganze Zahl) zuzuweisen und eine geeignete Datenstruktur (wie eine Hash-Karte) zu haben, die diese Knoten-IDs mit Typen assoziiert. Der Job des Typ-Inferenz-Durchlaufs wäre dann nur, diese Map zu erstellen.

Normalerweise überschreibe ich eine Quelle (oder eine bereits mehrere Schritte tiefer) AST in ein neues Formular und ersetze jeden expression Knoten durch ein Paar (tag, expression) .

Tags sind eindeutige Zahlen oder Symbole, die dann vom nächsten Durchlauf verwendet werden, der vom AST folgende Typgleichungen ableitet. Zum Beispiel ergibt a + b etwas wie { numeric(Tag_a). numeric(Tag_b). equals(Tag_a, Tag_b). equals(Tag_e, Tag_a). }.

Dann werden die Typengleichungen gelöst (z. B. indem sie einfach als Prolog-Programm ausgeführt werden), und wenn sie erfolgreich sind, werden alle Tags (die Variablen in diesem Programm sind) nun an konkrete Typen gebunden, und wenn nicht, werden sie als Typparameter zurückgelassen.

In einem nächsten Schritt wird unser vorheriger AST erneut umgeschrieben, wobei diesmal die Tags durch alle abgeleiteten Typinformationen ersetzt werden.

Der ganze Prozess ist eine Sequenz von reinen Umschreibungen, keine Notwendigkeit, irgendetwas in Ihrem AST zerstörend zu ersetzen. Eine typische Kompilierungspipeline kann einige Dutzend Umschreibungen erfordern, von denen einige den AST-Datentyp ändern.

Es gibt mehrere Möglichkeiten, dies zu modellieren. Sie können die gleiche Art von Nullwert-Datenfeldern wie im Imperativ verwenden:

oder sogar, mit einem genaueren Typ

Ich kann nicht dafür sprechen, wie angenommen ist, aber ich habe das in F # für einen C # -Compiler gemacht hier

Der Ansatz war im Grunde genommen - erstelle einen AST von der Quelle und lasse Dinge wie Typinformationen unbeschränkt. Also ist AST.fs im Grunde der AST, der nach Typnamen, Funktionsnamen usw. stringt.

Wenn die AST in (in diesem Fall) .NET IL kompiliert wird, erhalten wir mehr Typinformation (wir erzeugen die Typen in der Quelle - lasst diese Typen-Stubs aufrufen). Dies gibt uns dann die Informationen, die benötigt werden, um Methoden-Stubs zu erzeugen (der Code kann Signaturen aufweisen, die Typ-Stubs sowie eingebaute Typen enthalten). Von hier aus haben wir jetzt genügend Typinformationen, um einen der Typnamen oder Methodensignaturen im Code aufzulösen.

Ich speichere das in der Datei TypedAST.fs. Ich mache das in einem einzigen Durchgang, aber der Ansatz mag naiv sein.

Jetzt haben wir einen vollständig getippten AST, mit dem Sie Dinge kompilieren, vollständig analysieren oder was immer Sie wollen.

Also in der Antwort auf die Frage " Bedeutet das, dass ich zwei Typen pro AST-Knoten definieren muss, einen für die Syntaxphase und einen für die semantische Phase? ", kann ich definitiv nicht sagen Dies ist der Fall, aber es ist sicherlich, was ich getan habe, und es scheint, dass MS mit Roslyn getan haben (obwohl sie im Wesentlichen den ursprünglichen Baum mit Typ Info IIRC geschmückt haben)

" Gibt es rein funktionale Programmiertricks, die dem Compilerschreiber bei diesem Problem helfen? " Angesichts der Tatsache, dass die ASTs in meinem Fall im Wesentlichen gespiegelt sind, wäre es möglich, sie generisch zu machen und den Baum zu transformieren, aber der Code kann am Ende (mehr) abscheulich sein.

d. h.