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®
{
    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 tuples потрібно пояснити:
 
template test(T...) {}
    
    alias a1 = test!(ulong, float, double); // передаем список типов
    alias a2 = test!("hi!", 23+42, [true, false], float); // передаем список выражений

За допомогою expression tuples в шаблони можна передати що завгодно, що можна обчислити на етапі компіляції. Разом далі ми будемо працювати зі списками виразів практично повсюдно.
 
 

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

Почнемо збирати необхідний шаблон 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 Tuple(T...)
{
    // И просто возвращаем его
    alias Tuple = T;
}

 
Тепер скористаємося допомогою компілятора і дізнаємося список членів інтерфейсу (методи і поля):
 
template getMembers(T)
    {
        // Оборочиваем сырые данные в Tuple
        alias getMembers = Tuple!(__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 = Tuple!(T, staticReplicate!(T, n-1));
    }
    else
    {
        alias staticReplicate = Tuple!();
    }
} 
/// 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 = Tuple!();
    }
    else static if (T.length == 2)
    {
        alias staticMap2 = Tuple!(F!(T[0], T[1]));
    }
    else
    {
        alias staticMap2 = Tuple!(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 = Tuple!(); 
    }
    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 .. $]);
    }
}

 
 
При передачі декількох Tuple в будь-який шаблон, вони автоматично розкриваються і склеюються, що часто заважає реалізувати операції над декількома списками, тому оголосимо ще «жорстку» обгортку над списком, яка розкривається при явному виклику її подшаблона:
 
template StrictTuple(T...)
{
    template expand()
    {
        alias expand = T;
    }
}

У цьому шаблоні ми не оголошували псевдонім з ім'ям StrictTuple , що не дозволяє цим шаблоном автоматично замінюватися на цей псевдонім при використанні. Також можна провести аналогію між подшаблонамі і методами, при виклику StrictTuple! (T, U). Expand! () нам повернуть список з T і U.
 
Використовуючи попередні шаблони, реалізуємо останній допоміжний шаблон. Він буде брати список списків (!) Виразів і формувати новий список, в який елементи аргументів потрапляють по черзі (аналог функції zip у функціональних мовах):
 код
// Списки обернуты в StrictTuple, чтобы не слипались
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 = Tuple!();
        }
        else
        {
            // staticMap!(takeByIndex, SF) развернется в список  i-ых значений  соответствующих списков
            alias robin = Tuple!(staticMap!(takeByIndex, SF), robin!(i+1));
        }
    }
    
    // Вызываем подшаблон
    alias staticRobin = robin!0; 
}
/// Example
unittest
{
    alias test = staticRobin!(StrictTuple!(int, int, int), StrictTuple!(float, float));
    static assert(is(test == Tuple!(int, float, int, float)));
    
    alias test2 = staticRobin!(StrictTuple!(1, 2), StrictTuple!(3, 4, 5), StrictTuple!(6, 7));
    static assert([test2]== [1, 3, 6, 2, 4, 7]);
}

 
 
Ось коли у нас є всі необхідні цеглинки конвеера, можна намалювати його схему:
 
 
Перша частина конвеера, реалізується так:
 
alias intMembers = StrictTuple!(getMembers!Interface); 
        alias intTypes = StrictTuple!(staticReplicate!(Interface, intMembers.expand!().length));
        alias pairs = staticMap2!(bindType, staticRobin!(intTypes, intMembers));

        private template bindType(Base, string T)
        {
            alias bindType = Tuple!(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 = Tuple!(__traits(allMembers, T));
    }
    
    private template isExposeSingle(Interface)
    {
        alias intMembers = StrictTuple!(getMembers!Interface); 
        alias intTypes = StrictTuple!(staticReplicate!(Interface, intMembers.expand!().length));
        alias pairs = staticMap2!(bindType, staticRobin!(intTypes, intMembers));
                
        private template bindType(Base, string T)
        {
            alias bindType = Tuple!(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 .
    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.