Функционално програмиране

В компютърните науки функционално програмиране е парадигма за програмиране – стил за изграждането на структурата и елементите на компютърни програми, който третира като изчислява оценката на математически функции и избягва променящите състоянието непостоянни данни. Това е декларативна парадигма за програмиране, което означава, че програмирането се извършва с изрази. Във функционален код, изходната стойност на функция зависи само от аргументите, които са вложени по време на функцията, така призованата функция е два пъти с една и съща стойност за един аргумент Х и тя ще произведе същия резултат (Х) всеки път. Премахване на нежелани реакции, т.е. промени в състоянието, което не зависи от входовете на функцията, може да направи много по-лесно разбирането и да се предскаже поведението на една програма, което е един от основните мотиви за развитието на функционално програмиране.

Функционално програмиране има своите корени в ламбда-смятането, което е официална система, разработена през 1930 г., за да разследва изчислимост на дефиниция на функция, приложение функция и рекурсия. Много функционални езици за програмиране могат да бъдат разглеждани като изградени върху ламбда-смятането. Друга добре позната декларативна парадигма за програмиране е логическото програмиране което, се основава на релацията.

За разлика, императивното програмиране променя състоянието, чрез команди в началния език, най-прост пример за това е задачата. Императивното програмиране наистина има функции, не в математическия смисъл, а в смисъл на подпрограми. Те могат да имат странични ефекти, които могат да променят стойността на програмата. Функции без стойности за връщане могат да доведат до това. Поради това, че те нямат референтна прозрачност, т.е. същия израз в друг език може да доведе до различни стойности по различно време в зависимост от състоянието на изпълняващата програмата.

Функционални програмни езици, особено изцяло функционални такива като Hope и Rex, са използвани повече в академичните среди, отколкото в развитието на търговски софтуер. Въпреки това, видни функционални езици за програмиране като Common Lisp, Scheme, Clojure, Language Wolfram Language, Racket, Erlang, OCaml, Haskell, и F# са били използвани в промишлени и търговски заявления от голямо разнообразие от организации. Функционално програмиране се подкрепя и в някои специфични програмни езици за домейн като R, J, K и (programming language from Kx Systems) Q от Kx Systems (финансов анализ), XQuery / XSLT (XML), и Opal. Широко разпространени специфични програмни езици за домейн като SQL и Lex / Yacc използват някои елементи на функционалното програмиране.

Програмиране на функционален стил може да се осъществи в езици, които не са специално предназначени за функционално програмиране. Например, императивния Perl език за програмиране е бил обект на една книга, описваща как да се прилагат концепции на функционалното програмиране. Това е вярно и за езика PHP. C # 3.0 и Java 8 добавят конструкции за улесняване на функционалния стил. Езикът Julia също предлага функционални възможности за програмиране. Интересен случай е този на Scala – често се пише във функционален стил, но присъствието на странични ефекти и непостоянни състояния го провежда в сивата зона между императивни и функционални езици.

История

Ламбда-смятането осигурява теоретична рамка за описване на функции и тяхната оценка. Въпреки че е по-скоро математическа абстракция, отколкото език за програмиране, то е в основата на почти всички функционални програмни езици днес. Една равностойна теоретична формулировка, комбинаторната логика, обикновено се възприема като по-абстрактна от ламбда-смятането. Комбинаторната логика и ламбда-смятането са първоначално разработени, за да се постигне по-ясен подход към основите на математиката.

Един от ранните функционални език е Lisp, разработен от Джон Маккарти, в Масачузетския технологичен институт (MIT) за серията 700/7000 на IBM – научни компютри от края на 50-те години на XX век. Lisp въвежда много функции, които могат да се намерят и в съвременните функционални езици. Scheme и Dylan са по-късни опити да се опрости и подобри Lisp.

Езикът за обработка на информация IPL е първият компютърнобазиран функционален език за програмиране. Това е език за обработка на списъци от символи. Той съдържа така наречения генератор – функция, която приема друга функция като аргумент. Въпреки това той разчита основно на структури от променливи списъци и подобни императивни свойства.

Кенет Айвърсън разработва APL в началото на 60-те години на XX век и го описва в книгата си „A Programming Language“, издадена през 1962 г. По модела на APL Джон Бекъс създава езика FP. В началото на 90-те години на XX век Айвърсън и Роджър Хюи създават езика J. В средата на 90-те години Артър Уитни, който преди това е работил с Айвърсън, създава езика K, който се използва комерсиално във финансовите индустрии заедно със своя наследник Q.

Джон Бекъс представя FP в своята лекция по време на наградите Тюринг, през 1977, наименувана „Може ли програмирането да бъде освободено от архитектурата на фон Нойман? Функционалният стил и неговата алгебра от програми“. Научната статия на Бакъс популяризира изследванията в областта на функционалното програмиране, макар че набляга на програмиране на функционално ниво, а не на стила на ламбда-смятането, който се свързва по-често с функционалното програмиране.

През 70-те години на 20 век Робин Милнер създава езика ML в Единбургския университет, а Дейвид Търнър, първоначално разработва езика SASL в университета Сейнт Андрюс и по-късно езика Miranda в университета Кент. Също така в Единбург през 70-те години, Бурсщал и Дарлингтън разработват функционалния език NPL. NPL се основава на рекурсивните теореми на Клийн и за първи път го въвеждат в работата им по трансформация на програми. Бурсщал, МакКуийн и Санела по-късно въвеждат полиморфичния вид проверка от ML, за да измислят езика Hope. След време ML се разделя на няколко диалекта, най-често срещаните от които са OCaml и Standard ML. В същото време, развитието на Scheme (от части функционален диалект на Lisp), показва на обществото занимаващо се с програмни езици истинската сила на функционалното програмиране.

През 80-те години, Пер Мартин-Льоф разработва неговата интуиционистка теория (наричана също конструктивна теория), която свързва функционалните програми с конструктивните доказателства за произволно сложни математически твърдения, изразени като зависими типове. Това довежда до мощни нови подходи към интерактивното доказване на теореми и повлиява на развитието на много последващи функционални програмни езици.

Езикът Haskell започва с консенсус през 1987 г., за да създаде отворен стандарт за изследвания в сферата на функционалното програмиране; имплементациите продължават от 1990 г. до днес.

Концепции

Определен брой концепции и парадигми са специфични за функционалното програмиране и като цяло чужди на императивното програмиране (включително и обектно-ориентираното програмиране). Въпреки това, програмните езици често са хибриди на няколко програмни парадигми, така че програмистите използващи "предимно императивни” езици може и да използват някои от тези понятия.

Първокласни функции и функции от по-висок ред

Функции от по-висок ред са функции, които могат или да приемат други функции като аргументи или да ги върнат като резултат. В пресмятането пример за функция от по-висок ред е диференциалния оператор, който връща производната на дадена функция.

Функциите от по-висок ред са тясно свързани с първокласните функции по това, че и двата типа функции позволяват функции като аргументи и резултати от други функции. Разликата между двете е малка: „по-висок ред“ описва математическо понятие от функции, които работят върху други функции, докато „първокласни“ е термин от компютърната наука, който описва единици в програмния език, които нямат ограничение за тяхното ползване (по този начин първокласните функции могат да се появяват навсякъде в програмата, където и други първокласни единици, като числата, могат, както и като аргументи на други функции и като техните стойности за връщане).

Функциите от по-висок ред позволяват частично прилагане, техника, при която една функция се прилага към нейните аргументи един по един, като всяко прилагане връща нова функция, която приема следващия аргумент. Това позволява да се изрази накратко, например, функцията наследник като оператора за събиране е частично приложен към естественото число едно.

Чисти функции

Чистите функционални функции (или изрази) нямат никакви странични ефекти (памет или I / O). Това означава, че чистите функции имат няколко полезни свойства, много от които могат да бъдат използвани за оптимизиране на кода:

• Ако не се използва в резултат на чистото изразяване, тя може да бъде отстранена без да се засягат други изрази.

• Ако чистата функция се нарича с аргументи, които не причиняват странични ефекти, резултатът е константа по отношение на този списък с аргументи (понякога се нарича референтна прозрачност), т.е. ако чистата функция отново е призована със същите аргументи, същият резултат ще бъде върнат.

• Ако няма зависимост от данни между два чисти израза, тяхната цел може да бъде обърната, или може да се извършва успоредно и те не могат да пречат един на друг (с други думи, оценката на всеки чист израз е безопасна).

• Ако пълния език не позволява странични ефекти, тогава всяка стратегия за оценка може да бъде използвана; това дава свободата на компилатора да преподреди или комбинира оценката на изразяване в програма.

Докато повечето компилатори за императивни езици за програмиране засичат чисти функции и изпълняват елиминиране за чисти функционални разговори, те не винаги могат да направят това за предварително компилирани библиотеки, които по принцип не излагат тази информация, като по този начин предотвратява оптимизации, които включват тези външни функции. Някои компилатори, като GCC, добавят думи за един програмист за да отбележат изрично външни функции като чистите, за да се даде възможност за тези оптимизации. Fortran 95 също така позволява на функции да бъдат определени като „чисти“.

Рекурсия

Повторение (итерация) във функционалните езици обикновено се осъществява чрез рекурсия. Рекурсивни функции се позовават, позволявайки на операция, да се извърши отново и отново, докато се достигне базовия модел. Въпреки че някои рекурсии изисква поддържане на стека, „опашатата“ рекурсия може да бъде разпозната и оптимизирана чрез компилатора в същия код, използван за въвеждане на итерация в императивните езици. Стандартът за език „Схема“ (Scheme) изисква имплементации за да разпознава и да се оптимизира опашатата рекурсия (Tail call). Оптимизацията на опашатата рекурсия може да бъде имплементирана чрез трансформиране на програмата към продължителен стил (Continuation-passing style (CPS), стил на програмиране при който функциите не връщат стойности), наред и с други подходи.

Общи модели на рекурсия може да се отчитат, като се използват по-високи функции за поръчка, с катаморфизъм и анаморфизъм (или „гънки“ и „разгъвки“) са най-очевидните примери. Такива високи поръчкови функции играят роля, аналогична на вградени контролни структури като цикли в императивните езици.

Най-основното предназначение на функционално програмиращите езици е, че позволяват неограничена рекурсия и са Turing Complete (могат напълно да се възползват от Машина на Тюринг). Някои езици със специално предназначение като Coq позволяват да само добре обосновани и са силно нормализиращи (непрекъсващи изчисления могат да бъдат изразени само с безкрайни потоци от стойности, наречени codata). Вследствие на това, тези езици не могат да бъдат Turing Complete и изразяването на определени функции в тях е невъзможно, но те все пак могат да изразяват широк клас от интересни изчисления, като се избягват проблемите, въведени с неограничена рекурсия. Функционално програмиране ограничено до добре обоснована рекурсия с няколко други ограничения се нарича пълно функционално програмиране.

Стриктно в сравнение с нестриткно оценяване

Функционалните езици могат да бъдат категоризирани с това дали използват стриктно (нетърпеливи (Eager)) или нестриктна (мързеливи (Lazy)) оценка, понятия, които се отнасят до начина на това как аргументите са преработени, когато израз бъде оценяван. Под строго оценяване, оценката на всеки термин, с липсващ subterm ще се провали. Например, изразът:

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

ще се провали при строга оценка поради делението на нула в третия елемент на списъка. Под мързелива оценка, дължината на функцията ще върне стойност 4 (т.е. броят на елементи в списъка), тъй като оценяването на това няма да се опита да направи оценка на условията, обхождайки списъка. Накратко, строга оценка винаги напълно оценява функционалните аргументите, преди извикването на функцията. Мързеливата оценка не оценява функционалните аргументите, освен ако техните стойности не са необходими за оценяване на извикването на самата функция.

Обичайната стратегия за имплементация на мързелива оценка във функционалните езици е намаляване на графика. „Мързеливата оценка“ се използва по подразбиране в няколко чисти функционални езика, включително Miranda, Clean, и Haskell.

Типови системи

Във функционалните езици за програмирани, разработени след 1970 г., обикновено се използват типизирани изрази, за разлика от нетипизираните, използвани в Lisp и неговите варианти (като (Scheme)). Използването на алгебрични типове данни и модел за съвпадение прави обработката на сложни структури от данни удобна и изразителна; наличието на силна типова проверка по време на компилиране повишава надеждността на програмите.

Някои изследователски ориентирани функционални езици като Coq, Agda, Cayenne и Epigram се основават на интуиционистка теория на типовете, което позволява типовете да зависят от условията (зависими типове). Зависимите типове могат да изразяват произволни твърдения в предикатна логика. Чрез изоморфизма на Къри—Хауърд добре написаните програми на тези езици стават средство за писане на формално математическо доказателство, от което компилаторът може да генерира сертифициран код. Макар че тези езици поради силния си уклон към математически формализъм представляват интерес главно за академични изследвания, те са започнали да се използват и в инженерството. Compcert е компилатор за подмножество на програмния език C.

Ограничена форма на зависимите типове, наречена обобщени алгебрични типове данни, осигурява някои от ползите от зависимото програмиране и в същото време избягва техните недостатъци. Обобщени алгебрични типове данни има в компилатора Glasgow Haskell, в OCaml (от версия 4.00) и в Scala (като „case classes“) и са били предложени като допълнения към други езици, включително Java и C# (C Sharp).

Функционално програмиране в нефункционални езици

Възможно е да се използва функционален стил на програмиране на езици, които не са традиционно смятани за функционални. Например езиците за програмиране D и Fortran 95 изрично подкрепят чисти функции.

JavaScript и Python имат първокласни функции още от самото начало. Armit Prem добави поддръжка на Python за „ламбда“, „карта“, „намаляване“ и „филтър“ през 1994 г., както и закриване (closure) в Python 2.2, макар Python 3 изхвърли „намаляване“-то, в functools стандартна модул библиотека. Първокласни функции са въведени в други масови езици като PHP 5.3, Visual Basic 9, C# 3.0 и C++11.

В Java анонимните класове понякога могат да бъдат използвани, за да се симулира затваряне. Обаче анонимните класове невинаги са подходящи заместители на затварянето, защото те имат по-ограничени възможности. Java 8 поддържа ламбда-изрази като заместители на някои анонимни класове. Въпреки това наличието на проверени изключения в Java може да направи функционалното програмиране неудобно, защото може да се наложи да се прехващат изключения и след това да се пораждат повторно – проблем, който не се среща в други JVM езици (като Scala), които нямат проверени изключения.

В C# не са необходими анонимни класове, тъй като затварянето и операцията ламбда се поддържат напълно. Разработват се библиотеки и езикови разширения за неизменяеми структури от данни, за да се подпомогне функционалното програмиране в C#.

Много обектно-ориентирани модели за проектиране са изразими във функционално програмиране: например, модел на стратегия (strategy pattern) просто диктува използването на функция за по-висш порядък и модел на посетител (visitor pattern) приблизително съответства на катаморфизма или сгъвката.

По същия начин, идеята за неизменни (immutable) данни от функционално програмиране често е включена в императивни езици за програмиране, например кортеж в Python, която е неизменен масив.

Сравнение с императивното програмиране

Функционалното програмиране е много различно от императивното програмиране. Най-значителните разлики произхождат от факта, че функционалното програмиране избягва страничните ефекти, които се използват в императивното програмиране за да имплементират състоянието и вход / изход. Чистото функционално програмиране изцяло предотвратява страничните ефекти и предоставя прозрачност на референциите, което прави лесно потвърждаването, оптимизирането и паралелизацията на програмите, както и писането на автоматизирани инструменти за изпълняването на тези задачи.

Функции от по-висок ред се използват рядко в по-старите езици за императивно програмиране. Там където една традиционна императивна програма би използвала цикъл, за да обходи списък, една функционална програма би използвала различна техника. Би използвала функция от по-висок ред, която взима като аргументи функция и списък. Функцията от по-висок ред тогава би приложила дадената функция върху всеки елемент от дадения списък и би върнала нов списък с резултатите.

Симулиране на състояние

Някои задачи (например поддържането на банкова сметка с баланс) често най-естествено се прилагат посредством състояние. Чистото функционално програмиране изпълнява тези задачи, както и входно / изходни задачи (например получаването на вход от потребителя и извеждането на изход на екрана) по различен начин.

Чистият функционален език Haskell ги имплементира чрез монади, заимствани от теория на категориите. Монадите представят начин за абстракция на дадени типове изчислителни шаблони, включително моделиране на изчисления с променливо състояние по императивен начин, без загуба на чистота.

Друг начин, по който функционалните езици симулират състояние е чрез предаването на структура от данни, която представлява сегашното състояние, като параметър към повикваните функции. При всяко повикване на функция се създава копие на тези данни с каквито разлики остават след действието на функцията.

Нечистите функционални езици обикновено включват по-директен метод за работа с променливо състояние. Clojure, например, използва менажирани референции, които могат да се обновяват чрез прилагането на чисти функции към сегашното състояние. Този подход позволява променливост, докато все още предразполага към използването на чисти функции.

Проблеми с производителността

Функционалните езици за програмиране обикновено са по-неефективни в употребата си на процесора и паметта от императивни езици, като C и Pascal. Това е поради факта, че някои променливи структури от данни имат прости имплементации с модерния хардуер. Плоските масиви могат да се обработват много ефективно с поточни процесори, могат ефективно да се извличат предварително чрез кешове, или да се обработват със SIMD инструкции. По-трудно се създават непроменливи плоски масиви, каквито се използват във функционалното програмиране. За чистите функционални езици, забавянето в най-лош случай е логаритмично относно памет, тъй като променливата памет може да бъде представена чрез чисто функционална структура от данни с логаритмично време за достъп (например балансирано дърво). От друга страна, подобни забавяния не са универсални. За програми, които извършват тежки числени операции, някои функционални езици като OCaml и Clean са само леко по-бавни от C. За програми, които обработват големи матрици и многомерни бази данни, функционалните езици за масиви (като J и K) са създадени с оптимизации за скорост.

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

Мързеливото оценяване може също да ускори програмата, дори асимптотично, докато може да я забави най-много с константен фактор.

Стилове код

Императивните програми поставят фокус върху стъпките, които програмата предприема, за да изпълни едно действие. Функционалните програми поставят фокус върху композицията и подредбата на функциите, често без да се обособяват изрични стъпки. Един прост пример показва това с две решения на една и съща задача (намирането на числа на Фибоначи). Императивният пример е написан на Python.

Версия 1 – с генератори

# Fibonacci numbers, imperative style
# [https://docs.python.org/2.7/tutorial/modules.html docs.python.org]
def fibonacci(n, first=0, second=1):
 for i in range(n):
 yield first # Return current iteration
 first, second = second, first + second

print [x for x in fibonacci(10)]

Версия 2 – нормална

def fibonacci(n):
 first, second = 0, 1
 for i in range(n):
 print first # Print current iteration
 first, second = second, first + second #Calculate next values

fibonacci(10)

Версия 3 – с рекурсия

def fibonacci(n, first=0, second=1):
 if n == 1:
 return [first]
 else:
 return [first] + fibonacci(n – 1, second, first + second)

print fibonacci(10)

Haskell

Функционална версия, написана на Haskell:

-- Fibonacci numbers, functional style

-- describe an infinite list based on the recurrence relation for Fibonacci numbers
fibRecurrence first second = first: fibRecurrence second (first + second)

-- describe fibonacci list as fibRecurrence with initial values 0 and 1
fibonacci = fibRecurrence 0 1

-- describe action to print the 10th element of the fibonacci list
main = print (fibonacci !! 10)

Или по-кратко:

fibonacci2 = 0:1:zipWith (+) fibonacci2 (tail fibonacci2)

Императивният стил описва междинните стъпки, нужни за изчисляването на fibonacci(N) и поставя тези стъпки в цикъл. Функционалната имплементация показана тук описва математическата рекурентна релация и определя цялата редица Фибоначи, след което избира елемент от тази редица. Този пример използва мързеливото оценяване на Haskell, за да създаде „безкраен“ списък, от който само нужните елементи (първите 10, в този случай) се изчисляват.

Lisp

Функцията Fibonacci може да бъде написана на Common Lisp по следния начин:

(defun fib (n &optional (a 0) (b 1))
 (if (= n 0)
 a
 (fib (- n 1) b (+ a b))))

После може да бъде извикана като:

(fib 10)