📜 ⬆️ ⬇️

Esoteric language translated into C ++ templates

KDV with code examples 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.

How it works?


Here we will lay the basic building blocks for building a compilation phase from the program templates. For those who are not familiar with functional programming, we will describe some necessary concepts in simple language. Having examined the basic things, we will be ready to switch to a new language, its syntax, capabilities and problems. Those who wish to go straight to the main point immediately can skip to the green image next to the repeated appearance of the article title.

Honestly, a couple of years ago I was trying to write here a post about explaining the principles of the work of compile-time programs using the example of the algorithm for changing the priorities of operators in expressions (i.e., I implemented options for the compile-time and run-time algorithm, which allowed 2 + 2 2 “Reassemble” with alternative priorities and calculate how eight , but not 6 ).

I’ve almost finished a long article with pictures and UML diagrams, but suddenly I realized that Habré was so often told about metaprograms that it’s simply not interesting to anyone. Especially because 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.
')
If, despite all my efforts, it will still be difficult for the reader to perceive the material, I recommend reading these articles, and after - a gentle introduction to Haskell ( part 1 , part 2 ) from Paul Hyudak and others, translated by Denis Moskvin and Lambda calculus on Javascript from ibessonov . All this to some extent influenced the author, maybe it will affect the reader ?!

Meta values ​​and meta functions


Class templates are, in a sense, functions of types that accept and return types. Accordingly, patterns become meta-functions, and types and integers become meta-values. For example, the 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.

We can single out one meta-field, for example 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; }; 

Called is applied, as they say in the FP, meta-function as follows: square<5>::value .

But integers are the usual meanings, to work with which simple C ++ is enough, and therefore it would be somewhat unsportsmanlike to use them in meta-expressions. A real honest meta value is a type. The easiest way to create it is to declare a structure:

 struct One; struct Zero; 

From the point of view of C ++, 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.

For zero and one as Boolean values, it is natural to write NOT, AND, and OR functions. Consider the negation metafunction:

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

List


If you do not limit yourself to the default 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 call using a function with modified arguments, so there will not be setters and their analogues here.

Such a list is usually recursive, since there are no cycles in functional languages:

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

It turns out that Haskell is not as scary as it is painted. All the same looks so simple that it is not a sin to add examples in this language for clarity. For the untrained reader, we note the main difference from C ++ and school math: in Haskell, arguments are separated by spaces and are not grouped in brackets. Those. f(x+y,g(y),z) will be written to Haskell as 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 

Unlike the strongly typed Haskell and C ++, duck-typing works in the template language. 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 to work to compile.

Higher order functions


In functional languages, functions are the same values. So, you can write a higher order function — that takes a function as an argument or returns a function. For example, element-by-element list conversion is performed using the FVP map:

 --       map f (Cons x xs) = Cons (fx) (map f xs) --      map f Nil = Nil 

STL contains such a transformation under the name 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; }; 

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

Expression Naming Operations


It can be seen that 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.

Starting with C ++ 11, you can use type and pattern aliases to set values ​​and functions through known expressions:

 using x = Not<One>::value; template <typename xs> using g = Cons<x, xs>; 

Template aliases allow you to get rid of the 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.

The program can just go into endless recursion.
Remember that 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    

At the same time, the template alias version provides that some 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   


Basically, pseudonyms of patterns are simply syntactic sugar, equivalent to patterns, without which it is quite possible to do.

Closures


If in ordinary C / C ++ the arguments and local variables die after the function ends, in functional languages ​​functions can return functions that depend on the arguments and local variables of the parent function. Accordingly, the parent function has already completed, but its local variables remain alive, “tied” to the child function. In practice, this is useful when the interface requires, for example, a unary function, and in its implementation there is some context on which it also depends.

For example, 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 

It would be possible to leave Cons , but g can be passed as a unary function into an already written map function, and as a binary one, Cons not!

However, normal C ++ does not suffer from the absence of closures.
To do this, use a functional object or lambda function. That is, if the transfer of additional parameters to the function via global variables violates the flexibility of the program, instead of a function, use an object, 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); }; 


When replacing functions (for example, int(int) ) with functional objects (for example, std::function<int(int)> ), the C ++ programmer gets a full-fledged closure.

At the template level, there is no need for the substitution of “function → object”, as it turns out. Closures are supported by the language itself:

 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> 

Unlike C ++ and Haskell, the 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 ).

Unlimited number of arguments or syntactic sugar for lists


Variation patterns allow you to record functions from lists. Again, in some cases it is more convenient, but without them you can also live in peace with 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; }; }; 

Iterative / recursive processing of the list even with the help of this is not so easy to implement. For example, to implement 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; }; 

It turned out that for a beautiful view of the record \ {x1, x2, x3 \}\ {x1, x2, x3 \} when declared, I had to suffer, packing, transferring and unpacking these sequences. 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.

Exit to the outside world


So far, we have considered only values ​​and pure functions (the result of which depends entirely on their arguments, and for the same arguments, the function will produce the same value). To print the result of the program, you need to go beyond the use of both pure functions and calculations at the compilation stage.

Upon completion of the calculations in the metaprogram, the resulting expression is interpreted as an entity from the real world and is either saved to a variable or displayed on the screen. You can use template classes for output. In the constructor or other methods imperative code is located. It can be either inside the meta-values ​​themselves (for example, 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" 

Similarly, you can display a list and anything. For example, we could implement AND, NOT, XOR, the binary adder, represent numbers as lists from One and Zero and build addition, multiplication, ...

Prior to C ++ 11 and the emergence of 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;  

Of course, this feature allowed us to write ideologically more correct code in C ++ at a lower cost, but it slightly shaken the ideology of the metalanguage of templates. In Haskell, for example, the function that consumed the poisonous cup of the imperative world remains poisoned by them forever and does not have the right to return ordinary values ​​belonging to the pure world. That is, the transition from functional purity to imperativeness can be made only in one direction.

Before 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.

In C ++ 11, you can calculate a certain type, create a value of this type, convert it in some way, and transfer the result type to an expression over types using 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; 

Going beyond the brackets breaks the purity:

 auto v = one() + two() + three(); // v     typedef decltype(v) x; 

Esoteric language translated into C ++ templates


The main problem of C ++ templates as compile-time FIAs is excessive verbosity. All these ::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.



In general, I decided to create my own language, which will be translated into C ++ templates. This can be done in different ways. You can use even the most ingenious transformations like those made by the JSFuck translator. But such an approach (a) will generate another unnecessary language, (b) divorced from C ++, (c) that still needs to be invented, and (d) spend energy on implementation. And to develop and implement a powerful enough and unnecessary FJ is troublesome and useless. Especially when in C ++ templates there are already constructions equivalent to functions, closures, pattern matching ... And it’s not sporty either.

I chose the path of the most appropriate. The code in my language should look simple, but remain ideologically similar to C ++. That is, the transformation should have been the most literal to translate my language into C ++. He was supposed to be a kilogram of syntactic sugar over the templates.

Let's rewrite the above pieces of code in the created language, thus having considered its features and their application in practice. We will move in the same order from the definition of the values ​​"zero" and "one", the function of negating the number, the constructors of the list to the definition of the function of negating the list, FVP map, etc.

Values ​​and Functions


To declare a value, the struct keyword is not required:

 One; Zero; 

The function declaration encloses the arguments and their types in curly brackets, leaving the body behind the "=" sign. The descriptions of specific cases are given after the description of the general case and differ in that the specific values ​​of the arguments do not indicate the type:

 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) 

In C ++, a template parameter can be a type ( 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.

Here I have a little retreated from the literal translation and introduced pseudonyms of types, which have no analogue (pseudonyms of types) in C ++. Via#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 

It can be considered #typeas an analogue #definein C, which sets textual transformations, which can also be carried out manually in a simple way.

List


I have not canceled a multiple return as a useful feature. This comes in handy when implementing the list:

 Nil; Cons(val x, val y) { head = x; tail = y; } 

Application of the function to the arguments, being translated into C ++, automatically opens ::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)'.

I have been thinking about this problem for a long time. On the one hand, ::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 

However, the meta-field ::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; 

Higher order functions


Recall that we declared the types of a unary function and a list and write a map:

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

Of course, instead of unaryand listit was possible to immediately indicate val -> val, valrespectively, but the record would have been longer and less visual.

Closures


Since closures are supported by the C ++ templates themselves, there is nothing unusual here:

 f(val x) = { g(val xs) = Cons(x, xs)'; } // : f(x)'.g(list)  map(f(x)'.g, list) 

But it is required to give the name (for example, g) of the returned function. The nameless function 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! }; }; 

In C ++, you cannot specialize a nested template, so instead of pattern-matching, you need to use some other mechanisms in the child meta-functions.

C ++ also does not allow reuse of template parameter names within a template. Since these names in my language refer to local metavariables and do not go beyond the template, I automated their renaming:

 f (val x) = g(Not(x)) { g (val x) = x; //    g (x1) = x1 // .. x   template f    x   template g } 

This transformation, it seems to me, did not add “unsportsmanship” (due to the possibility of a trivial manual replacement), but life was somewhat simplified.


At a certain stage, it turned out that the purely functional part is more or less successfully translated into C ++, and we must somehow be able to at least print the result. This part went beyond the framework of the interesting world of templates that I was interested in (because of which I thought less well in the end) and, more importantly, it was described quite well with ordinary C ++. In programs with compile-time computing on templates, regular C ++ without templates is responsible for entering the outside world . That is, I had to either make my language a superset of C ++, or create my own analogue of C ++. Of course, I chose the first option.

It only remained to enter the tags to insert the code in C ++ and rub their hands with satisfaction. But a logical problem arose: in the source code it is not mentioned anywhere that it is used for the application of meta-functions ::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>(); //  ? } 

There were few ideas about the uninteresting imperative part, and after scoring a few options, I decided to introduce (a) imperative blocks with the possibility of using the usual C ++ in them and (b) exporting values ​​from the pure functional world to them. A block 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.

As a demonstration of the work, we will 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; } } 

Namespaces


Since in my language in theory it would be possible to create libraries that would be used in ordinary C ++, I “threw” into it 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".

Lambda


I did not want to leave a functional language without lambda functions. Full support could not be implemented, but instead at least you can transfer its function to the other side of the = sign when the function is declared.

 f (val x) = y(x) { y(x) = g(x); } //  f = lambda (val x) -> y(x) { y(x) = g(x); } //  

Full support for lambdas is made difficult by the fact that in C ++ (a) you cannot create an anonymous class and (b) you cannot declare something equivalent to a template without unwinding the description until the type is equivalent to the type. Ie, to put it in mathematical terms,x=y You can write, but instead g=f will have to use g(x)=f(x) . Users of imperative programming have become accustomed to this state of affairs, but by the standards of functional programming it is rather cumbersome.

 template <typename x> struct f {}; //    f using g = f; //      //    ,   template <typename x> using g = f<x>; // g<x> - , f<x> -  

To implement the view records, you map(lambda(val x) -> y, xs)will have to modify the language and generate templates with temporary names.

As discussed above, 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.

Disadvantages and possible solutions


  1. No hiding of local variables.
    It is naively solved by inserting impure { private: }into the code or by elementary modification of the language.
  2. «typename».
    , . (, 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 ), , .
  3. : .
    .

    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 .
  4. Variadic patterns and integers are not taken into account as template parameters.
    To implement the required support in addition to 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.

Sample program


As an example, build a list {1,1,0}, take its negation in two ways and print all these values ​​in 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); } } 

The program will display the following:

 my list is 1, 1, 0, negated list is 0, 0, 1, negated list is also 0, 0, 1, 

Source code of the entire program
 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); } } 


Code after translation in C ++
 #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> (); } 


Translator


I wrote my translator in JavaScript (I love this language, I think it is easier for me to think). I used PEG.js as a parser generator.

When running, the translator (see the language page on GitHub) reads the file whose name is specified as a command line parameter, and outputs the resulting C ++ program text to stdout.

 node src/compile <> #  

As soon as the translator more or less earned and working programs were written, I posted all this stuff on GitHub and, like the mathematician from the anecdote, exclaiming “There is a solution!”, Almost lost interest in the development of the project. I tried to solve the above problems by alternating / indicating the type / Hungarian notation, but this required serious changes and repeated mental exertion. To think, having something ready and working, was laziness. Moreover, the principle of maximum compliance could be violated. Unnecessary wrappers and code to work with them would have killed the beauty of the straightness of the broadcast and would bring the program closer to exceeding the limit on nesting patterns.

Therefore, I stopped at what has been accomplished and will be glad if someone is interested and, perhaps, makes his contribution to the development of the language.

Source: https://habr.com/ru/post/337590/


All Articles