Stork, Часть 3: Реализация выражений и переменных

В части 3 нашей серии наш облегченный язык программирования наконец-то заработает. Он не будет полным по Тьюрингу, не будет мощным, но сможет вычислять выражения и даже вызывать внешние функции, написанные на C++.

Я постараюсь описать процесс как можно подробнее, главным образом потому, что это цель этой серии блогов, а также для моей собственной документации, потому что в этой части все немного усложнилось.

Я начал программировать эту часть еще до публикации второй статьи, но потом выяснилось, что парсер выражений должен быть отдельным компонентом, заслуживающим отдельного поста в блоге.

Это, наряду с некоторыми печально известными методами программирования, позволило этой части не быть чудовищно большой, и тем не менее, некоторые читатели, скорее всего, укажут на упомянутые методы программирования и зададутся вопросом, почему я должен был их использовать.

Почему мы используем макросы?

Когда я приобрел опыт программирования, работая над разными проектами и с разными людьми, я понял, что разработчики склонны к догматизму — возможно, потому, что так проще.

Первая догма программирования состоит в том, что goto плохой, злой и ужасный. Я могу понять, откуда берется это мнение, и я согласен с этим мнением в подавляющем большинстве случаев, когда кто-то использует goto . Обычно этого можно избежать, вместо этого можно написать более читаемый код.

Однако нельзя отрицать, что выход из внутреннего цикла в C++ можно легко выполнить с помощью goto . Альтернатива, требующая переменной bool или специальной функции, может быть менее читабельной, чем код, который догматически попадает в корзину запрещенных приемов программирования.

Вторая догма, относящаяся исключительно к разработчикам C и C++, состоит в том, что макросы плохи, злы, ужасны и, по сути, представляют собой катастрофу, ожидающую своего часа. Это почти всегда сопровождается этим примером:

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

И затем возникает вопрос: каково значение x после этого фрагмента кода, и ответ равен 5 , потому что x увеличивается дважды, по одному с каждой стороны ? -оператор.

Единственная проблема в том, что никто не использует макросы в этом сценарии. Макросы — зло, если они используются в сценарии, где обычные функции работают нормально, особенно если они притворяются функциями, поэтому пользователь не знает об их побочных эффектах. Однако мы не будем использовать их как функции, и мы будем использовать печатные буквы для их имен, чтобы было очевидно, что они не являются функциями. Мы не сможем их нормально отлаживать, и это плохо, но с этим мы будем жить, так как альтернатива — десятки раз копипастить один и тот же код, что гораздо более подвержено ошибкам, чем макросы. Одним из решений этой проблемы является написание генератора кода, но зачем нам его писать, если он уже встроен в C++?

Догмы в программировании почти всегда плохи. Я осторожно использую здесь слово «почти», чтобы избежать рекурсивного попадания в ловушку догмы, которую я только что расставил.

Вы можете найти код и все макросы для этой части здесь.

Переменные

В предыдущей части я упомянул, что Stork не будет компилироваться в двоичный файл или что-то похожее на язык ассемблера, но я также сказал, что это будет язык со статической типизацией. Следовательно, он будет скомпилирован, но в объект C++, который сможет выполняться. Позже станет понятнее, а пока давайте просто заявим, что все переменные будут сами по себе объектами.

Поскольку мы хотим хранить их в контейнере глобальных переменных или в стеке, одним из удобных подходов является определение базового класса и наследование от него.

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

Как видите, это довольно просто, а функция clone , выполняющая глубокое копирование, является его единственной виртуальной функцией-членом, не считая деструктора.

Поскольку мы всегда будем использовать объекты этого класса через shared_ptr , имеет смысл наследовать его от std::enable_shared_from_this , чтобы мы могли легко получить от него общий указатель. Функция static_pointer_downcast здесь для удобства, потому что нам часто придется выполнять понижающее приведение от этого класса к его реализации.

Настоящая реализация этого класса — variable_impl , параметризованная типом, который она содержит. Он будет создан для четырех типов, которые мы будем использовать:

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

Мы будем использовать double в качестве типа числа. Строки подсчитываются по ссылкам, поскольку они будут неизменяемыми, чтобы обеспечить определенные оптимизации при передаче их по значению. Массив будет std::deque , так как он стабилен, и давайте просто отметим, что runtime_context — это класс, который содержит всю необходимую информацию о памяти программы во время выполнения. Мы вернемся к этому позже.

Также часто используются следующие определения:

 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» сокращена до «lvalue». Всякий раз, когда у нас есть lvalue для какого-либо типа, мы будем использовать общий указатель на variable_impl .

Контекст выполнения

Во время выполнения состояние памяти хранится в классе 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); };

Он инициализируется количеством глобальных переменных.

• _globals хранит все глобальные переменные. Доступ к ним осуществляется с помощью global функции-члена с абсолютным индексом.
• _stack хранит локальные переменные и аргументы функций, а целое число в начале _retval_idx хранит абсолютный индекс в _stack текущего возвращаемого значения.
• Доступ к возвращаемому значению осуществляется с помощью функции retval , а доступ к локальным переменным и аргументам функции осуществляется с помощью local функции путем передачи индекса относительно текущего возвращаемого значения. Аргументы функции в этом случае имеют отрицательные индексы.
• Функция push добавляет переменную в стек, а end_scope удаляет переданное количество переменных из стека.
• Функция call изменит размер стека на единицу и поместит индекс последнего элемента в _stack в _retval_idx .
• end_function удаляет возвращаемое значение и переданное количество аргументов из стека, а также возвращает удаленное возвращаемое значение.

Как видите, мы не будем реализовывать какое-либо низкоуровневое управление памятью, а воспользуемся преимуществами собственного (C++) управления памятью, которое мы можем считать само собой разумеющимся. Мы также не будем реализовывать выделение кучи, по крайней мере, сейчас.

С runtime_context у нас, наконец, есть все строительные блоки, необходимые для центрального и самого сложного компонента этой части.

Выражения

Чтобы полностью объяснить сложное решение, которое я здесь представлю, я кратко познакомлю вас с парой неудачных попыток, которые я предпринял, прежде чем остановился на этом подходе.

Самый простой подход — оценивать каждое выражение как variable_ptr и иметь этот виртуальный базовый класс:

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

Затем мы будем наследоваться от этого класса для каждой операции, такой как сложение, конкатенация, вызов функции и т. д. Например, это будет реализация выражения сложения:

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

Поэтому нам нужно оценить обе стороны ( _expr1 и _expr2 ), добавить их, а затем построить variable_impl<number> .

Мы можем безопасно преобразовывать переменные, потому что мы проверяли их тип во время компиляции, так что здесь проблема не в этом. Однако большой проблемой является потеря производительности, которую мы платим за выделение кучи для возвращаемого объекта, что теоретически не нужно. Мы делаем это, чтобы выполнить объявление виртуальной функции. В первой версии Stork у нас будет такой штраф, когда мы возвращаем числа из функций. Я могу жить с этим, но не с простым выражением перед приращением, выполняющим выделение кучи.

Затем я попытался использовать выражения для конкретных типов, унаследованные от общей базы:

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

Это только часть иерархии (только для чисел), и мы уже столкнулись с проблемами формы ромба (класс, наследующий два класса с одним и тем же базовым классом).

К счастью, C++ предлагает виртуальное наследование, которое дает возможность наследовать от базового класса, сохраняя указатель на него в унаследованном классе. Следовательно, если классы B и C виртуально наследуются от A, а класс D наследуется от B и C, в D будет только одна копия A.

Однако в этом случае нам приходится платить за некоторые штрафы — производительность и невозможность понизить уровень из A, и это лишь некоторые из них, — но это все равно выглядело как возможность для меня впервые использовать виртуальное наследование в моя жизнь.

Теперь реализация выражения сложения будет выглядеть более естественно:

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

С точки зрения синтаксиса больше нечего просить, и это настолько естественно, насколько это возможно. Однако, если какое-либо из внутренних выражений является числовым выражением lvalue, для его оценки потребуются два вызова виртуальных функций. Не идеально, но и не ужасно.

Давайте добавим в этот микс струны и посмотрим, к чему это приведет:

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

Поскольку мы хотим, чтобы числа можно было преобразовать в строки, нам нужно наследовать number_expression от 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>;

Мы пережили это, но нам нужно переопределить виртуальный метод evaluate , иначе мы столкнемся с серьезными проблемами производительности из-за ненужного преобразования числа в строку.

Итак, вещи явно становятся уродливыми, и наш дизайн едва переживает их, потому что у нас нет двух типов выражений, которые должны быть преобразованы одно в другое (в обоих направлениях). Если бы это было так, или если бы мы попытались выполнить какое-либо циклическое преобразование, наша иерархия не смогла бы с этим справиться. В конце концов, иерархия должна отражать отношения «есть», а не отношения «есть», которые слабее.

Все эти безуспешные попытки привели меня к сложной, но, на мой взгляд, правильной конструкции. Во-первых, наличие единого базового класса для нас не критично. Нам нужен класс выражений, который оценивается как void, но если мы можем различать выражения void и выражения другого типа во время компиляции, нет необходимости преобразовывать их во время выполнения. Поэтому мы параметризуем базовый класс возвращаемым типом выражения.

Вот полная реализация этого класса:

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

У нас будет только один вызов виртуальной функции на одно вычисление выражения (конечно, нам придется вызывать ее рекурсивно), а так как мы не компилируем в бинарный код, то это вполне хороший результат. Единственное, что осталось сделать, это преобразование между типами, когда это разрешено.

Для этого мы параметризуем каждое выражение возвращаемым типом и наследуем его от соответствующего базового класса. Затем в функции evaluate мы преобразуем результат оценки в возвращаемое значение этой функции.

Например, это наше выражение сложения:

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

Чтобы написать функцию «конвертировать», нам понадобится некоторая инфраструктура:

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

Структура is_boxed — это черта типа, которая имеет внутреннюю константу value , которая принимает значение true, если (и только если) первый параметр является общим указателем на variable_impl , параметризованным вторым типом.

Реализация функции convert была бы возможна даже в более старых версиях C++, но в C++17 есть очень полезная инструкция if constexpr , которая оценивает условие во время компиляции. Если он оценивается как false , он полностью удаляет блок, даже если это вызывает ошибку времени компиляции. В противном случае блок 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); } }

Попробуйте прочитать эту функцию:

• Преобразование, если оно может быть преобразовано в C++ (это для повышения указателя variable_impl ).
• Распакуйте, если он в коробке.
• Преобразование в строку, если целевой тип — строка.
• Ничего не делайте и проверьте, является ли цель недействительной.

На мой взгляд, это гораздо более читабельно, чем старый синтаксис, основанный на SFINAE.

Я дам краткий обзор типов выражений и опущу некоторые технические детали, чтобы сделать его достаточно кратким.

В дереве выражений есть три типа листовых выражений:

• Выражение глобальной переменной
• Выражение локальной переменной
• Постоянное выражение

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

Помимо возвращаемого типа, он также параметризуется типом переменной. Аналогично обрабатываются локальные переменные, и это класс для констант:

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

В этом случае мы конвертируем константу сразу в конструкторе.

Он используется в качестве базового класса для большинства наших выражений:

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

Первый аргумент — это тип функтора, который будет создан и вызван для оценки. Остальные типы являются возвращаемыми типами дочерних выражений.

Чтобы сократить шаблонный код, мы определяем три макроса:

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

Обратите внимание, что operator() определен как шаблон, хотя обычно это не обязательно. Легче определить все выражения одинаково, чем указывать типы аргументов в качестве аргументов макроса.

Теперь мы можем определить большинство выражений. Например, это определение для /= :

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

Мы можем определить почти все выражения с помощью этих макросов. Исключениями являются операторы, которые имеют определенный порядок оценки аргументов (логические операторы && и || , тернарный ( ? ) и оператор запятой ( , )), индекс массива, вызов функции и param_expression , который клонирует параметр для передачи его в функцию. по стоимости.

Ничего сложного в реализации оных нет. Реализация вызова функции самая сложная, поэтому я объясню ее здесь:

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

Он подготавливает runtime_context , помещая все оцененные аргументы в свой стек и вызывая функцию call . Затем он вызывает оцененный первый аргумент (который является самой функцией) и возвращает возвращаемое значение метода end_function . Здесь также можно увидеть использование синтаксиса if constexpr . Это избавляет нас от написания специализации всего класса для функций, возвращающих void .

Теперь у нас есть все, что связано с выражениями, доступными во время выполнения. Осталось только преобразовать разобранное дерево выражений (описанное в предыдущей записи блога) в дерево выражений.

Построитель выражений

Чтобы избежать путаницы, давайте назовем разные фазы нашего цикла разработки языка:

• Мета-компиляция: фаза, когда запускается компилятор C++.
• Время компиляции: этап, когда запускается компилятор Stork.
• Время выполнения: этап, когда запускается скрипт Stork.

Вот псевдокод построителя выражений:

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

Помимо необходимости обрабатывать все операции, это кажется простым алгоритмом.

Если бы это работало, было бы здорово, но это не так. Для начала нам нужно указать возвращаемый тип функции, а здесь он явно не фиксирован, потому что возвращаемый тип зависит от типа узла, который мы посещаем. Типы узлов известны во время компиляции, но возвращаемые типы должны быть известны во время метакомпиляции.

В предыдущем посте я упомянул, что не вижу преимуществ в языках с динамической проверкой типов. В таких языках приведенный выше псевдокод можно было реализовать практически буквально. Теперь я хорошо осведомлен о преимуществах языков с динамическим типом. Мгновенная карма во всей красе.

К счастью, мы знаем тип выражения верхнего уровня — он зависит от контекста компиляции, но мы знаем его тип без разбора дерева выражений. Например, если у нас есть цикл for:

 for (expression1; expression2; expression3) ...

Первое и третье выражения имеют возвращаемый тип void , потому что мы ничего не делаем с результатом их вычисления. Второе выражение, однако, имеет number типа, потому что мы сравниваем его с нулем, чтобы решить, останавливать цикл или нет.

Если мы знаем тип выражения, связанного с операцией узла, оно обычно определяет тип его дочернего выражения.

Например, если выражение (expression1) += (expression2) имеет тип lnumber , это означает, что expression1 также имеет этот тип, а expression2 имеет тип number .

Однако выражение (expression1) < (expression2) всегда имеет тип number , но их дочерние выражения могут иметь тип number или тип string . В случае этого выражения мы проверим, являются ли оба узла числами. Если это так, мы создадим expression1 и expression2 как expression<number> . В противном случае они будут иметь тип expression<string> .

Есть еще одна проблема, которую мы должны принять во внимание и решить.

Представьте, если нам нужно построить выражение типа number . Затем мы не сможем вернуть ничего действительного, если столкнемся с оператором конкатенации. Мы знаем, что этого не может быть, так как мы уже проверяли типы при построении дерева выражений (в предыдущей части), но это означает, что мы не можем написать шаблонную функцию, параметризованную возвращаемым типом, потому что она будет иметь недопустимые ветки в зависимости на этом возвращаемом типе.

Один из подходов разделил бы функцию по типу возвращаемого значения, используя if constexpr , но это неэффективно, потому что если одна и та же операция существует в нескольких ветвях, нам придется повторять ее код. В этом случае мы могли бы написать отдельные функции.

Реализованное решение разделяет функцию в зависимости от типа узла. В каждой из ветвей мы проверим, можно ли преобразовать этот тип ветви в возвращаемый тип функции. Если это не так, мы выдадим ошибку компилятора, потому что этого никогда не должно произойти, но код слишком сложен для такого сильного утверждения. Я, возможно, сделал ошибку.

Мы используем следующую не требующую пояснений структуру признаков типа для проверки конвертируемости:

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

После этого разделения код становится почти простым. Мы можем семантически преобразовать исходный тип выражения в тот, который мы хотим построить, и при мета-компиляции не будет ошибок.

Однако существует много шаблонного кода, поэтому я в значительной степени полагался на макросы, чтобы сократить его.

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

Функция build_expression — единственная общедоступная функция здесь. Он вызывает функцию std::visit для типа узла. Эта функция применяет переданный функтор к variant , отделяя его в процессе. Подробнее об этом и о overloaded функторе можно прочитать здесь.

Макрос RETURN_EXPRESSION_OF_TYPE вызывает приватные функции для построения выражения и выдает исключение, если преобразование невозможно:

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

Приходится возвращать пустой указатель в else-ветви, так как компилятор не может знать тип возврата функции в случае невозможности преобразования; в противном случае std::visit требует, чтобы все перегруженные функции имели один и тот же тип возвращаемого значения.

Например, есть функция, которая строит выражения со string в ​​качестве возвращаемого типа:

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

Он проверяет, содержит ли узел строковую константу, и, если это так, строит constant_expression .

Затем он проверяет, содержит ли узел идентификатор, и в этом случае возвращает выражение глобальной или локальной переменной типа lstring. Он может содержать идентификатор, если мы реализуем постоянные переменные. В противном случае предполагается, что узел выполняет операцию узла и пытается выполнить все операции, которые могут вернуть string .

Вот реализации макросов CHECK_IDENTIFIER и 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\ )\ )\ );

Макрос CHECK_IDENTIFIER должен обратиться compiler_context , чтобы построить выражение глобальной или локальной переменной с правильным индексом. Это единственное использование compiler_context в этой структуре.

Вы можете видеть, что CHECK_BINARY_OPERATION рекурсивно вызывает build_expression для дочерних узлов.

Подведение итогов

На моей странице GitHub вы можете получить полный исходный код, скомпилировать его, а затем ввести выражения и увидеть результат оцениваемых переменных.

Я предполагаю, что во всех областях человеческого творчества наступает момент, когда автор осознает, что их произведение в каком-то смысле живое. При построении языка программирования это момент, когда вы можете увидеть, что язык «дышит».

В следующей и последней части этой серии мы реализуем остальную часть минимального набора функций языка, чтобы увидеть, как он работает вживую.