compile-time abstract nonsense in D

[thedeemon]

Допустим, захотелось нам на обед монад. Монада - это troika из (эндо-)функтора и пары естественных преобразований, такие что.. Постойте, а что такое функтор? Это отображение объектов и стрелок категории в объекты и стрелки другой (или той же самой) категории, но не любое, а для которого выполнены определенные законы - сохранение identity морфизмов и сохранение композиций:
Identity: fmap id ≡ id
Composition: fmap (f ∘ g) ≡ fmap f ∘ fmap g
И по сути у нас в функторе два отображения - одно для объектов, второе для стрелок. В привычном нам применении этого дела в программировании первое отображение становится конструктором типов: всякому типу T оно сопоставляет тип F(T), например из Int делает List[Int]. Второе отображение становится функцией fmap с типом вроде (A -> B) -> (F(A) -> F(B)). Функциональные языки позволяют определить эти отображения, но вот проверку выполнения необходимых законов приходится делать в уме - компилятор этим не занимается.

А вот в D, с его умением выполнять код при компиляции, это сделать можно попытаться, хотя бы некоторое приближение.

Для примера опишем функтор "список", который внутри будет представлен массивом. Напомню, что передача статических параметров (например, типов), которая в иных языках заключается в угловые или квадратные скобки, в D заключается в !(), и если параметр один, то скобки можно опустить, оставив один восклицательный знак. Таким образом, List[Int] в D записывается как List!(int) или List!int.

struct List
{
    template tmap(T) { alias T[] tmap; }
    static tmap!T unit(T)(T x) { return [x]; }
    static tmap!B fmap(A,B, alias f)(tmap!A as)
    {
        auto n = as.length;
        auto bs = new B[n];
        foreach(i; 0..n) bs[i] = f(as[i]);
        return bs; 
    }
}

struct тут используется не для описания структуры данных, а для группировки нескольких определений.
tmap - это первое отображение функтора: оно маппит объекты категории в другие объекты, т.е. одни типы данных в другие, в данном случае из типа T делается массив T[]. Реализовано это как eponymous template, компилятор tmap!(T) будет внутри раскрывать в T[]. Нам пригодится также функция unit, которая из конкретного значения некоторого типа T делает конкретное значение типа tmap!(T), в данном случае из значения х делается массив [x] с единственным элементом. Второе отображение функтора - стрелки в стрелки - т.е. для нас функции в функции. По-хорошему, оно должно возвращать функцию, но создание замыканий в compile-time в D не работает, поэтому мы ее подвергнем каррингу:
(A -> B) -> (F(A) -> F(B)) эквивалентно
(A -> B) -> F(A) -> F(B) эквивалентно
((A -> B), F(A)) -> F(B)
Т.е. fmap будет брать функцию типа A -> B и значение типа F(A) (т.е. список/массив из А) и возвращать F(B) (список/массив из В). Внутри она создает массив той же длины, что и аргумент, и заполняет его, применяя поэлементно переданную функцию f к элементам входного массива.

Теперь самое интересное. Я хочу в коде удостовериться, что переданная структура действительно описывает функтор. D позволяет навешивать на типы-аргументы весьма сложные проверки. Вот так будет выглядеть использование:

void useFunctor(F)() if (isFunctor!(F))
{
    writeln(F.stringof ~ " is ok");
    // do something using F
}

Эта функция не скомпилируется, если предикат isFunctor!(F) не вернет истину. Как он устроен?

template isFunctor(F) {
    enum isFunctor = hasMember!(F, "tmap") && hasMember!(F, "fmap") && hasMember!(F, "unit")
                     && idCheck!(F) && compCheck!(F);
}

Переданная структура F обязана содержать нужные функции (отображения) и они должны удовлетворять двум условиям сохранения. hasMember - предикат из стандартной библиотеки, простой compile time reflection. А вот проверки выполнения законов опишем мы:

//Identity:    fmap id      ≡ id
template idCheck(F)
{ 
    T id(T)(T x) { return x; } 

    bool test(T)(T x) 
    {
        auto fx = F.unit!T(x);
        auto fid_fx = F.fmap!(T,T, id!T)(fx);
        return fid_fx == fx;
    }
    static if (test(1) && test("abc") && test(2.0) && test(false))
        enum idCheck = true;
    else 
        static assert(0, F.stringof ~ " identity check failed");
}

Мы не можем физически проверить, сохраняется ли identity у всех-всех объектов категории (то бишь типов), но можно протестировать выполнение на нескольких, и поскольку они выбраны случайно, надеяться, что этой проверки будет достаточно. Т.е. это не полноценное доказательство, это юнит-тестинг, от которого зависит успешность компиляции. Опишем id - identity морфизм, возвращающий аргумент без изменений. Функция test берет значение х некоторого типа T, получает его образ fx типа F(T) (для этого и нужна была функция unit), дальше строит образ стрелки id c помощью fmap и тут же применяет его к fx. Если функтор правильный и identity отображает в identity, то в результат должен быть равен исходному fx. Имея такую функцию, мы ее запускаем с несколькими разными типами. Если везде истина, то весь предикат idCheck возвращает true, в противном случае мы можем вернуть false, но я сделал иначе: сразу прерываю компиляцию с осмысленным сообщением.

Аналогично делаем тест сохранения композиции:

//Composition: fmap (f ∘ g) ≡ fmap f ∘ fmap g
template compCheck(F)
{
    bool g(int x) { return x < 10; }
    string f(bool x) { return to!string(x); }

    bool test(int x)
    {  
        auto fx = F.unit!int(x);
        auto left = F.fmap!(int, string, compose!(f,g))( fx );
        auto right = compose!( F.fmap!(bool, string, f), F.fmap!(int, bool, g) )(fx);
        return left == right;
    }

    enum compCheck = test(1) && test(11);
}

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

В таком виде все компилируется и работает успешно. Теперь, если в реализации fmap для списка например создавать массив чуть длиннее исходного:
auto bs = new B[n+1];
то получим при компиляции ошибку:


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

Comments

[thedeemon.livejournal.com]

Для студии есть плагин VisualD, я им пользуюсь.
Есть еще Mono-D для MonoDevelop, он покруче, как говорят.

Насчет где исключительно хорош - не знаю. Возможно, такой ниши и нет вовсе. Имхо, как замена перла/питона/руби/окамла для вспомогательных задач и небольших проектов (вроде обработчика логов и генератора картинок из недавнего поста) может пойти. Что-то очень большое или критичное я не буду советовать на нем делать, т.к. грабли все еще возможны, да и необходимость регулярно адаптировать codebase под изменения в языке в большом проекте будет минусом.