Функциональное программирование на JavaScript === Мусор

wall-e, мусор

Функциональное программирование превосходно. Оно позволяет легко упрощать программы, также легко их тестировать. К сожалению, не все языки одинаковы. Я немного писал на Clojure и действительно наслаждался им. Поэтому попробовал перенести полученный опыт на JavaScript, и столкнулся с несколькими проблемами о которых собственно и поговорим.

Предпочтение персистентных данных

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

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

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

Если хотите поэкспериментировать, ClojureScript - версия Clojure, которая компилируется в JavaScript, включает персистентные структуры данных. Так же существует проект Mori который берет структуры из ClojureScript, компилирует в одиночный файл-библиотеку и представляет простой JavaScript API.

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

Рекурсия и хвостовая оптимизация

Однажды начав работать с функциями, вы начнете передавать сами функции в другие функции как аргумент. Это называется функции высокого порядка и вы возможно знакомы с ними. Пример с jQuery.fn.each:

function logElem() {
  console.log(this);
}

jQuery("elem").each(logElem);

Это не совсем функциональный подход, так как оно использует this, но вы поняли идею. Для более "функциональной" версии, посмотрите на метод _.each библиотеки underscore.

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

Метод map возвращает обновленное значение для каждого элемента:

function plus1(a) { return a + 1; }

map(plus1, [1,2,3]); // => [2,3,4]

Метод filter возвращает подмножество списка, в зависимости от истинности функции.

function even(a) { return a % 2 === 0; }

filter(even, [1,2,3]); // => [2]

Оба метода могут быть реализованы через редюсер.

function map(f, list) {
  return reduce(function(val, sum) {
    sum.push(f(val));
    return sum;
  }, list, []);
}

Редюсер получает функцию которая может обновить суму значения, начиная с пустой коллекции ([]), и будет вызван для каждого элемента списка.

Ладно, это длинное введение. Вот как в лоб можно было бы реализовать редюсер:

function reduce(f, list, sum) {
  if (list.length < 1) {
    return sum;
  } else {
    var val = list.shift();
    return reduce(f, list, f(val, list));
  }
}

Красиво и чисто (в сравнении с изменяемыми коллекциями). В то же время, использование рекурсии в JavaScript это часовая бомба прямо в вашем коде. Каждый шаг вглубь в reduce, увеличивает стек. В зависимости от обозревателя, версии и доступной памяти, он может решить что стек слишком глубокий и с генерировать исключение. Тесты такое могут не обнаружить и важно не забывать об этом.

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

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

function trampoline(f) {
  return function() {
    var result = f.apply(this, arguments);

    while (result instanceof Function) {
      result = result();
    }

    return result;
  };
}

var reduce = trampoline(function myself(f, list, sum) {
  if (list.length < 1) {
    return sum;
  } else {
    return function() {
      var val = list.shift();
      return myself(f, list, f(val, list));
    };
  }
});

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

Мы получили базовый метод для итерации и мы можем построить map, filter и тд. Но мы внесли более критичный изъян: больше мусора.

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

requestAnimationFrame(function() {
  each(tickPhysics, worldEntities);
});

Следовательно, для избежания генерации мусора, мы должны помнить о избежании рекурсии в низкоуровневых итераторах, и использовать простой, хотя и не функциональный, цикл while. Для более глубокого понимания трамплинов в JavaScript читайте пост Реджинальда Брейтуэйта

Композиция функций и частичное применение

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

function plus(a, b) { return a + b; }

var plus1 = partial(plus, 1);

map(plus1, [1,2,3]); // => [2,3,4]

Теперь у нас есть функция plus1 которая является plus у которой первый аргумент которой уже заполнен. Реализация partial может быть следующая:

function partial() {
  var args = Array.prototype.slice.call(arguments, 0);
  var f = args.shift();

  return function partialExecute_() {
    var args2 = Array.prototype.slice.call(arguments, 0);
    return f.apply(this, args.concat(args2));
  };
}

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

Композиция функции очень похожая, она получает две функции и возвращает новую которая вызывает обе переданные.

function plus1(a) { return a + 1; };
function mult2(a) { return a * 2; };

var addThenMult = compose(mult2, plus1);

map(addThenMult, [1,2,3]); // => [4,6,8]

Простая реализация:

function compose() {
  var fns = Array.prototype.slice.call(arguments, 0);

  return function composedExecute_(value) {
    for (var i = fns.length - 1; i >= 0; --i) {
      value = fns[i](value);
    }
    return value;
  };
}

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

Выводы

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

Оригинал

Добавить комментарий