Функційне програмування: відмінності між версіями

* [[Nemerle]] — гібридна функціональнофункційно/імперативна мова.

[[Лямбда-числення]] стало теоретичною базою для опису і обчислення функцій. Будучи математичною [[Абстракція|абстракцією]], а не [[Мова програмування|мовою програмування]], воно склало базис майже всіх мов функціональногофункційного програмування на сьогодні. Подібне теоретичне поняття, [[комбінаторна логіка]], є більш абстрактним, ніж λ-числення і було створено раніше. Ця логіка використовується в деяких езотеричних мовах, наприклад в [[Unlambda]]. І λ-числення, і комбінаторна логіка були розроблені для більш ясного й точного опису принципів і основ математики<ref> {{книга|автор = [[Пенроуз, Роджер|Роджер Пенроуз]]|частина = Глава 2: Лямбда-числення Черча|заголовок = Новий розум короля. Про комп'ютери, мисленні і законах фізики|оригінал = The Emperors New Mind: Concerning Computers, Minds and The Laws of Physics|видавництво = Едіторіал УРСС|рік = 2003|isbn = 5-354-00005-X}} + перевидання ISBN 978-5-382-01266-7; 2011 </ref>.

Першою функціональноюфункційною мовою був [[Lisp]], створений [[Джон МакКарті|Джоном МакКарті]] в період його роботи в [[Массачусетський технологічний інститут|Массачусетському технологічному інституті]] в кінці п'ятдесятих і реалізований, спочатку, для {{Не перекладено|IBM 700/7000|||IBM 700/7000 series}}. Lisp визначив множину понять функціональноїфункційної мови, хоча при цьому сповідував не тільки парадигму функціональногофункційного програмування {{sfn|J. Harrison|1997|loc = Гл. 3. λ-числення як мова програмування}}. Подальшим розвитком Ліспу стали такі мови як [[Scheme]] і [[Dylan (мова програмування)|Dylan]].

Мова обробки інформації (Information Processing Language}}, IPL) іноді визначається як найперша машинно-функціональнафункційна мова<ref> У своїх мемуарах [[Герберт Саймон]] (1991),'' Models of My Life'' pp. 189–190 ISBN 0-465-04640-1 стверджує, що його, Al. Ньюелл, і Кліфф Шоу яких «часто називають батьками штучного інтелекту» за написання програми {{не перекладено|Logic Theorist}} автоматично доводить теореми з ''[[Principia Mathematica]]''. Для того, щоб досягти цього, вони повинні були придумати мову і парадигму, яку, ретроспективно, можна розглядати як функціональнефункційне програмування. </Ref>. Це мова [[Мова асемблера|ассемблерного]] типу для роботи зі списком символів. У ньому було поняття «генератора», який використовував функцію як аргумент, а також, оскільки це мова ассемблерного рівня, він може позиціонуватися як мова, що має функції вищого порядку. Однак, в цілому IPL акцентовано на використання імперативних понять<ref> [http://hopl.murdoch.edu.au/showlanguage.prx?exp=13&language=IPL History of Programming Languages: IPL] </ref>.

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

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

[[Haskell]] був створений в кінці вісімдесятих у спробі поєднати безліч ідей, отриманих у ході дослідження функціональногофункційного програмування.<ref Name="hudak1989"> {{cite journal|author = {{Не перекладено| Хьюдак Пол|Пол Хьюдак|en|Paul Hudak}}|title = Conception, evolution, and application of functional programming languages ​​| journal = [[Association for Computing Machinery|ACM]] Computing Surveys|volume = 21|issue = 3|pages = 359 −411|month = September|year = 1989|url = }} </ref>

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

Функції вищих порядків&nbsp;— це такі функції, які можуть приймати як аргументи і повертати інші функції.<ref Name="functional"> [http://wm-help.net/books/book/49.html Завантажити PDF: "Техніки функціональногофункційного програмування, В.&nbsp;А.&nbsp;Потапенко «стор. 8» Функції вищих порядків "]. </ref> Математики таку функцію частіше називають [[оператор (математика) | оператором]], наприклад, оператор взяття похідної або інтегральний оператор.

У функціональнихфункційних мовах [[Цикл (програмування)|цикл]] зазвичай реалізується у вигляді рекурсії. Строго кажучи, в функціональноїфункційної парадигми програмування немає такого поняття, як цикл. Рекурсивні функції викликають самі себе, дозволяючи операції виконуватися знову і знову. Для використання рекурсії може знадобитися великий [[стек]], але цього можна уникнути в разі [[Хвостова рекурсія | хвостової рекурсії]]. Хвостова рекурсія може бути розпізнана і оптимізована компілятором в код, одержуваний після компіляції, аналогічної ітерації в імперативній мові програмування.<ref> [Http://c2.com/cgi/wiki?TailCallOptimization Tail call optimization] </ref> Стандарти мови Scheme вимагають розпізнавати і оптимізувати хвостову рекурсію. Оптимізувати хвостову рекурсію можна шляхом перетворення програми в стилі використання продовжень при її компіляції, як один із способів.<ref> [Http://www.schemers.org/Documents/Standards/R5RS/ Revised5 Report on the Algorithmic Language Scheme, 3.5. Proper tail recursion] </ref>

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

на виході буде помилка, оскільки в третьому елементі списку присутнє ділення на нуль. При нестрогому підході значенням виразу буде 4, оскільки для обчислення довжини списку значення його елементів, строго кажучи, не важливі і можуть взагалі не обчислюватися. При строгому (аплікативному) порядку обчислення заздалегідь підраховуються значення всіх аргументів перед обчисленням самої функції. При нестрогому підході (нормальний порядок обчислення) значення аргументів не обчислюються до тих пір, поки їх значення не знадобляться при обчисленні функції<ref name="lenivie">'' Н.&nbsp;А.&nbsp;Роганова'' Функціональнефункційне програмування: Навчальний посібник для студентів вищих навчальних закладів&nbsp;— М.: ГІНФО, 2002.&nbsp;— 260 с. Стор. 14 п. 3.1. Ледачі і енергійні обчислення </ref>.

Як правило, нестрогий підхід реалізується у вигляді редукції графа. Нестроге обчислення використовується за замовчуванням в декількох чисто функціональнихфункційних мовах, у тому числі [[Міранда (мова програмування) | Miranda]], [[Clean]] і [[Haskell]].{{fact}}

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

Принципово немає перешкод для написання програм у функціональномуфункційному стилі на мовах, які традиційно не вважаються функціональнимифункційними, точно так само, як програми в [[Об'єктно-орієнтоване програмування|об'єктно-орієнтованому]] стилі можна писати на структурних мовах. Деякі імперативні мови підтримують типові для функціональнихфункційних мов конструкції, такі як функції вищого порядку і спискові включення (list comprehensions), що полегшує використання функціональногофункційного стилю в цих мовах. Прикладом може бути програмування на мові [[Python]].

У мові [[Сі (мова програмування)|C]] покажчики на функцію як типи аргументів можуть бути використані для створення функцій вищого порядку. Функції вищого порядку і відкладена списковому структура реалізовані в бібліотеках [[C++]]. У мові [[C Sharp|C #]] версії 3.0 і вище можна використовувати λ-функції для написання програми в функціональномуфункційному стилі. У складних мовах, типу [[Алгол-68]], наявні засоби метапрограмування (фактично, доповнення мови новими конструкціями) дозволяють створити специфічні для функціональногофункційного стилю об'єкти даних і програмні конструкції, після чого можна писати функціональніфункційні програми з їх використанням.

Імперативні програми мають схильність акцентувати послідовності кроків для виконання якоїсь дії, а функціональніфункційні програми до розташування і композиції функцій, часто не позначаючи точної послідовності кроків. Простий приклад двох рішень однієї задачі (використовується одна і та ж мова [[Python]]) ілюструє це.

Функціональнафункційна версія виглядає по-іншому:

# Функціональнийфункційний стиль

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

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

Оскільки функція у функціональномуфункційному програмуванні не може породжувати побічні ефекти, змінювати об'єкти не можна як усередині області видимості, так і зовні (на відміну від імперативних програм, де одна функція може встановити яку-небудь зовнішню змінну, що зчитується іншою функцією). Єдиним ефектом від обчислення функції є повернений їй результат, і єдиний чинник, який впливає на результат&nbsp;— це значення аргументів.

Таким чином, є можливість протестувати кожну функцію в програмі, просто обчисливши її від різних наборів значень аргументів. При цьому можна не турбуватися ні про виклик функцій в правильному порядку, ні про правильне формуванні зовнішнього стану. Якщо будь-яка функція в програмі проходить модульні тести, то можна бути впевненим у якості всієї програми. В імперативних програмах перевірка значення, що повертається функції, недостатня: функція може модифікувати зовнішній стан, який теж потрібно перевіряти, чого не потрібно робити в функціональнихфункційних програмах<ref> [http://www.rsdn.ru/article/funcprog/fp.xml Ахмечет В . «Функціональнефункційне програмування для всіх»] </ref>.

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

Ще однією перевагою функціональнихфункційних програм є те, що вони надають найширші можливості для [[автоматичне розпаралелювання | автоматичного розпаралелювання]] обчислень. Оскільки відсутність побічних ефектів гарантовано, в будь-якому виклику функції завжди припустиме паралельне обчислення двох різних параметрів&nbsp;— порядок їх обчислення не може вплинути на результат виклику.

Недоліки функціональногофункційного програмування випливають з тих же самих його особливостей. Відсутність присвоювання і заміна їх на породження нових даних призводять до необхідності постійного виділення та автоматичного звільнення пам'яті, тому в системі виконання функціональноїфункційної програми обов'язковим компонентом стає високоефективний [[збирач сміття]]. Нестрога модель обчислень призводить до непередбачуваного порядку виклику функцій, що створює проблеми при введенні-виведенні, де порядок виконання операцій є важливим. Крім того, очевидно, функції введення в своєму природному вигляді (наприклад, getchar із стандартної бібліотеки мови [[C (мова програмування) | C]]) не є чистими, оскільки здатні повертати різні значення для одних і тих же аргументів, і для усунення цього потрібні певні хитрощі.

Для подолання недоліків функціональнихфункційних програм вже перші мови функціональногофункційного програмування включали не тільки чисто функціональніфункційні засоби, але і механізми імперативного програмування (присвоєння, цикл, «неявний PROGN» були вже в LISP'і). Використання таких засобів дозволяє вирішити деякі практичні проблеми, але означає відхід від ідей (і переваг) функціональногофункційного програмування і написання імперативних програм функціональнимифункційними мовами. У чистих функціональнихфункційних мовах ці проблеми вирішуються іншими засобами, наприклад, в мові [[Haskell]] ввід-вивід реалізований за допомогою [[Монади (програмування)| монади]]&nbsp;— нетривіальної концепції, запозиченої з теорії категорій.

* [[:Категорія:Функціональніфункційні мови програмування|Категорія: Функційні мови програмування]]

* [[Функціональніфункційні мови програмування]]

[[Категорія:Функціональнефункційне програмування]]