Разбираемся с монадами с помощью Javascript

Оригинальная статья — Understanding Monads With JavaScript (Ionuț G. Stan).
Буду признателен за комментарии об ошибках/опечатках/неточностях перевода в личку

От автора

Последние несколько недель я пытаюсь понять монады. Я все еще изучаю Haskell, и, честно говоря, думал, что знаю, что это такое, но когда я захотел написать маленькую библиотечку — так, для тренировки — я обнаружил, что хотя и понимаю, как работают монадические bind (>>=) и return, но не представляю, откуда берется состояние. Так что, вероятно, я вообще не понимаю, как это все работает. В результате, я решил заново изучить монады на примере Javascript. План был тот же, когда я выводил Y Combinator: взял изначальную задачу (здесь это взаимодействие с неизменяемым явно состоянием), и проделал весь путь к решению, шаг за шагом изменяя изначальный код.

Я выбрал Javascript, потому что он заставляет писать все то, что Haskell услужливо прячет благодаря своему лаконичному синтаксису или различным семантикам (лямбда-выражениям, операторам и встроенному каррированию функций). И наконец, я лучше учусь на сравнении, поэтому я решил эту задачу еще и на CoffeeScript и Scheme, вот ссылки на фрагменты кода:

• CoffeeScript: gist.github.com/936519
• Scheme: gist.github.com/936695

Ограничения

В этой статье я ограничусь монадой состояния, этого достаточно для понимания, что такое монады вообще. Так что вот наши ограничения:

• нет изменяемого состояния
  Haskell использует монады, так как в нем нет изменяемого состояния.
  
• нет явного состояния
  Когда у вас нет изменяемого состояния, вы вынуждены везде передавать результирующее состояние. Написание и чтение подобного кода вряд ли доставляет удовольствие, монады же прячут все это уродство (чуть позже вы это увидите).
  
• нет дублирования кода
  Это замечание идет рука об руку с предыдущим, но я все равно вынесу его отдельно, потому как удаление дублирующегося кода — мощный инструмент для исследования новых высот.
  

Многабукафниасилю

Статья получилась довольно насыщенной, так что я подумал, что неплохо бы добавить дополнительного материала, и записал небольшое видео со всеми шагами, которые описаны ниже. Это вроде tl;dr версии, и должно помочь показать все описанные переходы, но, похоже, просмотр видео не будет сильно полезен без прочтения статьи.
Я рекомендую смотреть его непосредственно на Vimeo, где оно доступно в HD.

Наш подопытный кролик

Я буду использовать стек в качестве нашего подопытного, потому что он имеет простую для понимания структуру, и его обычная реализация использует изменение состояния. Вот, как обычно реализуют стек на Javascript:

var stack = [];

stack.push(4);
stack.push(5);
stack.pop(); // 5
stack.pop(); // 4

Массив в Javascript имеет все методы, которые мы ожидаем увидеть у стека: push и pop. Что мне не нравится, так это то, что они меняют состояние. Ну, по крайней мере, мне это не нравится в рамках данной статьи.
Каждый шаг, который я опишу, рабочий. Просто откройте консоль своего браузера, и обновите эту страницу: вы увидите несколько групп строк 5 : 4. Однако в тексте статьи я буду приводить только изменения по сравнению с предыдущим шагом.

Стек с явной обработкой состояния

Очевидное решение для избежания изменяемого состояния — создавать новый объект состояния на каждое изменение. В Javascript это могло бы выглядеть так:

// .concat() и .slice() - два метода массива, которые не изменяют объект, для которого они были вызваны, а возвращают новый массив
var push = function (element, stack) {
  var newStack = [element].concat(stack);

  return newStack;
};

var pop = function (stack) {
  var value = stack[0];
  var newStack = stack.slice(1);

  return { value: value, stack: newStack };
};

var stack0 = [];

var stack1 = push(4, stack0);
var stack2 = push(5, stack1);
var result0 = pop(stack2);        // {value: 5, stack: [4]}
var result1 = pop(result0.stack); // {value: 4, stack: []}

Как видите, pop и push возвращают результирующий стек. pop к тому же возвращает и значение с вершины стека. Каждая последующая операция со стеком использует предыдущую версию стека, но это не так очевидно из за разницы в представлении возвращаемых значений. Мы можем усилить дублирование кода, нормализовав возвращаемые значения: заставим push возвращать undefined:

var push = function (element, stack) {
  var value = undefined;
  var newStack = [element].concat(stack);

  return { value: value, stack: newStack };
};

var pop = function (stack) {
  var value = stack[0];
  var newStack = stack.slice(1);

  return { value: value, stack: newStack };
};

var stack0 = [];

var result0 = push(4, stack0);
var result1 = push(5, result0.stack);
var result2 = pop(result1.stack); // {value: 5, stack: [4]}
var result3 = pop(result2.stack); // {value: 4, stack: []}

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

Перепишем код в стиле передачи продолжения

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

var bind = function (value, continuation) {
  return continuation(value);
};

var stack0 = [];

var finalResult = bind(push(4, stack0), function (result0) {
  return bind(push(5, result0.stack), function (result1) {
    return bind(pop(result1.stack), function (result2) {
      return bind(pop(result2.stack), function (result3) {
        var value = result2.value + " : " + result3.value;
        return { value: value, stack: result3.stack };
      });
    });
  });
});

Значение всего выражения, возвращенное в finalResult, имеет тот же тип, что и значение отдельной операции push или pop. Нам нужен единообразный интерфейс.

Каррирование push и pop

Далее, нам нужно оторвать аргумент со стеком от push и pop, потому что мы хотим, чтобы его скрыто передавал bind.
Для этого мы используем еще один трюк лямбда-исчисления, называемый каррирование. Другими словами его можно было бы назвать прокрастинацией применения функции.
Теперь вместо вызова push(4, stack0) мы будем вызывать push(4)(stack0). В Haskell нам не понадобился бы этот шаг, потому что там функции и так каррированы.

var push = function (element) {
  return function (stack) {
    var value = undefined;
    var newStack = [element].concat(stack);

    return { value: value, stack: newStack };
  };
};

var pop = function () {
  return function (stack) {
    var value = stack[0];
    var newStack = stack.slice(1);

    return { value: value, stack: newStack };
  };
};

var stack0 = [];

var finalResult = bind(push(4)(stack0), function (result0) {
  return bind(push(5)(result0.stack), function (result1) {
    return bind(pop()(result1.stack), function (result2) {
      return bind(pop()(result2.stack), function (result3) {
        var value = result2.value + " : " + result3.value;
        return { value: value, stack: result3.stack };
      });
    });
  });
});

Готовим bind к передаче промежуточных стеков

Как я сказал в предыдущей части, мне бы хотелось, чтоб bind занимался передачей аргумента с явным стеком. Для этого, во-первых, давайте сделаем так, чтоб bind принимал стек последним параметром, но в виде каррированой функции, т.е. пусть bind возвращает функцию, которая принимает стек в качестве аргумента. Также, теперь push и pop применены частично, то есть мы больше не передаем им стек напрямую, этим теперь занимается bind.

var bind = function (stackOperation, continuation) {
  return function (stack) {
    return continuation(stackOperation(stack));
  };
};

var stack0 = [];

var finalResult = bind(push(4), function (result0) {
  return bind(push(5), function (result1) {
    return bind(pop(), function (result2) {
      return bind(pop(), function (result3) {
        var value = result2.value + " : " + result3.value;
        return { value: value, stack: result3.stack };
      })(result2.stack);
    })(result1.stack);
  })(result0.stack);
})(stack0);

Убираем стеки в конце

Теперь мы можем спрятать промежуточные стеки, изменив bind таким образом, чтоб она анализировала возвращенное значение функции stackOperation, доставала оттуда стек, и передавала его продолжению, которое должно быть функцией, принимающей стек. Также мы должны обернуть возвращаемое значение { value: value, stack: result3.stack } в анонимную функцию.

var bind = function (stackOperation, continuation) {
  return function (stack) {
    var result = stackOperation(stack);
    var newStack = result.stack;
    return continuation(result)(newStack);
  };
};

var computation = bind(push(4), function (result0) {
  return bind(push(5), function (result1) {
    return bind(pop(), function (result2) {
      return bind(pop(), function (result3) {
        var value = result2.value + " : " + result3.value;

        // We need this anonymous function because we changed the protocol
        // of the continuation. Now, each continuation must return a
        // function which accepts a stack.
        return function (stack) {
          return { value: value, stack: stack };
        };
      });
    });
  });
});

var stack0 = [];
var finalResult = computation(stack0);

Прячем оставшийся стек

В предыдущей реализации мы спрятали несколько промежуточных стеков, но добавили еще один, в функции, возвращающей финальное значение. Мы можем спрятать и этот след стека, написав другую вспомогательную функцию result. К тому же, это спрячет представление состояния, которое мы храним — структуру с двумя полями, value и stack.

var result = function (value) {
  return function (stack) {
    return { value: value, stack: stack };
  };
};

var computation = bind(push(4), function (result0) {
  return bind(push(5), function (result1) {
    return bind(pop(), function (result2) {
      return bind(pop(), function (result3) {

        return result(result2.value + " : " + result3.value);

      });
    });
  });
});

var stack0 = [];
var finalResult = computation(stack0);

Это как раз то, что делает функция return в Haskell. Она оборачивает результат вычисления в монаду. В нашем случае она оборачивает результат в замыкание, которое принимает стек, и это как раз и есть монада вычислений с изменяемым состоянием — функция, принимающая свое состояние. Другими словами result/return можно описать, как фабричную функцию, создающую новый контекст с состоянием вокруг значения, которое мы ей передаем.

Делаем состояние внутренним

Нам не надо, чтоб наши продолжения должны были знать о структуре, возвращаемой функциями push и pop, которая на самом деле представляет внутренности монады. Так что мы модифицируем bind для передачи только необходимого минимума данных в коллбэки.

var bind = function (stackOperation, continuation) {
  return function (stack) {
    var result = stackOperation(stack);
    return continuation(result.value)(result.stack);
  };
};

var computation = bind(push(4), function () {
  return bind(push(5), function () {
    return bind(pop(), function (result1) {
      return bind(pop(), function (result2) {

        return result(result1 + " : " + result2);

      });
    });
  });
});

var stack0 = [];
var finalResult = computation(stack0);

Выполняем вычисление стека

Раз уж мы можем комбинировать операции над стеком, то мы захотим и выполнять эти вычисления, и использовать результат. Это в общем и называется вычислением (evaluation) монады. В Haskell монада вычислений с изменяемым состоянием предоставляет три функции для ее вычисления: runState, evalState и execState.
Для целей данной статьи я заменю суффикс State на Stack.

// Returns both the result and the final state.
var runStack = function (stackOperation, initialStack) {
  return stackOperation(initialStack);
};

// Returns only the computed result.
var evalStack = function (stackOperation, initialStack) {
  return stackOperation(initialStack).value;
};

// Returns only the final state.
var execStack = function (stackOperation, initialStack) {
  return stackOperation(initialStack).stack;
};

var stack0 = [];

console.log(runStack(computation, stack0));
// { value="5 : 4", stack=[]}

console.log(evalStack(computation, stack0));
// 5 : 4

console.log(execStack(computation, stack0));
// []

Если все, что нам интересно — это конечное вычисленное значение, то evalStack — это то, что нам нужно. Она запустит монадическое вычисление, отбросит конечное состояние и вернет вычисленное значение. Используя эту функцию, мы можем вытащить значение из монадического контекста.
Если вы когда либо слышали, что вы не сможете выйти (escape) из монады, то я скажу, что это правда только в малом количестве случаев, таких, как монада IO. Но это уже другая история, главное — это то, что вы можете выйти из монады вычислений с изменяемым состоянием.

Готово

Если вы все еще со мной, то я скажу, что вот так может выглядеть монада в Javascript. Не так круто и читаемо, как в Haskell, но это вроде лучшее, что я смог сделать.
Монады — это довольно абстрактная концепция, потому что она почти не указывает, что писать. В основном, она говорит, что вы должны создать функцию, которая принимает несколько аргументов (состояние в случае монады с изменяемым состоянием) и две дополнительные функции: result и bind. Первая будет работать, как фабрика для функции, которую вы создали, а вторая будет предоставлять внешнему миру только необходимые данные о монаде, и делать всю скучную работу, такую как передачу состояния, используя продолжение, которое будет получать вычисленное монадой значение. Все, что должно быть внутри монады — остается внутри. Прям как в ООП — можно даже создавать монадические геттеры/сеттеры.
Для протокола, вот как выглядело бы computation на Haskell:

computation = do push 4
                 push 5
                 a <- pop
                 b <- pop
                 return $ (show a) ++ " : " ++ (show b)

Главная причина, почему на Haskell это выглядит лучше, это поддержка монад на уровне синтаксиса в виде do-нотации. Это просто сахар для версии, которая все равно выглядит лучше, чем в Javascript. Haskell, благодаря поддержке переопределения операторов и лаконичным лямбда-выражениям, позволяет реализовать более читаемую реализацию монад:

computation = push 4 >>= \_ ->
              push 5 >>= \_ ->
              pop    >>= \a ->
              pop    >>= \b ->
              return $ (show a) ++ " : " ++ (show b)

В Haskell >>= — это то, что я назвал bind в Javascript, а return — то, что я назвал result. Да, return в Haskell не ключевое слово, а функция. В других случаях return является unit'ом. Brian Marick называл >>= decider'ом в своем видео про монады в Clojure. Patcher'ом он, конечно, называл return.

Немного сахара для Javascript

На самом деле, гораздо лучше производить монадические вычисления в Javascript, используя вспомогательную функцию sequence. Благодаря динамической природе Javascript, sequence может принимать произвольное число аргументов, которые представляют собой монадические операции, которые необходимо выполнить последовательно, и последним аргументом действие, которое нужно выполнить над результатом монадических действий. Этому коллбеку будут переданы все не-undefined результаты монадических вычислений.

var sequence = function (/* monadicActions..., continuation */) {
  var args           = [].slice.call(arguments);
  var monadicActions = args.slice(0, -1);
  var continuation   = args.slice(-1)[0];

  return function (stack) {
    var initialState = { values: [], stack: stack };

    var state = monadicActions.reduce(function (state, action) {
      var result = action(state.stack);
      var values = state.values.concat(result.value);
      var stack  = result.stack;

      return { values: values, stack: stack };
    }, initialState);

    var values = state.values.filter(function (value) {
      return value !== undefined;
    });

    return continuation.apply(this, values)(state.stack);
  };
};

var computation = sequence(
  push(4), // <- programmable commas :)
  push(5),
  pop(),
  pop(),

  function (pop1, pop2) {
    return result(pop1 + " : " + pop2);
  }
);

var initialStack = [];
var result = computation(initialStack); // "5 : 4"

Авторы книги Real World Haskell сравнивают монады с программно-эмулируемой точкой с запятой (programmable semicolon). В нашем случа, мы имеем программно-эмулируемую запятую, поскольку я использовал ее для разделения монадических действий в sequence.

Монады, как отложенные вычисления

Частенько вы слышали, как монады называли вычислениями. Сначала я не понимал, почему. Можно сказать, мол, потому что они вычисляют разные штуки, но нет, никто не говорит: «монады вычисляют», обычно говорят, «монады — это вычисления». Я, наконец, понял (ну или думаю, что понял), что это значит, после завершения черновика статьи. Все эти цепочки действий и значений ничего не вычисляют, пока им не скажут это сделать. Это просто большая цепь частично примененных функций, которые могут быть выполнены после вызова с начальным состоянием. Вот пример.

var computation = sequence(
  push(4),
  push(5),
  pop(),
  pop(),

  function (pop1, pop2) {
    return result(pop1 + " : " + pop2);
  }
);

Этот кусок кода вычисляет что-либо после выполнения? Нет. Необходимо его запустить с помощью runStack, evalStack или execStack.

var initialStack = [];
evalStack(computation, initialStack);

Похоже, что push и pop производят действия над каким-то глобальным значением, в то время как на самом деле они всегда ждут, когда им это значение передадут. Это почти как в ООП, когда у нас есть this в качестве контекста вычисления. В нашем случае, это реализовано с помощью каррирования и частичного применения, и также указыаает на новый контекст в каждом выражении. И, если в ООП контекст назван неявным, то используя монады вы делаете его еще более неявным (если он вообще есть).
Преимущество монад (и вообще функционального программирования) в том, что вы получаете легко комбинируемые блоки. И все это благодаря каррированию. Каждый раз, когда два монадических действия производятся последовательно, создается новая функция, которая ожидает выполнения.

var computation1 = sequence(
  push(4),
  push(5),
  pop(),
  pop(),

  function (pop1, pop2) {
    return result(pop1 + " : " + pop2);
  }
);

var computation2 = sequence(
  push(2),
  push(3),
  pop(),
  pop(),

  function (pop1, pop2) {
    return result(pop1 + " : " + pop2);
  }
);

var composed = sequence(
  computation1,
  computation2,

  function (a, b) {
    return result(a + " : " + b);
  }
);

console.log( evalStack(composed, []) ); // "5 : 4 : 3 : 2"

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

Конец

Ну, надеюсь, данная статья оказалась вам полезной. Ее написание (и перевод — прим. пер.) определенно помогло мне в улучшении понимания монад.

Ссылки

Книги

• Programming in Haskell
• Learn You a Haskell For Great Good!
• Real World Haskell

Статьи и документы

• A Schemer’s Introduction to Monads
• Monadic Parsing in Haskell
• Monadic Parser Combinators
• Monads in Python
• What the hell are Monads?

Видео

• The Quick Essence of Functional Programming
• Monad Tutorial in Clojure, Part 1
• Monad Tutorial in Clojure, Part 2
• Monad Tutorial in Clojure, Part 3
• Monad Tutorial in Clojure, Part 4