Чистые функции и функциональное программирование

22 апреля
Денис Душин, Senior Java-разработчик
Чистые функции и функциональное программирование
Сегодня о функциональном программировании, его концепциях и практическом применении говорят очень много. Я как большой поклонник этого направления хочу поделиться взглядом на функции и чистые функции. В статье кратко изложу, почему, на мой взгляд, их стоит использовать.

Математика

В математике функция — соответствие между элементами двух множеств, установленное по такому правилу, что каждому элементу первого множества соответствует один и только один элемент второго множества.

Википедия

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

Существуют различные способы записи функции:

1) Функциональная запись или запись через равенство:

y = f(x) читается как: y равно f от x. 

Другое представление этой функциональной записи — набор связок в соответствии с определением функции:

{(x, y) } →{(x, f(x)) }

2) Запись в виде стрелочной функции

f: X → Y

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

Программирование

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

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

Давайте определим эти утверждения как свойства:

  1. Функция возвращает только одно значение.
  2. Функция всегда возвращает один и тот же результат при вызове с тем же самым списком аргументов.
  3. Функция не имеет ни состояния, ни доступа к внешнему состоянию. Каждый раз при вызове функции результат будет одинаковым с одним и тем же списком аргументов.
  4. Функция не зависит от контекста. Неважно, сколько раз и в каких контекстах она будет вызвана: чистая функция всегда даст один и тот же результат.

Поэтому информатика в целом пытается задействовать все свойства функции из математики.

Почему именно чистые функции?

Композиция 

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

Неизменяемые структуры данных

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

Структурная индукция

В программировании многие структуры рекурсивно определены. Их части обладают теми же характеристиками и имеют те же свойства, что и целые структуры.

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

Примеры таких структур:

  • Бинарные деревья.
  • Множества (да, их также можно определять рекурсивно).

Ссылочная прозрачность

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

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

  • Мемоизация.
  • Свертка констант в JIT-компиляторах (и другие правила специализации в компиляторах).
  • Правила специализации/переопределения в компиляторах для объектов из теории категорий. Многие категориальные объекты, такие как моноиды или функторы, легко вырождаются в набор элементарных и интуитивных функций.
  • Распараллеливание.

Завершение

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

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