C ++ Templates is a Turing-complete language in which you can write compile-time programs. Only here the syntax is designed for the description of parameterized types and is poorly adapted to clearly express something more complex. In this article, we will look at how types and patterns become values and functions, and also find out what the author’s attempt to create a functional language that translates into C ++ patterns led to. Knowledge of functional programming is almost not required to read text.constexpr added for practical use, but I wanted to stay in the area of perverted entertainment and use the minimum of language features. Wonderful articles Life during compilation from HurrTheDurr and Interpretation at compile time, or Alternative understanding of lambda in C ++ 11 by ilammy (the second is more hardcore and without using template with constexpr ) described almost everything that the perverted mind needed to know. In the end, I left the article in the drafts, but did not leave the desire to metaprogram. And today I come back with newly written text and new ideas.std::vector metafunction takes the meta value T and returns the meta value std::vector<T> . It is important that metadata has a set of metafields (from the point of view of C ++, nested classes, type aliases, static constant fields) with which you can make the most interesting.value , and understand it as the value that the metafunction returns. Metafunctions over integers are fairly simple: template <int x> struct square { static const int value = x * x; }; square<5>::value . struct One; struct Zero; one and zero only declared and practically useless. is that enough? Yes. What, then, are they equal and how to use them? Equal to them, which is important, only to themselves. These are a kind of abstract symbols that can be used in symbolic calculations (almost as in Mathematica, etc.). The metaprogram will calculate the values of meta expressions of varying complexity. We first consider these expressions, and a little later we will deal with the interpretation of symbols and the display of results on the screen. template <typename T> struct Not { typedef Zero value; }; template <> struct Not <Zero> { typedef One value; }; Not takes some value and returns one if this value is zero. In all other cases, it will return zero. Thus, due to the specialization of templates, we have pattern matching (comparison with a sample) in the embryonic stage: we can describe separately the behavior of a function for one or several arguments that have specific values, and the C ++ compiler, noting that the template parameters match one of the samples, will substitute necessary specialization. Using this, we could already write something recursive (for example, factorial, dividing the description into fac<0> and fac< > ).value , you can imagine how many-valued functions look. We write the constructor of the Cons list and the empty Nil list, familiar to connoisseurs of functional programming: template <typename h, typename t> struct Cons { typedef h head; typedef t tail; }; struct Nil; Cons in the OP is a function that constructs a list of the first element (head) and the list of other elements (tail). Normal list \ {one, two, three \}\ {one, two, three \} will correspond to Cons<one, Cons<two, Cons<three, Nil>>> . Since to work with a list you need to be able to get its components, we will make Cons multivalued function that returns the head ( Cons<...,...>::head ) and tail ( Cons<...,...>::tail ). OOP lovers can imagine that Cons is a constructor, and head and tail are getters. In the FP, all assignments are replaced by a // template <typename list> struct negate { private: // typedef typename list::head h; // typedef typename Not<h>::value not_head; // typedef typename list::tail t; // typedef typename negate<t>::value not_tail; // public: // - , // typedef Cons<not_head, not_tail> value; }; // template <> struct negate <Nil> { // - typedef Nil value; }; f (x+y) (gy) z . -- - ( - ), -- data List a = Cons a List | Nil -- head (Cons x _) = x -- tail (Cons _ xs) = xs -- -- negate (Cons x xs) = Cons (Not x) (negate xs) negate Nil = Nil negate<One>::value , of course, will not work, but if One has the metafield and head and tail , it will be fine. However, while the negate<One> not “dereferenced” with ::value , the program continues -- map f (Cons x xs) = Cons (fx) (map f xs) -- map f Nil = Nil std::transform . In our language, the map metafunction is declared using template template parameterization: // // f - - template <template <typename> class f, typename list> struct map { private: typedef typename list::head h; // typedef typename f<h>::value new_head; // typedef typename list::tail t; // typedef typename map<f, t>::value new_tail; // public: // typedef Cons<new_head, new_tail> value; }; // template <template <typename> class f> struct map<f, Nil> { // typedef Nil value; }; f here, we can substitute the function Not described earlier and calculate the list of negatives: typedef map<Not, Cons<One, Cons<One, Cons<Zero, Nil>>>>::value list; // list Cons<Zero, Cons<Zero, Cons<One, Nil>>> typedef is some equivalent of an assignment operator. Or, which sounds more correct for functional languages, is the operation of specifying the name and expression. using x = Not<One>::value; template <typename xs> using g = Cons<x, xs>; value metafield when the metafunction returns a single meta value. This can be more convenient if the programmer is too lazy to explicitly specify ::value , and also impose a computability requirement.negate<Zero> compiled, but negate<Zero>::value is not. Using the cumbersome metafields, you can write a branch metafunction that calculates ::value for only one branch depending on the condition and returns this value. It turns out that one of the expressions will never be calculated: all operations are performed only when receiving ::value , and nobody touched it: // template <typename expr1, typename expr2> struct If <True, expr1, expr2> { // expr1, expr2 , expr1::value expr2::value - typedef typename expr1::value value; } // If<One, id<One>, destroy<the_world>>::value g<x> makes sense of the already calculated f<x>::value . And if you branch between two recursive variants, the calculations will be infinite - an analog of stack overflow at the compilation stage. template <typename expr1, typename expr2> struct If <True, expr1, expr2> { // expr1, expr2 typedef expr1 value; }; // If<One, One, destroy<the_world>::value>::value fx returns a unary function g , implicitly using the x argument of f . fx = g where g xs = Cons x xs -- : (fx) xs , , map (fx) list Cons , but g can be passed as a unary function into an already written map function, and as a binary one, Cons not!this contains the entire context of interest, and operator () takes the arguments required by the interface. The beautiful concept of the OP is replaced by the equivalent power concept of the PLO. Even the standard std::function template is provided! // C++11: , struct f { f(something& x) : x(x) {} something_else operator () (something_else& xs) { // xs - return Cons(x, xs); } private: something x; // }; // C++11 : -, something x; auto f = [x](something_else& xs) { return Cons(x, xs); }; int(int) ) with functional objects (for example, std::function<int(int)> ), the C ++ programmer gets a full-fledged closure. template <typename x> struct f { template <typename xs> struct g { typedef Cons<x, xs> value; }; }; // : f<x>::g<list>::value map<f<x>::g, list> g character comes out of f here, but the rest is fair closure. The expression f<x>::g can be used instead of the usual unary function (for example, Not ).Cons and Nil . In addition, it may be even more simple move. To transfer two lists to a metafunction, it’s enough ... to transfer two lists: f<xs, ys> , for variadic templates, you need to set a wrapper that captures all lists except the last one: f<list_wrapper<x1,x2,x3>, y1, y2, y3> , since the list of arguments of arbitrary length must be one, and several lists written in a row simply “stick together”. Upon completion of the calculations, you have to return the wrapper, since in C ++ you cannot add a list of several types. And in order to “pick out” the list from the wrapper and transfer it to the metafunction (say, f ), you will have to use metacallbacks: implement the metamethod that accepts this metafunction f and transfers the contents of the list to the wrapper: typename <typename... xs> struct list_wrapper { // list_wrapper<...>::call , // xs struct call<template <typename...> class f> { typedef typename f<xs...>::value value; }; }; negate you need to construct an auxiliary unary metafunction f , which takes the result of the recursive use of negate to the tail of the list, calculates the negation of the head, and returns the wrapper for the list assembled together: typename <typename x, typename... xs> struct negate { template <typename... ys> struct f { typedef list_wrapper<Not<x>::value, ys> value; }; typedef typename negate<xs>::template call<f>::value; }; typename <> struct negate<> { typedef list_wrapper<> value; }; negate looks more cumbersome even compared to the version for Cons / Nil . It also requires more serious fabrications, when, as writing a “normal” version, the basics of the OP and mechanical replacement of Haskell → C ++ are sufficient. Therefore, using variadic templates, it is better to write a wrapper for converting the sequence of parameters into the Cons / Nil list, and then using the program to use it already. So we will be able to set the lists by a pleasant comma-separated listing, and to think in more simple categories.void One::print(); ), or inside the meta-function, if the possibilities of the pattern-match are enough to consider all the options. For example, a print metafunction that prints its argument (one, zero, or a list) at the stage of constructing an instance of print<...> : template <typename T> struct print { print () { std::cout << "unknown number" << std::endl; } }; template <> struct print <One> { print () { std::cout << "1" << std::endl; } }; template <> struct print <Zero> { print () { std::cout << "0" << std::endl; } }; // print<Not<Zero>::value>() "1" One and Zero and build addition, multiplication, ...decltype it was impossible to carry out purely functional calculations on types, create variables and C ++ objects of the appropriate types, perform calculations on them, and then return to calculations on types. sum<sum<One, two>, three> // - sum<sum<One, two>, three>() // - do_something(sum<One, two>(), three()) // - sum<sum<One, two>(), three()> // , // .. sum<decltype(sum<One, two>()), decltype(three())> // C++11; decltype types were an analogy of purity, and values were entities of the imperative world: only a type could be a template parameter, and a type could only be obtained by type conversions; once creating a value, it was impossible to go back to types.decltype . However, decltype does not decltype its argument, but only answers the question "what would be the type of expression if we began to consider it," which does not violate functional purity. Therefore, as long as the expression above the variables does not leave the decltype bracket , purity is preserved. From the point of view of the template language, decltype beneficial to use along with operator overloading. In the following example, the expressions are equivalent, but the bottom one looks less cumbersome: typedef sum<sum<one, two>, three> x; typedef decltype(one() + two() + three()) x; auto v = one() + two() + three(); // v typedef decltype(v) x; ::value , parentheses and typename exhaust the programmer and stretch the program code. Of course, the logic says that one who decides to program in such a style should suffer, but ... this is one of those perverted entertainments to which the IT specialist's brain often leans. I want to try to do so that the perversion is preserved, but to the extent that suffering can still be endured. One; Zero; Not (val x) = Zero; // Not (Zero) = One; // And(val x, val y); // x,y != One,Zero And And(val x, One) = x; // One - , val x - And(val x, Zero) = Zero; // : Not(One) And(One, Zero) typename), another template ( template <typename> class), etc., and this should be indicated. So, creating meta-phwp, one typenamecan not do, and the requirement to specify the type also goes into my language. By default, the type is set valto correspond to the usual meta value (structure or normal type in C ++). To describe the functions, you can combine types with the arrow ( ->). For example, val -> val- a unary function (a template that takes one parameter), (val, val) -> val- a binary function (a template that takes two parameters), and so on.#type You can specify synonyms to shorten the record a little more and clarify the meaning through appropriate naming: #type number = val; #type list = val; #type unary = number -> number; #type map_t = (unary, list) -> list; // map_t template <template <typename> class, typename> class #typeas an analogue #definein C, which sets textual transformations, which can also be carried out manually in a simple way. Nil; Cons(val x, val y) { head = x; tail = y; } ::value. That is f(x)equivalent f<x>::value. But Consit is generated only two Metafields headand tail. To prevent the disclosure ::valueis required explicitly by using the apostrophe: Cons(x, xs)'.::valueas one of the frequent constructs, it had to open automatically, but there had to be an opportunity to (a) convey an undisclosed value (see the problem of the branch function and infinite recursion above the spoiler) and (b) use other metafields except value. As a result, I settled on “shielding”, recording metafields through a dot, and introduced the reverse “!” Operator for shielding, revealing ::value: Cons(x, xs)'.head; // x Cons(x, xs)'.tail; // xs Not(Zero); // One Not(Zero)'!; // One ::valuemay well coexist with multiple returns. Implementing the negation of the list negatein C ++, we created local metavariables that could be returned. Here is the same, only all values are public: // : // - , // negate (list list) = Cons(not_head, not_tail)' { h = list.head; // not_head = Not(h); // t = list.tail; // not_tail = negate(t); // } // ! // - negate (Nil) = Nil; // map (unary f, list list) = Cons(new_head, new_tail)' { h = list.head; // new_head = f(h); // t = list.tail; // new_tail = map(f, t); // } // map (unary f, Nil) = Nil; unaryand listit was possible to immediately indicate val -> val, valrespectively, but the record would have been longer and less visual. f(val x) = { g(val xs) = Cons(x, xs)'; } // : f(x)'.g(list) map(f(x)'.g, list) valuereturned would have to have a name and return value. A member of the same name with a class in C ++ is already given to the constructor, which is why assigning a new meaning to it through typedefleads to a compilation error: template <typename x> struct f { template <typename xs> struct value { // value! typedef Cons<x, xs> value; // value! }; }; f (val x) = g(Not(x)) { g (val x) = x; // g (x1) = x1 // .. x template f x template g } ::value, it is not said anywhere thatf(x)- it is f<x>::value, but not call<f, x>::result. This knowledge was stored inside the translator , and its use in the program would break through the abstraction: f(val x) = One; f(Zero) = Zero; main { print<f<One>::value>(); // ? } impure { }may appear instead of a value / function declaration, as well as to the right after the "=" sign when a function is declared. In these cases, C ++ code is inserted into the appropriate place in the program. To export an expression, a keyword is placed before it impure. From the point of view of C ++, this is equivalent to constructing an object of the type described by the expression.impureprepare a list “printer”: print(val list) { head = list.head; tail = list.tail; impure { // typedef- head, tail : print() { impure print(head); // "print<head>();" std::cout << ", "; impure print(tail); } } } print(Zero) = impure { // print(Zero) { impure { ..., print() { std::cout << "0"; } } print(One) = impure { print() { std::cout << "1"; } } print(Nil) = impure { print() { std::cout << std::endl; } } namespaceand using namespace: namespace ns1 { namespace ns2 { f(val x) = x; } } namespace ns3 { using namespace ns1.ns2; g(val x) = f(x); } using namespaceis also a necessary measure. In C ++, in some cases, not enough of the record type f<x>::y<z>. If f, xor zare not specific types / templates, but template parameters, it ::ybecomes the output of the black box. It is necessary to specify what we get in the calculation ::y- type or pattern (for example, typename f<x>::yor f<x>::template y<z>). I did not automate these instructions and did not implement syntactic sugar for a simpler manual description, therefore each use of a dot causes the appearance of a “typename”. Those. f<x>::y<z>It is translated into something incorrect form typename typename f<x>::value::typename y<z>::value. In the case of a namespace, this unnecessarily using namespaceallows you to do without the insertion of "typename". f (val x) = y(x) { y(x) = g(x); } // f = lambda (val x) -> y(x) { y(x) = g(x); } // template <typename x> struct f {}; // f using g = f; // // , template <typename x> using g = f<x>; // g<x> - , f<x> - map(lambda(val x) -> y, xs)will have to modify the language and generate templates with temporary names.value::valuethis is a constructor, so it is not possible to directly implement a lambda, which returns a lambda. To return functions from lambdas and resolve view records, g = fyou need to use other concepts and almost completely rewrite the translator.impure { private: }into the code or by elementary modification of the language.fMap(fCurry(fCons).fApply(vXs), vObj.vYs) — template , typename , «f», «v» «n» ). // x struct x { typedef internal::value type; // x }; // f(x) = x struct f { typedef internal::function type; // f template <typename x> struct value { typedef typename x::type type; // f struct result { // , value::value typedef x value; }; }; }; internal ; struct result value::value . - , ( , ), ( typedef ), , .value , . , value::value value1::value2 : template <typename x> struct f { typedef internal::True uses_value1; // value1 template <typename y> struct value1 { typedef internal::False uses_value1; // value2 typedef Cons<x, y> value2; }; }; uses_value1 , value1 value2 .valother types of numbers ( int, uint, ...) and arrays ( [val], [int], [uint]...). When using metafields, you will have to solve the problem described above with an indication templateand typename, since for numbers, nothing is required, but for types and patterns - required.main: // : my_list = Cons(One, Cons(One, Cons(Zero, Nil)')')'; negated_list = negate(my_list); negated_list2 = map(Not, my_list); impure { int main() { // : std::cout << "my list is "; impure print(my_list); std::cout << "negated list is "; impure print(negated_list); std::cout << "negated list is also "; impure print(negated_list2); } } my list is 1, 1, 0, negated list is 0, 0, 1, negated list is also 0, 0, 1, impure { #include <iostream> } One; Zero; Not (val x) = Zero; // Not (Zero) = One; // And(val x, val y); // x,y != One,Zero And And(val x, One) = x; // One - , val x - And(val x, Zero) = Zero; #type number = val; #type list = val; #type unary = number -> number; #type map_t = (unary, list) -> list; Nil; Cons(val x, val y) { head = x; tail = y; } // : negate (list list) = Cons(not_head, not_tail)' { h = list.head; not_head = Not(h); t = list.tail; not_tail = negate(t); } // - negate (Nil) = Nil; // map (unary f, list list) = Cons(new_head, new_tail)' { h = list.head; new_head = f(h); t = list.tail; new_tail = map(f, t); } // map (unary f, Nil) = Nil; print(val list) { head = list.head; tail = list.tail; impure { print() { impure print(head); std::cout << ", "; impure print(tail); } } } print(Zero) = impure { print() { std::cout << "0"; } } print(One) = impure { print() { std::cout << "1"; } } print(Nil) = impure { print() { std::cout << std::endl; } } my_list = Cons(One, Cons(One, Cons(Zero, Nil)')')'; negated_list = negate(my_list); negated_list2 = map(Not, my_list); impure { int main() { std::cout << "my list is "; impure print(my_list); std::cout << "negated list is "; impure print(negated_list); std::cout << "negated list is also "; impure print(negated_list2); } } #include <iostream> struct One; struct Zero; template <typename x> struct Not { typedef Zero _value; }; template <> struct Not<Zero> { typedef One _value; }; template <typename x, typename y> struct And; template <typename x> struct And<x, One> { typedef x _value; }; template <typename x> struct And<x, Zero> { typedef Zero _value; }; struct Nil; template <typename x, typename y> struct Cons { typedef x head; typedef y tail; }; template <typename list> struct negate { typedef typename list::head h; typedef typename Not <h> ::_value not_head; typedef typename list::tail t; typedef typename negate <t> ::_value not_tail; typedef Cons <not_head, not_tail> _value; }; template <> struct negate<Nil> { typedef Nil _value; }; template <template <typename> class f, typename list> struct map { typedef typename list::head h; typedef typename f <h> ::_value new_head; typedef typename list::tail t; typedef typename map <f, t> ::_value new_tail; typedef Cons <new_head, new_tail> _value; }; template <template <typename> class f> struct map<f, Nil> { typedef Nil _value; }; template <typename list> struct print { typedef typename list::head head; typedef typename list::tail tail; print() { print <head> (); std::cout << ", "; print <tail> (); } }; template <> struct print<Zero> { print() { std::cout << "0"; } }; template <> struct print<One> { print() { std::cout << "1"; } }; template <> struct print<Nil> { print() { std::cout << std::endl; } }; typedef Cons <One, Cons <One, Cons <Zero, Nil> > > my_list; typedef typename negate <my_list> ::_value negated_list; typedef typename map <Not, my_list> ::_value negated_list2; int main() { std::cout << "my list is "; print <my_list> (); std::cout << "negated list is "; print <negated_list> (); std::cout << "negated list is also "; print <negated_list2> (); } node src/compile <> # Source: https://habr.com/ru/post/337590/
All Articles