Пользователь
0,0
рейтинг
2 октября 2014 в 20:19

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

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

От автора


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

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



Ограничения


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

  • нет изменяемого состояния
    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.

Конец


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

Ссылки



Книги




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




Видео


Перевод: Ionuț G. Stan
maxatwork @maxatwork
карма
31,5
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

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

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

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

  • –4
    Зачем ломать голову над тем, что непонятно? Ну не лежит душа, и фиг с ним, с Хаскелем.
    • +6
      Странный подход, мне вот наоборот — непонятное обычно кажется очень интересным.
      • +2
        Интересно — это когда вау-эффект. Когда чувствуешь, что это круто. А это головоломка ради головоломки.
        • +6
          Был код с побочными эффектами, стал без побочных эффектов, не потеряв в красоте и элегантности — по мне так очень круто и вау-эффект.
        • +6
          Это не вау-эффект. Это типобезопасное программирование без NullPointerException'ов, например.
    • 0
      путь джедая опасен и тернист…
  • 0
    Мне кажется, шаги здесь немного перепутаны: каррирование надо делать раньше перехода к продолжениям, иначе продолжения выглядят бессмысленно.
  • 0
    Так вот оно как оказывается называется.
  • +3
    Сначала из языка выкидывается состояние как вредное, опасное и чреватое ошибками. Потом оно тайком вносится в язык, только обернутое плотным туманом ничего не делающих функций, вызывающих функции и передающих им функции, а под этим флером скрывается банальное копирование всех меняющихся объектов с тайным убиением старых, чтобы никто не заметил, что смена состояния из отдельных объектов переносится в смену состояния всей исполняющей системы.

    Таким образом, мы приходим все к тому же банальному а:=2, но выполненному per anum, требующему x10 ресурсов для своей работы, непонятному для простых смертных и сакральному для непростых.

    Автору и переводчику спасибо за то, что тайное сделали явным.
    • +1
      Состояние остается, выкидывается только изменяемое состояние.
      • 0
        Вы правы. К сожалению, отредактировать уже нельзя. Так что следует читать: «выкидывается изменяемое состояние»
    • +5
      Там ничего не выкидывается. Просто изначально, в математической модели языка, никаких изменяемых состояний нет. Монады его в язык опять же не вносят. Монады — это просто один из pattern-ов функционального программирования, чтобы вручную не протаскивать аргументы между вызовами функций.

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

      Так что, корень проблемы в математике и в том, как мы формально рассуждаем, а совсем не произволе авторов Haskell.
      • –1
        Скорее, корень проблемы в неумеренном пиаре языка Хаскель как очередной панацеи и must-know. Впрочем, ни язык, ни его авторы в этом не виноваты — это был всего лишь эксперимент.
    • +1
      Вынесенное состояние, которое затем внесли обратно через монады и линзы — это не только лишняя сложность, но и удобная абстракция.

      Для таких состояний проще хранить историю, реализовывать операцию отмены, такое состояние проще сохранять в файл…
      • 0
        Достаточно спорно. В приведенной статье исходный стек сохраняется в файл банальным образом. А вот последняя версия — сразу и не сообразишь как.
        • 0
          Пока стек один — да. Как только объектов, хранящих в себе состояние, становится много — уследить за всеми сложнее. Хотя тоже возможно, не спорю.
          • 0
            Вы имеете в виду, если они будут ссылаться друг на друга? Не приведете ли пример, как эту проблему решают в чистом ФП?
  • 0
    Главная причина, почему на Haskell это выглядит лучше, это поддержка монад на уровне синтаксиса в виде do-нотации.

    С помощью ловкости рук и небольшого мошенничества с eval можно реализовать что-то подобное на JS и писать код вида:
    var getUser = eval(async(function (eMail) {
      id <- db1.getID(eMail);
      user <- db2.getData(id);
      return user;
    }));
    

    Это оказалось побочным эффектом идеи, с которой я пришёл на хабр.
    P.S. maxatwork, спасибо большое за перевод интересной статьи!

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