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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

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

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

Функционални програмни езици, особено изцяло функционални такива като Hope и Rex, са използвани повече в академичните среди, отколкото в развитието на търговски софтуер. Въпреки това, видни функционални езици за програмиране като  Common Lisp, Scheme, Clojure, Wolfram Language, Racket,  Erlang, OCaml, Haskell, и F # са били използвани в промишлени и търговски заявления от голямо разнообразие от организации. Функционално програмиране се подкрепя и в някои специфични програмни езици за домейн като R , J, K и 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-те години на 20 век. Lisp въвежда много функции, които можем да намерим във функционалните езици днес, въпреки че, на практика Lisp е език мулти-парадигма. Scheme и Dylan са по-късни опити да се опрости и подобри Lisp.

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

Кенет Айвърсън разработва APL в началото на 60-те години на 20 век, който е описал в книгата си, A Programming Language (ISBN 9780471430148), издадена през 1962 г. APL е основната причина Джон Бeкъс да създаде езика FP. В началото на 90-те години Айвърсън и Роджър Хюи създават 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). Това означава, че чистите функции имат няколко полезни свойства, много от които могат да бъдат използвани за оптимизиране на кода:

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

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

Рекурсия[редактиране | редактиране на кода]

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

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

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

Стриктно в сравнение с нестриткно оценяване[редактиране | редактиране на кода]

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

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

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

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

Типови системи[редактиране | редактиране на кода]

Особено след като развитието на Hindley-Milner type inference през 1970 г., функционално програмните езици са склонни да използват типизирани ламбда изчисления, за разлика от нетипизираните, използвани в Lisp и неговите варианти (като Схема (Scheme)). Използването на алгебрични типове данни и модел за съвпадение прави манипулирането на сложни структури от данни удобни и изразително; наличието на силна типова проверка по време на компилация прави програмите по-надеждни, докато type interface освобождава програмиста от необходимостта да декларира ръчно типовете в компилатора.

Някои изследователски-ориентирани функционални езици като Coq, Agda, Cayenne и Epigram се основават на теорията интуиционистки тип (intuitionistic type theory), което позволява да зависят от условията. Такива типове се наричат ​​зависими видове (dependent type). Тези системи нямат решен тип за подразбиране и са трудни за разбиране и програмиране. Но зависимите видове могат да изразяват произволни твърдения в предикатна логика (predicate logic). Чрез изоморфизъм Curry-Хауърд (Curry-Howard isomorphism), добре написаните програми на тези езици стават средство за писане на формално математическо доказателство, от което компилатора може да генерира сертифицирани код. Макар че тези езици са с интерес главно към академичните изследвания (включително в формализирана математика), те са започнали да се използват също и в инженерството. Compcert е компилатор за подмножество на C (език за програмиране), което е написано в Coq и е официално потвърден.

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

Функционално програмиране в нефункционални езици[редактиране | редактиране на кода]

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

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

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

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

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

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

Сравнение с императивното програмиране[редактиране | редактиране на кода]

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

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

Симулиране на състояние[редактиране | редактиране на кода]

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

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

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

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

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

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

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

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

Стилове код[редактиране | редактиране на кода]

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

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

# Fibonacci numbers, imperative style
# https://docs.python.org/2.7/tutorial/modules.html
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)

Бележки[редактиране | редактиране на кода]

  1. Larry C. Paulson (28 June 1996). ML for the Working Programmer. Cambridge University Press. ISBN 978-0-521-56543-1. Retrieved 10 February 2013.
  2. Daniel Spiewak. "Implementing Persistent Vectors in Scala". Retrieved Apr 17, 2012.
  3. "Which programs are fastest? | Computer Language Benchmarks Game". benchmarksgame.alioth.debian.org. Retrieved2011-06-20.