Compile-time functional programming in D

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



    Formulation of the problem



    D often uses structural typing (similar to duck typing for static typing), for example, to check whether an operation type supports it 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 the classic assert , but which is performed at the compilation stage, and if an expression equal to false is passed to it, then it will stop compilation. And isInputRange is declared as a template that checks for the presence of the necessary methods (you can not go into the next example in detail, we will consider all concepts further):
    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 compile-time interface you have to do one or more checking patterns. 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.

    Warm up


    First, let's 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 to writing templates is declaring a constant or an alias with a name identical to the name of the template; this is an analogue of return in ordinary functions. This template uses one more internal to organize tail recursion (via battery).

    You can transfer values ​​of basic types, types, lists of types, and, most interestingly, spiks expressions to templates. With values ​​and types, everything is quite clear, 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); // передаем список выражений
    

    Using expression lists, you can pass anything you want to templates that can be calculated at the compilation stage. Total further we will 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 template as the first parameter that is declared with the alias keyword , which means "pass by name." Without this keyword, the compiler would swear that the F template was applied incorrectly, and with alias we get an analogue of deferred computation in functional languages. allSatisfy applies F to each element of T and checks that each time the pattern F returns true . It may also seem strange how to split the list of arguments in the else branch. This technique allows you to significantly delay the response of the compiler protection to infinite recursion, since in this way we build a balanced "call tree" instead of linearly biting one element from the list. If everything is still not clear, here is the diagram:



    Now you need to solve the sub-task of checking the type for the presence of one compile-time interface. To begin with, we need the ability to explicitly create new expression lists, this can be done with 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 , more about traits can be found 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 can match, but their types are not. To attach element types to their names, we will organize a simple pipeline, but first we need some auxiliary templates.

    A template that repeats its argument n times and returns this list of copies:
    the code
    template staticReplicate(TS...)
    {
        // is(T) вернет true, если T является любым типом
        static if(is(TS[0]))
            alias T = TS[0];
        else // иначе это значение
            enum T = TS[0];
        enum n = TS[1];
        static if(n > 0)
        {
            alias staticReplicate = List!(T, staticReplicate!(T, n-1));
        }
        else
        {
            alias staticReplicate = List!();
        }
    } 
    /// Example
    unittest
    {    
        template isBool(T)
        {
            enum isBool = is(T == bool);
        }
        static assert(allSatisfy!(isBool, staticReplicate!(bool, 2))); 
        static assert([staticReplicate!("42", 3)] == ["42", "42", "42"]);
    }
    



    A template that applies a template with two parameters to the list:
    the code
    template staticMap2(alias F, T...)
    {
        static assert(T.length % 2 == 0);
        static if (T.length < 2)
        {
            alias staticMap2 = List!();
        }
        else static if (T.length == 2)
        {
            alias staticMap2 = List!(F!(T[0], T[1]));
        }
        else
        {
            alias staticMap2 = List!(F!(T[0], T[1]), staticMap2!(F, T[2  .. $]));
        }
    }
    /// Example
    unittest
    {
        template Test(T...)
        {
            enum Test = T[0] && T[1];
        }
        static assert([staticMap2!(Test, true, true, true, false)] == [true, false]);
    }
    



    Analogue fold or reduce for templates:
    the code
    template staticFold(alias F, T...)
    {
        static if(T.length == 0) // invalid input
        {
            alias staticFold = List!(); 
        }
        else static if(T.length == 1)
        {
            static if(is(T[0]))
                alias staticFold = T[0];
            else
                enum staticFold = T[0];
        }
        else 
        {
            alias staticFold = staticFold!(F, F!(T[0], T[1]), T[2 .. $]);
        }
    }
    



    When transferring several List to any template, they are automatically opened and glued, which often interferes with the implementation of operations on several lists, so we will declare another “hard” wrapper over the list, which is opened when its subpattern is explicitly called:
    template StrictList(T...)
    {
         alias expand = T;
    }
    

    In this template, we did not declare an alias with the name StrictList , which does not allow this template to be automatically replaced with this alias when used. You can also draw an analogy between subpatterns and methods when calling StrictList! (T, U) .expand we will get a list from T and U.

    Using the previous templates, we implement the last auxiliary template. He will take a list of lists (!) Of expressions and form a new list, into which the elements of the arguments fall in turn (an analog of the zip function in functional languages):
    the code
    // Списки обернуты в StrictList, чтобы не слипались
    template staticRobin(SF...)
    {
        // Подшаблон для вычисления минимальной длины всех списков
        private template minimum(T...)
        {
            enum length = T[1].expand.length;
            enum minimum = T[0] > length ? length : T[0];
        }
        // Проходимся по всем спискам сверктой и сохраняем минимальную длину
        enum minLength = staticFold!(minimum, size_t.max, SF);
        // Инкапсулирующий подшаблон, в отличии от родительского, он уже знает о минимальной длине
        private template robin(ulong i)
        {
            // Берет из списка элемент с индексом i        
            private template takeByIndex(alias T)
            {
                // Таким образом проверяем, значение или тип хранится в элементе
                static if(is(T.expand[i]))
                    alias takeByIndex = T.expand[i];
                else
                    enum takeByIndex = T.expand[i];
            }
            static if(i >= minLength)
            {
                alias robin = List!();
            }
            else
            {
                // staticMap!(takeByIndex, SF) развернется в список  i-ых значений  соответствующих списков
                alias robin = List!(staticMap!(takeByIndex, SF), robin!(i+1));
            }
        }
        // Вызываем подшаблон
        alias staticRobin = robin!0; 
    }
    /// Example
    unittest
    {
        alias test = staticRobin!(StrictList!(int, int, int), StrictList!(float, float));
        static assert(is(test == List!(int, float, int, float)));
        alias test2 = staticRobin!(StrictList!(1, 2), StrictList!(3, 4, 5), StrictList!(6, 7));
        static assert([test2]== [1, 3, 6, 2, 4, 7]);
    }
    



    That's when we have all the necessary bricks of the conveyor, we can draw its diagram:


    The first part of the conveyor, 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 get the type of the interface element, we used an impurity that connected the interface type through a dot to the method name. And with the help of the typeof operator we get the type of expression generated in the admixture. Next, we check whether the type-name pairs are actually present in the tested class / structure:
            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 puzzle pieces fell into place, totaling the complete template code:
    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 usage examples:
        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 convenient DSLs or templates that eliminate boilerplate code. A great example of putting this approach into practice is the pegged compile-time parser generator .

    Also popular now: