Функційне програмування

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Ширша концепція функційного програмування визначає набір спільних правил та тем замість переліку відмінностей від інших парадигм. До таких, що часто вважаються важливими, належать функції вищого порядку[2] та функції першого класу: замикання, та рекурсія. До інших поширених можливостей функційних мов програмування належать продовження, система типізації Хіндлі-Мілнера, нечіткі обчислення (включно з, але, не обмежуючись, лінивими обчисленнями), та монади.

Основну увагу функційним мовам програмування, особливо, «чисто функційним», приділили академічні дослідники. Однак, до відомих функційних мов програмування, які використовуються в промисловості та комерційному програмуванні належить 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. І λ-числення, і комбінаторна логіка були розроблені для більш ясного й точного опису принципів і основ математики[3].

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

Мова обробки інформації (Information Processing Language}}, IPL) іноді визначається як найперша машинно-функціональна мова[5]. Це мова ассемблерного типу для роботи зі списком символів. У ньому було поняття «генератора», який використовував функцію як аргумент, а також, оскільки це мова ассемблерного рівня, він може позиціонуватися як мова, що має функції вищого порядку. Однак, в цілому IPL акцентовано на використання імперативних понять[6].

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

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

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

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

Концепції[ред.ред. код]

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

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

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

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

Чисті функції[ред.ред. код]

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

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

Хоча більшість компіляторів імперативних мов програмування розпізнають чисті функції і видаляють загальні підвирази для викликів чистих функцій, вони не можуть робити це завжди для попередньо скомпільованих бібліотек, які, як правило, не надають цю інформацію. Деякі компілятори, такі як gcc, з метою оптимізації надають програмісту ключові слова для позначення чистих функцій[10]. Fortran 95 дозволяє позначати функції як «pure»[11].

Рекурсія[ред.ред. код]

Докладніше: Рекурсія

У функціональних мовах цикл зазвичай реалізується у вигляді рекурсії. Строго кажучи, в функціональної парадигми програмування немає такого поняття, як цикл. Рекурсивні функції викликають самі себе, дозволяючи операції виконуватися знову і знову. Для використання рекурсії може знадобитися великий стек, але цього можна уникнути в разі хвостової рекурсії. Хвостова рекурсія може бути розпізнана і оптимізована компілятором в код, одержуваний після компіляції, аналогічної ітерації в імперативній мові програмування.[12] Стандарти мови Scheme вимагають розпізнавати і оптимізувати хвостову рекурсію. Оптимізувати хвостову рекурсію можна шляхом перетворення програми в стилі використання продовжень при її компіляції, як один із способів.[13]

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

Підхід до обчислення аргументів[ред.ред. код]

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

print (len ([2 +1, 3 * 2, 1/0, 5-4]))

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

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

ФП в нефункціональних мовах[ред.ред. код]

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

У мові C покажчики на функцію в якості типів аргументів можуть бути використані для створення функцій вищого порядку. Функції вищого порядку і відкладена списковому структура реалізовані в бібліотеках 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)

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

Особливості[ред.ред. код]

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

Сильні сторони[ред.ред. код]

Підвищення надійності коду[ред.ред. код]

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

Зручність організації модульного тестування[ред.ред. код]

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

Таким чином, є можливість протестувати кожну функцію в програмі, просто обчисливши її від різних наборів значень аргументів. При цьому можна не турбуватися ні про виклик функцій в правильному порядку, ні про правильне формуванні зовнішнього стану. Якщо будь-яка функція в програмі проходить модульні тести, то можна бути впевненим у якості всієї програми. В імперативних програмах перевірка значення, що повертається функції, недостатня: функція може модифікувати зовнішній стан, який теж потрібно перевіряти, чого не потрібно робити в функціональних програмах[15].

Можливості оптимізації при компіляції[ред.ред. код]

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

Можливості паралелізму[ред.ред. код]

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

Недоліки[ред.ред. код]

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

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

Замітки[ред.ред. код]

  1. Хендерсон 1983, Предисловие редактора перевода
  2. Вольфенгаген В. Э. Конструкции языков программирования. Приемы описания. — М: АО «Центр ЮрИнфоР», 2001. — 276 с ISBN 5-89158-079-9.
  3. Роджер Пенроуз Глава 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
  4. J. Harrison , 1997, Гл. 3. λ-числення як мова програмування
  5. У своїх мемуарах Герберт Саймон (1991), Models of My Life pp. 189–190 ISBN 0-465-04640-1 стверджує, що його, Al. Ньюелл, і Кліфф Шоу яких «часто називають батьками штучного інтелекту» за написання програми Logic Theorist(англ.)укр. автоматично доводить теореми з Principia Mathematica. Для того, щоб досягти цього, вони повинні були придумати мову і парадигму, яку, ретроспективно, можна розглядати як функціональне програмування.
  6. History of Programming Languages: IPL
  7. XIV. APL Session // History of Programming Language / Richard L. Wexelbblat. — Academic Press, 1981. — С. 661-693. — ISBN 0-12-745040-8.
  8. Пол Хьюдак(англ.)укр. Conception, evolution, and application of functional programming languages ​​ // ACM Computing Surveys, 21 (September 1989) (3) С. 359 −411.
  9. Завантажити PDF: "Техніки функціонального програмування, В. А. Потапенко «стор. 8» Функції вищих порядків ".
  10. GCC , Declaring Attributes of Functions
  11. XL Fortran for AIX, V13.1 Language Reference, Pure procedures (Fortran 95)]
  12. Tail call optimization
  13. Revised5 Report on the Algorithmic Language Scheme, 3.5. Proper tail recursion
  14. Н. А. Роганова Функціональне програмування: Навчальний посібник для студентів вищих навчальних закладів — М.: ГІНФО, 2002. — 260 с. Стор. 14 п. 3.1. Ледачі і енергійні обчислення
  15. Ахмечет В . «Функціональне програмування для всіх»

Посилання[ред.ред. код]

  • Why functional programming matters, by John Hughes, The Computer Journal, Vol. 32, No. 2, 1989, pp. 98 — 107. [1] — про переваги функційного програмування.

Джерела інформації[ред.ред. код]

  • Functional programming — стаття в англомовній вікіпедії.
  • Peter Henderson, Functional Programming Application and Implementation, 1980. П. Хендерсон, Функциональное программирование, применение и реализация, перевод с англ. Москва, Мир, 1983

Див. також[ред.ред. код]