Prvotřídní funkce - First-class function

V informatice se říká , že programovací jazyk má prvotřídní funkce, pokud s funkcemi zachází jako s občany první třídy . To znamená, že jazyk podporuje předávání funkcí jako argumentů jiným funkcím, vrací je jako hodnoty z jiných funkcí a přiřazuje je proměnným nebo je ukládá do datových struktur. Někteří teoretici programovacího jazyka vyžadují podporu také pro anonymní funkce (literály funkcí). V jazycích s prvotřídními funkcemi nemají názvy funkcí žádný zvláštní status; jsou považovány za běžné proměnné s typem funkce . Termín vytvořil Christopher Strachey v kontextu „funkcí prvotřídních občanů“ v polovině 60. let minulého století.

Prvotřídní funkce jsou nezbytností pro funkční programovací styl, ve kterém je používání funkcí vyššího řádu standardní praxí. Jednoduchým příkladem funkce s vyšším uspořádáním je funkce map , která jako argument bere funkci a seznam a vrací seznam vytvořený aplikací funkce na každého člena seznamu. Aby jazyk podporoval mapu , musí podporovat předávání funkce jako argumentu.

Při předávání funkcí jako argumentů nebo jejich vracení jako výsledků existují určité potíže s implementací, zejména v přítomnosti nelokálních proměnných zavedených ve vnořených a anonymních funkcích . Historicky se jim říkalo funargové problémy , název pochází z „funkčního argumentu“. V raných imperativních jazycích se těmto problémům vyhýbalo buď nepodporováním funkcí jako typů výsledků (např. ALGOL 60 , Pascal ), nebo vynecháním vnořených funkcí a tedy nelokálních proměnných (např. C ). Raný funkční jazyk Lisp vzal přístup dynamického rozsahu , kde nelokální proměnné odkazují na nejbližší definici této proměnné v místě, kde je funkce spuštěna, místo kde byla definována. Správná podpora pro prvotřídní funkce s lexikálním rozsahem byla zavedena ve schématu a vyžaduje zpracování odkazů na funkce jako uzávěry místo ukazatelů holé funkce , což zase činí sběr odpadků nezbytností.

Pojmy

V této části porovnáváme, jak jsou konkrétní programovací idiomy zpracovány ve funkčním jazyce s prvotřídními funkcemi ( Haskell ) ve srovnání s imperativním jazykem, kde jsou funkce občany druhé třídy ( C ).

Funkce vyššího řádu: předávání funkcí jako argumentů

V jazycích, kde jsou funkce prvotřídními občany, lze funkce předávat jako argumenty jiným funkcím stejným způsobem jako jiné hodnoty (funkce, která jako argument bere jinou funkci, se nazývá funkce vyššího řádu). V jazyce Haskell :

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

Jazyky, kde funkce nejsou prvotřídní, často stále umožňují psát funkce vyššího řádu pomocí funkcí, jako jsou ukazatele funkcí nebo delegáti . V jazyce C :

void map(int (*f)(int), int x[], size_t n) {
    for (int i = 0; i < n; i++)
        x[i] = f(x[i]);
}

Existuje celá řada rozdílů mezi oběma přístupy, které nejsou přímo spojené s podporou funkce first-class. Ukázka Haskell pracuje na seznamech , zatímco ukázka C funguje na polích . Oba jsou nejpřirozenější složené datové struktury v příslušných jazycích a kdyby vzorek C fungoval na propojených seznamech, bylo by to zbytečně složité. To také odpovídá skutečnosti, že funkce C potřebuje další parametr (udávající velikost pole.) Funkce C aktualizuje pole na místě a nevrací žádnou hodnotu, zatímco v datových strukturách Haskell jsou trvalé (je vrácen nový seznam zatímco starý zůstane nedotčen.) Ukázka Haskell používá k procházení seznamem rekurzi , zatímco vzorek C používá iteraci . Opět je to nejpřirozenější způsob, jak vyjádřit tuto funkci v obou jazycích, ale Haskellův vzorek mohl být snadno vyjádřen jako záhyb a vzorek C jako rekurze. Nakonec má funkce Haskell polymorfní typ, protože to C nepodporuje, opravili jsme všechny typové proměnné na typovou konstantu int.

Anonymní a vnořené funkce

V jazycích podporujících anonymní funkce můžeme takovou funkci předat jako argument funkci vyššího řádu:

main = map (\x -> 3 * x + 1) [1, 2, 3, 4, 5]

V jazyce, který nepodporuje anonymní funkce, ho musíme místo toho svázat se jménem:

int f(int x) {
    return 3 * x + 1;
}

int main() {
    int list[] = {1, 2, 3, 4, 5};
    map(f, list, 5);
}

Nelokální proměnné a uzávěry

Jakmile máme anonymní nebo vnořené funkce, je pro ně přirozené odkazovat na proměnné mimo své tělo (nazývané nelokální proměnné ):

main = let a = 3
           b = 1
        in map (\x -> a * x + b) [1, 2, 3, 4, 5]

Pokud jsou funkce zastoupeny pomocí ukazatelů holé funkce, nemůžeme už vědět, jak by do něj měla být předána hodnota, která je mimo tělo funkce, a proto je třeba uzavření vytvořit ručně. Nemůžeme zde tedy hovořit o funkcích „první třídy“.

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);
}

Všimněte si také, že mapse nyní specializuje na funkce odkazující na dva ints mimo jejich prostředí. To lze nastavit obecněji, ale vyžaduje to více standardního kódu . Pokud fby to byla vnořená funkce , stále bychom narazili na stejný problém, a to je důvod, proč nejsou podporovány v C.

Funkce vyššího řádu: vrací funkce jako výsledky

Při vrácení funkce ve skutečnosti vracíme její uzavření. V příkladu C všechny místní proměnné zachycené uzávěrem zmizí mimo rozsah, jakmile se vrátíme z funkce, která uzavření vytváří. Vynucení uzavření v pozdějším okamžiku bude mít za následek nedefinované chování, případně poškození zásobníku. Toto je známé jako problém funargování směrem nahoru .

Přiřazení funkcí proměnným

Přiřazování funkcí proměnným a jejich ukládání do (globálních) datových struktur potenciálně trpí stejnými obtížemi jako vracející se funkce.

f :: [[Integer] -> [Integer]]
f = let a = 3
        b = 1
     in [map (\x -> a * x + b), map (\x -> b * x + a)]

Rovnost funkcí

Jelikož lze testovat většinu literálů a hodnot pro rovnost, je přirozené se ptát, zda programovací jazyk může podporovat testovací funkce pro rovnost. Při dalším zkoumání se tato otázka jeví jako obtížnější a je třeba rozlišovat několik typů rovnosti funkcí:

Extenzionální rovnost

Dvě funkce f a g jsou považovány za extenzivně stejné, pokud se shodnou na svých výstupech pro všechny vstupy (∀ x . F ( x ) = g ( x )). Podle této definice rovnosti by například byly považovány za rovnocenné jakékoli dvě implementace stabilního algoritmu řazení , jako je vkládání a sloučení . Rozhodování o rovnosti extenzí je obecně nerozhodnutelné a dokonce i pro funkce s konečnými doménami často neřešitelné. Z tohoto důvodu žádný programovací jazyk neimplementuje rovnost funkcí jako extenzionální rovnost.

Intenzivní rovnost

Podle intenzivní rovnosti jsou dvě funkce f a g považovány za stejné, pokud mají stejnou „vnitřní strukturu“. Tento druh rovnosti by mohl být implementován v interpretovaných jazycích porovnáním zdrojového kódu funkčních těl (například v Interpreted Lisp 1.5) nebo objektového kódu v kompilovaných jazycích . Intenzivní rovnost znamená extenzní rovnost (za předpokladu, že funkce jsou deterministické a nemají žádné skryté vstupy, jako je čítač programu nebo proměnná globální proměnná .)

Referenční rovnost

Vzhledem k nepraktičnosti implementace extenzionální a intenzionální rovnosti používá většina jazyků podporujících testovací funkce pro rovnost referenční rovnost. Všem funkcím nebo uzávěrům je přiřazen jedinečný identifikátor (obvykle adresa těla funkce nebo uzavření) a o rovnosti se rozhoduje na základě rovnosti identifikátoru. Dvě samostatně definované, ale jinak identické definice funkcí budou považovány za nerovné. Referenční rovnost znamená intenzivní a extenzivní rovnost. Referenční rovnost narušuje referenční transparentnost, a proto není podporována v čistých jazycích, jako je například Haskell.

Teorie typů

V teorii typ , typ funkcí přijímání hodnoty typu A a vracejících se hodnoty typu B lze vyjádřit jako A → B nebo B ^A . V Curry-Howard korespondence , typy funkce jsou spojeny s logickou implikaci ; lambda abstrakce odpovídá vybíjení hypotetických předpokladů a aplikace funkcí odpovídá odvozovacímu pravidlu modus ponens . Kromě obvyklého případu programovacích funkcí používá teorie typů také prvotřídní funkce k modelování asociativních polí a podobných datových struktur .

V kategorii teoretických účtů programování odpovídá dostupnost prvotřídních funkcí předpokladu uzavřené kategorie . Například jednoduše napsaný lambda kalkul odpovídá vnitřnímu jazyku karteziánských uzavřených kategorií .

Jazyková podpora

Funkční programovací jazyky, jako jsou Scheme , ML , Haskell , F# a Scala , mají všechny prvotřídní funkce. Když byl navržen Lisp , jeden z prvních funkčních jazyků, nebyly správně pochopeny všechny aspekty prvotřídních funkcí, což vedlo k dynamickému rozsahu funkcí. Pozdější dialekty Scheme a Common Lisp mají lexikálně vymezené prvotřídní funkce.

Mnoho skriptovacích jazyků, včetně Perl , Python , PHP , Lua , Tcl /Tk, JavaScript a Io , má prvotřídní funkce.

U imperativních jazyků je třeba rozlišovat mezi Algolem a jeho potomky, jako je Pascal, tradiční rodina C a moderní varianty sbírané odpadky. Rodina Algol jako argumenty povolila vnořené funkce a funkce vyššího řádu, ale nikoli funkce vyššího řádu, které vracejí funkce jako výsledky (kromě Algolu 68, který to umožňuje). Důvodem bylo to, že nebylo známo, jak zacházet s nelokálními proměnnými, pokud byla v důsledku toho vrácena vnořená funkce (a Algol 68 v takových případech vytváří chyby za běhu).

Rodina C povolila obě předávající funkce jako argumenty a vracela je jako výsledky, ale vyhýbala se problémům tím, že nepodporovala vnořené funkce. (Kompilátor gcc je umožňuje jako rozšíření.) Protože užitečnost vracejících se funkcí spočívá především ve schopnosti vracet vnořené funkce, které zachytily nelokální proměnné, namísto funkcí nejvyšší úrovně se tyto jazyky obecně nepovažují za první -funkce třídy.

Moderní imperativní jazyky často podporují sběr odpadků, což umožňuje implementaci prvotřídních funkcí. Prvotřídní funkce byly často podporovány pouze v pozdějších revizích jazyka, včetně C# 2.0 a rozšíření Apple Blocks na C, C ++ a Objective-C. C ++ 11 přidal podporu pro anonymní funkce a uzavření jazyka, ale vzhledem k povaze jazyka, který není shromažďován odpadky, je třeba věnovat zvláštní pozornost tomu, aby se lokální proměnné ve funkcích vracely jako výsledky (viz níže ).

C ++

Uzávěry C ++ 11 mohou zachytit nelokální proměnné konstrukcí kopírování, referencí (bez prodloužení jejich životnosti) nebo konstrukcí přesunu (proměnná žije tak dlouho, jak uzávěr dělá). První možnost je bezpečná, pokud je uzávěrka vrácena, ale vyžaduje kopii a nelze ji použít k úpravě původní proměnné (která v době volání uzávěrky již nemusí existovat). Druhá možnost se potenciálně vyhýbá nákladné kopii a umožňuje upravit původní proměnnou, ale není bezpečná v případě vrácení uzávěru (viz visící odkazy ). Třetí možnost je bezpečná, pokud je uzávěr vrácen a nevyžaduje kopii, ale nelze jej použít ani k úpravě původní proměnné.

Jáva

Uzávěry Java 8 mohou zachytit pouze konečné nebo „efektivně konečné“ nelokální proměnné. Typy funkcí Java jsou reprezentovány jako třídy. Anonymní funkce přebírají typ odvozený z kontextu. Odkazy na metody jsou omezené. Další podrobnosti viz Anonymní funkce § Omezení Javy .

Lisp

Varianty Lisp s Lexikálním rozsahem podporují uzávěry. Varianty s dynamickým rozsahem nepodporují uzávěry nebo k vytvoření uzávěrů potřebují speciální konstrukci.

V Common Lisp nelze použít identifikátor funkce v oboru názvů funkcí jako odkaz na hodnotu první třídy. K functionnačtení funkce jako hodnoty je třeba použít speciální operátor : (function foo)vyhodnotí se na objekt funkce. #'fooexistuje jako zkratka. Chcete-li použít takovou funkci objektu, se musí použít funcallfunkce: (funcall #'foo bar baz).

Krajta

Explicitní částečná aplikace functools.partialod verze 2.5 a operator.methodcallerod verze 2.6.

Rubín

Identifikátor běžné „funkce“ v Ruby (což je ve skutečnosti metoda) nelze použít jako hodnotu ani předat. Nejprve musí být načten do objektu Methodnebo, Procaby byl použit jako prvotřídní data. Syntaxe pro volání takového funkčního objektu se liší od volání běžných metod.

Vnořené definice metod ve skutečnosti nevnořují rozsah.

Explicitní kari s [1].

Viz také

• Defunkcionalizace
• eval
• Prvotřídní zpráva
• Kappa kalkul -formalismus, který vylučuje prvotřídní funkce
• Test muže nebo chlapce
• Částečná aplikace

Poznámky

Reference

• Leonidas Fegaras . „Funkční jazyky a funkce vyššího řádu“ . CSE5317/CSE4305: Návrh a konstrukce kompilátorů. University of Texas v Arlingtonu.

externí odkazy

• Prvotřídní funkce v kódu Rosetta .
• Funkce vyššího řádu u IBM developerWorks