Функција прве класе
У информатици се каже да програмски језик има функције прве класе ако функције третира као објекте прве класе. То значи да језик подржава слање функција као аргументе другим функцијама, при чему их враћа као вредност других функција и додељује их променљивама или их чува у структурама података.[1] Неки програмски језици захтевају подршку анонимних фунција.[2] У језицима са првокласним функцијама, називи функција немају никакав специјалан статус, третирају се као обичне променљиве са типом функције.[3] Израз је први употребио Christopher Strachey у контексту „functions as first-class citizens“ средином 1960-их. [4]
Функције прве класе су нужне за функционално програмирање, у којем је употреба функција вишег реда стандардна пракса. Једноставан пример функције вишег реда је функција мапе, која као своје аргументе узима функцију и листу, и враћа листу формирану применом функције на сваки члан листе. Да би језик подржао мапу, мора подржати прослеђивање функције као аргумента.
Постоје одређене потешкоће у имплементацији при преношењу функција као аргумената или њиховог чувања као резултат, посебно у присуству не-локалних променљивих које су унете у угнеждене или анонимне функције. Током историје, то су назвали фунарг проблемом, назив који потиче из „function argument“.[5] У раним императивним језицима ови проблеми су избегнути или не подржавањем функција као резултата или изостављањем угнеждених функција, а тиме и не-локалних променљивих. Ранији функционални језик Лисп имао је приступ динамичком опсегу, где се нелокалне променљиве односе на најближу дефиницију те променљиве на месту где се функција извршава, уместо на месту где је дефинисана. Одговарајућа подршка за лексички обухваћене првокласне функције уведена је у Scheme и захтева руковање референцама на функције као затворења уместо голих функцијских показивача, што заузврат чини garbage collection неопходним.[6]
Контекст уреди
У овом одељку упоређујемо како се рукује појединим програмским идиомима на функционалном језику са првокласним функцијама у поређењу са императивним језиком где су функције објекти друге класе.
Функције вишег реда: прослеђивање функција попут аргумената уреди
У језицима где су функције објекти прве класе, функције се могу проследити као аргументи другим функцијама на исти начин као и друге вредносит. На језику Haskell:
map :: (a -> b) -> [a] -> [b]map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
Језици у којима функције нису првокласне и даље омогућавају писање функција вишег реда коришћењем показивача на функције или делегата. У језику С:[7]
void map(int (*f)(int), int x[], size_t n) {
for (int i = 0; i < n; i++)
x[i] = f(x[i]);
}
Између ова 2 примера, постоји низ разлика између два приступа која нису директно повезана са подршком првокласних функција. Haskell узорак ради са листама, док С узорак ради са низовима. Оба узорка су најприродније структуре података на одговарајућим језицима, и ако би С узорак радио са повезаним листама, то би се чинило непотребно сложеним. Ово такође објашњава чињеницу да С функцији треба додатни параметар. Функција С ажурира низ на место, при чему не враћа никакву вредност, док су Haskell структуре података постојане. Haskell узорак користи рекурзију да пређе листу, док С узорак користи итерацију. Поново, ово је најприроднији начин да се изрази ова функција на оба језика, али Haskell узорак се лако може изразити у облику набора а С узорак у облику рекурзије. Коначно, Haskell функција има полиморфни тип, али С ово не подржава па смо фиксирали све променљиве на константу типа int.
Анонимне и угнеждене функције уреди
На језицима који подржавају анонимне функције, можемо проследити функцију као аргумент функцији вишег реда.
main=map(\x -> 3 * x + 1)[1, 2, 3, 4, 5]
На језику који не подржава анонимне функције, морамо да је вежемо за назив:
int f(int x) {
return 3 * x + 1;
}
int main() {
int list[] = {1, 2, 3, 4, 5};
map(f, list, 5);
}
Не-локалне променљиве и затворења уреди
Једном када имамо анонимне или угнеждене функције, природно је да се позивају на променљиве изван свог тела:
main = let a = 3
b = 1
in map (\x -> a * x + b) [1, 2, 3, 4, 5]
Ако су функције представљене голим показивачима, ми више не знамо како се вредност изван тела функције прослеђује и због тога затворење треба изградити мануелно. Стога овде не можемо говорити о првокласним функцијама.
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);
}
Такође запазите да је мапа сада специјализована за функције које се односе на два int-a изван њихове средине. Ово се може подесити, али захтева више boilerplate кода.[8] Ако би f била угнеждена функција и даље бисмо наишли на исти проблем, и то је разлог зашто их С не подржава.[9]
Функције вишег реда: враћање функција као резултат уреди
Када враћамо функцију, ми заправо њено затворење. У примеру C-а било која локална променљива ухваћена затворењем ће изаћи из опсега једном када се вратимо из функције која гради затворење. Форсирање затворења у неком каснијем временском тренутку резултираће недефинисаним понашањем, врло могуће корумпирањем стека. Ово је познато као улазни проблем фунарга.[10]
Додељивање функција променљивама уреди
Додељивање функција променљивама и њихово складиштење унутар структуре података потенцијално трпи исте потешкоће као и повратне функције.
f :: [[Integer] -> [Integer]]
f = let a = 3
b = 1
in [map (\x -> a * x + b), map (\x -> b * x + a)]
Једнакост функција уреди
Како се може тестирати већина литерала и вредности за једнакост, природно је питати се да ли програмски језик може подржати тестирање функција једнакости. Даљим истраживањем, ово питање се чини тежим и треба разликовати неколико типова једнакости.
Екстензивна једнакост
Две функције f и g сматрају се екстензивно једнаким ако се слажу са својим излазима за све улазе (∀x. f(x) = g(x)). Под овом дефиницијом за једнакост, на пример, било које две имплементације стабилног алгоритма сортирања, као што су сортирање уметањем и спајањем, сматраће се једнаким. Одлучивање о екстензионалној једнакости уопште није одлучно, чак и ни за функције са ограниченим доменима. Из тог разлога ни један програмски језик не имплементира једнакост као једнакост екстензија.[11]
Интензионална једнакост
Под овом једнакошћу, функције f и g сматрају се једнаким ако имају исту унутрашњу структуру. Ова врста једнакости може се имплементирати у интерпретираним језицима упоређивањем изворног кода тела функција или објектног кода у компајлираним језицима.[12]
Референтна једнакост
С обзиром на непрактичност примене екстензивне и интезивне једнакости, већина језика који подржавају испитивање функција једнакости користи референтну једнакост. Свим функцијама и затворењима додељен је јединствени идентификатор, а једнакост се базира на једнакости идентификатора. Две одвојено дефинисане, али иначе идентичне дефиниције функције сматраће се неједнаким. Референтна једнакост нарушава референтну транспарентност и зато није подржана у чистим језицима као што је Haskell.
Теорија типова уреди
У теорији типова, тип функције прихвата вредност типа А и враћа вредности типа Б и може се записати као A → B или BA. У коресподенцији Curry–Howard, типови функција су повезани логичком импликацијом; апстракција ламбда одговара испуњењу хипотетских претпоставки,а примена функције одговара начину закључивања модуса. Поред уобичајеног случаја програмских функција, теорија типова користи и првокласне функције за моделирање асоцијативних низова и сличних структура података.
Језичка подршка уреди
Функционални програмски језици, као што су Scheme, ML, Haskell, F#, и Scala, сви имају првокласне функције. Када је Лисп, један од најранијих функционалних језика био дизајниран, није било могуће разумети све аспекте првокласних функција, што је резултирало динамичким обухватањем функција. Каснији дијалекти Scheme и уобичајени Лисп имају лексички обухваћене првокласне функције.
За императивне језике треба направити разлику између Algol-а и његових потомака као што су Pascal, традиционална породица C-а и модерне garbage-collected варијанте.Породица Algol је дозволила угнеждене функције и узимање функција вишег реда као аргументе, али не и функције вишег реда које враћају функције као резултате Разлог за то је био то што није било познато како да се поступа са не-локалним променљивим ако се као резултат врати угнеждена функција.
Породица C-а је дозволила обе пролазне функције као аргументе и вратила их као резултате, али је избегла било какве проблеме не подржавајући угнеждене функције. Будући да корист враћања функција пре свега лежи у могућности враћања угнеждених функција које су узеле не-локалне променљиве, уместо функција на највишем нивоу, обично се не сматра да ови језици имају први -разредне функције.
Савремени императивни језици често подржавају garbage-collection чинећи имплементацију првокласних функција изводљивом. Првокласне функције често су подржане само у каснијим верзијама језика, укључујући C# 2.0 иApple's Blocks проширење на C, C++ и Objective-C. C.11 је додао подршку анонимним функцијама и затворењу језика, али због природе језика који је сакупљен без ђубрета мора се посебно пазити да се не-локалне променљиве у функцијама врате као резултати.
С++
С++ затворења могу ухватити не-локалну променљиву по референци, копирањем или померањем конструкције. Избегава се скупа копија и омогућава модификовање оригиналне променљиве, али није сигурно у случају када се врати затворење. Друго је сигурно ако је затворење враћено али захтева копије и не може се користити за модификовање оригиналне променљиве. Касније је сигурно ако се затворење врати и не захтева копије, али се не може користити за промену оригиналне променљиве.[13]
Java
Java 8 затворења могу заробити само финалне или „ефективно финалне“ не-локалне променљиве. Типови функција у Јави представљени су као класе. Анонимне функције узимају тип закључен из контекста. Референце метода су ограничене.
Lisp
Варијанте Лисп-а с лексичким опсегом подржавају затворење. Варијанте са динамичким опсегом не подржавају затворења или им је потребна посебан конструктор за стварање затворења.
У Common Lisp, идентификатор функције у функцији namespace не може се користити као референца на првокласну вредност. Посебна функција оператора мора се користити за дохватање функције као вредности.[14]
Ruby
Идентификатор регуларне "функције" у Руби-у не може се користити као вредност или пренети. Прво се мора дохватити у Методи или Proc object да би се користио као првокласни податак. Синтакса за позивање таквог функционалног објекта разликује се од позивања регуларних метода.[1]
Види још уреди
Референце уреди
- ^ „Structure and interpretation of computer programs : Abelson, Harold : Free Download, Borrow, and Streaming”. Internet Archive (на језику: енглески). Приступљено 2020-08-22.
- ^ Scott, Michael Lee (1999). Programming language pragmatics (на језику: енглески). 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. Архивирано из оригинала 05. 08. 2020. г. Приступљено 2020-08-22.
- ^ Higher-Order and Symbolic Computation (на језику: енглески), 2017-08-29, Приступљено 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” (на језику: енглески).
- ^ Garbage collection (computer science) (на језику: енглески), 2020-07-22, Приступљено 2020-08-22
- ^ Delegate (CLI) (на језику: енглески), 2020-05-11, Приступљено 2020-08-22
- ^ Boilerplate code (на језику: енглески), 2020-06-08, Приступљено 2020-08-22
- ^ „Nested Functions - Using the GNU Compiler Collection (GCC)”. gcc.gnu.org. Приступљено 2020-08-22.
- ^ Funarg problem (на језику: енглески), 2020-06-20, Приступљено 2020-08-22
- ^ Sorting algorithm (на језику: енглески), 2020-08-21, Приступљено 2020-08-22
- ^ Interpreted language (на језику: енглески), 2020-07-02, Приступљено 2020-08-22
- ^ C++11 (на језику: енглески), 2020-08-10, Приступљено 2020-08-22
- ^ Wayback Machine (на језику: енглески), 2020-08-19, Приступљено 2020-08-22