Композиция логирования
Вы видели, как сделать категорию типов и чистых функций. Я также упомянул, что есть способ смоделировать побочные эффекты, или нечистые функции, в рамках теории категорий. Давайте рассмотрим пример: функции, которые логируют или записывают ход своего выполнения.
Что-то, что в императивном языке, скорее всего, будет реализовано посредством мутации некоторого глобального состояния, например:
string logger;
bool negate(bool b) {
logger += "Not so! ";
return !b;
}
Вы знаете, что это не чистая функция, потому что ее версия с кешированием результатов будет не в состоянии записать в лог. Эта функция имеет побочные эффекты.
В современном программировании, мы стараемся держаться подальше от глобального изменяемого состояния, пока это возможно — как минимум, из-за сложностей с параллелизмом. И вы никогда не пишете подобный код в библиотеки.
К счастью для нас, можно сделать эту функцию чистой. Нужно просто передать лог в явном виде в функцию и из нее. Давайте сделаем это путем добавления строкового аргумента, и возвращение пары из основного результата и строки, содержащей обновленный журнал:
pair<bool, string> negate(bool b, string logger) {
return make_pair(!b, logger + "Not so! ");
}
Эта функция чистая, она не имеет никаких побочных эффектов, она возвращает одинаковую пару каждый раз, когда ее вызывают с одинаковыми аргументами, и ее результаты можно закешировать, если нужно. Однако, учитывая накопительный характер лога, вам придется закешировать все возможные истории, которые могут привести к данному вызову. Там будет отдельная закешированная запись для:
negate(true, "It was the best of times. ");
и
negate(true, "It was the worst of times. ");
и так далее.
Еще это не очень хороший интерфейс для библиотечной функции. Пользователи могут свободно игнорировать строку в возвращаемом значении, так что тут небольшая дополнительная сложность, но они вынуждены передавать строку в качестве входных данных, что может быть неудобно.
Есть ли способ сделать то же самое менее навязчиво? Есть ли способ разделить проблемы? В этом простом примере, основная цель функции negate — превратить один Boolean в другой. Логирование вторично. Конечно, сообщение, которое логируется, является специфичным для функции, но агрегирование сообщений в один непрерывный лог — отдельная задача. Мы все еще хотим, что функция возвращала строку, но мы хотели бы освободить ее от задачи создания лога. Вот компромиссное решение:
pair<bool, string> negate(bool b) {
return make_pair(!b, "Not so! ");
}
Идея в том, что лог будет агрегироваться между вызовами функции.
Чтобы увидеть, как это можно это сделать, давайте перейдем к немного более реалистичному примеру. У нас есть одна функция из строки в строку, которая превращает строчные буквы в верхний регистр:
string toUpper(string s) {
string result;
int (*toupperp)(int) = &toupper; // toupper is overloaded
transform(begin(s), end(s), back_inserter(result), toupperp);
return result;
}
и другая, которая разбивает строку на вектор строк, разбивая ее по пробелам:
vector<string> toWords(string s) {
return words(s);
}
Основная работа делается во вспомогательной функции words:
vector<string> words(string s) {
vector<string> result{""};
for (auto i = begin(s); i != end(s); ++i)
{
if (isspace(*i))
result.push_back("");
else
result.back() += *i;
}
return result;
}
Мы хотим изменить функции toUpper и toWords так, чтобы они цепляли строку сообщения поверх их обычных возвращаемых значений.
Мы «обогатим» возвращаемые значения этих функций. Давайте сделаем это в общем виде путем определения шаблона Writer, который инкапсулирует пару, первый компонент которой — значение произвольного типа А, а второй компонент — строка:
template<class A>
using Writer = pair<A, string>;
Вот обогащенные функции:
Writer<string> toUpper(string s) {
string result;
int (*toupperp)(int) = &toupper;
transform(begin(s), end(s), back_inserter(result), toupperp);
return make_pair(result, "toUpper ");
}
Writer<vector<string>> toWords(string s) {
return make_pair(words(s), "toWords ");
}
Мы хотим скомпоновать эти функции в другую обогащенную функцию, которая возводит строку в верхний регистр и разбивает ее на слова, при этом логируя эти действия. Вот как мы можем это сделать:
Writer<vector<string>> process(string s) {
auto p1 = toUpper(s);
auto p2 = toWords(p1.first);
return make_pair(p2.first, p1.second + p2.second);
}
Мы добились своей цели: объединение журнала больше не забота отдельных функций. Они производят свои собственные сообщения, которые затем, снаружи, собираются в целый лог.
А теперь представьте себе всю программу, написанную в этом стиле. Это кошмар повторяющегося и подверженного ошибкам кода. Но мы программисты. Мы знаем, как бороться с повторяющимся кодом: мы его абстрагируем! Это, однако, не ваши обычные абстракции: мы должны абстрагировать саму композицию функций. Но композиция — суть теории категорий, поэтому перед тем, как писать код дальше, давайте проанализируем эту проблему с категорной точки зрения.
Категория Writer
Идея обогащать типы возвращаемых значений функций для того, чтобы прицепить некоторую дополнительную функциональность оказывается очень полезной. Мы увидим еще много таких примеров. Отправной точкой является наша обычная категория типов и функций. Мы оставим типы как объекты, но переопределим морфизмы, как обогащенные функции.
Например, предположим, что мы хотим обогатить функцию isEven, которая преобразует int в bool. Мы превратим ее в морфизм, который представлен обогащенной функцией. Важно то, что этот морфизм до сих пор считается стрелкой между объектами int и bool, хотя украшенная функция возвращает пару:
pair<bool, string> isEven(int n) {
return make_pair(n % 2 == 0, "isEven ");
}
По законам категории, мы должны быть в состоянии скомпоновать этот морфизм с другим морфизмом, который идет из bool к чему угодно. В частности, мы должны быть в состоянии объединять его с нашей предыдущей функцией negate:
pair<bool, string> negate(bool b) {
return make_pair(!b, "Not so! ");
}
Очевидно, что мы не можем составить эти два морфизма так же, как мы составляем обычные функции, из-за несоответствия входа/выхода. Их композиция должна выглядеть примерно так:
pair<bool, string> isOdd(int n) {
pair<bool, string> p1 = isEven(n);
pair<bool, string> p2 = negate(p1.first);
return make_pair(p2.first, p1.second + p2.second);
}
Итак, вот рецепт для композиции двух морфизмов в этой новой категории, которую мы строим:
- Выполните обогащенную функцию, соответствующую первому морфизму
- Извлеките первый компонент пары-результата и передайте его в обогащенную функцию, соответствующую второму морфизму
- Соедините второй компонент (строку) первого результата и второй компонент (тоже строку) второго результата
- Верните новую пару, объединяющую первый компонент конечного результата с конкатенированной строкой.
Если мы хотим абстрагировать эту композицию в виде функции высшего порядка в C++, мы должны использовать шаблон, параметризованный тремя типами, соответствующими трем объектам в нашей категории. Следует взять две обогащенные функции, которые компонуемы в соответствии с нашими правилами, и вернуть третью обогащенную функцию:
template<class A, class B, class C>
function<Writer<C>(A)> compose(function<Writer<B>(A)> m1,
function<Writer<C>(B)> m2)
{
return [m1, m2](A x) {
auto p1 = m1(x);
auto p2 = m2(p1.first);
return make_pair(p2.first, p1.second + p2.second);
};
}
Теперь мы можем вернуться к нашему примеру и реализовать композицию toUpper и toWords с помощью этого шаблона:
Writer<vector<string>> process(string s) {
return compose<string, string, vector<string>>(toUpper, toWords)(s);
}
Тут все еще много шума с передачей типов в шаблон compose. Этого можно избежать, если пока у вас есть С++14-совместимый компилятор, который поддерживает обобщенные лямбда-функции с дедукцией возвращаемого типа (спасибо Эрику Ниблеру за код):
auto const compose = [](auto m1, auto m2) {
return [m1, m2](auto x) {
auto p1 = m1(x);
auto p2 = m2(p1.first);
return make_pair(p2.first, p1.second + p2.second);
};
};
В этом новом определении, реализация process упрощается:
Writer<vector<string>> process(string s){
return compose(toUpper, toWords)(s);
}
Но мы еще не закончили. Мы определили композицию в нашей новой категории, но какие единичные морфизмы? Это не наши регулярные функции тождества! Они должны быть морфизмами из типа A обратно в тип А, значит, они — обогащенные функции вида:
Writer<A> identity(A);
Они должны вести себя как единицы по отношению к композиции. Если вы посмотрите на наше определение композиции, вы увидите, что тождественный морфизм, должен передать свой аргумент без изменения, а только добавить пустую строку в лог:
template<class A>
Writer<A> identity(A x) {
return make_pair(x, "");
}
Можно легко убедиться, что категория, которую мы только что определили действительно законная категория. В частности, наша композиция тривиально ассоциативна. Если вы проследите, что происходит с первым компонентом каждой пары, вы увидите, что это просто обычная композиция функций, которая ассоциативна. Вторые компоненты соединяются, а конкатенация также ассоциативна.
Проницательный читатель может заметить, что можно легко обобщить эту конструкцию на любой моноид, а не только строки. Мы хотели бы использовать mappend внутри compose и mempty внутри identity (на месте + и ""). Действительно, нет никаких оснований ограничивать себя логированием только строк. Хороший писатель библиотек должен быть в состоянии определить необходимый минимум ограничений, которые необходимы библиотеке для работы — тут единственное требование библиотеки логирования заключается в том, что у лога есть моноидальные свойства.
Writer на Haskell
Та же конструкция на Haskell будет намного более лаконична, и компилятор нам поможет намного больше. Давайте начнем с определения типа Writer:
type Writer a = (a, String)
Здесь я просто определяю псевдоним типа, эквивалент typedef (или using) в C++. Тип Writer параметризирован переменной типа и эквивалентен паре a и String. Синтаксис для пар минимален: всего два имени в скобках, через запятую.
Наши морфизмы — функции из произвольного типа к определенному типу Writer:
a -> Writer b
Мы объявим композицию как забавный инфиксный оператор, который иногда называют «рыба»:
(>=>) :: (a -> Writer b) -> (b -> Writer c) -> (a -> Writer c)
Это функция от двух аргументов, каждый из которых сам по себе функция, и она возвращает функцию. Первый аргумент имеет тип (a -> Writer b), второй (b -> Writer c) и результат (a -> Writer c).
Вот определение этого инфиксного оператора — два аргумента m1 и m2, появляются по обе стороны от рыбного символа:
m1 >=> m2 = x ->
let (y, s1) = m1 x
(z, s2) = m2 y
in (z, s1 ++ s2)
В результате получается лямбда функция одного аргумента x. Лямбда записывается в виде обратной косой черты — можно думать о ней, как о греческой букве λ с ампутированной ногой.
Слово let позволяет объявить вспомогательные переменные. Здесь результат вызова m1 сматчен с парой переменных (у, s1), а результат вызова m2 с аргументом y из первого паттерна, будет сматчен с (z, s2).
В Haskell матчинг пар — обычная замена использованию геттеров, как мы это делали в С++. Помимо этого есть довольно простое соответствие между двумя реализациями.
Значение let выражения содержится после in: здесь это пара, чей первый компонент z, а второй компонент — объединение двух строк, s1 ++ s2.
Я также определю единичный морфизм для нашей категории, но по причинам, которые станут ясны значительно позже, я буду называть его return.
return :: a -> Writer a
return x = (x, "")
Для полноты давайте напишем Haskell версии, обогащенных функций upCase (прим. переводчика: имелось ввиду toUpper из C++ примера, но функция с таким именем уже есть в стандартном модуле Prelude) и toWords:
upCase :: String -> Writer String
upCase s = (map toUpper s, "upCase ")
toWords :: String -> Writer [String]
toWords s = (words s, "toWords ")
Функция map соответствует функции transform в C++. Она применяет функцию на символах toUpper к строке s. Вспомогательная функция words определена в стандартной библиотеке Prelude.
Наконец, композиция этих двух функций строится с помощью оператора рыбы:
process :: String -> Writer [String]
process = upCase >=> toWords
Категории Клейсли
Вы, наверное, догадались, что я не придумал эту категорию на лету. Это пример так называемой категории Клейсли — категории на основе монады. Мы пока не готовы обсуждать монады, но я хотел показать, что они могут делать. Для наших ограниченных целей, категория Клейсли имеет типы, как объекты. Морфизмы из типа A в тип B — это функции, которые идут от A к типу, полученному из B с помощью особого обогащения. Каждая категория Клейсли определяет свой собственный способ композиции таких морфизмов, а также тождественные морфизмы по отношению к этой композиции. (Позже мы увидим, что неточный термин «обогащение» соответствует понятию эндофунктора в категории.)
Конкретная монада, которую я использовал в качестве основы категории в этом посте называется writer и она используется для логирования или отслеживания выполнения функций. Она также является примером более общего механизма для встраивания эффектов в чистые вычисления. Вы видели ранее, что мы могли бы моделировать типы языка программирования и функции в категории множеств (без учета bottom, как обычно). Здесь мы расширили эту модель до несколько иной категории, категории, где морфизмы представлены обогащенными функциями, и их композиция делает больше, чем просто передать результат одной функции на вход другой. У нас есть на одну степень свободы больше: можно изменять саму композицию. Оказывается, что это именно эта степень свободы позволяет дать простую денотационную семантику программам, которые в императивных языках традиционно реализованы с использованием побочных эффектов.
Теория категорий для программистов: предисловие
Категория: суть композиции
Типы и функции
Категории, большие и малые
Категории Клейсли
Автор: Monnoroch
