пятница, 22 ноября 2013 г.

Функциональное реактивное программирование

Это примерный текст выступления "Функциональное реактивное программирование", которое Алексей Осипенко и я проводили на ноябрьской встрече Донецкого Лямбда-клуба.

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


Нам очень нравится определение функционального программирования из выступления Дэниэла Спивака “Жизнь в пост-функциональном мире”. Это “функция как основная единица абстракции”. Основа основ функцинального программирования - это композируемые примитивы для решения широкого класса задач. За счёт этого о программах, написанных полностью в функциональной парадигме, легко рассуждать в терминах математики - они предсказуемы и даже доказуемы.


“Функциональное программирование объединяет гибкость и мощь абстрактной математики с интуитивной понятностью абстрактной математики”.


Реактивное программирование - это программирование приложений, управляемых событиями. Очень, надо сказать, востребованная штука, потому что это почти все приложения, которыми мы пользуемся - то, что называется, интерактивные приложения. В качестве примера исключения я бы привёл утилиты командной строки. Почти всё остальное - интерактивно и управляется событиями.


События имеют свойство происходить в произвольное время и совершенно не предсказуемы заранее. Чаще всего их обрабатывают как-то так:


function Counter(element) {
  var that = this;
  this.count = 0;
  this.clicked = function () {
    this.count += 1;  
  }
  $(element).click(function() {
    return that.clicked();
  });
};

Код простой и в нём можно очень быстро разобраться, но у него есть несколько проблем. Во-первых, ненавистное нашему сердцу изменяемое состояние, а во-вторых - очень плохая композируемость. Плохая композируемость означает, что код будет очень сложно использовать повторно в других частях приложения и объединять с другими подобными элементами.


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


Однако же мы не зря сюда пришли. Реактивное программирование, о котором мы хотим рассказать, основывается по большому счёту на концепциях из функционального программирования и его способах заводить примитивы.
Лирическое отступление: почему мы про UI и где ещё это применимо. Это применимо везде, где есть входящие события. Ну вот просто везде. Однако UI ставит наиболее интересные и сложные задачи по комбинации потоков: хоть сколь-нибудь развесистый пользовательский интерфейс начинает требовать всё более и более новых и интересных комбинаторов.


Идея примитивов ФРП вкратце. Естественный код:


$("#login").on("click", function (event) {
  var value = $(event.target).val();
  if (value.length > 0) {
    $("#notice").text(value);
  }
});


Вводим один уровень абстракции:


var clickE = $("#login").events("click");
clickE.onValue(function (event) {
  var value = $(event.target).val();
  if (value.length > 0) {
    $("#notice").text(value);
  }
});


На первый взгляд кажется, что мы ничего не добились. Однако же, теперь с этим примитивом мы можем кое-что делать.


var clickE = $("#login").events("click");
var values = clickE.map(function (event) {
  return $(event.target).val();
});
var nonEmptyValues = values.filter(function (value) {
  return value.length > 0;
});
nonEmptyValues.onValue(function (value) {
  $("#notice").text(value);
});


Ну и инлайним лишние переменные:


var values = $("#login").events("click").map(function (event) {
  return $(event.target).val();
}).filter(function (value) {
  return value.length > 0;
});

values.onValue(function (value) {
  $("#notice").text(value);
});


Лирическое отступление: point-free style или tacit programming. Если функция - гражданин первого класса, то имея богатую библиотеку хелперных функций, можно писать, избегая термов. Получается элегантно.

var values = $("#login").events("click").map(
  chain(pluck('target'), $, method('val')
).filter(nonEmpty);
values.onValue(function (value) { $("#notice").text(value); });


Теперь немного разберёмся с денотационной семантикой. Функциональных примитивов для ФРП - два. Традиционно их называют Event и Behaviour, мы же по своих соображениям возьмём другие - Stream и Box.


Stream представляет собой дискретный поток событий и семантически эквивалентен списку кортежей “время-значение” при неубывающем времени:


type Stream[a] = [(T, a)]


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


type Box[a] = T -> a


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


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


Писать будем только интерфейс библиотеки, и если захотим поделиться чем-то интересным - тогда и реализацию.


Что у нас в потоке может быть? Всё. Простейшие конструкторы:


Box.nothing();   // empty box
Box.unit(10);    // box with constant value of 10
Stream.never();  // empty stream
Stream.unit(10); // stream with immediate value of 10


Самоочевидно. 

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


Введём и мы у себя понятие Error события, которое раз появившись будет нетронутым проходить все нормальные ошибки и комбинаторы до тех пор, пока кто-то специально не поинтересуется. Естественно, нужен элементарный способ сконструировать ошибку.


Stream.error(10); // stream with immediate error of 10
Box.error(10);    // box with constant error of 10

Это UI, поэтому, здесь будет полезна работа с временем. Базовый конструктор для этого:


Stream.later(1000, 10); // in a second pops out 10


Более интересно - из DOM-события. Это логично добавить в jQuery.fn:


$('input').stream('keyup'); // stream with keyup events


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


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


asyncCall(data,function(response){
  // You have response from your asynchronous call here.
}, function(err){
  // if the async call fails, the error callback is invoked
});


А вот так это делается с помощью promise:


var promise = asyncCall(data);

promise.done(function(response){
  // You have response from your asynchronous call here.
}).fail(function(err){
  // if the async call fails, you have the error response here.
});


То есть, всё как обычно в функциональном программировании - возвращаем специальное значение и можем с ним что-то такое делать. В новом jQuery обещания используются очень активно - все вызовы ajax и все анимации возвращают такой promise, который успешно завершается при хорошем ответе от сервера или конце анимации, а неуспешно - при плохом ответе от сервера (мне трудно придумать fail для анимации).


Интерфейс очень удобный и очень нужный, поэтому мы им и возпользуемся:


Stream.fromPromise($.ajax(params)); 
// pops a success event on successful response
// or the error event on error response

Итак, что мы можем сделать с нашими потоками?


Самое простое - отобразить, или пропустить через функцию. Для коллекций, наверно, это всем знакомо.


_.map([1, 2, 3], function (x) { return x*x; }); // returns [1, 4, 9]


На потоке и коробке map работает совершенно очевидным способом - получается новый поток или коробка, значения на которой соответствуют исходным, пропущенным через функцию.


priceValue.map(function(x) {
  return x > 1000;
});


В примере мы получим булевое значение, характеризующее, достаточно ли денег предлагает пользователь.


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


Рядом со словом map часто звучит что? filter. Rails программисты знают его под словом “select”.


priceValue.filter(function(x) {
   return x >= 1000;
});


Мы получим значение цены, если оно превышает 1000. Опять-таки, хорошая аналогия с коллекциями.


Ладно. Перейдём к по-настоящему интересной функции. flatMap. Это тоже преобразование значений в контейнере, но существенно более общим образом. Функция, которая передаётся в flatMap должна возвращать не значение, а значение, завёрнутое в новый контейнер. Сам же flatMap каким-то образом связывает результаты этой функции и возвращает опять-таки обёрнутое значение. Что-то на словах сложно получается.


Ну вот, например, есть список пользователей, а у каждого из них есть список комментариев. Нужно получить список всех комментариев.


_.flatMap(users, function (user) { return user.comments(); });
// returns flat list of all the comments the users have


Обратите внимание, что comments() может вернуть и пустой список - что, в свою очередь, никак не вложится в результат.


В нашем случае функция внутри flatMap должная возвращать не список, а поток или коробку. А вот связывать результат можно по-разному. Можно в результирующий поток замешать события всех дочерних потоков. Это наиболее логичная стратегия для потока. А можно подписаться на первый дочерний поток, а при появлении второго, переключиться на него и отписаться от первого. Это наиболее логичная стратегия для коробки.
Заканчивать же результирующий поток будем тогда, когда все дети и родительский поток закончились.


Зачем нам такое преобразование? Хм. Сейчас покажу. Это невероятно мощная штука. Для начала, её можно использовать для прозрачного связывания локальных потоков с асинхронными действиями.


var requests = usernames.map(function(u) {
  return { url: "/check-username/" + u; }
});
requests.flatMap(function (params) {
  return Stream.fromPromise($.ajax(params));
});
// usernames  => "John",          "Peter"
// requests   => {"url": "/check-username/John"}, ...
// flatMap    => {correct: true}, {correct: false}

Во-вторых, с её помощью можно написать map и filter.


Stream.prototype.map = function (f) {
  return this.flatMap(function (x) {
    return Stream.unit(f(x));
  });
}

Stream.prototype.filter = function (f) {
  return this.flatMap(function (x) {
    if f(x) {
      return Stream.unit(x);
    } else {
      return Stream.nothing();
    }
  });
}


Но наибольшие возможности flatMap открывает для написания комбинаторов. Давайте предположим, что нам нужно скомбинировать две коробки в одну. Например для получения значения “пароль и подтверждение” заполнен корректно.


password.map2(passwordConfirmation,
              function(l, r) { return l == r; });


Давайте попробуем написать map2:


Box.prototype.map2 = function (other, f) {
  return this.flatMap(function (x) {
    return other.map(function (y) { return f(x, y); });
  });
}



Поскольку операция map2 имеет смысл только на Box, мы используем версию flatMap, которая берёт только последний поток.


Те, кто сейчас сказал “о, я всё понял!” - поздравляю, вы познакомились с монадами.


Да, монада - это способ положить простое значение в контейнер и способ его достать и сделать новый контейнер. Ну плюс три простых как азимовские закона, о которых мы тоже можем рассказать. Положить простое значение в контейнер принято называть unit (мы его назвали так же), а сделать новый контейнер принято называть bind (мы его назвали flatMap и это имя реально имеет шанс победить, потому что на Scala тупо больше человек пишет код за деньги).


Поскольку мы получили монаду, мы получили аппликативный функтор, и это подтверждается наличием map2 (который позволяет нам тривиально определить apply).


Box.prototype.apply = function (other) {
  return this.map2(function (f, x) { return f(x); } );
}

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


Для потоков же, вместо map2, мы сделаем не менее полезную функцию - merge, позволяющую просто объединить потоки в один. Используя flatMap для потоков, который слушает все дочерние потоки, сделать это очень просто.


var id = function (x) { return x; }
Stream.merge = function (streams) {
  return Stream.fromList(streams).flatMap(id);
}


merge - полезная штука.


var inc = plusClicks.map(function() { return 1; });
var dec = minusClicks.map(function() { return -1; });
var change = plus.merge(minus);


Ещё пара примеров фокусов с flatMap:


Stream.prototype.debounce = function (delay) {
  return this.flatMapLast(function (value) {
      return Stream.later(delay, value);
  });
}

debounce сглаживает слишком частые события. То есть, если на исходном потоке события будут возникать чаще, чем delay, то отправится только последнее из них. Здесь мы используем неродной flatMap, на что и указываем.

Или вот - очень полезный комбинатор sampledBy:


Box.prototype.sampledBy = function (sampler) {
  var that = this;
  return sampler.flatMap(function () { return that.take(1); } );
}


О нём легко думать, как об отображении (map) потока на коробку.


Вот как просто и красиво таким способом записывается такая сложная и неприятная вещь, как drag and drop. Получаем события мыши:


mousedown = $(document).stream('mousedown', '.item')
mouseup = $(document).stream('mouseup')
mousemove = $(document).stream('mousemove')


Легко и непринуждённо получаем такую прелесть, как событие mouseDrag:


mousedrag = mousedown.flatMapLast( 
  (e)-> mousemove.takeUntil(mouseup)
)


Ловим положение курсора...


cursorPosition = mousemove.box().map(
  (e)-> { x: e.clientX, y: e.clientY }
)


...в нужные нам моменты…


startPosition = cursorPosition.sampledBy mousedown
currentPosition = cursorPosition.sampledBy mousedrag


Потом немножко считаем…


shiftPosition = startPosition.zip(currentPosition)
  .map((s, m)-> 
    { left: m.x-s.x, top: m.y-s.y }
  )


...и двигаем объект, куда просили:


shiftPosition.onValue( (pos)-> $('.item').css(pos) )


Ах, да, и просим браузер не умничать:


mousedown.onValue (e)-> e.preventDefault()

Можно ещё вместо этого обойтись замыканиями:


newPosition = mousedown.flatMapLast (md)->
 target = $(md.target);
 {left, top} = target.offset();
 [startX, startY] = [md.clientX - left, md.clientY - top]
 mousemove.map (mm)->
   target: target
   left: mm.clientX - startX
   top: mm.clientY - startY
 .takeUntil mouseup


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


Итак, как теперь жить:


  • Bacon.js, полностью рабочая библиотека.
  • jnoid, демонстрационная библиотека, которая была написана, чтобы разобраться в теме и другие тоже могли в ней разобраться. Для этого даже было использовано “литературное программирование”.
  • javelin для closurescript от пользователя с одним из самых зачётных ников на Гитхабе.
  • elm для маньяков. Красивая вещь для поразбираться, не очень подходит для работы - там jQuery нету.


Берите любой и пробуйте решать проблемы. Не пожалеете.

Другие ссылки:


1 комментарий:

  1. А можно немного прояснить мысль насчет доказуемости кода в 100% функциональном стиле?

    ОтветитьУдалить