Parametrický polymorfismus - Parametric polymorphism

Polymorfismus
Ad hoc polymorfismus
Parametrický polymorfismus
Podtypování

v programovací jazyky a teorie typů, parametrický polymorfismus je způsob, jak zvýšit expresivitu jazyka při zachování plné statiky bezpečnost typu. Pomocí parametrických polymorfismus, funkci nebo datový typ lze zapsat obecně, aby mohl zpracovávat hodnoty identický bez závislosti na jejich typu.[1] Takovým funkcím a datovým typům se říká generické funkce a generické datové typy respektive a tvoří základ generické programování.

Například funkce připojit který spojuje dva seznamy, může být vytvořen tak, že se nestará o typ prvků: může připojit seznamy celých čísel, seznamy reálných čísel, seznamy řetězců atd. Nech proměnná typu a označují typ prvků v seznamech. Pak připojit lze psát

pro všechny a. [a] × [a] -> [a]

kde [A] označuje typ seznamů s prvky typu A. Říkáme, že typ připojit je parametrizováno a pro všechny hodnoty A. (Všimněte si, že protože existuje pouze jedna typová proměnná, funkci nelze použít na libovolnou dvojici seznamů: dvojice i seznam výsledků musí sestávat ze stejného typu prvků.) Pro každé místo, kde připojit je použita hodnota je rozhodnuta A.

Následující Christopher Strachey,[2] s parametrickým polymorfismem lze kontrastovat ad hoc polymorfismus, ve kterém může mít jedna polymorfní funkce řadu odlišných a potenciálně heterogenních implementací v závislosti na typu argumentu (argumentů), na který je použita. Polymorfismus ad hoc tedy může obecně podporovat pouze omezený počet takových odlišných typů, protože pro každý typ musí být poskytnuta samostatná implementace.

Dějiny

Parametrický polymorfismus byl poprvé představen v programovacích jazycích v ML v roce 1975.[3] Dnes existuje v Standardní ML, OCaml, F#, Ada, Haskell, Rtuť, Vizuální prolog, Scala, Julie, Krajta, Strojopis, C ++ a další. Jáva, C#, Visual Basic .NET a Delphi každý zavedl „generika“ pro parametrický polymorfismus. Některé implementace polymorfismu typu jsou povrchně podobné parametrickému polymorfismu a zároveň zavádějí ad hoc aspekty. Jedním z příkladů je C ++ specializace šablony.

Nejobecnější formou polymorfismu je „vyšší hodnost předběžný polymorfismus ". Dvě populární omezení této formy jsou omezený polymorfismus pořadí (například pořadí 1 nebo prenex polymorfismus) a predikativní polymorfismus. Společně tato omezení dávají „predikativní prenexový polymorfismus“, což je v podstatě forma polymorfismu nalezená v ML a raných verzích Haskellu.

Vyšší polymorfismus

Polymorfismus 1. úrovně (prenex)

V prenex polymorfní systému, proměnné typu nemusí být konkretizovány s polymorfními typy.[4] Toto je velmi podobné tomu, co se nazývá „ML-styl“ nebo „Let-polymorfismus“ (technicky ML Let-polymorfismus má několik dalších syntaktických omezení). Toto omezení činí rozdíl mezi polymorfními a nepolymorfními typy velmi důležitým; v predikativních systémech jsou tedy polymorfní typy někdy označovány jako schémata typu odlišit je od běžných (monomorfních) typů, kterým se někdy říká monotypy. Důsledkem je, že všechny typy lze psát ve formě, která umisťuje všechny kvantifikátory na nejvzdálenější (prenexovou) pozici. Zvažte například připojit funkce popsaná výše, která má typ

pro všechny a. [a] × [a] -> [a]

Aby bylo možné použít tuto funkci na dvojici seznamů, musí být proměnná nahrazena typem A v typu funkce tak, aby se typ argumentů shodoval s výsledným typem funkce. V předběžný systém, nahrazovaný typ může být jakéhokoli typu, včetně typu, který je sám o sobě polymorfní; tím pádem připojit lze použít na dvojice seznamů s prvky libovolného typu - dokonce i na seznamy polymorfních funkcí, jako jsou připojit sám. Polymorfismus v jazyce ML je predikativní.[Citace je zapotřebí ] Důvodem je, že predikativita spolu s dalšími omezeními činí typový systém dost jednoduché, že plné odvození typu je vždy možné.

Jako praktický příklad OCaml (potomek nebo dialekt ML ) provádí odvození typu a podporuje impredikativní polymorfismus, ale v některých případech, kdy se použije impredikativní polymorfismus, je odvození typu systému neúplné, pokud programátor neposkytne některé explicitní poznámky k typu.

Hodnost-k polymorfismus

Pro nějakou pevnou hodnotu k, hodnost-k polymorfismus je systém, ve kterém se kvantifikátor nemusí zobrazit nalevo od k nebo více šipek (když je typ nakreslen jako strom).[1]

Odvození typu pro polymorfismus 2. úrovně je rozhodnutelný, ale rekonstrukce 3. a vyšší úrovně není.[5]

Hodnost-n („vyšší hodnost“) polymorfismus

Hodnost-n polymorfismus je polymorfismus, ve kterém se mohou kvantifikátory objevovat nalevo od libovolně mnoha šipek.

Predikativita a nepravděpodobnost

Predikativní polymorfismus

V predikativním parametrickém polymorfním systému typ obsahující proměnnou typu nelze použít takovým způsobem, že je konkretizován na polymorfní typ. Mezi teorie predikativního typu patří Teorie typu Martin-Löf a NuPRL.

Nepředvídatelný polymorfismus

Nepředvídatelný polymorfismus (také zvaný prvotřídní polymorfismus) je nejsilnější forma parametrického polymorfismu.[6] Definice se říká, že je předběžný pokud je samo-referenční; v teorii typů to umožňuje vytvoření instance proměnné v typu s jakýmkoli typem, včetně polymorfních typů, jako je sám. Příkladem toho je Systém F s proměnnou typu X v typu , kde X může dokonce odkazovat T sám.

v teorie typů, nejčastěji studovaný nedůtklivý zadaný λ-kalkul jsou založeny na těch z lambda kostka, zvláště Systém F.[1]

Ohraničený parametrický polymorfismus

Hlavní článek: Omezená kvantifikace

V roce 1985 Luca Cardelli a Peter Wegner poznal výhody povolení meze na parametry typu.[7] Mnoho operací vyžaduje určité znalosti datových typů, ale jinak mohou fungovat parametricky. Chcete-li například zkontrolovat, zda je položka zahrnuta v seznamu, musíme porovnat položky pro rovnost. v Standardní ML, zadejte parametry formuláře ''A jsou omezeny, takže je k dispozici operace rovnosti, takže funkce by měla typ ''A × ''A seznam → bool a ''A může být pouze typ s definovanou rovností. v Haskell, ohraničení je dosaženo vyžadováním typů, aby patřily k typová třída; tedy stejná funkce má typ v Haskellu. Ve většině objektově orientovaných programovacích jazyků, které podporují parametrický polymorfismus, lze parametry omezit na podtypy daného typu (viz Podtyp polymorfismu a článek o Generické programování ).

Viz také

Poznámky

  1. ^ A b C Pierce 2002.
  2. ^ Strachey 1967.
  3. ^ Milner, R., Morris, L., Newey, M. „Logic for Computable Functions with reflexive and polymorphic types“, Proc. Konference o ověřování a zlepšování programů, Arc-et-Senans (1975)
  4. ^ Benjamin C. Pierce; Benjamin C. (profesor Pierce, University of Pennsylvania) (2002). Typy a programovací jazyky. MIT Stiskněte. ISBN  978-0-262-16209-8.
  5. ^ Pierce 2002, str. 359.
  6. ^ Pierce 2002, str. 340.
  7. ^ Cardelli & Wegner 1985.

Reference