Undertype - Subtyping

I programmeringssprogsteorien er subtyping (også undertype polymorfisme eller inklusionspolymorfisme ) en form for type polymorfisme , hvor en undertype er en datatype, der er relateret til en anden datatype ( supertypen ) af en eller anden forestilling om substituerbarhed , hvilket betyder, at programelementer, typisk underprogrammer eller funktioner, der er skrevet til at fungere på elementer af supertypen, kan også fungere på elementer af undertypen. Hvis S er en undertype af T, den undertypisering forhold er ofte skrevet S <: T, til at betyde, at ethvert udtryk af typen S kan sikkert bruges i en kontekst, hvor der forventes et udtryk af typen T. Den præcise semantik i subtyping afhænger afgørende af detaljerne om, hvad "sikkert bruges i en kontekst, hvor" betyder i et givet programmeringssprog . Den typesystemet af et programmeringssprog væsentlige definerer sin egen undertypebestemmelse forhold, som meget vel kan være triviel skal sproget support ingen (eller meget lille) konvertering mekanismer.

På grund af undertypeforholdet kan et udtryk tilhøre mere end én type. Subtyping er derfor en form for type polymorfisme. I objektorienteret programmering bruges udtrykket 'polymorfisme' sædvanligvis kun til at referere til denne undertype polymorfisme , mens teknikkerne til parametrisk polymorfisme ville blive betragtet som generisk programmering .

Funktionelle programmeringssprog tillader ofte subtyping af poster . Følgelig er simpelthen indtastet lambda -beregning udvidet med posttyper måske den enkleste teoretiske indstilling, hvor en nyttig forestilling om underskrivning kan defineres og studeres. Fordi den resulterende beregning tillader udtryk at have mere end én type, er det ikke længere en "simpel" typeteori . Da funktionelle programmeringssprog pr. Definition understøtter funktionslitteraler , som også kan gemmes i poster, giver poster med undertyper nogle af funktionerne i objektorienteret programmering. Typisk giver funktionelle programmeringssprog også en, normalt begrænset, form for parametrisk polymorfisme. I en teoretisk setting er det ønskeligt at studere interaktionen mellem de to funktioner; en fælles teoretisk indstilling er systemet F _<: . Forskellige calculi, der forsøger at indfange de teoretiske egenskaber af objektorienteret programmering kan være afledt fra system F _<: .

Begrebet subtyping er relateret til de sproglige forestillinger om hyponymi og holonymi . Det er også relateret til begrebet begrænset kvantificering i matematisk logik (se Ordenssorteret logik ). Undertyping bør ikke forveksles med forestillingen om (klasse eller objekt) arv fra objektorienterede sprog; subtyping er en relation mellem typer (grænseflader i objektorienteret sprogbrug), mens arv er en relation mellem implementeringer, der stammer fra en sprogfunktion, der gør det muligt at oprette nye objekter fra eksisterende. I en række objektorienterede sprog kaldes undertyper interface-arv , med arv omtalt som implementeringsarv .

Oprindelse

Forestillingen om at skrive under på programmeringssprog går tilbage til 1960'erne; det blev introduceret i Simula -derivater. De første formelle behandlinger af undertyper blev givet af John C. Reynolds i 1980, der brugte kategoriteori til at formalisere implicitte konverteringer , og Luca Cardelli (1985).

Begrebet subtyping har fået synlighed (og synonym med polymorfisme i nogle kredse) med den almindelige vedtagelse af objektorienteret programmering. I denne sammenhæng kaldes princippet om sikker substitution ofte Liskov-substitutionsprincippet efter Barbara Liskov, der populariserede det i en hovedtale på en konference om objektorienteret programmering i 1987. Fordi det skal overveje mutable objekter, den ideelle forestilling om subtyping defineret af Liskov og Jeannette Wing , kaldet adfærdsundertyping er betydeligt stærkere end hvad der kan implementeres i en typechecker . (Se § Funktionstyper nedenfor for detaljer.)

Eksempler

Eksempel på undertyper: hvor fugl er supertypen og alle andre er undertyper som angivet med pilen i UML -notation

Et simpelt praktisk eksempel på undertyper er vist i diagrammet til højre. Typen "fugl" har tre undertyper "and", "gøg" og "strudse". Begrebsmæssigt er hver af disse en række af grundtypen "fugl", der arver mange "fugle" egenskaber, men har nogle specifikke forskelle. Den UML notation anvendes i dette diagram, med åbne hoveder pile viser retningen og typen af forholdet mellem supertype og dets undertyper.

Som et mere praktisk eksempel kan et sprog muliggøre, at der bruges heltalværdier, hvor der forventes floating point -værdier ( Integer< Float:), eller det kan definere en generisk typeNummersom en almindelig supertype af heltal og realer. I dette andet tilfælde, vi kun har Integer<: Numberog Float<: Number, men Integerog Floater ikke undertyper af hinanden.

Programmerere kan udnytte undertype til at skrive kode på en mere abstrakt måde, end det ville være muligt uden det. Overvej følgende eksempel:

function max (x as Number, y as Number) is
    if x < y then
        return y
    else
        return x
end

Hvis heltal og reel begge er undertyper af Number, og en operator for sammenligning med et vilkårligt tal er defineret for begge typer, kan værdier af begge typer overføres til denne funktion. Selve muligheden for at implementere en sådan operatør begrænser imidlertid taltypen stærkt (for eksempel kan man ikke sammenligne et helt tal med et komplekst tal), og faktisk kun sammenligne heltal med heltal og reelle med reelle, giver mening. Omskrivning af denne funktion, så den kun accepterer 'x' og 'y' af samme type, kræver begrænset polymorfisme .

Tilskud

Ved type teori begrebet subsumption bruges til at definere eller vurdere, om en type S er en undertype af typen T .

En type er et sæt værdier. Sættet kan beskrives udvidet ved at angive alle værdierne, eller det kan beskrives intensivt ved at angive medlemskabet af sættet af et prædikat over et domæne med mulige værdier. I almindelige programmeringssprog defineres optællingstyper udvidet ved at angive værdier. Brugerdefinerede typer som poster (strukturer, grænseflader) eller klasser defineres intensivt af en eksplicit typedeklaration eller ved at bruge en eksisterende værdi, som koder for typeoplysninger, som en prototype, der skal kopieres eller udvides.

I diskussionen af begrebet subsumption, er det sæt af værdier af en type indikeret ved at skrive sit navn i matematiske kursiv: T . Den type, ses som et prædikat på et domæne, indikeres ved at skrive sit navn med fed skrift: T . Det konventionelle symbol <: betyder "er en undertype af", og :> betyder "er en supertype af".

• A typen T indordner S hvis værdisæt T som den definerer, er en overordnet sættet S , således at hvert medlem af S er også et medlem af T .
• En type kan indordnes af mere end én type: de supertyper af S skærer hinanden ved S .
• Hvis S <: T (og derfor S ⊆ T ), derefter T , prædikatet som omgiver sæt T , skal være en del af prædikat S (over samme domæne), der definerer S .
• Hvis S subsumer T , og T subsumes S , så er de to typer ens (selvom de muligvis ikke er den samme type, hvis typesystemet adskiller typer ved navn).

En tommelfingerregel følger: en undertype er sandsynligvis "større/bredere/dybere" (dens værdier indeholder flere oplysninger) og "færre/mindre" (værdisættet er mindre) end en af ​​dens supertyper (som har mere begrænset information, og hvis værdisæt er et supersæt af værdierne for undertypen).

I forbindelse med subsumption kan typedefinitionerne udtrykkes ved hjælp af Set-builder-notation , der bruger et prædikat til at definere et sæt. Prædikater kan defineres over et domæne (sæt af mulige værdier) D . Predikater er delfunktioner, der sammenligner værdier med udvælgelseskriterier. For eksempel: "er en heltalværdi større end eller lig med 100 og mindre end 200?". Hvis en værdi matcher kriterierne, returnerer funktionen værdien. Hvis ikke, vælges værdien ikke, og intet returneres. (Listeforståelser er en form for dette mønster, der bruges i mange programmeringssprog.)

Hvis der er to prædikater, som anvender udvælgelseskriterier for typen T , og som anvender yderligere kriterier for typen S , kan sæt for de to typer defineres: ${\ displaystyle P_ {T}}$${\ displaystyle P_ {s}}$

${\ displaystyle T = \ {v \ i D \ mid \ P_ {T} (v) \}}$

${\ displaystyle S = \ {v \ i D \ mid \ P_ {T} (v) {\ tekst {og}} P_ {s} (v) \}}$

Prædikatet påføres sammen som en del af forbindelsen prædikat S afgrænser S . De to prædikater er sammenføjede , så begge skal være sande for at en værdi kan vælges. Det prædikat indordner prædikatet T , så S <: T .${\ displaystyle \ mathbf {T} = P_ {T}}$${\ displaystyle P_ {s}}$${\ displaystyle \ mathbf {S} = \ mathbf {T} \ land P_ {s} = P_ {T} \ land P_ {s}}$

For eksempel: der er en underfamilie af kattearter kaldet Felinae , som er en del af familien Felidae . Slægten Felis , som huskattearten Felis catus tilhører, er en del af denne underfamilie.

${\ displaystyle {\ mathit {Felinae = \ {cat \ in Felidae \ mid \ ofSubfamily (cat, felinaeSubfamilyName) \}}}}}$

${\ displaystyle {\ mathit {Felis = \ {cat \ in Felinae \ mid \ ofGenus (cat, felisGenusName) \}}}}}$

Forbindelsen af ​​prædikater er blevet udtrykt her ved anvendelse af det andet prædikat over domænet af værdier, der er i overensstemmelse med det første prædikat. Set som typer, Felis <: Felinae <: Felidae .

Hvis T undertrykker S ( T:> S ), vil en procedure, funktion eller udtryk, der får en værdi som en operand (inputargument eller udtryk) derfor kunne operere over denne værdi som en af ​​type T , fordi . I eksemplet ovenfor kunne vi forvente, at funktionen af underfamilien kan anvendes på værdier af alle tre typer Felidae , Felinae og Felis . ${\ displaystyle s \ i S}$${\ displaystyle s \ i T}$

Subtyping ordninger

Typeteoretikere skelner mellem nominel undertyping, hvor kun deklarerede typer på en bestemt måde kan være undertyper af hinanden og strukturel undertyping , hvor strukturen af ​​to typer afgør, om den ene er en undertype af den anden eller ej. Den ovenfor beskrevne klassebaserede objektorienterede undertyper er nominelle; en strukturel underskrivningsregel for et objektorienteret sprog kan sige, at hvis objekter af type A kan håndtere alle de meddelelser, som objekter af type B kan håndtere (det vil sige, hvis de definerer alle de samme metoder ), så er A en undertype af B uanset om enten arver fra den anden. Denne såkaldte andetyping er almindelig i dynamisk indtastede objektorienterede sprog. Lydstrukturerede underskrivingsregler for andre typer end objekttyper er også velkendte.

Implementeringer af programmeringssprog med undertyper falder i to generelle klasser: inkluderende implementeringer, hvor repræsentationen af ​​en hvilken som helst værdi af type A også repræsenterer den samme værdi ved type B, hvis A  <:  B , og tvangsimplementeringer , hvor en værdi af type A kan konverteres automatisk til et af typen B . Undertypingen forårsaget af subklassering i et objektorienteret sprog er normalt inkluderende; subtyping-relationer, der relaterer heltal og floating-point tal, som er repræsenteret forskelligt, er normalt tvangsmæssige.

I næsten alle typesystemer, der definerer en undertypeforhold, er det refleksivt (hvilket betyder A  <:  A for enhver type A ) og transitivt (hvilket betyder, at hvis A  <:  B og B  <:  C, så A  <:  C ). Dette gør det til en forudbestilling på typer.

Registreringstyper

Undertypning af bredde og dybde

Typer af registreringer giver anledning til begreberne bredde og dybde subtypning. Disse udtrykker to forskellige måder at opnå en ny type post, der tillader de samme operationer som den originale posttype.

Husk, at en post er en samling af (navngivne) felter. Da en undertype er en type, der tillader alle operationer, der er tilladt på den originale type, bør en postundertype understøtte de samme operationer på felterne som den originale type, der understøttes.

En slags måde at opnå sådan support, kaldet breddeundertypning , tilføjer flere felter til posten. Mere formelt vil hvert (navngivet) felt, der vises i breddet supertype, vises i undertypen for bredde. Enhver operation, der er mulig på supertypen, understøttes således af undertypen.

Den anden metode, kaldet dybdeunderskrivning , erstatter de forskellige felter med deres undertyper. Det vil sige, at felterne i undertypen er undertyper af felterne i supertypen. Da enhver handling, der understøttes for et felt i supertypen, understøttes for dens undertype, understøttes enhver operation, der er mulig på postens supertype, af postens undertype. Dybdeindskrivning giver kun mening for uforanderlige poster: for eksempel kan du tildele 1,5 til 'x' -feltet i et reelt punkt (en post med to rigtige felter), men du kan ikke gøre det samme til' x' -feltet i et helt tal (som dog er en dyb undertype af den virkelige punkttype), fordi 1,5 ikke er et helt tal (se Variance ).

Subtyping af poster kan defineres i System F _< :, som kombinerer parametrisk polymorfisme med subtyping af posttyper og er et teoretisk grundlag for mange funktionelle programmeringssprog, der understøtter begge funktioner.

Nogle systemer understøtter også undertypning af mærkede disjoint union -typer (f.eks. Algebraiske datatyper ). Reglen for breddeunderskrivning er omvendt: hvert mærke, der vises i undertypen for bredde, skal vises i breddet supertype.

Funktionstyper

Hvis T ₁ → T ₂ er en funktionstype, er en undertype af den en hvilken som helst funktionstype S ₁ → S ₂ med den egenskab, at T ₁ <: S ₁ og S ₂ <: T ₂ . Dette kan opsummeres ved hjælp af følgende skrive -regel :

${\ displaystyle T_ {1} \ leq: S_ {1} \ quad S_ {2} \ leq: T_ {2} \ over S_ {1} \ rightarrow S_ {2} \ leq: T_ {1} \ rightarrow T_ { 2}}$

Argumenttypen S ₁ → S ₂ siges at være kontravariant, fordi subtypeforholdet er omvendt for den, hvorimod returtypen er kovariant . Uformelt sker denne vending, fordi den raffinerede type er "mere liberal" i de typer, den accepterer og "mere konservativ" i den type, den returnerer. Det er præcis det, der fungerer i Scala : en n -ary -funktion er internt en klasse, der arver egenskaben (som kan ses som en generel grænseflade på Java -lignende sprog), hvor er parametertyperne, og B er dens returtype; " - " før typen betyder, at typen er kontravariant, mens " + " betyder kovariant. ${\ displaystyle {\ mathtt {Function_ {N} (-A_ {1},-A_ {2}, \ dots, -A_ {n},+B)}}}}$ ${\ displaystyle {\ mathtt {A_ {1}, A_ {2}, \ prikker A_ {n}}}}$

På sprog, der tillader bivirkninger, som de fleste objektorienterede sprog, er subtypning generelt ikke tilstrækkelig til at garantere, at en funktion sikkert kan bruges i kontekst af en anden. Liskovs arbejde på dette område fokuserede på adfærdsmæssig undertyping , som udover den systemsystemsikkerhed , der diskuteres i denne artikel, også kræver, at undertyper bevarer alle invarianter, der garanteres af supertyperne i en eller anden kontrakt . Denne definition af underskrivning er generelt uafgørelig , så den kan ikke verificeres af en typechecker .

Undertypingen af mutable referencer ligner behandlingen af ​​funktionsargumenter og returnværdier. Skrivebeskrevne referencer (eller dræn ) er modstridende, ligesom funktionsargumenter; skrivebeskyttede referencer (eller kilder ) er kovariante, ligesom returværdier. Omskiftelige referencer, der fungerer som både kilder og dræn, er uforanderlige.

Forholdet til arv

Subtyping og arv er uafhængige (ortogonale) relationer. De falder måske sammen, men ingen er et specielt tilfælde af den anden. Med andre ord, mellem to typer S og T er alle kombinationer af undertyper og arv mulige:

1. S er hverken en undertype eller en afledt type T
2. S er en undertype, men er ikke en afledt type T
3. S er ikke en undertype, men er en afledt type T
4. S er både en undertype og en afledt type T

Den første sag er illustreret af uafhængige typer, såsom Booleanog Float.

Det andet tilfælde kan illustreres ved forholdet mellem Int32og Int64. I de fleste objektorienterede programmeringssprog Int64er de ikke forbundet med arv til Int32. Imidlertid Int32kan betragtes som en undertype af Int64eftersom enhver 32 bit heltal kan fremmes i et 64 bit heltal værdi.

Det tredje tilfælde er en konsekvens af funktionstyping af inputkontravarians . Antag en superklasse af type T med en metode m, der returnerer et objekt af samme type ( dvs. typen af m er T → T , bemærk også, at det første argument for m er dette/selv) og en afledt klasse type S fra T . Ved arv, typen af m i S er S → S . For S at være en undertype af T typen af m i S skal være en undertype af typen af m i T , med andre ord: S → S ≤: T → T . Ved bottom-up anvendelse af funktionsunderskrivelsesreglen betyder dette: S ≤: T og T ≤: S , hvilket kun er muligt, hvis S og T er de samme. Eftersom arv er en irreflexive forhold, S kan ikke være en undertype af T .

Subtyping og arv er kompatible, når alle nedarvede felter og metoder af den afledte type har typer, der er undertyper af de tilsvarende felter og metoder fra den arvede type.

Tvang

I tvangsunderskrivende systemer defineres undertyper af implicitte konverteringsfunktioner fra subtype til supertype. For hver subtypning forholdet ( S <: T ), en tvang funktion tvinge : S → T er tilvejebragt, og enhver genstand s af type S betragtes som objektet tvinge _{S → T} ( s ) af typen T . En tvang funktion kan defineres ved sammensætning: hvis S <: T og T <: U derefter s kan betragtes som et objekt af typen u under forbindelsen tvang ( tvinge _{T → U} ∘ tvinge _{S → T} ). Den type, tvang fra en type til sig selv tvinge _{T → T} er identitetsfunktion id _T

Tvangsfunktioner for optegnelser og usammenhængende foreningers undertyper kan defineres komponentvis; i tilfælde af breddeudvidede poster, kasserer type tvang simpelthen alle komponenter, der ikke er defineret i supertypen. Typetvangen for funktionstyper kan angives ved f ' ( s ) = coerce _{S 2 → T 2} ( f ( coerce _{T 1 → S 1} ( t ))), hvilket afspejler kontravariansen mellem funktionsargumenter og kovarians af returværdier.

Tvangsfunktionen bestemmes entydigt givet subtype og supertype . Når der er defineret flere undertypeforhold, skal man således være omhyggelig med at garantere, at alle typer tvang er sammenhængende. For eksempel, hvis et helt tal som 2: int kan tvinges til et flydende tal (f.eks. 2.0: float ), er det ikke tilladt at tvinge 2.1: float til 2: int , fordi sammensat tvangstvang _{flyder → flyder} givet af coerce _{int → float} ∘ coerce _{float → int} ville så adskille sig fra identitetstvang id _float .

Se også

• Kovarians og kontravariation
• Den cirkel-ellipse problem (for farerne ved undertypisering variable-typer på samme grundlag som value-typer)
• Klassebaseret programmering
• Top type
• Forfiningstype
• Adfærdsmæssig underskrivning

Noter

Referencer

Lærebøger

Papirer

Yderligere læsning