Was ist der Unterschied zwischen den Typklassen von Haskell und den Schnittstellen von Go?

8

Ich frage mich, ob es einen Unterschied zwischen den Typklassen von Haskell und den Schnittstellen von Go gibt. Beide definieren Typen basierend auf Funktionen, so dass ein Wert mit einem Typ übereinstimmt, wenn für den Wert eine für den Typ erforderliche Funktion definiert ist.

Gibt es Unterschiede oder sind das nur zwei Namen für dasselbe?

ceving
quelle

Antworten:

6

Die beiden Konzepte sind sehr, sehr ähnlich. In normalen OOP-Sprachen fügen wir jedem Objekt eine vtable (oder für Schnittstellen: itable) hinzu:

| this
v
+---+---+---+
| V | a | b | the object with fields a, b
+---+---+---+
  |
  v
 +---+---+---+
 | o | p | q | the vtable with method slots o(), p(), q()
 +---+---+---+

Dies ermöglicht es uns, ähnliche Methoden wie aufzurufen this->vtable.p(this).

In Haskell ähnelt die Methodentabelle eher einem impliziten versteckten Argument:

method :: Class a => a -> a -> Int

würde wie die C ++ - Funktion aussehen

template<typename A>
int method(Class<A>*, A*, A*)

Wo Class<A>ist eine Instanz der Typklasse Classfür Typ A. Eine Methode würde wie aufgerufen

typeclass_instance->p(value_ptr);

Die Instanz ist von den Werten getrennt. Die Werte behalten ihren tatsächlichen Typ bei. Während Typklassen einen gewissen Polymorphismus zulassen, ist dies kein Subtyping-Polymorphismus. Das macht es unmöglich, eine Liste von Werten zu erstellen, die a erfüllen Class. Angenommen, wir haben instance Class Int ...und instance Class String ...können keinen heterogenen Listentyp wie [Class]diesen mit Werten wie erstellen [42, "foo"]. (Dies ist möglich, wenn Sie die Erweiterung "Existenzielle Typen" verwenden, die effektiv zum Go-Ansatz wechselt.)

In Go implementiert ein Wert keinen festen Satz von Schnittstellen. Folglich kann es keinen vtable-Zeiger haben. Stattdessen werden Zeiger auf Schnittstellentypen als fette Zeiger implementiert , die einen Zeiger auf die Daten und einen weiteren Zeiger auf die itable enthalten:

    `this` fat pointer
    +---+---+
    |   |   |
    +---+---+
 ____/    \_________
v                   v
+---+---+---+       +---+---+
| o | p | q |       | a | b | the data with
+---+---+---+       +---+---+ fields a, b
itable with method
slots o(), p(), q()

this.itable->p(this.data_ptr)

Die itable wird mit den Daten zu einem fetten Zeiger kombiniert, wenn Sie von einem normalen Wert in einen Schnittstellentyp umwandeln. Sobald Sie einen Schnittstellentyp haben, ist der tatsächliche Datentyp irrelevant geworden. Tatsächlich können Sie nicht direkt auf die Felder zugreifen, ohne Methoden durchzugehen oder die Schnittstelle herunterzuspielen (was möglicherweise fehlschlägt).

Der Ansatz von Go für den Schnittstellenversand ist mit Kosten verbunden: Jeder polymorphe Zeiger ist doppelt so groß wie ein normaler Zeiger. Beim Umwandeln von einer Schnittstelle in eine andere werden die Methodenzeiger in eine neue vtable kopiert. Sobald wir das itable erstellt haben, können wir Methodenaufrufe kostengünstig an viele Schnittstellen senden, unter denen traditionelle OOP-Sprachen leiden. Hier ist m die Anzahl der Methoden in der Zielschnittstelle und b die Anzahl der Basisklassen:

  • C ++ schneidet Objekte auf oder muss beim Casting virtuelle Vererbungszeiger verfolgen, hat dann aber einfachen vtable-Zugriff. O (1) oder O (b) Kosten für Upcasting, aber Versand nach O (1) -Methode.
  • Die Java Hotspot-VM muss beim Upcasting nichts tun, aber bei der Suche nach Schnittstellenmethoden werden alle von dieser Klasse implementierten itables linear durchsucht. O (1) Upcasting, aber O (b) Methodenversand.
  • Python muss beim Upcasting nichts tun, sondern verwendet eine lineare Suche durch eine C3-linearisierte Basisklassenliste. O (1) Upcasting, aber O (b²) Methode Versand? Ich bin mir nicht sicher, wie hoch die algorithmische Komplexität von C3 ist.
  • Die .NET-CLR verwendet einen ähnlichen Ansatz wie Hotspot, fügt jedoch eine weitere Indirektionsebene hinzu, um die Speichernutzung zu optimieren. O (1) Upcasting, aber O (b) Methodenversand.

Die typische Komplexität für den Methodenversand ist viel besser, da die Methodensuche häufig zwischengespeichert werden kann, aber die Komplexität im schlimmsten Fall ist ziemlich schrecklich.

Im Vergleich dazu hat Go O (1) oder O (m) Upcasting und O (1) Methodenversand. Haskell hat kein Upcasting (das Einschränken eines Typs mit einer Typklasse ist ein Effekt zur Kompilierungszeit) und den Versand der O (1) -Methode.

amon
quelle
Danke für [42, "foo"]. Es ist ein anschauliches Beispiel.
Ceving
2
Obwohl diese Antwort gut geschrieben ist und nützliche Informationen enthält, denke ich, dass durch die Konzentration auf die Implementierung im kompilierten Code die Ähnlichkeiten zwischen Schnittstellen und Typklassen erheblich überbewertet werden. Bei Typklassen (und dem Haskell-Typsystem im Allgemeinen) passieren die meisten interessanten Dinge während der Kompilierung und spiegeln sich nicht im endgültigen Maschinencode wider.
KA Buhr
7

Es gibt verschiedene Unterschiede

  1. Haskell-Typklassen sind nominativ typisiert - Sie müssen deklarieren, dass dies Maybeeine ist Monad. Go-Schnittstellen sind strukturell typisiert: Wenn dies circledeklariert wird area() float64, befinden sich squarebeide shapeautomatisch unter der Schnittstelle .
  2. Haskell (mit GHC-Erweiterungen) verfügt über Multi-Parameter-Typklassen und (wie in meinem Maybe aBeispiel) Typklassen für höherwertige Typen. Go hat für diese kein Äquivalent.
  3. In Haskell werden Typklassen mit gebundenem Polymorphismus verwendet, wodurch Sie Einschränkungen erhalten, die mit Go nicht ausgedrückt werden können. Zum Beispiel + :: Num a => a -> a -> aist es in Go unaussprechlich, dass Sie nicht versuchen, Gleitkomma und Quaternionen hinzuzufügen.
Walpen
quelle
Ist 1. wirklich ein Unterschied oder fehlt nur Zucker?
Ceving
1
Go-Schnittstellen definieren ein Protokoll für Werte, Haskell-Typklassen definieren ein Protokoll für Typen, das ist auch ein ziemlich großer Unterschied, würde ich sagen. (Deshalb werden sie schließlich "Typklassen" genannt. Sie klassifizieren Typen im Gegensatz zu OO-Klassen (oder Go-Schnittstellen), die Werte klassifizieren.)
Jörg W Mittag
1
@ceving, es ist definitiv kein Zucker im normalen Sinne: Wenn Haskell zu so etwas wie Scala-Impliziten für Typklassen springen würde, würde dies eine Menge vorhandenen Codes beschädigen.
Walpen
@ JörgWMittag Da stimme ich zu und mir hat Ihre Antwort gefallen: Ich habe versucht, den Unterschied aus der Sicht der Benutzer besser zu verstehen.
Walpen
@walpen Warum bricht dieser Code? Ich frage mich, wie ein solcher Code angesichts der Strenge des Haskell-Typsystems existieren könnte.
20.
4

Sie sind völlig anders. Go-Schnittstellen definieren ein Protokoll für Werte, Haskell-Typklassen definieren ein Protokoll für Typen. (Deshalb werden sie schließlich "Typklassen" genannt. Sie klassifizieren Typen im Gegensatz zu OO-Klassen (oder Go-Schnittstellen), die Werte klassifizieren.)

Go-Interfaces sind nur langweilige alte strukturelle Typisierung, nichts weiter.

Jörg W Mittag
quelle
1
Kannst du es erklären? Vielleicht sogar ohne herablassenden Ton. Was ich gelesen habe, besagt, dass Typklassen Ad-hoc-Polymorphismus sind, vergleichbar mit Operatorüberladung, die mit Schnittstellen in Go identisch ist.
Ceving
Aus dem Haskell- Tutorial : "Wie eine Schnittstellendeklaration definiert eine Haskell-Klassendeklaration ein Protokoll für die Verwendung eines Objekts"
am
2
Aus demselben Tutorial ( fett Hervorhebung von mir): „Typklassen [...] erlauben es uns zu erklären , welche Arten sind Instanzen , welche Klasse“ Die Instanzen einer Go - Schnittstelle sind Werte , sind die Instanzen einer Haskell Typ Klasse - Typen . Werte und Typen leben in zwei völlig getrennten Welten (zumindest in Sprachen wie Haskell und Go sind abhängig typisierte Sprachen wie Agda, Guru, Epigramm, Idris, Isabelle, Coq usw. eine andere Sache).
Jörg W Mittag
Abstimmung, weil die Antwort aufschlussreich ist, aber ich denke, mehr Details könnten helfen. Und was ist langweilig an struktureller Typisierung?! Es ist ziemlich selten und meiner Meinung nach eine Feier wert.
Max Heiber