Funkcija prve klase
U informatici se kaže da programski jezik ima funkcije prve klase ako funkcije tretira kao objekte prve klase. To znači da jezik podržava slanje funkcija kao argumente drugim funkcijama, pri čemu ih vraća kao vrednost drugih funkcija i dodeljuje ih promenljivama ili ih čuva u strukturama podataka.[1] Neki programski jezici zahtevaju podršku anonimnih funcija.[2] U jezicima sa prvoklasnim funkcijama, nazivi funkcija nemaju nikakav specijalan status, tretiraju se kao obične promenljive sa tipom funkcije.[3] Izraz je prvi upotrebio Christopher Strachey u kontekstu „functions as first-class citizens“ sredinom 1960-ih. [4]
Funkcije prve klase su nužne za funkcionalno programiranje, u kojem je upotreba funkcija višeg reda standardna praksa. Jednostavan primer funkcije višeg reda je funkcija mape, koja kao svoje argumente uzima funkciju i listu, i vraća listu formiranu primenom funkcije na svaki član liste. Da bi jezik podržao mapu, mora podržati prosleđivanje funkcije kao argumenta.
Postoje određene poteškoće u implementaciji pri prenošenju funkcija kao argumenata ili njihovog čuvanja kao rezultat, posebno u prisustvu ne-lokalnih promenljivih koje su unete u ugneždene ili anonimne funkcije. Tokom istorije, to su nazvali funarg problemom, naziv koji potiče iz „function argument“.[5] U ranim imperativnim jezicima ovi problemi su izbegnuti ili ne podržavanjem funkcija kao rezultata ili izostavljanjem ugneždenih funkcija, a time i ne-lokalnih promenljivih. Raniji funkcionalni jezik Lisp imao je pristup dinamičkom opsegu, gde se nelokalne promenljive odnose na najbližu definiciju te promenljive na mestu gde se funkcija izvršava, umesto na mestu gde je definisana. Odgovarajuća podrška za leksički obuhvaćene prvoklasne funkcije uvedena je u Scheme i zahteva rukovanje referencama na funkcije kao zatvorenja umesto golih funkcijskih pokazivača, što zauzvrat čini garbage collection neophodnim.[6]
Kontekst uredi
U ovom odeljku upoređujemo kako se rukuje pojedinim programskim idiomima na funkcionalnom jeziku sa prvoklasnim funkcijama u poređenju sa imperativnim jezikom gde su funkcije objekti druge klase.
Funkcije višeg reda: prosleđivanje funkcija poput argumenata uredi
U jezicima gde su funkcije objekti prve klase, funkcije se mogu proslediti kao argumenti drugim funkcijama na isti način kao i druge vrednosit. Na jeziku Haskell:
map :: (a -> b) -> [a] -> [b]map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
Jezici u kojima funkcije nisu prvoklasne i dalje omogućavaju pisanje funkcija višeg reda korišćenjem pokazivača na funkcije ili delegata. U jeziku S:[7]
void map(int (*f)(int), int x[], size_t n) {
for (int i = 0; i < n; i++)
x[i] = f(x[i]);
}
Između ova 2 primera, postoji niz razlika između dva pristupa koja nisu direktno povezana sa podrškom prvoklasnih funkcija. Haskell uzorak radi sa listama, dok S uzorak radi sa nizovima. Oba uzorka su najprirodnije strukture podataka na odgovarajućim jezicima, i ako bi S uzorak radio sa povezanim listama, to bi se činilo nepotrebno složenim. Ovo takođe objašnjava činjenicu da S funkciji treba dodatni parametar. Funkcija S ažurira niz na mesto, pri čemu ne vraća nikakvu vrednost, dok su Haskell strukture podataka postojane. Haskell uzorak koristi rekurziju da pređe listu, dok S uzorak koristi iteraciju. Ponovo, ovo je najprirodniji način da se izrazi ova funkcija na oba jezika, ali Haskell uzorak se lako može izraziti u obliku nabora a S uzorak u obliku rekurzije. Konačno, Haskell funkcija ima polimorfni tip, ali S ovo ne podržava pa smo fiksirali sve promenljive na konstantu tipa int.
Anonimne i ugneždene funkcije uredi
Na jezicima koji podržavaju anonimne funkcije, možemo proslediti funkciju kao argument funkciji višeg reda.
main=map(\x -> 3 * x + 1)[1, 2, 3, 4, 5]
Na jeziku koji ne podržava anonimne funkcije, moramo da je vežemo za naziv:
int f(int x) {
return 3 * x + 1;
}
int main() {
int list[] = {1, 2, 3, 4, 5};
map(f, list, 5);
}
Ne-lokalne promenljive i zatvorenja uredi
Jednom kada imamo anonimne ili ugneždene funkcije, prirodno je da se pozivaju na promenljive izvan svog tela:
main = let a = 3
b = 1
in map (\x -> a * x + b) [1, 2, 3, 4, 5]
Ako su funkcije predstavljene golim pokazivačima, mi više ne znamo kako se vrednost izvan tela funkcije prosleđuje i zbog toga zatvorenje treba izgraditi manuelno. Stoga ovde ne možemo govoriti o prvoklasnim funkcijama.
typedef struct {
int (*f)(int, int, int);
int *a;
int *b;
} closure_t;
void map(closure_t *closure, int x[], size_t n) {
for (int i = 0; i < n; ++i)
x[i] = (*closure->f)(*closure->a, *closure->b, x[i]);
}
int f(int a, int b, int x) {
return a * x + b;
}
void main() {
int l[] = {1, 2, 3, 4, 5};
int a = 3;
int b = 1;
closure_t closure = {f, &a, &b};
map(&closure, l, 5);
}
Takođe zapazite da je mapa sada specijalizovana za funkcije koje se odnose na dva int-a izvan njihove sredine. Ovo se može podesiti, ali zahteva više boilerplate koda.[8] Ako bi f bila ugneždena funkcija i dalje bismo naišli na isti problem, i to je razlog zašto ih S ne podržava.[9]
Funkcije višeg reda: vraćanje funkcija kao rezultat uredi
Kada vraćamo funkciju, mi zapravo njeno zatvorenje. U primeru C-a bilo koja lokalna promenljiva uhvaćena zatvorenjem će izaći iz opsega jednom kada se vratimo iz funkcije koja gradi zatvorenje. Forsiranje zatvorenja u nekom kasnijem vremenskom trenutku rezultiraće nedefinisanim ponašanjem, vrlo moguće korumpiranjem steka. Ovo je poznato kao ulazni problem funarga.[10]
Dodeljivanje funkcija promenljivama uredi
Dodeljivanje funkcija promenljivama i njihovo skladištenje unutar strukture podataka potencijalno trpi iste poteškoće kao i povratne funkcije.
f :: [[Integer] -> [Integer]]
f = let a = 3
b = 1
in [map (\x -> a * x + b), map (\x -> b * x + a)]
Jednakost funkcija uredi
Kako se može testirati većina literala i vrednosti za jednakost, prirodno je pitati se da li programski jezik može podržati testiranje funkcija jednakosti. Daljim istraživanjem, ovo pitanje se čini težim i treba razlikovati nekoliko tipova jednakosti.
Ekstenzivna jednakost
Dve funkcije f i g smatraju se ekstenzivno jednakim ako se slažu sa svojim izlazima za sve ulaze (∀x. f(x) = g(x)). Pod ovom definicijom za jednakost, na primer, bilo koje dve implementacije stabilnog algoritma sortiranja, kao što su sortiranje umetanjem i spajanjem, smatraće se jednakim. Odlučivanje o ekstenzionalnoj jednakosti uopšte nije odlučno, čak i ni za funkcije sa ograničenim domenima. Iz tog razloga ni jedan programski jezik ne implementira jednakost kao jednakost ekstenzija.[11]
Intenzionalna jednakost
Pod ovom jednakošću, funkcije f i g smatraju se jednakim ako imaju istu unutrašnju strukturu. Ova vrsta jednakosti može se implementirati u interpretiranim jezicima upoređivanjem izvornog koda tela funkcija ili objektnog koda u kompajliranim jezicima.[12]
Referentna jednakost
S obzirom na nepraktičnost primene ekstenzivne i intezivne jednakosti, većina jezika koji podržavaju ispitivanje funkcija jednakosti koristi referentnu jednakost. Svim funkcijama i zatvorenjima dodeljen je jedinstveni identifikator, a jednakost se bazira na jednakosti identifikatora. Dve odvojeno definisane, ali inače identične definicije funkcije smatraće se nejednakim. Referentna jednakost narušava referentnu transparentnost i zato nije podržana u čistim jezicima kao što je Haskell.
Teorija tipova uredi
U teoriji tipova, tip funkcije prihvata vrednost tipa A i vraća vrednosti tipa B i može se zapisati kao A → B ili BA. U korespodenciji Curry–Howard, tipovi funkcija su povezani logičkom implikacijom; apstrakcija lambda odgovara ispunjenju hipotetskih pretpostavki,a primena funkcije odgovara načinu zaključivanja modusa. Pored uobičajenog slučaja programskih funkcija, teorija tipova koristi i prvoklasne funkcije za modeliranje asocijativnih nizova i sličnih struktura podataka.
Jezička podrška uredi
Funkcionalni programski jezici, kao što su Scheme, ML, Haskell, F#, i Scala, svi imaju prvoklasne funkcije. Kada je Lisp, jedan od najranijih funkcionalnih jezika bio dizajniran, nije bilo moguće razumeti sve aspekte prvoklasnih funkcija, što je rezultiralo dinamičkim obuhvatanjem funkcija. Kasniji dijalekti Scheme i uobičajeni Lisp imaju leksički obuhvaćene prvoklasne funkcije.
Za imperativne jezike treba napraviti razliku između Algol-a i njegovih potomaka kao što su Pascal, tradicionalna porodica C-a i moderne garbage-collected varijante.Porodica Algol je dozvolila ugneždene funkcije i uzimanje funkcija višeg reda kao argumente, ali ne i funkcije višeg reda koje vraćaju funkcije kao rezultate Razlog za to je bio to što nije bilo poznato kako da se postupa sa ne-lokalnim promenljivim ako se kao rezultat vrati ugneždena funkcija.
Porodica C-a je dozvolila obe prolazne funkcije kao argumente i vratila ih kao rezultate, ali je izbegla bilo kakve probleme ne podržavajući ugneždene funkcije. Budući da korist vraćanja funkcija pre svega leži u mogućnosti vraćanja ugneždenih funkcija koje su uzele ne-lokalne promenljive, umesto funkcija na najvišem nivou, obično se ne smatra da ovi jezici imaju prvi -razredne funkcije.
Savremeni imperativni jezici često podržavaju garbage-collection čineći implementaciju prvoklasnih funkcija izvodljivom. Prvoklasne funkcije često su podržane samo u kasnijim verzijama jezika, uključujući C# 2.0 iApple's Blocks proširenje na C, C++ i Objective-C. C.11 je dodao podršku anonimnim funkcijama i zatvorenju jezika, ali zbog prirode jezika koji je sakupljen bez đubreta mora se posebno paziti da se ne-lokalne promenljive u funkcijama vrate kao rezultati.
S++
S++ zatvorenja mogu uhvatiti ne-lokalnu promenljivu po referenci, kopiranjem ili pomeranjem konstrukcije. Izbegava se skupa kopija i omogućava modifikovanje originalne promenljive, ali nije sigurno u slučaju kada se vrati zatvorenje. Drugo je sigurno ako je zatvorenje vraćeno ali zahteva kopije i ne može se koristiti za modifikovanje originalne promenljive. Kasnije je sigurno ako se zatvorenje vrati i ne zahteva kopije, ali se ne može koristiti za promenu originalne promenljive.[13]
Java
Java 8 zatvorenja mogu zarobiti samo finalne ili „efektivno finalne“ ne-lokalne promenljive. Tipovi funkcija u Javi predstavljeni su kao klase. Anonimne funkcije uzimaju tip zaključen iz konteksta. Reference metoda su ograničene.
Lisp
Varijante Lisp-a s leksičkim opsegom podržavaju zatvorenje. Varijante sa dinamičkim opsegom ne podržavaju zatvorenja ili im je potrebna poseban konstruktor za stvaranje zatvorenja.
U Common Lisp, identifikator funkcije u funkciji namespace ne može se koristiti kao referenca na prvoklasnu vrednost. Posebna funkcija operatora mora se koristiti za dohvatanje funkcije kao vrednosti.[14]
Ruby
Identifikator regularne "funkcije" u Rubi-u ne može se koristiti kao vrednost ili preneti. Prvo se mora dohvatiti u Metodi ili Proc object da bi se koristio kao prvoklasni podatak. Sintaksa za pozivanje takvog funkcionalnog objekta razlikuje se od pozivanja regularnih metoda.[1]
Vidi još uredi
Reference uredi
- ^ „Structure and interpretation of computer programs : Abelson, Harold : Free Download, Borrow, and Streaming”. Internet Archive (na jeziku: engleski). Pristupljeno 2020-08-22.
- ^ Scott, Michael Lee (1999). Programming language pragmatics (na jeziku: engleski). San Francisco: Morgan Kaufmann. ISBN 978-1-55860-442-1. OCLC 222529448.
- ^ „(R. Ierusalimschy, L. de Figueiredo, W. Celes) The Implementation of Lua 5.0”. www.jucs.org. doi:10.3217/jucs-011-07-1159. Arhivirano iz originala 05. 08. 2020. g. Pristupljeno 2020-08-22.
- ^ Higher-Order and Symbolic Computation (na jeziku: engleski), 2017-08-29, Pristupljeno 2020-08-22
- ^ Moses, Joel (1970-06-01). „The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem” (na jeziku: engleski).
- ^ Garbage collection (computer science) (na jeziku: engleski), 2020-07-22, Pristupljeno 2020-08-22
- ^ Delegate (CLI) (na jeziku: engleski), 2020-05-11, Pristupljeno 2020-08-22
- ^ Boilerplate code (na jeziku: engleski), 2020-06-08, Pristupljeno 2020-08-22
- ^ „Nested Functions - Using the GNU Compiler Collection (GCC)”. gcc.gnu.org. Pristupljeno 2020-08-22.
- ^ Funarg problem (na jeziku: engleski), 2020-06-20, Pristupljeno 2020-08-22
- ^ Sorting algorithm (na jeziku: engleski), 2020-08-21, Pristupljeno 2020-08-22
- ^ Interpreted language (na jeziku: engleski), 2020-07-02, Pristupljeno 2020-08-22
- ^ C++11 (na jeziku: engleski), 2020-08-10, Pristupljeno 2020-08-22
- ^ Wayback Machine (na jeziku: engleski), 2020-08-19, Pristupljeno 2020-08-22