Введение в Immutable.js и основные концепции функционального программирования
Перевод статьи Sebastián Peyrott: Introduction to Immutable.js and Functional Programming Concepts.
Знакомимся с функциональными структурами данных и их использованием в обзоре популярной JavaScript библиотеки от Facebook — Immutable.js
Последние несколько лет функциональное программирование переживает свой подъём. Такие языки, как Clojure, Scala и Haskell, дали возможность разработчикам, привыкшим писать в императивном стиле, использовать интересные техники, которые в определённых случаях могут приносить значительные преимущества. Цель Immutable.js — привнести эти преимущества в JavaScript с помощью простого и понятного API. В этом обзоре мы познакомимся с некоторыми из них и научимся использовать их в своих проектах.
Введение: важность иммутабельности и Immutable.js
Несмотря на то, что функциональное программирование понятие гораздо более широкое, чем просто иммутабельность данных, многие функциональные языки уделяют особое внимание именно этому аспекту. Некоторые, такие как Clean и Haskell, на этапе компиляции накладывают строгие ограничения на то, как и когда данные могут быть мутированы. Это отталкивает многих разработчиков. Для тех же, кто справился с волной первоначального шока, начинают появляться новые паттерны и новые способы решения проблем. В частности, структуры данных — это ключевой момент, вызывающий трудности у тех, кто только начинает знакомиться с функциональной парадигмой.
В конечном итоге вопрос иммутабельных и мутабельных структур данных сводится к чистой математике. Анализ алгоритмов подскажет, какие структуры данных лучше подойдут для решения тех или иных типов задач. Поддержка языком, однако, может облегчить использование и реализацию этих структур данных. JavaScript, чьим достоинством является мультипарадигмальность, хорошо подходит и для мутабельных, и для иммутабельных структур данных. В других языках, таких как C, можно реализовывать иммутабельные структуры, однако, их использование может быть не слишком удобным из-за ограничений языка.
Что же такое мутация? Мутация — это изменение существующих данных или структуры, которая их в себе хранит. Иммутабельность же, в свою очередь, предполагает создание копии существующих данных или структуры, когда необходимы изменения, и добавление этих изменений туда.
Каковы же основные принципы функциональных структур данных, и, что особенно важно, что делает иммутабельность таким значимым фактором? В каких случаях это можно использовать? Эти вопросы мы рассмотрим дальше.
Важно: вы могли не знать об этом, но возможно, вы уже используете некоторые конструкции функционального программирования в своём JavaScript-коде. Например,
Array.map()применяет переданную функцию на каждом элементе массива и возвращает вам новый массив, не модифицируя существующий. Функциональное программирование как парадигма поощряет использование функций первого порядка, которые могут передаваться в алгоритм и возвращать новую версию существующих данных. В частности, именно это и делаетArray.map(). Такой подход к написанию кода предполагает использование композиции - ещё один базовый концепт функционального программирования.
Ключевые концепции
За функциональным программированием стоит несколько ключевых идей. Надеюсь, следуя далее по статье, вы поймёте, как эти идеи находят отражение в Immutable.js и других функциональных библиотеках.
Иммутабельность
Иммутабельность предполагает, что после создания данные или структура, которая их содержит, не могут быть изменены. На практике существует два типа мутаций (изменений) — видимые и невидимые. Видимые мутации — это мутации, изменяющие данные или структуру, содержащую эти данные, способом, который контролируется внешним наблюдателем через API. Невидимые мутации не могут контролироваться через API (хорошим примером являются кэширующие структуры данных). В некотором смысле невидимые изменения могут рассматриваться как сайд-эффекты (side-effects) (мы рассмотрим этот аспект и его значение чуть позже). В контексте функционального программирования обычно запрещены оба вида модификаций: не только данные являются иммутабельными по умолчанию, но и структуры данных не могут быть изменены после создания.
Когда разработчики (и компиляторы/среды выполнения) могут быть уверены, что данные не могут измениться, появляются довольно интересные преимущества:
- блокировка для многопоточности больше не является проблемой: если данные не изменяются, нет необходимости в какой-либо блокировке, чтобы синхронизировать разные потоки;
- хранение (persistence) — ещё один ключевой концепт, который мы рассмотрим позже, становится проще;
- копирование возможно за константное время, потому что этот процесс становится лишь вопросом создания новой ссылки на уже существующий экземпляр структуры данных;
- в некоторых случаях сравнение значений может быть оптимизировано: когда среда выполнения или компилятор во время загрузки или компиляции могут быть уверены, что одна переменная равна другой только в том случае, если они обе указывают на один и тот же объект в памяти, глубокое сравнение значений становится сравнением ссылок. Этот процесс известен как интернирование и обычно возможен только для данных, доступных во время компиляции или загрузки. Эту оптимизацию можно выполнить и вручную (в конце статьи в отдельной секции я объясню, как это сделано в React и Angular).
Вы уже используете иммутабельные структуры данных: строки
Строки в JavaScript иммутабельны. Все методы в String.prototype предоставляют возможности либо только для чтения, либо возвращают новую строку.
Иногда во время выполнения JavaScript извлекает из этого преимущества: во время загрузки или во время JIT (Just-In-Time) компиляции упрощается сравнение строк (обычно между строковыми литералами), превращаясь в простое сравнение ссылок. Вы можете сами увидеть, как браузер делает это с помощью теста JSPerf, а также сделать много других простых проверок.
Иммутабельность и Object.freeze()
JavaScript — это динамический слабо типизированный язык (или нетипизированный, если вы знакомы с теорией языков программирования). Из-за этого временами трудно обеспечить наличие определённых ограничений на объекты и данные, и здесь нам на помощь приходит Object.freeze(). Вызов этого метода делает все свойства объекта неизменяемыми. Попытка присвоить значение либо просто упадёт, либо выбросит ошибку (в strict mode). Если вы хотите создать иммутабельный объект, то вызов Object.freeze() после создания объекта может вам помочь.
Имейте в виду, что Object.freeze() работает поверхностно: свойства вложенных объектов могут быть модифицированы. Чтобы исправить это, Mozilla показали, как может быть написана версия этого метода с глубокой заморозкой (deepFreeze):
Сайд-эффекты
В теории языков программирования сайд-эффекты какой-либо операции (обычно это вызов функции или метода) определяются как наблюдаемые эффекты, которые могут быть заметны за пределами вызова функции (изменяют состояния за пределами своей области видимости). Другими слова, после вызова вы увидите изменение состояния. Каждый вызов мутирует (изменяет) состояние. В отличие от концепции иммутабельности, которая обычно связана только с данными или структурой данных, сайд-эффекты касаются состояния программы в целом. Функция, сохраняющая иммутабельность структуры данных, может вызывать побочные эффекты. Хорошим примером этого служат кэширующие функции или мемоизация. Несмотря на то, что внешнему наблюдателю может казаться, что никаких изменений не произошло, обновление глобального или локального кэша имеет побочный эффект обновления внутренних структур данных, которые работают как кэш (результирующие ускорения также являются побочным эффектом). Задача разработчика — знать о побочных эффектах и уметь работать с ними.
Например, продолжая пример с кэшем, иммутабельная структура данных, кэширующая обращения к ней для ускорения работы, не может безопасно передаваться между потоками: либо кэш должен поддерживать многопоточность, либо это может привести к неожиданным результатам.
Функциональное программирование как парадигма предполагает использование функций, не вызывающих сайд-эффекты. Это означает, что функции должны просто выполнять операции над данными, переданными в качестве параметров, и эффекты этих операций должны быть видны только тому, кто вызвал эту функцию. Иммутабельные структуры данных идут рука об руку с функциями без сайд-эффектов.
Чистота
Чистота — это ещё одно ограничение, которое может быть наложено на функции: чистые функции при вычислении результата используют только то, что явно передано им в качестве параметров. Другими словами, чистые функции не могут использовать глобальное состояние или состояния, доступные через какие-то другие конструкции.
Ссылочная прозрачность
Сочетание функций, не создающих сайд-эффекты, и чистоты рождает ссылочную прозрачность. В любом месте программы мы можем заменить функцию, обладающую ссылочной прозрачностью, результатом её выполнения и быть уверены, что это не повлияет на вычисления в целом.
Как вы могли заметить, все эти особенности накладывают намного более строгие ограничения на то, как данные и код могут себя вести. И хотя решения становятся менее гибкими, когда дело доходит до анализа и доказательств, мы можем увидеть, как много преимуществ мы получаем. Как минимум, разные потоки без блокировки могут работать с иммутабельными структурами данных без сайд-эффектов.
Персистентность
Как мы могли понять из предыдущих глав, иммутабельность делает некоторые вещи проще. Ещё одна вещь, которая становится проще с иммутабельными структурами данных, — это персистентность. В контексте структур данных персистентность относится к возможности сохранения старых версий структуры данных после создания новой версии.
Как уже упоминалось ранее, в результате операции записи на иммутабельных структурах данных возвращается новая версия структуры, не изменяя напрямую существующую. В большинстве случаев эти изменения незначительны (в зависимости от количества данных или размера структуры) и в таком случае создание полной копии всей структуры данных целиком является не самым оптимальным решением. Большинство алгоритмов, работающих с иммутабельными структурами данных, пользуются преимуществами иммутабельности первой созданной версии и создают копию только тех данных (или частей структуры данных), которые необходимо изменить.
Частично персистентные структуры данных поддерживают возможность изменения последней версии структуры данных и возможность выполнения операций чтения на остальных версиях. Полностью персистентные структуры поддерживают операции чтения и записи на всех версиях. Однако во всех случаях подразумевается, что при записи или какой-либо модификации данных создаётся новая версия структуры данных.
Это может казаться не совсем очевидным, но персистентные структуры данных намного лучше работают со сборщиком мусора, чем со счетчиком ссылок или ручным управлением памятью. Поскольку каждое изменение приводит к созданию новой версии данных, и при этом предыдущие версии остаются доступными, каждый раз, когда выполняется изменение, создаются новые ссылки на существующие данные. В системах с ручным управлением памятью отслеживание, где и какие фрагменты данных имеют ссылки, довольно быстро превращается в проблему. С другой стороны, с точки зрения разработчика, счетчик ссылок может казаться вещью более удобной, однако это неэффективно с алгоритмической точки зрения: каждый раз, когда происходит изменение, счетчик ссылок изменённых данных должен обновиться. Кроме того, это невидимое изменение по сути является сайд-эффектом, ограничивающим возможность применения некоторых преимуществ. В противовес этому, сборщик мусора не имеет ни одной из этих проблем. Создание ссылки на существующие данные не влечет за собой никаких накладных расходов.
В примере ниже каждая версия оригинального списка доступна, начиная с самой первой версии (через переменную):
Ленивые вычисления
Ещё один плюс иммутабельности, хоть и не такой очевидный — более простая организация ленивых вычислений. Ленивыми операциями называют операции, которые не выполняются до тех пор, пока не потребуется результат их выполнения (обычно используется строгая модель вычислений; строгие вычисления в данном контексте противопоставляются ленивым). Иммутабельность невероятно полезна в контексте ленивых операций, потому что ленивые вычисления обычно предполагают выполнение операции в будущем. Если данные, связанные с такой операцией, каким-либо образом изменяются между моментом завершения операции и её результатами, то операция не может быть безопасно выполнена. Иммутабельность данных даёт возможность использовать ленивые вычисления и не беспокоиться, что определённые данные могут измениться. Другими словами, иммутабельность поддерживает ленивые вычисления в качестве вычислительной стратегии.
Ленивые вычисления поддерживаются и в Immutable.js:
У ленивых вычислений есть несколько плюсов, самый важный из которых — вычисляться будут только необходимые значения. Например, представьте, что у вас есть список элементов от 1 до 10. Давайте применим две независимые операции на каждом элементе списка. Первая операция будет называться plusOne, а вторая - plusTen. Обе операции делают довольно очевидные вещи, первая прибавляет к переданному аргументу единицу, вторая - десять.
Как вы можете заметить, работает это не слишком эффективно — map дважды пробегается по списку, даже если ни один из элементов result нигде не был использован. А теперь представьте, что вам нужен только первый элемент - при строгом вычислении оба цикла отработают полностью. При ленивом вычислении каждый цикл отработает столько раз, сколько потребуется, чтобы рассчитать требуемое значение - то есть, если нам потребуется result[0], каждый plus... будет выполнен лишь один раз.
Ленивые вычисления могут также использоваться с бесконечными структурами данных. Например, при поддержке ленивых вычислений мы можем безопасно посчитать от единицы до бесконечности. Также ленивые вычисления удобны при работе с невалидными значениями: если в процессе вычислений невалидное значение никогда не будет запрошено, тогда ни одна невалидная операция, которая может вызвать исключение или другую ошибку, не будет выполнена.
В некоторых функциональных языках программирования можно реализовать продвинутые оптимизации, используя ленивые вычисления, такие как дефорестация (deforestation) и расщепление тела цикла (loop fusion). По существу, эти оптимизации могут превратить операции, определённые в нескольких циклах, в один цикл или, другими словами, удалять промежуточные структуры данных. По сути, два вызоваmap из примера выше превращаются в один map, который вызываетplusOne иplusTen в одном цикле. Ловко, не правда ли?
Однако, конечно, ленивые вычисления имеют свои недостатки: во время их использования часто становится неочевидно, когда именно будет посчитано выражение и завершатся вычисления. Анализ некоторых довольно сложных ленивых операций становится затруднительным. Другим недостатком являются утечки памяти: они обусловлены необходимостью хранить данные, которые могут понадобиться для будущих вычислений. Определенные ленивые конструкции могут привести к бесконтрольному расходу памяти, что может вызвать проблемы.
Композиция
Композиция в контексте функционального программирования — это возможность комбинировать различные функции, создавая из них новые мощные функции. В основе этого лежит использование функций первого порядка (функций, которые можно рассматривать как данные и передавать в другие функции), замыкания и каррирование (думайте об этом, как о Function.bind на стероидах). Синтаксис JavaScript, в отличие от некоторых функциональных языков программирования, не так удобен для реализации композиции, однако, это всё же возможно. Хорошо спроектированный API может дать хороший результат.
Поддержка Immutable.js ленивых вычислений в сочетании с композицией дают хорошо читаемый JavaScript код:
Аварийный люк: мутация
При всех преимуществах, которые может обеспечить иммутабельность, определенные операции и алгоритмы эффективны только при поддержке мутации. И хотя по умолчанию в большинстве функциональных языков (в отличие от императивных) данные иммутабельны, как правило, мутации всё же возможны для эффективной реализации подобных операций.
И с этим тоже прекрасно справляется Immutable.js:
Анализ алгоритмов
В мире алгоритмов и структур данных ничего не происходит просто так. За улучшения в одной области приходится платить ухудшениями в другой. Мы обсудили преимущества иммутабельности: лёгкая персистентность, простое прослеживание изменений и их причин, сокращение блокировок и так далее. А что насчёт недостатков?
Пожалуй, первое, о чём стоит задуматься, когда мы говорим об алгоритмах, это временная сложность. Иммутабельные структуры данных имеют совершенно иные характеристики времени выполнения, чем изменяемые структуры. В частности, иммутабельные структуры обычно имеют очень хорошие показатели времени выполнения, если принимать во внимание требования к персистентности.
Простым примером этих различий являются однонаправленные списки: списки, в которых каждый элемент имеет ссылку на следующий (но не наоборот).
Изменяемые (мутабельные) однонаправленные списки имеют следующую временную сложность (рассмотрим наихудший случай, при условии, что известна первая, последняя и вставляемая нода):
- добавление в начало O(1)
- добавление в конец O(1)
- вставка O(1)
- поиск O(n)
- копирование O(n)
А вот как ведет себя иммутабельный однонаправленный список в тех же условиях (наихудший случай, известна первая, последняя и вставляемая нода):
- добавление в начало O(1)
- добавление в конец O(n)
- вставка O(n)
- поиск O(n)
- копирование O(1)
Если вы не знакомы с анализом временной сложности алгоритмов и Big O нотацией, прочтите эту статью.
Результаты выглядят не слишком привлекательно. Однако временной анализ наихудшего случая не учитывает ограничения требований, накладываемых персистентностью. То есть, если те же требования применить к изменяемым структурам данных, расчет времени выполнения был бы почти такой же, как у иммутабельной версии (по крайней мере, для рассмотренных операций). Копирование при записи и другие техники могут улучшить среднее время для некоторых операций, которые так же не принимаются в расчет анализа наихудшего случая.
Как показывает практика, анализ наихудшего варианта не всегда самый лучший способ анализа при выборе структуры данных. Амортизационный анализ рассматривает структуру данных как последовательность операций. Структура данных с хорошим средним временем выполнения операций редко демонстрирует поведение наихудшего случая, на деле показывая куда более впечатляющий результат. Хорошим примером случая, где амортизационный анализ имеет смысл, это пример работы с динамическим массивом, оптимизированным удваивать свой размер, когда элемент необходимо вставить за границы массива. Анализ наихудшего случая оценивает операцию добавления в конец как O(n). Амортизационное время может рассматриваться как константное (O(1)), так как половина (n/2) случаев может быть выполнена прежде, чем выполнится удвоение массива, которое будет стоить O(n). Как правило, если в вашем случае важно постоянное время, амортизационный анализ не применим. С другой стороны, тщательный анализ ваших требований может помочь найти структуру данных с хорошим средним временем, больше подходящую для решения вашей задачи.
Анализ временной сложности алгоритма упускает еще одну важную вещь: как использование той или иной структуры данных повлияет на остальной код? Например, с иммутабельными структурами данных вам больше нет нужды в блокировке, если требуется работа с многопоточностью.
Кэш процессора
Еще одна вещь, о которой стоит задуматься, это то, каким образом выбранная структура данных будет взаимодействовать с кэшем процессора, особенно если речь идёт о высокопроизводительных вычислениях. Как правило, для мутабельных структур данных помещение в кэш является хорошим вариантом (если только структура не персистентная) в случаях, когда выполняется много операций записи.
Использование памяти
Использование иммутабельных структур данных по своей природе является причиной пиковых значений в использовании памяти. После каждого изменения создается копия. Если копии больше не используются, то сборщик мусора собирает старые кусочки данных во время очередной сборки. С этим и связано появление пикового использования памяти: чем дольше сборщик мусора не удалял старые, неиспользуемые копии данных, тем выше пики. Если мы используем персистентные структуры, то пикового использования памяти не наблюдается.
Как вы могли заметить, концепция иммутабельности становится невероятно привлекательной, если мы используем персистентность.
Пример: React DBMon Benchmark
Взяв за основу нашу предыдущую серию бенчмарков, мы решили обновить наш тест React DBMon, чтобы использовать Immutable.js там, где это потребуется. Поскольку DBMon фактически итак обновляет все данные после каждой итерации, не предвиделось никакой выгоды от переключения на React + Immutable.js: Immutable.js позволяет React предотвращать глубокие проверки равенства после изменения состояния; если все состояния обновляются после каждой итерации, то улучшение невозможно. Поэтому мы изменили наш пример таким образом, чтобы случайным образом пропустить изменения состояния:
После этого мы изменили структуру данных, содержащую образцы данных: обычный JavaScript массив мы заменили на список (Immutable List), который предоставляет Immutable.js. Этот список передаётся в компонент для отрисовки в качестве параметра. Когда мы добавили в класс компонента PureRenderMixin, стали доступны более эффективные сравнения.
Это всё, что необходимо, чтобы увидеть прирост в этом случае. Если данные считаются неизменёнными, никаких дальнейших действий, чтобы отрисовать эту ветку в DOM дерево, не предпринимается.
Также, как и в наших предыдущих экспериментах, мы использовали browser-perf, чтобы зафиксировать различия. Вот итоговое время выполнения JavaScript кода:
Здесь вы можете посмотреть все результаты.
Отступление: Immutable.js в Auth0
Здесь, в Auth0, мы постоянно находимся в поиске новых инструментов, которые могли бы использовать. Immutable.js не является исключением. Она нашла своё применение в таких проектах, как Lock и Lock Passwordless. Обе библиотеки разработаны на React. Отрисовку React компонентов можно существенно ускорить, пользуясь преимуществами иммутабельности благодаря оптимизации, доступной для проверки равенства: когда два объекта ссылаются на один и тот же объект, и вы точно знаете, что этот объект иммутабелен, вы можете быть уверены, что данные, которые он содержит, не изменились. Поскольку React вызывает процесс перерисовки объектов после того, как убедится, что они были изменены, это устраняет необходимость в глубоких сравнениях значений.
Похожую оптимизацию можно реализовать и для приложений, разработанных на Angular.js.
А вам нравится React и Immutable.js? Присылайте нам своё резюме и укажите, в каких проектах вы уже участвовали, используя эти технологии.
Заключение
Благодаря функциональному программированию мы можем использовать и тестировать преимущества иммутабельности и множества других связанных с этим концепций. Истории успеха проектов, использующих Clojure, Scala и Haskell, привели к тому, что многие идеи, активно используемые в этих языках, получили более широкое распространение. Иммутабельность — одна из этих концепций: иммутабельные структуры данных с их явными преимуществами анализа, хранения, копирования и сопоставления нашли своё применение в некоторых конкретных случаях использования даже в браузере. И, как всегда, когда речь заходит об алгоритмах и структурах данных, чтобы выбрать подходящий инструмент, необходимо тщательно проанализировать каждый конкретный сценарий. Только приняв во внимания все аспекты, связанные с производительностью, использованием памяти, поведением кэша процессора и типами операций, которые будут производиться над данными, можно понять, станет ли иммутабельность преимуществом для вас. Использование Immutable.js с React является ярким примером того, какие огромные выгоды может принести проекту этот подход.
Если эта статья пробудила в вас интерес к функциональному программированию и к структурам данных в целом, я настоятельно рекомендую почитать книгу Криса Окасаки «Чисто функциональные структуры данных», это поможет понять, как на самом деле работают функциональные структуры данных и как их можно эффективно использовать. Наслаждайтесь!
Слушайте наш подкаст в iTunes и SoundCloud, читайте нас на Medium, контрибьютьте на GitHub, общайтесь в группе Telegram, следите в Twitter и канале Telegram, рекомендуйте в VK и Facebook.
