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

У рачунарству, функционално програмирање је програмска парадигма која третира програм као израчунавање математичких функција и избегава стања и променљиве податке. Акценат је на примени функција, у супротности са стилом императивног програмирања, код кога је нагласак на промени стања. Корени функционалног програмирања леже у ламбда рачуну, формалном систему развијеном током 1930-их ради проучавања дефиниције и примене функција и рекурзије. Многи функционални програмски језици могу да се посматрају као практична разрада теоретског ламбда рачуна.

У пракси, разлика између математичке функције и појма функције који се користи у императивном програмирању је у томе што императивне функције могу да имају бочне ефекте, због тога што могу да промене вредности већ извршених израчунавања. Због овога, њима недостаје референцијална транспарентност, то јест, исти израз може да доведе до различитих резултата у различитим тренуцима, у зависности од стања програма који се извршава. Са друге стране, у функционалном коду, излазна вредност функције зависи само од аргумената који се проследе функцији, па тако позивање функције f два пута, са истом вредношћу аргумента x ће произвести исти резултат, f(x) оба пута. Елиминисањем бочних ефеката разумевање и предвиђање понашања програма може да постане много лакше, и ово је једна од кључних мотивација за развој фунцкионалног програмирања.

Функционални програмски језици, посебно они који су чисто функционални, се више користе на универзитетима него у комерцијалном развоју софтвера. Међутим међу значајнијим функционалним програмским језицима који се користе у комерцијалној примени су Ерланг, -{OCaml}-, Хаскел, -{Scheme}- и домен-специфични програмски језици као што су -{R}- (статистика), -{Mathematica}- (симболичка математика), -{J}- и -{K}- (финансијска анализа), и -{XSLT}- (-{XML}-). Широко коришћени декларативни домен-специфични језици као што су -{SQL}- и -{Lex}-/-{Yacc}-, користе неке елементе функционалног програмирања, посебно у избегавању променљивих вредности. Спредшитови такође могу да се посматрају као функционални програмски језици.

Програмирање у функционалном стилу може да се постигне и у језицима као што су -{C}-, -{C++}-, -{Python}-, или -{Java}-, који нису специфично дизајнирани за функционално програмирање.

Историја

Ламбда рачун пружа теоријски оквир за описивање функција и њихово израчунавање. Мада се ради о математичкој апстракцији, а не о програмском језику, он представља основу скоро свих модерних функционалних програмских језика. Еквивалентна теоријска формулација, комбинаторна логика, се обично сматра апстрактнијом од ламбда рачуна. Она се користи у неким езотеричним језицима, као што је Униламбда. И комбинаторна логика и ламбда рачун су развијени да би се постигао јаснији приступ основама математике.

Рани језик са функционалним акцентом је био Lisp, који је развио Џон Макарти док је био на МИТ за IBM серију 700/7000 научних рачунара крајем 1950-их. Lisp је увео многе особинее које се сада јављају у програмским језицима, мада је он технички мулти-парадигматски језик. Програмски језици -{Scheme}- и -{Dylan}- представљају касније покушаје да се поједностави и унапреди Lisp.

Језик за процесирање података (ИПЛ) се понекад наводи као први рачунарски функционални програмски језик. То је језик асемблерског стила за манипулисање листама симбола. Он поседује појам генератора који се односи на функцију која прима функцију као аргумент, а како се ради о језику на асемблерском нивоу, код може да се интерпретира на исти начин као и подаци, тако да може да се посматра да ИПЛ има функције вишег реда. Међутим, овај језик се значајно ослања на одређена императивна својства.

Кенет Е. Ајверсон је развио програмски језик АПЛ почетком 1960-их. Описао га је у својој књизи -{A Programming Language}-. АПЛ је извршио највећи утицај на Бакусов ФП. Почетком 1990-их, Ајверсон и Роџер Хуи су развили наследника АПЛ, програмски језик Ј. Средином 1990-их, Артур Витни, који је претходно радио са Ајверсоном, је развио програмски језик К, који се комерцијално користи у финансијском сектору.

Џон Бакус је представио програмски језик ФП 1977. године у свом говору током примања Тјурингове награде Да ли програмирање може да буде ослобожено фон Нојмановог стила? Функционални стил и његова алгебра програма Шаблон:Wayback. Бакусов рад је популаризовао истраживање функционалног програмирања, мада је његов акценат био на програмирању на нивоу функција а не на стилу ламбда рачуна који је постао везан за функционално програмирање.

Током 1970-их, Робин Милнер са Универзитета у Единбургу је развио програмски језик ML, а Дејвид Тарнер је радио на језику САСЛ на Универзитету Сент Ендруз и касније на језику Миранда на Универзитету у Кенту. ML се касније развио у неколико дијалеката, од којих су најпознатији -{Objective Caml}- и -{Standard ML}-. Такође, крајем 1970-их, развој програмског језика -{Scheme}- (делом функционалног дијалекта Lisp-а) је раширио свест о моћи функционалног програмирања у ширим програмерским заједницама.

Током 1980-их, Пер Мартин-Леф је развио интуиционистичку теорију типова (такође познату као конструктивна теорија типова), која је повезала функционалне програме са конструктивним доказима произвољно комплексних математичких исказа изражених у облику зависних типова. Ово је довело до моћних нових приступа интерактивном доказивању теорема и утицало на развој многих будућих функционалних програмских језика.

Програмски језик Хаскел је настао крајем 1980-их у покушају да се у једном језику споје многе идеје у истраживању функционалног програмирања.

Концепти

Постоји више концепата и парадигми који су специфични за функционално програмирање, а не користе се у императивно програмирање (укључујући и објектно оријентисано програмирање). Међутим, програмски језици су често хибриди више програмских парадигми, тако да програмери који користе углавном императивне језике понекад користе и неке од ових концепата.

Функције вишег реда

Функције вишег реда су оне функције које могу да узимају друге функције као своје аргументе, и да их враћају као резултат. (Примери су оператори у математици, као што је диференцијални оператор $d/dx$ који даје извод када се примени на функцију $f$.)

Функције вишег реда су у блиској вези са функцијама прве класе, пошто и функције вишег реда и функције прве класе могу да имају функције као аргументе и да враћају друге функције. Разлика између ова два појма је суптилна: вишег реда описује математички концепт функција које оперишу над другим функцијама, док прва класа у рачунарству означава ентитете програмског језика који немају ограничења за своју употребу (стога функције прве класе могу да се појављују било где у програму где и други ентитети прве класе, као што су бројеви, укључујући и као аргументи других функција и њихове повратне вредности..

Функције вишег реда омогућавају кариинг (Шаблон:Јез-енгл), технику код које се функција примењује на један по један свој аргумент, а свака примена враћа нову функцију која прима следећи аргумент.

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

Чисто функционалне функције (или изрази) немају памћење или улазно/излазне бочне ефекте, осим ако се само израчунавање рачуна као споредни ефекат. Ово значи да чисте функције имају неколико корисних својстава, од којих многа могу да се користе за оптимизовање кода:

• Ако се резултат чистог израза не користи, он може да буде уклоњен, и тиме се не утиче на остале изразе.
• Ако се чиста функција позива са параметрима који не проузрокују бочне ефекте, резултат је константа у односу на ту листу параметара (то се понекад назива референцијална транспарентност), то јест, ако се чиста функција поново позове са истим параметрима, резултат ће бити исти (ово омогућава оптимизације са кеширањем).
• Ако не постоји зависност у подацима између два чиста израза, њихов редослед може да буде замењен или могу да буду израчунати паралелно, и неће утицати један на други (другим речима, израчунавање сваког чистог израза је тред-безбедно).
• Ако цео језик не дозвољава бочне ефекте, онда може да се користи било која стратегија израчунавања; ово компајлеру оставља слободу да преуреди или комбинује израчунавања израза у програму (на пример, коришћењем дефорестације).

Иако већина компајлера за императивне програмске језике детектује чисте изразе, и врше уобичајену елиминацију позива чистих функција у подизразима, они не могу увек ово спроведу за прекомпајлиране библиотеке, које начелно не откривају ове информације, и тиме спречавају оптимизовање које укључује те спољашње функције. Неки компајлери, као што је -{gcc}-, имају додатне кључне речи које програмеру омогућавају да експлицитно означи спољашње функције као чисте, како би омогућио такве оптимизације. Фортран 95 омогућава да функције буду означене као чисте.

Литература

• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Cousineau, Guy and Michel Mauny. The Functional Approach to Programming. Cambridge, UK: Cambridge University Press, 1998.
• Шаблон:Cite book
• Dominus, Mark Jason. Higher-Order Perl. Morgan Kaufmann. 2005.
• Шаблон:Cite book
• Graham, Paul. ANSI Common LISP. Englewood Cliffs, New Jersey: Prentice Hall, 1996.
• MacLennan, Bruce J. Functional Programming: Practice and Theory. Addison-Wesley, 1990.
• Шаблон:Cite book
• Шаблон:Cite book
• Pratt, Terrence W. and Marvin Victor Zelkowitz. Programming Languages: Design and Implementation. 3rd ed. Englewood Cliffs, New Jersey: Prentice Hall, 1996.
• Salus, Peter H. Functional and Logic Programming Languages. Vol. 4 of Handbook of Programming Languages. Indianapolis, Indiana: Macmillan Technical Publishing, 1998.
• Thompson, Simon. Haskell: The Craft of Functional Programming. Harlow, England: Addison-Wesley Longman Limited, 1996.

Спољашње везе

• Шаблон:Cite web
• Шаблон:Cite web An introduction
• Functional programming in Python (by David Mertz): part 1, part 2, part 3