Cicogna, Parte 3: Implementazione di espressioni e variabili

Nella parte 3 della nostra serie, finalmente verrà eseguito il nostro linguaggio di programmazione leggero. Non sarà completo di Turing, non sarà potente, ma sarà in grado di valutare espressioni e persino chiamare funzioni esterne scritte in C++.

Cercherò di descrivere il processo nel modo più dettagliato possibile, principalmente perché è lo scopo di questa serie di blog, ma anche per la mia documentazione perché, in questa parte, le cose si sono un po' complicate.

Ho iniziato a programmare per questa parte prima della pubblicazione del secondo articolo, ma poi si è scoperto che il parser di espressioni dovrebbe essere un componente autonomo che merita il proprio post sul blog.

Ciò, insieme ad alcune famigerate tecniche di programmazione, ha reso possibile che questa parte non fosse mostruosamente grande, eppure, molto probabilmente alcuni lettori indicheranno le suddette tecniche di programmazione e si chiederanno perché ho dovuto usarle.

Perché utilizziamo le macro?

Quando ho acquisito esperienza di programmazione lavorando su progetti diversi e con persone diverse, ho imparato che gli sviluppatori tendono a essere piuttosto dogmatici, probabilmente perché è più facile in questo modo.

Il primo dogma della programmazione è che l'istruzione goto è cattiva, malvagia e orribile. Posso capire da dove ha origine quel sentimento e sono d'accordo con questa nozione nella stragrande maggioranza dei casi in cui qualcuno usa l'istruzione goto . Di solito può essere evitato e invece è possibile scrivere codice più leggibile.

Tuttavia, non si può negare che l'interruzione del ciclo interno in C++ può essere facilmente ottenuta con l'istruzione goto . L'alternativa, che richiede una variabile bool o una funzione dedicata, potrebbe essere meno leggibile del codice che cade dogmaticamente nel secchio delle tecniche di programmazione proibite.

Il secondo dogma, rilevante esclusivamente per gli sviluppatori C e C++, è che le macro sono cattive, malvagie, terribili e, fondamentalmente, un disastro in attesa di accadere. Questo è quasi sempre accompagnato da questo esempio:

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

E poi c'è una domanda: qual è il valore di x dopo questo pezzo di codice, e la risposta è 5 perché x viene incrementato due volte, uno su ciascun lato del ? -operatore.

L'unico problema è che nessuno utilizza le macro in questo scenario. Le macro sono malvagie se vengono utilizzate in uno scenario in cui le funzioni ordinarie funzionano bene, specialmente se fingono di essere funzioni, quindi l'utente non è a conoscenza dei loro effetti collaterali. Tuttavia, non le useremo come funzioni e useremo lettere in stampatello per i loro nomi per rendere ovvio che non sono funzioni. Non saremo in grado di eseguirne il debug correttamente, e questo è un male, ma conviveremo con quello, poiché l'alternativa è copiare e incollare lo stesso codice dozzine di volte, il che è molto più soggetto a errori rispetto alle macro. Una soluzione a questo problema è scrivere il generatore di codice, ma perché dovremmo scriverlo quando ne abbiamo già uno incorporato in C++?

I dogmi nella programmazione sono quasi sempre cattivi. Sto usando con cautela "quasi" qui solo per evitare di cadere ricorsivamente nella trappola del dogma che ho appena preparato.

Puoi trovare il codice e tutte le macro per questa parte qui.

Variabili

Nella parte precedente, ho menzionato che Stork non verrà compilato in binario o qualcosa di simile al linguaggio assembly, ma ho anche detto che sarà un linguaggio tipizzato staticamente. Pertanto, verrà compilato, ma in un oggetto C++ che sarà in grado di essere eseguito. Diventerà più chiaro in seguito, ma per ora affermiamo semplicemente che tutte le variabili saranno oggetti a sé stanti.

Dal momento che vogliamo mantenerli nel contenitore delle variabili globali o nello stack, un approccio conveniente consiste nel definire la classe base ed ereditare da essa.

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

Come puoi vedere, è abbastanza semplice e la funzione clone , che esegue la copia profonda, è la sua unica funzione membro virtuale a parte il distruttore.

Poiché useremo sempre oggetti di questa classe tramite shared_ptr , ha senso ereditarlo da std::enable_shared_from_this , in modo da poter ottenere facilmente il puntatore condiviso da esso. La funzione static_pointer_downcast è qui per comodità perché dovremo spesso eseguire il downcast da questa classe alla sua implementazione.

La vera implementazione di questa classe è variable_impl , parametrizzata con il tipo che detiene. Verrà istanziata per i quattro tipi che utilizzeremo:

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

Useremo il double come tipo di numero. Le stringhe vengono conteggiate per riferimento, poiché saranno immutabili, per abilitare determinate ottimizzazioni quando le passano per valore. L'array sarà std::deque , poiché è stabile, e notiamo solo che runtime_context è la classe che contiene tutte le informazioni rilevanti sulla memoria del programma durante il runtime. Ci arriveremo più tardi.

Vengono spesso utilizzate anche le seguenti definizioni:

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

La "l" usata qui è abbreviata per "lvalue". Ogni volta che abbiamo un lvalue per un tipo, useremo il puntatore condiviso a variable_impl .

Contesto di runtime

Durante il runtime, lo stato della memoria viene mantenuto nella 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); };

Viene inizializzato con il conteggio delle variabili globali.

• _globals mantiene tutte le variabili globali. Vi si accede con la funzione membro global con l'indice assoluto.
• _stack mantiene le variabili locali e gli argomenti delle funzioni e il numero intero all'inizio di _retval_idx mantiene l'indice assoluto in _stack del valore restituito corrente.
• Si accede al valore di ritorno con la funzione retval , mentre le variabili locali e gli argomenti di funzione sono accessibili con la funzione local passando l'indice relativo al valore di ritorno corrente. Gli argomenti di funzione hanno indici negativi in ​​questo caso.
• La funzione push aggiunge la variabile allo stack, mentre end_scope rimuove il numero passato di variabili dallo stack.
• La funzione di call ridimensionerà lo stack di uno e spingerà l'indice dell'ultimo elemento in _stack su _retval_idx .
• end_function rimuove il valore restituito e il numero passato di argomenti dallo stack e restituisce anche il valore restituito rimosso.

Come puoi vedere, non implementeremo alcuna gestione della memoria di basso livello e sfrutteremo la gestione della memoria nativa (C++), che possiamo dare per scontata. Non implementeremo nemmeno allocazioni di heap, almeno per ora.

Con runtime_context , abbiamo finalmente tutti i blocchi di costruzione necessari per il componente centrale e più difficile di questa parte.

Espressioni

Per spiegare completamente la complicata soluzione che presenterò qui, ti presenterò brevemente un paio di tentativi falliti che ho fatto prima di stabilirmi su questo approccio.

L'approccio più semplice è valutare ogni espressione come variable_ptr e avere questa classe base virtuale:

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

Quindi erediteremo da questa classe per ogni operazione, come addizione, concatenazione, chiamata di funzione, ecc. Ad esempio, questa sarebbe l'implementazione dell'espressione di addizione:

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

Quindi dobbiamo valutare entrambi i lati ( _expr1 e _expr2 ), aggiungerli e quindi costruire variable_impl<number> .

Possiamo tranquillamente eseguire il downcast delle variabili perché abbiamo verificato il loro tipo durante la compilazione, quindi non è questo il problema qui. Tuttavia, il grosso problema è la penalizzazione delle prestazioni che paghiamo per l'allocazione dell'heap dell'oggetto restituito, che, in teoria, non è necessario. Lo stiamo facendo per soddisfare la dichiarazione della funzione virtuale. Nella prima versione di Stork, avremo quella penalità quando restituiamo numeri dalle funzioni. Posso conviverci ma non con la semplice espressione di pre-incremento che esegue l'allocazione dell'heap.

Quindi, ho provato con espressioni specifiche del tipo ereditate dalla base comune:

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

Questa è solo la parte della gerarchia (solo per i numeri) e abbiamo già riscontrato problemi di forma a diamante (la classe che eredita due classi con la stessa classe base).

Fortunatamente, C++ offre l'ereditarietà virtuale, che dà la possibilità di ereditare dalla classe base, mantenendo il puntatore ad essa, nella classe ereditata. Pertanto, se le classi B e C ereditano virtualmente da A e la classe D eredita da B e C, ci sarebbe solo una copia di A in D.

Ci sono un certo numero di penalità che dobbiamo pagare in quel caso, tuttavia, prestazioni e incapacità di abbattere da A, solo per citarne alcune, ma questa sembrava comunque un'opportunità per me di usare l'eredità virtuale per la prima volta in la mia vita.

Ora, l'implementazione dell'espressione di addizione apparirà più naturale:

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

Per quanto riguarda la sintassi, non c'è più niente da chiedere, e questo è naturale. Tuttavia, se una qualsiasi delle espressioni interne è un'espressione numerica lvalue, saranno necessarie due chiamate di funzioni virtuali per valutarla. Non perfetto, ma nemmeno terribile.

Aggiungiamo stringhe in questo mix e vediamo dove ci arriva:

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

Poiché vogliamo che i numeri siano convertibili in stringhe, dobbiamo ereditare number_expression da 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>;

Siamo sopravvissuti a questo, ma dobbiamo sovrascrivere nuovamente il metodo virtuale di evaluate , o dovremo affrontare seri problemi di prestazioni a causa della conversione non necessaria da numero a stringa.

Quindi, le cose stanno evidentemente peggiorando e il nostro design sta a malapena sopravvivendo loro perché non abbiamo due tipi di espressioni che dovrebbero essere convertiti l'uno nell'altro (in entrambi i modi). Se fosse così, o se cercassimo di avere un qualsiasi tipo di conversione circolare, la nostra gerarchia non sarebbe in grado di gestirlo. Dopotutto, la gerarchia dovrebbe riflettere una relazione è, non è convertibile in relazione, che è più debole.

Tutti questi tentativi infruttuosi mi hanno portato a un design complicato ma - a mio avviso - corretto. Primo, avere un'unica classe base non è cruciale per noi. Abbiamo bisogno della classe expression che valuterebbe void, ma se possiamo distinguere tra espressioni void ed espressioni di altro tipo in fase di compilazione, non è necessario convertire tra loro in un runtime. Pertanto, parametrizzeremo la classe base con il tipo restituito dell'espressione.

Ecco l'implementazione completa di quella 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; };

Avremo solo una chiamata di funzione virtuale per valutazione dell'espressione (ovviamente, dovremo chiamarla in modo ricorsivo) e poiché non compiliamo in codice binario, è un buon risultato. L'unica cosa rimasta da fare è la conversione tra i tipi, quando è consentita.

Per fare ciò, parametrizzeremo ogni espressione con il tipo restituito e la erediteremo dalla classe base corrispondente. Quindi, nella funzione di evaluate , convertiremo il risultato della valutazione nel valore restituito di quella funzione.

Ad esempio, questa è la nostra espressione di addizione:

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

Per scrivere la funzione "converti", abbiamo bisogno di alcune infrastrutture:

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

La struttura is_boxed è un tratto di tipo che ha una costante interna, value , che restituisce true se (e solo se) il primo parametro è un puntatore condiviso a variable_impl parametrizzato con il secondo tipo.

L'implementazione della funzione convert sarebbe possibile anche nelle versioni precedenti di C++, ma c'è un'istruzione molto utile in C++17 chiamata if constexpr , che valuta la condizione in fase di compilazione. Se restituisce false , eliminerà del tutto il blocco, anche se causa l'errore in fase di compilazione. Altrimenti, rilascerà il blocco 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); } }

Prova a leggere questa funzione:

• Converti se è convertibile in C++ (questo è per il puntatore variable_impl upcast).
• Unbox se è inscatolato.
• Converti in stringa se il tipo di destinazione è stringa.
• Non fare nulla e controlla se il bersaglio è vuoto.

A mio parere, questo è molto più leggibile rispetto alla vecchia sintassi basata su SFINAE.

Fornirò una breve panoramica dei tipi di espressione e ometterò alcuni dettagli tecnici per mantenerla ragionevolmente breve.

Esistono tre tipi di espressioni foglia in un albero delle espressioni:

• Espressione di variabile globale
• Espressione di variabile locale
• Espressione costante

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

Oltre al tipo restituito, viene parametrizzato anche con il tipo di variabile. Le variabili locali sono trattate in modo simile e questa è la classe per le costanti:

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

In questo caso, convertiamo la costante immediatamente nel costruttore.

Questa è usata come classe base per la maggior parte delle nostre espressioni:

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

Il primo argomento è il tipo di funtore che verrà istanziato e chiamato per la valutazione. Il resto dei tipi sono tipi restituiti di espressioni figlio.

Per ridurre il codice standard, definiamo tre macro:

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

Si noti che operator() è definito come un modello, sebbene di solito non debba esserlo. È più facile definire tutte le espressioni allo stesso modo invece di fornire i tipi di argomento come argomenti di macro.

Ora possiamo definire la maggior parte delle espressioni. Ad esempio, questa è la definizione di /= :

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

Possiamo definire quasi tutte le espressioni usando queste macro. Le eccezioni sono gli operatori che hanno definito l'ordine di valutazione degli argomenti (operatore logico && e || , ternario ( ? ) e virgola ( , )), indice di matrice, chiamata di funzione e param_expression , che clona il parametro per passarlo alla funzione per valore.

Non c'è nulla di complicato nell'attuazione di questi. L'implementazione della chiamata di funzione è la più complessa, quindi la spiegherò qui:

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

Prepara il runtime_context tutti gli argomenti valutati nel suo stack e chiamando la funzione di call . Quindi chiama il primo argomento valutato (che è la funzione stessa) e restituisce il valore di ritorno del metodo end_function . Possiamo vedere l'uso della sintassi if constexpr anche qui. Ci evita di scrivere la specializzazione per l'intera classe per le funzioni che restituiscono void .

Ora abbiamo tutto ciò che riguarda le espressioni disponibili durante il runtime. L'unica cosa rimasta è la conversione dall'albero delle espressioni analizzato (descritto nel post precedente del blog) all'albero delle espressioni.

Costruttore di espressioni

Per evitare confusione, diamo un nome alle diverse fasi del nostro ciclo di sviluppo del linguaggio:

• Meta-compilazione: la fase in cui viene eseguito il compilatore C++
• Tempo di compilazione: la fase in cui viene eseguito il compilatore Stork
• Runtime: la fase in cui viene eseguito lo script Stork

Ecco lo pseudo-codice per il generatore di espressioni:

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

Oltre a dover gestire tutte le operazioni, questo sembra un algoritmo semplice.

Se funzionasse, sarebbe fantastico, ma non è così. Per cominciare, dobbiamo specificare il tipo di ritorno della funzione, e ovviamente non è corretto qui, perché il tipo di ritorno dipende dal tipo di nodo che stiamo visitando. I tipi di nodo sono noti in fase di compilazione, ma i tipi restituiti dovrebbero essere noti in fase di meta-compilazione.

Nel post precedente, ho detto che non vedo il vantaggio dei linguaggi che eseguono il controllo dinamico del tipo. In tali linguaggi, lo pseudocodice mostrato sopra potrebbe essere implementato quasi letteralmente. Ora, sono abbastanza consapevole dei vantaggi dei linguaggi di tipo dinamico. Karma istantaneo al suo meglio.

Fortunatamente, conosciamo il tipo dell'espressione di primo livello: dipende dal contesto della compilazione, ma ne conosciamo il tipo senza analizzare l'albero delle espressioni. Ad esempio, se abbiamo il ciclo for:

 for (expression1; expression2; expression3) ...

La prima e la terza espressione hanno un tipo restituito void perché non facciamo nulla con il loro risultato di valutazione. La seconda espressione, invece, ha un number di tipo perché lo stiamo confrontando con zero, per decidere se interrompere o meno il ciclo.

Se conosciamo il tipo dell'espressione correlata all'operazione del nodo, di solito determinerà il tipo della sua espressione figlia.

Ad esempio, se l'espressione (expression1) += (expression2) ha il tipo lnumber , significa che anche expression1 ha quel tipo e expression2 ha il tipo number .

Tuttavia, l'espressione (expression1) < (expression2) ha sempre il tipo number , ma le loro espressioni figlio possono avere tipo number o tipo string . In caso di questa espressione, verificheremo se entrambi i nodi sono numeri. In tal caso, costruiremo expression1 ed expression2 come expression<number> . In caso contrario, saranno del tipo expression<string> .

C'è un altro problema che dobbiamo prendere in considerazione e affrontare.

Immagina se abbiamo bisogno di costruire un'espressione del tipo number . Quindi, non possiamo restituire nulla di valido se ci imbattiamo in un operatore di concatenazione. Sappiamo che non può succedere, poiché abbiamo già verificato i tipi quando abbiamo costruito l'albero delle espressioni (nella parte precedente), ma ciò significa che non possiamo scrivere la funzione template, parametrizzata con il tipo restituito, perché avrà rami non validi a seconda su quel tipo di ritorno.

Un approccio dividerebbe la funzione per tipo restituito, usando if constexpr , ma è inefficiente perché se la stessa operazione esiste in più rami, dovremo ripetere il suo codice. In questo caso potremmo scrivere funzioni separate.

La soluzione implementata suddivide la funzione in base al tipo di nodo. In ciascuno dei rami, verificheremo se quel tipo di ramo è convertibile nel tipo restituito dalla funzione. In caso contrario, genereremo l'errore del compilatore, perché non dovrebbe mai accadere, ma il codice è troppo complicato per un'affermazione così forte. Potrei aver commesso un errore.

Utilizziamo la seguente struttura autoesplicativa del tratto tipo per verificare la convertibilità:

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

Dopo quella divisione, il codice è quasi semplice. Possiamo lanciare semanticamente dal tipo di espressione originale a quello che vogliamo costruire e non ci sono errori nel meta-compilazione.

C'è molto codice standard, tuttavia, quindi ho fatto molto affidamento sulle macro per ridurlo.

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

La funzione build_expression è l'unica funzione pubblica qui. Richiama la funzione std::visit sul tipo di nodo. Quella funzione applica il funtore passato sulla variant , disaccoppiandolo nel processo. Puoi leggere di più a riguardo e sul funtore overloaded qui.

La macro RETURN_EXPRESSION_OF_TYPE chiama funzioni private per la creazione di espressioni e genera un'eccezione se la conversione non è possibile:

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

Dobbiamo restituire il puntatore vuoto nel ramo else, poiché il compilatore non può conoscere il tipo restituito dalla funzione in caso di conversione impossibile; in caso contrario, std::visit richiede che tutte le funzioni sovraccaricate abbiano lo stesso tipo restituito.

C'è, ad esempio, la funzione che costruisce espressioni con string come tipo restituito:

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

Verifica se il nodo mantiene la stringa costante e crea constant_expression se questo è il caso.

Quindi, controlla se il nodo contiene un identificatore e restituisce un'espressione di variabile globale o locale di tipo lstring in quel caso. Può contenere un identificatore se implementiamo variabili costanti. In caso contrario, presuppone che il nodo contenga l'operazione del nodo e prova tutte le operazioni che possono restituire string .

Ecco le implementazioni delle macro 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\ )\ )\ );

La macro CHECK_IDENTIFIER deve consultare compiler_context per creare un'espressione di variabile globale o locale con l'indice corretto. Questo è l'unico utilizzo di compiler_context in questa struttura.

Puoi vedere che CHECK_BINARY_OPERATION chiama ricorsivamente build_expression per i nodi figlio.

Avvolgendo

Nella mia pagina GitHub, puoi ottenere il codice sorgente completo, compilarlo, quindi digitare espressioni e vedere il risultato delle variabili valutate.

Immagino che, in tutti i rami della creatività umana, ci sia un momento in cui l'autore si rende conto che il loro prodotto è vivo, in un certo senso. Nella costruzione di un linguaggio di programmazione, è il momento in cui puoi vedere che il linguaggio “respira”.

Nella parte successiva e finale di questa serie, implementeremo il resto del set minimo di funzionalità del linguaggio per vederlo funzionare dal vivo.