Elaborazione AST e utilità del pattern visitatore

Question

Elaborazione AST e utilità del pattern visitatore

#1 da (12 voti)

5

So che il pattern visitor viene in genere utilizzato per attraversare una gerarchia di oggetti eterogenei (che ereditano uno stesso oggetto astratto) e dissociare l'elaborazione di questi oggetti dai dati al loro interno. Un classico utilizzo del pattern visitor (spesso citato) è l'elaborazione di un albero di sintassi astratto in un compilatore. In effetti, la struttura dell'albero è nota solo in fase di esecuzione (una volta che il programma è stato analizzato) e si desidera attraversare l'albero modificando i nodi in base ai passaggi semantici implementati come visitatori. Ma il pattern del visitatore mi sembrava eccessivo, dal momento che consente una doppia (dinamica) distribuzione in funzione del tipo ASTNode e del tipo Visitor, o uno staticamente conosce l'ordine del visitatore che useremo per elaborare l'AST durante la semantica fase. Se dovessi codificare questo in C ++ (fatto sul posto senza compilare), farei:

struct AstNode
{
    //virtual void accept() = 0; //this won't work since template does not override virtual pure method
    virtual ~AstNode();
};

struct SpecificNode : public AstNode
{
    template <class Visitor>
    void accept(Visitor v)
    {
        v.visit(*this);
    }
};

//other AST nodes

class MyVisitor
{
    void visit(SpecificNode n) {/*...*/}

    //other visit methods for other AST nodes
};

//other visitors

Qui non c'è una doppia spedizione, non è un vero visitatore. Ma posso capire perché avrei bisogno di questa doppia spedizione.

Note:

Queste pagine di wikipedia elencano altri usi di doppia spedizione ma non AST: link .

c++ design-patterns compiler visitor-pattern

posta matovitch 12.05.2015 - 13:51

fonte

1 risposta

Leggi altre domande sui tag c++ design-patterns compiler visitor-pattern

Quale ruolo hanno avuto i miglioramenti dell'hardware nello sviluppo dei linguaggi moderni (ad es. Python / Java)? I test di integrazione sono considerati ridondanti?

score 12 · Accepted Answer

Una cosa di cui spesso non si parla è il pattern Visitor, che consente di scegliere da quale lato del problema di espressione si vuole affrontare.

Quindi, qual è il problema dell'espressione? Si riferisce al problema di base dell'estensibilità: i nostri programmi manipolano i tipi di dati utilizzando le operazioni. Con l'evolversi dei nostri programmi, è necessario estenderli con nuovi tipi di dati e nuove operazioni. In particolare, vogliamo essere in grado di aggiungere nuove operazioni che funzionano con i tipi di dati esistenti e vogliamo aggiungere nuovi tipi di dati che funzionino con le operazioni esistenti. E vogliamo che questa sia la vera estensione , cioè non vogliamo modificare il programma esistente , vogliamo rispettare le astrazioni esistenti, vogliamo che le nostre estensioni siano moduli separati, in spazi dei nomi separati, compilati separatamente, distribuiti separatamente, controllati separatamente. Vogliamo che siano sicuri per il tipo.

Il problema dell'espressione è, in che modo puoi fornire tale estensibilità in una lingua?

Si scopre che per le tipiche implementazioni ingenue della programmazione procedurale e / o funzionale, è molto facile aggiungere nuove operazioni (procedure, funzioni), ma molto difficile aggiungere nuovi tipi di dati, poiché fondamentalmente le operazioni funzionano con i dati tipi che usano una sorta di discriminazione del caso ( switch , case , pattern matching) e devi aggiungere nuovi casi, cioè modificare il codice esistente:

func print(node):
  case node of:
    AddOperator => print(node.left) + '+' + print(node.right)
    NotOperator => '!' + print(node)

func eval(node):
  case node of:
    AddOperator => eval(node.left) + eval(node.right)
    NotOperator => !eval(node)

Ora, se si desidera aggiungere una nuova operazione, ad esempio, la verifica del tipo, è facile, ma se si desidera aggiungere un nuovo tipo di nodo, è necessario modificare tutte le espressioni di corrispondenza del modello esistenti in tutte le operazioni.

E per il tipico OO ingenuo, hai il problema esattamente opposto: è facile aggiungere nuovi tipi di dati che funzionano con le operazioni esistenti (ereditandole o sovrascrivendole), ma è difficile aggiungere nuove operazioni, dal momento che fondamentalmente significa modificare classi / oggetti esistenti.

class AddOperator(left: Node, right: Node) < Node:
  meth print:
    left.print + '+' + right.print

  meth eval
    left.eval + right.eval

class NotOperator(expr: Node) < Node:
  meth print:
    '!' + expr.print

  meth eval
    !expr.eval

In questo caso, aggiungere un nuovo tipo di nodo è facile, perché erediti, esegui l'override o implementa tutte le operazioni richieste, ma l'aggiunta di una nuova operazione è difficile, perché devi aggiungerla a tutte le classi foglia o a una classe base, modificando così il codice esistente.

Diverse lingue hanno diversi costrutti per risolvere il Problema di Espressione: Haskell ha typeclass, Scala ha argomenti impliciti, Racket ha Unità, Go ha Interfacce, CLOS e Clojure hanno Multimethods.

Tuttavia, in un linguaggio OO che non ha un modo di risolvere il Problema di Espressione (come Java o C #), il Pattern Visitatore ti consente almeno di "scegliere il tuo veleno". Quello che fa il modello è trasformare il tuo disegno di 90 ° di lato: le operazioni diventano classi ( PrintVisitor , EvalVisitor ) e viceversa, i tipi diventa metodi ( visitAddOperator , visitNotOperator (o solo visit , se la tua lingua supporta l'overload basato su argomenti)). Questo non risolve il Problema di Espressione (cioè come semplificare l'aggiunta di entrambi tipi e operazioni), ma fa ti permette di scegliere quale per semplificare.

Quindi, se la tua lingua supporta un modo per risolvere il problema dell'espressione, non hai bisogno di questa soluzione alternativa.

Nota, tuttavia, questa non è l'unica cosa che fa il pattern Visitor.

Nota: noterai la notevole assenza di qualsiasi menzione del C ++, qualunque sia. Sfortunatamente, semplicemente non ne so abbastanza. Sospetto che tra il sovraccarico e la distribuzione basata sull'argomento, l'ereditarietà virtuale, le funzioni libere, le macro e soprattutto la metaprogrammazione del modello in fase di compilazione, il Problema di espressione sia risolto in C ++, ma non lo so di sicuro.

Il problema è che una volta che qualcuno trova una soluzione per il Problema dell'espressione, lo ridefinisce per renderlo ancora più difficile, in modo da risolvere, in modo che le nuove soluzioni siano ancora più potenti ed espressive. Ad esempio, la formulazione originale della comunità Haskell non richiedeva un controllo di tipo modulare, ma la comunità di Scala ha proposto che il Problema dell'espressione non includesse solo l'estensione modulare (compilazione separata, ecc.) Di tipi e operazioni, ma anche la tipizzazione modulare e l'inferenza di tipo di quelle estensioni, che al momento sono qualcosa che solo gli impliciti di Scala possono fare e le typeclass di Haskell e i funtori di ML non possono.