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

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

Математика

У математиці функція — відповідність між елементами двох множин, встановлена за таким правилом, що кожному елементу першої множини відповідає один і тільки один елемент другої множини.

Вікіпедія

Суть поняття функції в тому, що вона, будучи сполучною ланкою між множинами значень, пов'язує з першою тільки один елемент другої множини.

Існують різні способи запису функції:

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

y = f(x) читається як: y дорівнює f від x. 

Інше представлення цього функціонального запису — набір зв'язок відповідно до визначення функції:

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

2) Запис у вигляді стрілочної функції:

f: X → Y

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

ПРОГРАМУВАННЯ

Функція називається чистою, якщо вона відповідає функції в математичному сенсі: пов'язує кожне можливе вхідне значення з вихідним, і більше нічого. Зокрема:

  • Вона не містить ніяких інших обчислень (побічні ефекти при наявності зазвичай можна помітити). Тобто звернення до неї не чинить ніякого помітного ефекту, окрім результату, який вона повертає. Вона також не може, наприклад, здійснювати запис на диск чи виводити результати на екран, підключатися до бази даних, читати файли, надсилати пакети мережею.
  • Вона не залежить ні від чого, крім власних параметрів. Тобто при виклику в різних контекстах або в різний час з одними й тими самими аргументами буде отримано один і той самий результат.

Давайте визначимо ці твердження як властивості:

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

Тому інформатика загалом намагається задіяти всі властивості функції з математики.

ЧОМУ САМЕ ЧИСТІ ФУНКЦІЇ?

Композиція

Перш за все, справа саме в ній! При наявності двох або більше функцій, за допомогою композиції їх можна об'єднати в одну, отримавши нову результуючу функцію. Це не працює з недетермінованими ефектами, але чисті функції можна компонувати. Використання композиції дозволяє написати мінімальні функції та скомпонувати їх у більш розгорнуту для проведення необхідних обчислень.

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

Щоб написати чисту функцію зі складною структурою і міркувати про її поведінку, потрібна незмінна структура даних. Якщо структура даних незмінна, підтвердити властивості нової функції набагато простіше.

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

У програмуванні багато структур є рекурсивно визначеними. Їхні частини мають ті самі характеристики і властивості, що й цілі структури.

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

Приклади таких структур:

  • Бінарні дерева.
  • Множини (так, їх також можна визначати рекурсивно).

Прозорість посилань

Прозорість посилань означає, що функцію можна замінити її значенням без зміни поведінки програми. Будь-яка чиста функція є посилально прозорою за визначенням. Також будь-які складові частини чистої функції за замовчуванням є чистими й посилально прозорим.

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

  • Мемоізація.
  • Згортка констант у JIT-компіляторах (та інші правила спеціалізації в компіляторах).
  • Правила спеціалізації/перевизначення в компіляторах для об'єктів з теорії категорій. Багато категоріальних об'єктів, такі як моноїд або функтори, легко вироджуються в набір елементарних та інтуїтивних функцій.
  • Розпаралелювання.

Завершення

Парадигма функціонального програмування намагається трактувати будь-яку програму як чисту функцію. Це дозволяє поглянути на розробку програм і алгоритмів з нової точки зору. Будь-яка функція має унікальні властивості. Отже, програми стають об'єктом математичного доказу. Залишається лише довести необхідну властивість!

І навіть верифікація програми переходить із простого написання юніт-тестів у сферу частково формальної верифікації. Якщо програма є функцією, то вона має властивості, які можна верифікувати за допомогою спеціальних програм (чекерів) або засобами автоматичного доведення теорем.