Ja, darüber habe ich auch nachgedacht. Grundsätzlich ist die Idee, dass es so aussieht, als könnte man Haskell 98 implementieren, aber nicht einige der Spracherweiterungen dazu, indem man Polymorphismus durch Multiinstanziierung anstelle von Polymorphismus durch Boxen verwendet.
Man kann Einblicke darin gewinnen, indem man versucht, einige Haskell-Funktionen als C++-Bibliotheken zu implementieren (wie Sie bemerken, verwendet C++ Polymorphismus durch Multiinstanziierung). Was man feststellt, ist, dass man alles tun kann, was Haskell kann, außer dass es unmöglich ist, polymorphe Werte zu haben, was auch Verweise auf polymorphe Funktionen einschließt.
Wie das aussieht, ist dass, wenn Sie haben
template
void f(T); // f :: a -> IO ()
können Sie die Adresse einer bestimmten Instanziierung nehmen, um sie als Funktionszeiger zur Laufzeit zu übergeben:
&f
aber Sie können nicht die Adresse eines Templates (&f) nehmen. Das macht Sinn: Templates sind ein rein kompilierzeitliches Konstrukt. Es macht auch Sinn, dass wenn Sie Polymorphismus durch Multiinstanziierung machen, Sie einen Zeiger auf eine bestimmte Instanziierung haben können, aber keinen Zeiger auf die polymorphe Funktion selbst, weil auf Maschinencodeebene keine existiert.
Wo verwendet Haskell also polymorphe Werte? Auf den ersten Blick scheint eine gute Faustregel "überall, wo Sie ein explizites forall schreiben müssen". Also PolymorphicComponents, Rank2Types, RankNTypes und ImpredicativeTypes sind offensichtliche No-Gos. Dies kann nicht in C++ übersetzt werden:
data MkList = MkList (forall a. a -> [a])
singleton = MkList (\x -> [x])
Andererseits ist ExistentialQuantification in zumindest einigen Fällen durchführbar: Es bedeutet, eine nicht-template Klasse mit einem Vorlagenkonstruktor zu haben (oder allgemeiner ausgedrückt, eine Klasse, deren Konstruktor auf mehr Dinge als die Klasse selbst vortemplate ist).
Wenn Sie also in Haskell haben:
data SomeShow = forall a. Show a => SomeShow a
instance Show SomeShow where show (SomeShow a) = show a
kann man dies in C++ wie folgt implementieren:
// eine Funktion, die einen void* nimmt, diesen auf den gegebenen Typ castet und
// die entsprechende show() Funktion aufruft (statisch ausgewählt aufgrund
// der Überladungsauflösungsregeln)
template
String showVoid(void *x)
{
show(*(T*)x);
}
class SomeShow
{
private:
void *m_data;
String (*m_show)(void*); // m_show :: Any -> String
public:
template
SomeShow(T x)
: m_data(new T(x)) // Speicherprobleme, die aber nichts damit zu tun haben
, m_show(&showVoid)
{
}
String show()
{
// alternativ könnten wir die Top-Level-show() als friend deklarieren und
// dies dort platzieren
return m_show(m_data);
}
};
// C++ hat keine Typklassen im eigentlichen Sinne, aber es hat Überladung, was bedeutet,
// dass Schnittstellen implizit sind: Wo in Haskell man eine Klasse und
// Instanzen schreiben würde, schreibt man in C++ einfach eine Funktion mit dem gleichen Namen für jeden Typ
String show(SomeShow x)
{
return x.show();
}
In beiden Sprachen hat man also einen nicht-polymorphen Typ mit einem polymorphen Konstruktor.
Wir haben also gezeigt, dass es einige Spracherweiterungen gibt, die Sie implementieren können und einige, die Sie nicht können, aber was ist mit der anderen Seite der Medaille: Gibt es etwas in Haskell 98, das Sie nicht implementieren können? Wenn Sie bedenken, dass Sie eine Spracherweiterung (ExplicitForAll) benötigen, um überhaupt ein forall zu schreiben, würden Sie denken, dass die Antwort nein ist. Und Sie wären fast richtig, aber es gibt zwei Haken: Typklassen und polymorphe Rekursion. Typklassen werden typischerweise mit dem Durchreichen von Dictionaries implementiert: Jede Instanzerklärung führt zu einem Satz von Funktionen, die implizit überall dort übergeben werden, wo sie benötigt werden.
Also für Monad hätten Sie beispielsweise:
data MonadDict m = MonadDict {
return :: forall a. a -> m a,
(>>=) :: forall a b. m a -> (a -> m b) -> m b
}
Nun, schauen Sie sich diese Foralls an! Sie können sie nicht explizit schreiben, aber in Implementierungen mit Dictionary-Passing, selbst in Haskell 98, führen Klassen mit polymorphen Methoden zu Records, die polymorphe Funktionen enthalten. Was, wenn Sie versuchen, das Ganze mit Multiinstanziierung zu implementieren, offensichtlich ein Problem darstellt. Sie könnt fast ohne Dictionary-Passing auskommen, weil, wenn Sie sich an Haskell 98 halten, Instanzen fast immer global und statisch bekannt sind. Jede Instanz führt zu einigen polymorphen Funktionen, aber weil zur Compile-Zeit fast immer bekannt ist, welche Funktion aufgerufen werden soll, müssen Sie fast nie Referenzen darauf zur Laufzeit übergeben (was gut ist, denn Sie können es nicht). Der Kompromiss besteht darin, dass Sie eine gesamte Programm-Kompilierung durchführen müssen, da Instanzen sonst nicht mehr statisch bekannt sind: Sie könnten in einem anderen Modul sein. Und die Ausnahme ist polymorphe Rekursion, die Sie praktisch dazu zwingt, ein Dictionary zur Laufzeit aufzubauen. Sehen Sie sich die andere Antwort für weitere Details dazu an. Polymorphe Rekursion macht den Multi.instanziierung Ansatz auch ohne Typklassen zunichte: Siehe den Kommentar zu BTrees. (Auch ExistentialQuantification *plus* Klassen mit polymorphen Methoden sind nicht mehr durchführbar, weil Sie wieder anfangen müssten, Verweise auf polymorphe Funktionen zu speichern.)
