Parametrischer Polymorphismus vs. Ad-hoc-Polymorphismus

Ich würde gerne den Hauptunterschied zwischen parametrischem Polymorphismus wie Polymorphismus generischer Klassen/Funktionen in den Sprachen Java/Scala/C++ und “Ad-hoc”-Polymorphismus im Haskell-Typsystem verstehen. Ich bin mit der ersten Art von Sprachen vertraut, aber ich habe noch nie mit Haskell gearbeitet.

Etwas präziser:

1. Wie unterscheidet sich der Typinferenzalgorithmus zB in Java von der Typinferenz in Haskell?
2. Geben Sie mir bitte ein Beispiel für die Situation, in der etwas in Java/Scala geschrieben werden kann, aber nicht in Haskell (auch gemäß den modularen Merkmalen dieser Plattformen) und umgekehrt.

Danke im Voraus.

Gemäß der TAPL§23.2:

Parametrischer Polymorphismus (…) ermöglicht es, ein einzelnes Stück Code „generisch“ zu typisieren, indem Variablen anstelle von tatsächlichen Typen verwendet und dann bei Bedarf mit bestimmten Typen instanziiert werden. Parametrische Definitionen sind einheitlich: Alle ihre Instanzen verhalten sich gleich. (…)

Im Gegensatz dazu ermöglicht Ad-hoc-Polymorphismus, dass ein polymorpher Wert unterschiedliche Verhaltensweisen zeigt, wenn er bei verschiedenen Typen „betrachtet“ wird. Das häufigste Beispiel für Ad-hoc-Polymorphismus ist das Überladen, das ein einzelnes Funktionssymbol mit vielen Implementierungen verknüpft; Der Compiler (oder das Laufzeitsystem, je nachdem, ob die Überladungsauflösung statisch oder dynamisch ist) wählt basierend auf den Typen der Argumente eine geeignete Implementierung für jede Anwendung der Funktion aus.

Wenn Sie also aufeinanderfolgende Phasen der Geschichte betrachten, ist nicht generisches offizielles Java (auch bekannt als Pre-J2SE 5.0, vor. Sept. 2004) hatte Ad-hoc-Polymorphismus – also konnte man eine Methode überladen – aber kein parametrischer Polymorphismus, also konnten Sie nicht Schreiben Sie eine generische Methode. Danach kann man natürlich beides machen.

Zum Vergleich: Seit den Anfängen in 1990Haskell war parametrisch polymorph, was bedeutet, dass Sie schreiben könnten:

swap :: (A; B) -> (B; A)
swap (x; y) = (y; x)

wobei A und B Typvariablen sind, die instanziiert werden können alle Typen, ohne Annahmen.

Aber es gab kein vorbestehendes Konstruktgeben ad hoc Polymorphismus, mit dem Sie Funktionen schreiben können, die gelten für mehrereaber nicht alle Typen. Um dieses Ziel zu erreichen, wurden Typenklassen implementiert.

Sie lassen Sie beschreiben a Klasse (so etwas wie eine Java-Schnittstelle), wobei die Signatur eingeben der Funktionen, die Sie für Ihren generischen Typ implementieren möchten. Dann können Sie einige registrieren (und hoffentlich mehrere) Instanzen passend zu dieser Klasse. In der Zwischenzeit können Sie eine generische Methode schreiben, wie zum Beispiel:

between :: (Ord a)  a -> a -> a -> Bool
between x y z = x ≤ y ^ y ≤ z

bei dem die Ord ist die Klasse, die die Funktion definiert (_ ≤ _). Wenn benutzt, (between "abc" "d" "ghi") ist statisch aufgelöst rechts auszuwählen Beispiel für Strings (statt zB Integer) – genau in dem Moment, in dem (Java’s) Methode überladen würde.

Sie können etwas Ähnliches in Java mit tun begrenzte Wildcards. Aber die Der Hauptunterschied zwischen Haskell und Java an dieser Front besteht darin, dass nur Haskell die Wörterbuchübergabe automatisch durchführen kann: in beiden Sprachen, gegeben zwei Instanzen von Ord Tsagen b0 und b1können Sie eine Funktion erstellen f das nimmt diese als Argumente und erzeugt die Instanz für den Paartyp (b0, b1), indem Sie beispielsweise die lexikografische Reihenfolge verwenden. Sagen Sie jetzt, dass Sie gegeben sind (("hello", 2), ((3, "hi"), 5)). In Java müssen Sie sich die Instanzen für merken string und intund übergeben Sie die richtige Instanz (bestehend aus vier Anwendungen von f!) Um sich zu bewerben between zu diesem Objekt. Haskell kann sich bewerben Kompositionalitätund finden Sie heraus, wie Sie die richtige Instanz erstellen, wenn Sie nur die Bodeninstanzen und die angeben f Konstruktor (dies gilt natürlich auch für andere Konstruktoren) .

Nun, soweit Typ Inferenz geht (und das sollte wahrscheinlich eine eigene Frage sein), für beide Sprachen ist es unvollständigin dem Sinne, dass Sie immer an schreiben können unkommentiert Programm, dessen Typ der Compiler nicht bestimmen kann.

1. für Haskell liegt dies daran, dass dies der Fall ist unprädikativ (auch bekannt als erstklassiger) Polymorphismus, für den die Typinferenz unentscheidbar ist. Beachten Sie, dass Java in diesem Punkt auf Polymorphismus erster Ordnung beschränkt ist (etwas, das Scala erweitert).

2. für Java liegt dies daran, dass es unterstützt kontravariante Subtypisierung.

Aber diese Sprachen unterscheiden sich hauptsächlich in der Bereich von Programmanweisungen, für die Typrückschluss gilt in der Praxis und in der Wert auf Korrektheit gelegt der Ergebnisse der Typinferenz.

1. Für Haskell gilt die Inferenz für alle „nicht hochgradig polymorphen“ Begriffe und bemüht sich ernsthaft, solide Ergebnisse basierend auf veröffentlichten Erweiterungen eines bekannten Algorithmus zurückzugeben:

   • Im Kern basiert die Schlussfolgerung von Haskell auf Hindley-Milnerdie Ihnen vollständige Ergebnisse liefert, sobald Sie auf die Art einer Anwendung schließen, Variablen eingeben (zB die A und B im obigen Beispiel) kann nur mit instanziiert werden nicht polymorph Typen (ich vereinfache, aber das ist im Wesentlichen der Polymorphismus im ML-Stil, den Sie zB in Ocaml finden können.).
   • ein aktuelles GHC stellt sicher, dass eine Typanmerkung erforderlich sein kann nur für eine let-Bindung oder λ-Abstraktion, die einen Nicht-Damas-Milner-Typ hat.
   • Haskell hat versucht, selbst in seinen haarigsten Erweiterungen (z GADTs). Auf jeden Fall kommen vorgeschlagene Erweiterungen fast immer in einem Papier mit einem Beweis der Richtigkeit der erweiterten Typinferenz .

2. Für Java gilt Typrückschluss in a viel begrenztere Mode ohnehin :

   Vor der Veröffentlichung von Java 5 gab es in Java keinen Typrückschluss. Gemäß der Java-Sprachkultur Der Typ jeder Variablen, Methode und jedes dynamisch zugewiesenen Objekts muss vom Programmierer explizit deklariert werden. Als Generika (nach Typ parametrisierte Klassen und Methoden) in Java 5 eingeführt wurden, Die Sprache behielt diese Anforderung für Variablen, Methoden und Zuweisungen bei. Aber die Einführung polymorpher Methoden (parametrisiert nach Typ) diktierte, dass entweder (i) der Programmierer die Methodentypargumente an jeder polymorphen Methodenaufrufstelle bereitstellt oder (ii) die Sprache die Inferenz von Methodentypargumenten unterstützt. Um eine zusätzliche Bürolast für Programmierer zu vermeiden, haben sich die Designer von Java 5 dafür entschieden, eine Typinferenz durchzuführen, um die Typargumente zu bestimmen für polymorphe Methodenaufrufe. (QuelleHervorhebung von mir)

   Das Inferenzalgorithmus Ist im Wesentlichen die von GJaber mit einem etwas klumpig Hinzufügung von Platzhaltern als nachträglicher Einfall (Beachten Sie, dass ich nicht auf dem neuesten Stand der möglichen Korrekturen bin, die in J2SE 6.0 vorgenommen wurden). Der große konzeptionelle Unterschied im Ansatz besteht darin, dass die Schlussfolgerung von Java ist lokalin dem Sinne, dass der abgeleitete Typ eines Ausdrucks nur von Einschränkungen abhängt, die aus dem Typsystem und den Typen seiner Unterausdrücke generiert werden, aber nicht vom Kontext.

   Beachten Sie, dass die Parteilinie in Bezug auf die unvollständige und manchmal falsche Typinferenz relativ entspannt ist. Gem die spez:

   Beachten Sie auch, dass die Typinferenz die Korrektheit in keiner Weise beeinflusst. Wenn die abgeleiteten Typen unsinnig sind, ergibt der Aufruf einen Typfehler. Der Typinferenzalgorithmus sollte als Heuristik angesehen werden, die in der Praxis gut funktionieren soll. Wenn das gewünschte Ergebnis nicht abgeleitet werden kann, können stattdessen explizite Typparameter verwendet werden.

Parametrischer Polymorphismus Das heißt, wir kümmern uns nicht um den Typ, wir implementieren die Funktion für jeden Typ gleich. Zum Beispiel in Haskell:

length :: [a] -> Int
length [] = 0          
length (x:xs) = 1 + length xs

Wir kümmern uns nicht um den Typ der Elemente der Liste, wir kümmern uns nur darum, wie viele es sind.

Ad-hoc-Polymorphismus (auch bekannt als Methodenüberladung)bedeutet jedoch, dass wir je nach Typ des Parameters eine andere Implementierung verwenden.

Hier ist ein Beispiel in Haskell. Angenommen, wir möchten eine Funktion mit dem Namen definieren makeBreakfast.

Wenn der Eingabeparameter ist EggsIch will makeBreakfast um eine Nachricht zu senden, wie man Eier macht.

Wenn der Eingabeparameter ist PancakesIch will makeBreakfast um eine Nachricht darüber zurückzugeben, wie man Pfannkuchen macht.

Wir erstellen eine Typklasse namens BreakfastFood das implementiert die makeBreakfast Funktion. Die Implementierung von makeBreakfast wird je nach Art der Eingabe unterschiedlich sein makeBreakfast.

class BreakfastFood food where
  makeBreakfast :: food -> String

instance BreakfastFood Eggs where
  makeBreakfast = "First crack 'em, then fry 'em"

instance BreakfastFood Toast where
  makeBreakfast = "Put bread in the toaster until brown"

Laut John Mitchells Konzepte in Programmiersprachen,

Der Hauptunterschied zwischen parametrischem Polymorphismus und Überladen (auch bekannt als Ad-hoc-Polymorphismus) besteht darin, dass parametrische polymorphe Funktionen einen Algorithmus verwenden, um mit Argumenten vieler verschiedener Typen zu arbeiten, während überladene Funktionen für jeden Argumenttyp einen anderen Algorithmus verwenden können.

Eine vollständige Diskussion darüber, was parametrischer Polymorphismus und Ad-hoc-Polymorphismus bedeuten und inwieweit sie in Haskell und Java verfügbar sind, ist langwierig; Ihre konkreten Fragen lassen sich jedoch viel einfacher angehen:

Wie unterscheidet sich der Algorithmus der Typinferenz zB in Java von der Typinferenz in Haskell?

Soweit ich weiß, führt Java keine Typrückschlüsse durch. Der Unterschied ist also, dass Haskell es tut.

Geben Sie mir bitte ein Beispiel für die Situation, in der etwas in Java/Scala geschrieben werden kann, aber nicht in Haskell (auch gemäß den modularen Merkmalen dieser Plattformen) und umgekehrt.

Ein sehr einfaches Beispiel dafür, was Haskell kann, was Java nicht kann, ist das Definieren maxBound :: Bounded a => a. Ich kenne Java nicht genug, um darauf hinzuweisen, dass es etwas kann, was Haskell nicht kann.