Bangau, Bagian 3: Menerapkan Ekspresi dan Variabel

Di Bagian 3 dari seri kami, bahasa pemrograman ringan kami akhirnya akan berjalan. Itu tidak akan Turing-lengkap, itu tidak akan kuat, tetapi akan dapat mengevaluasi ekspresi dan bahkan memanggil fungsi eksternal yang ditulis dalam C++.

Saya akan mencoba menjelaskan prosesnya sedetail mungkin, terutama karena itu adalah tujuan dari seri blog ini, tetapi juga untuk dokumentasi saya sendiri karena, di bagian ini, semuanya menjadi sedikit rumit.

Saya mulai mengkode untuk bagian ini sebelum publikasi artikel kedua, tetapi ternyata pengurai ekspresi harus menjadi komponen mandiri yang layak mendapatkan posting blognya sendiri.

Itu, bersama dengan beberapa teknik pemrograman yang terkenal, memungkinkan bagian ini tidak terlalu besar, namun, beberapa pembaca kemungkinan besar akan menunjuk pada teknik pemrograman tersebut dan bertanya-tanya mengapa saya harus menggunakannya.

Mengapa Kami Menggunakan Macro?

Ketika saya memperoleh pengalaman pemrograman bekerja pada proyek yang berbeda dan dengan orang yang berbeda, saya belajar bahwa pengembang cenderung sangat dogmatis — mungkin karena lebih mudah seperti itu.

Dogma pertama pemrograman adalah bahwa pernyataan goto itu buruk, jahat, dan mengerikan. Saya bisa mengerti dari mana sentimen itu berasal, dan saya setuju dengan gagasan itu di sebagian besar kasus ketika seseorang menggunakan pernyataan goto . Biasanya dapat dihindari, dan kode yang lebih mudah dibaca dapat ditulis sebagai gantinya.

Namun, seseorang tidak dapat menyangkal bahwa pemutusan dari loop dalam di C++ dapat dengan mudah dilakukan dengan pernyataan goto . Alternatifnya—yang memerlukan variabel bool atau fungsi khusus—bisa jadi kurang terbaca daripada kode yang secara dogmatis termasuk dalam ember teknik pemrograman terlarang.

Dogma kedua, yang relevan secara eksklusif untuk pengembang C dan C++, adalah bahwa makro itu buruk, jahat, mengerikan, dan pada dasarnya, bencana yang menunggu untuk terjadi. Ini hampir selalu disertai dengan contoh ini:

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

Dan kemudian ada pertanyaan: Berapa nilai x setelah potongan kode ini, dan jawabannya adalah 5 karena x bertambah dua kali, satu di setiap sisi ? -operator.

Satu-satunya masalah adalah tidak ada yang menggunakan makro dalam skenario ini. Makro jahat jika digunakan dalam skenario di mana fungsi biasa berfungsi dengan baik, terutama jika mereka berpura-pura menjadi fungsi, sehingga pengguna tidak menyadari efek sampingnya. Namun, kami tidak akan menggunakannya sebagai fungsi, dan kami akan menggunakan huruf balok untuk nama mereka untuk memperjelas bahwa mereka bukan fungsi. Kami tidak akan dapat men-debug mereka dengan benar, dan itu buruk, tetapi kami akan hidup dengan itu, karena alternatifnya adalah menyalin-menempelkan kode yang sama puluhan kali, yang jauh lebih rawan kesalahan daripada makro. Salah satu solusi untuk masalah itu adalah menulis pembuat kode, tetapi mengapa kita harus menulisnya ketika kita sudah memilikinya di C++?

Dogma dalam pemrograman hampir selalu buruk. Saya dengan hati-hati menggunakan "hampir" di sini hanya untuk menghindari jatuh secara rekursif ke dalam perangkap dogma yang baru saja saya buat.

Anda dapat menemukan kode dan semua makro untuk bagian ini di sini.

Variabel

Di bagian sebelumnya, saya menyebutkan bahwa Bangau tidak akan dikompilasi ke dalam biner atau apa pun yang mirip dengan bahasa assembly, tetapi saya juga mengatakan bahwa itu akan menjadi bahasa yang diketik secara statis. Oleh karena itu, itu akan dikompilasi, tetapi dalam objek C++ yang akan dapat dieksekusi. Ini akan menjadi lebih jelas nanti tetapi untuk saat ini, mari kita nyatakan bahwa semua variabel akan menjadi objeknya sendiri.

Karena kita ingin menyimpannya dalam wadah variabel global atau di tumpukan, satu pendekatan yang mudah adalah mendefinisikan kelas dasar dan mewarisinya.

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

Seperti yang Anda lihat, ini cukup sederhana, dan fungsi clone , yang melakukan salinan dalam, adalah satu-satunya fungsi anggota virtual selain dari destruktor.

Karena kita akan selalu menggunakan objek kelas ini melalui shared_ptr , masuk akal untuk mewarisinya dari std::enable_shared_from_this , sehingga kita dapat dengan mudah mendapatkan pointer bersama darinya. Fungsi static_pointer_downcast ada di sini untuk kenyamanan karena kita sering harus downcast dari kelas ini ke implementasinya.

Implementasi nyata dari kelas ini adalah variable_impl , diparametrikan dengan tipe yang dipegangnya. Ini akan dipakai untuk empat jenis yang akan kita gunakan:

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

Kami akan menggunakan double sebagai jenis nomor kami. String dihitung sebagai referensi, karena tidak dapat diubah, untuk mengaktifkan pengoptimalan tertentu saat meneruskannya berdasarkan nilai. Array akan menjadi std::deque , karena stabil, dan perhatikan bahwa runtime_context adalah kelas yang menyimpan semua informasi yang relevan tentang memori program selama runtime. Kami akan membahasnya nanti.

Definisi berikut juga sering digunakan:

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

Huruf "l" yang digunakan di sini disingkat menjadi "nilai". Setiap kali kita memiliki lvalue untuk beberapa tipe, kita akan menggunakan pointer bersama ke variable_impl .

Konteks Waktu Proses

Selama runtime, status memori disimpan di kelas 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); };

Ini diinisialisasi dengan jumlah variabel global.

• _globals menyimpan semua variabel global. Mereka diakses dengan fungsi anggota global dengan indeks absolut.
• _stack menyimpan variabel lokal dan argumen fungsi, dan integer di bagian atas _retval_idx menyimpan indeks absolut di _stack dari nilai pengembalian saat ini.
• Nilai kembalian diakses dengan fungsi retval , sedangkan variabel lokal dan argumen fungsi diakses dengan fungsi local dengan melewatkan indeks relatif terhadap nilai pengembalian saat ini. Argumen fungsi memiliki indeks negatif dalam kasus ini.
• Fungsi push menambahkan variabel ke tumpukan, sementara end_scope menghapus jumlah variabel yang diteruskan dari tumpukan.
• Fungsi call akan mengubah ukuran tumpukan satu per satu dan mendorong indeks elemen terakhir di _stack ke _retval_idx .
• end_function menghapus nilai kembalian dan jumlah argumen yang diteruskan dari tumpukan dan juga mengembalikan nilai pengembalian yang dihapus.

Seperti yang Anda lihat, kami tidak akan menerapkan manajemen memori tingkat rendah apa pun dan kami akan memanfaatkan manajemen memori asli (C++), yang dapat kami terima begitu saja. Kami juga tidak akan menerapkan alokasi tumpukan, setidaknya untuk saat ini.

Dengan runtime_context , kami akhirnya memiliki semua blok bangunan yang diperlukan untuk komponen utama dan paling sulit dari bagian ini.

Ekspresi

Untuk sepenuhnya menjelaskan solusi rumit yang akan saya hadirkan di sini, saya akan secara singkat memperkenalkan Anda pada beberapa upaya gagal yang saya lakukan sebelum memutuskan pendekatan ini.

Pendekatan termudah adalah mengevaluasi setiap ekspresi sebagai variable_ptr dan memiliki kelas dasar virtual ini:

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

Kami kemudian akan mewarisi dari kelas ini untuk setiap operasi, seperti penambahan, penggabungan, panggilan fungsi, dll. Misalnya, ini akan menjadi implementasi ekspresi tambahan:

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

Jadi kita perlu mengevaluasi kedua sisi ( _expr1 dan _expr2 ), menambahkannya, dan kemudian membangun variable_impl<number> .

Kami dapat menurunkan variabel dengan aman karena kami memeriksa tipenya selama waktu kompilasi, jadi bukan itu masalahnya di sini. Namun, masalah besarnya adalah penalti kinerja yang kami bayar untuk alokasi tumpukan objek yang kembali, yang—secara teori—tidak diperlukan. Kami melakukan itu untuk memenuhi deklarasi fungsi virtual. Di versi pertama Stork, kita akan mendapatkan penalti itu ketika kita mengembalikan angka dari fungsi. Saya bisa hidup dengan itu tetapi tidak dengan ekspresi pra-kenaikan sederhana yang melakukan alokasi tumpukan.

Kemudian, saya mencoba dengan ekspresi khusus tipe yang diwarisi dari basis umum:

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

Ini hanya bagian dari hierarki (hanya untuk angka), dan kami telah mengalami masalah bentuk berlian (kelas mewarisi dua kelas dengan kelas dasar yang sama).

Untungnya, C++ menawarkan pewarisan virtual, yang memberikan kemampuan untuk mewarisi dari kelas dasar, dengan menyimpan penunjuk ke sana, di kelas yang diwarisi. Oleh karena itu, jika kelas B dan C mewarisi hampir dari A, dan kelas D mewarisi dari B dan C, hanya akan ada satu salinan A di D.

Ada sejumlah penalti yang harus kita bayar dalam kasus itu, meskipun — kinerja dan ketidakmampuan untuk turun dari A, untuk beberapa nama — tetapi ini masih tampak seperti kesempatan bagiku untuk menggunakan warisan virtual untuk pertama kalinya di hidupku.

Sekarang, implementasi ekspresi tambahan akan terlihat lebih alami:

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

Dari segi sintaks, tidak ada lagi yang perlu ditanyakan, dan ini sealami mungkin. Namun, jika salah satu ekspresi dalam adalah ekspresi bilangan bernilai, itu akan memerlukan dua panggilan fungsi virtual untuk mengevaluasinya. Tidak sempurna, tapi juga tidak mengerikan.

Mari tambahkan string ke dalam campuran ini dan lihat di mana itu membawa kita:

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

Karena kita ingin angka dapat dikonversi menjadi string, kita perlu mewarisi number_expression dari 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>;

Kami selamat dari itu, tetapi kami harus mengganti ulang metode evaluate virtual, atau kami akan menghadapi masalah kinerja yang serius karena konversi yang tidak perlu dari angka ke string.

Jadi, hal-hal menjadi jelek, dan desain kami hampir tidak bertahan karena kami tidak memiliki dua jenis ekspresi yang harus dikonversi satu ke yang lain (dua arah). Jika itu masalahnya, atau jika kami mencoba melakukan konversi melingkar apa pun, hierarki kami tidak dapat menanganinya. Bagaimanapun, hierarki harus mencerminkan hubungan is-a, bukan is-convertible-to, yang lebih lemah.

Semua upaya yang gagal ini membawa saya ke desain yang rumit - menurut saya - yang tepat. Pertama, memiliki satu kelas dasar tidak penting bagi kami. Kita membutuhkan kelas ekspresi yang akan dievaluasi menjadi void, tetapi jika kita dapat membedakan antara ekspresi void dan ekspresi jenis lain dalam waktu kompilasi, tidak perlu mengonversinya dalam waktu proses. Oleh karena itu, kita akan membuat parameter kelas dasar dengan tipe kembalian dari ekspresi.

Berikut adalah implementasi penuh dari kelas itu:

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

Kami hanya akan memiliki satu panggilan fungsi virtual per evaluasi ekspresi (tentu saja, kami harus memanggilnya secara rekursif), dan karena kami tidak mengkompilasi ke kode biner, itu adalah hasil yang cukup baik. Satu-satunya yang tersisa untuk dilakukan adalah konversi antar jenis, bila diizinkan.

Untuk mencapai itu, kita akan membuat parameter setiap ekspresi dengan tipe pengembalian dan mewarisinya dari kelas dasar yang sesuai. Kemudian, pada fungsi evaluate , kita akan mengubah hasil evaluasi menjadi nilai balik dari fungsi tersebut.

Misalnya, ini adalah ekspresi penambahan kami:

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

Untuk menulis fungsi "convert", kita memerlukan beberapa infrastruktur:

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

Struktur is_boxed adalah sifat tipe yang memiliki konstanta bagian dalam, value , yang bernilai true jika (dan hanya jika) parameter pertama adalah penunjuk bersama ke variable_impl yang diparametrikan dengan tipe kedua.

Implementasi fungsi convert akan dimungkinkan bahkan di versi C++ yang lebih lama, tetapi ada pernyataan yang sangat berguna di C++17 yang disebut if constexpr , yang mengevaluasi kondisi dalam waktu kompilasi. Jika bernilai false , itu akan menghapus blok sama sekali, bahkan jika itu menyebabkan kesalahan waktu kompilasi. Jika tidak, itu akan menjatuhkan blok else .

 template<typename To, typename From> auto convert(From&& from) { if constexpr(std::is_convertible<From, To>::value) { return std::forward<From>(from); } else if constexpr(is_boxed<From, To>::value) { return unbox(std::forward<From>(from)); } else if constexpr(std::is_same<To, string>::value) { return convert_to_string(from); } else { static_assert(std::is_void<To>::value); } }

Coba baca fungsi ini:

• Konversi jika dapat dikonversi dalam C++ (ini untuk variable_impl pointer upcast).
• Buka kotak jika kotak.
• Konversikan ke string jika tipe targetnya adalah string.
• Jangan lakukan apa pun dan periksa apakah targetnya batal.

Menurut pendapat saya, ini jauh lebih mudah dibaca daripada sintaks lama berdasarkan SFINAE.

Saya akan memberikan gambaran singkat tentang jenis ekspresi dan menghilangkan beberapa detail teknis untuk membuatnya cukup singkat.

Ada tiga jenis ekspresi daun dalam pohon ekspresi:

• Ekspresi variabel global
• Ekspresi variabel lokal
• Ekspresi konstan

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

Terlepas dari tipe pengembalian, itu juga diparametrikan dengan tipe variabel. Variabel lokal diperlakukan sama, dan ini adalah kelas untuk konstanta:

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

Dalam hal ini, kami mengonversi konstanta segera di konstruktor.

Ini digunakan sebagai kelas dasar untuk sebagian besar ekspresi kami:

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

Argumen pertama adalah tipe functor yang akan dipakai dan dipanggil untuk evaluasi. Jenis lainnya adalah jenis pengembalian ekspresi anak.

Untuk mengurangi kode boilerplate, kami mendefinisikan tiga makro:

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

Perhatikan bahwa operator() didefinisikan sebagai template, meskipun biasanya tidak harus demikian. Lebih mudah untuk mendefinisikan semua ekspresi dengan cara yang sama daripada menyediakan tipe argumen sebagai argumen makro.

Sekarang, kita dapat mendefinisikan sebagian besar ekspresi. Misalnya, ini adalah definisi untuk /= :

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

Kita dapat mendefinisikan hampir semua ekspresi dengan menggunakan makro ini. Pengecualian adalah operator yang telah mendefinisikan urutan evaluasi argumen (logis && dan || , operator ternary ( ? ) dan koma ( , )), indeks array, panggilan fungsi, dan param_expression , yang mengkloning parameter untuk meneruskannya ke fungsi berdasarkan nilai.

Tidak ada yang rumit dalam penerapannya. Implementasi pemanggilan fungsi adalah yang paling kompleks, jadi saya akan menjelaskannya di sini:

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

Ini mempersiapkan runtime_context dengan mendorong semua argumen yang dievaluasi pada tumpukannya dan memanggil fungsi call . Ia kemudian memanggil argumen pertama yang dievaluasi (yang merupakan fungsi itu sendiri) dan mengembalikan nilai kembalian dari metode end_function . Kita juga bisa melihat penggunaan sintaks if constexpr di sini. Ini menyelamatkan kita dari penulisan spesialisasi untuk seluruh kelas untuk fungsi yang mengembalikan void .

Sekarang, kami memiliki semua yang terkait dengan ekspresi yang tersedia selama runtime. Satu-satunya yang tersisa adalah konversi dari pohon ekspresi yang diuraikan (dijelaskan dalam posting blog sebelumnya) ke pohon ekspresi.

Pembuat Ekspresi

Untuk menghindari kebingungan, beri nama fase yang berbeda dari siklus pengembangan bahasa kita:

• Meta-compile-time: fase ketika compiler C++ berjalan
• Waktu kompilasi: fase ketika kompiler Bangau berjalan
• Runtime: fase ketika skrip Bangau berjalan

Berikut adalah pseudo-code untuk pembuat ekspresi:

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

Selain harus menangani semua operasi, ini tampak seperti algoritma yang mudah.

Jika berhasil, itu akan bagus, tetapi tidak. Sebagai permulaan, kita perlu menentukan tipe pengembalian fungsi, dan ini jelas tidak diperbaiki di sini, karena tipe pengembalian tergantung pada tipe node yang kita kunjungi. Tipe node diketahui pada waktu kompilasi, tetapi tipe pengembalian harus diketahui pada waktu kompilasi meta.

Dalam posting sebelumnya, saya menyebutkan bahwa saya tidak melihat keuntungan dari bahasa yang melakukan pengecekan tipe dinamis. Dalam bahasa seperti itu, kode semu yang ditunjukkan di atas dapat diimplementasikan hampir secara harfiah. Sekarang, saya cukup menyadari keuntungan dari bahasa tipe dinamis. Karma instan yang terbaik.

Untungnya, kami mengetahui jenis ekspresi tingkat atas - ini bergantung pada konteks kompilasi, tetapi kami mengetahui jenisnya tanpa menguraikan pohon ekspresi. Misalnya, jika kita memiliki for-loop:

 for (expression1; expression2; expression3) ...

Ekspresi pertama dan ketiga memiliki tipe pengembalian void karena kami tidak melakukan apa pun dengan hasil evaluasinya. Ekspresi kedua, bagaimanapun, memiliki number tipe karena kami membandingkannya dengan nol, untuk memutuskan apakah akan menghentikan loop atau tidak.

Jika kita mengetahui jenis ekspresi yang terkait dengan operasi simpul, biasanya akan ditentukan jenis ekspresi anaknya.

Misalnya, jika ekspresi (expression1) += (expression2) memiliki tipe lnumber , itu berarti expression1 memiliki tipe itu juga, dan expression2 memiliki tipe number .

Namun, ekspresi (expression1) < (expression2) selalu memiliki tipe number , tetapi ekspresi turunannya dapat memiliki tipe number atau type string . Dalam hal ekspresi ini, kami akan memeriksa apakah kedua node adalah angka. Jika demikian, kita akan membangun expression1 dan expression2 sebagai expression<number> . Jika tidak, mereka akan bertipe expression<string> .

Ada masalah lain yang harus kita perhitungkan dan atasi.

Bayangkan jika kita perlu membangun ekspresi dari tipe number . Kemudian, kami tidak dapat mengembalikan apa pun yang valid jika kami mengalami operator gabungan. Kita tahu bahwa itu tidak bisa terjadi, karena kita sudah memeriksa tipe ketika kita membangun pohon ekspresi (di bagian sebelumnya), tapi itu berarti kita tidak bisa menulis fungsi template, diparametrikan dengan tipe kembalian, karena akan memiliki cabang yang tidak valid tergantung pada tipe pengembalian itu.

Satu pendekatan akan membagi fungsi berdasarkan tipe pengembalian, menggunakan if constexpr , tetapi tidak efisien karena jika operasi yang sama ada di banyak cabang, kita harus mengulangi kodenya. Kita bisa menulis fungsi terpisah dalam kasus itu.

Solusi yang diimplementasikan membagi fungsi berdasarkan tipe node. Di setiap cabang, kami akan memeriksa apakah tipe cabang tersebut dapat dikonversi ke tipe pengembalian fungsi. Jika tidak, kami akan membuang kesalahan kompiler, karena itu seharusnya tidak pernah terjadi, tetapi kodenya terlalu rumit untuk klaim yang begitu kuat. Saya mungkin telah membuat kesalahan.

Kami menggunakan struktur tipe-sifat yang cukup jelas berikut untuk memeriksa konvertibilitas:

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

Setelah pemisahan itu, kodenya hampir mudah. Kita dapat melakukan cast secara semantik dari tipe ekspresi asli ke tipe ekspresi yang ingin kita buat, dan tidak ada kesalahan dalam waktu kompilasi meta.

Namun, ada banyak kode boilerplate, jadi saya sangat bergantung pada makro untuk menguranginya.

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

Fungsi build_expression adalah satu-satunya fungsi publik di sini. Itu memanggil fungsi std::visit pada tipe node. Fungsi itu menerapkan functor yang diteruskan pada variant , memisahkannya dalam proses. Anda dapat membaca lebih lanjut tentang itu dan tentang functor yang overloaded di sini.

Makro RETURN_EXPRESSION_OF_TYPE memanggil fungsi pribadi untuk pembuatan ekspresi dan memberikan pengecualian jika konversi tidak memungkinkan:

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

Kita harus mengembalikan pointer kosong di cabang lain, karena kompilator tidak dapat mengetahui tipe pengembalian fungsi jika konversi tidak mungkin dilakukan; jika tidak, std::visit mengharuskan semua fungsi yang kelebihan beban memiliki tipe pengembalian yang sama.

Ada, misalnya, fungsi yang membangun ekspresi dengan string sebagai tipe pengembalian:

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

Ia memeriksa apakah node memegang konstanta string dan membangun constant_expression jika itu masalahnya.

Kemudian, ia memeriksa apakah node memiliki pengidentifikasi dan mengembalikan ekspresi variabel global atau lokal dari tipe lstring dalam kasus itu. Itu dapat menampung pengidentifikasi jika kita mengimplementasikan variabel konstan. Jika tidak, itu mengasumsikan bahwa node memegang operasi node dan mencoba semua operasi yang dapat mengembalikan string .

Berikut adalah implementasi makro CHECK_IDENTIFIER dan CHECK_BINARY_OPERATION :

 #define CHECK_IDENTIFIER(T1)\ if (std::holds_alternative<identifier>(np->get_value())) {\ const identifier& id = std::get<identifier>(np->get_value());\ const identifier_info* info = context.find(id.name);\ if (info->is_global()) {\ return std::make_unique<\ global_variable_expression<R, T1>\ >(info->index());\ } else {\ return std::make_unique<\ local_variable_expression<R, T1>\ >(info->index());\ }\ }

 #define CHECK_BINARY_OPERATION(name, T1, T2)\ case node_operation::name:\ return expression_ptr(\ std::make_unique<name##_expression<R, T1, T2> > (\ expression_builder<T1>::build_expression(\ np->get_children()[0], context\ ),\ expression_builder<T2>::build_expression(\ np->get_children()[1], context\ )\ )\ );

Makro CHECK_IDENTIFIER harus berkonsultasi compiler_context untuk membangun ekspresi variabel global atau lokal dengan indeks yang tepat. Itulah satu-satunya penggunaan compiler_context dalam struktur ini.

Anda dapat melihat bahwa CHECK_BINARY_OPERATION secara rekursif memanggil build_expression untuk node anak.

Membungkus

Di halaman GitHub saya, Anda bisa mendapatkan kode sumber lengkap, mengompilasinya, lalu mengetikkan ekspresi dan melihat hasil dari variabel yang dievaluasi.

Saya membayangkan bahwa, di semua cabang kreativitas manusia, ada saat ketika penulis menyadari bahwa produk mereka hidup, dalam arti tertentu. Dalam konstruksi bahasa pemrograman, ini adalah saat di mana Anda dapat melihat bahwa bahasa "bernafas."

Di bagian berikutnya dan terakhir dari seri ini, kami akan menerapkan sisa set minimal fitur bahasa untuk melihatnya berjalan secara langsung.