Bocian, część 3: Implementacja wyrażeń i zmiennych
Opublikowany: 2022-03-11W części 3 naszej serii wreszcie zacznie działać nasz lekki język programowania. Nie będzie kompletny pod względem Turinga, nie będzie potężny, ale będzie w stanie oceniać wyrażenia, a nawet wywoływać funkcje zewnętrzne napisane w C++.
Postaram się opisać ten proces jak najdokładniej, głównie dlatego, że jest to cel tej serii blogów, ale także dla własnej dokumentacji, ponieważ w tej części sprawy trochę się skomplikowały.
Zacząłem kodować tę część przed publikacją drugiego artykułu, ale potem okazało się, że parser wyrażeń powinien być samodzielnym komponentem, który zasługuje na swój własny wpis na blogu.
To, wraz z kilkoma niesławnymi technikami programowania, sprawiło, że ta część nie była potwornie duża, a jednak niektórzy czytelnicy najprawdopodobniej wskażą na te techniki programowania i będą się zastanawiać, dlaczego musiałem ich użyć.
Dlaczego używamy makr?
Kiedy zdobywałem doświadczenie programistyczne pracując przy różnych projektach i z różnymi ludźmi, nauczyłem się, że programiści są dość dogmatyczni – prawdopodobnie dlatego, że w ten sposób jest łatwiej.
Pierwszy dogmat programowania mówi, że stwierdzenie goto jest złe, złe i okropne. Rozumiem, skąd bierze się ten sentyment i zgadzam się z tym poglądem w zdecydowanej większości przypadków, gdy ktoś używa instrukcji goto . Zwykle można tego uniknąć, a zamiast tego można napisać bardziej czytelny kod.
Jednak nie można zaprzeczyć, że wyrwanie się z wewnętrznej pętli w C++ można łatwo osiągnąć za pomocą goto . Alternatywa — która wymaga zmiennej bool lub dedykowanej funkcji — może być mniej czytelna niż kod, który dogmatycznie wpada w wiadro zabronionych technik programowania.
Drugi dogmat, odnoszący się wyłącznie do programistów C i C++, mówi, że makra są złe, złe, okropne iw zasadzie katastrofa, która może się wydarzyć. Prawie zawsze towarzyszy temu ten przykład:
#define max(a, b) ((a) > (b) ? (a) : (b)) ... int x = 3; int z = 2; int y = max(x++, z); A potem pojawia się pytanie: Jaka jest wartość x po tym kawałku kodu, a odpowiedź to 5 , ponieważ x jest zwiększane dwukrotnie, po jednym z każdej strony ? -operator.
Jedynym problemem jest to, że w tym scenariuszu nikt nie używa makr. Makra są złe, jeśli są używane w scenariuszu, w którym zwykłe funkcje działają dobrze, zwłaszcza jeśli udają, że są funkcjami, więc użytkownik nie jest świadomy ich skutków ubocznych. Jednak nie będziemy ich używać jako funkcji, a ich nazwy użyjemy literami blokowymi, aby było oczywiste, że nie są funkcjami. Nie będziemy w stanie poprawnie ich debugować, a to źle, ale będziemy z tym żyć, ponieważ alternatywą jest kopiowanie i wklejanie tego samego kodu dziesiątki razy, co jest znacznie bardziej podatne na błędy niż makra. Jednym z rozwiązań tego problemu jest napisanie generatora kodu, ale po co go pisać, skoro mamy już wbudowany w C++?
Dogmaty w programowaniu są prawie zawsze złe. Ostrożnie używam tutaj słowa „prawie”, aby uniknąć rekursywnego wpadania w pułapkę dogmatów, którą właśnie zastawiłem.
Kod i wszystkie makra do tej części znajdziesz tutaj.
Zmienne
W poprzedniej części wspomniałem, że Stork nie będzie kompilowany do formatu binarnego ani nic podobnego do asemblera, ale powiedziałem też, że będzie to język statycznie typowany. Dlatego zostanie skompilowany, ale w obiekcie C++, który będzie mógł zostać wykonany. Później stanie się to jaśniejsze, ale na razie załóżmy, że wszystkie zmienne będą same w sobie obiektami.
Ponieważ chcemy trzymać je w globalnym kontenerze zmiennych lub na stosie, jednym z wygodnych podejść jest zdefiniowanie klasy bazowej i dziedziczenie po niej.
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()); } }; Jak widać, jest to dość proste, a funkcja clone , która wykonuje głęboką kopię, jest jedyną wirtualną funkcją składową poza destruktorem.
Ponieważ zawsze będziemy używać obiektów tej klasy za pośrednictwem shared_ptr , sensowne jest odziedziczenie jej po std::enable_shared_from_this , tak abyśmy mogli łatwo uzyskać z niej wskaźnik do współdzielenia. Funkcja static_pointer_downcast jest tutaj dla wygody, ponieważ często będziemy musieli przejść z tej klasy do jej implementacji.
Prawdziwą implementacją tej klasy jest variable_impl , sparametryzowana typem, który przechowuje. Zostanie utworzona instancja dla czterech typów, których użyjemy:
using number = double; using string = std::shared_ptr<std::string>; using array = std::deque<variable_ptr>; using function = std::function<void(runtime_context&)>; Użyjemy double jako naszego typu liczby. Łańcuchy są liczone jako odwołania, ponieważ będą niezmienne, aby umożliwić pewne optymalizacje podczas przekazywania ich przez wartość. Tablica będzie std::deque , ponieważ jest stabilna, a zauważmy, że runtime_context to klasa, która przechowuje wszystkie istotne informacje o pamięci programu w czasie wykonywania. Dojdziemy do tego później.
Często używane są również następujące definicje:
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>>; Użyte tutaj „l” jest skrócone do „lvalue”. Ilekroć mamy lwartość dla jakiegoś typu, użyjemy wspólnego wskaźnika do variable_impl .
Kontekst wykonawczy
W czasie wykonywania stan pamięci jest przechowywany w klasie 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); };Jest inicjowany liczbą zmiennych globalnych.
-
_globalsprzechowuje wszystkie zmienne globalne. Dostęp do nich uzyskuje się za pomocą funkcji członkowskiejglobalz indeksem bezwzględnym. -
_stackprzechowuje zmienne lokalne i argumenty funkcji, a liczba całkowita na górze_retval_idxprzechowuje indeks bezwzględny w_stackbieżącej wartości zwracanej. - Dostęp do wartości zwracanej uzyskuje się za pomocą funkcji
retval, natomiast zmienne lokalne i argumenty funkcji uzyskuje się za pomocą funkcjilocalpoprzez przekazanie indeksu względem bieżącej wartości zwracanej. Argumenty funkcji mają w tym przypadku indeksy ujemne. - Funkcja
pushdodaje zmienną do stosu, podczas gdyend_scopeusuwa ze stosu przekazaną liczbę zmiennych. - Funkcja
callzmieni rozmiar stosu o jeden i przekaże indeks ostatniego elementu w_stackdo_retval_idx. -
end_functionusuwa wartość zwracaną i przekazaną liczbę argumentów ze stosu, a także zwraca usuniętą wartość zwracaną.
Jak widać, nie zaimplementujemy żadnego niskopoziomowego zarządzania pamięcią i skorzystamy z natywnego (C++) zarządzania pamięcią, co możemy przyjąć za pewnik. Przynajmniej na razie nie będziemy też wdrażać żadnych alokacji sterty.
Dzięki runtime_context , mamy w końcu wszystkie bloki potrzebne do centralnego i najtrudniejszego komponentu tej części.
Wyrażenia
Aby w pełni wyjaśnić skomplikowane rozwiązanie, które tutaj przedstawię, pokrótce przedstawię kilka nieudanych prób, które podjąłem przed podjęciem takiego podejścia.
Najprostszym podejściem jest oszacowanie każdego wyrażenia jako variable_ptr i posiadanie tej wirtualnej klasy bazowej:
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>;Następnie dziedziczylibyśmy z tej klasy dla każdej operacji, takiej jak dodawanie, konkatenacja, wywołanie funkcji itp. Na przykład byłaby to implementacja wyrażenia dodawania:
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) ); } ... }; Musimy więc obliczyć obie strony ( _expr1 i _expr2 ), dodać je, a następnie skonstruować variable_impl<number> .
Możemy bezpiecznie odrzucić zmienne, ponieważ sprawdzaliśmy ich typ w czasie kompilacji, więc nie o to tutaj chodzi. Jednak dużym problemem jest kara wydajnościowa, jaką płacimy za alokację sterty zwracanego obiektu, co teoretycznie nie jest potrzebne. Robimy to, aby spełnić deklarację funkcji wirtualnej. W pierwszej wersji Stork będziemy mieli tę karę, gdy zwrócimy liczby z funkcji. Mogę z tym żyć, ale nie z prostym wyrażeniem pre-inkrementacyjnym wykonującym alokację sterty.
Następnie spróbowałem z wyrażeniami specyficznymi dla typu odziedziczonymi ze wspólnej podstawy:
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>;To tylko część hierarchii (tylko dla liczb), a my już napotkaliśmy problemy w kształcie rombu (klasa dziedzicząca dwie klasy z tą samą klasą bazową).
Na szczęście C++ oferuje wirtualne dziedziczenie, które daje możliwość dziedziczenia po klasie bazowej, poprzez trzymanie wskaźnika w klasie dziedziczonej. Dlatego jeśli klasy B i C dziedziczą wirtualnie po A, a klasa D dziedziczy po B i C, to w D byłaby tylko jedna kopia A.
Istnieje jednak wiele kar, które musimy zapłacić w takim przypadku — wydajność i niemożność obniżenia wartości z A, żeby wymienić tylko kilka — ale nadal wyglądało to na okazję do skorzystania z wirtualnego dziedziczenia po raz pierwszy w moje życie.
Teraz implementacja wyrażenia dodawania będzie wyglądać bardziej naturalnie:
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); } ... };Jeśli chodzi o składnię, nie ma o co prosić i jest to tak naturalne, jak to tylko możliwe. Jeśli jednak którekolwiek z wyrażeń wewnętrznych jest wyrażeniem liczby l-wartości, do jego oceny będą potrzebne dwa wywołania funkcji wirtualnych. Nie idealnie, ale też nie strasznie.
Dodajmy ciągi do tego miksu i zobaczmy, dokąd nas to zaprowadzi:
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>; Ponieważ chcemy, aby liczby były konwertowane na ciągi, musimy odziedziczyć number_expression od 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>; Przeżyliśmy to, ale musimy ponownie przesłonić wirtualną metodę evaluate , w przeciwnym razie napotkamy poważne problemy z wydajnością z powodu niepotrzebnej konwersji z liczby na ciąg.
Rzeczy ewidentnie stają się więc brzydkie, a nasz projekt ledwo je przetrwa, ponieważ nie mamy dwóch typów wyrażeń, które należy przekonwertować jeden na drugi (w obie strony). Gdyby tak było, lub gdybyśmy próbowali przeprowadzić jakąkolwiek konwersję kołową, nasza hierarchia nie mogła sobie z tym poradzić. W końcu hierarchia powinna odzwierciedlać relację typu is-relation, a nie is-convertible-to, która jest słabsza.
Wszystkie te nieudane próby doprowadziły mnie do skomplikowanego, ale – moim zdaniem – właściwego projektu. Po pierwsze, posiadanie jednej klasy bazowej nie jest dla nas kluczowe. Potrzebujemy klasy wyrażeń, której wynikiem będzie void, ale jeśli możemy odróżnić wyrażenia void od wyrażeń innego rodzaju w czasie kompilacji, nie ma potrzeby konwertowania między nimi w czasie wykonywania. Dlatego parametryzujemy klasę bazową typem zwracanym wyrażenia.
Oto pełna implementacja tej klasy:
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; };Będziemy mieli tylko jedno wywołanie funkcji wirtualnej na obliczenie wyrażenia (oczywiście będziemy musieli wywoływać to rekurencyjnie), a ponieważ nie kompilujemy do kodu binarnego, jest to całkiem dobry wynik. Jedyne, co pozostało do zrobienia, to konwersja między typami, jeśli jest to dozwolone.
Aby to osiągnąć, sparametryzujemy każde wyrażenie typem zwracanym i odziedziczymy go z odpowiedniej klasy bazowej. Następnie w funkcji evaluate przekonwertujemy wynik oceny na wartość zwracaną przez tę funkcję.
Na przykład to jest nasze wyrażenie dodawania:
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) ); } ... };Aby napisać funkcję „convert”, potrzebujemy pewnej infrastruktury:
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); } Struktura is_boxed jest cechą typu, która ma wewnętrzną stałą value , która ma wartość true, jeśli (i tylko jeśli) pierwszy parametr jest wspólnym wskaźnikiem do variable_impl sparametryzowanej drugim typem.
Implementacja funkcji convert byłaby możliwa nawet w starszych wersjach C++, ale w C++17 jest bardzo przydatna instrukcja o nazwie if constexpr , która ocenia warunek w czasie kompilacji. Jeśli zwróci wartość false , całkowicie porzuci blok, nawet jeśli spowoduje błąd w czasie kompilacji. W przeciwnym razie porzuci blok 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); } }Spróbuj przeczytać tę funkcję:
- Konwertuj, jeśli można go konwertować w C++ (jest to dla rzutowania wskaźnika
variable_impl). - Rozpakuj, jeśli jest zapakowany.
- Konwertuj na ciąg, jeśli typem docelowym jest ciąg.
- Nie rób nic i sprawdź, czy cel jest pusty.
Moim zdaniem jest to o wiele bardziej czytelne niż starsza składnia oparta na SFINAE.
Przedstawię krótki przegląd typów wyrażeń i pominę niektóre szczegóły techniczne, aby zachować rozsądną zwięzłość.
W drzewie wyrażeń istnieją trzy typy wyrażeń typu liść:
- Globalne wyrażenie zmiennej
- Lokalne wyrażenie zmiennej
- Wyrażenie stałe
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>() ); } };Oprócz typu zwracanego jest również sparametryzowany typem zmiennej. Podobnie traktowane są zmienne lokalne, a oto klasa dla stałych:
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); } };W takim przypadku konwertujemy stałą natychmiast w konstruktorze.
Jest używana jako klasa bazowa dla większości naszych wyrażeń:
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 ); } };Pierwszym argumentem jest typ funktora, który zostanie utworzony i wywołany do oceny. Pozostałe typy to zwracane typy wyrażeń podrzędnych.
W celu zredukowania kodu wzorcowego definiujemy trzy makra:
#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>; Zauważ, że operator() jest zdefiniowany jako szablon, chociaż zwykle nie musi tak być. Łatwiej jest zdefiniować wszystkie wyrażenia w ten sam sposób, zamiast podawać typy argumentów jako argumenty makr.
Teraz możemy zdefiniować większość wyrażeń. Na przykład jest to definicja /= :
BINARY_EXPRESSION(div_assign, t1->value /= t2; return t1; ); Za pomocą tych makr możemy zdefiniować prawie wszystkie wyrażenia. Wyjątkiem są operatory, które mają zdefiniowaną kolejność oceny argumentów (logiczny && i || , trójargumentowy ( ? ) i przecinek ( , ) ), indeks tablicy, wywołanie funkcji i param_expression , który klonuje parametr w celu przekazania go do funkcji według wartości.
W ich realizacji nie ma nic skomplikowanego. Implementacja wywołania funkcji jest najbardziej złożona, więc wyjaśnię to tutaj:
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>() ); } } }; Przygotowuje runtime_context , wkładając wszystkie ocenione argumenty na swój stos i wywołując funkcję call . Następnie wywołuje oceniany pierwszy argument (którym jest sama funkcja) i zwraca wartość zwracaną przez metodę end_function . Widzimy tutaj również użycie składni if constexpr . Oszczędza nam to pisania specjalizacji dla całej klasy dla funkcji zwracających void .
Teraz mamy wszystko, co związane z wyrażeniami, dostępne w czasie wykonywania. Pozostała tylko konwersja z drzewa przeanalizowanych wyrażeń (opisanego w poprzednim wpisie na blogu) do drzewa wyrażeń.
Konstruktor wyrażeń
Aby uniknąć nieporozumień, nazwijmy różne fazy naszego cyklu rozwoju języka:
- Czas meta-kompilacji: faza działania kompilatora C++
- Czas kompilacji: faza działania kompilatora Stork
- Runtime: faza uruchamiania skryptu Stork
Oto pseudokod do konstruktora wyrażeń:
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 ); } } }Oprócz konieczności obsługi wszystkich operacji, wydaje się to prostym algorytmem.
Gdyby to zadziałało, byłoby świetnie, ale tak nie jest. Na początek musimy określić typ zwracany funkcji i oczywiście nie jest to tutaj ustalone, ponieważ typ zwracany zależy od typu węzła, który odwiedzamy. Typy węzłów są znane w czasie kompilacji, ale typy zwracane powinny być znane w czasie meta-kompilacji.
W poprzednim poście wspomniałem, że nie widzę przewagi języków, które wykonują dynamiczne sprawdzanie typów. W takich językach powyższy pseudokod mógłby zostać zaimplementowany niemal dosłownie. Teraz jestem całkiem świadomy zalet języków typu dynamicznego. Natychmiastowa karma w najlepszym wydaniu.
Na szczęście znamy typ wyrażenia najwyższego poziomu - zależy to od kontekstu kompilacji, ale znamy jego typ bez parsowania drzewa wyrażeń. Na przykład, jeśli mamy pętlę for:
for (expression1; expression2; expression3) ... Pierwsze i trzecie wyrażenie mają zwracany typ void , ponieważ nie robimy nic z ich wynikiem oceny. Drugie wyrażenie ma jednak number typu, ponieważ porównujemy go do zera, aby zdecydować, czy zatrzymać pętlę, czy nie.
Jeśli znamy typ wyrażenia, które jest powiązane z operacją węzła, zwykle określa typ swojego wyrażenia podrzędnego.
Na przykład, jeśli wyrażenie (expression1) += (expression2) ma typ lnumber , oznacza to, że expression1 również ma ten typ, a expression2 ma typ number .
Jednak wyrażenie (expression1) < (expression2) zawsze ma typ number , ale ich wyrażenia podrzędne mogą mieć typ number lub typ string . W przypadku tego wyrażenia sprawdzimy, czy oba węzły są liczbami. Jeśli tak, zbudujemy expression1 i expression2 jako expression<number> . W przeciwnym razie będą typu expression<string> .
Jest jeszcze jeden problem, który musimy wziąć pod uwagę i z którym musimy sobie poradzić.
Wyobraź sobie, że musimy zbudować wyrażenie typu number . Wtedy nie możemy zwrócić niczego ważnego, jeśli natkniemy się na operator konkatenacji. Wiemy, że tak się nie stanie, ponieważ sprawdziliśmy już typy przy budowaniu drzewa wyrażeń (w poprzedniej części), ale to oznacza, że nie możemy napisać funkcji szablonu, sparametryzowanej typem zwracanym, ponieważ będzie ona miała niepoprawne gałęzie w zależności od w tym typie zwrotu.
Jedno podejście podzieliłoby funkcję według typu zwracanego, używając if constexpr , ale jest to nieefektywne, ponieważ jeśli ta sama operacja istnieje w wielu gałęziach, będziemy musieli powtórzyć jej kod. W takim przypadku moglibyśmy napisać osobne funkcje.
Zaimplementowane rozwiązanie dzieli funkcję w zależności od typu węzła. W każdej z gałęzi sprawdzimy, czy dany typ gałęzi jest konwertowalny na typ zwracany przez funkcję. Jeśli tak nie jest, wyrzucimy błąd kompilatora, bo to nigdy nie powinno się zdarzyć, ale kod jest zbyt skomplikowany na tak mocne twierdzenie. Mogłem popełnić błąd.
Do sprawdzenia wymienialności używamy następującej, oczywistej, struktury typu i cechy:
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 ) ); };Po tym podziale kod jest prawie prosty. Możemy semantycznie rzutować z oryginalnego typu wyrażenia na ten, który chcemy skompilować, i nie ma błędów w czasie meta-kompilacji.
Istnieje jednak wiele szablonowego kodu, więc w dużej mierze polegałem na makrach, aby go zredukować.
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()); } }; Funkcja build_expression jest tutaj jedyną publiczną funkcją. Wywołuje funkcję std::visit na typie węzła. Ta funkcja stosuje przekazany funktor na variant , odsprzęgając go w procesie. Więcej o tym i o overloaded funktorze można przeczytać tutaj.
Makro RETURN_EXPRESSION_OF_TYPE wywołuje funkcje prywatne do tworzenia wyrażeń i zgłasza wyjątek, jeśli konwersja nie jest możliwa:
#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();\ } Musimy zwrócić pusty wskaźnik w gałęzi else, ponieważ kompilator nie może poznać typu zwracanej funkcji w przypadku niemożliwej konwersji; w przeciwnym razie std::visit wymaga, aby wszystkie przeciążone funkcje miały ten sam typ zwracany.
Jest na przykład funkcja, która buduje wyrażenia z string jako typem zwracanym:
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(); } } Sprawdza, czy węzeł przechowuje stałe łańcuchy i buduje constant_expression , jeśli tak jest.
Następnie sprawdza, czy węzeł posiada identyfikator i w takim przypadku zwraca globalne lub lokalne wyrażenie zmiennej typu lstring. Może przechowywać identyfikator, jeśli zaimplementujemy zmienne stałe. W przeciwnym razie zakłada, że węzeł przechowuje operację węzła i próbuje wszystkich operacji, które mogą zwrócić string .
Oto implementacje makr 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\ )\ )\ ); Makro CHECK_IDENTIFIER musi skonsultować się z compiler_context aby zbudować globalne lub lokalne wyrażenie zmiennej z odpowiednim indeksem. To jedyne użycie compiler_context w tej strukturze.
Możesz zobaczyć, że CHECK_BINARY_OPERATION rekursywnie wywołuje build_expression dla węzłów podrzędnych.
Zawijanie
Na mojej stronie GitHub możesz pobrać pełny kod źródłowy, skompilować go, a następnie wpisać wyrażenia i zobaczyć wynik ocenianych zmiennych.
Wyobrażam sobie, że we wszystkich gałęziach ludzkiej twórczości jest moment, w którym autor uświadamia sobie, że ich produkt w pewnym sensie żyje. W konstrukcji języka programowania jest to moment, w którym widać, że język „oddycha”.
W następnej i ostatniej części tej serii zaimplementujemy resztę minimalnego zestawu funkcji językowych, aby zobaczyć, jak działa na żywo.