пятница, 16 января 2015 г.

Про Монады

После прочтения десятков «самых понятных введений в монады» и чтения (тоже) десятков обсуждений на разных форумах я пришёл к выводу, что существует группа абстрактных ОО-программистов, которым моя интерпретация «чего-то похожего на монады» может помочь немного приблизиться к правильному пониманию.

Итак, в этой публикации вы не найдете ответы на следующие вопросы:
1. Что такое монада?
2. Где и как использовать монады?
3. Почему монады лучше, чем их отсутствие?

В программировании есть такой феномен — «паттерны проектирования». Официально это набор лучших практик, которыми следует руководствоваться при решении «типичных задач». Неофициально — просто набор костылей для языков, в которых нет встроенных средств для решения типичных проблем.

Есть такой паттерн проектирования — Interpreter. Замечателен он в первую очередь тем, что позволяет сделать некое подобие виртуальной машины поверх любимого языка программирования, при этом:

1. Можно описать программу на языке, понятном виртуальной машине.
2. Можно грабить корованы во всех подробностях описать как виртуальная машина должна интерпретировать каждую инструкцию.

Всё что написано ниже имеет смысл только если любезный читатель минимально знаком с упомянутым паттерном.

Сравнительно каноничный пример:
function add(x) {
  return { op: "add", x: x };
}

function div(x) {
  return { op: "div", x: x };
}

function run(value, statements) {
  for(var i = 0; i < statements.length; ++i) {
    var statement = statements[i];
    var op = statement.op;
    var x = statement.x;
    if(op === "add") {
      value += x;
    } else if(op === "div") {
      value /= x;
    } else {
      throw new Error("Unknown operation " + op);
    }
  }
  return value;
}

var program = [
  add(10),
  div(3)
];

var result = run(0, program);
console.log(result); // 3.3333...

Любители GoF могут поспорить, мол, «это Command, а не Interpreter». Для них пусть это будет Command. В контексте статьи это не очень важно.

В этом примере, во-первых, есть программа, состоящая из двух инструкций: «добавить 10» и «разделить на 3». Что бы это ни значило. Во-вторых, есть исполнитель, который делает что-то осмысленное глядя на программу. Важно заметить, что «программа» влияет на результат своего исполнения очень косвенно: исполнитель совершенно не обязан выполнять инструкции сверху-вниз, он не обязан выполнять каждую инструкцию ровно 1 раз, он вообще может вызовы add() транслировать в «Hello», а div() — в «World».

Договоримся, что трансляция add() в console.log() нам неинтересна. Интересны вычисления. Поэтому немного упростим код, отказавшись от ненужной гибкости:

function add(x) { // add(2)(3) === 5
  return function(a) { return a + x; };
}

function div(x) { // div(10)(5) === 2
  return function(a) { return a / x; };
}

function run(value, statements) {
  for(var i = 0; i < statements.length; ++i) {
    var statement = statements[i];
    value = statement(value);
  }
  return value;
}

var program = [ add(10), div(3) ];
var result = run(program);
console.log(0, result); // 3.3333...

Здесь стоит остановиться. У нас есть некий инструмент, позволяющий отдельно описывать программу и отдельно «способ её исполнения». В зависимости от наших пожеланий к результату исполнения, реализация исполнителя может быть очень разной.

Например, хочется, чтобы как только где-то в вычислениях появляется NaN,null или undefined, вычисления прекращались и возвращался результат null:

...
function run(value, statements) {
  if(!value) {
    return null;
  }
  
  for(var i = 0; i < statements.length; ++i) {
    var statement = statements[i];
    value = statement(value);
    if(!value) {
      return null;
    }
  }
  
  return value;
}

console.log(run(undefined, [add(1)])); // null
console.log(run(1, [add(undefined)])); // null

Хорошо. А что если мы хотим одну и ту же программу выполнять для коллекции разных начальных значений? Тоже не вопрос:

...
function run(values, statements) {
  return values.map(function(value) {
    for(var i = 0; i < statements.length; ++i) {
      var statement = statements[i];
      value = statement(value);
    }
    return value;
  });
}

var program = [ add(10), div(3) ];
console.log(run([0, 1, 2], program)); // [3.333..., 3.666..., 4]

Здесь снова стоит остановиться. Мы используем одни и те же выражения, чтобы описывать программу, но в зависимости от исполнителя получаем очень разные результаты. Попробуем теперь снова немного переписать пример. В этот раз, во-первых, уберём ещё немного гибкости: выражения теперь выполняются строго от первых — к последним, а во-вторых, избавимся от цикла внутри run(). Результат назовём словом Context (чтобы никто не догадался):

...
function Context(value) {
  this.value = value;
}

Context.prototype.run = function(f) {
  var result = f(this.value);
  return new Context(result);
};

var result = new Context(0)
  .run(add(10))
  .run(div(3))
  .value;

console.log(result); // 3.3333... 

Реализация сильно отличается от предыдущих вариантов, но делает оно примерно то же самое. Здесь предлагается ввести термин мунада (от англ.moonad — «лунная реклама»). Здравствуй, Identity moonad:

...
function IdentityMoonad(value) {
  this.value = value;
}

IdentityMoonad.prototype.bbind = function(f) {
  var result = f(this.value);
  return new IdentityMoonad(result);
};

var result = new IdentityMoonad(0)
  .bbind(add(10))
  .bbind(div(3))
  .value;

console.log(result); // 3.3333... 

Эта штука чем-то отдалённо похожа на Identity monad.

Вспомним теперь про тот вариант исполнителя, где мы боролись с NaN и попробуем переписать его используя новый подход к реализации:

function MaybeMoonad(value) {
  this.value = value;
}

MaybeMoonad.prototype.bbind = function(f) {
  if(!this.value) {
    return this;
  }
  
  var result = f(this.value);
  return new MaybeMoonad(result);
};

var result = new MaybeMoonad(0)
  .bbind(add(10))
  .bbind(add(undefined))
  .bbind(div(3))
  .value;

console.log(result); // null

Можно даже более привычный пример:

var person = {
  // address: {
  //   city: {
  //     name: "New York"
  //   }
  // }
};

console.log(person.address.city.name); // падает

console.log(new MaybeMoonad(person)
  .bbind(function(person) { return person.address; })
  .bbind(function(address) { return address.city; })
  .bbind(function(city) { return city.name; })
  .bbind(function(cityName) { return cityName; })
  .value); // не падает, возвращает null

Издалека может показаться, что это Maybe monad. Любезному читателю предлагается самостоятельно реализовать что-то похожее на List monad.

При базовых навыках работы напильником не составит изменитьIdentityMoonad таким образом, чтобы вызовы f() стали асинхронными. В результате получится Promise moonad (что-то похожее на q).

Теперь, если внимательно приглядеться к последним примерам, можно попробовать дать более-менее формальное определение мунады. Мунада — это штука, у которой есть 2 операции:
1. return — принимает обычное значение, помещает его в мунадический контекст и возвращает этот самый контекст. Это просто вызов конструктора.
2. bind — принимает функцию от обычного значения, возвращающую обычное значение, выполняет её в контексте мунадического контекста и возвращает монадический контекст. Это вызов `bbind()`

Комментариев нет:

Отправить комментарий