Polymorphie und Generika

Polymorphie ermöglicht es einem einzelnen Codeabschnitt, einheitlich über viele Typen hinweg zu operieren, wobei parametrische Polymorphie (Generika), Ad-hoc-Polymorphie (Überladung und Typklassen) und Subtyp-Polymorphie ihre Hauptformen sind.

Definition

Polymorphie ist die Eigenschaft, durch die eine einzelne Funktion, ein Typ oder eine Operation auf Werte mehrerer Typen angewendet werden kann; parametrische Polymorphie tut dies einheitlich über Typparameter (Generika), während Ad-hoc-Polymorphie auf typspezifische Implementierungen verzweigt.

Scope

Dieses Thema behandelt die wichtigsten Arten der Polymorphie: parametrische Polymorphie, realisiert durch Generika und System F, Ad-hoc-Polymorphie über Überladung und Typklassen sowie Inklusions- (Subtyp-) Polymorphie. Es befasst sich mit Parametrizität und den starken Schlussfolgerungsprinzipien, die sie liefert, sowie damit, wie generische Abstraktionen kompiliert und eingeschränkt werden.

Core questions

• Wie ermöglichen Generika Wiederverwendung, ohne die Typsicherheit zu opfern?
• Was ist Parametrizität und welche Garantien bietet sie „kostenlos“?
• Wie systematisieren Typklassen die Ad-hoc-Überladung?
• Wie werden generische Definitionen kompiliert und welche Einschränkungen können Typparameter binden?

Key theories

Parametrizität (Abstraktionstheorem)

Reynolds' Abstraktionstheorem zeigt, dass parametrisch polymorphe Funktionen sich über Typen hinweg einheitlich verhalten, eine Eigenschaft, die ihr mögliches Verhalten unabhängig von der konkreten Typinstanziierung einschränkt.

„Theorems for free“ (Freie Theoreme)

Wadler zeigte, dass der Typ einer parametrisch polymorphen Funktion allein „freie Theoreme“ über ihr Verhalten impliziert, eine direkte und praktische Konsequenz der Parametrizität.

Typklassen für prinzipielle Überladung

Wadler und Blott führten Typklassen ein, die der Ad-hoc-Polymorphie eine kohärente typentheoretische Grundlage gaben, bei der überladene Operationen durch die Übergabe impliziter Dictionaries von Methodenimplementierungen aufgelöst werden.

Clinical relevance

Generika und Polymorphie sind zentral für das Design wiederverwendbarer Bibliotheken und Sammlungs-Frameworks in modernen Sprachen. Typklassen und ihre Analoga (Traits, Konzepte, Protokolle) bieten eine prinzipielle, typsichere Überladung, während Parametrizität die Korrektheitsprüfung und Compiler-Optimierungen unterstützt.

History

System F, das die parametrische Polymorphie erfasst, wurde in den frühen 1970er Jahren unabhängig voneinander von Girard und Reynolds entdeckt. ML brachte Polymorphie mit Inferenz in die Praxis. Cardelli und Wegners Übersicht von 1985 klassifizierte die Formen der Polymorphie, Reynolds formalisierte die Parametrizität 1983, und Wadler und Blotts Typklassen von 1989 prägten die Überladung in Haskell und beeinflussten Traits und Konzepte anderswo.

Debates

Erasure versus reifizierte Generika

Sprachimplementierer debattieren die Kompilierung von Generika durch Typ-Erasure, was einfach ist, aber Laufzeit-Typinformationen verliert, versus die Reifizierung von Typparametern zur Laufzeit, was Introspektion ermöglicht, aber Kosten in Komplexität und Codeumfang verursacht.

Key figures

• John Reynolds
• Jean-Yves Girard
• Philip Wadler
• Luca Cardelli
• Robin Milner

Seminal works

• reynolds1983
• wadler1989free
• wadler1989
• cardelli1985

Frequently asked questions

Was ist der Unterschied zwischen parametrischer und Ad-hoc-Polymorphie?

Parametrische Polymorphie wendet eine einheitliche Implementierung auf alle Typargumente an (wie bei Generika), während Ad-hoc-Polymorphie eine typspezifische Implementierung auswählt, wie bei Überladung oder Typklassen.

Was gibt uns die Parametrizität?

Parametrizität garantiert, dass eine generische Funktion alle Typinstanzen einheitlich behandelt, was „freie Theoreme“ über ihr Verhalten liefert, die allein aus ihrer Typsignatur ableitbar sind.