Untertypisierung – Wikipedia

Form des Typpolymorphismus

In der Programmiersprachtheorie Untertypisierung (ebenfalls Subtyp Polymorphismus oder Einschlusspolymorphismus) ist eine Form des Typpolymorphismus, bei der a Subtyp ist ein Datentyp, der mit einem anderen Datentyp verknüpft ist (der Supertyp) durch einen Begriff der Substituierbarkeit, was bedeutet, dass Programmelemente, typischerweise Unterprogramme oder Funktionen, die geschrieben wurden, um Elemente des Supertyps zu bearbeiten, auch Elemente des Untertyps bearbeiten können. Wenn S ein Subtyp von T ist, wird die Subtypisierungsbeziehung oft S <: T geschrieben, was bedeutet, dass jeder Term vom Typ S sein kann sicher in einem Kontext verwendet, in dem ein Term vom Typ T wird erwartet. Die genaue Semantik der Subtypisierung hängt entscheidend von den Einzelheiten dessen ab, was “sicher in einem Kontext verwendet wird, in dem” in einer bestimmten Programmiersprache bedeutet. Das Typsystem einer Programmiersprache definiert im Wesentlichen ihre eigene Subtypisierungsbeziehung, was durchaus trivial sein kann, wenn die Sprache keine (oder nur sehr wenige) Konvertierungsmechanismen unterstützt.

Aufgrund der Subtypisierungsbeziehung kann ein Begriff zu mehr als einem Typ gehören. Die Subtypisierung ist daher eine Form des Typpolymorphismus. In der objektorientierten Programmierung wird der Begriff “Polymorphismus” üblicherweise verwendet, um sich ausschließlich darauf zu beziehen Subtyp Polymorphismus, während die Techniken des parametrischen Polymorphismus berücksichtigt würden generische Programmierung.

Funktionale Programmiersprachen ermöglichen häufig die Untertypisierung von Datensätzen. Folglich ist ein einfach typisierter Lambda-Kalkül, der um Datensatztypen erweitert wurde, möglicherweise die einfachste theoretische Einstellung, in der ein nützlicher Begriff der Subtypisierung definiert und untersucht werden kann^{[citation needed]}. Da der resultierende Kalkül zulässt, dass Begriffe mehr als einen Typ haben, handelt es sich nicht mehr um eine “einfache” Typentheorie. Da funktionale Programmiersprachen per Definition Funktionsliterale unterstützen, die auch in Datensätzen gespeichert werden können, bieten Datensatztypen mit Untertypisierung einige der Merkmale der objektorientierten Programmierung. Typischerweise bieten funktionale Programmiersprachen auch eine, normalerweise eingeschränkte Form des parametrischen Polymorphismus. In einer theoretischen Umgebung ist es wünschenswert, die Wechselwirkung der beiden Merkmale zu untersuchen; Eine übliche theoretische Einstellung ist System F._<:. Verschiedene Kalküle, die versuchen, die theoretischen Eigenschaften der objektorientierten Programmierung zu erfassen, können vom System F abgeleitet werden_<:.

Das Konzept der Subtypisierung hängt mit den sprachlichen Begriffen Hyponymie und Holonymie zusammen. Es hängt auch mit dem Konzept der begrenzten Quantifizierung in der mathematischen Logik zusammen. Die Subtypisierung sollte nicht mit dem Begriff der (Klassen- oder Objekt-) Vererbung von objektorientierten Sprachen verwechselt werden. Subtyping ist eine Beziehung zwischen Typen (Schnittstellen in objektorientierter Sprache), während Vererbung eine Beziehung zwischen Implementierungen ist, die aus einem Sprachfeature stammen, mit dem neue Objekte aus vorhandenen Objekten erstellt werden können. In einer Reihe von objektorientierten Sprachen wird die Untertypisierung aufgerufen Schnittstellenvererbung, mit Vererbung bezeichnet als Implementierungsvererbung.

Ursprünge[edit]

Der Begriff der Untertypisierung in Programmiersprachen stammt aus den 1960er Jahren; Es wurde in Simula-Derivaten eingeführt. Die ersten formalen Behandlungen der Subtypisierung wurden 1980 von John C. Reynolds, der die Kategorietheorie zur Formalisierung impliziter Konvertierungen verwendete, und Luca Cardelli (1985) gegeben.^[2]

Das Konzept der Subtypisierung hat durch die gängige Übernahme der objektorientierten Programmierung an Sichtbarkeit gewonnen (und in einigen Kreisen Synonymie mit Polymorphismus). In diesem Zusammenhang wird das Prinzip der sicheren Substitution oft als Liskov-Substitutionsprinzip bezeichnet, nachdem Barbara Liskov es 1987 in einer Grundsatzrede auf einer Konferenz über objektorientierte Programmierung populär gemacht hatte. Da es veränderbare Objekte berücksichtigen muss, ist dies der ideale Begriff der Subtypisierung Die von Liskov und Jeannette Wing definierte verhaltensbezogene Subtypisierung ist erheblich stärker als das, was in einer Typprüfung implementiert werden kann. (Einzelheiten finden Sie unten unter Funktionstypen.)

Beispiele[edit]

Beispiel für Subtypen: wobei Vogel der Supertyp ist und alle anderen Subtypen sind, wie durch den Pfeil in der UML-Notation angegeben

Ein einfaches praktisches Beispiel für Untertypen ist in der Abbildung rechts dargestellt. Der Typ “Vogel” hat drei Untertypen “Ente”, “Kuckuck” und “Strauß”. Konzeptionell ist jedes davon eine Vielzahl des Grundtyps “Vogel”, der viele “Vogel” -Eigenschaften erbt, jedoch einige spezifische Unterschiede aufweist. In diesem Diagramm wird die UML-Notation verwendet, wobei Pfeile mit offenem Kopf die Richtung und den Typ der Beziehung zwischen dem Supertyp und seinen Subtypen anzeigen.

Als praktischeres Beispiel könnte eine Sprache die Verwendung ganzzahliger Werte überall dort ermöglichen, wo Gleitkommawerte erwartet werden (Integer <: Float), oder es könnte einen generischen Typ definieren Nummer als ein üblicher Supertyp von ganzen Zahlen und den Realzahlen. In diesem zweiten Fall haben wir nur Integer <: Number und Float <: Number, aber Integer und Float sind keine Untertypen voneinander.

Programmierer können die Untertypisierung nutzen, um Code abstrakter zu schreiben, als dies ohne möglich wäre. Betrachten Sie das folgende Beispiel:

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

Wenn Integer und Real beide Subtypen von sind NumberWenn für beide Typen ein Vergleichsoperator mit einer beliebigen Zahl definiert ist, können Werte beider Typen an diese Funktion übergeben werden. Die Möglichkeit, einen solchen Operator zu implementieren, schränkt den Zahlentyp jedoch stark ein (zum Beispiel kann man eine ganze Zahl nicht mit einer komplexen Zahl vergleichen), und tatsächlich ist es nur sinnvoll, ganze Zahlen mit ganzen Zahlen und reelle mit reellen zu vergleichen. Um diese Funktion so umzuschreiben, dass nur ‘x’ und ‘y’ des gleichen Typs akzeptiert werden, ist ein begrenzter Polymorphismus erforderlich.

Subsumtion[edit]

In der Typentheorie ist das Konzept von Subsumtion^[3] wird verwendet, um zu definieren oder zu bewerten, ob ein Typ S. ist ein Untertyp vom Typ T..

Ein Typ ist eine Reihe von Werten. Das Set kann beschrieben werden erweitert durch Auflisten aller Werte, oder es kann beschrieben werden intensiv durch Angabe der Zugehörigkeit der Menge durch ein Prädikat über eine Domäne möglicher Werte. In gängigen Programmiersprachen werden Aufzählungstypen durch Auflisten von Werten erweitert. Benutzerdefinierte Typen wie Datensätze (Strukturen, Schnittstellen) oder Klassen werden intensiv durch eine explizite Typdeklaration oder durch Verwendung eines vorhandenen Werts, der Typinformationen codiert, als zu kopierender oder zu erweiternder Prototyp definiert.

Bei der Erörterung des Konzepts der Subsumtion wird die Menge der Werte eines Typs angegeben, indem sein Name in mathematischer Kursivschrift geschrieben wird: T.. Der Typ, der als Prädikat über einer Domain angesehen wird, wird durch Fettdruck angegeben: T.. Das herkömmliche Symbol <: bedeutet “ist ein Subtyp von” und :> bedeutet “ist ein Supertyp von”.

• Eine Art T. subsumiert S. wenn die Menge der Werte T. was es definiert, ist eine Obermenge der Menge S., so dass jedes Mitglied von S. ist auch Mitglied von T..
• Ein Typ kann von mehr als einem Typ subsumiert werden: den Supertypen von S. schneiden bei S..
• Wenn S <: T. (und deshalb S. ⊆ T. ), dann T., das Prädikat, das die Menge umschreibt T.muss Teil des Prädikats sein S. (über dieselbe Domain) die definiert S..

• Wenn S. subsumiert T., und T. subsumiert S.Dann sind die beiden Typen gleich (obwohl sie möglicherweise nicht vom selben Typ sind, wenn das Typsystem Typen nach Namen unterscheidet).

Als Faustregel gilt: Ein Subtyp ist wahrscheinlich “größer / breiter / tiefer” (seine Werte enthalten mehr Informationen) und “weniger / kleiner” (der Wertesatz ist kleiner) als einer seiner Supertypen (der eingeschränkter ist) Informationen, und deren Wertesatz eine Obermenge derjenigen des Subtyps ist).

Im Zusammenhang mit Subsumtionen können Typdefinitionen mit der Set-Builder-Notation ausgedrückt werden, bei der ein Prädikat zum Definieren einer Menge verwendet wird. Prädikate können über eine Domäne definiert werden (Satz möglicher Werte) D.. Prädikate sind Teilfunktionen, die Werte mit Auswahlkriterien vergleichen. Zum Beispiel: “Ist ein ganzzahliger Wert größer oder gleich 100 und kleiner als 200?”. Wenn ein Wert den Kriterien entspricht, gibt die Funktion den Wert zurück. Wenn nicht, wird der Wert nicht ausgewählt und nichts zurückgegeben. (Listenverständnis ist eine Form dieses Musters, das in vielen Programmiersprachen verwendet wird.)

Wenn es zwei Prädikate gibt,

Hier werden Auswahlkriterien für den Typ angewendet T., und

Dies gilt für zusätzliche Kriterien für den Typ S.Dann können Sätze für die beiden Typen definiert werden:

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

${ displaystyle S = {v in D mid P_ {T} (v) { text {und}} P_ {s} (v) }}$

Das Prädikat T. =

wird neben angewendet

als Teil des zusammengesetzten Prädikats S. definieren S.. Die beiden Prädikate sind verbundenDaher müssen beide zutreffen, damit ein Wert ausgewählt werden kann. Das Prädikat S. = T.

=

fasst das Prädikat zusammen T., damit S. <: (Untertypen) T..

Zum Beispiel: Es gibt eine Unterfamilie von Katzenarten namens Felinae, die ein Teil der Familie ist Felidae. Die Gattung Felis, zu denen die Hauskatzenart Felis catus gehört, ist Teil dieser Unterfamilie.

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

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

Die Konjunktion von Prädikaten wurde hier durch Anwendung des zweiten Prädikats auf den Wertebereich ausgedrückt, der dem ersten Prädikat entspricht. Als Typen angesehen, Felis <: Felinae <: Felidae.

Wenn T. subsumiert S. ((T:> S.) dann eine Prozedur, Funktion oder ein Ausdruck mit einem bestimmten Wert

als Operand (Eingabeargument oder Term) kann daher über diesen Wert als einer vom Typ operiert werden T., weil

. Im obigen Beispiel können wir die Funktion erwarten ofSubfamily auf Werte aller drei Typen anwendbar sein Felidae, Felinae und Felis.

Subtypisierungsschemata[edit]

Typentheoretiker unterscheiden zwischen nominelle Untertypisierung, in denen nur auf bestimmte Weise deklarierte Typen Untertypen voneinander sein dürfen, und strukturelle Subtypisierung, bei dem die Struktur zweier Typen bestimmt, ob einer ein Subtyp des anderen ist oder nicht. Die oben beschriebene klassenbasierte objektorientierte Untertypisierung ist nominal; Eine strukturelle Subtypisierungsregel für eine objektorientierte Sprache könnte sagen, dass wenn Objekte vom Typ sind EIN kann alle Nachrichten verarbeiten, die Objekte vom Typ sind B. kann damit umgehen (dh wenn sie alle die gleichen Methoden definieren), dann EIN ist ein Subtyp von B. unabhängig davon, ob einer vom anderen erbt. Dies wird so genannt Ente tippen ist in dynamisch typisierten objektorientierten Sprachen üblich. Gute strukturelle Subtypisierungsregeln für andere Typen als Objekttypen sind ebenfalls bekannt.^{[citation needed]}

Implementierungen von Programmiersprachen mit Untertypisierung fallen in zwei allgemeine Klassen: inklusive Implementierungen, bei denen die Darstellung eines beliebigen Wertes vom Typ EIN repräsentiert auch den gleichen Wert bei Typ B. wenn EIN<:B., und Zwang Implementierungen, in denen ein Wert vom Typ EIN kann sein automatisch konvertiert in einen Typ B.. Die durch Unterklassen in einer objektorientierten Sprache induzierte Untertypisierung ist normalerweise inklusive; Subtypisierungsbeziehungen, die Ganzzahlen und Gleitkommazahlen betreffen, die unterschiedlich dargestellt werden, sind normalerweise zwanghaft.

In fast allen Typsystemen, die eine Subtypisierungsbeziehung definieren, ist sie reflexiv (dh) EIN<:EIN für jeden Typ EIN) und transitiv (was bedeutet, dass wenn EIN<:B. und B.<:C. dann EIN<:C.). Dies macht es zu einer Vorbestellung für Typen.

Datensatztypen[edit]

Untertypisierung von Breite und Tiefe[edit]

Arten von Aufzeichnungen führen zu den Konzepten von Breite und Tiefe Untertypisierung. Diese drücken zwei verschiedene Möglichkeiten aus, um einen neuen Datensatztyp zu erhalten, der dieselben Vorgänge wie der ursprüngliche Datensatztyp ermöglicht.

Denken Sie daran, dass ein Datensatz eine Sammlung von (benannten) Feldern ist. Da ein Subtyp ein Typ ist, der alle für den Originaltyp zulässigen Operationen zulässt, sollte ein Datensatz-Subtyp dieselben Operationen für die Felder unterstützen wie der unterstützte Originaltyp.

Eine Art, eine solche Unterstützung zu erreichen, heißt Breite Untertypisierung, fügt dem Datensatz weitere Felder hinzu. Formal wird jedes (benannte) Feld, das im Supertyp width erscheint, im Subtyp width angezeigt. Somit wird jede Operation, die für den Supertyp möglich ist, vom Subtyp unterstützt.

Die zweite Methode heißt Tiefen-Subtypisierung, ersetzt die verschiedenen Felder durch ihre Untertypen. Das heißt, die Felder des Subtyps sind Subtypen der Felder des Supertyps. Da jede Operation, die für ein Feld im Supertyp unterstützt wird, für seinen Subtyp unterstützt wird, wird jede Operation, die für den Datensatz-Supertyp möglich ist, vom Datensatz-Subtyp unterstützt. Die Tiefenuntertypisierung ist nur für unveränderliche Datensätze sinnvoll: Sie können beispielsweise dem Feld ‘x’ eines realen Punkts (einem Datensatz mit zwei realen Feldern) 1,5 zuweisen, dem Feld ‘x’ von jedoch nicht das Gleiche ein ganzzahliger Punkt (der jedoch ein tiefer Subtyp des realen Punkttyps ist), da 1.5 keine ganze Zahl ist (siehe Varianz).

Die Untertypisierung von Datensätzen kann in System F definiert werden_<:Dies kombiniert parametrischen Polymorphismus mit der Subtypisierung von Datensatztypen und ist eine theoretische Grundlage für viele funktionale Programmiersprachen, die beide Funktionen unterstützen.

Einige Systeme unterstützen auch die Untertypisierung von markierten disjunkten Vereinigungstypen (z. B. algebraische Datentypen). Die Regel für die Breite-Untertypisierung ist umgekehrt: Jedes Tag, das im Breite-Untertyp erscheint, muss im Breite-Untertyp erscheinen.

Funktionstypen[edit]

Wenn T.₁ → T.₂ ist ein Funktionstyp, dann ist ein Subtyp davon ein beliebiger Funktionstyp S.₁ → S.₂ mit der Eigenschaft, dass T.₁ <: S.₁ und S.₂ <: T.₂. Dies kann mit der folgenden Tippregel zusammengefasst werden:

${ displaystyle T_ {1} leq: S_ {1} quad S_ {2} leq: T_ {2} über S_ {1} rightarrow S_ {2} leq: T_ {1} rightarrow T_ { 2}}$

Der Argumenttyp von S.₁ → S.₂ wird als kontravariant bezeichnet, da die Subtypisierungsbeziehung dafür umgekehrt ist, während der Rückgabetyp kovariant ist. Informell erfolgt diese Umkehrung, weil der verfeinerte Typ in den von ihm akzeptierten Typen “liberaler” und in dem zurückgegebenen Typ “konservativer” ist. Genau das funktioniert in Scala: a n-ary Funktion ist intern eine Klasse, die die erbt FunktionN (-A1, -A2,…, -An, + B) Merkmal (das als allgemeine Schnittstelle in Java-ähnlichen Sprachen angesehen werden kann), wobei A1, A2,… Ein sind die Parametertypen und B. ist der Rückgabetyp; “”– –“Bevor der Typ bedeutet, dass der Typ kontravariant ist, während”+“bedeutet kovariant.

In Sprachen, die Nebenwirkungen zulassen, wie in den meisten objektorientierten Sprachen, reicht die Subtypisierung im Allgemeinen nicht aus, um sicherzustellen, dass eine Funktion sicher im Kontext einer anderen verwendet werden kann. Liskovs Arbeit in diesem Bereich konzentrierte sich auf die Subtypisierung des Verhaltens, die neben der in diesem Artikel diskutierten Sicherheit des Typsystems auch erfordert, dass die Subtypen alle Invarianten beibehalten, die durch die Supertypen in einigen Verträgen garantiert werden.^[4] Diese Definition der Untertypisierung ist im Allgemeinen unentscheidbar und kann daher nicht von einer Typprüfung überprüft werden.

Die Untertypisierung veränderlicher Referenzen ähnelt der Behandlung von Funktionsargumenten und Rückgabewerten. Nur-Schreib-Referenzen (oder sinkt) sind kontravariante, wie Funktionsargumente; schreibgeschützte Referenzen (oder Quellen) sind kovariant wie Rückgabewerte. Veränderbare Referenzen, die sowohl als Quellen als auch als Senken fungieren, sind unveränderlich.

Beziehung zur Vererbung[edit]

Subtypisierung und Vererbung sind unabhängige (orthogonale) Beziehungen. Sie mögen zusammenfallen, aber keiner ist ein Sonderfall des anderen. Mit anderen Worten, zwischen zwei Typen S. und T.sind alle Kombinationen von Subtypisierung und Vererbung möglich:

1. S. ist weder ein Subtyp noch ein abgeleiteter Typ von T.
2. S. ist ein Subtyp, aber kein abgeleiteter Typ von T.
3. S. ist kein Subtyp, sondern ein abgeleiteter Typ von T.
4. S. ist sowohl ein Subtyp als auch ein abgeleiteter Typ von T.

Der erste Fall wird durch unabhängige Typen veranschaulicht, wie z Boolean und Float.

Der zweite Fall kann durch die Beziehung zwischen veranschaulicht werden Int32 und Int64. In den meisten objektorientierten Programmiersprachen Int64 sind durch Vererbung nicht verwandt Int32. jedoch Int32 kann als Subtyp von betrachtet werden Int64 da jeder 32-Bit-Ganzzahlwert in einen 64-Bit-Ganzzahlwert heraufgestuft werden kann.

Der dritte Fall ist eine Folge der Funktionsuntertypisierung der Eingangskontravarianz. Nehmen Sie eine Superklasse an T. eine Methode haben m Rückgabe eines Objekts des gleichen Typs (dh die Art von m ist T → T.Beachten Sie auch, dass das erste Argument von m ist dies / self) und ein abgeleiteter Klassentyp S. von T.. Durch Vererbung die Art von m im S. ist S → S.. Damit S. ein Subtyp von sein T. die Art von m im S. muss ein Subtyp des Typs von sein m im T., mit anderen Worten: S → S ≤: T → T.. Durch Bottom-up-Anwendung der Funktionsuntertypisierungsregel bedeutet dies: S ≤: T. und T ≤: S., was nur möglich ist, wenn S. und T. sind gleich. Da Vererbung eine irreflexive Beziehung ist, S. kann kein Subtyp von sein T..

Subtypisierung und Vererbung sind kompatibel, wenn alle geerbten Felder und Methoden des abgeleiteten Typs Typen haben, die Subtypen der entsprechenden Felder und Methoden des geerbten Typs sind.

Zwänge[edit]

In Zwangs-Subtypisierungssystemen werden Subtypen durch implizite Typkonvertierungsfunktionen von Subtyp zu Supertyp definiert. Für jede Subtypisierungsbeziehung (S. <: T.), eine Zwangsfunktion zwingen:: S. → T. wird zur Verfügung gestellt, und jedes Objekt s vom Typ S. wird als das Objekt angesehen zwingen_{S. → T.}((s) vom Typ T.. Eine Zwangsfunktion kann durch die Zusammensetzung definiert werden: wenn S. <: T. und T. <: U. dann s kann als ein Objekt des Typs angesehen werden u unter dem zusammengesetzten Zwang (zwingen_{T. → U.} ∘ zwingen_{S. → T.}). Der Typenzwang von einem Typ zu sich selbst zwingen_{T. → T.} ist die Identitätsfunktion Ich würde_T.

Zwangsfunktionen für Datensätze und disjunkte Vereinigungsuntertypen können komponentenweise definiert werden. Bei Datensätzen mit erweiterter Breite verwirft der Typzwang einfach alle Komponenten, die nicht im Supertyp definiert sind. Der Typenzwang für Funktionstypen kann gegeben sein durch f ‘((s) = zwingen_{S.2 → T.2}((f((zwingen_{T.1 → S.1}((t))), was die Kontravarianz von Funktionsargumenten und die Kovarianz von Rückgabewerten widerspiegelt.

Die Zwangsfunktion wird anhand des Subtyps und des Supertyps eindeutig bestimmt. Wenn also mehrere Subtypisierungsbeziehungen definiert werden, muss darauf geachtet werden, dass alle Typzwänge kohärent sind. Zum Beispiel, wenn eine Ganzzahl wie 2: int kann zu einer Gleitkommazahl gezwungen werden (z. B. 2.0: schweben), dann ist es nicht zulässig, 2.1 zu erzwingen: schweben zu 2 : int, weil der zusammengesetzte Zwang zwingen_{schweben → schweben} gegeben durch zwingen_{int → schweben} ∘ zwingen_{schweben → int} würde sich dann vom Identitätszwang unterscheiden Ich würde_schweben.

Siehe auch[edit]

Verweise[edit]

Lehrbücher

Papiere

Weiterführende Literatur[edit]