Чистота функций

Наряду с функциями высшего порядка еще одной отличительной чертой функционального программирования является трепетное отношение к побочным эффектам (side effects). "Should I be pure or impure?" - этот вопрос волнует не одно поколение функциональных программистов, и сегодня мы рассмотрим аргументы в пользу обеих сторон, а выбор предоставим вам.

Чистота функций (functional purity)

Функция называется чистой (pure), если 1) для одного и того же набора аргументов она всегда возвращает один и тот же результат, 2) единственный результат работы функции - ее возвращаемое значение. Антонимом этого понятия является изменчивость (impurity). Примеры:

• Оператор сложения целых чисел, синус, да и вообще все детерминированные математические функции являются чистыми.
• Функция получения текущего времени, генератор случайных чисел не являются чистыми, так их два последовательных вызова практически всегда возвращают разные значения, нарушая условие №1.
• Любая работа с пользователем и любой ввод-вывод не являются чистыми, так как нарушают условие №2, порождая побочные эффекты.
• Оператор присваивания не является чистым, так как нарушает условие №2, изменяя состояние приложения.

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

Программирование без изменчивости

Дилемма между чистотой и изменчивостью чаще всего возникает тогда, когда между двумя частями алгоритма - P1 и P2 есть зависимость, то есть P2 использует результаты работы P1 (существуют и более сложные случаи зависимостей, но для краткости мы опустим их анализ). Для разрешения такой ситуации императивное программирование предлагает переменные - изменяемое состояние, которое используется в обеих частях алгоритма (mutable shared state). Функциональный подход заключается в выделении зависимой части в отдельную функцию и передаче ей измененного состояния в аргументах (как мы убедились в прошлом посте, благодаря функциональной композиции даже небольшие фрагменты программы можно выносить в независимые, повторно используемые функции).

Рассмотрим пример - наивное сложение чисел некоторого конечного списка. Это итеративный алгоритм, который перебирает список от начала до конца, на каждом шаге накапливая частичную сумму. Очевидно, между соседними итерациями цикла есть зависимость, так как та итерация, которая будет выполняться позже, использует результат работы предыдущей итерации - частичную сумму. Ниже приведены качественно разные варианты реализации алгоритма (если вы не знакомы с F#, то в объеме, необходимом для понимания кода, приведенного ниже, его можно освоить, прочитав ознакомительный пост; реализации приведены лишь с иллюстративной целью - в базовых библиотеках обоих языков есть встроенные функции, которые можно использовать для достижения нужного результата):

 int SumAll(IEnumerable<int> list)

 {

     var sum = 0;

     foreach (var element in list)

         sum += element;

     return sum;

 }

 let sumAll list = 

     let rec fold f acc list = 

         match list with

         | h::t -> fold f (f acc h) t

         | [] -> acc

     fold (+) 0 list

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

Полезные свойства чистых программ

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

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

Компьютеру чистота и ссылочная прозрачность помогают тем, что можно применять автоматические рассуждения для анализа различных аспектов программы. Разрабатывая программу в чистом стиле, мы явно указываем зависимости между фрагментами нашего алгоритма, что делает возможным математически обоснованными оптимизирующие переупорядочение, распараллеливание и кэширование фрагментов. Еще из интересных особенностей применения компьютерных рассуждений можно отметить облегчение реализации live updates, обновлений программы прямо во время работы (как, например, это сделано в Erlang).

Недостатки чистых программ

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

Следующий недостаток непосредственно вытекает из неизменности состояния - массивы и структуры, представляющие сущности предметной области, создаются "на один раз" и, при необходимости быть измененными, пересоздаются заново. Так, например, упоминаемая в одном из предыдущих постов быстрая сортировка на языке Haskell: qsort (x:xs) = qsort(filter (< x) xs) ++ [x] ++ qsort(filter (>= x) xs) требует больше памяти, чем ее in-place эквивалент на языке C. Вот почему так сложилось, что исторически впервые сборщик мусора появился в функциональных языках - в императивных программах объекты обычно долгоживущие, ибо передаются по ссылке, а в функциональных языках большой процент кода обычно написан в чистом стиле (что, как показано выше, подразумевает более частую аллокацию/деаллокацию структур), поэтому явное управление памятью оказывается слишком неудобным.

Чаще всего получается, что чистая реализация алгоритма по крайней мере не уступает императивным эквивалентам по скорости написания и сложности поддержки, но иногда бывает, что императивная версия оказывается удобнее для записи и сопровождения. Эту тему отлично раскрыл Мэтью Подвысоцки в своем посте "Functionally Implementing Intersperse"

Заключение

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

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

Материалы для чтения

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

Работу с данными (функциональные структуры данных, применимость списков, сопоставление с образцом/активные образцы) мы намеренно оставляем за кадром, чтобы не выходить за рамки этого блога, поэтому по этой теме мы лишь дадим лишь ссылки на полезные документы:

1. "Purely Functional Data Structures", Chris Okasaki, 1996

2. "List comprehension", from Wikipedia, the free encyclopedia

3. "Pattern matching", from Wikipedia, the free encyclopedia

4. "Extensible Pattern Matching via a Lightweight Language", Don Syme et al., 2007