Функційне програмування — парадигма програмування, яка розглядає програму як обчислення математичних функцій та уникає станів та змінних даних. Функційне програмування наголошує на застосуванні функцій, на відміну від імперативного програмування, яке наголошує на змінах в стані та виконанні послідовностей команд.

Іншими словами, функційне програмування є способом створення програм, в яких єдиною дією є виклик функції, єдиним способом розбиття програми є створення нового імені функції та задання для цього імені виразу, що обчислює значення функції, а єдиним правилом композиції є оператор суперпозиції функцій. Жодних комірок пам'яті, операторів присвоєння, циклів, ні, тим більше, блок-схем чи команд переходу.Хендерсон 1983, Предисловие редактора перевода

Ширша концепція функційного програмування визначає набір спільних правил та тем замість переліку відмінностей від інших парадигм. До таких, що часто вважаються важливими, належать функції вищого порядкуВольфенгаген В. Э. Конструкции языков программирования. Приемы описания. — М: АО «Центр ЮрИнфоР», 2001. — 276 с ISBN 5-89158-079-9. та функції першого класу: замикання, та рекурсія. До інших поширених можливостей функційних мов програмування належать продовження, , нечіткі обчислення (включно з, але, не обмежуючись, лінивими обчисленнями), та монади.

Основну увагу функційним мовам програмування, особливо, «чисто функційним», приділили академічні дослідники. Однак, до відомих функційних мов програмування, які використовуються в промисловості та комерційному програмуванні належить Erlang (паралельні програми), R (статистика), Mathematica (символьні обчислення), J та K (фінансовий аналіз), та спеціалізовані мови програмування наприклад XSLT. Істотний вплив на функційне програмування здійснило лямбда-числення, мова програмування APL, мова програмування Lisp та новіша мова програмування Haskell.

Функційне програмування часто називають «функціональним», хоча насправді функціонально-орієнтоване програмування — це інша категорія, де основою є компонування програм у ряд програмних продуктів.

Мови програмування Найвідомішими мовами функційного програмування є: XQuery; Haskell — чиста функційна мова. Названа на честь Гаскелла Каррі; Lisp (Джон Маккарті, 1958, має безліч нащадків, найсучасніші з яких — Scheme і Common Lisp); ML (Робін Мілнер, 1979, з нині використовуваних діалектів відомі Standard ML і Objective Caml); Miranda (Девід Тернер, 1985, який згодом дав розвиток мові Haskell); Erlang — (Joe Armstrong, 1986) функційна мова з моделлю акторів. Nemerle — гібридна функційно/імперативна мова; F# — функційна мова для платформи .NET; Scala — гібридна об'єктно-орієнтована/функційна мова для платформи Java; Clojure — функційна мова для платформи Java.

Ще не повністю функційні початкові версії Lisp і APL зробили особливий внесок до створення і розвитку функційного програмування. Пізніші версії Lisp, такі як Scheme, а також різні варіанти APL, підтримували властивості і концепції функційної мови.

Як правило, інтерес до функційних мов програмування, особливо чисто функційних, був більше науковий, ніж комерційний. Проте, таким примітним мовам як Erlang, OCaml, Haskell, Scheme (після 1986), а так само специфічним R (статистика), Mathematica (символічна математика), J і K (фінансовий аналіз), і XSLT (XML) знаходили застосування в індустрії комерційного програмування. Такі широко поширені декларативні мови як SQL і Lex/Yacc містять деякі елементи функційного програмування, вони остерігаються використовувати змінні.

Історія Лямбда-числення стало теоретичною базою для опису і обчислення функцій. Будучи математичною абстракцією, а не мовою програмування, воно склало базис майже всіх мов функційного програмування на сьогодні. Подібне теоретичне поняття, комбінаторна логіка, є більш абстрактним, ніж λ-числення і було створено раніше. Ця логіка використовується в деяких езотеричних мовах, наприклад в Unlambda. І λ-числення, і комбінаторна логіка були розроблені для більш ясного й точного опису принципів і основ математики + перевидання ISBN 978-5-382-01266-7; 2011 .

Першою функційною мовою був Lisp, створений Джоном Маккарті в період його роботи в Массачусетському технологічному інституті в кінці п'ятдесятих і реалізований, спочатку, для . Lisp визначив множину понять функційної мови, хоча при цьому сповідував не тільки парадигму функційного програмування . Подальшим розвитком Ліспу стали такі мови як Scheme і Dylan.

Мова обробки інформації (, IPL) іноді визначається як найперша машинно-функційна мова У своїх мемуарах Герберт Саймон (1991), Models of My Life pp. 189–190 ISBN 0-465-04640-1 стверджує, що його, Al. Ньюелл, і Кліфф Шоу яких «часто називають батьками штучного інтелекту» за написання програми автоматично доводить теореми з Principia Mathematica. Для того, щоб досягти цього, вони повинні були придумати мову і парадигму, яку, ретроспективно, можна розглядати як функційне програмування. . Це мова ассемблерного типу для роботи зі списком символів. У ньому було поняття «генератора», який використовував функцію як аргумент, а також, оскільки це мова ассемблерного рівня, він може позиціонуватися як мова, що має функції вищого порядку. Однак, в цілому IPL акцентовано на використання імперативних понять.

Кеннет Айверсон розробив мову APL на початку шістдесятих, продокоментувавши її в своїй книзі A Programming Language (ISBN 9780471430148) . APL справив значний вплив на мову , створену Джоном Бекусом. На початку дев'яностих Айверсон і створили наступника APL — мова програмування J. У середині дев'яностих , який раніше працював з Айверсоном, створив мову K, яка згодом використовувалась у фінансовій індустрії на комерційній основі.

У сімдесятих в університеті Единбурга Робін Мілнер створив мову ML, а Девід Тернер починав розробку мови SASL в університеті Сент-Ендрюса і, згодом, мову Miranda в університеті міста Кент. У кінцевому підсумку на основі ML були створені кілька мов, серед яких найбільш відомі Objective Caml і Standard ML. Також в сімдесятих здійснювалася розробка мови програмування, побудованої за принципом Scheme (реалізація не лише функційної парадигми), що отримала опис у відомій роботі «Lambda Papers», а також у книзі вісімдесят п'ятого року «Structure and Interpretation of Computer Programs», в якій принципи функційного програмування були донесені до більш широкої аудиторії.

У вісімдесятих Пер Мартін-Леф створив інтуїціонистську теорію типів (також звану конструктивною). У цій теорії функційне програмування отримало конструктивний доказ того, що раніше було відомо як залежний тип. Це дало потужний поштовх до розвитку діалогового доказу теорем і до подальшого створення безлічі функційних мов.

Haskell був створений в кінці вісімдесятих у спробі поєднати безліч ідей, отриманих у ході дослідження функційного програмування.

Концепції Деякі концепції та парадигми специфічні для функційного програмування і в основному чужі імперативному програмуванню (включаючи об'єктно-орієнтоване програмування). Тим не менш, мови програмування звичайно являють собою гібрид декількох парадигм програмування, тому «здебільшого імперативні» мови програмування можуть використовувати які-небудь з цих концепцій.

Функції вищих порядків

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

Функції вищих порядків дозволяють використовувати каррінг — перетворення функції від пари аргументів у функцію, що бере свої аргументи по одному. Це перетворення отримало свою назву на честь Гаскелла Каррі.

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

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

Хоча більшість компіляторів імперативних мов програмування розпізнають чисті функції і видаляють загальні підвирази для викликів чистих функцій, вони не можуть робити це завжди для попередньо скомпільованих бібліотек, які, як правило, не надають цю інформацію. Деякі компілятори, такі як gcc, з метою оптимізації надають програмісту ключові слова для позначення чистих функцій GCC , Declaring Attributes of Functions . Fortran 95 дозволяє позначати функції як «pure» XL Fortran for AIX, V13.1 Language Reference, Pure procedures (Fortran 95)] .

Рекурсія

У функційних мовах цикл зазвичай реалізується у вигляді рекурсії. Власне, у функційної парадигми програмування немає такого поняття, як цикл. Рекурсивні функції викликають самі себе, дозволяючи операції виконуватися знову і знову. Для використання рекурсії може знадобитися великий стек, але цього можна уникнути в разі хвостової рекурсії. Хвостова рекурсія може бути розпізнана і оптимізована компілятором в код, одержуваний після компіляції, аналогічної ітерації в імперативній мові програмування. Tail call optimization Стандарти мови Scheme вимагають розпізнавати і оптимізувати хвостову рекурсію. Оптимізувати хвостову рекурсію можна шляхом перетворення програми в стилі використання продовжень при її компіляції, як один із способів. Revised5 Report on the Algorithmic Language Scheme, 3.5. Proper tail recursion

Рекурсивні функції можна узагальнити за допомогою функцій вищих порядків, використовуючи, наприклад, катаморфізм і анаморфізм (або «згортка» і «розгорнення»). Функції такого роду відіграють роль такого поняття, як цикл в імперативних мовах програмування.

Підхід до обчислення аргументів функційні мови можна класифікувати по тому, як обробляються аргументи функції в процесі її обчислення. Технічно відмінність полягає в денотаційній семантиці виразу. Наприклад, при строгому підході до обчислення виразу print (len ([2 +1, 3 * 2, 1/0, 5-4])) на виході буде помилка, оскільки в третьому елементі списку присутнє ділення на нуль. При нестрогому підході значенням виразу буде 4, оскільки для обчислення довжини списку значення його елементів, строго кажучи, не важливі і можуть взагалі не обчислюватися. При строгому (аплікативному) порядку обчислення заздалегідь підраховуються значення всіх аргументів перед обчисленням самої функції. При нестрогому підході (нормальний порядок обчислення) значення аргументів не обчислюються до тих пір, поки їх значення не знадобляться при обчисленні функції Н. А. Роганова функційне програмування: Навчальний посібник для студентів вищих навчальних закладів — М.: ГІНФО, 2002. — 260 с. Стор. 14 п. 3.1. Ледачі і енергійні обчислення .

Як правило, нестрогий підхід реалізується у вигляді редукції графа. Нестроге обчислення використовується за замовчуванням в декількох чисто функційних мовах, у тому числі Miranda, Clean і Haskell.

ФП в нефункційних мовах