Typ funkce - Function type
v počítačová věda a matematická logika, a typ funkce (nebo typ šipky nebo exponenciální) je typ a proměnná nebo parametr ke kterému a funkce má nebo může být přiřazen, nebo argument nebo typ výsledku a funkce vyššího řádu převzetí nebo vrácení funkce.
Typ funkce závisí na typu parametrů a typu výsledku funkce (přesněji nepoužité) konstruktor typu · → ·
, je typ vyššího druhu ). V teoretickém nastavení a programovací jazyky kde jsou funkce definovány v kari forma, tak jako jednoduše zadaný lambda kalkul, typ funkce závisí přesně na dvou typech, doména A a rozsah B. Zde se často označuje typ funkce A → B, podle matematické konvence, nebo BA, na základě toho, že přesně existuje BA (exponenciálně mnoho) množinově-teoretické funkce mapování A na B v kategorie sad. Třída takových map nebo funkcí se nazývá exponenciální objekt. Akt kari dělá typ funkce adjoint do typ produktu; toto je podrobně prozkoumáno v článku o kari.
Typ funkce lze považovat za zvláštní případ závislý typ produktu, který mimo jiné zahrnuje myšlenku a polymorfní funkce.
Programovací jazyky
Syntaxi použitou pro typy funkcí v několika programovacích jazycích lze shrnout, včetně příkladu podpisu typu pro vyšší řád složení funkce funkce:
Jazyk | Zápis | Příklad podpis typu | |
---|---|---|---|
S prvotřídní funkce, parametrický polymorfismus | C# | Func <α1,α2,...,αn,ρ> | Func<A,C> komponovat(Func<B,C> F, Func<A,B> G); |
Haskell | α -> ρ | komponovat :: (b -> C) -> (A -> b) -> A -> C | |
OCaml | α -> ρ | komponovat : ('b -> 'C) -> ('A -> 'b) -> 'A -> 'C | |
Scala | (α1,α2,...,αn) => ρ | def komponovat[A, B, C](F: B => C, G: A => B): A => C | |
Standardní ML | α -> ρ | komponovat : (b -> 'C) -> ('A -> b) -> 'A -> 'C | |
Rychlý | α -> ρ | func komponovat<A,B,C>(F: B -> C, G: A -> B) -> A -> C | |
Rez | fn (α1,α2,...,αn) -> ρ | fn komponovat<A,B,C>(F: fn(A)-> B,G: fn(B)-> C)-> fn(A)-> C | |
S prvotřídní funkce, bez parametrický polymorfismus | Jít | func (α1,α2,...,αn) ρ | var komponovat func(func(int)int, func(int)int) func(int)int |
C ++, Cíl-C, s bloky | ρ (^)(α1,α2,...,αn) | int (^komponovat(int (^F)(int), int (^G)(int)))(int); | |
Bez prvotřídní funkce, parametrický polymorfismus | C | ρ (*)(α1,α2,...,αn) | int (*komponovat(int (*F)(int), int (*G)(int)))(int); |
C ++ 11 | Není to jedinečné.
| funkce<funkce<int(int)>(funkce<int(int)>, funkce<int(int)>)> komponovat; |
Při pohledu na podpis typu příkladu, například C #, typ funkce komponovat
je ve skutečnosti Func
.
Kvůli vymazání typu v C ++ 11 std :: funkce
, je běžnější používat šablony pro funkce vyššího řádu parametry a odvození typu (auto
) pro uzávěry.
Denotační sémantika
Typ funkce v programovacích jazycích neodpovídá prostoru všech teoreticko-teoretických funkcí. Vzhledem k počítatelně nekonečný Typ přirozená čísla jako doména a booleové jako rozsah, pak existují nespočetně nekonečný číslo 2ℵ0 = C ) množinově-teoretických funkcí mezi nimi. Je zřejmé, že tento prostor funkcí je větší než počet funkcí, které lze definovat v jakémkoli programovacím jazyce, protože existuje pouze nespočetně mnoho programů (program je konečnou posloupností konečného počtu symbolů) a jedna z množinově teoretických funkcí efektivně řeší zastavení problému.
Denotační sémantika se zabývá hledáním vhodnějších modelů (tzv domén ) k modelování konceptů programovacího jazyka, jako jsou typy funkcí. Ukazuje se, že omezující výraz na množinu vypočítatelné funkce nestačí, pokud programovací jazyk umožňuje psaní nekončící výpočty (což je případ, pokud je programovací jazyk Turing dokončen ). Výraz musí být omezen na tzv spojité funkce (odpovídá kontinuitě v Scottova topologie, nikoli kontinuita ve skutečném analytickém smyslu). I poté sada spojitých funkcí obsahuje paralelně nebo funkce, kterou nelze správně definovat ve všech programovacích jazycích.
Viz také
- Kartézská uzavřená kategorie
- Kari
- Exponenciální objekt, teoreticko-teoretický ekvivalent
- Prvotřídní funkce
- Funkční prostor, set-teoretický ekvivalent
Reference
- Pierce, Benjamin C. (2002). Typy a programovací jazyky. MIT Press. str.99 –100.
- Mitchell, John C. Základy programovacích jazyků. MIT Press.
- typ funkce v nLab
- Teorie typu homotopy: Univalentní základy matematiky, Program Univalent Foundations, Institut pro pokročilé studium. Viz část 1.2.