Klarstellung zu existentiellen Typen in Haskell

Ich versuche, existentielle Typen in Haskell zu verstehen und bin auf ein PDF gestoßen: http://www.ii.uni.wroc.pl/~dabi/courses/ZPF15/rlasocha/prezentacja.pdf

Bitte korrigieren Sie mein unten stehendes Verständnis, das ich bis jetzt habe.

• Existenzielle Typen scheinen nicht an dem Typ interessiert zu sein, den sie enthalten, aber Mustervergleiche besagen, dass es einen Typ gibt, von dem wir nicht wissen, um welchen Typ es sich handelt, bis wir Typeable oder Data verwenden.
• Wir verwenden sie, wenn wir Typen ausblenden möchten (z. B. für heterogene Listen) oder wenn wir nicht wirklich wissen, welche Typen zur Kompilierungszeit vorhanden sind.
• GADT's bieten die klare und bessere Syntax für Code unter Verwendung von Existenztypen, indem implizite forall' s bereitgestellt werden

Meine Zweifel

• In Seite 20 des obigen PDF wird für den folgenden Code erwähnt, dass es für eine Funktion unmöglich ist, einen bestimmten Puffer anzufordern. Wieso ist es so? Wenn ich eine Funktion entwerfe, weiß ich genau, welche Art von Puffer ich verwenden werde, obwohl ich möglicherweise nicht weiß, welche Daten ich in diese Funktion einfügen werde. Was ist falsch daran, :: Worker MemoryBuffer Intwenn sie wirklich über Puffer abstrahieren wollen, können sie einen Summentyp data Buffer = MemoryBuffer | NetBuffer | RandomBufferund einen Typ wie haben:: Worker Buffer Int

data Worker x = forall b. Buffer b => Worker {buffer :: b, input :: x}
data MemoryBuffer = MemoryBuffer

memoryWorker = Worker MemoryBuffer (1 :: Int)
memoryWorker :: Worker Int

• Da Haskell eine Full Type Erasure-Sprache wie C ist, woher weiß es dann zur Laufzeit, welche Funktion aufgerufen werden soll. Ist es so, als würden wir nur wenige Informationen pflegen und eine riesige V-Tabelle mit Funktionen übergeben, und zur Laufzeit wird dies anhand der V-Tabelle herausgefunden? Wenn ja, welche Art von Informationen werden dann gespeichert?

GADTs bieten die klare und bessere Syntax für Code mithilfe von Existenztypen, indem implizite Foralls bereitgestellt werden

Ich denke, es besteht allgemeine Übereinstimmung darüber, dass die GADT-Syntax besser ist. Ich würde nicht sagen, dass dies daran liegt, dass GADTs implizite Foralls bereitstellen, sondern dass die ursprüngliche Syntax, die mit der ExistentialQuantificationErweiterung aktiviert wurde , möglicherweise verwirrend / irreführend ist. Diese Syntax sieht natürlich so aus:

data SomeType = forall a. SomeType a

oder mit einer Einschränkung:

data SomeShowableType = forall a. Show a => SomeShowableType a

und ich denke, der Konsens ist, dass die Verwendung des Schlüsselworts forallhier ermöglicht, dass der Typ leicht mit dem völlig anderen Typ verwechselt werden kann:

data AnyType = AnyType (forall a. a)    -- need RankNTypes extension

Bei einer besseren Syntax wurde möglicherweise ein separates existsSchlüsselwort verwendet, sodass Sie Folgendes schreiben würden:

data SomeType = SomeType (exists a. a)   -- not valid GHC syntax

Die implizite oder explizite GADT-Syntax forallist für diese Typen einheitlicher und scheint leichter zu verstehen. Selbst mit einer expliziten forallDefinition vermittelt die folgende Definition die Idee, dass Sie einen Wert eines beliebigen Typs ain einen monomorphen Wert einfügen können SomeType':

data SomeType' where
    SomeType' :: forall a. (a -> SomeType')   -- parentheses optional

und es ist leicht, den Unterschied zwischen diesem Typ zu erkennen und zu verstehen:

data AnyType' where
    AnyType' :: (forall a. a) -> AnyType'

Existenzielle Typen scheinen nicht an dem Typ interessiert zu sein, den sie enthalten, aber Mustervergleiche besagen, dass es einen Typ gibt, von dem wir nicht wissen, um welchen Typ es sich handelt, bis wir Typeable oder Data verwenden.

Wir verwenden sie, wenn wir Typen ausblenden möchten (z. B. für heterogene Listen) oder wenn wir nicht wirklich wissen, welche Typen zur Kompilierungszeit vorhanden sind.

Ich denke, diese sind nicht zu weit entfernt, obwohl Sie keine existenziellen Typen verwenden Typeableoder Dataverwenden müssen. Ich denke, es wäre genauer zu sagen, dass ein existenzieller Typ eine gut typisierte "Box" um einen nicht spezifizierten Typ liefert. Das Feld "versteckt" den Typ in gewissem Sinne, wodurch Sie eine heterogene Liste solcher Felder erstellen können, wobei die darin enthaltenen Typen ignoriert werden. Es stellt sich heraus, dass ein nicht eingeschränktes Existenzial wie SomeType'oben ziemlich nutzlos ist, aber ein eingeschränkter Typ:

data SomeShowableType' where
    SomeShowableType' :: forall a. (Show a) => a -> SomeShowableType'

ermöglicht es Ihnen, Musterübereinstimmungen vorzunehmen, um einen Blick in die "Box" zu werfen und die Typklasseneinrichtungen verfügbar zu machen:

showIt :: SomeShowableType' -> String
showIt (SomeShowableType' x) = show x

Beachten Sie, dass dies für jede Typklasse funktioniert, nicht nur für Typeableoder Data.

In Bezug auf Ihre Verwirrung über Seite 20 des Dia-Decks sagt der Autor, dass es für eine existenzielle Funktion unmöglich ist , eine bestimmte Instanz Workerzu fordern . Sie können eine Funktion schreiben, um eine mit einem bestimmten Typ von zu erstellen , wie z .WorkerBufferWorkerBufferMemoryBuffer

class Buffer b where
  output :: String -> b -> IO ()
data Worker x = forall b. Buffer b => Worker {buffer :: b, input :: x}
data MemoryBuffer = MemoryBuffer
instance Buffer MemoryBuffer

memoryWorker = Worker MemoryBuffer (1 :: Int)
memoryWorker :: Worker Int

Wenn Sie jedoch eine Funktion schreiben, die ein Workeras-Argument verwendet, kann sie nur die allgemeinen BufferTypklassenfunktionen (z. B. die Funktion output) verwenden:

doWork :: Worker Int -> IO ()
doWork (Worker b x) = output (show x) b

Es kann nicht versucht werden, zu verlangen, dass es sich bum einen bestimmten Puffertyp handelt, auch nicht durch Mustervergleich:

doWorkBroken :: Worker Int -> IO ()
doWorkBroken (Worker b x) = case b of
  MemoryBuffer -> error "try this"       -- type error
  _            -> error "try that"

Schließlich werden Laufzeitinformationen zu existenziellen Typen durch implizite "Wörterbuch" -Argumente für die beteiligten Typklassen verfügbar gemacht. Der Workerobige Typ hat zusätzlich zu den Feldern für den Puffer und die Eingabe auch ein unsichtbares implizites Feld, das auf das BufferWörterbuch verweist (ähnlich wie die V-Tabelle, obwohl sie kaum riesig ist, da sie nur einen Zeiger auf die entsprechende outputFunktion enthält).

Intern wird die Typklasse Bufferals Datentyp mit Funktionsfeldern dargestellt, und Instanzen sind "Wörterbücher" dieses Typs:

data Buffer' b = Buffer' { output' :: String -> b -> IO () }

dBuffer_MemoryBuffer :: Buffer' MemoryBuffer
dBuffer_MemoryBuffer = Buffer' { output' = undefined }

Der existentielle Typ hat ein verstecktes Feld für dieses Wörterbuch:

data Worker' x = forall b. Worker' { dBuffer :: Buffer' b, buffer' :: b, input' :: x }

und eine solche Funktion doWork, die mit existenziellen Worker'Werten arbeitet, wird implementiert als:

doWork' :: Worker' Int -> IO ()
doWork' (Worker' dBuf b x) = output' dBuf (show x) b

Für eine Typklasse mit nur einer Funktion ist das Wörterbuch tatsächlich auf einen neuen WorkerTyp optimiert. In diesem Beispiel enthält der existenzielle Typ ein verstecktes Feld, das aus einem Funktionszeiger auf die outputFunktion für den Puffer besteht. Dies ist die einzige erforderliche Laufzeitinformation von doWork.

In Seite 20 des obigen PDF wird für den folgenden Code erwähnt, dass es für eine Funktion unmöglich ist, einen bestimmten Puffer anzufordern. Wieso ist es so?

Da Workerwie definiert nur ein Argument verwendet wird, der Typ des "Eingabe" -Felds (Typvariable x). ZB Worker Intist ein Typ. Die Typvariable bist stattdessen kein Parameter von Worker, sondern sozusagen eine Art "lokale Variable". Es kann nicht wie in übergeben werden Worker Int String- das würde einen Typfehler auslösen.

Wenn wir stattdessen definieren:

data Worker x b = Worker {buffer :: b, input :: x}

dann Worker Int Stringwürde es funktionieren, aber der Typ ist nicht mehr existenziell - wir müssen jetzt immer auch den Puffertyp übergeben.

Da Haskell eine Full Type Erasure-Sprache wie C ist, woher weiß es dann zur Laufzeit, welche Funktion aufgerufen werden soll. Ist es so, als würden wir nur wenige Informationen pflegen und eine riesige V-Tabelle mit Funktionen übergeben, und zur Laufzeit wird dies anhand der V-Tabelle herausgefunden? Wenn ja, welche Art von Informationen werden dann gespeichert?

Das ist ungefähr richtig. Kurz gesagt, jedes Mal, wenn Sie den Konstruktor anwenden Worker, leitet GHC den bTyp aus den Argumenten von ab Workerund sucht dann nach einer Instanz Buffer b. Wenn dies gefunden wird, enthält GHC einen zusätzlichen Zeiger auf die Instanz im Objekt. In seiner einfachsten Form unterscheidet sich dies nicht allzu sehr von dem "Zeiger auf vtable", der jedem Objekt in OOP hinzugefügt wird, wenn virtuelle Funktionen vorhanden sind.

Im allgemeinen Fall kann es jedoch viel komplexer sein. Der Compiler verwendet möglicherweise eine andere Darstellung und fügt anstelle eines einzelnen Zeigers weitere Zeiger hinzu (z. B. direktes Hinzufügen der Zeiger zu allen Instanzmethoden), wenn dies den Code beschleunigt. Manchmal muss der Compiler auch mehrere Instanzen verwenden, um eine Einschränkung zu erfüllen. Wenn wir beispielsweise die Instanz für Eq [Int]... speichern müssen, gibt es nicht eine, sondern zwei: eine für Intund eine für Listen, und die beiden müssen kombiniert werden (zur Laufzeit, außer bei Optimierungen).

Es ist schwer zu erraten, was GHC in jedem Fall genau tut: Das hängt von einer Menge Optimierungen ab, die möglicherweise ausgelöst werden oder nicht.

Sie können versuchen, nach der "wörterbuchbasierten" Implementierung von Typklassen zu googeln, um mehr über die Vorgänge zu erfahren. Sie können GHC auch bitten, den internen optimierten Core mit -ddump-simplden Wörterbüchern zu drucken und zu beobachten, die erstellt, gespeichert und weitergegeben werden. Ich muss Sie warnen: Der Kern ist eher niedrig und kann zunächst schwer zu lesen sein.