Монады и срезы в Erlang'е: Erlando

Перевод статьи Can you hear the drums, Erlando?

Большинство из разработчиков в RabbitMQ HQ достаточно плотно работали с другими функциональными языками помимо Erlang'а, такими как Haskell, Scheme, Lisp, OCaml и т.п. И хотя в Erlang'е есть много хорошего (например его VM/эмулятор), рано или поздно нам всем начинает недоставать некоторых возможностей их других языков. Прежде чем вернуться в RabbitMQ я несколько лет работал с Haskell'ем. И в моем случае мне недостает многих возможностей: ленивость, классы типов, дополнительные infix-операторы, возможность указывать приоритет функций, меньшее количество скобок, частичное применение, и do-нотация. Это внушительный список, и понадобится немало времени, чтобы их всех реализовать. Но, для начала, мы реализовали две.

Введение

Erlando — это набор синтаксических расширений для Erlang'а. На данный момент этот набор содержит два расширения, каждое из которых представляет собой parse transform.

• Cut: Вводит поддержку срезов (cuts) в Erlang. Срезы вдохновлены аналогичной функциональностью в Scheme. Срезы являются легковесной абстракцией, чем-то похожей на частичное применение (или карринг).
• Do: Вводит поддержку do-нотаций и монад в Erlang. Эта функциональность вдохновлена Haskell'ем, а монады и соответствующая библиотека являются практически механическим переложением кода из GHC-библиотек Haskell'а

Использование

Для того, чтобы использовать любую из этих возможностей, необходимо добавить соответствующую опцию -compile. Например:

-module(test).
-compile({parse_transform, cut}).
-compile({parse_transform, do}).
...

При компиляции надо убедиться, что erlc может найти cut.beam и/или do.beam. Для этого достаточно передать путь к эти файлам с помощью аргумента -pa или -pz. Например:

erlc -Wall +debug_info -I ./include -pa ebin -o ebin src/cut.erl
erlc -Wall +debug_info -I ./include -pa ebin -o ebin src/do.erl
erlc -Wall +debug_info -I ./include -pa test/ebin -pa ./ebin -o test/ebin test/src/test.erl

Примечание: если вы используете QLC, будьте внимательны к порядку parse transforms. Для корректной работы необходимо, чтобы опция -compile({parse_transform, cut}). шла перед  -include_lib("stdlib/include/qlc.hrl").

Cut

Мотивация

Мотивацией для создания cut послужила частота, с которой простые абстракции (с точки зрения лямбда-исчисления) используются в Erlang'е, а также относительно «шумный» способ задания анонимных функций. Например, достаточно часто встречается примерно такой код:

with_resource(Resource, Fun) ->
    case lookup_resource(Resource) of
        {ok, R}          -> Fun(R);
        {error, _} = Err -> Err
    end.

my_fun(A, B, C) ->
    with_resource(A, fun (Resource) ->
                         my_resource_modification(Resource, B, C)
                     end).

То есть, функция создается для захвата переменной из окружающей области видимости, но оставить «дыры» для передачи дополнительных аргументов. Используя срез, можно переписать my_fun можно переписать следующим образом:

my_fun(A, B, C) ->
    with_resource(A, my_resource_modification(_, B, C)).

Определение

При нормальном использовании переменная _ может появляться только в шаблонах сопоставления с образцом — там, где происходит собственно сопоставление: в присвоении, в case, в заголовках функций. Например:

{_, bar} = {foo, bar}.

Cut использует _ в выражениях, чтобы указать, где должна произойти абстракция. Абстракция из среза всегда производится на ближайшем окружающем выражении. Например

list_to_binary([1, 2, math:pow(2, _)]).

создаст выражение

list_to_binary([1, 2, fun (X) -> math:pow(2, X) end]).

а не

fun (X) -> list_to_binary([1, 2, math:pow(2, X)]) end.

Можно использовать несколько срезов в выражении. Аргументы к создаваемой абстракции будут идти в порядке появления _ в выражении. Например:

assert_sum_3(X, Y, Z, Sum) when X + Y + Z == Sum -> ok;
assert_sum_3(_X, _Y, _Z, _Sum) -> {error, not_sum}.

test() ->
    Equals12 = assert_sum_3(_, _, _, 12),
    ok = Equals12(9, 2, 1).

Также возможно делать срезы срезов, так как создаваемая в результате среза абстракция является обыкновенной анонимной функцией и тоже может быть «срезана»:

test() ->
    Equals12 = assert_sum_3(_, _, _, 12),
    Equals5 = Equals12(_, _, 7),
    ok = Equals5(2, 3).

Обратите внимание, что из-за того, что срез создает простую функцию, аргументы вычисляются до того, как они передаются в cut. Например:

f1(_, _) -> io:format("in f1~n").

test() ->
    F = f1(io:format("test line 1~n"), _),
    F(io:format("test line 2~n")).

Результат будет

test line 2
test line 1
in f1

Это происходит потому, что срез создает fun (X) -> f1(io:format("test line 1~n"), X) end. Таким образом, понятно, что вычисление X должно произойти прежде, чем будет вызвана функция. Конечно, никому и в голову не прийдет создавать побочные эффекты в аргументах к функции, так что такой вызов не должен создавать никаких проблем!

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

Кортежи

F = {_, 3},
{a, 3} = F(a).

Списки

dbl_cons(List) -> [_, _ | List].

test() ->
    F = dbl_cons([33]),
    [7, 8, 33] = F(7, 8).

Обратите внимание, что если вы вкладываете еще один список как хвост списка (list tail) в Erlang'е, это все равно обрабатывается, как одно выражение. Например:

A = [a, b | [c, d | [e]]]

абсолютно идентично (начиная от парсера Erlang'а и далее) следующему:

A = [a, b, c, d, e]

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

F = [1, _, _, [_], 5 | [6, [_] | [_]]],
%% Это идентично следующему:
%%  [1, _, _, [_], 5, 6, [_], _]
[1, 2, 3, G, 5, 6, H, 8] = F(2, 3, 8),
[4] = G(4),
[7] = H(7).

Однако, стоит четко различать разницу между «,» и «|»: хвост списка определяется только элементами, следующими за «|». За «,» просто следуют очередные элементы списка.

F = [_, [_]],
%% Это **не** то же самое, что и [_, _] или его синоним: [_ | [_]]
[a, G] = F(a),
[b] = G(b).

Records/Записи

-record(vector, { x, y, z }).

test() ->
    GetZ = _#vector.z,
    7 = GetZ(#vector { z = 7 }),
    SetX = _#vector{x = _},
    V = #vector{ x = 5, y = 4 } = SetX(#vector{ y = 4 }, 5).

Case

F = case _ of
        N when is_integer(N) -> N + N;
        N                    -> N
    end,
10 = F(5),
ok = F(ok).

В файле test_cut.erl можно увидеть эти и другие примеры, также показывающие использование срезов в list comprehensions и при создании binary.

Обратите внимание, что срезы нельзя использовать там, где результат среза может быть использован только для взаимодействия с областью выполнения (evaluation scope). Например:

F = begin _, _, _ end.

Такое использование запрещено, потому что аргументы к функции F должны быть вычислены до выполнения ее тела, что не даст никакого результата, так как они к этому моменту уже полностью вычислены.

Do

Do позволяет использовать do-нотацию в стиле Haskell'а, что делает возможным и лешким использование монад и монадических преобразований (monad transformers). Без do-нотации использование монад выглядит, как нагромождение букв и строчек.

Неизбежное введение в монады

Механизм запятой

Представляем вам короткое техническое введение в монады. Оно отличается от других введений в монады для Haskell'а. Дело в том, что в большинстве введений монады описываются как способ задать последовательность выполнения операций, что в Haskell'е, как ленивом языке, может быть сложно. Erlang не является ленивым языком, но мощные абстракции, возникающие при использовании монад, все равно являются достаточно ценными. Несмотря на то, что это введение достаточно коротко и технично, можно увидеть, какие расширенные абстракции становятся доступны.

Возьмем для примера следующие три строчки кода:

A = foo(),
B = bar(A, dog),
ok.

Это три простых выражения, выполняемых последовательно. Монады дают вам возможность контролировать то, то происходит между выражениями. В Erlang'е это «программная запятая» (programmatic comma).

Если бы вам захотелось реализовать программную запятую, как бы она выглядела? Скорее всего, вы бы начали с такого кода::

A = foo(),
comma(),
B = bar(A, dog),
comma(),
ok.

К сожалению, такой подход недостаточен. Нет никакого способа предотвратить выполнение последующего выражения, кроме как выкинуть ошибку в comma/0. Более того, скорее всего нам бы хотелось, чтобы comma/0 работала с какими-то переменными, которые находятся в текущей области видимости. Здесь же это невозможно. Значит, нам необходимо расширить функцию comma/0 так, чтобы она принимала результат предыдущей функции и могла выбирать, вызывать следующую функцию, или нет:

comma(foo(),
fun (A) -> comma(bar(A, dog),
fun (B) -> ok end)).

Таким образом, функция comma/2 принимает результат предыдущего выражения и контролирует, как они передаются следующему выражению и передаются ли они вообще.

Такое определение функции comma/2 дает нам определение монадической функции >>=/2.

При использовании функции comma/2 код становится сложен для понимания (в частности, из-за того, что Erlang не позволяет определять infix-функции). Поэтому нам необходим специальный синтаксис. В Haskell'е есть do-нотация, которую мы в какой-то степени эмулируем специально для использования монад. Таким образом, используя Do, можно записать:

do([Monad ||
    A <- foo(),
    B <- bar(A, dog),
    ok]).

что достаточно просто и прямолинейно, но в реальности трансформируется в:

Monad:'>>='(foo(),
            fun (A) -> Monad:'>>='(bar(A, dog),
                                   fun (B) -> ok end)).

Стремления сделать эту трансформацию более читаемой, чем comma/2, нет. Но должно быть ясно, что у функции Monad:'>>='/2 теперь есть полный контроль над тем, что происходит: будет ли вызываться функция с правой стороны? Если да, то с каким значением?

Множество различных монад

Так как теперь у нас есть относительно приятный способ для монад, что мы можем с ними сделать?

Более того, в коде

do([Monad ||
    A <- foo(),
    B <- bar(A, dog),
    ok]).

какие значения может принимать Monad?

Ответ на первый вопрос: практически все. Ответ на второй вопрос: имя любого модуля, который реализует поведение монад.

Выше мы рассмотрели один из трех монадических операторов, >>=/2. Два других:

• return/1. «Поднимает»(lifts) значение из монады. Совсем скоро мы рассмотрим примеры, использующие его
• fail/1. Принимает терм, описывающий возникшую ошибку и информирует текущую монаду о произошедшей ошибке

Обратите внимание, что внутри do-нотации любой вызов функции с именем return или fail автоматически переписывается в вызов функции return или fail текущей монады.

Те, кто знаком с Haskell'ем, ожидают увидеть и четвертый оператор, >>/2. Интересно, что, оказывается, нельзя реализовать >>/2 в языке со строгим порядком выполнения, если только не реализовать все типы монад на функциях. Дело в том, что в строгом языке аргументы функции вычисляются до того, как вызывается сама функция. В операторе >>=/2 второй аргумент сводится к функции до собственно вызова >>=/2. Но, так как второй аргумент в >>/2 не является функцией, в строго языке он будет полностью вычислен до собственно вызова >>/2. Это создает проблемы, так как предполагается, что >>/2 должен сам контролировать, будут вычисляться последующие выражения или нет. Эту проблему можно решить единственным способом: определить базой монадических типов функцию, что в итоге привело бы к тому, что вторым аргументом в >>=/2 стала бы функция от функции от результата! Как бы то ни было, есть требование, что '>>'(A,B) должно вести себя идентично '>>='(A, fun (_) -> B end). Именно так мы и делаем: как только мы встречаем do([Monad || A, B ]), мы переписываем это в '>>='(A, fun (_) -> B end), а не в '>>'(A, B). В результате необходимость в операторе >>/2 отпадает.

Простейшей возможной монадой является монада Identity:

-module(identity_m).
-behaviour(monad).
-export(['>>='/2, return/1, fail/1]).

‘>>=’(X, Fun) -> Fun(X).
return(X)     -> X.
fail(X)       -> throw({error, X}).

Эта монада позволяет нашей программной запятой действовать, как обыкновенная запятая в Erlang'е. Связывающий оператор >>=/2 не рассматривает передаваемые ему значения, и всегда вызывает следующее выражение.

Что же можно сделать, если мы будем рассматривать передаваемые значения? Одна из возможностей — реализация монады Maybe.

-module(maybe_m).
-behaviour(monad).
-export(['>>='/2, return/1, fail/1]).

‘>>=’({just, X}, Fun) -> Fun(X);
‘>>=’(nothing,  _Fun) -> nothing.

return(X) -> {just, X}.
fail(_X)  -> nothing.

Таким образом, если результатом предыдущего выражения является nothing, тогда следующее выражение не выполняется. Это значит, что можно написать опрятный код, который моментально останавливает выполнение как только сталкивается с ошибкой.

if_safe_div_zero(X, Y, Fun) ->
    do([maybe_m ||
        Result <- case Y == 0 of
                      true  -> fail("Cannot divide by zero");
                      false -> return(X / Y)
                  end,
        return(Fun(Result))]).

Если Y равно 0, то Fun не будет вызвана, и результатом вызова функции if_safe_div_zero будет nothing. Если Y не равно 0, то результатом вызова if_safe_div_zero будет {just, Fun(X / Y)}.

Как видно, внутри блока do нигде не упоминаются nothing или just — они спрятаны за абстракцией монады Maybe. Таким образом можно заменить используемую монаду на другую без необходимости менять или переписывать код.

Одно из мест, где монада Maybe используется — это код со множеством вложенных case-ов для определения возвращаемых ошибок. Например:

write_file(Path, Data, Modes) ->
    Modes1 = [binary, write | (Modes -- [binary, write])],
    case make_binary(Data) of
        Bin when is_binary(Bin) ->
            case file:open(Path, Modes1) of
                {ok, Hdl} ->
                    case file:write(Hdl, Bin) of
                        ok ->
                            case file:sync(Hdl) of
                                ok ->
                                    file:close(Hdl);
                                {error, _} = E ->
                                    file:close(Hdl),
                                    E
                            end;
                        {error, _} = E ->
                            file:close(Hdl),
                            E
                    end;
                {error, _} = E -> E
            end;
        {error, _} = E -> E
    end.

make_binary(Bin) when is_binary(Bin) ->
    Bin;
make_binary(List) ->
    try
        iolist_to_binary(List)
    catch error:Reason ->
            {error, Reason}
    end.

Этот код можно трансформировать в гораздо более короткий:

write_file(Path, Data, Modes) ->
    Modes1 = [binary, write | (Modes -- [binary, write])],
    do([error_m ||
        Bin <- make_binary(Data),
        {ok, Hdl} <- file:open(Path, Modes1),
        {ok, Result} <- return(do([error_m ||
                                   ok <- file:write(Hdl, Bin),
                                   file:sync(Hdl)])),
        file:close(Hdl),
        Result]).

Обратите внимание, что, как и в случае с кодом, не использующем монады, в случае, если мы открываем файл, то мы его закрываем, даже если произошла ошибка в одной из последующих операций. Мы можем так сделать, обернув вложенный блок do в вызов return/1. Тогда, если внутренний блок do сгенерирует ошибку, она «поднимается» (lifted) в обыкновенное значение во внешнем блоку do. Таким образом, исполнение последующих вызовов все равно происходит и происходит вызов file:close/1.

В этом коде мы используем монаду Error, которая очень похожа на монаду Maybe, но продолжает традицию Erlang'а отмечать ошибки кортежами {error, Tuple}:

-module(error_m).
-behaviour(monad).
-export(['>>='/2, return/1, fail/1]).

‘>>=’({error, _Err} = Error, _Fun) -> Error;
‘>>=’(Result,                 Fun) -> Fun(Result).

return(X) -> {ok,    X}.
fail(X)   -> {error, X}.

Монадные трансформеры

Монады могут быть вложены друг в друга с помощью блоков do внутри других блоков do. Монады так же могут быть параметризованы путем определения монады как трансформации другой, внутренней монады.. State Transform (трансформер состояния) — это часто используемый трансформер, который очень удобен в Erlang'е. Так как значения в Erlang'е могут присваиваться всего один раз, нередки ситуации, когда в коде появляется множество переменных с последовательно возрастающими порядковыми номерами:

State1 = init(Dimensions),
State2 = plant_seeds(SeedCount, State1),
{DidFlood, State3} = pour_on_water(WaterVolume, State2),
State4 = apply_sunlight(Time, State3),
{DidFlood2, State5} = pour_on_water(WaterVolume, State4),
{Crop, State6} = harvest(State5),
...

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

Наша реализация монадных трансформеров (вроде State) использует «скрытую возможность» Erlang'а под названием «параметризованые модули». Они описаны в Parameterized Modules in Erlang.

Трансформер State можно применить к любой монаде. Если мы применим его к монаде Identity, мы получим искомое. Ключевая дополнительная функциональность трансформера State позволяет нам получить, установить (или просто изменить) состояние из внутренней монады. Если мы используем одновременно Do и Cut, то мы можем написать, например:

StateT = state_t:new(identity_m),
SM = StateT:modify(_),
SMR = StateT:modify_and_return(_),
StateT:exec(
  do([StateT ||

      StateT:put(init(Dimensions)),
      SM(plant_seeds(SeedCount, _)),
      DidFlood <- SMR(pour_on_water(WaterVolume, _)),
      SM(apply_sunlight(Time, _)),
      DidFlood2 <- SMR(pour_on_water(WaterVolume, _)),
      Crop <- SMR(harvest(_)),
      ...

      ]), undefined).

Код начинается с того, что мы создаем трансформер State поверх монады Identity.

Синтаксис, что вы видите — это синтаксис для инстанциирования праметризованых модулей. StateT — переменная, содержащая ссылку на экземпляру модуля, в то раз — на монаду.

Мы создаем два сокращения для функций, которые либо изменяют состояние либо изменяют состояние и возвращают результат. Несмотря то, что нам надо следить за тем, что и куда отсылается, мы достигли желаемого результата: мы избавились от переменных, хранящих состояние, которые надо было переименовывать при любом изменении кода. Для передачи состояния мы используем срезы в аргументах функций. Нам так же надо следовать протоколу в том, что если функция возвращает и результат и измененное состояние, то они должны возвращаться в виде {Result, State}. Все остальное выполняет трансформация State.

Расширяя горизонты

В модуле monad реализованы некоторые стандартные функции вроде join/2 и sequence/2. Мы таке реализовали monad_plus, который работает с монадами, для которых есть явное понимание что есть ноль и плюс (на данный момент — это монады Maybe, List и Omega). Соответствующие функции guard, msum и mfilter также доступны в модуле monad_plus.

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