Пређи на садржај

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

С Википедије, слободне енциклопедије

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

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

Функционални програмски језици, посебно они који су чисто функционални, се више користе на универзитетима него у комерцијалном развоју софтвера. Међутим међу значајнијим функционалним програмским језицима који се користе у комерцијалној примени су Ерланг,[2] OCaml,[3] Хаскел,[4] Scheme[5] и домен-специфични програмски језици као што су R (статистика),[6] Mathematica (симболичка математика),[7] J и K (финансијска анализа), и XSLT (XML).[8][9] Широко коришћени декларативни домен-специфични језици као што су SQL и Lex/Yacc, користе неке елементе функционалног програмирања, посебно у избегавању променљивих вредности.[10] Спредшитови такође могу да се посматрају као функционални програмски језици.[11]

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

Историја

[уреди | уреди извор]

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

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

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

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

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

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

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

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

Концепти

[уреди | уреди извор]

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

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

[уреди | уреди извор]

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

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

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

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

[уреди | уреди извор]

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

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

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

Рекурзија

[уреди | уреди извор]

Строго и не-строго израчунавање

[уреди | уреди извор]

Референце

[уреди | уреди извор]
  1. ^ а б в Худак, Пол (1989). „Концепт, еволуција и примена функционалних програмских језика” (PDF). ACM Computing Surveys. 21 (3): 359—411. doi:10.1145/72551.72554. Архивирано из оригинала (PDF) 20. 3. 2009. г. Приступљено 20. 4. 2009. 
  2. ^ 0 „Ко користи Ерланг за развој производа?” Проверите вредност параметра |url= (помоћ). Често постављања питања о Ерлангу. Приступљено 5. 8. 2007. 
  3. ^ Мински, Јарон; Викс, Стивен (2008). „Caml трговина - искуства са функционалним програмирањем на Вол стриту”. Журнал Функционалног програмирања. Cambridge University Press. 18 (4): 553—564. doi:10.1017/S095679680800676X. Приступљено 27. 8. 2008. 
  4. ^ „"Хаскел - Хаскел вики”. Приступљено 27. 8. 2008. 
  5. ^ Клингер, Вил (1987). "Мултитаскинг и MacScheme". MacTech 3 (12). http://www.mactech.com/articles/mactech/Vol.03/03.12/Multitasking/index.html. Добављено дана 2008-08-28.
  6. ^ The useR! 2006 распоред конференције укључује радове о комерцијалној употреби језика R, Приступљено 29. 4. 2013.
  7. ^ Одељење за примењену математику; Колораду, Универзитет у. „Функционални vs. процедурални програмски језик”. Архивирано из оригинала 13. 11. 2007. г. Приступљено 28. 8. 2006. 
  8. ^ Новачев, Димитре. „Функционални програмски језик XSLT - ��оказ кроз примере”. TopXML. Архивирано из оригинала 18. 05. 2006. г. Приступљено 27. 5. 2006. 
  9. ^ Мерц, Дејвид. „XML Програмска парадигма (четврти део): Прилаз функционалног програмирања XML-у”. IBM developerWorks. Архивирано из оригинала 15. 08. 2007. г. Приступљено 27. 5. 2006. 
  10. ^ Чемберлен, Доналд Д.; Рејмонд Ф. Бојс (1974). „SEQUEL: Структурисани енглески језик за упите”. Proceedings of the 1974 ACM SIGFIDET: 249—264. . У овом раду, који представља једну од првих формалних презентација коцепата SQL-а (и пре него што је име касније скраћено), Чемберлен и Бојс истичу да је SQL развијен „Без посезања за концептима везаних променљивих и квантификатора“.
  11. ^ Џонс, Сајмон Пејтон; Барнет, Маргарет; Блеквел, Алан (2003). „Унапређивање најпопуларнијег функционалног програмског језика на свету: кориснички дефинисане функције у Ексцелу”. 
  12. ^ Curry, Haskell Brooks; Feys, Robert; Craig, William (1958). Combinatory Logic. Volume I. Amsterdam: North-Holland Publishing Company. 
  13. ^ McCarthy, John (1978). „History of Lisp”. In ACM SIGPLAN History of Programming Languages Conference: 173—196. doi:10.1145/800025.808387.  " The implementation of LISP began in Fall 1958."
  14. ^ Pountain, Dick. „Functional Programming Comes of Age”. BYTE.com (August 1994). Архивирано из оригинала 27. 08. 2006. г. Приступљено 31. 8. 2006. 

Литература

[уреди | уреди извор]

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

[уреди | уреди извор]


  1. ^ „Greg Michaelson's Homepage”. Mathematical and Computer Sciences. Riccarton, Edinburgh: Heriot-Watt University. Приступљено 6. 11. 2022.