Википедија

Funkcionalno programiranje

U računarstvu, funkcionalno programiranje je programska paradigma koja tretira program kao izračunavanje matematičkih funkcija i izbegava stanja i promenljive podatke. Akcenat je na primeni funkcija, u suprotnosti sa stilom imperativnog programiranja, kod koga je naglasak na promeni stanja.[1] Koreni funkcionalnog programiranja leže u lambda računu, formalnom sistemu razvijenom tokom 1930-ih radi proučavanja definicije i primene funkcija i rekurzije. Mnogi funkcionalni programski jezici mogu da se posmatraju kao praktična razrada teoretskog lambda računa.[1]

U praksi, razlika između matematičke funkcije i pojma funkcije koji se koristi u imperativnom programiranju je u tome što imperativne funkcije mogu da imaju bočne efekte, zbog toga što mogu da promene vrednosti već izvršenih izračunavanja. Zbog ovoga, njima nedostaje referencijalna transparentnost, to jest, isti izraz može da dovede do različitih rezultata u različitim trenucima, u zavisnosti od stanja programa koji se izvršava. Sa druge strane, u funkcionalnom kodu, izlazna vrednost funkcije zavisi samo od argumenata koji se proslede funkciji, pa tako pozivanje funkcije f dva puta, sa istom vrednošću argumenta x će proizvesti isti rezultat, f(x) oba puta. Eliminisanjem bočnih efekata razumevanje i predviđanje ponašanja programa može da postane mnogo lakše, i ovo je jedna od ključnih motivacija za razvoj funckionalnog programiranja.[1]

Funkcionalni programski jezici, posebno oni koji su čisto funkcionalni, se više koriste na univerzitetima nego u komercijalnom razvoju softvera. Međutim među značajnijim funkcionalnim programskim jezicima koji se koriste u komercijalnoj primeni su Erlang,[2] OCaml,[3] Haskel,[4] Scheme[5] i domen-specifični programski jezici kao što su R (statistika),[6] Mathematica (simbolička matematika),[7] J i K (finansijska analiza), i XSLT (XML).[8][9] Široko korišćeni deklarativni domen-specifični jezici kao što su SQL i Lex/Yacc, koriste neke elemente funkcionalnog programiranja, posebno u izbegavanju promenljivih vrednosti.[10] Spredšitovi takođe mogu da se posmatraju kao funkcionalni programski jezici.[11]

Programiranje u funkcionalnom stilu može da se postigne i u jezicima kao što su C, C++, Python, ili Java, koji nisu specifično dizajnirani za funkcionalno programiranje.

Istorija

uredi

Lambda račun pruža teorijski okvir za opisivanje funkcija i njihovo izračunavanje. Mada se radi o matematičkoj apstrakciji, a ne o programskom jeziku, on predstavlja osnovu skoro svih modernih funkcionalnih programskih jezika. Ekvivalentna teorijska formulacija, kombinatorna logika, se obično smatra apstraktnijom od lambda računa. Ona se koristi u nekim ezoteričnim jezicima, kao što je Unilambda. I kombinatorna logika i lambda račun su razvijeni da bi se postigao jasniji pristup osnovama matematike.[12]

Rani jezik sa funkcionalnim akcentom je bio Lisp, koji je razvio Džon Makarti dok je bio na MIT za IBM seriju 700/7000 naučnih računara krajem 1950-ih.[13] Lisp je uveo mnoge osobinee koje se sada javljaju u programskim jezicima, mada je on tehnički multi-paradigmatski jezik. Programski jezici Scheme i Dylan predstavljaju kasnije pokušaje da se pojednostavi i unapredi Lisp.

Jezik za procesiranje podataka (IPL) se ponekad navodi kao prvi računarski funkcionalni programski jezik. To je jezik asemblerskog stila za manipulisanje listama simbola. On poseduje pojam generatora koji se odnosi na funkciju koja prima funkciju kao argument, a kako se radi o jeziku na asemblerskom nivou, kod može da se interpretira na isti način kao i podaci, tako da može da se posmatra da IPL ima funkcije višeg reda. Međutim, ovaj jezik se značajno oslanja na određena imperativna svojstva.

Kenet E. Ajverson je razvio programski jezik APL početkom 1960-ih. Opisao ga je u svojoj knjizi A Programming Language. APL je izvršio najveći uticaj na Bakusov FP. Početkom 1990-ih, Ajverson i Rodžer Hui su razvili naslednika APL, programski jezik J. Sredinom 1990-ih, Artur Vitni, koji je prethodno radio sa Ajversonom, je razvio programski jezik K, koji se komercijalno koristi u finansijskom sektoru.

Džon Bakus je predstavio programski jezik FP 1977. godine u svom govoru tokom primanja Tjuringove nagrade Da li programiranje može da bude osloboženo fon Nojmanovog stila? Funkcionalni stil i njegova algebra programa Arhivirano na sajtu Wayback Machine (21. jun 2007). Bakusov rad je popularizovao istraživanje funkcionalnog programiranja, mada je njegov akcenat bio na programiranju na nivou funkcija a ne na stilu lambda računa koji je postao vezan za funkcionalno programiranje.

Tokom 1970-ih, Robin Milner sa Univerziteta u Edinburgu je razvio programski jezik ML, a Dejvid Tarner je radio na jeziku SASL na Univerzitetu Sent Endruz i kasnije na jeziku Miranda na Univerzitetu u Kentu. ML se kasnije razvio u nekoliko dijalekata, od kojih su najpoznatiji Objective Caml i Standard ML. Takođe, krajem 1970-ih, razvoj programskog jezika Scheme (delom funkcionalnog dijalekta Lisp-a) je raširio svest o moći funkcionalnog programiranja u širim programerskim zajednicama.

Tokom 1980-ih, Per Martin-Lef je razvio intuicionističku teoriju tipova (takođe poznatu kao konstruktivna teorija tipova), koja je povezala funkcionalne programe sa konstruktivnim dokazima proizvoljno kompleksnih matematičkih iskaza izraženih u obliku zavisnih tipova. Ovo je dovelo do moćnih novih pristupa interaktivnom dokazivanju teorema i uticalo na razvoj mnogih budućih funkcionalnih programskih jezika.

Programski jezik Haskel je nastao krajem 1980-ih u pokušaju da se u jednom jeziku spoje mnoge ideje u istraživanju funkcionalnog programiranja.

Koncepti

uredi

Postoji više koncepata i paradigmi koji su specifični za funkcionalno programiranje, a ne koriste se u imperativno programiranje (uključujući i objektno orijentisano programiranje). Međutim, programski jezici su često hibridi više programskih paradigmi, tako da programeri koji koriste uglavnom imperativne jezike ponekad koriste i neke od ovih koncepata.[14]

Funkcije višeg reda

uredi

Funkcije višeg reda su one funkcije koje mogu da uzimaju druge funkcije kao svoje argumente, i da ih vraćaju kao rezultat. (Primeri su operatori u matematici, kao što je diferencijalni operator   koji daje izvod kada se primeni na funkciju  .)

Funkcije višeg reda su u bliskoj vezi sa funkcijama prve klase, pošto i funkcije višeg reda i funkcije prve klase mogu da imaju funkcije kao argumente i da vraćaju druge funkcije. Razlika između ova dva pojma je suptilna: višeg reda opisuje matematički koncept funkcija koje operišu nad drugim funkcijama, dok prva klasa u računarstvu označava entitete programskog jezika koji nemaju ograničenja za svoju upotrebu (stoga funkcije prve klase mogu da se pojavljuju bilo gde u programu gde i drugi entiteti prve klase, kao što su brojevi, uključujući i kao argumenti drugih funkcija i njihove povratne vrednosti..

Funkcije višeg reda omogućavaju kariing (engl. currying), tehniku kod koje se funkcija primenjuje na jedan po jedan svoj argument, a svaka primena vraća novu funkciju koja prima sledeći argument.

Čiste funkcije

uredi

Čisto funkcionalne funkcije (ili izrazi) nemaju pamćenje ili ulazno/izlazne bočne efekte, osim ako se samo izračunavanje računa kao sporedni efekat. Ovo znači da čiste funkcije imaju nekoliko korisnih svojstava, od kojih mnoga mogu da se koriste za optimizovanje koda:

  • Ako se rezultat čistog izraza ne koristi, on može da bude uklonjen, i time se ne utiče na ostale izraze.
  • Ako se čista funkcija poziva sa parametrima koji ne prouzrokuju bočne efekte, rezultat je konstanta u odnosu na tu listu parametara (to se ponekad naziva referencijalna transparentnost), to jest, ako se čista funkcija ponovo pozove sa istim parametrima, rezultat će biti isti (ovo omogućava optimizacije sa keširanjem).
  • Ako ne postoji zavisnost u podacima između dva čista izraza, njihov redosled može da bude zamenjen ili mogu da budu izračunati paralelno, i neće uticati jedan na drugi (drugim rečima, izračunavanje svakog čistog izraza je tred-bezbedno).
  • Ako ceo jezik ne dozvoljava bočne efekte, onda može da se koristi bilo koja strategija izračunavanja; ovo kompajleru ostavlja slobodu da preuredi ili kombinuje izračunavanja izraza u programu (na primer, korišćenjem deforestacije).

Iako većina kompajlera za imperativne programske jezike detektuje čiste izraze, i vrše uobičajenu eliminaciju poziva čistih funkcija u podizrazima, oni ne mogu uvek ovo sprovedu za prekompajlirane biblioteke, koje načelno ne otkrivaju ove informacije, i time sprečavaju optimizovanje koje uključuje te spoljašnje funkcije. Neki kompajleri, kao što je gcc, imaju dodatne ključne reči koje programeru omogućavaju da eksplicitno označi spoljašnje funkcije kao čiste, kako bi omogućio takve optimizacije. Fortran 95 omogućava da funkcije budu označene kao čiste.

Rekurzija

uredi
Glavni članak: Rekurzija (računarstvo)

Strogo i ne-strogo izračunavanje

uredi
Glavni članak: Strategije izračunavanja

Reference

uredi
  1. ^ a b v Hudak, Pol (1989). „Koncept, evolucija i primena funkcionalnih programskih jezika” (PDF). ACM Computing Surveys. 21 (3): 359—411. doi:10.1145/72551.72554. Arhivirano iz originala (PDF) 20. 3. 2009. g. Pristupljeno 20. 4. 2009. 
  2. ^ 0 „Ko koristi Erlang za razvoj proizvoda?” Proverite vrednost parametra |url= (pomoć). Često postavljanja pitanja o Erlangu. Pristupljeno 5. 8. 2007. 
  3. ^ Minski, Jaron; Viks, Stiven (2008). „Caml trgovina - iskustva sa funkcionalnim programiranjem na Vol stritu”. Žurnal Funkcionalnog programiranja. Cambridge University Press. 18 (4): 553—564. doi:10.1017/S095679680800676X. Pristupljeno 27. 8. 2008. 
  4. ^ „"Haskel - Haskel viki”. Pristupljeno 27. 8. 2008. 
  5. ^ Klinger, Vil (1987). "Multitasking i MacScheme". MacTech 3 (12). http://www.mactech.com/articles/mactech/Vol.03/03.12/Multitasking/index.html. Dobavljeno dana 2008-08-28.
  6. ^ The useR! 2006 raspored konferencije uključuje radove o komercijalnoj upotrebi jezika R, Pristupljeno 29. 4. 2013.
  7. ^ Odeljenje za primenjenu matematiku; Koloradu, Univerzitet u. „Funkcionalni vs. proceduralni programski jezik”. Arhivirano iz originala 13. 11. 2007. g. Pristupljeno 28. 8. 2006. 
  8. ^ Novačev, Dimitre. „Funkcionalni programski jezik XSLT - Dokaz kroz primere”. TopXML. Arhivirano iz originala 18. 05. 2006. g. Pristupljeno 27. 5. 2006. 
  9. ^ Merc, Dejvid. „XML Programska paradigma (četvrti deo): Prilaz funkcionalnog programiranja XML-u”. IBM developerWorks. Arhivirano iz originala 15. 08. 2007. g. Pristupljeno 27. 5. 2006. 
  10. ^ Čemberlen, Donald D.; Rejmond F. Bojs (1974). „SEQUEL: Strukturisani engleski jezik za upite”. Proceedings of the 1974 ACM SIGFIDET: 249—264. . U ovom radu, koji predstavlja jednu od prvih formalnih prezentacija kocepata SQL-a (i pre nego što je ime kasnije skraćeno), Čemberlen i Bojs ističu da je SQL razvijen „Bez posezanja za konceptima vezanih promenljivih i kvantifikatora“.
  11. ^ Džons, Sajmon Pejton; Barnet, Margaret; Blekvel, Alan (2003). „Unapređivanje najpopularnijeg funkcionalnog programskog jezika na svetu: korisnički definisane funkcije u Ekscelu”. 
  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). Arhivirano iz originala 27. 08. 2006. g. Pristupljeno 31. 8. 2006. 

Literatura

uredi

Spoljašnje veze

uredi


  1. ^ „Greg Michaelson's Homepage”. Mathematical and Computer Sciences. Riccarton, Edinburgh: Heriot-Watt University. Pristupljeno 6. 11. 2022. 
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Функционално_програмирање&oldid=27555724”