Syntaxbaum CAS

[henriknikolas]

Hallo,
ich programmiere mir gerade ein ein kleines CAS.
Zurzeit bin ich soweit, dass ich die Simplifizierunngsalgorithmen auf dem Syntaxbaum implementiere. Dabei macht sich aber bemerkbar, dass ich den
Syntaxbaum nicht so sorgfältig entworfen habe, und deshalb dachte ich, dass jemand hier vielleicht Verbesserungsvorschläge für mein Design hat.
Ich beschreib das mal kurz und sage auch was ich mir dabei gedacht habe:

Der Parser erstellt aus der Eingabe zunächst einen binären Baum, aber später können einzelne Knoten auch mehrere Operanden habe, da sich damit leichter rechnen lässt. Das ist der Knoten für Produkte und auch der für Summen, da hier die Reihenfolge der Operanden(Kommutativgesetz) nicht wichtig ist.

Für jede Rechenoperation gibt es einen Knoten und dann gibt es noch Knoten für Funktionen, Symbole, Ganzzahlen und Brüche.

Alle Knoten unterstützen die folgenden Operationen:

substitute(t,x) : jedes Vorkommen von t durch x ersetzen
contains(t) : prüfen ob ein Knoten t enthält
get_type() : Typ der Rechenoperation,...
print
equal(t)
Außerdem haben die Knoten der Rechenoperation und der Knoten für Funktionen
zusätzlich noch eine Funktion um den i-ten Operanden zu erhalten (als const Node*)

Diese Ideen habe ich so umgesetzt:

class Node
    {
    public:
        virtual Node* substitute(const Node* t, Node* r) const = 0;

        virtual void print() const = 0;
        virtual Node_Type get_type() const = 0;
        virtual bool equal(const Node* t) const = 0;
        virtual bool contains(const Node* t) const = 0;
    }; 

    class Calc_Node : public Node
    {
    public:
        virtual const Node* get_operand(int i) const = 0;
        virtual int number_of_operands() const = 0;
    };

Dann gibt es noch SumNode, DiffNode, ProductNode... , FunctionNode, FractionNode, VarNode, IntNode
alle bis auf FractionNode, VarNode, IntNode sind von Calc_Node abgeleitet, da sie Operanden haben, die selbst wieder Knoten sind.
Die drei letztgenannten sind von Node abgeleitet.

Die erste Frage, die ich mir gestellt habe, war ob ich den Ableitungs-Algorithmus als Member von Node machen soll, oder nicht. Ich habe mich dagegen entschieden. Als ich das dann implementiert habe, musste ich manchmal neue Bäume aus vorhanden Operanden von einzelnen Knoten erstellen (zum Beispiel wenn ich ein Produkt mit der Produkregel ableite (die allgemeine für beliebig viele Fakoren)). Da der i-te Operand nur als const Node* zurückgegeben wird (sonst könnte ja jeder beliebig an meinem Baum rumpfuschen) musste ich eine neue Methode einführen, die einen ganzen Baum kopiert.

Meine allgemeine Frage (nach dem ganzen Geschwafel ist folgende:
1. Welche Operationen (ableitung, simplifizierung, ...) sollten Memberfunktion der Knoten sein, und welche nicht?
2.Wie sollte ich mit den Operatoren umgehen, die nicht als Memberfunktion implementiert sind und welche Möglichkeiten sollte ich ihnen geben mit den übergebenen Bäumen zu arbeiten (zum Beispiel irgendwelche Operanden kopieren um daraus neue Bäume zu machen...)
3. Würde es was verbessern wenn jeder Knoten einen Verweis auf seinen parent spiechern könnte, dann könnte man substitue zum Beispiel den Knoten direkt verändern lassen, da man ändern kann worauf der parent zeigt
4. Kann man irgendwas anderes am Design verbessern, weil das alles ein bisschen wie en "Flickenteppich" aussieht

Herzliche Grüße
Paul

[SDGHAR]

henriknikolas schrieb:

Welche Operationen (ableitung, simplifizierung, ...) sollten Memberfunktion der Knoten sein, und welche nicht?

Keine!

Der AST ist nur dazu zuständig, den Ausdruck abzubilden. Rechenoperationen wendet man darauf von aussen an.

Hilfreich dazu: https://en.wikipedia.org/wiki/Visitor_pattern . Node braucht nur accept und clone.

Damit kannst du eine freie Funktion

unique_ptr<Node> simplify(unique_ptr<Node> ast)

bauen. Diese muss natürlich als Implementierungsdetail einen Visitor implementieren.

Abgesehen von IntNode, RealNode, FractionNode und VarNode brauchst du eigentlich nur FunctionNode, oder falls FunctionNode für Benutzer gedacht ist, einen BuiltinNode. Diese speichern einen

std::function<unique_ptr<Node>(unique_ptr<Node>)> action;

als Membervariable. Wenn simplify darauf antrifft, wird die Action angewendet.

Nur falls du es noch nicht selbst gemerkt hast, a+b ist auch nur eine ganz normale Funktion: +(a,b)

[henriknikolas]

Danke erstmal für die Antwort. Ich hatte mich davor noch nicht mit Design Patterns beschäftig, es kann also sein, dass ich manche Sachen noch nicht richtig verstanden habe.

Wie funktioniert das jetzt genau, wenn zwei visitors verschiedene Rückgabetypen habe, also der eine void (zum Beispiel fürs ausgeben), der andere aber unique_ptr<Node*> für das Simplifizieren?

Was ich auch nicht verstehe ist folgendes:
Die Elementklassen (also Node, ...) rufen ja in accept visit auf.
Aber zum Beispiel fürs Ausgeben spielt es eine Rolle, ob ich als erstes die Operanden besuche und dann erst this oder einen Operanden, dann this und dann den anderen Operanden?

Und was ich noch nicht verstanden habe ist, was du mit

Abgesehen von IntNode, RealNode, FractionNode und VarNode brauchst du eigentlich nur FunctionNode, oder falls FunctionNode für Benutzer gedacht ist, einen BuiltinNode. Diese speichern einen
C++:
std::function<unique_ptr<Node>(unique_ptr<Node>)> action;
als Membervariable. Wenn simplify darauf antrifft, wird die Action angewendet.

meintest.
Viele Grüße
Paul

[Mechanics]

Visitoren brauchen nicht unbedingt Rückgabewerte, die können als weitere Member implementiert werden.

SimplifyVisitor visitor;
root->accept(visitor);
auto newRoot = visitor.simplifiedRoot();

Was in welcher Reihenfolge aufgerufen wird, könnte z.B. die Implementierung von accept des jeweiligen Knoten wissen.

[henriknikolas]

Ich habe nochmal lange über das Problem nachgedacht und bin zu folgendem Ergebnis gekommen:
Die Reihenfolge, in der die Visitor aufgerufen werden variert von Visitor zu Visitor. Ein SimplifyVisitor zum Beispiel brucht eine andere Reihenfolge als ein PrintVisitor. Deshalb müsste der Visitor jeweils stuern, wer oder was in welcher Reihenfolge besucht wird. Dafür brauche ich dann aber wieder Zugriff auf die Repräsentation(zum Beispiel durch Überladen des Indexoperators).
Da macht es doch dann wirklich keinen Unterschied mehr, ob ich schreibe

void SimplifyVisitor::visit(SumNode* t)
{
    SimplifyVisitor v1, v2;
    t[0]->accept(v1);
    t[1]->accept(v2);
    //weitere Aktionen...
}

oder

void simplify(Node* t)
{
    //Basisfälle für Ganzzahlen, Brüche, Symbole

    if(t->type() = Node_Type::SUM)
    {
        simplify(dynamic_cast<SumNode*>(t)[0]);  //okay, mit der Indexschreibweise siehts doch etwas unschön aus
        simplify(dynamic_cast<SumNode*>(t)[1]);
    }
    //weitere Fälle...

}

?
Brauche ich in diesem Fall das Visitor Pattern wirklich noch, also bietet es mir einen Vorteil es zu verwenden?

[Mechanics]

henriknikolas schrieb:

Brauche ich in diesem Fall das Visitor Pattern wirklich noch

Ja. Ist immer noch viel schöner, als dynamic_cast und irgendwelche type() Aufrufe.
Und der Aufruf wäre wahrscheinlich eher

t[0]->accept(this);

und nicht ein anderer Visitor, wobei sich das natürlich von Fall zu Fall unterscheiden kann.

[SDGHAR]

Mit einem PostOrderVisitor und PreOrderVisitor als Basisklasse musst du dich nicht einmal um die Traversierung kümmern. Du sparst insgesamt viel Code und es wird sicher nicht langsamer.

Und wie gesagt, auf SumNode würde ich verzichten, wenn du nur 5 Typen hast, wird es viel übersichtlicher.

[henriknikolas]

Das mit dem Preorder / Posorder / Inorder als Basisklasse ist wirklich schlau!

Die Frage, die ich jetzt noch hätte, wäre wie ein visitor für eine Funktion wie
equal aussieht, also wo ein Baum mit einem anderen verglichen wird.
Als Member der jeweiligen Knoten wäre das einfach, aber wie man das als Visitor machen kann verstehe ich irgendwie nicht.

Ginge das, wäre das echt nützlich, denn dann könnte ich mir die ganzen dynamic_cast bei einer Funktion, die überprüft ob zwei Knoten richtig geordnet sind, sparen!

Vielen Dank nochmal!!!
Paul

[henriknikolas]

Habe es jetzt doch hingekriegt:

class equal_visitor : public visitor
{
    bool same;
    const Node* right_side;
public:
    equal_visitor(const Node* r) : right_side(r), same(false) {}

    //left_side mit right_side vergleichen und das Ergebnis in same speichern
    virtual void visit(const Sum* left_side)
    {
        if(right_side->get_type() != NodeType::SUM)
        {
            same = false;
            return;
        }

        //"Sicherung" von right_side anlegen, um es später wiederherzustellen
        const Node* tmp = right_side;
        const Sum* right = dynamic_cast<const Sum*>(right_side);

        for(int i = 0; i < left_side->number_of_operands(); ++i)
        {
            //der i-te Operand der ursprünglich rechten Seite wird neue rechte Seite
            right_side = right->get_operand(i);
            //den i-ten Operanden der linken Seite mit der rechten Seite (also dem
            //i-ten Operanden der ursprünglichen rechten Seite) vergleichen
            left_side->get_operand(i)->accept(*this);

            //Für den Fall, dass beide Seiten nicht übereinstimmen, die rechte Seite "wiederherstellen"
            if(!same)
            {
                right_side = tmp;
                same = false;
                return;
            }
        }

        //alle Operanden haben übereingestimmt
        same = true;
        //die rechte Seite "wiederherstellen"
        right_side = tmp;

    }
    virtual void visit(const Int* left_side)
    {
        if(right_side->get_type() != NodeType::INT)
        {
            same = false;
            return;
        }

        same = (left_side->get_val() == dynamic_cast<const Int*>(right_side)->get_val());
    }
    bool equal()
    {
        return same;
    }
};

Ist das grundsätzlich richtig oder kann man das noch verbessern? In dem Buch was ich mir zu Entwurfsmustern ausgeliehen habe war solch ein Fall leider nicht drin wo man eine Operation hat, die auf 2 Objekte angewendet wird / 2 Objekte verwendet.

Gruß
Paul

[SDGHAR]

Sehr schön, so hätte ich es auch gemacht.

Gibt noch ein paar Geschmackssachen, z.B. hätte ich im Konstruktor same=true gesetzt (weil das der logische Default-Wert ist: Es ist gleich bis eine Stelle gefunden wurde, an der es nicht gleich ist -- dann sparst du dir ein same=true im Code), die Sicherung der RHS kannst du dir in einen RAII-Guard verpacken, das eine same=false ist überflüssig und der dynamic_cast ist eigentlich ein static_cast (ich hätte eine eigene cast-Funktion geschrieben, die in einem assert den Typ überprüft).

Das kannst du jetzt noch in eine globale Funktion equal verpacken und den equal_visitor im Source-File verstecken, dann kann es niemand falsch verwenden.

Da du schon die get_type()-Methode in allen AST-Knoten hast noch einen Hinweis wie du den visitor schneller bekommst: Schreib dir eine accept-Methode mit einem switch/case nach get_type im Basis-Visitor. Dann brauchst du kein accept in den AST-Knoten und ein Dispatch fällt weg. Zusätzlich kannst du den Basis-Visitor noch als CRTP schreiben, dann brauchst du kein virtual und der zweite Dispatch fällt weg. Aber das würde ich erst machen, wenn deine AST-Hierarchie fertig steht.

[henriknikolas]

Vielen vielen Dank für die ganzen Verbesserungsvorschläge!!!

meintest du das mit der accept-Methode so:

class visitor
{
protected:
    virtual void visit_sum(const Sum*) = 0;
    virtual void visit_int(const Int*) = 0;
    //weitere

public:
    void accept(const Node* t)
    {
       switch(t->get_type())
       {
       case NodeType::INT:
          visit_int(static_cast<const Int*>(t));
          break;
        //und so weiter...
        }
    }
}

Oder habe ich das falsch verstanden?
Ansonsten vielen Dank nochmal!
Gruß
Paul
};

[SDGHAR]

Genau. Der grosse Geschwindigkeitsvorteil ergibt sich allerdings erst durch CRTP, weil dann alles geinlined werden kann:

template <typename T>
class visitor {
  T& get() { return *static_cast<T*>(this); }
public:
  void dispatch(Node const* n) { // oder accept
    switch (n->get_type()) {
    case NodeType::INT:
       get().visit(static_cast<const Int*>(t)); // sucht sich den passenden Overload raus
       break;
    ...
    }
  }
};

class xyz_visitor : visitor<xyz_visitor> {
  void visit(const Int *i) { ... } 
  void visit(const Sum *s) { ... } 
  ...
};

Weiterer Vorteil ist, dass du nicht alle Methoden bereitstellen musst, wenn es z.B. einen ConstantNode gibt, von dem IntNode und FractionNode erben, könntest du nur ein visit für ConstantNode anbieten.

Üblicherweise gibt get_type auch direkt eine Membervariable zurück und ist keine virtuelle Funktion, das macht es noch ein bisschen schneller.

Aber das sind Mikrooptimierungen.

[henriknikolas]

Das ist wirklich alles sehr sehr interessant, vielen Dank!
Kannst du mir ein Buch empfehlen, wo solche Sachen beschrieben werden?
Gruß
Paul