Compile-time functional programming in D

Today we will look at one of the main features of the D language, for which it was created - it is advanced programming at the compilation stage. Some may recall how factorial is calculated in C ++ or, more difficultly, the implementation of the game “Life” and get scared. It is not necessary, the patterns in D are an order of magnitude simpler and more powerful than the analogue from C ++, but still they require a special approach in thinking, therefore, for acclimatization, the complexity of the material will increase gradually.

Formulation of the problem

')
In D, structural typing is very often used (analogous to duck typing for static typing), for example, to check if the type of operation supports it for use in the foreach statement :

import std.range; static assert(isInputRange!(uint[])); // true static assert(isInputRange!string); // true static assert(!isInputRange!void); // false 

static assert is a variant of classic assert , but which is executed at the compilation stage, and if an expression of false is passed to it, it will stop compilation. And isInputRange is declared as a template that checks for the presence of the necessary methods (you can go into the following example in detail and consider all the concepts below):

 template isInputRange(R) { enum bool isInputRange = is(typeof( (inout int = 0) { R r = void; // can define a range object if (r.empty) {} // can test for empty r.popFront(); // can invoke popFront() auto h = r.front; // can get the front of the range })); } 

And for each of your compile-time interface you have to do one or several testing templates. This is a bit tiring, I would like to check for the implementation of the compile-time interface as follows:

 //    struct CInterface { string method1(); bool method2(); } //  / struct A {} static assert(isExpose!(A, CInterface)); 

Here we will implement the isExpose function, simultaneously delving into template programming.

Warming up

To begin with, we will calculate the factorial on the templates:

  //       template factorial(uint n) { // - private template inner(ulong acc, uint n) { //       static  if static if(n == 0) enum inner = acc; //  else enum inner = inner!(acc * n, n-1 ); //    } //       1 enum factorial = inner!(1, n); } static assert(factorial!5 == 120); 

The key point in writing templates is the declaration of a constant or an alias with the name identical to the name of the template; this is an analogue of return in ordinary functions. This template uses another internal one to organize tail recursion (via battery).

In templates, you can transfer the values ​​of the basic types, types, lists of types, and, most interestingly, the expression expressions. Everything is quite clear with values ​​and types, this is in many languages, but expression lists need to be clarified:

  template test(T...) {} alias a1 = test!(ulong, float, double); //    alias a2 = test!("hi!", 23+42, [true, false], float); //    

With the help of expression lists, anything can be transferred to templates that can be calculated at the compilation stage. In total, we will continue to work with lists of expressions almost everywhere.

Character operations

Let's start collecting the required isExpose template:

  //    ,      template isExpose(Type, Interfaces...) { //     ,     1  private template isExposeSingle(Interface) { } //  ,     1     enum isExpose = allSatisfy!(isExposeSingle, Interfaces); } 

Let's look at the allSatisfy template, it is declared in the standard library:

 template allSatisfy(alias F, T...) { static if (T.length == 0) { enum allSatisfy = true; } else static if (T.length == 1) { enum allSatisfy = F!(T[0]); } else { enum allSatisfy = allSatisfy!(F, T[ 0 .. $/2]) && allSatisfy!(F, T[$/2 .. $ ]); //   // enum allSatisfy = F!(T[0]) && allSatisfy!(F, T[1 .. $ ]); } } 

It takes another pattern as the first parameter, which is declared with the alias keyword, which means “pass by name”. Without this keyword, the compiler would have cursed that the F pattern was applied incorrectly, and with alias , an analogue of deferred computation in functional languages ​​is obtained. allSatisfy applies F to each element of T and checks that the pattern F returns true every time. It may also seem strange way of splitting the list of argument in the else branch. This technique allows you to significantly delay the triggering of the compiler protection to endless recursion, since in this way we build a balanced “tree of calls” instead of a linear bite one element at a time from the list. If it is still not clear, here is the scheme:



Now you need to solve the type subtask for the presence of one compile-time interface. To begin with, we need the ability to explicitly create new lists of expressions, this can be done using a tricky trick:

 //    template List(T...) { //     alias List = T; } 

Now we will use the help of the compiler and find out the list of interface members (methods and fields):

  template getMembers(T) { //     List alias getMembers = List!(__traits(allMembers, T)); } 

__traits (allMembers, T) will return a list of all internal elements of type T , you can read more about traits here . Now we have the names of the methods and fields of the compile-time interface, but this is not enough, the names of the interface elements and the type being checked may be the same, but their types are not. To attach element types to their names, we will organize a simple pipeline, but first we will need several auxiliary templates.

A template that repeats its argument n times and returns this list of copies:


A template that applies a template with two parameters to the list:


Analogous to fold or reduce for templates:


When transferring several List to any template, they are automatically opened and glued together, which often makes it difficult to implement operations on several lists, so we will also declare a “hard” wrapper on the list, which is revealed when you explicitly call its sublab:

 template StrictList(T...) { alias expand = T; } 

In this template, we did not declare an alias named StrictList , which does not allow this template to be automatically replaced by this alias when used. You can also draw an analogy between the subpatterns and methods, when you call StrictList! (T, U) .expand we will be returned a list of T and U.

Using the previous patterns, we implement the last auxiliary pattern. It will take a list of lists (!) Of expressions and form a new list in which the elements of the arguments fall in order (analogous to the zip function in functional languages):


That's when we have all the necessary bricks of the assembly line, you can draw its scheme:


The first part of the conveyor is implemented as follows:

  alias intMembers = StrictList!(getMembers!Interface); alias intTypes = StrictList!(staticReplicate!(Interface, intMembers.expand.length)); alias pairs = staticMap2!(bindType, staticRobin!(intTypes, intMembers)); private template bindType(Base, string T) { alias bindType = List!(typeof(mixin(Base.stringof ~ "." ~ T)), T); } 

To obtain the type of an element of the interface, we used an admixture that added an interface type through a dot to the name of the method. And using the typeof operator, we get the type of expression generated in the impurity. Next, we check whether the type-name pairs are present in the class / structure being checked:

  template checkMember(MemberType, string MemberName) { static if(hasMember!(Type, MemberName)) { enum checkMember = is(typeof(mixin(Type.stringof ~ "." ~ MemberName)) == MemberType); } else { enum checkMember = false; } } enum isExposeSingle = allSatisfy2!(checkMember, pairs); 

All the pieces of the puzzle fell into place; the total template code was:

 template isExpose(Type, Interfaces...) { private template getMembers(T) { alias getMembers = List!(__traits(allMembers, T)); } private template isExposeSingle(Interface) { alias intMembers = StrictList!(getMembers!Interface); alias intTypes = StrictList!(staticReplicate!(Interface, intMembers.expand.length)); alias pairs = staticMap2!(bindType, staticRobin!(intTypes, intMembers)); private template bindType(Base, string T) { alias bindType = List!(typeof(mixin(Base.stringof ~ "." ~ T)), T); } template checkMember(MemberType, string MemberName) { static if(hasMember!(Type, MemberName)) { enum checkMember = is(typeof(mixin(Type.stringof ~ "." ~ MemberName)) == MemberType); } else { enum checkMember = false; } } enum isExposeSingle = allSatisfy2!(checkMember, pairs); } enum isExpose = allSatisfy!(isExposeSingle, Interfaces); } 

And examples of use:

  struct CITest1 { string a; string meth1(); bool meth2(); } struct CITest2 { bool delegate(string) meth3(); } struct CITest3 { bool meth1(); } struct Test1 { string meth1() {return "";} bool meth2() {return true;} string a; bool delegate(string) meth3() { return (string) {return true;}; }; } static assert(isExpose!(Test1, CITest1, CITest2)); static assert(!isExpose!(Test1, CITest3)); 

Conclusion

Based on powerful metaprogramming, you can write handy DSL or templates that eliminate boilerplate code. A perfect example of practical application of this approach is the compile-time parsers generator pegged .