Нацрт:Функција прве класе

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

У информатици, каже се да програмски језик има првокласне функције ако функције третира као првокласне поданике. То значи да језик подржава слање функција као аргументе другим функцијама, при чему их враћа као вредности других функција и додељује их променљивама или их чува у структурама података.[1] Неки програмски језици захтевају подршку анонимних функција. [2]У језицима са првокласним функцијама, називи функција немају никакав специјалан статус; третирају се као обичне променљиве са типом функције.[3] Израз је увеоChristopher Strachey у контексту „functions as first-class citizens“ средином 1960-их. [4]

Првокласне функције су неопходне за функционално програмирање, у којем је употреба функција вишег реда стандардна пракса. Једноставан пример функције вишег реда је функција мапе, која као своје аргументе узима функцију и листу и враћа листу формирану применом функције на сваког члана листе. Да би језик подржао мапу, мора подржати прослеђивање функције као аргумента.

Постоје одређене потешкоће у имплементацији при преношењу функција као аргумената или њиховог чувања као резултат, посебни у присуству не-локалних променљивих које су увежене у угнеждене или анонимне функције. Током историје, то су назвали funarg проблемом, назив који потиче из „function argument“. [5]У раним императивним језицима ови проблеми су избегнути или не подржавањем функција као резултата или изостављањем угнеждених функција, а тиме и не-локалних променљивих. Ранији функционални језик Лисп имао је приступ динамичком опсегу, где се не-локалне променљиве односе на најближу дефиницију те променљиве на месту где се функција извршава, уместо на месту где је дефинисана. Одговарајућа подршка за лексички обухваћене првокласне функције уведена је у Scheme и захтева руковање референцама на функције као затворења уместо голих функцијских показивача, што заузврат чини garbage collection неопходним.

Контекст[уреди | уреди извор]

У овом одељку упоређујемо како се рукује појединим програмским идиомима на функционалном језику првокласним функцијама у поређењу са императивним језиком где су функције поданици друге класе.

Функције вишег реда: прослеђивање функција попут аргумената[уреди | уреди извор]

У језицима где су функције првокласни поданици, функције се могу проследити као аргументи другим функцијама на исти начин као и друге вредносит. На језику Haskell:

map :: (a -> b) -> [a] -> [b]

map f []     = []

map f (x:xs) = f x : map f xs


Језици у којима функције нису првокласне и даље омогућавају писање функција вишег реда коришћењем показивача на функције или делегата. У језику С:

void map(int (*f)(int), int x[], size_t n) {

   for (int i = 0; i < n; i++)

       x[i] = f(x[i]);

}

Између ова 2 примера, постоји низ разлика између два приступа која нису директно повезана са подршком првокласних функција. The 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);

}


Такође запазите да је мапа сада специјализована за функције које се односе на два улаза изван њихове средине. Ово се може подесити, али захтева више boilerplate кода. Ако би f била угнеждена функција и даље бисмо наишли на исти проблем, и то је разлог зашто их С не подржава.[6]

Функције вишег реда: враћање функција као резултат[уреди | уреди извор]

Када враћамо функцију, ми заправо њено затворење. У примеру C-а било која локална променљива ухваћена затворењем ће изаћи из опсега једном када се вратимо из функције која гради затворење. Форсирање затворења у неком каснијем временском тренутку резултираће недефинисаним понашањем, врло могуће корумпирањем стека. Ово је познато као улазни проблем фунарга.

Додељивање функција променљивама[уреди | уреди извор]

Додељивање функција променљивама и њихово складиштење унутар структуре података потенцијално трпи исте потешкоће као и повратне функције.

f :: [[Integer] -> [Integer]]

f = let a = 3

       b = 1

    in [map (\x -> a * x + b), map (\x -> b * x + a)]

Додељивање функција променљивама и њихово складиштење унутар структуре података потенцијално трпи исте потешкоће као и повратне функције.

Једнакост функција[уреди | уреди извор]

Како се може тестирати већина литерала и вредности за једнакост, природно је питати се да ли програмски језик може подржати тестирање функција једнакости. Даљим истраживањем, ово питање се чини тежим и треба разликовати неколико типова једнакости.[7]

Екстензивна једнакост

Две функције  f и g сматрају се екстензивно једнаким ако се слажу са својим излазима за све улазе (∀x. f(x) = g(x)). Под овом дефиницијом за једнакост, на пример, било које две имплементације стабилног алгоритма сортирања, као што су сортирање уметањем и спајањем, сматраће се једнаким. Одлучивање о екстензионалној једнакости уопште није одлучно, чак и ни за функције са ограниченим доменима. Из тог разлога ни један програмски језик не имплементира једнакост као једнакост екстензија.

Интензионална једнакост

Под овом једнакошћу, функције f и g сматрају се једнаким ако имају исту унутрашњу структуру. Ова врста једнакости може се имплементирати у интерпретираним језицима упоређивањем изворног кода тела функција или објектног кода у компајлираним језицима.

Референтна једнакост

С обзиром на непрактичност примене екстензивне и интезивне једнакости, већина језика који подржавају испитивање функција једнакости користи референтну једнакост. Свим функцијама и затворењима додељен је јединствени идентификатор, а једнакост се базира на једнакости идентификатора. Две одвојено дефинисане, али иначе идентичне дефиниције функције сматраће се неједнаким. Референтна једнакост нарушава референтну транспарентност и зато није подржана у чистим језицима као што је 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 је додао подршку анонимним функцијама и затворењу језика, али због природе језика који је сакупљен без ђубрета мора се посебно пазити да се не-локалне променљиве у функцијама врате као резултати.

Language Higher-order functions Nested functions Non-local variables Notes
Arguments Results Named Anonymous Closures Partial application
Algol family ALGOL 60 Yes No Yes No Downwards No Have function types.
ALGOL 68 Yes Yes Yes Yes Downwards No
Pascal Yes No Yes No Downwards No
Ada Yes No Yes No Downwards No
Oberon Yes Non-nested only Yes No Downwards No
Delphi Yes Yes Yes 2009 2009 No
C family C Yes Yes No No No No Has function pointers.
C++ Yes Yes C++11[8] C++11 C++11 C++11 Has function pointers, function objects. (Also, see below.)

Explicit partial application possible with std::bind.

C# Yes Yes 7 2.0 / 3.0 2.0 3.0 Has delegates (2.0) and lambda expressions (3.0).
Objective-C Yes Yes Using anonymous 2.0 + Blocks[9] 2.0 + Blocks No Has function pointers.
Java Partial Partial Using anonymous Java 8 Java 8 No Has anonymous inner classes.
Go Yes Yes Using anonymous Yes Yes Yes
Limbo Yes Yes Yes Yes Yes No
Newsqueak Yes Yes Yes Yes Yes No
Rust Yes Yes Yes Yes Yes Yes[10]
Functional languages Lisp Syntax Syntax Yes Yes Common Lisp No (see below)
Scheme Yes Yes Yes Yes Yes SRFI 26[11]
Julia Yes Yes Yes Yes Yes Yes
Clojure Yes Yes Yes Yes Yes Yes
ML Yes Yes Yes Yes Yes Yes
Haskell Yes Yes Yes Yes Yes Yes
Scala Yes Yes Yes Yes Yes Yes
F# Yes Yes Yes Yes Yes Yes
OCaml Yes Yes Yes Yes Yes Yes
Scripting languages JavaScript Yes Yes Yes Yes Yes ECMAScript 5 Partial application possible with user-land code on ES3
Lua Yes Yes Yes Yes Yes Yes[12]
PHP Yes Yes Using anonymous 5.3 5.3 No Partial application possible with user-land code.
Perl Yes Yes 6 Yes Yes 6[13]
Python Yes Yes Yes Expressions only Yes 2.5[14] (see below)
Ruby Syntax Syntax Unscoped Yes Yes 1.9 (see below)
Other languages Fortran Yes Yes Yes No No No
Io Yes Yes Yes Yes Yes No
Maple Yes Yes Yes Yes Yes No
Mathematica Yes Yes Yes Yes Yes No
MATLAB Yes Yes Yes Yes Yes Yes Partial application possible by automatic generation of new functions.
Smalltalk Yes Yes Yes Yes Yes Partial Partial application possible through library.
Swift Yes Yes Yes Yes Yes Yes

С++

С++ затворења могу ухватити не-локалну променљиву по референци , копирањем или померањем конструкције. Избегава се скупа копија и омогућава модификовање оригиналне променљиве, али није сигурно у случају када се врати затворење. Друго је сигурно ако је затворење враћено али захтева копије и не може се користити за модификовање оригиналне променљиве. Касније је сигурно ако се затворење врати и не захтева копије, али се не може користити за промену оригиналне променљиве.

Java

Java 8 затворења могу заробити само финалне или „ефективно финалне“ не-локалне променљиве. Типови функција у Јави представљени су као класе. Анонимне функције узимају тип закључен из контекста. Референце метода су ограничене.

Lisp

Варијанте Лисп-а с лексичким опсегом подржавају затворење. Варијанте са динамичким опсегом не подржавају затворења или им је потребан посебан конструктор за стварање затворења.

У Common Lisp, идентификатор функције у функцији namespace не може се користити као референца на првокласну вредност. Посебна функција оператора мора се користити за дохватање функције као вредности.

Ruby

Идентификатор регуларне "функције" у Руби-у не може се користити као вредност или пренети. Прво се мора дохватити у Методи или Proc object да би се користио као првокласни податак. Синтакса за позивање таквог функционалног објекта разликује се од позивања регуларних метода.

Погледај још[уреди | уреди извор]

Референце[уреди | уреди извор]

  1. ^ „Structure and interpretation of computer programs : Abelson, Harold : Free Download, Borrow, and Streaming”. Internet Archive (на језику: енглески). Приступљено 2020-08-10. 
  2. ^ Scott, Michael Lee (1999). Programming language pragmatics (на језику: енглески). San Francisco: Morgan Kaufmann. ISBN 978-1-55860-442-1. OCLC 222529448. 
  3. ^ „(R. Ierusalimschy, L. de Figueiredo, W. Celes) The Implementation of Lua 5.0”. www.jucs.org. doi:10.3217/jucs-011-07-1159. Приступљено 2020-08-10. 
  4. ^ „Wayback Machine” (PDF). 
  5. ^ Moses, Joel (1970-06-01). „The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem” (на језику: енглески). 
  6. ^ „Nested Functions - Using the GNU Compiler Collection (GCC)”. gcc.gnu.org. Приступљено 2020-08-08. 
  7. ^ „Intensional Equality” (PDF). 
  8. ^ „Can we have functions inside functions in C++?”. Stack Overflow. Приступљено 2020-08-08. 
  9. ^ https://developer.apple.com/download/universal//library/documentation/Cocoa/Conceptual/Blocks/Articles/00_Introduction.html
  10. ^ „partial_application - Rust”. docs.rs. Приступљено 2020-08-08. 
  11. ^ „SRFI 26: Notation for Specializing Parameters without Currying”. srfi.schemers.org. Приступљено 2020-08-08. 
  12. ^ „Tiny Little Life » Blog Archive » Lua Code for Curry (Currying Functions)”. web.archive.org. 2010-11-05. Приступљено 2020-08-08. 
  13. ^ „blog | Perlgeek.de :: Currying”. perlgeek.de. Приступљено 2020-08-08. 
  14. ^ „What’s New in Python 2.5 — Python 3.8.5 documentation”. docs.python.org. Приступљено 2020-08-08. 

Спољашње везе[уреди | уреди извор]