Storch, Teil 3: Implementierung von Ausdrücken und Variablen

In Teil 3 unserer Serie wird unsere leichtgewichtige Programmiersprache endlich laufen. Es wird nicht Turing-vollständig sein, es wird nicht leistungsfähig sein, aber es wird in der Lage sein, Ausdrücke auszuwerten und sogar externe Funktionen aufzurufen, die in C++ geschrieben sind.

Ich werde versuchen, den Prozess so detailliert wie möglich zu beschreiben, hauptsächlich weil es der Zweck dieser Blogserie ist, aber auch für meine eigene Dokumentation, weil die Dinge in diesem Teil etwas kompliziert wurden.

Ich habe vor der Veröffentlichung des zweiten Artikels mit der Programmierung für diesen Teil begonnen, aber dann stellte sich heraus, dass der Ausdrucksparser eine eigenständige Komponente sein sollte, die einen eigenen Blogbeitrag verdient.

Das, zusammen mit einigen berüchtigten Programmiertechniken, machte es möglich, dass dieser Teil nicht monströs groß war, und dennoch werden einige Leser höchstwahrscheinlich auf die besagten Programmiertechniken hinweisen und sich fragen, warum ich sie verwenden musste.

Warum verwenden wir Makros?

Als ich an verschiedenen Projekten und mit verschiedenen Leuten Programmiererfahrung sammelte, lernte ich, dass Entwickler dazu neigen, ziemlich dogmatisch zu sein – wahrscheinlich, weil es so einfacher ist.

Das erste Dogma der Programmierung ist, dass die goto Anweisung schlecht, böse und schrecklich ist. Ich kann verstehen, woher dieses Gefühl stammt, und ich stimme dieser Vorstellung in den allermeisten Fällen zu, wenn jemand die goto Anweisung verwendet. Es kann normalerweise vermieden werden, und stattdessen könnte besser lesbarer Code geschrieben werden.

Man kann jedoch nicht leugnen, dass das Brechen der inneren Schleife in C++ leicht mit der goto Anweisung erreicht werden kann. Die Alternative – die eine bool Variable oder eine dedizierte Funktion erfordert – könnte weniger lesbar sein als der Code, der dogmatisch in den Eimer verbotener Programmiertechniken fällt.

Das zweite Dogma, das ausschließlich für C- und C++-Entwickler relevant ist, besagt, dass Makros schlecht, böse, schrecklich und im Grunde eine Katastrophe sind, die nur darauf wartet, passiert zu werden. Dies wird fast immer von diesem Beispiel begleitet:

 #define max(a, b) ((a) > (b) ? (a) : (b)) ... int x = 3; int z = 2; int y = max(x++, z);

Und dann gibt es noch eine Frage: Welchen Wert hat x nach diesem Codestück, und die Antwort ist 5 , weil x zweimal erhöht wird, einmal auf jeder Seite des ? -Operator.

Das einzige Problem ist, dass in diesem Szenario niemand Makros verwendet. Makros sind schlecht, wenn sie in einem Szenario verwendet werden, in dem normale Funktionen gut funktionieren, insbesondere wenn sie vorgeben, Funktionen zu sein, sodass der Benutzer sich ihrer Nebenwirkungen nicht bewusst ist. Wir werden sie jedoch nicht als Funktionen verwenden, und wir werden Blockbuchstaben für ihre Namen verwenden, um deutlich zu machen, dass es sich nicht um Funktionen handelt. Wir werden nicht in der Lage sein, sie richtig zu debuggen, und das ist schlecht, aber wir werden damit leben, da die Alternative darin besteht, denselben Code dutzende Male zu kopieren und einzufügen, was viel fehleranfälliger ist als Makros. Eine Lösung für dieses Problem ist das Schreiben des Codegenerators, aber warum sollten wir ihn schreiben, wenn wir bereits einen in C++ eingebettet haben?

Dogmen in der Programmierung sind fast immer schlecht. Ich verwende hier „fast“ vorsichtig, nur um nicht rekursiv in die Dogma-Falle zu tappen, die ich gerade aufgestellt habe.

Den Code und alle Makros für diesen Teil finden Sie hier.

Variablen

Im vorigen Teil habe ich erwähnt, dass Stork nicht in Binärdateien oder ähnliches wie Assemblersprache kompiliert wird, aber ich habe auch gesagt, dass es eine statisch typisierte Sprache sein wird. Daher wird es kompiliert, aber in einem C++-Objekt, das ausgeführt werden kann. Es wird später klarer, aber fürs Erste wollen wir einfach festhalten, dass alle Variablen eigenständige Objekte sein werden.

Da wir sie im globalen Variablencontainer oder auf dem Stapel behalten möchten, besteht ein bequemer Ansatz darin, die Basisklasse zu definieren und von ihr zu erben.

 class variable; using variable_ptr = std::shared_ptr<variable>; class variable: public std::enable_shared_from_this<variable> { private: variable(const variable&) = delete; void operator=(const variable&) = delete; protected: variable() = default; public: virtual ~variable() = default; virtual variable_ptr clone() const = 0; template <typename T> T static_pointer_downcast() { return std::static_pointer_cast< variable_impl<typename T::element_type::value_type> >(shared_from_this()); } };

Wie Sie sehen können, ist es ziemlich einfach, und die Funktion clone , die die tiefe Kopie durchführt, ist neben dem Destruktor ihre einzige virtuelle Elementfunktion.

Da wir Objekte dieser Klasse immer über shared_ptr verwenden werden, ist es sinnvoll, sie von std::enable_shared_from_this zu erben, damit wir den Shared Pointer leicht daraus bekommen können. Die Funktion static_pointer_downcast dient der Bequemlichkeit, da wir häufig von dieser Klasse auf ihre Implementierung umsteigen müssen.

Die eigentliche Implementierung dieser Klasse ist variable_impl , parametrisiert mit dem Typ, den sie enthält. Es wird für die vier Typen instanziiert, die wir verwenden werden:

 using number = double; using string = std::shared_ptr<std::string>; using array = std::deque<variable_ptr>; using function = std::function<void(runtime_context&)>;

Wir werden double als Nummerntyp verwenden. Zeichenfolgen werden referenzgezählt, da sie unveränderlich sind, um bestimmte Optimierungen zu ermöglichen, wenn sie als Wert übergeben werden. Array ist std::deque , da es stabil ist, und beachten Sie, dass runtime_context die Klasse ist, die alle relevanten Informationen über den Programmspeicher während der Laufzeit enthält. Dazu kommen wir später.

Häufig werden auch folgende Definitionen verwendet:

 using lvalue = variable_ptr; using lnumber = std::shared_ptr<variable_impl<number>>; using lstring = std::shared_ptr<variable_impl<string>>; using larray = std::shared_ptr<variable_impl<array>>; using lfunction = std::shared_ptr<variable_impl<function>>;

Das hier verwendete „l“ wird für „lvalue“ abgekürzt. Immer wenn wir einen Lvalue für einen Typ haben, verwenden wir den gemeinsam genutzten Zeiger auf variable_impl .

Laufzeitkontext

Während der Laufzeit wird der Speicherzustand in der Klasse runtime_context gehalten.

 class runtime_context{ private: std::vector<variable_ptr> _globals; std::deque<variable_ptr> _stack; std::stack<size_t> _retval_idx; public: runtime_context(size_t globals); variable_ptr& global(int idx); variable_ptr& retval(); variable_ptr& local(int idx); void push(variable_ptr v); void end_scope(size_t scope_vars); void call(); variable_ptr end_function(size_t params); };

Es wird mit der Anzahl der globalen Variablen initialisiert.

• _globals behält alle globalen Variablen. Auf sie wird mit der Memberfunktion global mit dem absoluten Index zugegriffen.
• _stack behält lokale Variablen und Funktionsargumente, und die Ganzzahl am Anfang von _retval_idx behält den absoluten Index des aktuellen Rückgabewerts in _stack .
• Auf den Rückgabewert wird mit der Funktion retval , während auf lokale Variablen und Funktionsargumente mit der Funktion local zugegriffen wird, indem der Index relativ zum aktuellen Rückgabewert übergeben wird. Funktionsargumente haben in diesem Fall negative Indizes.
• Die push -Funktion fügt die Variable dem Stack hinzu, während end_scope die übergebene Anzahl von Variablen aus dem Stack entfernt.
• Die call ändert die Größe des Stapels um eins und verschiebt den Index des letzten Elements in _stack auf _retval_idx .
• end_function entfernt den Rückgabewert und die übergebene Anzahl von Argumenten vom Stapel und gibt auch den entfernten Rückgabewert zurück.

Wie Sie sehen können, werden wir keine Low-Level-Speicherverwaltung implementieren und die native (C++) Speicherverwaltung nutzen, die wir als selbstverständlich ansehen können. Wir werden auch keine Heap-Allokationen implementieren, zumindest vorerst.

Mit runtime_context haben wir endlich alle Bausteine, die für die zentrale und schwierigste Komponente dieses Teils benötigt werden.

Ausdrücke

Um die komplizierte Lösung, die ich hier vorstellen werde, vollständig zu erklären, werde ich Ihnen kurz einige gescheiterte Versuche vorstellen, die ich unternommen habe, bevor ich mich für diesen Ansatz entschieden habe.

Der einfachste Ansatz besteht darin, jeden Ausdruck als variable_ptr auszuwerten und diese virtuelle Basisklasse zu haben:

 class expression { ... public: variable_ptr evaluate(runtime_context& context) const = 0; lnumber evaluate_lnumber(runtime_context& context) const { return evaluate(context)->static_pointer_downcast<lnumber>(); } lstring evaluate_lstring(runtime_context& context) const { return evaluate(context)->static_pointer_downcast<lstring>(); } number evaluate_number(runtime_context& context) const { return evaluate_lnumber(context)->value; } string evaluate_string(runtime_context& context) const { return evaluate_lstring(context)->value; } ... }; using expression_ptr = std::unique_ptr<expression>;

Von dieser Klasse würden wir dann für jede Operation wie Addition, Verkettung, Funktionsaufruf usw. erben. Dies wäre beispielsweise die Implementierung des Additionsausdrucks:

 class add_expression: public expression { private: expression_ptr _expr1; expression_ptr _expr2; public: ... variable_ptr evaluate(runtime_context& context) const override{ return std::make_shared<variable_impl<number> >( _expr1->evaluate_number(context) + _expr2->evaluate_number(context) ); } ... };

Wir müssen also beide Seiten ( _expr1 und _expr2 ) auswerten, sie hinzufügen und dann variable_impl<number> konstruieren.

Wir können Variablen sicher downcasten, weil wir ihren Typ während der Kompilierzeit überprüft haben, also ist das hier nicht das Problem. Das große Problem ist jedoch die Leistungseinbuße, die wir für die Heap-Zuweisung des zurückgegebenen Objekts bezahlen, die – theoretisch – nicht benötigt wird. Wir tun dies, um die virtuelle Funktionsdeklaration zu erfüllen. In der ersten Version von Stork werden wir diese Strafe haben, wenn wir Zahlen von Funktionen zurückgeben. Ich kann damit leben, aber nicht mit dem einfachen Pre-Increment-Ausdruck, der die Heap-Zuweisung durchführt.

Dann habe ich es mit typspezifischen Ausdrücken versucht, die von der gemeinsamen Basis geerbt wurden:

 class expression { ... public: virtual void evaluate(runtime_context& context) const = 0; ... }; class lvalue_expression: public virtual expression { ... public: virtual lvalue evaluate_lvalue(runtime_context& context) const = 0; void evaluate(runtime_context& context) const override { evaluate_lvalue(context); } ... }; using lvalue_expression_ptr = std::unique_ptr<lvalue_expression>; class number_expression: public virtual expression { ... public: virtual number evaluate_number(runtime_context& context) const = 0; void evaluate(runtime_context& context) const override { evaluate_number(context); } ... }; using number_expression_ptr = std::unique_ptr<number_expression>; class lnumber_expression: public lvalue_expression, public number_expression { ... public: virtual lnumber evaluate_lnumber(runtime_context& context) const = 0; lvalue evaluate_lvalue(runtime_context& context) const override { return evaluate_lnumber(context); } number evaluate_number(runtime_context& context) const override { return evaluate_lnumber(context)->value; } void evaluate(runtime_context& context) const override { return evaluate_lnumber(context); } ... }; using lnumber_expression_ptr = std::unique_ptr<lnumber_expression>;

Dies ist nur ein Teil der Hierarchie (nur für Zahlen), und wir sind bereits auf Probleme mit der Rautenform gestoßen (die Klasse erbt zwei Klassen mit derselben Basisklasse).

Glücklicherweise bietet C++ virtuelle Vererbung, die es ermöglicht, von der Basisklasse zu erben, indem der Zeiger darauf in der geerbten Klasse beibehalten wird. Wenn also die Klassen B und C virtuell von A erben und die Klasse D von B und C erbt, gäbe es nur eine Kopie von A in D.

Es gibt jedoch eine Reihe von Strafen, die wir in diesem Fall zahlen müssen – Leistung und die Unfähigkeit, von A herunterzufallen, um nur einige zu nennen –, aber dies sah immer noch nach einer Gelegenheit für mich aus, das virtuelle Erbe zum ersten Mal in Anspruch zu nehmen mein Leben.

Jetzt sieht die Implementierung des Additionsausdrucks natürlicher aus:

 class add_expression: public number_expression { private: number_expression_ptr _expr1; number_expression_ptr _expr2; public: ... number evaluate_number(runtime_context& context) const override{ return _expr1->evaluate_number(context) + _expr2->evaluate_number(context); } ... };

In Bezug auf die Syntax gibt es nichts mehr zu verlangen, und das ist so natürlich wie es nur geht. Wenn jedoch einer der inneren Ausdrücke ein lvalue-Zahlenausdruck ist, sind zwei virtuelle Funktionsaufrufe erforderlich, um ihn auszuwerten. Nicht perfekt, aber auch nicht schrecklich.

Lassen Sie uns dieser Mischung Streicher hinzufügen und sehen, wo es uns hinführt:

 class string_expression: public virtual expression { ... public: virtual string evaluate_string(runtime_context& context) const = 0; void evaluate(runtime_context& context) const override { evaluate_string(context); } ... }; using string_expression_ptr = std::unique_ptr<string_expression>;

Da wir möchten, dass die Zahlen in Strings konvertiert werden können, müssen wir number_expression von string_expression erben.

 class number_expression: public string_expression { ... public: virtual number evaluate_number(runtime_context& context) const = 0; string evaluate_string(runtime_context& context) const override { return tostring(evaluate_number(context)); } void evaluate(runtime_context& context) const override { evaluate_number(context); } ... }; using number_expression_ptr = std::unique_ptr<number_expression>;

Wir haben das überlebt, aber wir müssen die Methode „ evaluate virtual“ erneut überschreiben, oder wir werden ernsthafte Leistungsprobleme aufgrund einer unnötigen Konvertierung von Zahl in Zeichenfolge haben.

Die Dinge werden also offensichtlich hässlich, und unser Design überlebt sie kaum, weil wir nicht zwei Arten von Ausdrücken haben, die ineinander umgewandelt werden sollten (in beide Richtungen). Wenn das der Fall war oder wenn wir versuchten, irgendeine Art von zirkulärer Konvertierung zu erreichen, konnte unsere Hierarchie nicht damit umgehen. Schließlich sollte die Hierarchie eine Ist-eine-Beziehung widerspiegeln, nicht eine Ist-umwandelbare-in-Beziehung, die schwächer ist.

All diese erfolglosen Versuche führten mich zu einem komplizierten, aber meiner Meinung nach richtigen Design. Erstens ist es für uns nicht entscheidend, eine einzige Basisklasse zu haben. Wir brauchen die Ausdrucksklasse, die zu void ausgewertet würde, aber wenn wir in der Kompilierzeit zwischen void-Ausdrücken und Ausdrücken anderer Art unterscheiden können, besteht keine Notwendigkeit, zwischen ihnen in einer Laufzeit zu konvertieren. Daher parametrisieren wir die Basisklasse mit dem Rückgabetyp des Ausdrucks.

Hier ist die vollständige Implementierung dieser Klasse:

 template <typename R> class expression { expression(const expression&) = delete; void operator=(const expression&) = delete; protected: expression() = default; public: using ptr = std::unique_ptr<const expression>; virtual R evaluate(runtime_context& context) const = 0; virtual ~expression() = default; };

Wir haben nur einen virtuellen Funktionsaufruf pro Ausdrucksauswertung (natürlich müssen wir ihn rekursiv aufrufen), und da wir nicht in Binärcode kompilieren, ist das ein ziemlich gutes Ergebnis. Das einzige, was noch zu tun ist, ist die Konvertierung zwischen Typen, wenn es erlaubt ist.

Dazu parametrisieren wir jeden Ausdruck mit dem Rückgabetyp und erben ihn von der entsprechenden Basisklasse. Dann konvertieren wir in der evaluate das Auswertungsergebnis in den Rückgabewert dieser Funktion.

Dies ist beispielsweise unser Additionsausdruck:

 template <typename R> class add_expression: public expression<R> { ... R evaluate(runtime_context& context) const override{ return convert<R>( _expr1->evaluate(context) + _expr2->evaluate(context) ); } ... };

Um die „convert“-Funktion zu schreiben, brauchen wir etwas Infrastruktur:

 template<class V, typename T> struct is_boxed { static const bool value = false; }; template<typename T> struct is_boxed<std::shared_ptr<variable_impl<T> >, T> { static const bool value = true; }; string convert_to_string(number n) { std::string str if (n == int(n)) { str = std::to_string(int(n)); } else { str = std::to_string(n); } return std::make_shared<std::string>(std::move(str)); } string convert_to_string(const lnumber& v) { return convert_to_string(v->value); }

Die Struktur is_boxed ist ein Typmerkmal, das eine innere Konstante, value , hat, die zu wahr ausgewertet wird, wenn (und nur wenn) der erste Parameter ein gemeinsam genutzter Zeiger auf variable_impl ist, der mit dem zweiten Typ parametrisiert ist.

Die Implementierung der convert -Funktion wäre auch in älteren Versionen von C++ möglich, aber es gibt in C++17 eine sehr nützliche Anweisung namens if constexpr , die die Bedingung in der Kompilierzeit auswertet. Wenn es zu false ausgewertet wird, wird der Block vollständig gelöscht, selbst wenn dies den Kompilierzeitfehler verursacht. Andernfalls wird der else -Block gelöscht.

 template<typename To, typename From> auto convert(From&& from) { if constexpr(std::is_convertible<From, To>::value) { return std::forward<From>(from); } else if constexpr(is_boxed<From, To>::value) { return unbox(std::forward<From>(from)); } else if constexpr(std::is_same<To, string>::value) { return convert_to_string(from); } else { static_assert(std::is_void<To>::value); } }

Versuchen Sie, diese Funktion zu lesen:

• Konvertieren, wenn es in C++ konvertierbar ist (dies gilt für den Upcast des variable_impl -Zeigers).
• Unbox, wenn es verpackt ist.
• In String konvertieren, wenn der Zieltyp String ist.
• Tun Sie nichts und prüfen Sie, ob das Ziel leer ist.

Meiner Meinung nach ist dies viel besser lesbar als die ältere Syntax, die auf SFINAE basiert.

Ich werde einen kurzen Überblick über Ausdrucksarten geben und einige technische Details weglassen, um es einigermaßen kurz zu halten.

Es gibt drei Arten von Blattausdrücken in einem Ausdrucksbaum:

• Globaler Variablenausdruck
• Lokaler Variablenausdruck
• Konstanter Ausdruck

 template<typename R, typename T> class global_variable_expression: public expression<R> { private: int _idx; public: global_variable_expression(int idx) : _idx(idx) { } R evaluate(runtime_context& context) const override { return convert<R>( context.global(_idx) ->template static_pointer_downcast<T>() ); } };

Sie wird neben dem Rückgabetyp auch mit dem Variablentyp parametriert. Lokale Variablen werden ähnlich behandelt, und dies ist die Klasse für Konstanten:

 template<typename R, typename T> class constant_expression: public expression<R> { private: T _c; public: constant_expression(T c) : _c(std::move(c)) { } R evaluate(runtime_context& context) const override { return convert<R>(_c); } };

In diesem Fall konvertieren wir die Konstante sofort im Konstruktor.

Dies wird als Basisklasse für die meisten unserer Ausdrücke verwendet:

 template<class O, typename R, typename... Ts> class generic_expression: public expression<R> { private: std::tuple<typename expression<Ts>::ptr...> _exprs; template<typename... Exprs> R evaluate_tuple( runtime_context& context, const Exprs&... exprs ) const { return convert<R>(O()( std::move(exprs->evaluate(context))...) ); } public: generic_expression(typename expression<Ts>::ptr... exprs) : _exprs(std::move(exprs)...) { } R evaluate(runtime_context& context) const override { return std::apply( [&](const auto&... exprs){ return this->evaluate_tuple(context, exprs...); }, _exprs ); } };

Das erste Argument ist der Funktortyp, der instanziiert und für die Auswertung aufgerufen wird. Die restlichen Typen sind Rückgabetypen von untergeordneten Ausdrücken.

Um Boilerplate-Code zu reduzieren, definieren wir drei Makros:

 #define UNARY_EXPRESSION(name, code)\ struct name##_op {\ template <typename T1> \ auto operator()(T1 t1) {\ code;\ }\ };\ template<typename R, typename T1>\ using name##_expression = generic_expression<name##_op, R, T1>; #define BINARY_EXPRESSION(name, code)\ struct name##_op {\ template <typename T1, typename T2>\ auto operator()(T1 t1, T2 t2) {\ code;\ }\ };\ template<typename R, typename T1, typename T2>\ using name##_expression = generic_expression<name##_op, R, T1, T2>; #define TERNARY_EXPRESSION(name, code)\ struct name##_op {\ template <typename T1, typename T2, typename T3>\ auto operator()(T1 t1, T2 t2, T3 t3) {\ code;\ }\ };\ template<typename R, typename T1, typename T2, typename T3>\ using name##_expression = generic_expression<name##_op, R, T1, T2, T3>;

Beachten Sie, dass operator() als Vorlage definiert ist, obwohl dies normalerweise nicht der Fall sein muss. Es ist einfacher, alle Ausdrücke auf die gleiche Weise zu definieren, anstatt Argumenttypen als Makroargumente bereitzustellen.

Jetzt können wir die meisten Ausdrücke definieren. Dies ist beispielsweise die Definition für /= :

 BINARY_EXPRESSION(div_assign, t1->value /= t2; return t1; );

Mit diesen Makros können wir fast alle Ausdrücke definieren. Die Ausnahmen sind Operatoren, die eine definierte Reihenfolge der Auswertung von Argumenten haben (logischer && und || , ternärer ( ? ) und Komma ( , ) Operator), Array-Index, Funktionsaufruf und param_expression , der den Parameter klont, um ihn an die Funktion zu übergeben nach Wert.

Die Umsetzung ist nicht kompliziert. Die Implementierung von Funktionsaufrufen ist am komplexesten, daher werde ich sie hier erklären:

 template<typename R, typename T> class call_expression: public expression<R>{ private: expression<function>::ptr _fexpr; std::vector<expression<lvalue>::ptr> _exprs; public: call_expression( expression<function>::ptr fexpr, std::vector<expression<lvalue>::ptr> exprs ): _fexpr(std::move(fexpr)), _exprs(std::move(exprs)) { } R evaluate(runtime_context& context) const override { std::vector<variable_ptr> params; params.reserve(_exprs.size()); for (size_t i = 0; i < _exprs.size(); ++i) { params.push_back(_exprs[i]->evaluate(context)); } function f = _fexpr->evaluate(context); for (size_t i = params.size(); i > 0; --i) { context.push(std::move(params[i-1])); } context.call(); f(context); if constexpr (std::is_same<R, void>::value) { context.end_function(_exprs.size()); } else { return convert<R>( context.end_function( _exprs.size() )->template static_pointer_downcast<T>() ); } } };

Es bereitet den runtime_context , indem es alle ausgewerteten Argumente auf seinen Stack legt und die call Funktion aufruft. Anschließend ruft es das ausgewertete erste Argument auf (das die Funktion selbst ist) und gibt den Rückgabewert der end_function Methode zurück. Wir können hier auch die Verwendung der if constexpr Syntax sehen. Es erspart uns das Schreiben der Spezialisierung für die gesamte Klasse für Funktionen, die void zurückgeben.

Jetzt haben wir alles, was mit Ausdrücken zu tun hat, während der Laufzeit verfügbar. Das Einzige, was übrig bleibt, ist die Konvertierung vom geparsten Ausdrucksbaum (beschrieben im vorherigen Blogbeitrag) zum Ausdrucksbaum.

Ausdrucksgenerator

Um Verwirrung zu vermeiden, nennen wir verschiedene Phasen unseres Sprachentwicklungszyklus:

• Meta-Kompilierungszeit: Die Phase, in der der C++-Compiler ausgeführt wird
• Kompilierzeit: Die Phase, in der der Stork-Compiler ausgeführt wird
• Laufzeit: die Phase, in der das Stork-Skript ausgeführt wird

Hier ist der Pseudocode für den Ausdrucksgenerator:

 function build_expression(nodeptr n, compiler_context context) { if (n is constant) { return constant_expression(n.value); } else if (n is identifier) { id_info info = context.find(n.value); if (context.is_global(info)) { return global_variable_expression(info.index); } else { return local_variable_expression(info.index); } } else { //operation switch (n->value) { case preinc: return preinc_expression( build_expression(n->child[0]) ); ... case add: return add_expression( build_expression(n->child[0]), build_expression(n->child[1]) ); ... case call: return call_expression( n->child[0], //function n->child[1], //arg0 ... n->child[k+1], //argk ); } } }

Abgesehen davon, dass alle Operationen verarbeitet werden müssen, scheint dies ein einfacher Algorithmus zu sein.

Wenn es funktionieren würde, wäre es großartig, aber es funktioniert nicht. Für den Anfang müssen wir den Rückgabetyp der Funktion angeben, und er ist hier offensichtlich nicht festgelegt, da der Rückgabetyp von der Art des besuchten Knotens abhängt. Knotentypen sind zur Kompilierzeit bekannt, aber Rückgabetypen sollten zur Meta-Kompilierzeit bekannt sein.

Im vorherigen Beitrag habe ich erwähnt, dass ich den Vorteil von Sprachen, die eine dynamische Typprüfung durchführen, nicht sehe. In solchen Sprachen könnte der oben gezeigte Pseudocode fast wörtlich implementiert werden. Nun, ich bin mir der Vorteile dynamischer Sprachen durchaus bewusst. Sofortiges Karma vom Feinsten.

Glücklicherweise kennen wir den Typ des Ausdrucks der obersten Ebene – er hängt vom Kontext der Kompilierung ab, aber wir kennen seinen Typ, ohne den Ausdrucksbaum zu analysieren. Wenn wir zum Beispiel die for-Schleife haben:

 for (expression1; expression2; expression3) ...

Der erste und der dritte Ausdruck haben einen void -Rückgabetyp, weil wir nichts mit ihrem Auswertungsergebnis machen. Der zweite Ausdruck hat jedoch eine number , weil wir ihn mit Null vergleichen, um zu entscheiden, ob die Schleife beendet werden soll oder nicht.

Wenn wir den Typ des Ausdrucks kennen, der sich auf die Knotenoperation bezieht, bestimmt er normalerweise den Typ seines untergeordneten Ausdrucks.

Wenn beispielsweise der Ausdruck (expression1) += (expression2) den Typ lnumber hat, bedeutet dies, dass expression1 auch diesen Typ hat und expression2 den Typ number hat.

Der Ausdruck (expression1) < (expression2) hat jedoch immer den Typ number , aber ihre untergeordneten Ausdrücke können den Typ number oder den Typ string haben. Bei diesem Ausdruck prüfen wir, ob beide Knoten Zahlen sind. Wenn dies der Fall ist, werden wir expression1 und expression2 als expression<number> erstellen. Andernfalls sind sie vom Typ expression<string> .

Es gibt noch ein weiteres Problem, das wir berücksichtigen und lösen müssen.

Stellen Sie sich vor, wir müssten einen Ausdruck vom Typ number erstellen. Dann können wir nichts Gültiges zurückgeben, wenn wir auf einen Verkettungsoperator stoßen. Wir wissen, dass dies nicht passieren kann, da wir die Typen bereits beim Erstellen des Ausdrucksbaums (im vorherigen Teil) überprüft haben, aber das bedeutet, dass wir die mit dem Rückgabetyp parametrisierte Vorlagenfunktion nicht schreiben können, da sie abhängig davon ungültige Zweige haben wird auf diesem Rückgabetyp.

Ein Ansatz würde die Funktion nach Rückgabetyp unter Verwendung von if constexpr , aber es ist ineffizient, da wir den Code wiederholen müssen, wenn dieselbe Operation in mehreren Zweigen vorhanden ist. In diesem Fall könnten wir separate Funktionen schreiben.

Die implementierte Lösung teilt die Funktion basierend auf dem Knotentyp auf. In jedem Zweig prüfen wir, ob dieser Zweigtyp in den Rückgabetyp der Funktion konvertierbar ist. Wenn dies nicht der Fall ist, werfen wir den Compilerfehler aus, da dies niemals passieren sollte, aber der Code für eine so starke Behauptung zu kompliziert ist. Ich habe möglicherweise einen Fehler gemacht.

Wir verwenden die folgende selbsterklärende Type-Trait-Struktur, um die Konvertierbarkeit zu überprüfen:

 template<typename From, typename To> struct is_convertible { static const bool value = std::is_convertible<From, To>::value || is_boxed<From, To>::value || ( std::is_same<To, string>::value && ( std::is_same<From, number>::value || std::is_same<From, lnumber>::value ) ); };

Nach dieser Aufteilung ist der Code fast unkompliziert. Wir können semantisch vom ursprünglichen Ausdruckstyp in denjenigen umwandeln, den wir erstellen möchten, und es gibt keine Fehler in der Meta-Kompilierungszeit.

Es gibt jedoch eine Menge Boilerplate-Code, also habe ich mich stark auf Makros verlassen, um ihn zu reduzieren.

 template<typename R> class expression_builder{ private: using expression_ptr = typename expression<R>::ptr; static expression_ptr build_void_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_number_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_lnumber_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_string_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_lstring_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_array_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_larray_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_function_expression( const node_ptr& np, compiler_context& context ); static expression_ptr build_lfunction_expression( const node_ptr& np, compiler_context& context ); public: static expression_ptr build_expression( const node_ptr& np, compiler_context& context ) { return std::visit(overloaded{ [&](simple_type st){ switch (st) { case simple_type::number: if (np->is_lvalue()) { RETURN_EXPRESSION_OF_TYPE(lnumber); } else { RETURN_EXPRESSION_OF_TYPE(number); } case simple_type::string: if (np->is_lvalue()) { RETURN_EXPRESSION_OF_TYPE(lstring); } else { RETURN_EXPRESSION_OF_TYPE(string); } case simple_type::nothing: RETURN_EXPRESSION_OF_TYPE(void); } }, [&](const function_type& ft) { if (np->is_lvalue()) { RETURN_EXPRESSION_OF_TYPE(lfunction); } else { RETURN_EXPRESSION_OF_TYPE(function); } }, [&](const array_type& at) { if (np->is_lvalue()) { RETURN_EXPRESSION_OF_TYPE(larray); } else { RETURN_EXPRESSION_OF_TYPE(array); } } }, *np->get_type_id()); } };

Die Funktion build_expression ist hier die einzige öffentliche Funktion. Es ruft die Funktion std::visit für den Knotentyp auf. Diese Funktion wendet den übergebenen Funktor auf die variant an und entkoppelt sie dabei. Hier können Sie mehr darüber und über den overloaded Funktor lesen.

Das Makro RETURN_EXPRESSION_OF_TYPE ruft private Funktionen zum Erstellen von Ausdrücken auf und wirft eine Ausnahme, wenn die Konvertierung nicht möglich ist:

 #define RETURN_EXPRESSION_OF_TYPE(T)\ if constexpr(is_convertible<T, R>::value) {\ return build_##T##_expression(np, context);\ } else {\ throw expression_builder_error();\ return expression_ptr();\ }

Wir müssen den leeren Zeiger im Else-Zweig zurückgeben, da der Compiler den Rückgabetyp der Funktion im Falle einer unmöglichen Konvertierung nicht kennen kann; andernfalls erfordert std::visit , dass alle überladenen Funktionen denselben Rückgabetyp haben.

Da gibt es zum Beispiel die Funktion, die Ausdrücke mit string als Rückgabetyp aufbaut:

 static expression_ptr build_string_expression( const node_ptr& np, compiler_context& context ) { if (std::holds_alternative<std::string>(np->get_value())) { return std::make_unique<constant_expression<R, string>>( std::make_shared<std::string>( std::get<std::string>(np->get_value()) ) ); } CHECK_IDENTIFIER(lstring); switch (std::get<node_operation>(np->get_value())) { CHECK_BINARY_OPERATION(concat, string, string); CHECK_BINARY_OPERATION(comma, void, string); CHECK_TERNARY_OPERATION(ternary, number, string, string); CHECK_INDEX_OPERATION(lstring); CHECK_CALL_OPERATION(lstring); default: throw expression_builder_error(); } }

Es prüft, ob der Knoten eine Zeichenfolge constant_expression hält, und erstellt in diesem Fall einen konstanten_Ausdruck.

Dann prüft es, ob der Knoten einen Bezeichner enthält, und gibt in diesem Fall einen globalen oder lokalen Variablenausdruck vom Typ lstring zurück. Es kann einen Bezeichner enthalten, wenn wir konstante Variablen implementieren. Andernfalls wird davon ausgegangen, dass der Knoten die Knotenoperation enthält, und versucht alle Operationen, die string zurückgeben können.

Hier sind die Implementierungen der Makros CHECK_IDENTIFIER und CHECK_BINARY_OPERATION :

 #define CHECK_IDENTIFIER(T1)\ if (std::holds_alternative<identifier>(np->get_value())) {\ const identifier& id = std::get<identifier>(np->get_value());\ const identifier_info* info = context.find(id.name);\ if (info->is_global()) {\ return std::make_unique<\ global_variable_expression<R, T1>\ >(info->index());\ } else {\ return std::make_unique<\ local_variable_expression<R, T1>\ >(info->index());\ }\ }

 #define CHECK_BINARY_OPERATION(name, T1, T2)\ case node_operation::name:\ return expression_ptr(\ std::make_unique<name##_expression<R, T1, T2> > (\ expression_builder<T1>::build_expression(\ np->get_children()[0], context\ ),\ expression_builder<T2>::build_expression(\ np->get_children()[1], context\ )\ )\ );

Das CHECK_IDENTIFIER Makro muss compiler_context konsultieren, um einen globalen oder lokalen Variablenausdruck mit dem richtigen Index zu erstellen. Das ist die einzige Verwendung von „ compiler_context “ in dieser Struktur.

Sie können sehen, dass CHECK_BINARY_OPERATION rekursiv build_expression für die untergeordneten Knoten aufruft.

Einpacken

Auf meiner GitHub-Seite können Sie den vollständigen Quellcode abrufen, kompilieren und dann Ausdrücke eingeben und das Ergebnis der ausgewerteten Variablen anzeigen.

Ich stelle mir vor, dass es in allen Bereichen der menschlichen Kreativität einen Moment gibt, in dem der Autor erkennt, dass sein Produkt in gewissem Sinne lebendig ist. Bei der Konstruktion einer Programmiersprache ist es der Moment, in dem man sieht, dass die Sprache „atmet“.

Im nächsten und letzten Teil dieser Serie werden wir den Rest des minimalen Satzes von Sprachfunktionen implementieren, um zu sehen, wie es live läuft.