Compile-time функциональное программирование в D

    Сегодня мы рассмотрим одну из главных фич языка D, ради которой он и создавался — это продвинутое программирование на этапе компиляции. Некоторые могут припомнить как на C++ высчитывается факториал или, что посложнее, реализацию игры «Жизнь» и испугаться. Не стоит, шаблоны в D на порядок проще и мощнее аналога из C++, но все равно они требуют особого подхода в размышлениях, поэтому для акклиматизации сложность материала будет нарастать постепенно.



    Постановка задачи



    В D очень часто используется структурная типизация (аналог duck typing для статической типизации), например, чтобы проверить, поддерживает ли тип операции для его использования в операторе foreach:
        import std.range;
    
        static assert(isInputRange!(uint[])); // true
        static assert(isInputRange!string);  // true
        static assert(!isInputRange!void);   // false
    


    static assert является вариантом классического assert, но который выполняется на этапе компиляции, и если в него передали выражение равное false, то он остановит компиляцию. А isInputRange объявлен как шаблон, который проверяет на наличие необходимых методов (можно детально и не вникать в следующий пример, все концепции рассмотрим дальше):
    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
        }));
    }
    


    И на каждый свой compile-time интерфейс приходится делать по одному или несколько проверяющих шаблонов. Это немного утомляет, хотелось бы проверять на реализацию compile-time интерфейса следующим образом:
    // Наше описание интерфейса
    struct CInterface
    {
        string method1();
        bool method2();
    }
    
    // Проверяемая структура/класс
    struct A {}
    
    static assert(isExpose!(A, CInterface));
    


    Вот функцию isExpose мы и будем реализовывать, попутно вникая в шаблонное программирование.

    Разогрев


    Для начала посчитаем факториал на шаблонах:
        // Параметризиуем только целочисленными значениями без знака
        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);
    


    Ключевой момент в написании шаблонов — объявление константы или псевдонима с именем идентичным имени шаблона, это аналог return в обычных функциях. В данном шаблоне используется еще один внутренний, чтобы организовать хвостовую рекурсию (через аккумулятор).

    В шаблоны можно передавать значения базовых типов, типы, списки типов, и, самое интересное, спикси выражений. Со значениями и типами все вполне понятно, такое есть во многих языках, но expression lists нужно пояснить:
        template test(T...) {}
        
        alias a1 = test!(ulong, float, double); // передаем список типов
        alias a2 = test!("hi!", 23+42, [true, false], float); // передаем список выражений
    

    С помощью expression lists в шаблоны можно передать что угодно, что можно вычислить на этапе компиляции. Итого далее мы будем работать со списками выражений практически повсеместно.

    Операции над символами


    Начнем собирать необходимый шаблон isExpose:
        // Передаем в него тип, который проверяем и список интерфейсов
        template isExpose(Type, Interfaces...)
        {
            // Теперь неплохо бы иметь шаблон, который работает только для 1 интерфейса
            private template isExposeSingle(Interface)
            {
                
            }
            // А теперь, расширим наше решение для 1 интерфейса на их список
            enum isExpose = allSatisfy!(isExposeSingle, Interfaces);
        }
    


    Посмотрим на шаблон allSatisfy, он объявлен в стандартной библиотеке:
    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 ..  $ ]);
        }
    }
    

    Он берет другой шаблон как первый параметр, который объявлен с ключевым словом alias, что обозначает «передача по имени». Без этого ключевого слова компилятор ругнулся бы о том, что шаблон F применен неправильно, а с alias получается аналог отложенного вычисления в функциональных языках. allSatisfy применяет F к каждому элементу T и проверяет, чтобы каждый раз шаблон F вернул true. Также может показаться странным способ разбиения списка агрументов в ветке else. Этот прием позволяет значительно оттянуть срабатывание защиты компилятора на бесконечную рекурсию, так как таким образом мы строим сбалансированное «дерево вызовов» вместо линейного откусывания по одному элементу от списка. Если все еще непонятно, вот схема:



    Теперь нужно решить подзадачу проверки типа на наличие одного compile-time интерфейса. Для начала нам нужна способность явно создавать новые списки выражений, сделать это можно с помощью хитрого трюка:
    // Берем список выражений
    template List(T...)
    {
        // И просто возвращаем его
        alias List = T;
    }
    


    Теперь воспользуемся помощью компилятора и узнаем список членов интерфейса (методы и поля):
        template getMembers(T)
        {
            // Оборочиваем сырые данные в List
            alias getMembers = List!(__traits(allMembers, T));
        }
    


    __traits(allMembers, T) вернет список имент всех внутренних элементов типа T, подобронее о traits можно почитать тут. Теперь у нас есть имена методов и полей compile-time интерфейса, но этого недостаточно, имена элементов интерфейса и проверяемого типа могут совпадать, а их типы нет. Чтобы прикрепить типы элементов к их именам, организуем простой конвеер, но прежде нам понадобятся несколько вспомогательных шаблонов.

    Шаблон, который повторяет свой аргумент n раз и возвращает этот список копий:
    код
    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"]);
    }
    



    Шаблон, который применяет шаблон с двумя параметрами к списку:
    код
    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]);
    }
    



    Аналог fold или reduce для шаблонов:
    код
    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 .. $]);
        }
    }
    



    При передаче нескольких List в любой шаблон, они автоматически раскрываются и склеиваются, что зачастую мешает реализовать операции над несколькими списками, поэтому объявим еще «жесткую» обертку над списком, которая раскрывается при явном вызове ее подшаблона:
    template StrictList(T...)
    {
         alias expand = T;
    }
    

    В этом шаблоне мы не объявляли псевдоним с именем StrictList, что не позволяет этому шаблону автоматически заменяться на этот псевдоним при использовании. Также можно провести аналогию между подшаблонами и методами, при вызове StrictList!(T,U).expand нам вернут список из T и U.

    Используя предыдущие шаблоны, реализуем последний вспомогательный шаблон. Он будет брать список списков(!) выражений и формировать новый список, в который элементы аргументов попадают по очереди (аналог функции zip в функциональных языках):
    код
    // Списки обернуты в 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]);
    }
    



    Вот когда у нас есть все необходимые кирпичики конвеера, можно нарисовать его схему:


    Первая часть конвеера, реализуется так:
            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);
            }
    


    Для получения типа элемента интерфейса мы воспользовались примесью, которая присоединила тип интерфейса через точку к имени метода. И с помощью оператора typeof получаем тип выражения, сгенерированного в примеси. Далее проверяем, действительно ли пары тип-имя присутствуют в проверяемом классе/структуре:
            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); 
    


    Все кусочки пазла встали на свое место, итого полный код шаблона:
    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);
    }
    


    И примеры использования:
        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));
    


    Заключение


    На основе мощного метапрограммирования можно писать удобные DSL или шаблоны, избавляющие от boilerplate кода. Прекрасным примером применения на практике этого подхода — compile-time генератор парсеров pegged.
    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 29
    • +2
      И опять магия и трюки. В языке D конечно учтены многие ошибки дизайна C++, но метапрограммирование все так-же натянуто — впечатление, что его прикручивали уже после разработки языка.
      • 0
        Мне не нравится разделение типов и значений, но если их приравнивать, то получается система с зависимыми типами. Развитие в эту сторону мне кажется логичным.

        Также напрягают шероховатости при получении информации от компилятора, она просто нетипизирована, пока не обернута в список. Есть другой подход через вызов обычных функций во время компиляций, но он не может оперировать типами напрямую, только строками. Шаблонный подход более элегантный.

        Знаком еще с Template Haskell, там оперируешь с AST, это по мощности где-то посередине между примесями и шаблонами. Я бы его не назвал удобным, опасность чуть ниже примесей, а удобства не прибавляет.
        • +1
          Мне нравится подход языка Nemerle. Там есть «макросы» — специальные функции, начинающиеся с ключевого слова «macro». По сути это функции, выполняющиеся во время компиляции. В них можно обычным императивным способом выполнять код, который имеет доступ к API компилятора. Этим функциям можно передать объекты кода в виде AST-деревьев. С одной стороны, никаких строк — с другой стороны, никакой шаблонной магии.

          А что вы имеете в виду под «разделение типов и значений»? Я наверное не знаком с зависимыми типами, интересно что это такое.
          • +1
            А что вы имеете в виду под «разделение типов и значений»?

            Если аргумент значение, то используется enum, если тип, то alias. Осталось совсем немного, чтобы оперировать с типами как с значениями. На словах это будет все равно непонятно, вот пример из Idris:
            (++) : Vect n a -> Vect m a -> Vect (n + m) a
            (++) Nil ys = ys
            (++) (x :: xs) ys = x :: xs ++ ys
            

            Главная мысль — в сигнатуре вектора используется значение его длины, поэтому тип как бы «зависит» от своих значений, добавил новый элемент в вектор — тип изменился. Также видно, что даже в сигнатуре функции происходят некие вычисления. Возможно, это самый органичный способ вписать мету в язык. Увы я знаю о зависимых типах не так уж много, чтобы делать какие-то выводы.

            Там есть «макросы» — специальные функции, начинающиеся с ключевого слова «macro». По сути это функции, выполняющиеся во время компиляции. В них можно обычным императивным способом выполнять код, который имеет доступ к API компилятора. Этим функциям можно передать объекты кода в виде AST-деревьев. С одной стороны, никаких строк — с другой стороны, никакой шаблонной магии.

            Но это же получается boilerplate код, от D подхода при генерации через compile-time function evaluation не отличается (нужно заметить, что в D не полностью строковой подход, можно примешивать только целые expressions или объявления).
            • 0
              Макросы и шаблоны реально оперируют не типами и не значениями, а фрагментами AST. То что традиционно шаблоны в С++ в качестве аргументов получают исключительно типы и значения (почему-то только целочисленные) — это ИМХО недоразумение. У меня при работе с низкоуровневым программингом для микроконтроллеров не раз возникала необходимость сделать шаблон, в который можно было бы передать просто фрагмент кода (даже не функцию, а просто код в фигурных скобках). Приходилось делать костыли с сишными лексическими макросами, которые как вы понимаете, далеко не лучшее решение в программировании.

              Поэтому все эти alias и enum в D воспринимаются как унаследованные от С++ костыли. Конечно, должен быть некий механизм ограничения того, что мы передаем в шаблон — если там предусмотре тип, то это должен быть только тип а не что угодно. Но на самом верхнем уровне это именно нода синтаксического дерева.
              • 0
                Через alias параметры можно передавать символы, это, конечно, не целое AST, но уже его часть. Разработчики заняли довольно принципиальную позицию о том, что вместо операций над AST удобнее собирать строки и примешивать. Максимум, что можно ожидать в будущих версиях — расширение traits возможностью получать AST в виде списка-дерева из строк и работать с ним через compile-time функции.
                • +1
                  Я был неправ, AST макросы давно обсуждаются DIP50, но пока не реализованы (первое упомнинание как о «запланированной» фиче это 2010 г.).
                  • +1
                    Макросы обсуждались ещё на первом DConf в (страшно представить!) 2007 году, с тех пор в языке существует ключево слово «macro», которое на практике не используется. Со временем было принято решение что генерация кода через CTFE/mixin — решение более универсальное и простое для изучения новичками, хотя и существенно уступающее в гигиене для более сложных проектов. На данный момент введение AST макросов не рассматривается, DIP50 — просто мысли одно из активных участников сообщества.

                    В целом макросы вещь важная и нужна, но не столь однозначно превосходящая CTFE/mixin, как может показаться. Преобразование существующего кода — да, тут вопросов не возникает. Но поддержка произвольных строковых DSL куда проще реализуется простым лексическим разбором этих самых DSL.

                    Лично мне в текущей системе не хватает аргументов-выражений (по аналогии с тем, как alias это аргумент-символ), это решило бы множество задач, где пригодились бы макросы.
                    • 0
                      Нужно заметить, что сложные грамматики не запихнешь в compile-time, не хватает памяти. Распарсить D код с модификациями не получится без серьезной доработки эффективности CTFE.
                      • +1
                        Это дефект реализации CTFE, фундаментально тут никакой проблемы нет. Всего лишь исправление issues.dlang.org/show_bug.cgi?id=6498 уменьшит потребление памяти на порядок и больше.

                        Экспериментальный альтернативный front-end для D (https://github.com/deadalnix/SDC) использует LLVM JIT для CTFE и вообще не имеет таких проблем :)
                        • 0
                          Думал, что SDC заглох. Меня он привлекает в первую очередь как compiler as a library, можно было бы использовать D как встраиваемый скриптовый язык.
                          • +1
                            Нет, он очень даже жив. deadalnix выступал с презентацией на недавнем DConf: dconf.org/2014/talks/sechet.html + планируется в качестве одной из заявок на GSoC.
                            Видео с конференции правда придётся ждать долго, т.к. выступал он последним, а публикуют их по порядку :) Но архитектура намного более перспективная, чем жуткая каша в исходниках DMD.
      • –1
        Что люди не делают, только чтобы не познавать Haskell… Я когда-то был в эйфории от метапрограммирования на C++, но после Haskell это смешно и неудобно.
        • 0
          Можно пояснить, что именно вы имели ввиду? Я познал Haskell на среднем уровне и не помню там меты, кроме банальных вычислений на типах (Nat и вектора на них) и TH, который требует отдельного прогона компилятора, оперирует AST и с легкостью получает невалидный код.

          Тем более, почему бы императивным языкам не иметь элементы функционального подхода в мете, если это удобно и zero-cost для производительности? На Haskell нужно специально затачивать код под производительность, зачастую теряя в читаемости.
        • 0
          template Tuple(T...)
          {
              alias Tuple = T;
          }
          

          Пожалуйста, не надо использовать термин Tuple (кортеж) для обозначения списка шаблонных аргументов в D. Это очень специфическая для языка сущность, с огромным количеством особенностей и заморочек, почти ничего общего с кортежами из других языков не имеющая. На дальнейшие объяснения «почему так, а не эдак» приходится тратить очень много времени.

          Ссылка по теме: wiki.dlang.org/DIP54
          • 0
            Ни разу не видел эту рекомендацию. Называть их «TemplateArgumentList» — ужасное решение, весь код разбухнет раза в 3-4, а делать alias на тот же Tuple (или другое короткое имя, мб ETuple) — костыль.
            • +1
              Разбухание кода 1-5% разработчиков, которые активно использует метапрограммирование — терпимая цена за упрощение документации для всех остальных. Это я говорю как тот самый разработчик, чей код может разбухнуть :) В любом случае, имя Tuple уже используется стандартной библиотекой для std.typecons.Tuple, поэтому этот вариант вообще недопустим в обучающих материалах.

              Кстати рекомендуемый короткий alias — List и Pack соответственно.
              • 0
                Спасибо, List и Pack действительно лучше. Переведу код на них.

                P.S. Меня никогда не смущало наличие второго «Tuple» в std.typecons, т.к. все попытки его использовать разбивались о плохую поддержку IDE и проблемы с сериализацией, а еще он не работает с immutable.
                • 0
                  В std.typetuple уже есть private Pack и он не является по смыслу 'StrictTuple', итого dmd не позволяет мне использовать название Pack.
                  • 0
                    Да, DIP54 ещё не закончен (я работаю над этим по мере свободного времени), пока что в «живых» проектах приходится выкручитываться на свой вкус. Я изначально говорил только об учёбных материалах, вводящих в заблуждение.
                    • 0
                      Тогда пока вместо Pack буду использовать StrictList. С обучающими примерами сложнее: нельзя же пока использовать Pack, так как, если пользователь попробует скомпилировать пример, то сразу наткнется на эту проблему.
                    • 0
                      Ещё один мой DIP на эту же тему: wiki.dlang.org/DIP63
                      • 0
                        Стоящее предложение. Почему бы тогда не сделать alias с параметрами доступными не только в шаблонах?
                        • 0
                          Не понял вопроса :)
                          • 0
                            У меня устаревшие сведения, полгода назад не мог делать параметризированные alias:
                            /// Alias for vector of 2 elements
                            alias vec2(T) = Vector!(T, 2);
                            /// Alias for vector of 3 elements
                            alias vec3(T) = Vector!(T, 3);
                            
                            • +1
                              Да, этот синтаксис появился в прошлом релизе компилятора.

                              alias Name(T)  = T
                              

                              эквивалентно
                              template Name(T)
                              {
                                  alias Name = T;
                              }
                              

                              … просто более короткая форма. То же самое и для enum.
            • 0
              Простите за тупые вопросы но как мне сделать глобальный мутабельный обьект-структуру?

              struct Predmet{ x: int }

              в функции я пишу так:
              let predmet = Predmet{ x: 15};
              а как зделать вне функции чтобы глобально?
              • 0
                struct Predmet { int x; }
                
                Predmet globalPredmet = Predmet(15);
                
                unittest
                {
                    std.stdio.writeln(globalPredmet);
                }
                


                Или, если нужны сложные вычисления для создания структуры, то можно через конструктор модуля:
                struct Predmet { int x; }
                
                Predmet globalPredmet;
                
                static this()
                {
                    globalPredmet = Predmet(15);
                }
                
                unittest
                {
                    std.stdio.writeln(globalPredmet);
                }
                
                • 0
                  простите походу я ещё и пример не из того языка приложил :) спасибо… всё работает… буду теперь писать на D.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.