Основи функціонального програмування

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

Функціональне програмування (functional programming) спирається на теорію рекурсивних функцій і лямбда-числення Алонзо Черча. В ньому акцент робиться на залежність між функціями та даними. Функціональна програма складається з сукупності визначень функцій, які у свою чергу є викликами інших функцій і операторів, що управляють послідовністю викликів.

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

Енциклопедія Wiki дає наступне визначення:

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

 

Свою історію функціональне програмування веде з 1958 року, коли Джон Маккарті створив мову Лісп (LISP - LISt Processing – мова обробки списків) - першу в світі мову функціонального програмування. До 80-х років минулого століття цей напрям досить добре розвивався. Була створена ціла низка мов функціонального програмування, а також було значно вдосконалено сам Лісп. З появою персональних комп’ютерів (ПК) і поширенням об’єктно-орієнтованої парадигми інтерес до функціонального програмування різко знизився. Перші ПК не мали достатньо обчислювальних ресурсів і, в той же час, вимагали зручного інтерфейсу користувача. Дейкстра зазначав, що поява ПК відкинула програмування на 15 років назад. Програмісти знову почали рахувати байти і такти процесора. Поступово на перший план виходить об'єктно-орієнтоване програмування, яке є дійсно зручним для створення графічних інтерфейсів. Декларативні мови застосовувалися переважно в університетах, наукових центрах, а також в тих компаніях, які займалися складними задачами і мали досить потужні обчислювальні ресурси.

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

Основна особливість функціональних мов – відсутність типів даних. (безтиповість).

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

1.) Аплікативність: програма є вираз, який складається із застосування функцій до аргументів.

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

Настроюваність активно використовується в такому напрямі програмування, як генеруюче програмування (generic programming,). Основна задача, вирішувана в рамках цього напряму - створення максимально універсальних бібліотек, орієнтованих на вирішення задач, які часто зустрічаються (обробка агрегатних даних; потокове введення-виведення; взаємодія між програмами, написаними на різних мовах, універсальні віконні бібліотеки). Ці напрями найбільш яскраво представлені в STL - стандартній бібліотеці шаблонів мови С++ та в реалізації платформи DOT.NET.

Сфера застосування.

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

Найбільш відома мова функціонального програмування – Lisp (1958) і його нащадки, найбільш сучасні з яких - Scheme і Common Lisp.

Основи Лісп

Базис Ліспу досить лаконічний — атоми і структури з найпростіших бінарних вузлів, а також декілька базових функцій і функціоналів. Базис містить вбудовані (примітивні) функції, які аналізують та будують будь-які структурні значення (atom, eq, cons, car, cdr), і вбудовані спеціальні функції і функціонали, які управляють обробкою структур, що представляють обчислювані вирази (quote, cond, lambda, label, eval). Над базисом будуються прості формули у вигляді списків, де перший елемент — функція, інші — її аргументи, у тому числі змінні, реалізовані за допомогою різних варіантів стека або асоціативного списку. Вся решта механізмів обчислення і перетворення формул може бути зведена до цього базису, розглядатися як його варіант або розширення.

Програма на Ліспі – це функція, яка застосовується до вхідних даних (аргументів) та повертає результат:

output = program(input)

Не дивлячись на важливість, у нас Лісп не отримав поширення, а його застосування обмежено лише кількома науковими проектами.

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