Polymorfismus (informatika)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 25. března 2021; kontroly vyžadují 11 úprav .

Polymorfismus v programovacích jazycích a teorii typů  je schopnost funkce zpracovávat data různých typů [1] [2] [3] .

Existuje několik typů polymorfismu. Dvě zásadně odlišné popsal Christopher Strachey v roce 1967 : jedná se o parametrický polymorfismus a ad-hoc polymorfismus , další formy jsou jejich poddruhy nebo kombinace. Parametrický polymorfismus je pravdivý, protože implikuje spuštění stejného kódu pro všechny platné typy argumentů a ad-hoc polymorfismus je imaginární, protože je zajistit kosmetickou jednotnost potenciálně odlišného spustitelného kódu pro každý konkrétní typ argumentu [1] [4] . Zároveň existují situace, kdy je nutné použít přesně ad-hoc polymorfismus, nikoli parametrický [5] . Teorie kvalifikovaných typů spojuje všechny druhy polymorfismu do jediného modelu.

Existuje rozšířená definice polymorfismu připisovaná Björnu Stroustrupovi : " jedno rozhraní (jako seznam deklarací) - mnoho implementací (definic spojených s těmito deklaracemi) " [6] , ale pouze ad-hoc polymorfismus (imaginární polymorfismus) spadá pod toto definice.

Obecné informace

Základní možnost pro stejný kód zpracovávat data různých typů je určena vlastnostmi typového systému jazyka . Z tohoto hlediska se rozlišuje [7] statické nepolymorfní typování (potomci Algol a BCPL ), dynamické typizace (potomci Lisp , Smalltalk , APL ) a statické polymorfní typizace (potomci ML ). Použití ad-hoc polymorfismu je nejcharakterističtější pro nepolymorfní typizaci. Parametrický polymorfismus a dynamické typování zvyšují opětovné použití kódu mnohem více než ad-hoc polymorfismus, protože jednou definovaná funkce implementuje zadané chování bez duplikace pro nekonečný počet nově definovaných typů, které splňují podmínky požadované ve funkci. Na druhou stranu je někdy nutné zajistit odlišné chování funkce v závislosti na typu parametru, a pak je nutný speciální polymorfismus.

Parametrický polymorfismus je synonymem pro typovou abstrakci [8] . Je všudypřítomný ve funkcionálním programování , kde se obvykle nazývá jednoduše „polymorfismus“.

V komunitě objektově orientovaného programování termín „polymorfismus“ obvykle znamená dědičnost a použití parametrického polymorfismu se nazývá generické programování [9] nebo někdy „statický polymorfismus“.

Klasifikace

Poprvé klasifikaci odrůd polymorfismu provedl Christopher Strachey .

Pokud je s parametrem funkce spojen právě jeden typ, pak se taková funkce nazývá monomorfní. Mnoho programovacích jazyků poskytuje syntaktický mechanismus pro přiřazení jednoho jména (identifikátoru) více monomorfním funkcím. V tomto případě je ve zdrojovém kódu možné volat funkci se skutečnými parametry různých typů, ale v kompilovaném kódu jsou ve skutečnosti volány různé funkce (viz procedura a přetížení funkcí ). Strachey nazval tuto možnost „ad-hoc polymorfismus“.

Pokud je s parametrem funkce spojeno více typů, pak se taková funkce nazývá polymorfní . Ke každé skutečné hodnotě lze samozřejmě přiřadit pouze jeden typ, ale polymorfní funkce bere v úvahu parametry založené na vnějších vlastnostech, nikoli na jejich vlastní organizaci a obsahu. Strachey nazval tuto možnost „parametrický polymorfismus“.

Později klasifikaci upřesnil Luca Cardelli [10] , přičemž zdůraznil čtyři typy polymorfismu:

V některých pracích je parametrický, ad-hoc- a podtypový polymorfismus rozlišován jako tři nezávislé třídy polymorfismu [11] .

Dualita významu pojmu "ad hoc" (na jedné straně - "spontánní, nedomyšlený, vyrobený při příležitosti", na druhé straně - "zvláštní, uspořádaný speciálně pro daný účel nebo danou příležitost") byla zasloužená již řadu let [5] . Strachey zvolil tento termín na základě prvního významu a zdůraznil, že s ad-hoc polymorfismem neexistuje jediný systematický způsob, jak odvodit typ výsledku z typu argumentů, a přestože je možné sestavit určitý soubor pravidel, zužují spektrum vyhledávání, tato pravidla jsou spontánní povahy jak v obsahu, tak v kontextu aplikace [1] .

Ad-hoc polymorfismus skutečně není skutečným polymorfismem [12] . Přetížení funkcí nevede k „hodnotě s více typy“, ale „znaku s více typy “, ale hodnoty identifikované tímto symbolem jsou různých (potenciálně nekompatibilních) typů. Stejně tak přetypování není skutečný polymorfismus: zdá se, že operátor přijímá hodnoty mnoha typů, ale hodnoty musí být převedeny na nějakou reprezentaci, než je může použít, aby operátor skutečně pracoval pouze s jedním typem (tj. má jeden typ). Typ návratové hodnoty zde navíc nezávisí na typu vstupního parametru , jako v případě parametrického polymorfismu.

Definování konkrétních implementací funkcí pro různé typy je však v některých případech nutností, nikoli náhodou. Klasickými příklady jsou implementace aritmetických operací (fyzicky odlišných pro celá čísla a čísla s plovoucí desetinnou čárkou ) a typová rovnost, která po desetiletí neměla žádnou přijatou univerzální formalizaci. Řešením byly typové třídy , které jsou mechanismem pro explicitní diskrétní výčet povolených hodnot typových proměnných pro statické odeslání v typové vrstvě. Spojují dohromady dvě varianty polymorfismu oddělené Stracheyem, " činí ad-hoc polymorfismus méně ad hoc " [5] ( hraní na dualitu). Další zobecnění typových tříd vedlo ke konstrukci teorie kvalifikovaných typů , která jednotně formalizuje nejexotičtější typové systémy, včetně rozšiřitelných zápisů a podtypů.

Na rozdíl od přetěžování a přetypování je polymorfismus podtypů skutečný polymorfismus: s objekty podtypů lze manipulovat jednotně, jako by patřily k jejich nadtypům (to však neplatí pro jazyky, které implementují „polymorfismus dědičností“ pomocí přetypování . přetížení typů a funkcí , jako v případě C++ ). Nejčistší je parametrický polymorfismus : stejný objekt nebo funkci lze použít jednotně v různých kontextech psaní bez úprav, přetypování nebo jakýchkoli jiných kontrol nebo konverzí za běhu. To však vyžaduje určitou jednotnou reprezentaci dat (například pomocí ukazatelů ) [4] .

Základní typy polymorfismu

Ad-hoc polymorfismus

Ad-hoc polymorfismus (nejčastěji překládaný v ruské literatuře jako „speciální polymorfismus“ nebo „specializovaný polymorfismus“, ačkoli obě možnosti nejsou vždy pravdivé ) je podporován v mnoha jazycích prostřednictvím přetížení funkcí a metod a ve slabě typizovaných ty  také prostřednictvím typového lití .

V následujícím příkladu ( jazyk Pascal ) funkce Addvypadají, že implementují stejnou funkcionalitu na různých typech, ale kompilátor je definuje jako dvě zcela odlišné funkce.

program Adhoc ; funkce Add ( x , y : Integer ) : Integer ; begin Add := x + y end ; function Add ( s , t : String ) : String ; begin Add := Concat ( s , t ) end ; begin Writeln ( Add ( 1 , 2 )) ; Writeln ( Přidat ( 'Ahoj, ' , 'Svět!' )) ; konec .

V dynamicky typovaných jazycích může být situace komplikovanější, protože volbu požadované funkce, kterou chcete volat, lze provést pouze za běhu.

Přetížení  je syntaktický mechanismus, který umožňuje volání různých funkcí pomocí jediného identifikátoru [13] . Přetypování typu  je sémantický mechanismus prováděný za účelem převodu skutečného typu argumentu na očekávaný typ funkce, bez něhož by došlo k chybě typu . To znamená, že když je funkce volána s typem přetypování, je pro různé typy spuštěn různý kód (předchází volání samotné funkce) [13] .

Parametrický polymorfismus

Parametrický polymorfismus umožňuje genericky definovat funkci nebo datový typ, takže s hodnotami se zachází stejně bez ohledu na jejich typ. Parametricky polymorfní funkce používá argumenty založené na chování spíše než na hodnotách, přičemž přistupuje pouze k vlastnostem argumentů, které potřebuje, takže je použitelná v jakémkoli kontextu, kde typ objektu splňuje dané požadavky na chování.

Systémy pokročilého typu (jako je Hindley-Milnerův systém ) poskytují mechanismy pro definování polymorfních typů , díky čemuž je použití polymorfních funkcí pohodlnější a poskytují bezpečnost statického typu . Takové systémy jsou systémy druhého řádu, které k systémům prvního řádu (používaným ve většině procedurálních jazyků ) přidávají typovou parametrizaci (prostřednictvím typové proměnné ) a typovou abstrakci (prostřednictvím existenciální kvantifikace nad nimi). V systémech typu druhého řádu není bezprostřední potřeba podporovat primitivní typy , protože je lze vyjádřit pokročilejšími prostředky. [čtrnáct]

Klasickým příkladem polymorfního typu je seznam prvků libovolného typu, pro které mnoho Hindley-Milnerových typovaných jazyků (většina staticky typovaných funkčních programovacích jazyků ) poskytuje syntaktický cukr . Následující příklad demonstruje definici nového algebraického typu "parametricky polymorfní seznam " a na něm dvě funkce:

seznam dat a = nula | Nevýhody a ( seznam a ) délka :: Seznam a -> Délka celého čísla Nil = 0 délka ( Cons x xs ) = 1 + délka xs mapa :: ( a -> b ) -> Seznam a -> Seznam b mapa f Nil = Nil mapa f ( Nevýhody x xs ) = Nevýhody ( f x ) ( mapa f xs )

Při nahrazení konkrétních typů do proměnné typu atd . se vytvoří konkrétní typy a tak dále. Tyto konkrétní typy mohou být zase nahrazeny do proměnné typu znovu , čímž se vytvoří typy a tak dále. V tomto případě bude pro všechny objekty všech konstruovaných typů použita stejná fyzická implementace funkcí a . aIntStringList IntList StringList List StringList (Int, List String)lengthmap

Omezené formy parametrického polymorfismu jsou také dostupné v některých imperativních (zejména objektově orientovaných ) programovacích jazycích, kde se pro něj běžně používá termín „ generické programování “. Zejména v C je netypový parametrický polymorfismus tradičně poskytován prostřednictvím použití netypovaného ukazatele void* , ačkoli typizovaná forma je také možná. Použití C++ šablon je povrchně podobné parametrickému polymorfismu, ale sémanticky implementováno kombinací ad-hoc mechanismů; v komunitě C++ se tomu říká „statický polymorfismus“ (na rozdíl od „dynamického polymorfismu“ ).

Parametricita

Formalizace parametrického polymorfismu vede ke konceptu parametricity , který spočívá ve schopnosti předpovídat chování programů pouze pohledem na jejich typy. Pokud je například funkce typu " forall a. a -> a", pak bez jakýchkoliv vnějších prostředků, které doplňují jazyk , lze dokázat , že může být pouze totožná . Parametricita je proto často doprovázena heslem „teorems for free“ ( angl.  theorems for free ). [15] [16] [17]

Důležitým důsledkem toho  je také nezávislost reprezentace , což znamená, že funkce nad abstraktním typem jsou necitlivé na jeho strukturu a různé implementace tohoto typu se mohou navzájem volně nahrazovat (i v rámci stejného programu), aniž by to ovlivnilo chování těchto funkcí. [18] .

Nejpokročilejší parametricky polymorfní systémy (nejvyšší bod v lambda kostce ) dovádějí myšlenku parametričnosti do té míry, že jsou schopny plně prokázat správnost programů: umožňují psát programy, které jsou designově správné, takže procházení kontrola typové konzistence sama o sobě zaručuje, že chování programu je správné.očekávané [19] .

Záznamový a variantní polymorfismus

Samostatným problémem je rozšíření parametrického polymorfismu na agregované typy: diskriminované součiny typů (tradičně nazývané záznamy ) a diskriminované součty typů (známé také jako variantní typy ). Různé " záznamové počty " ( anglicky  record calculi ) slouží jako formální základ pro objektově orientované a modulární programování [20] .

val r = { a = 1 , b = pravda , c = "ahoj" } val { a = n , ... = r1 } = r val r2 = { d = 3,14 , ... = r1 }

Elipsa znamená určitý počet typovaných polí, tedy abstrakci kódu z konkrétních typů záznamů, které by zde bylo možné zpracovat (a „délka“ této řady se také může lišit). Kompilace polymorfního přístupu k polím, která mohou být umístěna v různém pořadí v různých záznamech, je obtížný problém, a to jak z pohledu kontroly bezpečnosti operací na jazykové úrovni, tak z pohledu výkonu na strojovém kódu. úroveň. Naivním řešením může být dynamické vyhledávání slovníku při každém volání (a skriptovací jazyky jej používají), ale to je zjevně extrémně neefektivní. Tento problém je aktivně studován již několik desetiletí; bylo vybudováno mnoho teoretických modelů a na nich založených praktických systémů, které se liší vyjadřovací silou a metateoretickou složitostí. Nejdůležitějšími úspěchy v této oblasti jsou in-line polymorfismus navržený Mitchellem Wandem a polymorfní záznamový počet vytvořený Atsushi Ohori .  Běžnějším, ale v mnoha charakteristikách zaostávajícím modelem je podtypování na záznamech .  

Podpora polymorfismu záznamů v té či oné formě může otevřít možnosti v polymorfním jazyce, jako jsou zprávy vyššího řádu (nejvýkonnější forma objektově orientovaného programování ), bezproblémové vkládání operací s databázovými prvky ( SQL ) do univerzální jazykový kód a další, až po rozšiřitelné programování (tj. programování bez problému s výrazem ), zaručující absenci neošetřených výjimek v programech a určité formy metaprogramování .

Polymorfismus podtypů

Polymorfismus inkluze jezobecněná formalizace podtypování a dědičnosti [21] . Tyto pojmy by se neměly zaměňovat: podtypy definují vztahy na úrovni rozhraní, zatímco dědičnost definuje vztahy na úrovni implementace [22] .

Subtypování ( subtyping ), nebo subtypový polymorfismus ( subtype polymorphism ), znamená, že chování parametricky polymorfní funkce je omezeno na množinu typů ohraničených v hierarchii supertyp-podtyp [23] [10] [24] . Například, pokud existují typy , a , omezené vztahy a , pak funkce definovaná na type , bude také schopna přijímat argumenty typů nebo a její chování bude identické. Skutečný typ objektu může být skryt jako "černá skříňka" a poskytnut pouze na žádost o identifikaci objektu. Ve skutečnosti, pokud je typ abstraktní, pak konkrétní objekt tohoto typu ani nemůže existovat (viz abstraktní třída , ale nezaměňovat s abstraktním datovým typem ). Tato hierarchie typů je známá (zejména v kontextu jazyka Scheme ) jako číselná věž a obvykle obsahuje více typů. NumberRationalIntegerNumber :> RationalNumber :> IntegerNumberIntegerRationalNumber

Myšlenka podtypování je motivována zvýšením množiny typů, které mohou být zpracovány již napsanými funkcemi, a tím zvýšením míry opětovného použití kódu při silném psaní (tj. zvýšením množiny typovaných programů). To je zajištěno pravidlem subsumpce : „ pokud výraz epatří k typu t'v kontextu psaní Гa je pravdivý t'<:t, pak etaké patří k typut “ [25] [26] .

Vztahy podtypů jsou možné na široké škále kategorií typů: primitivní typy (jako Integer <: Number), typy součtů , typy produktů , funkční typy atd. Kromě toho Luca Cardelli navrhl koncept druhů moci ( "silové" druhy ), aby popsal podtyp [27] : pojmenoval rod všech jeho podtypů jako mocninný druh typu [ 28 ] .

Zvláštní místo v informatice zaujímá podtypování na záznamech .

Podtypování záznamů

Podtypování záznamu , také známé jako subsumpce (  viz princip substituce Barbary Liskov ) , je nejběžnějším teoretickým odůvodněním pro objektově orientované programování (OOP) [29] [30] [24] [31] (ale ne jediné - viz # záznamový a variantní polymorfismus ).

Martín Abadi a Luca Cardelli formalizovali podtypování na záznamech prostřednictvím omezené kvantifikace nad parametricky polymorfními typy [29] [30] ; zatímco parametr type je nastaven implicitně [32] .

Při podtypování na záznamech se rozlišují dvě varianty: na šířku a do hloubky.

Podtypování šířky zahrnuje přidání nových polí do záznamu . Například:

typ Object = { věk: Int } typ Vozidlo = { věk: Int; rychlost: Int} typ Kolo = { věk: Int; rychlost: Int; převodovka: Int; } typeMachine = { věk: Int; palivo: Struna

Na jedné straně lze psát vztahy podtypů Vehicle <: Object, Bike <: Vehicle(a protože je podtypování tranzitivní , pak a Bike <: Object) a Machine <: Object. Na druhou stranu můžeme říci, že typy Vehicle, Bikea Machine zahrnují (zdědí) všechny vlastnosti typu Object. (Zde je implikována strukturální sémantika typového systému )

Vzhledem k tomu, že typ je často intuitivně vnímán jako soubor hodnot, zvýšení počtu polí v podtypu může být z hlediska teorie množin kontraintuitivní . Ve skutečnosti typy nejsou množiny [33] , jsou určeny k ověření chování programů a myšlenkou podtypování je, že podtyp má alespoň vlastnosti svého nadtypu, a je tedy schopen jej alespoň emulovat. kde se u objektu očekává supertyp [25] . Nebo jinak: nadtyp definuje minimální množinu vlastností pro množinu objektů a pak typ, který má tyto vlastnosti a případně i některé další, tvoří podmnožinu této množiny, a je tedy jejím podtypem [30] .

Vztahy podtypů z hlediska množin jsou v případě variantních typů intuitivnější [34] :

typ Den = po | út | svatba | čt | pá | seděl | slunce typ Pracovní den = Po | út | svatba | čt | pá typ WeekEnd = so | slunce

Zde Workday <: Daya WeekEnd <: Day.

Pojmenování polí umožňuje abstrahovat od pořadí jejich výskytu v záznamech (na rozdíl od n-tic ), což umožňuje vytvářet libovolné řízené acyklické grafy dědičnosti, formalizující vícenásobnou dědičnost [34] :

typ Auto = { věk: Int; rychlost: Int; palivo: Struna

Nyní Car <: Vehiclea zároveň Car <: Machine. Je také zřejmé, že Car <: Object(viz dědičnost ve tvaru diamantu ).

Hloubkové podtypování znamená, že typy konkrétních polí záznamů lze nahradit jejich podtypy :

typ Voyage = { veh: Vozidlo; datum: den typ Sport = { veh: Kolo; datum: den typ Dovolená = { veh: Auto; datum: víkend }

Z výše uvedených definic můžeme odvodit , že Sports <: Voyagea Vacation <: Voyage.

Metody v podtypech záznamů

Plná podpora objektově orientovaného programování znamená zahrnutí do počtu záznamových polí také funkcí , které zpracovávají hodnoty typů záznamů, ke kterým patří [29] [35] . Takové funkce se tradičně nazývají „ metody “. Zobecněným modelem pro vazbu záznamů na metody je matice odeslání ; v praxi jej většina jazyků rozkládá na vektory v řádcích nebo sloupcích – v tomto pořadí implementuje buď organizaci založenou na třídách, nebo organizaci založenou na metodách [36 ] . Zároveň je třeba rozlišovat mezi přepisovacími metodami v podtypech ( přepis metody ) a funkcemi podtypování ( funkční podtypování ). Přepisovací metody je nesvazují s podtypovacími vztahy na funkcích, ale umožňují jim měnit podpisy typu. V tomto případě jsou možné tři možnosti: invariantní, kovariantní a kontravariantní redefinice a poslední dvě využívají podtypování svých parametrů [37] (podrobněji viz kovariance a kontravariance ). Abadi-Cardelliho kalkul [29] uvažuje pouze invariantní metody, které jsou nezbytné k prokázání bezpečnosti .

Mnoho objektově orientovaných jazyků poskytuje vestavěný mechanismus pro vazbu funkcí do metod , čímž implementuje třídní organizaci programů. Jazyky, které zacházejí s funkcemi jako s prvotřídními objekty a zadávají je (viz prvotřídní funkce , funkční typ  – nezaměňujte s návratovým typem funkce ), umožňují libovolnou organizaci založenou na metodách, která umožňuje objektově orientovaný návrh bez přímá podpora ze stran jazyka [38] . Některé jazyky (například OCaml ) podporují obojí.

Jazyky s typovými systémy založenými na formální teorii podtypování ( OCaml , nástupnický projekt ML ) zacházejí s objektovými systémy a systémy tříd nezávisle [39] [40] . To znamená, že typ objektu je primárně přidružen k objektu a pouze když je explicitně specifikován, je typ objektu přidružen k určité třídě. V tomto případě je dynamické odesílání prováděno na úrovni objektů, což znamená, že v takových jazycích mohou mít dva objekty patřící do stejné třídy, obecně řečeno, různé sady metod. Spolu s formálně definovanou sémantikou vícenásobné dědičnosti to poskytuje okamžitou komplexní podporu pro mixiny .

CLOS implementuje celou dispatch matici prostřednictvím multimetod , tedy dynamicky odesílaných metod, které jsou polymorfní v několika argumentech najednou [41] .

Některé jazyky používají zvláštní ad-hoc] řešení. Například typový systém jazyka C++ poskytuje automatické přetypování (to znamená, že je slabý ), nepolymorfní , emuluje podtypování manifestního dědění s invariantními signaturami metod a nepodporuje abstrakci typu (neplést s polním úkrytem ). Dědičnost v C++ je implementována sadou ad-hoc mechanismů, nicméně její použití se v jazykové komunitě nazývá „polymorfismus“ (a skrývání polí se nazývá „abstrakce“ [42] ). Je možné ovládat graf dědičnosti: dědičnost ve tvaru kosočtverce v C++ se nazývá " virtuální dědičnost " a je specifikována explicitním atributem ; ve výchozím nastavení jsou zděděná pole duplikována a přistupuje se k nim pomocí kvalifikovaného názvu. Použití takového jazyka může být nebezpečné  - nelze zaručit stabilitu programů [43] [37] (jazyk se nazývá bezpečný , pokud programy v něm, které mohou být kompilátorem akceptovány jako dobře zformované, nikdy nepřekročí povolené chování v dynamice [44] ). virtual

Podtypování vyššího řádu

Systém je rozšířením systému F (není reprezentován v lambda-krychli ), který formalizuje omezenou kvantifikaci nad typovými operátory a rozšiřuje vztahy podtypů z rodu na typy vyššího rodu . Existuje několik verzí systému , které se liší vyjadřovací silou a metateoretickou složitostí, ale většinu hlavních myšlenek položil Luca Cardelli [45] . *

Kombinace odrůd polymorfismu

Typové třídy

Typová třída implementuje jedinou nezávislou tabulku virtuálních metod pro mnoho ( univerzálně kvantifikovaných ) typů. Tímto způsobem se typové třídy liší od tříd v objektově orientovaném programování , kde je každý objekt libovolného ( omezeně kvantifikovaného ) typu doprovázen ukazatelem na virtuální tabulku metod [46] . Typové třídy nejsou typy, ale kategorie typů; jejich instancemi nejsou hodnoty, ale typy.

Například [46] :

class Num a kde ( + ), ( * ) :: a -> a -> a negovat :: a -> a

Tato deklarace zní takto: " Typ apatří do třídy , Numpokud jsou na něm definovány funkce (+), (*)a negate, s danými podpisy ."

instance Num Int kde ( + ) = addInt ( * ) = mulInt negate = negInt instance Num Float kde ( + ) = addFloat ( * ) = mulFloat negate = negFloat

První deklarace zní: " Existují funkce (+)a odpovídající podpisy (*), negatekteré jsou definovány nad typemInt ." Druhé prohlášení zní podobně.

Nyní můžete správně zadat následující funkce (a odvození typu je rozhodnutelné ):

čtverec :: Počet a => a - > čtverec x = x * x čtverce3 :: Počet a , Počet b , Číslo c => ( a , b , c ) -> ( a , b , c ) čtverec3 ( x , y , z ) = ( čtverec x , čtverec y , čtverec z )

Vzhledem k tomu, že operace násobení je implementována fyzicky odlišně pro celá čísla a čísla s pohyblivou řádovou čárkou , při absenci typových tříd by zde již byly vyžadovány dvě přetížené funkce squarea osm přetížených funkcí squares3a ve skutečných programech se složitými datovými strukturami existuje mnohem více duplicitních kódů . . V objektově orientovaném programování se problémy tohoto druhu řeší pomocí dynamického odesílání , s přidruženou režií. Třída typu odesílá staticky a přináší parametrické a ad-hoc polymorfismy do jediného modelu [5] . Z hlediska parametrického polymorfismu má typová třída parametr ( typová proměnná ) zahrnující sadu typů. Z hlediska ad-hoc polymorfismu je tato množina nejen diskrétní, ale i explicitně specifikovaná až na implementační úroveň. Jednoduše řečeno, signatura znamená, že funkce je parametricky polymorfní , ale rozsah typů jejího parametru je omezen pouze na ty typy, které patří do typové třídy . Díky tomu je funkce typována jedinečným způsobem i přes volání přetížené funkce z jejího těla. square :: Num a => a -> aNum

Nativní podpora typových tříd byla poprvé implementována v Haskell , ale lze je zavést i do libovolného parametricky polymorfního jazyka jednoduchým předzpracováním [5] a implementovat i idiomaticky (viz např. jazyk modulu ML#Implementing Alternative Models ). Přímá podpora však může usnadnit automatické uvažování o smyslu programů.

Typy rovnosti v Haskellu jsou implementovány jako instance třídy typuEq(zobecňující proměnné typu rovnosti ze Standard ML ) :

( == ) :: Rovnice a => a -> a -> Bool

Aby se snížilo potíže s kódováním některých často zjevně nezbytných vlastností uživatelsky definovaných typů, Haskell navíc poskytuje syntaktický cukr  , konstrukt deriving, který je platný pro omezenou sadu standardních typových tříd (jako je Eq). (V rusky mluvící komunitě je jeho použití často zaměňováno s pojmem „ dědičnost “ kvůli zvláštnostem překladu slova „ odvodit “.)

Obecné algebraické datové typy

Polytypismus

Někdy se používá termín „polytypismus“ nebo „zobecnění datových typů“. Polytyping v podstatě odkazuje na vestavěnou podporu jazyka pro polymorfismus typového konstruktoru , navržený ke sjednocení programovacích rozhraní a zvýšení opětovného použití kódu . Příkladem polytypismu je zobecněný algoritmus porovnávání vzorů [47] .

Podle definice, ve funkci polytype, „ ačkoli pro některé typy může existovat konečný počet ad-hoc větví, neexistuje žádný ad-hoc kombinátor “ [48] .

Polytypování lze implementovat pomocí generického datového typu nebo polymorfismu vyšší úrovně . Rozšíření PolyP [49] Haskellu je syntaktický konstrukt , který zjednodušuje definici polytypových funkcí v Haskellu .

Funkce polytypizace je v jistém smyslu obecnější než funkce polymorfní, ale na druhou stranu funkce může být polytypová a nikoli polymorfní, jak lze vidět z následujících podpisů typů funkcí :

hlava :: [ a ] ​​​​-> a ( + ) :: Num a => a -> a -> a délka :: Regulární d => d a -> Int součet :: Regulární d => d Int -> Int

První funkce ( head) je polymorfní (parametricky polymorfní ), druhá (infixový operátor „ “) je přetížená (ad-hoc-polymorfní), třetí a čtvrtá jsou polytypové: typová proměnná se v jejich definici liší podle typu konstruktéři . Zároveň je třetí funkce ( ) polytypová a polymorfní (pravděpodobně počítá "délku" pro nějakou sadu polymorfních typů agregátů - například počet prvků v seznamech a stromech ), a čtvrtá ( ) je polytypový, ale ne polymorfní (monomorfní nad typy agregátů patřící do typové třídy , pro které pravděpodobně vypočítává součet celých čísel, která tvoří objekt konkrétního typu agregátu). + dlengthsum Regular

Různé

Dynamicky typované jazyky jednotně reprezentují různé druhy polymorfismu, který v nich tvoří osobitou ideologii a ovlivňuje aplikované metodologie dekompozice úloh. Například ve Smalltalku je jakákoli třída schopna přijímat zprávy jakéhokoli typu a buď je zpracovávat samostatně (včetně introspekce ), nebo je předávat jiné třídě – jakákoli metoda je tedy formálně parametricky polymorfní, zatímco její vnitřní struktura může se větvit podle podmínky typu dynamického argumentu s implementací speciálního polymorfismu. V CLOS jsou multimetody zároveň prvotřídními funkcemi , což nám umožňuje považovat je jak za omezeně kvantifikované , tak za zobecněné ( pravé polymorfní ).

Naproti tomu staticky polymorfně typované jazyky mohou implementovat různé polymorfismy ortogonálně (nezávisle na sobě), což jim umožňuje složitě konstruovat typově bezpečným způsobem. Například OCaml podporuje parametrické třídy (podobné schopnostem jako šablony tříd C++ , ale ověřitelné bez nutnosti konkretizace), jejich dědičnost šířky a hloubky (včetně více ), idiomatickou implementaci tříd typu (prostřednictvím signatur - viz odpovídající příklad použití jazyka modulu ML ), inline polymorfismus , parametrický polymorfismus řádků nad 1 (pomocí tzv. lokálně abstraktních typů , které implementují existenciální typy ) a zobecněné algebraické datové typy .

Historie

Termín "polymorfismus" pochází z řečtiny. πολύς („hodně“) a μορφή („forma, tvar, zařízení“).

Termíny „specializovaný polymorfismus“ a „parametrický polymorfismus“ jsou poprvé zmíněny v roce 1967 v poznámkách k přednášce Christophera Stracheye s názvem „ Základy programovacích jazyků [ [1] . V roce 1985 Peter Wegner a Luca Cardelli formalizovali polymorfismus zadržování pro modelování podtypů a dědičnost [10] [27] , ačkoli implementace podtypů a dědičnosti se objevily mnohem dříve, v jazyce Simula v roce 1967 . Polymorfismus inkluze je založen na omezené kvantifikaci .

Zápis parametrického polymorfismu jako vývoje λ-kalkulu (nazývaného F systém ) formálně popsal logik Jean-Yves Girard [50] [51] ( 1971 ), nezávisle na něm byl popsán podobný systém počítačovým vědcem Johnem S. Reynoldsem [52] ( 1974 ).

První jazyk zcela založený na polymorfním λ-kalkulu byl ML ( 1973 ); nezávisle na něm byly parametrické typy implementovány v Clu ( 1974 ) [27] . Mnoho moderních jazyků ( C++ , Java , C# , D a další) poskytuje parametrické typy ve formě více či méně blízké jejich implementaci v Clu.

V roce 1987 Mitchel Wand formalizoval inline polymorfismus a odvodil pro něj typ [53] ; tato práce měla obrovský dopad na následný vývoj typových systémů . Ve stejném roce Philip Wadler a Stephen Blott navrhli typové třídy k formalizaci ad-hoc polymorfismu . 

Viz také

Poznámky

  1. 1 2 3 4 Strachey, 1967 .
  2. Cardelli, 1991 , str. 3.
  3. Pierce, 2012 , 22.7. Polymorfismus přes let, str. 354.
  4. 1 2 Cardelli, 1985 , str. 6.
  5. 1 2 3 4 5 Wadler, 1988 , str. 1-2.
  6. Bjarne Stroustrup . Slovník C++ (19. února 2007). Archivováno z originálu 29. června 2018.
  7. Andrew W. Appel. Kritika standardního ML . — Princetonská univerzita, 1992.
  8. Harper, 2012 , 20.1 System F, str. 172.
  9. Pierce, 2012 , 23.2 Variety polymorfismu, s. 365.
  10. 1 2 3 Cardelli, 1985 .
  11. Mitchell, 2002 , 6.4. Polymorfismus a přetěžování, str. 145-151.
  12. Cardelli, 1985 , 1.3. Druhy polymorfismu, str. 6.
  13. 1 2 Cardelli, 1985 , str. 5-6.
  14. Cardelli, 1996 , 5 Typové systémy druhého řádu, str. 25.
  15. Harper, 2012 , 20.3 Přehled parametrů, str. 177.
  16. Harper, 2012 , 49 Parametricita, str. 495-508.
  17. Pierce, 2012 , 23.9 Parametricita, str. 384-385.
  18. Harper, 2012 , 21.4 Representation Independence, str. 188.
  19. Pierce, 2012 , 30.5 Jít dále: závislé typy, str. 489-493.
  20. Reynolds, 1998 , 16. Subtypes and Intersection Types. Bibliografické poznámky, str. 376.
  21. Cardelli, 1985 .
  22. Mitchell, 2002 , 10.2.6 Dědičnost není podtypování, s. 287.
  23. Cardelli, 1991 .
  24. 1 2 Pierce, 2012 , 15 podtypů, str. 193.
  25. 1 2 Pierce, 2012 , 15. Podtypy, str. 193.
  26. Harper, 2012 , 23.1. Subsumpce, str. 208.
  27. 1 2 3 Pierce, 2012 , 1.4 Stručná historie, str. 11-13.
  28. Cardelli, 1991 , 6. Druhy sil, str. 32.
  29. 1 2 3 4 Abadi, Cardelli, 1994 .
  30. 1 2 3 Cardelli, 1985 , 6. Omezená kvantifikace, str. 28.
  31. Minsky přeložil DMK, 2014 , Subtyping, str. 259.
  32. Cardelli, 1985 , str. 9.
  33. Harper, 2012 , Kapitola 16. Rekurzivní typy, str. 132.
  34. 1 2 Cardelli, 1991 , str. 35-37.
  35. Cardelli, 1985 , 2.3. Základní typy, strukturované typy a rekurze, str. 12-14.
  36. Harper, 2012 , Kapitola 25. Dynamic Dispatch, str. 229.
  37. 1 2 Joyner, 1996 , 3.38 Signature Variance, str. 35.
  38. Objektově orientované programování ve standardním ML . Získáno 11. března 2016. Archivováno z originálu 14. ledna 2016.
  39. Minsky přeložil DMK, 2014 , Kapitola 11. Objekty, str. 253.
  40. Pracovní skupina ML2000. Principy a předběžný návrh pro ML2000 . — 1999.
  41. Castagna, Ghelli, Longo. Výpočet pro přetížené funkce s podtypováním  // Information and Computation. - Akademický tisk, 1995. - T. 117 , no. 1 . - S. 115-135 . - doi : 10.1006/inco.1995.1033 .
  42. Joyner, 1996 , 2.8 Encapsulation, str. osm.
  43. Mitchell, 2002 , 6.2.1 Bezpečnost typu, str. 132-133.
  44. Harper, 2012 , Kapitola 4. Statika, str. 35.
  45. Pierce, 2012 , 31. Podtypy vyššího řádu, s. 495.
  46. 12 Wadler , 1988 , s. 3.
  47. Johan Jeuring. Shoda polytypických vzorů  // FPCA. - 1995. - doi : 10.1.1.36.5645 .
  48. Ralf Lammel a Joost Visser, „Typed Combinators for Generic Traversal“, v Praktické aspekty deklarativních jazyků: 4. mezinárodní symposium (2002), str. 153.
  49. Patrik Jansson, Johan Jeuring. PolyP - Rozšíření polytypického programovacího jazyka . — Sigplan SPPL, 1997.
  50. Girard - Rozšíření teorie typů, 1971 .
  51. Girard – kalkul vyššího řádu, 1972 .
  52. Reynolds, 1974 .
  53. Hůlka, 1987 .

Literatura

  • Christopher Strachey. Základní pojmy v programovacích  jazycích . - 1967. Archivováno 12. srpna 2017.
    • Znovu publikováno: Christopher Strachey. Základní pojmy v programovacích jazycích  // Vyšší řád a symbolické výpočty  . - 2000. - Sv. 13 . - str. 11-49 . - doi : 10.1023/A:1010000313106 .
  • Jean-Yves Girard. Une Extension de l'Interpretation de l'Interpretation de Gödel à l'Analyse, et son Application à l'Elimination des Coupures dans l'Analyse et la Théorie des Types  (francouzsky)  // Sborník z druhého sympozia skandinávské logiky. - Amsterdam, 1971. - S. 63-92 . - doi : 10.1016/S0049-237X(08)70843-7 .
  • Jean-Yves Girard. Interprétation fonctionnelle et elimination des coupures de l'arithmétique d'ordre supérieur  (francouzsky) . — Université Paris 7, 1972.
  • John C. Reynolds. Towards a Theory of Type Structure // Poznámky k přednáškám z informatiky . - Paříž: Colloque sur la programmation, 1974. - svazek 19 . - S. 408-425 . - doi : 10.1007/3-540-06859-7_148 .
  • Luca Cardelli , Peter Wegner. O porozumění typům, abstrakci dat a polymorfismu //ACM Computing Surveys. - New York, USA:ACM, 1985. -17,č. 4. -S. 471-523. —ISSN 0360-0300. -doi:10.1145/6041.6042.
  • Robert Harper . Úvod do standardního ML. - Carnegie Mellon University, 1986. - ISBN PA 15213-3891.
  • Překlad do ruštiny: Robert Harper . Úvod do standardního ML. - Carnegie Mellon University, 1986. - 97 s. — ISBN PA 15213-3891.
  • Mitchell Wand . Kompletní odvození typu pro jednoduché objekty // In Proc. 2nd IEEE Symposium on Logic in Computer Science. - 1987. -S. 37-44.
  • Philip Wadler, Stephen Blott. Jak snížit ad-hoc polymorfismus ad hoc  . — 1988.
  • Luca Cardelli . Typické programování // Zprávy IFIP o stavu umění. - New York: Springer-Verlag, 1991. -Iss. Formální popis programovacích konceptů. -S. 431-507.
  • Martin Abadi, Luca Cardelli . Sémantika typů objektů  . — LICS , 1994.
  • Luca Cardelli . Typové systémy (anglicky) // Handbook of Computer Science and Engineering. — CRC Press, 1996.
  • John C. Reynolds. Teorie programovacích jazyků . - Cambridge University Press, 1998. - ISBN 978-0-521-59414-1 (pevná vazba), 978-0-521-10697-9 (brožovaná).
  • Benjamin Pierce. Typy a programovací jazyky  . - MIT Press , 2002. - ISBN 0-262-16209-1 .
    • Překlad do ruštiny: Benjamin Pierce. Typy v programovacích jazycích . - Dobrosvet , 2012. - 680 s. — ISBN 978-5-7913-0082-9 .
  • John C. Mitchell Koncepty v programovacích jazycích  . - Cambridge University Press, 2002. - 540 s. - ISBN 978-0-521-78098-8 .
  • Minsky, Madhavapeddy, Hickey. Skutečný svět OCaml: Funkční programování pro  masy . - O'Reilly Media, 2013. - 510 s. — ISBN 9781449324766 .
    • Překlad do ruštiny: Minsky, Madhavapeddy, Hickey. Programování v jazyce OCaml . - DMK, 2014. - 536 s. - (Funkcionální programování). - ISBN 978-5-97060-102-0 .