Polymorfism (datavetenskap)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 25 mars 2021; kontroller kräver 11 redigeringar .

Polymorfism i programmeringsspråk och typteori är en funktions förmåga att bearbeta data av olika typer [1] [2] [3] .

Det finns flera typer av polymorfism. Två fundamentalt olika beskrevs av Christopher Strachey 1967 : dessa är parametrisk polymorfism och ad -hoc polymorfism , andra former är deras underarter eller kombinationer. Parametrisk polymorfism är sant eftersom innebär exekvering av samma kod för alla giltiga argumenttyper, och ad-hoc polymorfism är imaginär, eftersom är att säkerställa kosmetisk enhetlighet för potentiellt olika körbar kod för varje särskild typ av argument [1] [4] . Samtidigt finns det situationer där det är nödvändigt att använda exakt ad-hoc polymorfism, och inte parametrisk [5] . Teorin om kvalificerade typer kombinerar alla typer av polymorfism till en enda modell.

Det finns en utbredd definition av polymorfism som tillskrivs Björn Stroustrup : " ett gränssnitt (som en lista över deklarationer) - många implementeringar (definitioner förknippade med dessa deklarationer) " [6] , men endast ad-hoc polymorfism (imaginär polymorfism) faller under detta definition.

Allmän information

Den grundläggande möjligheten för samma kod att behandla data av olika typer bestäms av egenskaperna hos språkets typsystem . Ur denna synvinkel skiljer man [7] statisk icke-polymorf typning (ättlingar till Algol och BCPL ), dynamisk typning (ättlingar till Lisp , Smalltalk , APL ) och statisk polymorf typning (ättlingar till ML ). Användningen av ad-hoc polymorfism är mest karakteristisk för icke-polymorf typning. Parametrisk polymorfism och dynamisk typning ökar kodåteranvändningen mycket mer än ad-hoc polymorfism, eftersom en funktion som definierats en gång implementerar det specificerade beteendet utan duplicering för ett oändligt antal nydefinierade typer som uppfyller de villkor som krävs i funktionen. Å andra sidan, ibland blir det nödvändigt att tillhandahålla ett annat beteende hos funktionen beroende på typen av parameter, och då är speciell polymorfism nödvändig.

Parametrisk polymorfism är synonymt med typabstraktion [8] . Det är allestädes närvarande i funktionell programmering , där det vanligtvis bara kallas "polymorfism".

I den objektorienterade programmeringsgemenskapen betyder termen "polymorfism" vanligtvis arv , och användningen av parametrisk polymorfism kallas generisk programmering [9] eller ibland "statisk polymorfism".

Klassificering

För första gången utfördes klassificeringen av varianter av polymorfism av Christopher Strachey .

Om exakt en typ är associerad med en funktionsparameter, kallas en sådan funktion monomorf. Många programmeringsspråk tillhandahåller en syntaktisk mekanism för att tilldela ett enda namn (identifierare) till flera monomorfa funktioner. I det här fallet blir det i källkoden möjligt att anropa en funktion med faktiska parametrar av olika typer, men i den kompilerade koden anropas faktiskt olika funktioner (se procedur och funktionsöverbelastning ). Strachey kallade denna möjlighet "ad-hoc polymorfism".

Om mer än en typ är associerad med en funktionsparameter kallas en sådan funktion polymorf . Naturligtvis kan endast en typ associeras med varje faktiskt värde, men en polymorf funktion tar hänsyn till parametrar baserade på externa egenskaper, inte deras egen organisation och innehåll. Strachey kallade denna möjlighet "parametrisk polymorfism".

Senare förfinades klassificeringen av Luca Cardelli [10] , och lyfte fram fyra typer av polymorfism:

universell
- parametrisk
- inneslutningar (eller undertyper )
ad hoc
- överbelastning
- kasta

I vissa arbeten särskiljs parametrisk, ad-hoc- och subtyp polymorfism som tre oberoende klasser av polymorfism [11] .

Dualiteten i betydelsen av termen "ad hoc" (å ena sidan - "spontan, ogenomtänkt, gjord vid tillfället", å andra sidan - "speciell, arrangerad specifikt för ett givet ändamål eller ett givet tillfälle") har varit förtjänt i många år [5] . Strachey valde denna term baserat på den första betydelsen, och betonade att det med ad-hoc polymorfism inte finns något enda systematiskt sätt att härleda typen av resultat från typen av argument, och även om det är möjligt att bygga en viss uppsättning regler för att begränsa sökspektrumet, dessa regler är spontana till sin natur, både vad gäller innehåll och tillämpningssammanhang [1] .

Faktum är att ad-hoc polymorfism inte är sann polymorfism [12] . Funktionsöverbelastning ger inte "värde med flera typer" utan "karakter med flera typer ", men värdena som identifieras av den symbolen är av olika (potentiellt inkompatibla) typer. Likaledes är gjutning inte sann polymorfism: operatören verkar acceptera värden av många typer, men värdena måste konverteras till någon representation innan den kan använda dem, så att operatören faktiskt bara arbetar på en typ (d.v.s. har en typ). Dessutom beror inte typen av returvärde här på typen av ingångsparameter , som i fallet med parametrisk polymorfism.

Men att definiera specifika funktionsimplementeringar för olika typer är i vissa fall en nödvändighet, inte en olycka. Klassiska exempel är implementeringen av aritmetiska operationer (fysiskt olika för heltal och flyttal ) och typlikhet, som under decennier inte hade någon accepterad universell formalisering. Lösningen var , som är en mekanism för explicit diskret uppräkning av de tillåtna värdena för typvariabler för statisk sändning i typlagret. De sammanför de två varianterna av polymorfism åtskilda av Strachey, " gör ad-hoc polymorfism mindre ad hoc " [5] ( spelar på dualitet). Ytterligare generalisering av typklasser ledde till konstruktionen av en teori om kvalificerade typer , som enhetligt formaliserar de mest exotiska typsystemen, inklusive utvidgbara notationer och subtyper.

Till skillnad från överbelastning och typgjutning är subtyp polymorfism sann polymorfism: subtypobjekt kan manipuleras enhetligt som om de tillhörde deras supertyper (men detta är inte sant för språk som implementerar "polymorfism genom nedärvning" via gjutning typer och funktionsöverbelastning , som i fallet med C++ ). Den renaste är parametrisk polymorfism : samma objekt eller funktion kan användas enhetligt i olika typkontexter utan modifieringar, casts eller andra körtidskontroller eller omvandlingar. Detta kräver dock en viss enhetlig representation av data (till exempel genom pekare ) [4] .

Grundläggande typer av polymorfism

Ad-hoc polymorfism

Ad-hoc polymorfism (oftast översatt i rysk litteratur som "speciell polymorfism" eller "specialiserad polymorfism", även om båda alternativen inte alltid är sanna ) stöds på många språk genom funktions- och metodöverbelastning , och i svagt skriven sådana också genom typgjutning .

I följande exempel ( Pascal language ) ser funktionerna Addut som att de implementerar samma funktionalitet på olika typer, men kompilatorn definierar dem som två helt olika funktioner.

program Adhoc ; function Add ( x , y : Heltal ) : Heltal ; börja Lägg till := x + y slut ; function Add ( s , t : String ) : String ; börja Lägg till := Concat ( s , t ) slut ; börja Writeln ( Lägg till ( 1 , 2 ) ) ; Writeln ( Lägg till ( 'Hej, ' , 'Världen!' )) ; slut .

I dynamiskt typade språk kan situationen vara mer komplicerad, eftersom valet av den funktion som krävs att anropa endast kan göras under körning.

Överbelastning är en syntaktisk mekanism som gör det möjligt att anropa olika funktioner med en enda identifierare [13] . Typgjutning är en semantisk mekanism som utförs för att konvertera den faktiska typen av ett argument till den förväntade typen av en funktion, utan vilken ett typfel skulle uppstå . Det vill säga när en funktion anropas med en typcast exekveras olika kod för olika typer (före anropet av själva funktionen) [13] .

Parametrisk polymorfism

Parametrisk polymorfism tillåter att en funktion eller datatyp definieras generiskt, så att värden behandlas identiskt oavsett typ. En parametriskt polymorf funktion använder beteendebaserade argument snarare än värdebaserade, och får endast tillgång till egenskaperna för de argument den behöver, vilket gör den användbar i alla sammanhang där objekttypen uppfyller de givna beteendekraven.

Avancerade typsystem (som Hindley-Milner-systemet ) tillhandahåller mekanismer för att definiera polymorfa typer , vilket gör användningen av polymorfa funktioner bekvämare och ger statisk typsäkerhet . Sådana system är andra ordningens typsystem, som till första ordningens typsystem (används i de flesta procedurspråk ) lägger till typparametrisering (med hjälp av en typvariabel ) och typabstraktion (genom existentiell kvantifiering över dem). I andra ordningens typsystem finns det inget omedelbart behov av att stödja primitiva typer , eftersom de kan uttryckas på mer avancerade sätt. [fjorton]

Det klassiska exemplet på en polymorf typ är en lista över godtyckliga typelement, för vilka många Hindley-Milner- skrivna språk (de flesta statiskt typade funktionella programmeringsspråk ) tillhandahåller syntaktisk socker . Följande exempel visar definitionen av en ny algebraisk typ "parametriskt polymorf lista " och två funktioner på den:

datalista a = Noll | _ Nackdelar a ( Lista a ) längd :: Lista a - > Heltalslängd Noll = 0 längd ( Cons x xs ) = 1 + längd xs karta :: ( a -> b ) -> Lista a -> Lista b karta f Noll = Noll karta f ( Cons x xs ) = Cons ( f x ) ( map f xs )

När betongtyper ersätts med en typvariabel osv, kommer betongtyper att byggas respektive, och så vidare. Dessa speciella typer kan i sin tur ersättas med den typvariabeln igen , producera typer och så vidare. I det här fallet, för alla objekt av alla konstruerade typer, kommer samma fysiska implementering av funktionerna och att användas . aIntStringList IntList StringList List StringList (Int, List String)lengthmap

Begränsade former av parametrisk polymorfism är också tillgängliga i vissa imperativa (särskilt objektorienterade ) programmeringsspråk, där termen " generisk programmering " vanligtvis används för att hänvisa till det. I synnerhet, i C, tillhandahålls otypad parametrisk polymorfism traditionellt genom användning av en otypad pekare void* , även om en typad form också är möjlig. Att använda C++-mallar är ytligt likt parametrisk polymorfism, men semantiskt implementerat av en kombination av ad-hoc-mekanismer; i C++- gemenskapen kallas det "statisk polymorfism" (i motsats till "dynamisk polymorfism" ).

Parametrisitet

Formaliseringen av parametrisk polymorfism leder till begreppet parametricity , som består i förmågan att förutsäga beteendet hos program genom att bara titta på deras typer. Till exempel, om en funktion är av typen " forall a. a -> a", utan några externa medel som kompletterar språket , kan det bevisas att det bara kan vara identiskt . Därför åtföljs parametrisitet ofta av sloganen "theorems for free" ( eng. theorems for free ). [15] [16] [17]

En viktig konsekvens av detta är också representationsoberoende , vilket innebär att funktioner över en abstrakt typ är okänsliga för dess struktur, och olika implementeringar av denna typ kan fritt ersätta varandra (även inom samma program) utan att påverka dessa funktioners beteende. [18] .

De mest avancerade parametriskt polymorfa systemen (högsta punkten i lambdakuben ) tar idén om parametrisitet till den grad att de till fullo kan bevisa korrektheten av program: de tillåter att program skrivs som är korrekta genom design, så att godkänd en typkonsistenskontroll i sig garanterar att programmets beteende är korrekt förväntat [19] .

Registrera och variant polymorfism

Ett separat problem är utvidgningen av parametrisk polymorfism till aggregerade typer: diskriminerade produkter av typer (traditionellt kallade poster ) och diskriminerade summor av typer (även känd som varianttyper ). Olika " record calculus " ( engelska record calculi ) fungerar som en formell grund för objektorienterad och modulär programmering [20] .

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

En ellips betyder ett visst antal inskrivna fält, det vill säga en abstraktion av koden från specifika typer av poster som skulle kunna bearbetas här (och "längden" på denna serie kan också variera). Att sammanställa polymorf åtkomst till fält som kan placeras i olika ordning i olika register är ett svårt problem, både ur synvinkeln att kontrollera driftsäkerheten på språknivå, och ur funktionssynpunkt vid maskinkoden. nivå. En naiv lösning kan vara att dynamiskt slå upp ordboken vid varje samtal (och skriptspråk använder den), men detta är uppenbarligen extremt ineffektivt. Detta problem har aktivt studerats i flera decennier; många teoretiska modeller och praktiska system baserade på dem har byggts, som skiljer sig i uttryckskraft och metateoretisk komplexitet. De viktigaste prestationerna inom detta område är in-line polymorfism som föreslagits av Mitchell Wand och polymorf rekordkalkyl byggd av Atsushi Ohori . En vanligare, men släpar efter i många egenskaper, modell är subtypning på poster .

Stöd för postpolymorfism i en eller annan form kan öppna möjligheter i ett polymorft språk som meddelanden av högre ordning (den mest kraftfulla formen av objektorienterad programmering ), den sömlösa inbäddningen av operationer på databaselement ( SQL ) i allmän språkkod och andra, upp till utvidgbar programmering (det vill säga programmering fri från uttrycksproblemet ), som garanterar frånvaron av obehandlade undantag i program och vissa former av metaprogrammering .

Subtyp polymorfism

Inklusionspolymorfism ären generaliserad formalisering av subtypning [ och arv [21] . Dessa begrepp bör inte förväxlas: undertyper definierar relationer på gränssnittsnivå, medan arv definierar relationer på implementeringsnivå [22] .

Subtypning ( subtyping ), eller subtype polymorphism ( subtype polymorphism ), innebär att beteendet hos en parametriskt polymorf funktion är begränsad till en uppsättning typer avgränsade i en supertyp-subtyphierarki [23] [10] [24] . Till exempel, om det finns typer , och , begränsade av relationer och , då en funktion definierad på typ , kommer också att kunna acceptera argument av typer eller , och dess beteende kommer att vara identiskt. Den faktiska typen av ett objekt kan döljas som en "svart låda" och endast tillhandahållas på begäran för objektidentifiering. Faktum är att om en typ är abstrakt, kan ett konkret objekt av den typen inte ens existera (se abstrakt klass , men inte att förväxla med abstrakt datatyp ). Denna typhierarki är känd (särskilt i sammanhanget med Scheme-språket ) som nummertornet , och innehåller vanligtvis fler typer. NumberRationalIntegerNumber :> RationalNumber :> IntegerNumberIntegerRationalNumber

Idén med subtyping motiveras av att öka uppsättningen typer som kan hanteras av redan skrivna funktioner, och därigenom öka kodåteranvändningsfrekvensen under stark typning (dvs. öka uppsättningen av maskinskrivna program). Detta tillhandahålls av subsumtionsregeln : " om ett uttryck tillhör en typ i ett skrivsammanhang och är sant , så tillhör det också typen " [25] [26] . et'Гt'<:tet

Subtypningsrelationer är möjliga för en mängd olika typkategorier: primitiva typer (som Integer <: Number), summatyper , produkttyper , funktionstyper , etc. Luca Cardelli föreslog dessutom begreppet maktsorter ( “power”-slag ) för att beskriva subtyping [27] : han namngav släktet av alla dess undertyper som typens krafttyp [ 28 ] .

En speciell plats inom datavetenskap upptas av subtypning på poster .

Subtyping på poster

Record subtyping , även känd som subsumtion ( se Barbara Liskovs substitutionsprincip ) , är den vanligaste teoretiska motiveringen för objektorienterad programmering (OOP) [29] [30] [24] [31] (men inte den enda - se # rekord och variant polymorfism ).

Martín Abadi och Luca Cardelli formaliserade subtypning på poster genom begränsad kvantifiering över parametriskt polymorfa typer [29] [30] ; medan typparametern är inställd implicit [32] .

Vid subtypning på poster särskiljs två varianter: i bredd och på djup.

Undertypning av bredd innebär att nya fält läggs till i en post . Till exempel:

typ Objekt = { ålder: Int } typ Fordon = { ålder: Int; hastighet: Int} typ Cykel = { ålder: Int; hastighet: Int; gear: Int; } typeMachine = { age: Int; bränsle: String

Å ena sidan kan man skriva subtypningsrelationerna Vehicle <: Object, Bike <: Vehicle(och eftersom subtypningen är transitiv , då och Bike <: Object) och Machine <: Object. Å andra sidan kan vi säga att typer Vehicle, Bikeoch Machine inkluderar (ärver) alla egenskaper av typ Object. (Här antyds typsystemets strukturella semantik )

Eftersom en typ ofta intuitivt ses som en uppsättning värden, kan en ökning av antalet fält i en undertyp vara kontraintuitivt ur en mängdteoretisk synvinkel . I verkligheten är typer inte uppsättningar [33] , de är avsedda att verifiera programs beteende, och tanken med subtyping är att en subtyp åtminstone har egenskaperna hos sin supertyp och därmed kan emulera den åtminstone där ett objekt förväntas supertyp [25] . Eller med andra ord: en supertyp definierar en minsta uppsättning egenskaper för en uppsättning objekt, och sedan en typ som har dessa egenskaper och, möjligen, några andra, bildar en delmängd av denna uppsättning, och är därför dess subtyp [30] .

Subtyprelationer i termer av uppsättningar är mer intuitiva när det gäller varianttyper [34] :

Här Workday <: Dayoch WeekEnd <: Day.

Att namnge fält låter dig abstrahera från ordningen för deras förekomst i poster (till skillnad från tupler ), vilket gör det möjligt att bygga godtyckliga riktade acykliska arvsgrafer, vilket formaliserar multipelt arv [34] :

typ Bil = { ålder: Int; hastighet: Int; bränsle: String

Nu Car <: Vehicleoch samtidigt Car <: Machine. Det är också uppenbart att Car <: Object(se diamantformat arv ).

Djupundertypning innebär att typerna av särskilda postfält kan ersätta deras undertyper:

typ Voyage = { veh: Fordon; datum: Dag typ Sport = { veh: Cykel; datum: Dag typ Semester = { veh: Bil; datum: helg }

Från definitionerna ovan kan vi härleda att Sports <: Voyageoch Vacation <: Voyage.

Metoder i postundertyper

Fullständigt stöd för objektorienterad programmering innebär att inkludering i antalet postfält även funktioner som behandlar värdena för de posttyper som de tillhör [29] [35] . Sådana funktioner kallas traditionellt för " metoder ". En generaliserad modell för att binda poster till metoder är avsändningsmatrisen ; i praktiken sönderdelar de flesta språk det till vektorer i rader eller kolumner - respektive implementerar antingen en klassbaserad organisation eller en metodbaserad organisation [36 ] . Samtidigt bör man skilja på överordnade metoder i subtyper ( metodöverstyrning ) och subtypningsfunktioner ( funktionell subtypning ). Åsidosättande av metoder binder dem inte med subtypningsrelationer på funktioner, utan tillåter dem att ändra sina typsignaturer. I det här fallet är tre alternativ möjliga: invariant, kovarian och kontravariant omdefiniering, och de två sista använder subtypning av sina parametrar [37] (för mer information, se kovarians och kontravarians ). Abadi-Cardelli-kalkylen [29] tar endast hänsyn till invarianta metoder, vilket är nödvändigt för att bevisa säkerheten .

Många objektorienterade språk tillhandahåller en inbyggd mekanism för att binda funktioner till metoder , och implementerar därmed en klassbaserad organisation av program. Språk som behandlar funktioner som förstklassiga objekt och skriver in dem (se förstklassiga funktioner , funktionell typ - inte att förväxla med returtypen för en funktion ) tillåter godtycklig metodbaserad organisation, vilket tillåter objektorienterad design utan direkt stöd från sidorna av tungan [38] . Vissa språk (som OCaml ) stöder båda.

Språk med typsystem baserade på formell subtypningsteori ( OCaml , det efterföljande ML- projektet ) behandlar objektsystem och klasssystem oberoende [39] [40] . Detta innebär att objekttypen primärt är associerad med ett objekt , och endast när det är explicit specificerat är objekttypen associerad med en viss klass. I det här fallet utförs dynamisk dispatch på objektnivå, vilket innebär att i sådana språk kan två objekt som tillhör samma klass generellt sett ha olika metoder. Tillsammans med den formellt definierade semantiken för multipelt arv ger detta omedelbart omfattande stöd för mixins .

CLOS implementerar hela leveransmatrisen genom multimetoder , det vill säga dynamiskt skickade metoder som är polymorfa i flera argument samtidigt [41] .

Vissa språk använder speciella ad-hoc-lösningar. Till exempel tillhandahåller språktypsystemet C++ för automatisk typcasting ( det vill säga det är svagt ), icke-polymorft , emulerar subtyping manifest nedärvning med invarianta metodsignaturer och stöder inte typabstraktion (inte att förväxla med fältgömma ) . Nedärvning i C++ implementeras av en uppsättning ad-hoc-mekanismer, men dess användning kallas "polymorfism" i språkgemenskapen (och fältdöljning kallas "abstraktion" [42] ). Det är möjligt att styra arvsgrafen: diamantformat arv i C++ kallas " virtuellt arv " och specificeras av ett explicit attribut ; som standard dupliceras ärvda fält och nås med kvalificerat namn. Användningen av ett sådant språk kan vara osäkert - man kan inte garantera stabiliteten hos program [43] [37] (ett språk kallas säkert om program i det, som kan accepteras av kompilatorn som välformade, aldrig kommer att gå längre än det tillåtna beteendet i dynamik [44] ). virtual

Subtyping av högre ordning

Systemet är en förlängning av System F (ej representerat i lambda-kuben ), som formaliserar begränsad kvantifiering över typoperatorer , vilket utökar subtypningsrelationer från genus till typer av högre genus . Det finns flera versioner av systemet , som skiljer sig i uttryckskraft och metateoretisk komplexitet, men de flesta av huvudidéerna lades ner av Luca Cardelli [45] . ${\displaystyle F_{<:}^{\omega ))$ * ${\displaystyle F_{<:}^{\omega ))$

En kombination av varianter av polymorfism

Skriv klasser

En typklass implementerar en enda oberoende tabell över virtuella metoder för många ( universellt kvantifierade ) typer. På detta sätt skiljer sig typklasser från klasser i objektorienterad programmering , där varje objekt av valfri ( begränsad kvantifierad ) typ åtföljs av en pekare till en virtuell metodtabell [46] . Typklasser är inte typer, utan kategorier av typer; deras instanser är inte värden, utan typer.

Till exempel [46] :

klass Num a där ( + ), ( * ) :: a -> a -> a negate :: a -> a

Denna deklaration lyder så här: " En typ atillhör en klass Numom funktioner (+)och , (*)med negatede givna signaturerna är definierade på den ."

instans Num Int där ( + ) = addInt ( * ) = mulInt negate = negInt instans Num Float där ( + ) = addFloat ( * ) = mulFloat negate = negFloat

Den första deklarationen lyder: " Det finns funktioner (+), (*)och negatemotsvarande signaturer, som definieras över typenInt ." Det andra uttalandet lyder på liknande sätt.

Nu kan du skriva in följande funktioner korrekt (och skriv slutledning kan avgöras ):

kvadrat :: Num a => a -> a kvadrat x = x * x squares3 :: Num a , Num b , Num c => ( a , b , c ) -> ( a , b , c ) squares3 ( x , y , z ) = ( square x , square y , square z )

Eftersom multiplikationsoperationen implementeras fysiskt annorlunda för heltal och flyttal , i avsaknad av typklasser, skulle två överbelastade funktioner squareoch åtta överbelastade funktioner redan krävas här squares3, och i verkliga program med komplexa datastrukturer, finns det mycket mer duplicerad kod . I objektorienterad programmering löses problem av detta slag genom dynamisk dispatch , med tillhörande overhead. Typklassen sänder statiskt, vilket ger parametriska och ad-hoc polymorfismer till en enda modell [5] . När det gäller parametrisk polymorfism har en typklass en parameter ( en typvariabel ) som spänner över en uppsättning typer. Ur ad hoc-polymorfs synvinkel är denna uppsättning inte bara diskret, utan också explicit specificerad ner till implementeringsnivån. Enkelt uttryckt betyder signaturen att funktionen är parametriskt polymorf , men utbudet av typer av dess parameter är begränsat endast till de typer som tillhör typklassen . På grund av detta skrivs funktionen på ett unikt sätt, trots anropet till den överbelastade funktionen från dess kropp. square :: Num a => a -> aNum

Inbyggt stöd för typklasser implementerades först i Haskell , men de kan också introduceras i valfritt parametriskt polymorft språk genom enkel förbearbetning [5] och även implementeras idiomatiskt (se till exempel ML-modulspråket#Implementing Alternative Models ). Direktstöd kan dock underlätta automatiska resonemang om programmens betydelse.

Likhetstyper i Haskell implementeras som instanser av en typklass (Eq generaliserar variabler för likhetstyp från Standard ML ) :

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

För att minska besväret med att koda några av de ofta uppenbart nödvändiga egenskaperna hos användardefinierade typer, tillhandahåller Haskell dessutom syntaktisk sugar , en konstruktion derivingsom är giltig för en begränsad uppsättning standardtypklasser (som Eq). (I det rysktalande samfundet förväxlas dess användning ofta med begreppet " arv " på grund av särdragen i översättningen av ordet " härleda ".)

Generiska algebraiska datatyper

Polytypism

Termen "polytypism" eller "datatypsgeneralisering" används ibland. I huvudsak hänvisar polytyping till språkets inbyggda stöd för typkonstruktorpolymorfism , utformat för att förena programmeringsgränssnitt och öka kodåteranvändning . Ett exempel på polytypism är den generaliserade mönstermatchningsalgoritmen [47] .

Per definition, i en polytypfunktion, " även om det kan finnas ett ändligt antal ad-hoc-grenar för vissa typer, finns det ingen ad-hoc-kombinator " [48] .

Polytyping kan implementeras genom användning av en generisk datatyp eller högre rang polymorfism . PolyP [49] -förlängningen av Haskell är en syntaxkonstruktion som förenklar definitionen av polytypfunktioner i Haskell .

En polytypningsfunktion är i någon mening mer allmän än en polymorf funktion, men å andra sidan kan en funktion vara polytypad och inte polymorf, vilket kan ses av följande funktionstypsignaturer :

huvud :: [ a ] -> a ( + ) :: Num a => a -> a -> a längd :: Regular d => d a -> Int summa :: Regular d => d Int -> Int

Den första funktionen ( head) är polymorf (parametriskt polymorf ), den andra (infixoperatorn “ ”) är överbelastad (ad-hoc-polymorf), den tredje och fjärde är polytypade: typvariabeln i deras definition varierar över typ konstruktörer . Samtidigt är den tredje funktionen ( ) polytypad och polymorf (förmodligen beräknar den "längden" för någon uppsättning polymorfa aggregattyper - till exempel antalet element i listor och träd ), och den fjärde ( ) är polytypad, men inte polymorf (monomorf över aggregattyper som tillhör typklassen , för vilken den troligen beräknar summan av heltal som bildar ett objekt av en viss aggregattyp). + dlength sum Regular

Övrigt

Dynamiskt typade språk representerar enhetligt varianter av polymorfism, vilket bildar en distinkt ideologi i dem och påverkar de tillämpade metoderna för uppgiftsnedbrytning. Till exempel, i Smalltalk kan vilken klass som helst ta emot meddelanden av vilken typ som helst, och antingen bearbeta dem på egen hand (inklusive genom introspektion ), eller vidarebefordra den till en annan klass - sålunda är vilken metod som helst formellt parametriskt polymorf, medan dess interna struktur kan förgrena sig enligt villkoret för dynamisk argumenttyp, implementera speciell polymorfism. I CLOS är multimetoder samtidigt förstklassiga funktioner , vilket gör att vi kan betrakta dem både som begränsat kvantifierade och som generaliserade ( äkta polymorfa ).

Statiskt polymorfiskt typade språk, däremot, kan implementera varianter av polymorfism ortogonalt (oberoende av varandra), vilket gör att de kan konstrueras intrikat på ett typsäkert sätt. Till exempel stöder OCaml parametriska klasser (liknande förmåga till C++-klassmallar , men verifierbara utan behov av instansiering), deras bredd- och djuparv (inklusive flera ), idiomatisk implementering av (genom signaturer - se motsvarande exempel på användning av ML-modulens språk ), inline polymorfism , parametrisk polymorfism av rang över 1 (med hjälp av så kallade lokalt abstrakta typer som implementerar existentiella typer ) och generaliserade algebraiska datatyper .

Historik

Termen "polymorfism" kommer från grekiskan. πολύς ("mycket") och μορφή ("form, form, enhet").

Termerna "specialiserad polymorfism" och "parametrisk polymorfism" nämns första gången 1967 i Christopher Stracheys föreläsningsanteckningar med titeln " Fundamentals of Programming Languages [ " [1] . 1985 formaliserade Peter Wegner och Luca Cardelli inneslutningspolymorfism för modellering av subtyper och arv [10] [27] , även om implementeringar av subtyper och arv dök upp mycket tidigare, på Simula- språket 1967 . Inklusionspolymorfism är baserad på begränsad kvantifiering .

Notationen av parametrisk polymorfism som en utveckling av λ-kalkylen (kallad F-systemet ) beskrevs formellt av logikern Jean-Yves Girard [50] [51] ( 1971 ), oberoende av honom beskrevs ett liknande system av datavetaren John S. Reynolds [52] ( 1974 ).

Det första språket helt baserat på den polymorfa λ-kalkylen var ML ( 1973 ); oberoende av honom implementerades parametriska typer i Clu ( 1974 ) [27] . Många moderna språk ( C++ , Java , C# , D och andra) tillhandahåller parametriska typer i en form som är mer eller mindre nära deras implementering i Clu.

1987 formaliserade Mitchel Wand inline polymorfism och typ slutledning för det [53] ; detta arbete hade en enorm inverkan på den efterföljande utvecklingen av typsystem . Samma år föreslog Philip Wadler och Stephen Blott typklasser [ ⇨ för att formalisera ad-hoc polymorfism .

Se även

Anteckningar

↑ 1 2 3 4 Strachey, 1967 .
↑ Cardelli, 1991 , sid. 3.
↑ Pierce, 2012 , 22.7. Polymorphism through let, sid. 354.
↑ 1 2 Cardelli, 1985 , sid. 6.
↑ 1 2 3 4 5 Wadler, 1988 , sid. 1-2.
↑ Bjarne Stroustrup . C++ Ordlista (19 februari 2007). Arkiverad från originalet den 29 juni 2018. (obestämd)
↑ Andrew W. Appel. En kritik av Standard ML . — Princeton University, 1992.
↑ Harper, 2012 , 20.1 System F, sid. 172.
↑ Pierce, 2012 , 23.2 Varieties of polymorphism, sid. 365.
↑ 1 2 3 Cardelli, 1985 .
↑ Mitchell, 2002 , 6.4. Polymorfism och överbelastning, sid. 145-151.
↑ Cardelli, 1985 , 1.3. Typer of Polymorphism, sid. 6.
↑ 1 2 Cardelli, 1985 , sid. 5-6.
↑ Cardelli, 1996 , 5 andra ordningens typsystem, sid. 25.
↑ Harper, 2012 , 20.3 Parametrisitetsöversikt, sid. 177.
↑ Harper, 2012 , 49 Parametricity, sid. 495-508.
↑ Pierce, 2012 , 23.9 Parametricity, sid. 384-385.
↑ Harper, 2012 , 21.4 Representation Independence, sid. 188.
↑ Pierce, 2012 , 30.5 Going Further: Dependent Types, sid. 489-493.
↑ Reynolds, 1998 , 16. Undertyper och skärningstyper. Bibliografiska anteckningar, sid. 376.
↑ Cardelli, 1985 .
↑ Mitchell, 2002 , 10.2.6 Inheritance Is Not Subtyping, sid. 287.
↑ Cardelli, 1991 .
↑ 1 2 Pierce, 2012 , 15 undertyper, sid. 193.
↑ 1 2 Pierce, 2012 , 15. Subtyper, sid. 193.
↑ Harper, 2012 , 23.1. Subsumtion, sid. 208.
↑ 1 2 3 Pierce, 2012 , 1.4 Kort historia, sid. 11-13.
↑ Cardelli, 1991 , 6. Power kinds, sid. 32.
↑ 1 2 3 4 Abadi, Cardelli, 1994 .
↑ 1 2 3 Cardelli, 1985 , 6. Bounded Quantification, sid. 28.
↑ Minsky översatt av DMK, 2014 , Subtyping, sid. 259.
↑ Cardelli, 1985 , sid. 9.
↑ Harper, 2012 , kapitel 16. Rekursiva typer, sid. 132.
↑ 1 2 Cardelli, 1991 , sid. 35-37.
↑ Cardelli, 1985 , 2.3. Grundtyper, strukturerade typer och rekursion, sid. 12-14.
↑ Harper, 2012 , kapitel 25. Dynamic Dispatch, sid. 229.
↑ 1 2 Joyner, 1996 , 3.38 Signature Variance, sid. 35.
↑ Objektorienterad programmering i Standard ML . Hämtad 11 mars 2016. Arkiverad från originalet 14 januari 2016. (obestämd)
↑ Minsky översatt av DMK, 2014 , kapitel 11. Objekt, sid. 253.
↑ ML2000-arbetsgruppen. Principer och en preliminär design för ML2000 . — 1999.
↑ Castagna, Ghelli, Longo. En kalkyl för överbelastade funktioner med subtyping // Information and Computation. - Akademisk press, 1995. - T. 117 , nr. 1 . - S. 115-135 . - doi : 10.1006/inco.1995.1033 .
↑ Joyner, 1996 , 2.8 Encapsulation, sid. åtta.
↑ Mitchell, 2002 , 6.2.1 Typsäkerhet, sid. 132-133.
↑ Harper, 2012 , kapitel 4. Statik, sid. 35.
↑ Pierce, 2012 , 31. Subtyper av högre ordning, sid. 495.
↑ 12 Wadler , 1988 , sid. 3.
↑ Johan Jeuring. Polytypisk mönstermatchning // FPCA. - 1995. - doi : 10.1.1.36.5645 .
↑ Ralf Lammel och Joost Visser, "Typed Combinators for Generic Traversal", i Practical Aspects of Declarative Languages: 4th International Symposium (2002), sid. 153.
↑ Patrik Jansson, Johan Jeuring. PolyP - Ett polytypiskt programmeringsspråkstillägg . — Sigplan SPPL, 1997.
↑ Girard - Extension of Type Theory, 1971 .
↑ Girard - Kalkyl av högre ordning, 1972 .
↑ Reynolds, 1974 .
↑ Wand, 1987 .

Litteratur

Christopher Strachey. Grundläggande begrepp i programmeringsspråk . - 1967. Arkiverad 12 augusti 2017.
- Återpublicerad: Christopher Strachey. Grundläggande begrepp i programmeringsspråk // Högre ordning och symbolisk beräkning . - 2000. - Vol. 13 . - S. 11-49 . - doi : 10.1023/A:1010000313106 .
Jean-Yves Girard. Une Extension de l'Interpretation de Gödel à l'Analyse, et son Application à l'Élimination des Coupures dans l'Analyse et la Théorie des Types (franska) // Proceedings of the Second Scandinavian Logic Symposium. - Amsterdam, 1971. - S. 63-92 . - doi : 10.1016/S0049-237X(08)70843-7 .
Jean-Yves Girard. Tolkning fonctionnelle et elimination des coupures de l'arithmétique d'ordre supérieur (franska) . — Université Paris 7, 1972.
John C. Reynolds. Mot en teori om typstruktur // Lecture Notes in Computer Science . - Paris: Colloque sur la programmation, 1974. - Vol 19 . - S. 408-425 . - doi : 10.1007/3-540-06859-7_148 .
Luca Cardelli , Peter Wegner. Om att förstå typer, dataabstraktion och polymorfism //ACM Computing Surveys. - New York, USA:ACM, 1985. -17,nr. 4. -S. 471-523. —ISSN 0360-0300. -doi:10.1145/6041.6042.

Robert Harper . Introduktion till Standard ML. - Carnegie Mellon University, 1986. - ISBN PA 15213-3891.

Översättning till ryska: Robert Harper . Introduktion till Standard ML. - Carnegie Mellon University, 1986. - 97 sid. — ISBN PA 15213-3891.

Mitchell Wand . Komplett typslutning för enkla objekt // In Proc. Andra IEEE-symposiet om logik i datavetenskap. - 1987. -S. 37-44.
Philip Wadler, Stephen Blott. Hur man gör ad hoc polymorfism mindre ad hoc . — 1988.
Luca Cardelli . Typisk programmering // IFIP State-of-the-Art-rapporter. - New York: Springer-Verlag, 1991. -Iss. Formell beskrivning av programmeringskoncept. -s. 431-507.
Martin Abadi, Luca Cardelli . En semantik av objekttyper . — LICS , 1994.

Luca Cardelli . Typsystem (engelska) // Handbook of Computer Science and Engineering. — CRC Press, 1996.

Ian Joyner. En kritik av C++ och programmerings- och språktrender på 1990-talet - 3:e upplagan // copyright och publikationslista . — 1996.

John C. Reynolds. Teorier om programmeringsspråk . - Cambridge University Press, 1998. - ISBN 978-0-521-59414-1 (inbunden), 978-0-521-10697-9 (pocket).

Benjamin Pierce. Typer och programmeringsspråk . - MIT Press , 2002. - ISBN 0-262-16209-1 .
- Översättning till ryska: Benjamin Pierce. Typer i programmeringsspråk . - Dobrosvet , 2012. - 680 sid. — ISBN 978-5-7913-0082-9 . (ryska)

John C. Mitchell Begrepp i programmeringsspråk . - Cambridge University Press, 2002. - 540 sid. - ISBN 978-0-521-78098-8 .

Georg Neis, Derek Dreyer, Andreas Rossberg. Icke-parametrisk parametrisitet (engelska) // ICFP. — ACM, 2009.

Robert Harper . Praktiska grunder för programmeringsspråk. - version 1.37 (reviderad 2014-11-01). - licensierad under Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 United States License., 2012. - 544 sid. Arkiverad24 oktober 2015 påWayback Machine

Minsky, Madhavapeddy, Hickey. Real World OKaml: Funktionell programmering för massorna . - O'Reilly Media, 2013. - 510 sid. — ISBN 9781449324766 .
- Översättning till ryska: Minsky, Madhavapeddy, Hickey. Programmering i Ocaml-språket . - DMK, 2014. - 536 sid. — (Funktionell programmering). - ISBN 978-5-97060-102-0 . (ryska)