Stork, Partea 3: Implementarea expresiilor și variabilelor

În partea 3 a seriei noastre, limbajul nostru de programare ușor va rula în sfârșit. Nu va fi Turing-complet, nu va fi puternic, dar va fi capabil să evalueze expresii și chiar să apeleze funcții externe scrise în C++.

Voi încerca să descriu procesul cât mai detaliat posibil, în principal pentru că este scopul acestei serii de bloguri, dar și pentru propria mea documentare pentru că, în această parte, lucrurile s-au complicat puțin.

Am început să codific pentru această parte înainte de publicarea celui de-al doilea articol, dar apoi s-a dovedit că parserul de expresii ar trebui să fie o componentă de sine stătătoare care merită propria postare pe blog.

Acest lucru, împreună cu unele tehnici de programare infame, a făcut posibil ca această parte să nu fie monstruos de mare și, totuși, unii cititori vor indica, cel mai probabil, tehnicile de programare menționate și se vor întreba de ce a trebuit să le folosesc.

De ce folosim macrocomenzi?

Pe măsură ce am acumulat experiență de programare lucrând la diferite proiecte și cu diferiți oameni, am învățat că dezvoltatorii tind să fie destul de dogmatici - probabil pentru că este mai ușor așa.

Prima dogmă a programării este că afirmația goto este rea, diabolică și oribilă. Pot să înțeleg de unde provine acel sentiment și sunt de acord cu această noțiune în marea majoritate a cazurilor când cineva folosește declarația goto . De obicei, poate fi evitat, iar în schimb ar putea fi scris un cod mai lizibil.

Cu toate acestea, nu se poate nega că ruperea din bucla interioară în C++ poate fi realizată cu ușurință cu instrucțiunea goto . Alternativa – care necesită o variabilă bool sau o funcție dedicată – ar putea fi mai puțin lizibilă decât codul care se încadrează în mod dogmatic în găleata tehnicilor de programare interzise.

A doua dogma, relevantă exclusiv pentru dezvoltatorii C și C++, este că macro-urile sunt rele, rele, îngrozitoare și, practic, un dezastru care așteaptă să se întâmple. Acesta este aproape întotdeauna însoțit de acest exemplu:

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

Și apoi există o întrebare: Care este valoarea lui x după această bucată de cod, iar răspunsul este 5 deoarece x este incrementat de două ori, câte una pe fiecare parte a lui ? -operator.

Singura problemă este că nimeni nu folosește macrocomenzi în acest scenariu. Macro-urile sunt rele dacă sunt folosite într-un scenariu în care funcțiile obișnuite funcționează bine, mai ales dacă se prefac a fi funcții, astfel încât utilizatorul nu este conștient de efectele lor secundare. Cu toate acestea, nu le vom folosi ca funcții și vom folosi majuscule pentru numele lor pentru a face evident că nu sunt funcții. Nu vom putea să le depanăm corect, și asta e rău, dar vom trăi cu asta, deoarece alternativa este să copiați și lipiți același cod de zeci de ori, ceea ce este mult mai predispus la erori decât macrocomenzi. O soluție la această problemă este scrierea generatorului de cod, dar de ce ar trebui să-l scriem când avem deja unul încorporat în C++?

Dogmele în programare sunt aproape întotdeauna rele. Folosesc cu precauție „aproape” aici doar pentru a evita căderea recursiva în capcana dogmatică pe care tocmai am instalat-o.

Puteți găsi codul și toate macrocomenzile pentru această parte aici.

Variabile

În partea anterioară, am menționat că Stork nu va fi compilat în binar sau ceva similar cu limbajul de asamblare, dar am mai spus că va fi un limbaj tipizat static. Prin urmare, va fi compilat, dar într-un obiect C++ care se va putea executa. Va deveni mai clar mai târziu, dar deocamdată, să spunem doar că toate variabilele vor fi obiecte de la sine.

Deoarece dorim să le păstrăm în containerul de variabile globale sau pe stivă, o abordare convenabilă este să definim clasa de bază și să moștenim din ea.

 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()); } };

După cum puteți vedea, este destul de simplu, iar clone funcției, care face copierea profundă, este singura funcție de membru virtual, în afară de destructor.

Deoarece vom folosi întotdeauna obiecte din această clasă prin shared_ptr , este logic să o moștenim de la std::enable_shared_from_this , astfel încât să putem obține cu ușurință pointerul partajat de la acesta. Funcția static_pointer_downcast este aici pentru comoditate, deoarece va trebui frecvent să reducem de la această clasă la implementarea ei.

Implementarea reală a acestei clase este variable_impl , parametrizată cu tipul pe care îl deține. Acesta va fi instanțiat pentru cele patru tipuri pe care le vom folosi:

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

Vom folosi double ca tip de număr. Șirurile sunt numărate în funcție de referință, deoarece vor fi imuabile, pentru a permite anumite optimizări atunci când le transmit după valoare. Array va fi std::deque , deoarece este stabil și să reținem doar că runtime_context este clasa care deține toate informațiile relevante despre memoria programului în timpul rulării. Vom ajunge la asta mai târziu.

Următoarele definiții sunt de asemenea folosite frecvent:

 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>>;

„l” folosit aici este prescurtat pentru „lvalue”. Ori de câte ori avem o valoare l pentru un anumit tip, vom folosi pointerul partajat la variable_impl .

Contextul de rulare

În timpul rulării, starea memoriei este păstrată în clasa runtime_context .

 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); };

Este inițializat cu numărul de variabile globale.

• _globals păstrează toate variabilele globale. Acestea sunt accesate cu funcția membru global cu index absolut.
• _stack păstrează variabilele locale și argumentele funcției, iar întregul din partea de sus a _retval_idx păstrează indexul absolut în _stack al valorii returnate curente.
• Valoarea returnată este accesată cu funcția retval , în timp ce variabilele locale și argumentele funcției sunt accesate cu funcția local prin trecerea indexului relativ la valoarea returnată curentă. Argumentele funcției au indici negativi în acest caz.
• Funcția push adaugă variabila la stivă, în timp ce end_scope elimină numărul de variabile trecute din stivă.
• Funcția de call va redimensiona stiva cu unul și va împinge indexul ultimului element din _stack la _retval_idx .
• end_function elimină valoarea returnată și numărul de argumente transmis din stivă și returnează, de asemenea, valoarea returnată eliminată.

După cum puteți vedea, nu vom implementa niciun management de memorie de nivel scăzut și vom profita de gestionarea memoriei native (C++), pe care o putem lua de la sine înțeles. Nu vom implementa nicio alocare heap, cel puțin deocamdată.

Cu runtime_context , avem în sfârșit toate blocurile necesare pentru componenta centrală și cea mai dificilă a acestei părți.

Expresii

Pentru a explica pe deplin soluția complicată pe care o voi prezenta aici, vă voi prezenta pe scurt câteva încercări eșuate pe care le-am făcut înainte de a decide această abordare.

Cea mai ușoară abordare este de a evalua fiecare expresie ca variable_ptr și de a avea această clasă de bază virtuală:

 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>;

Apoi vom moșteni din această clasă pentru fiecare operație, cum ar fi adăugarea, concatenarea, apelul de funcție etc. De exemplu, aceasta ar fi implementarea expresiei de adăugare:

 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) ); } ... };

Deci trebuie să evaluăm ambele părți ( _expr1 și _expr2 ), să le adăugăm și apoi să construim variable_impl<number> .

Putem reduce în siguranță variabilele deoarece le-am verificat tipul în timpul compilării, așa că nu aceasta este problema aici. Cu toate acestea, marea problemă este penalizarea de performanță pe care o plătim pentru alocarea heap-ului obiectului returnat, care, în teorie, nu este necesară. Facem asta pentru a satisface declarația funcției virtuale. În prima versiune de Stork, vom avea acea penalizare atunci când returnăm numerele din funcții. Pot trăi cu asta, dar nu cu simpla expresie pre-incrementare care face alocarea heap.

Apoi, am încercat cu expresii specifice tipului moștenite de la baza comună:

 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>;

Aceasta este doar o parte a ierarhiei (doar pentru numere) și deja am întâlnit probleme de formă de diamant (clasa moștenind două clase cu aceeași clasă de bază).

Din fericire, C++ oferă moștenire virtuală, ceea ce oferă posibilitatea de a moșteni din clasa de bază, păstrând pointerul către aceasta, în clasa moștenită. Prin urmare, dacă clasele B și C moștenesc practic de la A, iar clasa D moștenește de la B și C, ar exista o singură copie a lui A în D.

Există totuși o serie de penalități pe care trebuie să le plătim în acest caz—performanță și incapacitatea de a reduce de la A, pentru a numi câteva—dar aceasta mi-a părut totuși o oportunitate de a folosi moștenirea virtuală pentru prima dată în viata mea.

Acum, implementarea expresiei de adăugare va arăta mai naturală:

 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); } ... };

Din punct de vedere al sintaxei, nu mai este nimic de cerut, iar acest lucru este cât se poate de natural. Cu toate acestea, dacă oricare dintre expresiile interioare este o expresie numerică lvalue, va necesita două apeluri de funcții virtuale pentru ao evalua. Nu perfect, dar nici groaznic.

Să adăugăm șiruri în acest mix și să vedem unde ne duce:

 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>;

Deoarece dorim ca numerele să fie convertibile în șiruri de caractere, trebuie să moștenim number_expression de la string_expression .

 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>;

Am supraviețuit, dar trebuie să înlocuim din nou metoda de evaluate virtuală, sau ne vom confrunta cu probleme serioase de performanță din cauza conversiei inutile din număr în șir.

Deci, în mod evident, lucrurile devin urâte, iar designul nostru abia le supraviețuiește, deoarece nu avem două tipuri de expresii care ar trebui convertite una în alta (în ambele sensuri). Dacă acesta ar fi fost cazul, sau dacă am încercat să avem orice fel de conversie circulară, ierarhia noastră nu ar putea face față. La urma urmei, ierarhia ar trebui să reflecte este-o relație, nu este-convertibilă-în relație, care este mai slabă.

Toate aceste încercări nereușite m-au condus la un design complicat și totuși - în opinia mea - adecvat. În primul rând, a avea o singură clasă de bază nu este crucială pentru noi. Avem nevoie de clasa de expresii care ar evalua void, dar dacă putem distinge între expresii void și expresii de alt fel în timpul compilării, nu este nevoie să facem conversie între ele într-un timp de execuție. Prin urmare, vom parametriza clasa de bază cu tipul returnat al expresiei.

Iată implementarea completă a acelei clase:

 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; };

Vom avea un singur apel de funcție virtuală pentru fiecare evaluare a expresiei (desigur, va trebui să o numim recursiv) și, din moment ce nu compilăm în cod binar, este un rezultat destul de bun. Singurul lucru rămas de făcut este conversia între tipuri, atunci când este permisă.

Pentru a realiza acest lucru, vom parametriza fiecare expresie cu tipul returnat și o vom moșteni din clasa de bază corespunzătoare. Apoi, în funcția evaluate , vom converti rezultatul evaluării în valoarea returnată a acelei funcție.

De exemplu, aceasta este expresia noastră de adăugare:

 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) ); } ... };

Pentru a scrie funcția „convertire”, avem nevoie de o infrastructură:

 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); }

Structura is_boxed este o trăsătură de tip care are o constantă interioară, value , care se evaluează la adevărat dacă (și numai dacă) primul parametru este un pointer partajat la variable_impl parametrizat cu al doilea tip.

Implementarea funcției de convert ar fi posibilă chiar și în versiunile mai vechi de C++, dar există o declarație foarte utilă în C++17 numită if constexpr , care evaluează condiția în timpul compilării. Dacă se evaluează la false , va elimina blocul cu totul, chiar dacă provoacă eroarea de timp de compilare. În caz contrar, va renunța la blocul else .

 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); } }

Încercați să citiți această funcție:

• Convertiți dacă este convertibil în C++ (acesta este pentru variable_impl pointer upcast).
• Despachetați dacă este în cutie.
• Convertiți în șir dacă tipul țintă este șir.
• Nu faceți nimic și verificați dacă ținta este nulă.

În opinia mea, aceasta este mult mai lizibilă decât sintaxa mai veche bazată pe SFINAE.

Voi oferi o scurtă prezentare generală a tipurilor de expresii și voi omite câteva detalii tehnice pentru a fi suficient de scurtă.

Există trei tipuri de expresii de frunze într-un arbore de expresii:

• Expresie variabilă globală
• Expresie variabilă locală
• Expresie constantă

 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>() ); } };

În afară de tipul de returnare, acesta este parametrizat și cu tipul de variabilă. Variabilele locale sunt tratate în mod similar, iar aceasta este clasa pentru constante:

 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); } };

În acest caz, convertim constanta imediat în constructor.

Aceasta este folosită ca clasă de bază pentru majoritatea expresiilor noastre:

 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 ); } };

Primul argument este tipul de functor care va fi instanțiat și chemat pentru evaluare. Restul tipurilor sunt tipuri returnate de expresii copil.

Pentru a reduce codul standard, definim trei macrocomenzi:

 #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>;

Observați că operator() este definit ca un șablon, deși de obicei nu trebuie să fie. Este mai ușor să definiți toate expresiile în același mod în loc să furnizați tipuri de argumente ca argumente macro.

Acum, putem defini majoritatea expresiilor. De exemplu, aceasta este definiția pentru /= :

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

Putem defini aproape toate expresiile folosind aceste macrocomenzi. Excepțiile sunt operatorii care au o ordine definită de evaluare a argumentelor (operator && și || , ternar ( ? ) și virgulă ( , ) definită), indexul matricei, apelul funcției și expresia_parametrului, care param_expression parametrul pentru a-l transmite funcției. după valoare.

Nu este nimic complicat în implementarea acestora. Implementarea apelurilor de funcție este cea mai complexă, așa că o voi explica aici:

 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>() ); } } };

Pregătește runtime_context împingând toate argumentele evaluate pe stiva sa și apelând funcția de call . Apoi apelează primul argument evaluat (care este funcția însăși) și returnează valoarea returnată a metodei end_function . Putem vedea și aici utilizarea sintaxei if constexpr . Ne scutește de a scrie specializarea pentru întreaga clasă pentru funcțiile care returnează void .

Acum, avem tot ce este legat de expresii disponibile în timpul rulării. Singurul lucru rămas este conversia din arborele de expresii analizat (descris în postarea anterioară de blog) în arborele de expresii.

Generator de expresii

Pentru a evita confuzia, să numim diferite faze ale ciclului nostru de dezvoltare a limbajului:

• Meta-compilare-time: faza în care se execută compilatorul C++
• Timp de compilare: faza în care se execută compilatorul Stork
• Timp de execuție: faza în care rulează scriptul Stork

Iată pseudo-codul pentru generatorul de expresii:

 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 ); } } }

Pe lângă faptul că trebuie să se ocupe de toate operațiunile, acesta pare a fi un algoritm simplu.

Dacă ar funcționa, ar fi grozav, dar nu funcționează. Pentru început, trebuie să specificăm tipul de returnare al funcției și, evident, nu este fixat aici, deoarece tipul de returnare depinde de tipul de nod pe care îl vizităm. Tipurile de noduri sunt cunoscute în timp de compilare, dar tipurile de returnare ar trebui să fie cunoscute în timpul meta-compilării.

În postarea anterioară, am menționat că nu văd avantajul limbilor care fac verificare dinamică de tip. În astfel de limbi, pseudo-codul prezentat mai sus ar putea fi implementat aproape literal. Acum, sunt destul de conștient de avantajele limbajelor de tip dinamic. Karma instantanee la maxim.

Din fericire, cunoaștem tipul expresiei de nivel superior - depinde de contextul compilației, dar îi cunoaștem tipul fără a analiza arborele de expresie. De exemplu, dacă avem bucla for:

 for (expression1; expression2; expression3) ...

Prima și a treia expresie au un tip de returnare void deoarece nu facem nimic cu rezultatul evaluării lor. A doua expresie, însă, are un number de tip pentru că o comparăm cu zero, pentru a decide dacă să oprim sau nu bucla.

Dacă cunoaștem tipul expresiei care are legătură cu operațiunea nodului, acesta va determina de obicei tipul expresiei sale copil.

De exemplu, dacă expresia (expression1) += (expression2) are tipul lnumber , înseamnă că expression1 are și acel tip, iar expression2 are tipul number .

Cu toate acestea, expresia (expression1) < (expression2) are întotdeauna tipul number , dar expresiile lor secundare pot avea tip number sau tip string . În cazul acestei expresii, vom verifica dacă ambele noduri sunt numere. Dacă da, vom construi expression1 și expression2 ca expression<number> . În caz contrar, vor fi de tipul expression<string> .

Există o altă problemă de care trebuie să ținem cont și de care trebuie să ne confruntăm.

Imaginați-vă dacă trebuie să construim o expresie a number de tip . Apoi, nu putem returna nimic valid dacă întâlnim un operator de concatenare. Știm că nu se poate întâmpla, deoarece am verificat deja tipurile când am construit arborele de expresii (în partea anterioară), dar asta înseamnă că nu putem scrie funcția șablon, parametrizată cu tipul returnat, deoarece va avea ramuri invalide în funcție de pe acel tip de returnare.

O abordare ar împărți funcția după tipul de returnare, folosind if constexpr , dar este ineficientă deoarece dacă aceeași operație există în mai multe ramuri, va trebui să-i repetăm ​​codul. Am putea scrie funcții separate în acest caz.

Soluția implementată împarte funcția în funcție de tipul de nod. În fiecare dintre ramuri, vom verifica dacă acel tip de ramură este convertibil în tipul de returnare a funcției. Dacă nu este, vom arunca eroarea compilatorului, pentru că nu ar trebui să se întâmple niciodată, dar codul este prea complicat pentru o afirmație atât de puternică. Poate am făcut o eroare.

Pentru a verifica convertibilitatea, folosim următoarea structură de tip auto-explicativă:

 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 ) ); };

După această împărțire, codul este aproape simplu. Putem turna semantic de la tipul de expresie original la cel pe care vrem să îl construim și nu există erori în timpul meta-compilării.

Cu toate acestea, există o mulțime de coduri standard, așa că m-am bazat foarte mult pe macrocomenzi pentru a-l reduce.

 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()); } };

Funcția build_expression este singura funcție publică aici. Invocă funcția std::visit pe tipul de nod. Această funcție aplică functorul transmis pe variant , decuplându-l în proces. Puteți citi mai multe despre el și despre functorul overloaded aici.

Macrocomanda RETURN_EXPRESSION_OF_TYPE apelează funcții private pentru construirea expresiilor și aruncă o excepție dacă conversia nu este posibilă:

 #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();\ }

Trebuie să returnăm indicatorul gol în ramura else, deoarece compilatorul nu poate cunoaște tipul de returnare a funcției în cazul conversiei imposibile; în caz contrar, std::visit necesită ca toate funcțiile supraîncărcate să aibă același tip de returnare.

Există, de exemplu, funcția care construiește expresii cu string ca tip de returnare:

 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(); } }

Verifică dacă nodul menține șirul constant și construiește constant_expression dacă acesta este cazul.

Apoi, verifică dacă nodul deține un identificator și returnează expresia variabilă globală sau locală de tip lstring în acest caz. Poate deține un identificator dacă implementăm variabile constante. În caz contrar, se presupune că nodul deține operația nodului și încearcă toate operațiunile care pot returna string .

Iată implementările macrocomenzilor CHECK_IDENTIFIER și 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\ )\ )\ );

Macro-ul CHECK_IDENTIFIER trebuie să consulte compiler_context pentru a construi o expresie variabilă globală sau locală cu indexul corespunzător. Aceasta este singura utilizare a compiler_context în această structură.

Puteți vedea că CHECK_BINARY_OPERATION apelează recursiv build_expression pentru nodurile copil.

Încheierea

Pe pagina mea GitHub, puteți obține codul sursă complet, îl puteți compila și apoi introduceți expresii și vedeți rezultatul variabilelor evaluate.

Îmi imaginez că, în toate ramurile creativității umane, există un moment în care autoarea își dă seama că produsul lor este viu, într-un anumit sens. În construcția unui limbaj de programare, este momentul în care poți vedea că limbajul „respiră”.

În următoarea și ultima parte a acestei serii, vom implementa restul setului minim de caracteristici ale limbajului pentru a-l vedea rulând live.