Was ist der einfachste Weg, um eine unveränderliche AST zu aktualisieren?

Während der Arbeit mit Makros habe ich den Punkt erreicht (ich habe mich bemüht, es zu vermeiden), wo ich jene Knoten im AST aktualisieren muss, die bestimmte Bedingungen erfüllen. Zum Beispiel, sagen wir, ich möchte jeden Knoten aktualisieren:Was ist der einfachste Weg, um eine unveränderliche AST zu aktualisieren?

Literal(Constant(1))

mit dem Wert:

Literal(Constant(2))

Diese AST-Knoten irgendwo im Ausdrucksbaum sein könnte, so kann ich nicht eine Ad-hoc verwenden Mustervergleicher. Offensichtlich ist das letzte, was ich tun möchte, einen vollständigen Muster-Matcher zu programmieren, der alle Compiler-Primitive abdeckt. Ich habe in der API Suche, aber ich habe den Eindruck, dass Methoden wie sammeln und die traversable Familie sind nicht gut genug, um meine Bedürfnisse zu erfüllen, da sie den Baum als eine lineare Sache behandeln, und ich will das ganze aktualisiert Baum als Ergebnis. Ist es also möglich, einen unveränderlichen Ausdrucksbaum auf intelligente Weise zu aktualisieren? Warum existiert solch eine "Update" -Operation nicht in der Standard-API?

Quelle

2012-07-09 jeslg

Für Plugins ein TreeTransformer ist. Ich nehme an, dass es für Makros ein ähnliches gibt, vielleicht sogar dasselbe. – pedrofurla

Wahrscheinlich wirst du [zippers] (http://anti-xml.org/zippers.html) –

@NikitaVolkov auschecken, würde ich sagen, wenn er nicht im Zusammenhang mit Makros gefragt. – pedrofurla

Hier ist ein Beispiel eines AST Transformator in einem Scala Makro mit:

https://github.com/retronym/macrocosm/blob/171be7e/src/main/scala/com/github/retronym/macrocosm/Macrocosm.scala#L129

Quelle

2012-07-09 18:57:14 retronym

Ich muss wirklich den Quellcode für Transformer nachschlagen. Es sieht aus wie die XML-Transformationsbibliothek, und diese Bibliothek weist eine exponentielle Leistung in der Tiefe der Struktur auf. –

Ein wilder Blick auf das Thema: bezieht sich dies auf Top-Down-vs-Bottom-Up-Traversal? Bei einem Top-Down-Traversal bedeutet das Ändern eines Blattes, dass der obige Baum neu erstellt wird. Die Implementierung von 'traceImpl' im obigen Link legt nahe, dass neue Bäume von Grund auf (zumindest dort) konstruiert werden. Aber im Allgemeinen hängt es davon ab, wie Sie 'super.transform' nennen. – Blaisorblade

Das generelle Ändern von Polytyp-Knoten in Datenstrukturen ist ein klassischer Fall von Datentypgenerika (Parametrisierung von Code über Typkonstruktor).

Für solche Operationen gibt es mehrere Ansätze, z. B. den "Scrap Your Boilerplate"-Ansatz, die generische Traversal-Funktionen des Datentyps definieren.

In Haskell, die Knoten-Update-Funktion ist in zwei Dimensionen parametriert: von Datentyp und durch Code - so können Sie verschiedene Update-Funktionen auf verschiedene Arten anwenden können, überall in einer Struktur:

-- | Apply a transformation everywhere in bottom-up manner 
everywhere :: (forall a. Data a => a -> a) 
      -> (forall a. Data a => a -> a)

Doing so in Haskell ist stark auf Typklassen angewiesen. In Scala gibt es mehr ported examples

Quelle

2012-07-09 15:19:30

Was ist der einfachste Weg, um eine unveränderliche AST zu aktualisieren?

Antwort

Verwandte Themen