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

30 април
Денис Душин, Senior Java разработчик
Чисти функции и функционално програмиране
Днес много се говори за функционалното програмиране, неговите концепции и практическо приложение. Като голям почитател на тази тенденция, искам да споделя малко повече за функциите и чистите функции. Статията ще разгледа накратко защо е добре да се използват и каква е ролята им.

МАТЕМАТИКА

В математиката функция е съответствие между елементи от две множества, установени чрез такова правило, че на всеки елемент от първото множество съответства един единствен елемент от второто.

Има различни нотации за описване на функция:

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

y = f (x) гласи: y е равно на f от x. 

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

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

2. Запис като функция със стрелка

f: X → Y

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

Чиста функция и ПРОГРАМИРАНЕ

Функцията се нарича чиста, ако съответства на функция в математическия смисъл: тя свързва всяка възможна входяща стойност с изходящата и с нищо друго. По-конкретно:

  • Тя не съдържа никакви други изчисления. Тоест - извикването й не предизвиква  други странични ефекти, с изключение на резултата, който връща. Функцията също не може да записва на диск или да показва резултати на екрана, да се свързва с база данни, да чете файлове, да изпраща пакети през мрежата.
  • Чистата функция не зависи от друго, освен от собствените си параметри. Тоест, когато се извиква в различен контекст или в различно време с едни и същи аргументи, ще се получи един и същ резултат.
  • Чистата функция (нямайки странични ефекти и връщайки винаги един и същи резултат, за едни и същи входни параметри), може да бъде заместена/заменена с резултата от изпълнението си, без това да промени логиката и резултата от програмата.

Нека дефинираме тези проявления като свойства:

  • Функцията връща само една стойност.
  • Функцията винаги връща един и същ резултат, когато се извиква със същия списък с аргументи.
  • Функцията няма нито състояние, нито достъп до външно състояние. Всеки път, когато се извика функцията, резултатът ще бъде един и същ за същия списък от аргументи.
  • Функцията не зависи от контекста. Няма значение колко пъти и в какъв контекст ще се извика: чистата функция винаги ще даде същия резултат.

Следователно - компютърните науки като цяло се опитват да използват всички свойства на функциите от математиката.

ЗАЩО ТОЧНО ЧИСТИ ФУНКЦИИ?

Композиция 

Това е крайъгълен камък! Ако имате две или повече функции, те могат да бъдат комбинирани/композирани в една нова функция. Функции със странични ефекти не могат да се композират и са недетерминирани. Но чистите функции са композируеми. Използването на композиция ви позволява да пишете малки (като размер) функции и да ги композирате в по-големи, за да извършите необходимите изчисления.

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

За да можете да напишете чиста функция със сложна структура и да разсъждавате за нейното поведение, са необходими неизменни структури от данни. Ако структурата от данните е неизменна, е много по-лесно да потвърдите свойствата на новата функция.

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

В програмирането много структури се дефинират рекурсивно. Техните части имат същите характеристики и същите свойства като цяло.

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

Примери за такива структури:

  • Двоични и други дървета.
  • Графи
  • Множества (да, те също могат да бъдат определени рекурсивно).
  • Дори масиви

Референтна прозрачност

Референтната прозрачност означава, че дадена функция може да бъде заменена със стойността си, без да се променя поведението на програмата. По дефиниция всяка чиста функция е референтно прозрачна. Всяка композиция на чисти функции по подразбиране също е чиста и следователно е референтно прозрачна.

Референтната прозрачност е следствие на това, че чистите функции са независими от контекста. Те играят значителна роля в програмната оптимизация. 

Примерни техники:

  • Мемоизация (техниката за запомняне на резултатите от функциите, вместо повторното им изпълнение).
  • „Сгъване“ на константи в JIT компилаторите  (и други правила за пренаписване и оптимизация).
  • Правила за предефиниране на обекти от теорията на категориите (моноиди, функтори).
  • Паралелизация

В заключение:

Парадигмата на функционалното програмиране се опитва да разглежда всяка програма като чиста функция. Това позволява да разглеждате разработването на програми и алгоритми от нова гледна точка. Всяка функция има уникални свойства. Следователно - програмите стават обект на математическо доказателство. Остава само да се докажат съответните свойства!

Дори верификацията на програмата след промени в нея може да премине от простото писане на тестове на ниво компоненти към областта на частично формалната проверка. Ако дадена програма е функция, тя има свойства, които могат да бъдат проверени с помощта на специални програми (тулове) или чрез софтуер за автоматично доказване на теореми.