std::function und Symboltabelle



  • Hallo allerseits,
    für meine Beschäftigung mit Computer Algebra schreibe ich mir gerade ein kleines Cas (es geht mir aber eher um ein gutes Design, als möglichst viele Algorithmen zu implementieren...). Ich habe eine Klassenhierarchie für Ausdrücke und verschiedene Besucher darauf erstellt. Es gibt beispielsweise einen Besucher für die Evaluierung, und dazu eine Symboltabelle. Bis jetzt sah mein Code für die Evaluierung von Funktionen so aus:

    Expr_ptr evaluate_visitor::visit(unique_ptr<FunctionNode> term)
    {
        //Wenn die Funktion definiert ist, gibt es einen Eintrag für sie in der Symboltabelle
        if(term->kind_of_function() != Function_Type::UNDEFINED)
            return Symbol_Table::instance().resolve_entry(term->get_name()).clone_value();
    
        ///vordefinierte mathematische Operatoren anwenden
        //Ableitung bilden
        else if(term->get_name() == "diff" && term->number_of_operands() == 2 && term->get_operand(1).get_type() == Expr_Type::SYMBOL)
        {
            //Die Vorbedingung von Analysis_Algorithms::derivate ist, dass Funktionen nicht evaluiert sind
            evaluate_function = false;
            Expression& expr_eval{*dispatch(term->extract_operand(0))};
            evaluate_function = true;
    
            //Den ausgewerteten Ausdruck ableiten
            return Analysis_Algorithms::derivate(expr_eval, *static_cast<Variable*>(term->extract_operand(1).release()));
        }
    
        //weitere Operatoren
        //...
    
        //Wenn Runden aktiviert ist, transzendente Funktionen wie sin, cos auswerten
        //...
    
        //Es gab keinen Eintrag für term in der Symboltabelle
        else return move(term);
    }
    

    Das Problem it der letzte Abschnitt, d.h. dort wo vordefinierte Operatoren und transzendente Funktionen ausgewertet werden, da das alles "hartgecodet" ist. Lieber wäre es mir, wenn man all diese Funktionen mit in der Symboltabelle speichern könnte.

    Jetzt gibt es ja seit C++11 std::function. Also dachte ich mir, ich erweitere meine vorhandene Hierarchie von Symbol_Table_Entry s wie folgt:

    class Base_Entry
        {
        public:
            Base_Entry(Entry_Type);
    
            virtual ~Base_Entry() = 0;
    
            Entry_Type kind() const;
        private:
            struct IMPLEMENTATION;
            IMPLEMENTATION* impl;
        };
    
    template<typename... Arg_Types>
        class Transcendental_Function_Entry : public Base_Entry
        {
        public:
            Transcendental_Function_Entry(std::function<std::unique_ptr<Syntax_Tree::Expression>(Arg_Types..., const Syntax_Tree::Integer&)>);
            virtual ~Transcendental_Function_Entry();
    
            std::unique_ptr<Syntax_Tree::Expression> evaluate(Arg_Types... arg, const Syntax_Tree::Integer& precision);
        private:
            std::function<std::unique_ptr<Syntax_Tree::Expression>(Arg_Types...)> approximation;
        };
    

    Base_Entry habe ich eingeführt, damit man in der Symboltabelle auch ein Objekt vom Typ Transcendental_Function_Entry einfügen kann (die Einträge werden in einer Hashmap gespeichert).
    Transcendental_Function_Entry übernimmt eine Funktion, die einen Ausdruck zurückgibt, und bei der der letzte Parameter eine Ganzzahl ist (die gibt die Genauigkeit an). Mein Plan ist, die vordefinierten Funktionen beim Programmstart in die Symboltabelle einzufügen, das müsste glaub ich nicht so schwer werden. Das Problem ist eher die Auswertung einer Funktion.
    Wenn ich eine vordefininierte Funktion auswerten will, kann ich den Eintrag einfach über den Namen erhalten. Jetzt ist das aber ein

    Base_Entry*
    

    also muss das noch gecastet werden. Blöd nur dass man die Template Parameter nicht kennt.
    Und wenn das in ein

    Transcendental_Function_Entry*
    

    gecastet werden konnte, muss ich die Funktion noch irgendwie auswerten. Dazu muss ich die Kindknoten im Baum der auszuwertenden Funktion übergeben. Dazu muss ich auch irgendwie rausfinden, ob die Typen der auszuwertenden Funktion passen.

    Am besten ich mache mal ein Beispiel:

    namespace Integer_Algorithms
    {
        Integer lcm(const Integer&, const Integer&);
        //...
    }
    

    Jetzt schreibt der Benutzer in der Eingabe folgendes:

    lcm(5, 15)
    

    Das wird dann geparst und der folgende Ausdruck entsteht:
    Function("lcm", Integer(5), Integer(15))
    Und dieser Ausdruck soll jetzt mit Hilfe der Symboltabelle ausgewertet werden (unter der Annahme dass die Funktion "lcm" eingefügt wurde).
    Die Parameter Integer(5) und Integer(15) müssen also irgendwie an den Eintrag für die Funktion "lcm" übergeben werden, und der muss dann "lcm" mit den Parametern ausführen.

    Meine Fragen wären jetzt:
    Ist dieser Ansatz schlüssig?
    Und wie kann man die oben beschriebenen Probleme lösen, oder habe ich etwas übersehen (Ich bitte um Nachsicht, ich habe bis gestern noch nie etwas mit std::function gemacht...)
    Gruß
    Paul



  • henriknikolas schrieb:

    Ist dieser Ansatz schlüssig?

    Schwer zu sagen. Ich finde das ganze noch etwas zu simpel aufgesetzt für ein komplettes CAS. Oder du hast zumindest die Rahmenbedingungen nicht klar genug definiert. Gutes Design ist wichtiger als viele Algorithmen zu implementieren, ok, aber was soll das Design insgesamt unterstützen können? Vektoren und Matrizen? Benutzerdefinierte Funktionen? Tausend andere Sachen, die in einem CAS wichtig sein könnten?

    Wenn du das auf der Ebene abstrahieren willst, müsstest du halt von konkreten Integer Parametern weggehen und mit Listen von Parametern arbeiten:

    Integer lcm(const Integer&, const Integer&);

    ->

    term execute(const std::vector<term>& params);

    Ob das in der Form für "alles" reicht, weiß ich aber nicht. Glaub ich eher nicht.



  • Hallo Mechanics,
    ich glaube ich habe mich etwas unverständlich ausgedrückt, mir rauchte nämlich schon der Kopf von der ganzen std::function Sache 🙂

    Eine der grundlegendsten Methoden in einem Cas (neben dem Einlesen und Überführen in eine bestimmte Darstellung) ist die Evaluierung. Dabei werden grundlegende Simplifikationen wie die Zusammenfassung von gewissen Termen (alle ganze Zahlen, Brüche natürlich, bei Summen die Summanden mit gleicher Basis und Exponent (also x³ und 4*x³ beispielsweise), ..., bei Produkten das Zusammenfassen von Faktoren mit der gleichen Basis, ..., bei Potenzen die Anwendung der Potenzgesetze) erledigt. Es werden aber auch Variablen und Funktionen ausgewertet, Variablenauswertung findet je nach Kontext statt oder nicht statt (Bei einer Zuweisung beispielsweise werden logischerweise keine Referenzen ausgewertet), bei der Funktionsauswertung muss man noch beachten, dass manche Funktionen auf unevaluierten Parametern schneller arbeiten...
    All das sind Dinge, die ich schon implementiert habe, und die auch alle klappen. Zur Erweiterbarkeit wäre ein nächster Schritt ein Typsystem zu implementieren (eher in die Richtung von Axiom - also ein objektorientierter Ansatz).
    Außerdem sind schon ein paar Algorithmen (zahlentheoretische, Ableitung, Substitution, ...) implementiert, die man als Benutzer (ich meine nicht den Entwickler) braucht. Ich möchte gar nicht die ganze Funktionalität in C++ selbst schreiben, sondern dem Cas später auch eine kleine eigene Programmiersprache hinzufügen, da zählt dann die Abstimmung mit dem Typsystem ( man sieht, ich habe schon auf ein paar Jahre geplant 😃 ).

    Worum es mir jetzt gerade geht, ist, Sachen möglichst nicht hartzucoden, und dazu möchte ich Funktionen dann zentral verwalten, und bei der zuständigen Stelle in der Evaluierungsfunktion nur der Symboltabelle sagen, sie soll das mal aufrufen, anstatt immer erst zu testen:
    Ist das eine vom Benutzer definierte Funktion (die klappen auch schon)
    Oder doch eine vordefinierte Funktion, und dann alle Fälle abzuklappern. Das finde ich zutiefst unhandlich. Dafür würde ich gerne eine Funktionstabelle mit

    std::function
    

    benutzen.

    Gruß
    Paul



  • Es ändert im Grunde nichts an meiner Aussage 😉

    Du musst die Parameter irgendwie abstrahieren, hab ich jetzt mal term genannt, und der Funktion eine Liste davon übergeben. Die Funktion kann dann schauen, ob sie zwei bekommen hat, und wenn nicht, einen Fehler schmeißen.
    Vielleicht kann man auch beim Registrieren der Funktion Metainfos mitgeben, und der Interpreter weiß dann schon, dass der Aufruf nicht funktionieren kann.



  • Stimmt, darauf bin ich gar nicht gekommen! Alle Ausdrücke die als Parameter auftreten können, sind ja Ableitungen von

    Expression
    

    . Dann könnte ich dafür eine

    initializer_list<unique_ptr<Expression>>
    

    benutzen. Was dann noch zu tun wäre, dass überprüft wird, dass die übergebenen Typen die richtigen sind, aber ich möchte auf keinen Fall, dass das die aufzurufenden Funktionenen machen.

    Ich werd mir was überlegen, und wenn ich nicht weiterkomme, schreibe ich wieder.

    Vielen Dank
    Gruß
    Paul


Anmelden zum Antworten