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 typename
can not do, and the requirement to specify the type also goes into my language. By default, the type is set val
to 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
#type
as an analogue #define
in 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 Cons
it is generated only two Metafields head
and tail
. To prevent the disclosure ::value
is required explicitly by using the apostrophe: Cons(x, xs)'
.::value
as 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
::value
may well coexist with multiple returns. Implementing the negation of the list negate
in 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;
unary
and list
it was possible to immediately indicate val -> val
, val
respectively, 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)
value
returned 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 typedef
leads 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.impure
prepare 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; } }
namespace
and using namespace
: namespace ns1 { namespace ns2 { f(val x) = x; } } namespace ns3 { using namespace ns1.ns2; g(val x) = f(x); }
using namespace
is also a necessary measure. In C ++, in some cases, not enough of the record type f<x>::y<z>
. If f
, x
or z
are not specific types / templates, but template parameters, it ::y
becomes 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>::y
or 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 namespace
allows 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::value
this 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 = f
you 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
.val
other 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 template
and 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