Betrachten wir nochmals die Funktion zur Umkehrung der Reihenfolge eines Feldes, das war:
fn reverse(a: &mut [i32]) {
let n = a.len();
for i in 0..n/2 {a.swap(i, n-1-i);}
}
Für jeden weiteren Element-Typ wäre diese neu zu schreiben. Hierbei stellt man jedoch fest, dass die Funktion für jeden Element-Typ die gleiche Gestalt besitzt. Es liegt auf der Hand. Wir würden die Funktion gerne für alle denkbaren Element-Typen auf einmal schreiben.
Zur Realisierung dieser Idee führt man ein neues Konzept ein. Der Element-Typ wird durch eine Typvariable ersetzt. In die so gegebene Typsignatur darf für die Typvariable dann jeder beim Aufruf vorgefundene Typ eingesetzt werden. Um Typvariablen besser von gewöhnlichen Typen unterscheiden zu können, werden diese zusätzlich in spitzen Klammern hinter den Bezeichner der Funktion gestellt.
fn reverse<T>(a: &mut [T]) {
let n = a.len();
for i in 0..n/2 {a.swap(i, n-1-i);}
}
Man spricht von einer Allquantifizierung über die
Typvariable T. Eine solche Funktion nennt man
generisch oder parametrisch polymorph.
So wie Funktionen dürfen auch andere Typen generisch sein. Betrachten wir zunächst die folgende Konstruktion eines dynamischen Stapels.
struct Node {
data: i32,
next: Option<Box<Node>>
}
struct Stack {
top: Option<Box<Node>>
}
impl Stack {
fn new() -> Self {
Stack {top: None}
}
fn push(&mut self, x: i32) {
let node = self.top.take();
self.top = Some(Box::new(Node {data: x, next: node}));
}
fn pop(&mut self) -> Option<i32> {
if let Some(node) = self.top.take() {
self.top = node.next;
Some(node.data)
} else {
None
}
}
}
Wie bei Funktionen enthält die Formulierung eine Typvariable, in die bei der Benutzung der jeweilige Element-Typ eingesetzt wird.
struct Node<T> {
data: T,
next: Option<Box<Node<T>>>
}
struct Stack<T> {
top: Option<Box<Node<T>>>
}
impl<T> Stack<T> {
fn new() -> Self {
Stack {top: None}
}
fn push(&mut self, x: T) {
let node = self.top.take();
self.top = Some(Box::new(Node {data: x, next: node}));
}
fn pop(&mut self) -> Option<T> {
if let Some(node) = self.top.take() {
self.top = node.next;
Some(node.data)
} else {
None
}
}
}
Man beachte, dass Stack und dessen Methoden
push und pop über dieselbe Typvariable
parametrisiert sind. Steht der in die Typvariable eingesetzte
Typ an einer Stelle fest, muss der gleiche Typ auch an allen
anderen Stellen für die Typvariable eingesetzt werden. Aufgrund
der Typinferenz besteht hierbei nicht immer die Notwendigkeit,
den Typ explizit anzugeben.
Nun sind auch generische Funktionen denkbar, bei denen für die Typvariable nur solche Typen einsetzbar sind, die notwendige Eigenschaften erfüllen. Betrachten wir dazu die Berechnung des Maximums eines nicht-leeren Feldes:
fn max(a: &[i32]) -> i32 {
let mut m = a[0];
for &x in a[1..].iter() {
if m < x {m = x;}
}
m
}
Auf den ganzen Zahlen ist auf natürliche Weise eine Totalordnung definiert. Wollen wir diese Funktion generisch formulieren, brauchen wir Zugriff auf die Ordnungsrelation. Die zielführende Idee dazu ist ein Funktionenzeiger auf die Ordnungsrelation.
fn max<T>(a: &[T], lt: fn(&T, &T) -> bool) -> &T {
let mut m = &a[0];
for x in a[1..].iter() {
if lt(m, x) {m = x;}
}
m
}
fn lt_i32(x: &i32, y: &i32) -> bool {
x < y
}
fn main() {
let a = [2, 4, 1, 3];
println!("{}", max(&a, lt_i32));
}
Die Benutzung von Funktionenzeigern kommt hier als unbefangener Ansatz daher, doch liegt darin ein kritischer Schritt, der das Potential der generischen Programmierung schlagartig um Größenordnungen ausweitet.
Weiterführende Überlegungen bringen die Einsicht, dass generische Funktionen durch Tabellen von Funktionenzeigern gesteuert werden, man spricht von sogenannten Dispatch-Tabellen. Wohlgemerkt darf der Compiler das Dispatching im Rahmen der Monomorphisierung bereits zur Kompilierzeit auflösen, womit die Dispatch-Tabellen zur Laufzeit verschwunden sein dürfen. Allerdings muss eine generische Funktion hierzu für jeden Typ neu kompiliert werden.
Zur Gewährleistung erhöhter Typsicherheit wollen wir nun aber haben, dass es zwischen einem Typ und seinen Eigenschaften eine feste Verbindung geben kann. Dazu wurde das Konzept der Traits in die Programmiersprache eingeführt. Ein Trait fasst analog zur Dispatch-Tabelle die Funktionen zusammen, die die generische Funktion benötigt.
In der Definition der generischen Funktion bekommt die Typvariable den benötigten Trait annotiert. Ein solcher Trait-Bound sagt aus, dass die Funktion nicht mehr über alle möglichen Typen parametrisiert ist, sondern nur noch über solche, die diese Eigenschaft erfüllen. Anders ausgedrückt ist die Allquantifizierung der Typvariable durch den Trait-Bound beschränkt.
Der Trait Ord stellt die Totalordnung dar.
Für Ganzzahltypen wie i32 ist dieser bereits durch die
Standardbibliothek implementiert. Damit dürfen wir formulieren:
fn max<T: Ord>(a: &[T]) -> &T {
let mut m = &a[0];
for x in a[1..].iter() {
if m < x {m = x;}
}
m
}
Wir können auch die gesamte Funktionalität nachbauen. Das geht so:
trait Ord {
fn lt(x: &Self, y: &Self) -> bool;
}
impl Ord for i32 {
fn lt(x: &i32, y: &i32) -> bool {x<y}
}
fn max<T: Ord>(a: &[T]) -> &T {
let mut m = &a[0];
for x in a[1..].iter() {
if Ord::lt(m, x) {m = x;}
}
m
}
Der eigentlichen Definition, wie sie in der Standardbibliothek auftritt, kommt die folgende Formulierung näher.
enum Ordering {
Less, Equal, Greater
}
trait Ord {
fn cmp(&self, other: &Self) -> Ordering;
fn lt(&self, other: &Self) -> bool {
matches!(Ord::cmp(self, other), Ordering::Less)
}
}
impl Ord for i32 {
fn cmp(&self, other: &i32) -> Ordering {
if self < other {Ordering::Less}
else if self == other {Ordering::Equal}
else {Ordering::Greater}
}
}
fn max<T: Ord>(a: &[T]) -> &T {
let mut m = &a[0];
for x in a[1..].iter() {
if m.lt(x) {m = x;}
}
m
}
Eine kurze Bemerkung noch. Zur Notation von Trait-Schranken darf man alternativ eine wobei-Klausel schreiben. Die Signatur
fn max<T: Ord>(a: &[T]) -> &T
ist äquivalent zu:
fn max<T>(a: &[T]) -> &T where T: Ord
Solche wobei-Klauseln bieten sich an, wenn die Signatur mehrere Typparameter und Trait-Schranken enthält, und man dabei Übersichtlichkeit wahren will. Wir werden darüber hinaus später auf Signaturen stoßen, bei denen die Benutzung der wobei-Klausel obligatorisch ist.
Nun verhält es sich so, dass Traits selbst Typparameter enthalten können. Wozu das nützlich ist, will ich am folgenden Beispiel erklären. Vorzulegen sei ein Trait, dessen Methode die Reihenfolge der Elemente eines sequentiellen Typs umdreht. Man könnte diesen Trait so formulieren:
trait Rev {
fn rev(self) -> Self;
}
impl Rev for [i32; 2] {
fn rev(self) -> Self {[self[1], self[0]]}
}
fn main() {
let a = [1, 2];
println!("{:?}", a.rev());
}
Soweit mag das in Ordnung sein. Gleichwohl stoßen wir umgehend auf eine Komplikation. Nämlich ist der Trait nicht für Leihgaben implementierbar, da die Rückgabe aufgrund der Signatur ebenfalls eine Leihgabe sein muss. Die Lebenszeit des erzeugten Wertes, zu welchem diese Leihgabe bestehen soll, wäre über die Funktion hinaus auszudehnen, was nicht machbar ist. Das heißt, wir würden gerne haben:
impl Rev for &[i32; 2] {
fn rev(self) -> Self {&[self[1], self[0]]}
}
Diese Funktion ist jedoch nicht kompilierbar. Stattdessen bedarf es einer Besitzübertragung des erzeugten Wertes von der aufgerufenen an die aufrufende Funktion. Dafür müssen wir zwangsläufig die Signatur ändern. Erreichbar ist dies durch Parametrisierung des Traits über den Rückgabetyp:
trait Rev<Return> {
fn rev(self) -> Return;
}
impl Rev<[i32; 2]> for &[i32; 2] {
fn rev(self) -> [i32; 2] {[self[1], self[0]]}
}
fn main() {
let a = &[1, 2];
println!("{:?}", &a.rev());
}
Nun gestattet die Parametrisierung das Hinzufügen einer jeweiligen Implementierung zu weiteren Rückgabetypen. Bspw. darf man hinzufügen:
impl Rev<(i32, i32)> for &[i32; 2] {
fn rev(self) -> (i32, i32) {(self[1], self[0])}
}
Der Aufruf braucht infolge allerdings die qualifizierte
Angabe der Methode, da nicht mehr eindeutig abgeleitet werden kann,
mit welchem Typ Return zu belegen ist. Das heißt, man
muss den Aufruf a.rev() gegen
Rev::<[i32; 2]>::rev(a) ersetzen.
Auf der anderen Seite möchte man unter Umständen die Beschränkung
haben, dass dem sequentiellen Typ genau ein Typ Return
zugeordnet ist. Um diese Beschränkung zum Ausdruck bringen zu können,
wurde das Konzept der assoziierten Typen in die
Programmiersprache eingebracht. Zur Angabe des assoziierten Typs wird
der Typparameter in den Trait geschoben und dort mit dem Schlüsselwort
type eingeleitet.
trait Rev {
type Return;
fn rev(self) -> Self::Return;
}
impl Rev for &[i32; 2] {
type Return = [i32; 2];
fn rev(self) -> [i32; 2] {[self[1], self[0]]}
}
fn main() {
let a = &[1, 2];
println!("{:?}", &a.rev());
}
Der aufgezeigte Weg verdeutlicht die Entbehrlichkeit assoziierter Typen bezüglich dieser Art von Problemstellung. Sie dienen zur Klarstellung der eindeutigen Zuordnung, bringen abseits dieser Verschärfung aber zunächst keine neue Funktionalität.
Aufgrund der eindeutigen Zuordnung kann man allerdings des Weiteren
zu jedem Typ die assoziierten Typen erhalten, was bei der Schaffung
fortgeschrittener generischer Konstruktionen dienlich ist. Ist
Rev für einen Typ X mit
Return = Y implementiert, gilt
Y = <X as Rev>::Return.
Eine Funktion zur elementweisen Addition zweier Arrays lässt sich ohne Schwierigkeiten umsetzen:
fn add(a: &[i32], b: &[i32]) -> Vec<i32> {
let mut acc: Vec<i32> = Vec::with_capacity(a.len());
for i in 0..a.len() {
acc.push(a[i] + b[i]);
}
acc
}
fn main() {
let a = vec![1, 2, 3, 4];
println!("{:?}", add(&a, &a));
}
Die Elemente haben hier nun allerdings 32 Bit große Ganzzahlen
als festen Datentyp. Man spricht von einer monomorphen
Typisierung. Die Funktion würde aber auch für andere Datentypen
wie f64 einen Sinn ergeben. Man könnte nun auf die Idee
kommen, die Funktion für die gewünschten Datentypen nochmals zu
implementieren. Es kann doch aber sein, dass die Anzahl der Datentypen
sehr groß oder nicht von vornherein bekannt ist.
Die Lösung dieses Problems besteht in der polymorphen Umsetzung der Funktion. Hierbei abstrahiert man das wiederkehrende Muster von den konkreten Datentypen. Nun stellt sich dabei aber die Frage, wie sich dies am besten bewerkstelligen lässt. Der Compiler weiß ja bisher nur wie er monomorphe Funktionen kompilieren muss.
Zunächst müssen wir Klarheit darüber bekommen, was die Polymorphie für die Funktion bedeutet. Was ändert sich an der Funktion für unterschiedliche Datentypen und was bleibt gleich? Ändern muss man die Addition, und dann auch noch die Operationen zum Verschieben der Zahlen im Speicher, denn diese sind ja von der Speichergröße des Datentyps abhängig. Nimmt man etwas Abstand, dann sieht man ein, dass Veränderungen nur überall dort zwangsweise vorkommen müssen, wo Operationen von den unterschiedlichen Eigenschaften der Datentypen abhängig sind.
Die Funktion sollte aber auch möglichst wenig über die Datentypen
wissen. Eigentlich muss die Funktion nur darüber Bescheid wissen,
dass für den gewünschten Datentyp die Addition definiert ist.
Datentypen mit dieser Eigenschaft fassen wir zu einer
Typklasse Add zusammen.
Die Funktion kann man nun polymorph mit einer gebundenen
Typvariable schreiben, die man nennen kann wie man möchte.
Nennen wir sie T. Die Funktion ließe sich dann
so formulieren:
fn add<T: Add>(a: &[T], b: &[T]) -> Vec<T> {
...
}
Die vollständige Angabe ist in Rust die folgende:
use std::ops::Add;
fn add<T: Copy + Add<Output = T>>(a: &[T], b: &[T]) -> Vec<T> {
let mut acc: Vec<T> = Vec::with_capacity(a.len());
for i in 0..a.len() {
acc.push(a[i] + b[i]);
}
acc
}
In Rust wird eine Typklasse als Trait bezeichnet. Jeder Trait macht bestimmte Aussagen über die Eigenschaften eines Datentyps. Daher entstammt auch die Bezeichnung Trait.
Was fängt der Compiler nun damit an? Nun ja, das ist nicht schwer
zu verstehen. Der Compiler prüft bei der Anwendung der Funktion einfach,
ob der dortige Datentyp in den Typklassen Add und
Copy liegt, entnimmt dann die somit bekannten
Eigenschaften des Datentyps und ist damit befähigt, die unbekannten
Operationen gegen ihre konkreten zu ersetzen. Dieser Prozess wird als
Monomorphisierung bezeichnet.
Man kann sich die polymorphe Funktion auch als Schablone vorstellen,
in der für die Typvariable T der gewünschte Datentyp
eingesetzt wird. Danach liegt die Funktion ja in monomorpher Form vor,
so dass sie auf ganz gewöhnliche Art vom Compiler kompiliert werden
kann.
Die bisherige Umsetzung von Polymorphie enthält noch einen kleinen Schönheitsfehler. Angenommen, die Datentypen sind zahlreich und die Implementation ist relativ groß, dann ist das Programm im Quelltext zwar polymorph, bei der Monomorphisierung bläht es sich jedoch in ein großes Maschinenprogramm auf. Außerdem kann ja auch die Situation bestehen, dass Datentypen nicht im Vorhinein bekannt sind. Dies führt dazu, dass die Funktionen über die Programm-Bibliothek hinaus polymorph vorliegen müssen und bei der Anwendung jeweils monomorphisiert werden. Zwar erlaubt die Monomorphisierung viele Optimierungen, jedoch führt dies auch zu langen Kompilierzeiten, da separate Kompilation höchstens teilweise möglich ist.
Die alternative Umsetzung ist eine ganz einfache Überlegung: Wir halten die Funktion einfach polymorph. Was muss man dafür genau tun? Nun, es gibt diese Operationen die von den Eigenschaften des Argument-Datentyps abhängig sind. Wenn die Funktion denn zur Laufzeit polymorph vorliegen soll, dann muss auf diese Operationen über Funktionenzeiger zugegriffen werden. Der Funktionenzeiger muss zur Laufzeit irgendwie an die Funktion übergeben werden. Dies lässt sich günstig bewerkstelligen, indem die Funktionenzeiger in einer Tabelle gespeichert werden, welche mit an die Funktion übergeben wird. Solche Tabellen werden als dispatch tables oder virtual method tables bezeichnet.
Beim Dispatch gibt es nun zwei Ansätze. Der erste Ansatz ist der homogene Dispatch. Hierbei werden zusätzlich Informationen über die Speichergröße gespeichert um einfache Kopien und Verschiebungen zu gestatten. Der zweite Ansatz ist der heterogene Dispatch. Hierbei findet eine Indirektion der Daten über einen Zeiger statt. Heterogener Dispatch bietet den Vorteil, dass er flexibler ist, indem er Daten von wechselndem Datentyp ermöglicht. Zum Beispiel lässt sich damit ein Array formulieren, in welchem jedes Element von einem anderen Datentyp ist.
Die Umsetzung von automatischem homogenen Dispatch gilt im Zusammenspiel mit dem Monomorphisierungs-System als schwierig. Um sich hier aus der Affäre zu ziehen, entschied man sich für kontrollierten heterogenen Dispatch. Hierzu wird in Rust ein Wert als Zeigerpaar gespeichert, wobei der erste Zeiger auf die Daten zeigt, und der zweite Zeiger auf die Dispatch-Tabelle. Für solche Zeigerpaare ist auch die Sprechweise fat pointer (engl. dicker Zeiger) geläufig.
Der kontrollierte Dispatch manifestiert sich nun aber auch im Typsystem. Die polymorphe Funktion soll ja eine feste Schnittstelle besitzen, auf die man zur Laufzeit zugreifen kann. Da diese Schnittstelle nicht automatisiert erzeugt wird, muss man sich darum kümmern wie diese aussehen soll. Dafür braucht man zwar nicht bis auf die Binärschnittstelle runtergehen, das sollte der Compiler schon erledigen, allerdings müssen wir in der Schnittstelle eine monomorphe Typisierung vorgaukeln.
Gegeben ist also zunächst die polymorphe Typisierung, wobei
die Typvariable in einer angegebenen Typklasse liegt. Gebraucht wird
aber ein monomorpher Typ, der diese Typklasse zur Laufzeit umsetzt.
Diese Abbildung erlaubt der Operator dyn, welcher
nur in Verbindung mit einem Zeigertyp vorkommt, also als
Pointer<dyn Trait> angeben wird. Werte dieses
Typs werden in Rust zuweilen auch als Trait-Objekte bezeichnet.
Speziell sind das z. B. Box<dyn Trait>
und Rc<dyn Trait>, außerdem auch
&dyn Trait und &mut dyn Trait.
Betrachten wir z. B. eine polymorphe Funktion zur Umkehrung der Reihenfolge eines Arrays:
fn reverse<T>(a: &mut [T]){
let n = a.len();
for i in 0..n/2 {a.swap(i, n-1-i);}
}
fn main(){
let mut a: Vec<i32> = vec![1, 2, 3, 4];
reverse(&mut a);
println!("{:?}", a);
}
Die Typvariable der Funktion reverse ist nicht
durch Traits eingeschränkt. Der Trait Any ermöglicht
eine Laufzeitdarstellung dieses Umstandes. Es folgt die
Laufzeit-polymorphe Implementation:
use std::any::Any;
fn reverse(a: &mut [&dyn Any]) {
let n = a.len();
for i in 0..n/2 {
a.swap(i, n-1-i);
}
}
fn downcast(a: &[&dyn Any]) -> Vec<i32> {
a.iter().map(|x| *(*x).downcast_ref::<i32>().unwrap()).collect()
}
fn main() {
let mut a: Vec<&dyn Any> = vec![&1, &2, &3, &4];
reverse(&mut a);
println!("{:?}", downcast(&a));
}
Der hierbei vorkommende Downcast ist allerdings kein gutes Zeichen.
Downcasts entstehen dadurch, dass der durch dyn
erzeugte Type erasure rückgängig gemacht werden muss. Hierbei kann
man aber Fehler machen, da Type erasure maßgeblich einen Teil der
Typisierung entfernt. Und bei Any ist das nicht nur
ein Teil, sondern die gesamte Typisierung. Downcasts laufen also
der Sicherheit zuwider, die uns das Typsystem eigentlich bieten soll.
Zur Umgehung dieses Problems kann man sämtliche von dem polymorphen Code abhängige Programmteile selbst polymorph gestalten:
use std::fmt::{Display, Debug};
trait Object: Display + Debug {}
impl<T: Display + Debug> Object for T {}
fn reverse(a: &mut [&dyn Object]) {
let n = a.len();
for i in 0..n/2 {
a.swap(i, n-1-i);
}
}
fn main() {
let mut a: Vec<&dyn Object> = vec![&1, &2, &3, &4];
reverse(&mut a);
println!("{:?}", a);
}
Der missliebige Downcast ist nun verschwunden.
Betrachten wir einmal den folgenden Algorithmus zur Berechnung von Potenzen mit natürlichem Exponenten.
fn pow(x: i32, n: u32) -> i32 {
let mut acc = 1;
for _ in 0..n {acc = acc*x;}
acc
}
fn main() {
println!("{}", pow(2,10));
}
Eigentlich ist diese Berechnung für jede Verknüpfung möglich, die mit dem zugrundeliegenden Definitionsbereich ein Monoid bildet. Das Monoid lässt sich als ein Trait darstellen, welcher das neutrale Element (auch »Einselement« genannt) und die multiplikativ geschriebene Verknüpfung enthält. Der abstrakte Algorithmus nimmt dann die folgende Gestalt an:
trait Monoid {
fn one() -> Self;
fn mul(&self, x: &Self) -> Self;
}
fn pow<T: Monoid>(x: T, n: u32) -> T {
let mut acc = T::one();
for _ in 0..n {acc = acc.mul(&x);}
acc
}
impl Monoid for i32 {
fn one() -> Self {1}
fn mul(&self, x: &Self) -> Self {self*x}
}
Nun ist der Compiler bisher (Stand Mai 2020) leider nicht zur Erzeugung eines Laufzeit-polymorphen Maschinenprogramms in der Lage. Die notwendigen Mittel zur Beschreibung dessen, was wir gerne haben wollten, bietet Rust allerdings schon.
Zunächst müssen wir hier zur Einsicht kommen, dass
Monoid für dyn unzugänglich ist.
Man sagt, Monoid sei nicht object safe.
Der Grund dafür liegt im expliziten Vorkommen von Self.
Die Aufgabe von dyn ist ja nämlich Type erasure, und da
darf dann der Typ nicht mehr explizit vorkommen, sonst ergibt das
nicht so richtig einen Sinn.
Eigentlich, so ist es am Algorithmus ersichtlich, wollen wir
die Dispatch-Tabelle auch nicht fest an das Objekt binden, sondern
in einer Variable speichern, welche den Platz der Typvariable
T einnimmt. Zur Erreichung von Polymorphie muss das
Maschinenprogramm auch die konkreten Eigenschaften des Typs vergessen
haben. Ein sicheres Mittel zur Bewerkstelligung dieser Forderung
ist dyn Any.
Zunächst die Struktur der Dispatch-Tabelle:
struct MonoidPtr(Box<dyn std::any::Any>);
struct MonoidType {
one: &'static dyn Fn() -> MonoidPtr,
mul: &'static dyn Fn(&MonoidPtr,&MonoidPtr) -> MonoidPtr
}
Die Dispatch-Tabelle nun für Monoid implementieren:
fn type_monoid<T: Monoid + 'static>() -> MonoidType {
let one = &|| -> MonoidPtr {MonoidPtr(Box::new(T::one()))};
let mul = &|a: &MonoidPtr, b: &MonoidPtr| -> MonoidPtr {
if let Some(a) = a.0.downcast_ref::<T>() {
if let Some(b) = b.0.downcast_ref::<T>() {
return MonoidPtr(Box::new(a.mul(b)));
}
}
unreachable!();
};
MonoidType {one, mul}
}
Nun der explizit Laufzeit-polymorphe Algorithmus:
fn pow_intern(t: &MonoidType, x: &MonoidPtr, n: u32) -> MonoidPtr {
let mut acc = (t.one)();
for _ in 0..n {acc = (t.mul)(&acc, &x);}
acc
}
Schließlich noch eine typsichere Einhüllung des Algorithmus:
fn pow<T: Monoid + 'static>(x: T, n: u32) -> T {
let t = type_monoid::<T>();
let px = MonoidPtr(Box::new(x));
match pow_intern(&t, &px, n).0.downcast::<T>() {
Ok(y) => *y,
_ => unreachable!()
}
}
Pedantische Leser mögen nun noch fragen, was es mit dem
Trait-Bound 'static auf sich hat. Dieser schließt
Lifetime-Variablen aus und ermöglicht dadurch die Benutzung von
Any. Es verhält sich nämlich so, dass Any für
jeden Datentyp eine Typ-Identifikation bekommt, bzw. bekommen muss,
diese jedoch für Lifetimes nicht erzeugt werden kann.
Letztendlich haben wir nun echte Laufzeit-Polymorphie, mussten dafür aber das Typsystem kaputtbrechen. Dies hat wieder den faulen Beigeschmack, dass der Compiler für die interne Implementation keine vollständige Typprüfung mehr durchführen kann und bei den Downcasts unnötige if-Anweisungen entstehen.
Beim Schreiben generischer Programme tut sich oft das Problem des
Code Bloats auf. Das soll am Beispiel von Vec, dem
Datentyp dynamischer Felder, verdeutlicht werden. Weil der Compiler
bei der Monomorphisierung von Vec für unterschiedliche
Typen A, B, C
jeweils neuen optimierten Programmcode zu Vec<A>,
Vec<B>, Vec<C>
erzeugt, können generische Programme zu großen Binärdateien führen.
Allerdings muss dies nicht bei jeder Funktionalität zwangsläufig geschehen. Sind die Funktionen recht kurz, könnte durch die inline-Optimierungen nach der Monomorphisierung sogar kürzerer Maschinencode entstehen, oder moderat aufgeblähter, aber dafür hocheffizienter Maschinencode.
Zur Lösung des Problems bieten sich vier Ansätze an:
str::ptr::copy, eventuell mit
ein paar Spezialisierungen zur Optimierung.
str::ptr::copy
verwendet und erkennt dabei, dass Funktionen wiederverwendet werden
können.
Davon wollen wir uns auf 1. beschränken.
Zunächst ist denkbar, dass der Compiler schon bei
Vec<Box<T>> für unterschiedliche Typen
T bei der Monomorphisierung die gleichen Funktionen
erzeugt und wiederverwendet. Ein guter Compiler sollte das auf jeden
Fall bewerkstelligen. Um das zu erzwingen, können aber Trait-Pointer
Box<dyn A> desselben Traits A benutzt
werden. Oder aber man verwendet Box<dyn Any>.
Wir wollen den allgemeinen Ansatz mit Box<dyn Any>
verfolgen. Rust bietet uns nun die Mittel, um den polymorphen Code
in ein monomorphisiertes Interface einzuhüllen. Das gestaltet sich wie
folgt:
pub mod polyvec {
use std::any::Any;
use std::marker::PhantomData;
pub struct PolyVec<T> {
v: Vec<Box<dyn Any>>,
_marker: PhantomData<T>
}
impl<T: 'static> PolyVec<T> {
pub fn new() -> Self {
Self {v: Vec::new(), _marker: PhantomData}
}
pub fn push(&mut self, x: T) {
self.v.push(Box::new(x));
}
pub fn pop(&mut self) -> Option<T> {
match self.v.pop() {
None => None,
Some(x) => {
if let Ok(x) = x.downcast::<T>() {
Some(*x)
} else {
unreachable!()
}
}
}
}
}
}
use polyvec::PolyVec;
struct LargeChunk {}
fn main() {
let mut v: PolyVec<LargeChunk> = PolyVec::new();
v.push(LargeChunk {});
v.push(LargeChunk {});
}
Interessant ist, dass PolyVec eine Teilmenge
der Operationen von Vec unterstützt und dabei nicht
von Vec zu unterscheiden ist.
Um diesen Umstand auszunutzen, können wir einen abstrakten Datentyp
als Typalias formulieren:
type VecADT = Vec; // type VecADT = PolyVec;
Aber Vorsicht: hierbei handelt es sich nicht um einen echten abstrakten Datentyp, sondern um eine Typvariable.
Man kann nun zu jeder Zeit zwischen Vec
und PolyVec umschalten, um zu sehen wie sich
die Speichergröße der erzeugten Binärdatei verändert.
Da PolyVec mit Box Indirektionen und
zusätzliche Speicherallokationen erzeugt, ist dieser Container natürlich
nicht für laufzeitkritische Unterprogramme geeignet. Wie immer gilt,
dass zur Entscheidungsfindung konkrete Messungen hilfreich sein können.