Сегодня мы рассмотрим одну из главных фич языка D, ради которой он и создавался — это продвинутое программирование на этапе компиляции. Некоторые могут припомнить как на C++ высчитывается факториал или, что посложнее, реализацию игры «Жизнь» и испугаться. Не стоит, шаблоны в D на порядок проще и мощнее аналога из C++, но все равно они требуют особого подхода в размышлениях, поэтому для акклиматизации сложность материала будет нарастать постепенно.
В D очень часто используется структурная типизация (аналог duck typing для статической типизации), например, чтобы проверить, поддерживает ли тип операции для его использования в операторе foreach:
static assert является вариантом классического assert, но который выполняется на этапе компиляции, и если в него передали выражение равное false, то он остановит компиляцию. А isInputRange объявлен как шаблон, который проверяет на наличие необходимых методов (можно детально и не вникать в следующий пример, все концепции рассмотрим дальше):
И на каждый свой compile-time интерфейс приходится делать по одному или несколько проверяющих шаблонов. Это немного утомляет, хотелось бы проверять на реализацию compile-time интерфейса следующим образом:
Вот функцию isExpose мы и будем реализовывать, попутно вникая в шаблонное программирование.
Для начала посчитаем факториал на шаблонах:
Ключевой момент в написании шаблонов — объявление константы или псевдонима с именем идентичным имени шаблона, это аналог return в обычных функциях. В данном шаблоне используется еще один внутренний, чтобы организовать хвостовую рекурсию (через аккумулятор).
В шаблоны можно передавать значения базовых типов, типы, списки типов, и, самое интересное, спикси выражений. Со значениями и типами все вполне понятно, такое есть во многих языках, но expression lists нужно пояснить:
С помощью expression lists в шаблоны можно передать что угодно, что можно вычислить на этапе компиляции. Итого далее мы будем работать со списками выражений практически повсеместно.
Начнем собирать необходимый шаблон isExpose:
Посмотрим на шаблон allSatisfy, он объявлен в стандартной библиотеке:
Он берет другой шаблон как первый параметр, который объявлен с ключевым словом alias, что обозначает «передача по имени». Без этого ключевого слова компилятор ругнулся бы о том, что шаблон F применен неправильно, а с alias получается аналог отложенного вычисления в функциональных языках. allSatisfy применяет F к каждому элементу T и проверяет, чтобы каждый раз шаблон F вернул true. Также может показаться странным способ разбиения списка агрументов в ветке else. Этот прием позволяет значительно оттянуть срабатывание защиты компилятора на бесконечную рекурсию, так как таким образом мы строим сбалансированное «дерево вызовов» вместо линейного откусывания по одному элементу от списка. Если все еще непонятно, вот схема:
Теперь нужно решить подзадачу проверки типа на наличие одного compile-time интерфейса. Для начала нам нужна способность явно создавать новые списки выражений, сделать это можно с помощью хитрого трюка:
Теперь воспользуемся помощью компилятора и узнаем список членов интерфейса (методы и поля):
__traits(allMembers, T) вернет список имент всех внутренних элементов типа T, подобронее о traits можно почитать тут. Теперь у нас есть имена методов и полей compile-time интерфейса, но этого недостаточно, имена элементов интерфейса и проверяемого типа могут совпадать, а их типы нет. Чтобы прикрепить типы элементов к их именам, организуем простой конвеер, но прежде нам понадобятся несколько вспомогательных шаблонов.
Шаблон, который повторяет свой аргумент n раз и возвращает этот список копий:
Шаблон, который применяет шаблон с двумя параметрами к списку:
Аналог fold или reduce для шаблонов:
При передаче нескольких List в любой шаблон, они автоматически раскрываются и склеиваются, что зачастую мешает реализовать операции над несколькими списками, поэтому объявим еще «жесткую» обертку над списком, которая раскрывается при явном вызове ее подшаблона:
В этом шаблоне мы не объявляли псевдоним с именем StrictList, что не позволяет этому шаблону автоматически заменяться на этот псевдоним при использовании. Также можно провести аналогию между подшаблонами и методами, при вызове StrictList!(T,U).expand нам вернут список из T и U.
Используя предыдущие шаблоны, реализуем последний вспомогательный шаблон. Он будет брать список списков(!) выражений и формировать новый список, в который элементы аргументов попадают по очереди (аналог функции zip в функциональных языках):
Вот когда у нас есть все необходимые кирпичики конвеера, можно нарисовать его схему:
Первая часть конвеера, реализуется так:
Для получения типа элемента интерфейса мы воспользовались примесью, которая присоединила тип интерфейса через точку к имени метода. И с помощью оператора typeof получаем тип выражения, сгенерированного в примеси. Далее проверяем, действительно ли пары тип-имя присутствуют в проверяемом классе/структуре:
Все кусочки пазла встали на свое место, итого полный код шаблона:
И примеры использования:
На основе мощного метапрограммирования можно писать удобные DSL или шаблоны, избавляющие от boilerplate кода. Прекрасным примером применения на практике этого подхода — compile-time генератор парсеров pegged.
Постановка задачи
В 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.
