Функціональне програмування — це розділ дискретної математики і парадигма програмування, в якій процес обчислення трактується як обчислення значень функцій у математичному розумінні останніх (на відміну від функцій як підпрограм в процедурному програмуванні).
Протиставляється парадигмі імперативного програмування, яка описує процес обчислень як послідовна зміна станів (у значенні, подібному такому в теорії автоматів). При необхідності, у функціональному програмуванні вся сукупність послідовних станів обчислювального процесу представляється явним чином, наприклад, як список.
Функціональне програмування передбачає обходитися обчисленням результатів функцій від вхідних даних і результатів інших функцій, і не передбачає явного зберігання стану програми. Відповідно, не припускає воно і змінюваність цього стану (на відміну від імперативного, де однією з базових концепцій є змінна, що зберігає своє значення і дозволяє змінювати його по мірі виконання алгоритму).
На практиці відмінність математичної функції від поняття «функції» в імперативному програмуванні полягає в тому, що імперативні функції можуть спиратися не тільки на аргументи, але і на стан зовнішніх по відношенню до функції змінних, а також мати побічні ефекти і змінювати стан зовнішніх змінних. Таким чином, в імперативному програмуванні при натисненні однієї і тієї ж функції з однаковими параметрами, але на різних етапах виконання алгоритму, можна отримати різні дані на виході з-за впливу на функцію стану змінних. А в функціональному мовою при виклику функції з одними і тими ж аргументами ми завжди отримаємо однаковий результат: вихідні дані залежать тільки від вхідних. Це дозволяє середовищ виконання програм на функціональних мовах кешувати результати функцій і викликати їх у порядку, що визначається алгоритмом і распараллеливать їх без яких-небудь додаткових дій з боку програміста (див. нижче Чисті функції).
λ-числення є основою для функціонального програмування, багато функціональні мови можна розглядати як «надбудову» над ними
Найбільш відомими мовами функціонального програмування є[]: LISP — (Джон Маккарті, 1958) і безліч його діалектів, найбільш сучасні з яких: Scheme Clojure Common Lisp Erlang — (Joe Armstrong, 1986) функціональний мову з підтримкою процесів. APL — попередник сучасних наукових обчислювальних середовищ, таких як MATLAB. ML (Робін Мілнер, 1979, з нині використовуються діалектів відомі Standard ML і Objective CAML). F# — функціональний мова сімейства ML для платформи .NET Scala Miranda (Девід Тернер, 1985, який згодом дав розвиток мові Haskell). Nemerle — гібридний функціонально/імперативний мову. XSLT[] і XQuery Haskell — чистий функціональний. Названий на честь Хаскелла Каррі.
Ще не повністю функціональні початкові версії і Lisp і APL внесли особливий внесок у створення і розвиток функціонального програмування. Більш пізні версії Lisp, такі як Scheme, а також різні варіанти APL підтримували всі властивості і концепції функціонального мови[].
Як правило, інтерес до функціональних мов програмування, особливо чисто функціональним, був скоріше науковий, ніж комерційний. Однак, такі примітні мови як Erlang, OCaml, Haskell, Scheme (після 1986), а також специфічні R (статистика), Wolfram (символьна математика), J і K (фінансовий аналіз), та XSLT (XML) знаходили застосування в індустрії комерційного програмування. Такі широко розповсюджені декларативні мови SQL і Lex/Yacc містять деякі елементи функціонального програмування, наприклад, вони остерігаються використовувати змінні. Мови роботи з електронними таблицями також можна розглядати як функціональні, тому що в осередках таблиць задається масив функцій, як правило залежать лише від інших осередків, а при бажанні змоделювати змінні доводиться вдаватися до можливостей імперативного мови макросів.
Деякі концепції і парадигми специфічні для функціонального програмування і в основному чужі імперативного програмування (включаючи об'єктно-орієнтоване програмування). Тим не менш, мови програмування зазвичай представляють собою гібрид декількох парадигм програмування, тому «здебільшого імперативні» мови програмування можуть використовувати які-небудь з цих концепцій.
Функції вищих порядків — це такі функції, які можуть приймати в якості аргументів і повертати інші функції.[] Математики таку функцію частіше називають оператором, наприклад, оператор взяття похідної або оператор інтегрування.
Функції вищих порядків дозволяють використовувати карринг — перетворення функції від пари аргументів у функцію, яка бере свої аргументи по одному. Це перетворення отримало свою назву на честь Х. Каррі.
Чистими називають функції, які не мають побічних ефектів введення-виведення і пам'яті (вони залежать тільки від своїх параметрів і повертають тільки свій результат). Чисті функції володіють декількома корисними властивостями, багато з яких можна використовувати для оптимізації коду: Якщо результат чистої функція не використовується, її виклик може бути видалений без шкоди для інших виразів. Результат виклику чистої функції може бути мемоизирован, тобто збережено у таблиці значень разом з аргументами виклику. Якщо функція викликається з цими ж аргументами, її результат може бути узятий прямо з таблиці, не вычисляясь (іноді це називається принципом прозорості посилань). Мемоизация, ціною невеликого витрати пам'яті, дозволяє істотно збільшити продуктивність і зменшити порядок зростання деяких рекурсивних алгоритмів. Якщо немає ніякої залежності за даними між двома чистими функціями, то порядок їх обчислення можна поміняти або розпаралелити (інакше кажучи обчислення чистих функцій задовольняє принципам thread-safe) Якщо мову не допускає побічних ефектів, то можна використовувати будь-яку політику обчислення. Це надає свободу компілятору комбінувати і реорганізовувати обчислення виразів у програмі (наприклад, виключити деревоподібні структури).
Хоча більшість компіляторів імперативних мов програмування розпізнають чисті функції і видаляють загальні подвираженія для дзвінків чистих функцій, вони не можуть робити це завжди для попередньо скомпільованих бібліотек, які, як правило, не надають цю інформацію. Деякі компілятори, такі як gcc, в цілях оптимізації надають програмісту ключові слова для позначення чистих функцій[]. Fortran 95 дозволяє позначати функції як «pure» (чисті)
У функціональних мовах цикл зазвичай реалізується у вигляді рекурсії. Строго кажучи, у функціональній парадигмі програмування немає такого поняття, як цикл. Рекурсивні функції викликають самі себе, дозволяючи операції виконуватися знову і знову. Для використання рекурсії може знадобитися великий стек, але цього можна уникнути у випадку хвостової рекурсії. Хвостова рекурсія може бути розпізнана і оптимізована компілятором в код, одержуваний після компіляції аналогічної ітерації в імперативному мовою програмування.[] Стандарти мови Scheme вимагають розпізнавати і оптимізувати хвостову рекурсію. Оптимізувати хвостову рекурсію можна шляхом перетворення програми в стилі використання продовжень при її компіляції, як один із способів.[]
Рекурсивні функції можна узагальнити за допомогою функцій вищих порядків, використовуючи, наприклад, катаморфизм і анаморфізм (або «згортка» і «розгортка»). Функції такого роду відіграють роль такого поняття як цикл в імперативних мовах програмування
Функціональні мови можна класифікувати по тому, як обробляються аргументи функції в процесі її обчислення. Технічно відмінність полягає в денотаційної семантики вираження. Наприклад, при строгому підході до обчислення виразу
print(len([2+1, 3*2, 1/0, 5-4]))
на виході буде помилка, так як в третьому елементі списку присутнє ділення на нуль. При спрощеному підході значенням виразу буде 4, оскільки для обчислення довжини списку значення його елементів, строго кажучи, не важливі і можуть взагалі не обчислюватися. При строгому (аппликативном) порядок обчислення заздалегідь підраховуються значення всіх аргументів перед обчисленням самої функції. При спрощеному підході (нормальний порядок обчислення) значення аргументу не обчислюються до тих пір, поки їх значення не знадобиться при обчисленні функції[].
Як правило, суворий підхід реалізується у вигляді редукції графа. Нестроге обчислення використовується за замовчуванням в декількох чисто функціональних мовах, у тому числі Miranda, Clean і Haskell
Принципово немає перешкод для написання програм у функціональному стилі на мовах, які традиційно не вважаються функціональними, точно так само, як програми в об'єктно-орієнтованому стилі можна писати на структурних мовами. Деякі імперативні мови підтримують типові для функціональних мов конструкції, такі як функції вищого порядку і списковые включення (list comprehensions), що полегшує використання функціонального стилю в цих мовах. Прикладом може бути функціональне програмування на Python. Іншим прикладом є мова Ruby, який має можливість створення як lambda-об'єктів, так і можливість організації анонімних функцій вищого порядку через блок з допомогою конструкції yield.
У мові C покажчики на функцію в якості типів аргументів можуть бути використані для створення функцій вищого порядку. Функції вищого порядку і відкладена списковий структура реалізовані в бібліотеках С++. У мові C# версії 3.0 і вище можна використовувати λ-функції для написання програми у функціональному стилі. У складних мовах, типу Алгол-68, наявні засоби метапрограммирования (фактично, доповнення мови новими конструкціями) дозволяють створити специфічні для функціонального стилю об'єкти даних і програмні конструкції, після чого можна писати функціональні програми з їх використанням
Імперативні програми мають схильність акцентувати послідовності кроків для виконання якоїсь дії, а функціональні програми до розташування і композиції функцій, часто не позначаючи точної послідовності кроків. Простий приклад двох рішень однієї задачі (використовується один і той же мова Python) ілюструє це.
# імперативний стиль target = [] # створити порожній список for item in source_list: # для кожного елемента вихідного списку trans1 = G(item) # застосувати функцію G() trans2 = F(trans1) # застосувати функцію F() target.append(trans2) # додати перетворений елемент у список
Функціональна версія виглядає по-іншому:
# функціональний стиль # мови ФП часто мають вбудовану функцію compose() compose2 = lambda A, B: lambda x: A(B(x)) target = map(compose2(F, G), source_list)
На відміну від імперативного стилю, що описує кроки, що ведуть до досягнення мети, функціональний стиль описує математичні відносини між даними і метою.
Основною особливістю функціонального програмування, що визначає як переваги, так і недоліки даної парадигми, є те, що в ній реалізується модель обчислень без станів. Якщо імперативна програма на будь-якому етапі виконання має стан, тобто сукупність значень всіх змінних, і виробляє побічні ефекти, то чисто функціональна програма ні цілком, ні частинами стану не має побічних ефектів не виробляє. Те, що в імперативних мовах робиться шляхом присвоювання значень змінним функціональних досягається шляхом передачі виразів параметри функцій. Безпосереднім наслідком стає те, що чисто функціональна програма не може змінювати вже наявні в неї дані, а може лише породжувати нові шляхом копіювання і/або розширення старих. Наслідком того ж є відмова від циклів на користь рекурсії.
Приваблива сторона обчислень без станів — підвищення надійності коду за рахунок чіткої структуризації та відсутності необхідності відстеження побічних ефектів. Будь-яка функція працює тільки з локальними даними і працює з ними завжди однаково, незалежно від того, де, як і за яких обставин вона викликається. Неможливість мутації даних при користуванні ними в різних місцях програми виключає появу труднообнаруживаемых помилок (таких, наприклад, як випадкове присвоювання невірного значення глобальної змінної в імперативній програмі).
Оскільки функція у функціональному програмуванні не може породжувати побічні ефекти, змінювати об'єкти не можна як усередині області видимості, так і зовні (на відміну від імперативних програм, де одна функція може встановити яку-небудь зовнішню змінну, считываемую другою функцією). Єдиним ефектом обчислення функції є зворотний їй результат, і єдиний фактор, що робить вплив на результат — це значення аргументів.
Таким чином, є можливість протестувати кожну функцію в програмі, просто обчисливши її від різних наборів значень аргументів. При цьому можна не турбуватися ні про виклик функцій в правильному порядку, ні про правильному формуванні зовнішнього стану. Якщо будь-яка функція в програмі проходить модульні тести, то можна бути впевненим в якості всієї програми. В імперативних програмах перевірка повертає значення функції недостатня функція може модифікувати зовнішнє стан, який теж потрібно перевіряти, чого не потрібно робити у функціональних програмах
Традиційно згадуваної позитивною особливістю функціонального програмування є те, що воно дозволяє описувати програму в так званому «декларативний» вигляді, коли жорстка послідовність виконання багатьох операцій, необхідних для обчислення результату, в явному вигляді не задається, а формується автоматично в процесі обчислення функцій. Це обставина, а також відсутність станів дає можливість застосовувати до функціональним програмам досить складні методи автоматичної оптимізації.
Ще однією перевагою функціональних програм є те, що вони надають найширші можливості для автоматичного розпаралелювання обчислень. Оскільки відсутність побічних ефектів гарантовано, у будь-якому виклику функції завжди допустиме паралельне обчислення двох різних параметрів — порядок їх обчислення не може вплинути на результат виклику.
Недоліки функціонального програмування випливають з тих же самих його особливостей. Відсутність присвоювань та заміна їх на породження нових даних приводять до необхідності постійного виділення і автоматичного звільнення пам'яті, тому в системі виконання функціональної програми обов'язковим компонентом стає високоефективний збирач сміття. Нестрога модель обчислень призводить до непередбачуваного порядку виклику функцій, що створює проблеми при вводі-виводі, де порядок виконання операцій важливий. Крім того, очевидно, функції введення в своєму природному вигляді (наприклад, getchar із стандартної бібліотеки мови C) не є чистими, оскільки здатні повертати різні значення для одних і тих же аргументів, і для усунення цього потрібні певні хитрощі.
Для подолання недоліків функціональних програм вже перші мови функціонального програмування включали не тільки чисто функціональні засоби, але і механізми імперативного програмування (присвоювання, цикл «неявний PROGN» були вже в LISPе). Використання таких засобів дозволяє вирішити деякі практичні проблеми, але означає відхід від ідей (і переваг) функціонального програмування і написання імперативних програм на функціональних мовах. В чистих функціональних мовах ці проблеми вирішуються іншими засобами, наприклад, в мові Haskell введення-виведення реалізований за допомогою монад — нетривіальною концепції, запозиченої з теорії категорій.
