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

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

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

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

Основну увагу функційним мовам програмування, особливо, «чисто функційним», приділили академічні дослідники. Однак, до відомих функційних мов програмування, які використовуються в промисловості та комерційному програмуванні належить 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^[en]. Lisp визначив множину понять функційної мови, хоча при цьому сповідував не тільки парадигму функційного програмування ^[4]. Подальшим розвитком Ліспу стали такі мови як Scheme і Dylan.

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

Кеннет Айверсон розробив мову APL на початку шістдесятих, продокоментувавши її в своїй книзі A Programming Language (ISBN 9780471430148)^[7]. APL справив значний вплив на мову FP^[en], створену Джоном Бекусом. На початку дев'яностих Айверсон і Роджер Гуй^[en] створили наступника APL — мова програмування J. У середині дев'яностих Артур Вітні^[en], який раніше працював з Айверсоном, створив мову 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, наявні засоби метапрограмування (фактично, доповнення мови новими конструкціями) дозволяють створити специфічні для функційного стилю об'єкти даних і програмні конструкції, після чого можна писати функційні програми з їх використанням.

Структури даних

Чисто функціональні структури даних часто представлені інакше, ніж їх процедурні аналоги.^[15] Наприклад, масив з постійним доступом і часом оновлення є основним компонентом більшості імперативних мов, і багато імперативних структур даних, таких як геш-таблиця і двійкова купа, засновані на масивах. Масиви можна замінити асоціативними масивами або списками випадкового доступу, які допускають суто функціональну реалізацію, але мають логарифмічний доступ і час оновлення. Чисто функціональні структури даних мають стійкість, тобкто властивість зберігати попередні версії структури даних незмінними. У Clojure постійні структури даних використовуються як функціональні альтернативи їхнім імперативним аналогам.

Стилі програмування

Імперативні програми мають схильність акцентувати послідовності кроків для виконання якоїсь дії, а функційні програми до розташування і композиції функцій, часто не позначаючи точної послідовності кроків. Простий приклад двох рішень однієї задачі (використовується одна і та ж мова 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)

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

Особливості

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

Сильні сторони

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

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

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

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

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

Можливості оптимізації при компіляції

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

Можливості паралелізму

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

Недоліки

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

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

Див. також

Примітки

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

Література

Функційне програмування : Навч. посіб. для студ. вищих навч. закл., що навч. за спец. "Програм. забезп. автоматиз. систем" / В. М. Заяць; Нац. ун-т "Львів. політехніка". - Л. : Бескид Біт, 2003. - 159 c. - Бібліогр.: 15 назв.

Додаткова література

Судомир В. Використання функційної парадигми при програмуванні мікроконтролерів //Матеріали Ⅱ Міжнародної студентської науково-технічної конференції „Природничі та гуманітарні науки. Актуальні питання “. – 2019. – С. 52-52

Джерела інформації

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

Посилання

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

[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

[FOOTNOTEJ._Harrison1997Гл._3._λ-числення_як_мова_програмування-4] J. Harrison, 1997, Гл. 3. λ-числення як мова програмування.

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

[6] History of Programming Languages: IPL. Архів оригіналу за 1 листопада 2006. Процитовано 6 грудня 2012.

[7] XIV. APL Session // History of Programming Language / Richard L. Wexelbblat. — Academic Press, 1981. — С. 661—693. — ISBN 0-12-745040-8.

[hudak1989-8] Пол Г'юдак^[en] (September 1989). Conception, evolution, and application of functional programming languages . ACM Computing Surveys. 21 (3): 359 −411.

[functional-9] В. А. Потапенко. Функції вищих порядків. Техніки функційного програмування. с. 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

[lenivie-14] Н. А. Роганова функційне програмування: Навчальний посібник для студентів вищих навчальних закладів — М.: ГІНФО, 2002. — 260 с. Стор. 14 п. 3.1. Ледачі і енергійні обчислення

[15] Okasaki, Chris (1998). Purely functional data structures. Cambridge, U.K.: Cambridge University Press. ISBN 978-1-139-81174-3. OCLC 822565696.

[16] Ахмечет В . «функційне програмування для всіх»

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]