Data Science/Machine Learning
0,0
рейтинг
28 января 2015 в 17:12

Разработка → Категории Клейсли перевод

Композиция логирования


Вы видели, как сделать категорию типов и чистых функций. Я также упомянул, что есть способ смоделировать побочные эффекты, или нечистые функции, в рамках теории категорий. Давайте рассмотрим пример: функции, которые логируют или записывают ход своего выполнения.

Что-то, что в императивном языке, скорее всего, будет реализовано посредством мутации некоторого глобального состояния, например:

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 так, чтобы они цепляли строку сообщения поверх их обычных возвращаемых значений.

image

Мы «обогатим» возвращаемые значения этих функций. Давайте сделаем это в общем виде путем определения шаблона 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);
}

Итак, вот рецепт для композиции двух морфизмов в этой новой категории, которую мы строим:
  1. Выполните обогащенную функцию, соответствующую первому морфизму
  2. Извлеките первый компонент пары-результата и передайте его в обогащенную функцию, соответствующую второму морфизму
  3. Соедините второй компонент (строку) первого результата и второй компонент (тоже строку) второго результата
  4. Верните новую пару, объединяющую первый компонент конечного результата с конкатенированной строкой.

Если мы хотим абстрагировать эту композицию в виде функции высшего порядка в 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, как обычно). Здесь мы расширили эту модель до несколько иной категории, категории, где морфизмы представлены обогащенными функциями, и их композиция делает больше, чем просто передать результат одной функции на вход другой. У нас есть на одну степень свободы больше: можно изменять саму композицию. Оказывается, что это именно эта степень свободы позволяет дать простую денотационную семантику программам, которые в императивных языках традиционно реализованы с использованием побочных эффектов.

Теория категорий для программистов: предисловие
Категория: суть композиции
Типы и функции
Категории, большие и малые
Категории Клейсли
Перевод: Bartosz Milewski
Max Strakhov @Monnoroch
карма
73,5
рейтинг 0,0
Data Science/Machine Learning
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (20)

  • 0
    Пример с логом не вполне корректный. С моей точки зрения, ведение лога не относится к (в терминах языка C++) наблюдаемому поведению программы — а потому нет разницы, один раз мы записали строку в лог или десять. То есть мы можем добавить к такой функции кэширование результата — и получить изменение в получившемся логе — но это будет не ошибкой.

    Надо придумать какой-нибудь другой пример, где бы побочный эффект был действительно важен.
    • +1
      Ваша точка зрения не совпадает с точкой зрения автора, логи — очень даже наблюдаемы.
      • 0
        Но тот, кто наблюдает логи, хочет понять, чем именно была занята программа в тот момент времени, к которому строчка лога относится — поэтому кэшировать строки лога попросту некорректно.
        • 0
          Конечно некорректно, поэтому это и называется побочным эффектом, откуда следует нечистота функции.
          • 0
            Если вы не заметили, ваша реализация закеширует строки лога вместе со значением, если применить мемоизацию к описанным у вас функциям.
            • –2
              Конечно, так и задумано. Но мемоизация в данном случае будет работать корректно: при одинаковых аргументах, будет одинаковый закешированный результат. Вся хитрость в композиции функций, именно она собирает лог.
              Если вы имеете ввиду, что при получении закешированного результата, писать в лог вызов функции неверно, то я с вами не соглашусь: семантически хит кеша и вызов реального кода эквивалентны.
              • +2
                Когда я вижу в логе строчку «запрос информации с сервера» — я хочу быть уверен, что информация и правда запрашивается, а не используется повторно ранее полученная. Если кэшировать строки лога рядом с значениями, такой уверенности у меня не будет.
                • –2
                  Нет никакой разницы, кеширование чистых функций не меняет семантику.
                  • +1
                    Вот только в данном случае надо, чтобы она изменилась.
                    • 0
                      Кто? Строка лога? Как ее изменить? Функция чистая, она обязана вернуть одно и тоже, независимо от мемоизации. Определение такое. В статье решена задача логирования работы композиции чистых функций. Если вам нужно возвращать разные вещи, то у вас побочные эффекты, и это совсем другая задача.
                      • 0
                        Функция возвращает некоторое значение — и это значение и правда не должно меняться. Побочный эффект (запись в лог) остальной программе не виден, а потому, с точки зрения остальной программы, функция обладает всеми свойствами чистой функции.

                        Побочный эффект виден пользователю программы — только вот пользователю совсем не нужна неизменность лога! Увидев, что в лог больше не пишутся повторяющиеся строчки, я не буду кричать, что поймал баг. А вместо этого обрадуюсь и скажу: «смотрите — повторяющихся строчек в логе больше нет. Значит, кеширование работает!».
                        • –1
                          В данном случае лог вполне виден программе. Еще раз, решена вполне конкретная задача. Просто, не та, что вы представили в голове.
                          Вы можете мысленно заменить лог на шахматную доску, а функцию на совершение хода. Один и тот же ход на одинаковых досках должен делать одинаковый побочный эффект — изменение состояния доски. Так вам понятней?
                          • +1
                            Я именно об этом и говорил в первом же комментарии. Статье нужен другой пример.
                            • 0
                              Статья, как Вы могли заметить, переводная, и поменять пример не получится (хотя можно сделать комментарий от переводчика).
                              Ну и под логом можно понимать разные вещи.
                              Например данный лог поможет понять, при вызове каких функций было получено значение.
                              Замечание на счёт сервера некорректно, поскольку запрос с сервера (и другие операции ввода/вывод которые важно видеть в логе) — не могут быть получены из чистых функций, так что похоже в контексте статьи дизайн и смысл лога вполне корректны, хотя и отличаются от привычного нам.
                              • 0
                                Замечание на счёт сервера некорректно, поскольку запрос с сервера (и другие операции ввода/вывод которые важно видеть в логе) — не могут быть получены из чистых функций
                                Зависит от того, подразумевается ли вообще в задаче возможность изменения этих данных в течении времени работы программы. Если на сервере хранится какой-нибудь большой справочник — то обращение к нему через «как бы чистые» функции — оправдано.

                                В любом случае, смысл моего комментария не поменяется, если запрос к серверу заменить на вычисление 1000000!.
    • 0
      В хаскеле (*) нет понятия «данный момент времени» для функций, так как нет грязных функций, все функции существуют вне времени в идеальном мире, и всегда возвращают одно и то же при одних и тех же параметрах. Даже print это не print, это «верни действие print», которое выполнится когда-нибудь потом, вне языка, так сказать.
      >Надо придумать какой-нибудь другой пример, где бы побочный эффект был действительно важен.
      Другой пример трудно будет написать на С++, если даже в таком минимальном виде приходится делать хаки из С++14.

      * Точнее, есть хак с unsafePerformIO, который используют для грязной отладки, но в нем-то как раз могут быть чудеса в виде выполнения программы задом наперед, например — никакой гарантии, в какой момент времени выполнится код под unsafePerformIO и выполнится ли нет. В С++ гарантии есть, поэтому «данный момент времени» обретает смысл.
      • 0
        Насчет времени не соглашусь. В хаскелле есть гарантии последовательности действий. Хаскелл транслируется в Core, а там есть строгие точки вычисления нормальной формы, что позволяет говорить, что вот тот код требует вот этого вычисленного значения. Так что, как таковой данный момент можно определить, как последнюю точку вычисления нормальной формы. Конечно, тогда время нелинейно, ведь иногда несколько точек одинаково хороши, но если говорить об IO, то там есть строгая последовательность.
        • 0
          В хаскеле не для всего есть гарантия последовательности действий.
          wiki.haskell.org/Evaluation_order_and_state_tokens
        • 0
          Core, насколько я знаю, особенность реализации GHC, в стандарте есть фраза «The order of evaluation of expressions in Haskell is constrained only by data dependencies». А отсюда уже следует в том числе и гарантированная последовательность в IO: данные цепляются друг за друга так, что IO будет выполняться последовательно. Мне надо было написать 'В С++ и Haskell IO гарантии есть, поэтому «данный момент времени» обретает смысл.', но если брать IO, тогда потеряет смысл чистая монада Writer, а автор явно руководствовался двумя вещами — максимально простой и реализуемый на С++ пример, и чисто функциональный при этом.
        • 0
          А что касается IO, то есть еще и Lazy IO (interact, getContents, hGetContents, readFile...), где уже нет гарантий, поскольку используется unsafeInterleaveIO, что дает непредсказуемые пути развития.

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