Name der Technik zum Ableiten von Typargumenten eines Typparameters?

9

Setup: Nehmen wir an, wir haben einen Typ namens, Iteratorder einen Typparameter hat Element:

interface Iterator<Element> {}

Dann haben wir eine Schnittstelle, Iterabledie eine Methode hat, die eine zurückgibt Iterator.

// T has an upper bound of Iterator
interface Iterable<T: Iterator> {
    getIterator(): T
}

Das Problem mit Iteratorder Generizität ist, dass wir sie mit Typargumenten versorgen müssen.

Eine Idee, um dies zu lösen, besteht darin, den Typ des Iterators "abzuleiten". Der folgende Pseudocode drückt die Idee aus, dass es eine Typvariable Elementgibt, von der abgeleitet wird, dass sie das Typargument ist für Iterator:

interface <Element> Iterable<T: Iterator<Element>> {
    getIterator(): T
}

Und dann benutzen wir es irgendwo so:

class Vec<Element> implements Iterable<VecIterator<Element>> {/*...*/}

Diese Definition von Iterabledoesn‘t verwendet Elementanderswo in seiner Definition , aber mein realer Anwendungsfall tut. Bestimmte Funktionen, die verwendet werden, Iterablemüssen auch in der Lage sein, ihre Parameter so zu beschränken, dass sie Iterables akzeptieren, die nur bestimmte Arten von Iteratoren zurückgeben, z. B. einen bidirektionalen Iterator. Aus diesem Grund wird der zurückgegebene Iterator anstelle nur des Elementtyps parametrisiert.


Fragen:

  • Gibt es einen festgelegten Namen für diese abgeleiteten Typvariablen? Was ist mit der Technik als Ganzes? Das Fehlen einer bestimmten Nomenklatur hat es schwierig gemacht, in freier Wildbahn nach Beispielen dafür zu suchen oder sprachspezifische Merkmale kennenzulernen.
  • Nicht alle Sprachen mit Generika haben diese Technik; Gibt es Namen für ähnliche Techniken in diesen Sprachen?
Levi Morrison
quelle
1
Können Sie Code anzeigen, der nicht kompiliert werden kann und den Sie kompilieren möchten? Ich denke, das wird die Frage klarer machen.
Kehrmaschine
1
Sie können auch eine Sprache auswählen (oder angeben, welche Sprache Sie verwenden und was die Syntax bedeutet). Es ist offensichtlich nicht zum Beispiel C #. Es gibt viele Informationen über "Typinferenz" im Internet, aber ich bin mir nicht sicher, ob sie hier zutreffen.
5
Ich implementiere Generika in einer Sprache und versuche nicht, Code in einer Sprache zum Kompilieren zu bekommen. Es ist auch eine Namens- und Designfrage. Deshalb ist es etwas agnostisch. Ohne Kenntnis der Begriffe ist es schwierig, Beispiele und Dokumentationen in vorhandenen Sprachen zu finden. Sicher ist dies kein einzigartiges Problem?
Levi Morrison

Antworten:

2

Ich weiß nicht, ob es einen bestimmten Begriff für dieses Problem gibt, aber es gibt drei allgemeine Klassen von Lösungen:

  • Vermeiden Sie konkrete Typen zugunsten eines dynamischen Versands
  • Platzhaltertypparameter in Typeinschränkungen zulassen
  • Vermeiden Sie Typparameter, indem Sie zugehörige Typen / Typfamilien verwenden

Und natürlich die Standardlösung: Schreiben Sie all diese Parameter weiter aus.

Vermeiden Sie Betontypen.

Sie haben eine IterableSchnittstelle definiert als:

interface <Element> Iterable<T: Iterator<Element>> {
    getIterator(): T
}

Dies gibt Benutzern der Schnittstelle maximale Leistung, da sie den genauen konkreten Typ Tdes Iterators erhalten. Auf diese Weise kann ein Compiler auch weitere Optimierungen wie Inlining anwenden.

Wenn Iterator<E>es sich jedoch um eine dynamisch versendete Schnittstelle handelt, ist es nicht erforderlich, den konkreten Typ zu kennen. Dies ist zB die Lösung, die Java verwendet. Die Schnittstelle würde dann wie folgt geschrieben:

interface Iterable<Element> {
    getIterator(): Iterator<Element>
}

Eine interessante Variante davon ist die impl TraitSyntax von Rust, mit der Sie die Funktion mit einem abstrakten Rückgabetyp deklarieren können, aber wissen, dass der konkrete Typ an der Aufrufstelle bekannt ist (wodurch Optimierungen möglich sind). Dies verhält sich ähnlich wie bei einem impliziten Typparameter.

Platzhaltertypparameter zulassen.

Die IterableSchnittstelle muss den Elementtyp nicht kennen, daher kann dies möglicherweise wie folgt geschrieben werden:

interface Iterable<T: Iterator<_>> {
    getIterator(): T
}

Wobei T: Iterator<_>die Einschränkung "T ist ein beliebiger Iterator, unabhängig vom Elementtyp" ausgedrückt wird. Streng genommen können wir dies so ausdrücken: „Es gibt einen Typ Element, der ein Tist Iterator<Element>“, ohne dass wir einen konkreten Typ dafür kennen müssen Element. Dies bedeutet, dass der Typausdruck Iterator<_>keinen tatsächlichen Typ beschreibt und nur als Typeinschränkung verwendet werden kann.

Verwenden Sie Typfamilien / zugehörige Typen.

In C ++ kann ein Typ beispielsweise Typmitglieder haben. Dies wird üblicherweise in der gesamten Standardbibliothek verwendet, z std::vector::value_type. Dies löst das Problem mit den Typparametern nicht in allen Szenarien. Da sich ein Typ jedoch möglicherweise auf andere Typen bezieht, kann ein einzelner Typparameter eine ganze Familie verwandter Typen beschreiben.

Definieren wir:

interface Iterator {
  type ElementType
  fn next(): ElementType
}

interface Iterable {
  type IteratorType: Iterator
  fn getIterator(): IteratorType
}

Dann:

class Vec<Element> implement Iterable {
  type IteratorType = VecIterator<Element>
  fn getIterator(): IteratorType { ... }
}

class VecIterator<T> implements Iterator {
  type ElementType = T
  fn next(): ElementType { ... }
}

Dies sieht sehr flexibel aus. Beachten Sie jedoch, dass dies das Ausdrücken von Typeinschränkungen erschweren kann. Zum Beispiel Iterableerzwingt, wie geschrieben , keinen Iteratorelementtyp, und wir möchten möglicherweise interface Iterator<T>stattdessen deklarieren . Und Sie haben es jetzt mit einem ziemlich komplexen Typkalkül zu tun. Es ist sehr einfach, ein solches Typsystem versehentlich unentscheidbar zu machen (oder vielleicht schon?).

Beachten Sie, dass zugeordnete Typen als Standardeinstellungen für Typparameter sehr praktisch sein können. Unter der Annahme, dass die IterableSchnittstelle einen separaten Typparameter für den Elementtyp benötigt, der normalerweise, aber nicht immer mit dem Iteratorelementtyp identisch ist, und dass wir Platzhaltertypparameter haben, kann möglicherweise Folgendes gesagt werden:

interface Iterable<T: Iterator<_>, Element = T::Element> {
  ...
}

Dies ist jedoch nur eine Sprachergonomiefunktion und macht die Sprache nicht leistungsfähiger.


Typsysteme sind schwierig, daher ist es gut, einen Blick darauf zu werfen, was in anderen Sprachen funktioniert und was nicht.

Lesen Sie beispielsweise das Kapitel Erweiterte Eigenschaften im Rostbuch, in dem die zugehörigen Typen erläutert werden. Beachten Sie jedoch, dass einige Punkte zugunsten zugeordneter Typen anstelle von Generika nur dort gelten, da die Sprache keine Untertypisierung aufweist und jedes Merkmal höchstens einmal pro Typ implementiert werden kann. Dh Rust-Merkmale sind keine Java-ähnlichen Schnittstellen.

Andere interessante Typsysteme umfassen Haskell mit verschiedenen Spracherweiterungen. OCaml- Module / Funktoren sind eine vergleichsweise einfache Version von Typfamilien, ohne sie direkt mit Objekten oder parametrisierten Typen zu vermischen. Java zeichnet sich durch Einschränkungen in seinem Typsystem aus, z. B. Generika mit Typlöschung und keine Generika über Werttypen. C # ist sehr Java-ähnlich, kann jedoch die meisten dieser Einschränkungen auf Kosten einer höheren Komplexität der Implementierung vermeiden. Scala versucht, Generika im C # -Stil in Typklassen im Haskell-Stil auf der Java-Plattform zu integrieren. Die täuschend einfachen Vorlagen von C ++ sind gut untersucht, unterscheiden sich jedoch von den meisten generischen Implementierungen.

Es lohnt sich auch, die Standardbibliotheken dieser Sprachen (insbesondere Standardbibliothekssammlungen wie Listen oder Hash-Tabellen) zu betrachten, um festzustellen, welche Muster häufig verwendet werden. Beispielsweise verfügt C ++ über ein komplexes System mit verschiedenen Iteratorfunktionen, und Scala codiert feinkörnige Erfassungsfunktionen als Merkmale. Die Java-Standardbibliotheksschnittstellen sind manchmal nicht funktionsfähig, Iterator#remove()können jedoch verschachtelte Klassen als eine Art zugeordneten Typ verwenden (z Map.Entry. B. ).

amon
quelle