Ich arbeite zur Zeit an einem Compiler für funktionale Compiler mit dem Ziel, typbezogene Dinge und leicht fortgeschrittene Techniken in Haskell zu lernen.
Ich glaube, ich muss an jeden Knoten in meinem Baum Informationen anhängen, wie Position im ursprünglichen Quellcode für eine bessere Fehlerberichterstattung, Typ abgeleitete, generierte Typabhängigkeiten usw. Also wählte ich zunächst diese Methode:
%Vor% Functor wird abgeleitet, um den angehängten Knoten effektiv zu transformieren, während Generic1 einer generischen Funktion erlaubt, diese Information herauszuholen.
Nachdem ich den Parser fertiggestellt habe, fand ich die Struktur für die zukünftige Verarbeitung etwas unfreundlich. Im Wesentlichen möchte ich eine zweischichtige Struktur, wie die hier . Etwas, was ich versuche:
%Vor%Die anfängliche Motivation ist für einen bequemeren / schöneren Mustervergleich, da die unnötige Information getrennt werden kann. Außerdem habe ich gerade eine sanfte Einführung in das Rekursionssystem gelesen, also hoffe ich, dass ich Vorteile nutzen könnte der vorhandenen Bibliothek.
Der obige Code, den ich versuchte, wurde jedoch von GHC abgelehnt. Genauer gesagt, ich kann es nicht verwenden, um Eq instance automatisch abzuleiten. Ich habe eine komplizierte Standalone-Ableitung ausprobiert:
Aber es wird abgelehnt, nachdem mehrere ausgefallene Erweiterungen aktiviert wurden. Ich habe bemerkt, dass die recursion-scheme -Bibliothek den folgenden Code hat:
Aber ich konnte die Instanz nicht verstehen - wie werden wir Eq (f (Fix f)) befriedigen?
Ich habe bemerkt, dass im Blog von ezyang, der AST-Typisierungsansätze behandelt, er verwendet:
%Vor% Aber ich habe verschiedene Arten von Knoten in Expr , z. Muster und Deklarationen.
Meine Frage ist:
Eq und Show Instanzen ableiten? Danke!
Eine Eq -Instanz für Expr w ist glücklicherweise relativ einfach zu schreiben. Beim Schreiben einer Eq -Instanz würden wir normalerweise nach einer Eq -Instanz für alle Typen fragen, die im Datentyp verwendet werden. Zum Beispiel, wenn wir eine Eq -Instanz für
Wir würden nach einer Möglichkeit fragen, a s und b s
Wenn ein Typ höherwertig ist ...
%Vor% ... wir bitten Sie immer noch um einen Vergleich aller Typen, die irgendwo in E
Das Gleiche kann rekursiv getan werden, und es wird nach einer Möglichkeit gefragt, die inneren Typen zu vergleichen, wenn man den Datentyp vergleicht. Rekursive Einschränkungen erfordern zusätzlich zu den oben verwendeten Erweiterungen UndecidableInstances .
Dies ist auch der Code der Rekursionschemata für Fix , aber der einzige Typ, der in Fix verwendet wird, ist f (Fix f) , daher sieht die Einschränkung magisch aus.
Eine Eq Instanz für Expr w wird auf die gleiche Weise geschrieben. Die Einschränkung fragt nach einer Möglichkeit, die einzelnen Typen in Expr w zu vergleichen.
Der Datentyp Expr w hat die etwas ungewöhnliche Art (* -> *) -> * , die ich ein Modell nenne. Es ist die Art von Dingen, die bei einem Functor oder Monad , die beide eine Art * -> * haben, einen Datentyp erzeugt (der * hat). Ein Expr Identity ist ein exaktes Modell eines Ausdrucks. Ein Expr IO könnte einen Ausdruck modellieren, dessen Wert durch Interaktion mit der Außenwelt konstruiert wird. Ein Expr ref könnte ein Expr modellieren, das über mehrere Maschinen verteilt ist, wobei der ref -Typ beschreibt, wohin die anderen Komponenten zu bekommen sind, wie ein Bezeichner für einen Datenbankeintrag. Ein Expr Proxy ist nur der Konstruktor eines Expr ohne die Daten. Sie suchen wahrscheinlich nach etwas wie dem Expr ((,) a) , das einen Ausdruck mit einer Anmerkung vom Typ a für jede Komponente modelliert.
Sie suchen wahrscheinlich nach (,) a (Expr ((,) a)) , das eine Annotation für die gesamte Struktur sowie für jede seiner Komponenten enthält. Das sieht ein wenig zu sehr nach Müll aus. Um es aufzuräumen, fügen wir ein Typen-Synonym für Datenmodelle hinzu, die sich in einem Funktor befinden.
Ein möglicher Typ für einen aus der Quelle gelesenen Ausdruck ist der Ausdruck, der mit der Zeilennummer und der Spalte versehen ist, aus der die einzelnen Komponenten stammen.
%Vor% Ich werde einige Beispiele von SourceExpr von Hand machen, um zu überprüfen, ob die abgeleitete Eq -Instanz funktioniert.
Zum Testen habe ich auch Datentypen für Pat et erstellt. al., jeweils mit einem einzigen namensgebenden Konstruktor. Die dervied Eq -Instanz funktioniert zufriedenstellend.
Ist es auf lange Sicht besser, einfach bei meinen ursprünglichen, alten AST-Typen zu bleiben?
Es gibt nicht viel Unterstützung von Haskell, um mit Modellen oder Datentypen mit der Art (* -> *) -> * zu arbeiten. Wenn Sie anfangen, mit ihnen zu arbeiten, ist das erste, was Sie wollen, eine Klasse für Datenmodelle d , die Funktoren sind, die eine natürliche Transformation (forall a. f a -> g a) -> d f -> d g abbilden. Sie würden dies beispielsweise verwenden, um die Anmerkungen aus einem Quellausdruck zu entfernen. Das nächste, was Sie wollen, ist eine Objektiv-Stil UniPlate-Bibliothek für Datenmodelle und alle% Co_de% -like Tools benötigt, um es zu unterstützen.
Du würdest dich in die weniger bekannten versetzen. Es gibt ein paar Wege, um zurück zu kommen, aber ich habe noch nicht komplett über sie nachgedacht.
Wenn Sie die Applicative -Anforderung für abgeleitete Instanzen für UndecidableInstances nicht mögen, können Sie die explizite Rekursion entfernen und ein Argument für das Modell hinzufügen, das für rekursive Vorkommen von Expr verwendet wird. Dies wäre kompatibel mit einer Expr Version von PolyKinded .
Der Typ MMorph erscheint immer nur im Typ e , der die Art e w hat. Wenn wir * durch e w ersetzen, schlägt es einen anderen etwas generischeren Typ vor, der mehr mit den Typen übereinstimmt, die eine gute Bibliotheksunterstützung haben. Diese a hat eine Art Expr , die viel häufiger ist; es ist die Art von Monadetransformatoren.
Wie auch immer, Sie würden wahrscheinlich immer noch nach einer Objektiv-ähnlichen Uniplate-Bibliothek suchen, die mit Ihrer (* -> *) -> (* -> *) s kompatibel ist.
Ich habe eine fast identische Frage zu Reddit gestellt, abgesehen von der Betonung, wie es geht Wenden Sie das Rekursionsschema auf gegenseitig rekursive Datentypen an. Redditor / u / AndrasKovacs wies darauf hin, dass ich indexierte Familien und GADTs reduzieren kann das Problem in der gewöhnlichen Situation:
%Vor%Für diesen Datentyp kann der alte einfache Fixpunkt verwendet werden:
%Vor%Dann müssen nur der indizierte Funktor sowie andere Klassen des indizierten Typs definiert werden, um den Vorteil des Rekursionsschemas zu nutzen. Er stellte auch ein Prototyp-Beispiel zur Verfügung. Der ursprüngliche Post erklärt die Dinge klar.
Danach dachte ich über das Modell nach, das von @ Cirdec erwähnt wurde. Die einfachste Lösung, beide Dinge zu integrieren (Rekursionsschema und Annotation auf jedem Knoten), ist sehr klar, aber ich konnte es einfach nicht herausfinden. Also habe ich einen festen Punkt mit direkter Unterstützung für Annotation oder "Modell" definiert, wie @Cirdec in seiner Antwort erwähnt:
%Vor% Der AST wurde zu einer dreischichtigen Struktur, einer für den Fixpunktwrapper, einer für das Modell w und einer für den tatsächlichen Knoten. Aber das ganze Rekursionsschema kann nicht auf diesem Fixpunkt aufbauen.
Glücklicherweise wurde mir klar, dass ich, da ich jedem f , dem Parameter von AstF , einen beliebigen Typ geben konnte, warum konnte ich die Annotation nicht auch dort so codieren?
IxTraversable , basierend auf dem Wert für AstF :
Andere Operationen, wie das Entfernen von Annotationen, können dann einfach über Primitive des Rekursionschemas definiert werden:
%Vor%Ich habe gerade einen Prototyp fertiggestellt Syntax.hs , aber ich glaube solche Eleganz ist, was ich suche. Möge die Macht mit mir sein! :)
Danke Leute.
Tags und Links haskell abstract-syntax-tree type-systems