2012-07-09 35 views
5

Mentre lavoravo con i macro, ho raggiunto il punto (ho cercato di evitarlo) dove ho bisogno di aggiornare quei nodi nell'AST che mantengono determinate condizioni. Per esempio, diciamo che vorrei aggiornare ogni nodo:Qual è il modo più semplice per aggiornare un AST immutabile?

Literal(Constant(1)) 

con il valore:

Literal(Constant(2)) 

quei nodi AST potrebbe essere ovunque nel albero di espressione, quindi non posso usare un ad-hoc pattern matcher. Ovviamente, l'ultima cosa che vorrei fare è codificare un pattern matcher completo che sia in grado di coprire tutti i primitivi del compilatore. Ho cercato nel API ma ho l'impressione che metodi come raccolgono e traversabili della famiglia non siano sufficienti per soddisfare i miei bisogni, poiché trattano l'albero come una cosa lineare, e voglio che il tutto sia aggiornato come risultato Quindi, è possibile aggiornare un albero di espressione immutabile in modo intelligente? Perché non esiste un'operazione di "aggiornamento" nell'API standard?

+0

per plugin c'è un TreeTransformer. Suppongo che ci debba essere un simile per macro, forse anche lo stesso. – pedrofurla

+0

Probabilmente vorrai controllare [zippers] (http://anti-xml.org/zippers.html) –

+0

@NikitaVolkov, direi che se non lo stava chiedendo nel contesto dei macro. – pedrofurla

risposta

3
+0

Devo davvero cercare il codice sorgente per Transformer. Sembra la libreria di trasformazione XML e quella libreria ha prestazioni esponenziali sulla profondità dell'albero. –

+0

Un tiro selvaggio al problema: si tratta di attraversamento dall'alto verso il basso o dal basso verso l'alto? In un attraversamento top-down, la modifica di una foglia implica la ricostruzione dell'albero sopra. L'implementazione di 'traceImpl', nel link sopra, suggerisce che i nuovi alberi siano costruiti dal basso verso l'alto (almeno lì). Ma, in generale, dipende da come chiami 'super.transform'. – Blaisorblade

2

La modifica di nodi poly-typed nelle strutture dati in genere è un caso classico di generici di tipi di dati (parametrizzazione del codice tramite il costruttore di tipi).

Esistono diversi approcci per tali operazioni, come l'approccio "Scrap Your Boilerplate", che definisce le funzioni di attraversamento generico dei tipi di dati.

In Haskell, la funzione di aggiornamento nodo è parametrizzato in due dimensioni: da tipo di dati e per codice - in modo da poter applicare diverse funzioni di aggiornamento di diversi tipi, ovunque in una struttura:

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

Ciò in Haskell fa molto affidamento sulle classi di tipi. In Scala, ci sono diversi ported examples

Problemi correlati