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

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

У рачунарству, функционално програмирање је програмска парадигма која третира програм као израчунавање математичких функција и избегава стања и променљиве податке. Акценат је на примени функција, у супротности са стилом императивног програмирања, код кога је нагласак на промени стања.[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]

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

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

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

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

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

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

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

Концепти[уреди]

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

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

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

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

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

Чисте функције[уреди]

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

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

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

Рекурзија[уреди]

Vista-xmag.png За више информација погледајте чланак Рекурзија (рачунарство)

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

Vista-xmag.png За више информација погледајте чланак Стратегије израчунавања

Референце[уреди]

  1. ^ а б в Худак, Пол (Септембар 1989). „Концепт, еволуција и примена функционалних програмских језика“ (PDF). ACM Computing Surveys 21 (3): 359–411. DOI:10.1145/72551.72554. 
  2. ^ 0 „Ко користи Ерланг за развој производа?“. Често постављања питања о Ерлангу Приступљено 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. процедурални програмски језик“ Приступљено 28. 8. 2006.. 
  8. ^ Димитре Новачев. „Функционални програмски језик XSLT - Доказ кроз примере“. TopXML Приступљено 27. 05. 2006.. 
  9. ^ Дејвид Мерц. „XML Програмска парадигма (четврти део): Прилаз функционалног програмирања XML-у“. IBM developerWorks Приступљено 27. 05. 2006.. 
  10. ^ Доналд Д. Чемберлен и Рејмонд Ф. Бојс (1974). „SEQUEL: Структурисани енглески језик за упите“. Proceedings of the 1974 ACM SIGFIDET: 249–264. . У овом раду, који представља једну од првих формалних презентација коцепата SQL-а (и пре него што је име касније скраћено), Чемберлен и Бојс истичу да је SQL развијен „Без посезања за концептима везаних променљивих и квантификатора“.
  11. ^ Сајмон Пејтон Џонс, Маргарет Барнет, Алан Блеквел (март 2003). „Унапређивање најпопуларнијег функционалног програмског језика на свету: кориснички дефинисане функције у Ексцелу“. 
  12. ^ Curry, Haskell Brooks; Robert Feys and Craig, William (1958). Combinatory Logic. Volume I. Amsterdam: North-Holland Publishing Company. 
  13. ^ McCarthy, John (June 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. ^ Dick Pountain. „Functional Programming Comes of Age“. BYTE.com (August 1994) Приступљено August 31 2006. 

Литература[уреди]

  • Curry, Haskell Brooks; Robert Feys and Craig, William (1958). Combinatory Logic. Volume I. Amsterdam: North-Holland Publishing Company.