Stork, Parte 3: Implementando expressões e variáveis

Na Parte 3 de nossa série, nossa linguagem de programação leve finalmente será executada. Não será Turing-completo, não será poderoso, mas será capaz de avaliar expressões e até mesmo chamar funções externas escritas em C++.

Vou tentar descrever o processo com o máximo de detalhes possível, principalmente porque é o objetivo desta série de blogs, mas também para minha própria documentação porque, nesta parte, as coisas ficaram um pouco complicadas.

Comecei a codificar para esta parte antes da publicação do segundo artigo, mas depois descobri que o analisador de expressão deveria ser um componente autônomo que merecesse seu próprio post no blog.

Isso, juntamente com algumas técnicas de programação infames, tornou possível que esta parte não fosse monstruosamente grande e, no entanto, alguns leitores provavelmente apontarão para as referidas técnicas de programação e se perguntarão por que eu tive que usá-las.

Por que usamos macros?

À medida que ganhei experiência em programação trabalhando em projetos diferentes e com pessoas diferentes, aprendi que os desenvolvedores tendem a ser bastante dogmáticos – provavelmente porque é mais fácil assim.

O primeiro dogma da programação é que a declaração goto é ruim, má e horrível. Posso entender de onde esse sentimento se origina e concordo com essa noção na grande maioria dos casos quando alguém usa a instrução goto . Geralmente, isso pode ser evitado e, em vez disso, um código mais legível pode ser escrito.

No entanto, não se pode negar que a quebra do loop interno em C++ pode ser facilmente realizada com a instrução goto . A alternativa – que requer uma variável bool ou uma função dedicada – pode ser menos legível do que o código que cai dogmaticamente no balde das técnicas de programação proibidas.

O segundo dogma, relevante exclusivamente para desenvolvedores de C e C++, é que macros são ruins, más, terríveis e basicamente um desastre esperando para acontecer. Isso é quase sempre acompanhado por este exemplo:

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

E então há uma pergunta: Qual é o valor de x após este pedaço de código, e a resposta é 5 porque x é incrementado duas vezes, uma em cada lado do ? -operador.

O único problema é que ninguém usa macros neste cenário. As macros são más se forem usadas em um cenário em que funções comuns funcionam bem, especialmente se fingirem ser funções, de modo que o usuário não tenha conhecimento de seus efeitos colaterais. No entanto, não as usaremos como funções e usaremos letras maiúsculas em seus nomes para tornar óbvio que não são funções. Não poderemos depurá-los corretamente, e isso é ruim, mas vamos conviver com isso, já que a alternativa é copiar e colar o mesmo código dezenas de vezes, o que é muito mais propenso a erros do que macros. Uma solução para esse problema é escrever o gerador de código, mas por que devemos escrevê-lo quando já temos um embutido em C++?

Dogmas na programação são quase sempre ruins. Estou usando cautelosamente “quase” aqui apenas para evitar cair recursivamente na armadilha do dogma que acabei de montar.

Você pode encontrar o código e todas as macros para esta parte aqui.

Variáveis

Na parte anterior, mencionei que o Stork não será compilado em binário ou algo semelhante à linguagem assembly, mas também disse que será uma linguagem de tipagem estática. Portanto, ele será compilado, mas em um objeto C++ que poderá ser executado. Ficará mais claro mais tarde, mas por enquanto, vamos apenas afirmar que todas as variáveis ​​serão objetos por conta própria.

Como queremos mantê-los no contêiner da variável global ou na pilha, uma abordagem conveniente é definir a classe base e herdar dela.

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

Como você pode ver, é bastante simples, e a função clone , que faz a cópia profunda, é sua única função de membro virtual além do destruidor.

Como sempre usaremos objetos desta classe via shared_ptr , faz sentido herdá-lo de std::enable_shared_from_this , para que possamos obter facilmente o ponteiro compartilhado dele. A função static_pointer_downcast está aqui por conveniência porque frequentemente teremos que fazer downcast dessa classe para sua implementação.

A implementação real desta classe é variable_impl , parametrizada com o tipo que ela contém. Ele será instanciado para os quatro tipos que usaremos:

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

Usaremos double como nosso tipo de número. Strings são contadas por referência, pois serão imutáveis, para permitir certas otimizações ao passá-las por valor. Array será std::deque , pois é estável, e vamos apenas observar que runtime_context é a classe que contém todas as informações relevantes sobre a memória do programa durante o tempo de execução. Chegaremos a isso mais tarde.

As seguintes definições também são frequentemente usadas:

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

O “l” usado aqui é abreviado para “lvalue”. Sempre que tivermos um lvalue para algum tipo, usaremos o ponteiro compartilhado para variable_impl .

Contexto de tempo de execução

Durante o tempo de execução, o estado da memória é mantido na classe 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); };

Ele é inicializado com a contagem de variáveis ​​globais.

• _globals mantém todas as variáveis ​​globais. Eles são acessados ​​com a função membro global com o índice absoluto.
• _stack mantém variáveis ​​locais e argumentos de função, e o inteiro na parte superior de _retval_idx mantém o índice absoluto em _stack do valor de retorno atual.
• O valor de retorno é acessado com a função retval , enquanto as variáveis ​​locais e os argumentos da função são acessados ​​com a função local passando o índice relativo ao valor de retorno atual. Os argumentos da função têm índices negativos neste caso.
• A função push adiciona a variável à pilha, enquanto end_scope remove o número passado de variáveis ​​da pilha.
• A função call redimensionará a pilha em um e enviará o índice do último elemento em _stack para _retval_idx .
• end_function remove o valor de retorno e o número passado de argumentos da pilha e também retorna o valor de retorno removido.

Como você pode ver, não implementaremos nenhum gerenciamento de memória de baixo nível e aproveitaremos o gerenciamento de memória nativo (C++), que podemos tomar como garantido. Também não implementaremos nenhuma alocação de heap, pelo menos por enquanto.

Com runtime_context , finalmente temos todos os blocos de construção necessários para o componente central e mais difícil desta parte.

Expressões

Para explicar completamente a solução complicada que apresentarei aqui, apresentarei brevemente algumas tentativas fracassadas que fiz antes de optar por essa abordagem.

A abordagem mais fácil é avaliar cada expressão como variable_ptr e ter esta classe base 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>;

Nós herdaríamos dessa classe para cada operação, como adição, concatenação, chamada de função, etc. Por exemplo, esta seria a implementação da expressão de adição:

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

Portanto, precisamos avaliar os dois lados ( _expr1 e _expr2 ), adicioná-los e, em seguida, construir variable_impl<number> .

Podemos fazer downcast de variáveis ​​com segurança porque verificamos seu tipo durante o tempo de compilação, então esse não é o problema aqui. No entanto, o grande problema é a penalidade de desempenho que pagamos pela alocação de heap do objeto retornado, o que, em teoria, não é necessário. Estamos fazendo isso para satisfazer a declaração da função virtual. Na primeira versão do Stork, teremos essa penalidade quando retornarmos números de funções. Eu posso viver com isso, mas não com a simples expressão de pré-incremento fazendo alocação de heap.

Então, tentei com expressões específicas do tipo herdadas da base comum:

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

Esta é apenas a parte da hierarquia (somente para números), e já nos deparamos com problemas de formato de diamante (a classe herdando duas classes com a mesma classe base).

Felizmente, C++ oferece herança virtual, que permite herdar da classe base, mantendo o ponteiro para ela, na classe herdada. Portanto, se as classes B e C herdam virtualmente de A, e a classe D herda de B e C, haveria apenas uma cópia de A em D.

No entanto, há uma série de penalidades que temos que pagar nesse caso - desempenho e incapacidade de fazer downcast de A, para citar alguns - mas isso ainda parecia uma oportunidade para eu usar a herança virtual pela primeira vez em Minha vida.

Agora, a implementação da expressão de adição parecerá mais 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); } ... };

Em termos de sintaxe, não há mais nada a pedir, e isso é o mais natural possível. No entanto, se qualquer uma das expressões internas for uma expressão de número lvalue, serão necessárias duas chamadas de função virtual para avaliá-la. Não é perfeito, mas também não é terrível.

Vamos adicionar strings a essa mistura e ver onde isso nos leva:

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

Como queremos que os números sejam conversíveis em strings, precisamos herdar number_expression de 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>;

Sobrevivemos a isso, mas temos que substituir o método virtual de evaluate ou enfrentaremos sérios problemas de desempenho devido à conversão desnecessária de número para string.

Então, as coisas estão evidentemente ficando feias, e nosso design mal está sobrevivendo a elas porque não temos dois tipos de expressões que devem ser convertidas uma para a outra (nos dois sentidos). Se fosse esse o caso, ou se tentássemos fazer algum tipo de conversão circular, nossa hierarquia não daria conta. Afinal, a hierarquia deve refletir o relacionamento é-um, não o relacionamento é conversível em, que é mais fraco.

Todas essas tentativas malsucedidas me levaram a um design complicado, mas - na minha opinião - adequado. Primeiro, ter uma única classe base não é crucial para nós. Precisamos da classe de expressão que seria avaliada como void, mas se pudermos distinguir entre expressões void e expressões de outro tipo em tempo de compilação, não há necessidade de converter entre elas em tempo de execução. Portanto, vamos parametrizar a classe base com o tipo de retorno da expressão.

Aqui está a implementação completa dessa classe:

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

Teremos apenas uma chamada de função virtual por avaliação de expressão (claro, teremos que chamá-la recursivamente), e como não compilamos para código binário, é um resultado bastante bom. A única coisa que resta a fazer é a conversão entre tipos, quando for permitido.

Para isso, vamos parametrizar cada expressão com o tipo de retorno e herdá-la da classe base correspondente. Então, na função de evaluate , converteremos o resultado da avaliação no valor de retorno dessa função.

Por exemplo, esta é a nossa expressão de adição:

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

Para escrever a função “convert”, precisamos de alguma infraestrutura:

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

A estrutura is_boxed é uma característica de tipo que possui uma constante interna, value , que é avaliada como true se (e somente se) o primeiro parâmetro for um ponteiro compartilhado para variable_impl parametrizado com o segundo tipo.

A implementação da função convert seria possível mesmo em versões mais antigas de C++, mas existe uma instrução muito útil em C++17 chamada if constexpr , que avalia a condição em tempo de compilação. Se for avaliado como false , ele descartará o bloco completamente, mesmo que cause o erro de tempo de compilação. Caso contrário, ele descartará o bloco 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); } }

Tente ler esta função:

• Converta se for conversível em C++ (isto é para upcast do ponteiro variable_impl ).
• Desembale se estiver em caixa.
• Converta em string se o tipo de destino for string.
• Não faça nada e verifique se o alvo está nulo.

Na minha opinião, isso é muito mais legível do que a sintaxe mais antiga baseada no SFINAE.

Fornecerei uma breve visão geral dos tipos de expressão e omitirei alguns detalhes técnicos para mantê-lo razoavelmente breve.

Existem três tipos de expressões de folha em uma árvore de expressão:

• Expressão de variável global
• Expressão de variável local
• Expressão constante

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

Além do tipo de retorno, também é parametrizado com o tipo de variável. Variáveis ​​locais são tratadas de forma semelhante, e esta é a classe para constantes:

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

Nesse caso, convertemos a constante imediatamente no construtor.

Isso é usado como a classe base para a maioria de nossas expressões:

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

O primeiro argumento é o tipo de functor que será instanciado e chamado para a avaliação. O restante dos tipos são tipos de retorno de expressões filhas.

Para reduzir o código clichê, definimos três macros:

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

Observe que operator() é definido como um modelo, embora geralmente não precise ser. É mais fácil definir todas as expressões da mesma maneira em vez de fornecer tipos de argumentos como argumentos de macro.

Agora, podemos definir a maioria das expressões. Por exemplo, esta é a definição para /= :

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

Podemos definir quase todas as expressões usando essas macros. As exceções são os operadores que possuem ordem definida de avaliação dos argumentos (operador lógico && e || , ternário ( ? ) e vírgula ( , )), índice de array, chamada de função e param_expression , que clona o parâmetro para passá-lo para a função por valor.

Não há nada complicado na implementação destes. A implementação de chamada de função é a mais complexa, então vou explicar aqui:

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

Ele prepara o runtime_context todos os argumentos avaliados em sua pilha e chamando a função de call . Ele então chama o primeiro argumento avaliado (que é a própria função) e retorna o valor de retorno do método end_function . Podemos ver o uso da sintaxe if constexpr aqui também. Isso nos poupa de escrever a especialização para toda a classe para funções que retornam void .

Agora, temos tudo relacionado a expressões disponíveis durante o tempo de execução. A única coisa que resta é a conversão da árvore de expressão analisada (descrita na postagem anterior do blog) para a árvore de expressões.

Construtor de Expressões

Para evitar confusão, vamos nomear diferentes fases do nosso ciclo de desenvolvimento da linguagem:

• Tempo de meta-compilação: a fase em que o compilador C++ é executado
• Tempo de compilação: a fase em que o compilador Stork é executado
• Tempo de execução: a fase em que o script Stork é executado

Aqui está o pseudocódigo para o construtor de expressões:

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

Além de ter que lidar com todas as operações, isso parece um algoritmo simples.

Se funcionasse, seria ótimo, mas não funciona. Para começar, precisamos especificar o tipo de retorno da função, e obviamente não é fixo aqui, porque o tipo de retorno depende do tipo de nó que estamos visitando. Os tipos de nó são conhecidos em tempo de compilação, mas os tipos de retorno devem ser conhecidos em tempo de metacompilação.

No post anterior, mencionei que não vejo vantagem em linguagens que fazem verificação dinâmica de tipos. Em tais linguagens, o pseudocódigo mostrado acima pode ser implementado quase literalmente. Agora, estou bem ciente das vantagens das linguagens de tipo dinâmico. Karma instantâneo no seu melhor.

Felizmente, sabemos o tipo da expressão de nível superior - depende do contexto da compilação, mas sabemos seu tipo sem analisar a árvore de expressão. Por exemplo, se tivermos o loop for:

 for (expression1; expression2; expression3) ...

A primeira e a terceira expressões têm um tipo de retorno void porque não fazemos nada com o resultado da avaliação. A segunda expressão, no entanto, tem um number de tipo porque estamos comparando-a com zero, para decidir se devemos ou não parar o loop.

Se soubermos o tipo da expressão relacionada à operação do nó, ela geralmente determinará o tipo de sua expressão filha.

Por exemplo, se a expressão (expression1) += (expression2) tiver o tipo lnumber , isso significa que expression1 também tem esse tipo e expression2 tem o tipo number .

No entanto, a expressão (expression1) < (expression2) sempre tem o tipo number , mas suas expressões filhas podem ter type number ou type string . No caso desta expressão, verificaremos se ambos os nós são números. Nesse caso, construiremos expression1 e expression2 como expression<number> . Caso contrário, eles serão do tipo expression<string> .

Há outro problema que temos que levar em conta e lidar.

Imagine se precisarmos construir uma expressão do tipo number . Então, não podemos retornar nada válido se encontrarmos um operador de concatenação. Sabemos que isso não pode acontecer, pois já verificamos os tipos quando construímos a árvore de expressão (na parte anterior), mas isso significa que não podemos escrever a função template, parametrizada com o tipo de retorno, pois ela terá ramos inválidos dependendo nesse tipo de retorno.

Uma abordagem seria dividir a função por tipo de retorno, usando if constexpr , mas é ineficiente porque se a mesma operação existir em várias ramificações, teremos que repetir seu código. Poderíamos escrever funções separadas nesse caso.

A solução implementada divide a função com base no tipo de nó. Em cada uma das ramificações, verificaremos se esse tipo de ramificação é conversível para o tipo de retorno da função. Se não for, lançaremos o erro do compilador, porque isso nunca deveria acontecer, mas o código é muito complicado para uma declaração tão forte. Posso ter cometido um erro.

Estamos usando a seguinte estrutura autoexplicativa de características de tipo para verificar a conversibilidade:

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

Após essa divisão, o código é quase direto. Podemos converter semanticamente do tipo de expressão original para aquele que queremos construir e não há erros em tempo de meta-compilação.

No entanto, há muito código clichê, então confiei muito em macros para reduzi-lo.

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

A função build_expression é a única função pública aqui. Ele invoca a função std::visit no tipo de nó. Essa função aplica o functor passado na variant , desacoplando-o no processo. Você pode ler mais sobre isso e sobre o functor overloaded aqui.

A macro RETURN_EXPRESSION_OF_TYPE chama funções privadas para construção de expressão e lança uma exceção se a conversão não for possível:

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

Temos que retornar o ponteiro vazio na ramificação else, pois o compilador não pode saber o tipo de retorno da função em caso de conversão impossível; caso contrário, std::visit requer que todas as funções sobrecarregadas tenham o mesmo tipo de retorno.

Existe, por exemplo, a função que constrói expressões com string como tipo de retorno:

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

Ele verifica se o nó mantém a string constante e cria constant_expression se for o caso.

Em seguida, ele verifica se o nó contém um identificador e retorna uma expressão de variável global ou local do tipo lstring nesse caso. Ele pode conter um identificador se implementarmos variáveis ​​constantes. Caso contrário, ele assume que o nó mantém a operação do nó e tenta todas as operações que podem retornar string .

Aqui estão as implementações das macros CHECK_IDENTIFIER e 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\ )\ )\ );

A macro CHECK_IDENTIFIER deve consultar compiler_context para construir uma expressão de variável global ou local com o índice apropriado. Esse é o único uso do compiler_context nesta estrutura.

Você pode ver que CHECK_BINARY_OPERATION chama recursivamente build_expression para os nós filho.

Empacotando

Na minha página do GitHub, você pode obter o código-fonte completo, compilá-lo e, em seguida, digitar expressões e ver o resultado das variáveis ​​avaliadas.

Imagino que, em todos os ramos da criatividade humana, haja um momento em que o autor perceba que seu produto está vivo, em algum sentido. Na construção de uma linguagem de programação, é o momento em que se vê que a linguagem “respira”.

Na próxima e última parte desta série, implementaremos o restante do conjunto mínimo de recursos de linguagem para vê-lo funcionando ao vivo.