Programmierressourcen vom Typ Scala

Nach dieser Frage ist Scalas Typensystem vollständig . Welche Ressourcen stehen zur Verfügung, mit denen ein Neuling die Möglichkeiten der Programmierung auf Typebene nutzen kann?

Hier sind die Ressourcen, die ich bisher gefunden habe:

• Daniel Spiewaks Hohe Zauberei im Land der Scala
• Apocalisps Typ-Level-Programmierung in Scala
• Jespers hList

Diese Ressourcen sind großartig, aber ich habe das Gefühl, dass mir die Grundlagen fehlen, und ich habe keine solide Grundlage, auf der ich aufbauen kann. Wo gibt es zum Beispiel eine Einführung in Typdefinitionen? Welche Operationen kann ich für Typen ausführen?

Gibt es gute Einführungsressourcen?

Überblick

Die Programmierung auf Typebene hat viele Ähnlichkeiten mit der herkömmlichen Programmierung auf Wertebene. Im Gegensatz zur Programmierung auf Wertebene, bei der die Berechnung zur Laufzeit erfolgt, erfolgt die Berechnung bei der Programmierung auf Typebene jedoch zur Kompilierungszeit. Ich werde versuchen, Parallelen zwischen der Programmierung auf Wertebene und der Programmierung auf Typebene zu ziehen.

Paradigmen

Bei der Programmierung auf Typebene gibt es zwei Hauptparadigmen: "objektorientiert" und "funktional". Die meisten von hier verlinkten Beispiele folgen dem objektorientierten Paradigma.

Ein gutes, ziemlich einfaches Beispiel für die Programmierung auf Typebene im objektorientierten Paradigma findet sich in der hier replizierten Apocalisp- Implementierung des Lambda-Kalküls :

// Abstract trait
trait Lambda {
  type subst[U <: Lambda] <: Lambda
  type apply[U <: Lambda] <: Lambda
  type eval <: Lambda
}

// Implementations
trait App[S <: Lambda, T <: Lambda] extends Lambda {
  type subst[U <: Lambda] = App[S#subst[U], T#subst[U]]
  type apply[U] = Nothing
  type eval = S#eval#apply[T]
}

trait Lam[T <: Lambda] extends Lambda {
  type subst[U <: Lambda] = Lam[T]
  type apply[U <: Lambda] = T#subst[U]#eval
  type eval = Lam[T]
}

trait X extends Lambda {
  type subst[U <: Lambda] = U
  type apply[U] = Lambda
  type eval = X
}

Wie im Beispiel zu sehen ist, läuft das objektorientierte Paradigma für die Programmierung auf Typebene wie folgt ab:

• Erstens: Definieren Sie ein abstraktes Merkmal mit verschiedenen abstrakten Typfeldern (siehe unten, was ein abstraktes Feld ist). Dies ist eine Vorlage, um sicherzustellen, dass bestimmte Typenfelder in allen Implementierungen vorhanden sind, ohne eine Implementierung zu erzwingen. In dem Lambda - Kalkül Beispiel das entspricht , trait Lambdadie garantiert , dass die folgenden Arten vorhanden ist : subst, applyund eval.
• Weiter: Definieren Sie Untermerkmale, die das abstrakte Merkmal erweitern, und implementieren Sie die verschiedenen Felder für abstrakte Typen
  • Oft werden diese Subtraits mit Argumenten parametrisiert. Im Beispiel der Lambda-Berechnung sind die Untertypen, trait App extends Lambdadie mit zwei Typen parametrisiert sind ( Sund Tbeide müssen Untertypen von sein Lambda), trait Lam extends Lambdamit einem Typ parametrisiert sind ( T) und trait X extends Lambda(der nicht parametrisiert ist).
  • Die Typfelder werden häufig implementiert, indem auf die Typparameter des Subtraits verwiesen wird und manchmal auf ihre Typfelder über den Hash-Operator verwiesen wird: #(der dem Punktoperator sehr ähnlich ist: .für Werte). Im Merkmal Appdes Lambda-Kalkül-Beispiels wird der Typ evalwie folgt implementiert : type eval = S#eval#apply[T]. Dies bedeutet im Wesentlichen, den evalTyp des Parameters des Merkmals Saufzurufen und das Ergebnis applymit dem Parameter aufzurufen T. Beachten Sie, dass Sgarantiert ein evalTyp vorhanden ist, da der Parameter angibt, dass es sich um einen Untertyp handelt Lambda. In ähnlicher Weise muss das Ergebnis von evaleinen applyTyp haben, da es als Subtyp von angegeben wird Lambda, wie im abstrakten Merkmal angegeben Lambda.

Das funktionale Paradigma besteht darin, viele parametrisierte Typkonstruktoren zu definieren, die nicht in Merkmalen zusammengefasst sind.

Vergleich zwischen Programmierung auf Wertebene und Programmierung auf Typebene

• abstrakte Klasse
  • Wertebene: abstract class C { val x }
  • Typ-Ebene: trait C { type X }
• Pfadabhängige Typen
  • C.x (Verweis auf Feldwert / Funktion x in Objekt C)
  • C#x (Referenzieren des Feldtyps x in Merkmal C)
• Funktionssignatur (keine Implementierung)
  • Wertebene: def f(x:X) : Y
  • Typ-Ebene: type f[x <: X] <: Y(Dies wird als "Typ-Konstruktor" bezeichnet und tritt normalerweise im abstrakten Merkmal auf.)
• Funktionsimplementierung
  • Wertebene: def f(x:X) : Y = x
  • Typ-Ebene: type f[x <: X] = x
• Bedingungen
  • siehe hier
• Gleichstellung prüfen
  • Wertebene: a:A == b:B
  • Typ-Ebene: implicitly[A =:= B]
  • Wertebene: Passiert in der JVM über einen Unit-Test zur Laufzeit (dh keine Laufzeitfehler):
    • in Essenz ist eine Behauptung: assert(a == b)
  • Typenebene: Passiert im Compiler über einen Typcheck (dh keine Compilerfehler):
    • Im Wesentlichen handelt es sich um einen Typvergleich: z implicitly[A =:= B]
    • A <:< B, wird nur kompiliert, wenn Aes sich um einen Subtyp von handeltB
    • A =:= B, wird nur kompiliert, wenn Aes sich um einen Subtyp von Bund Bum einen Subtyp von handeltA
    • A <%< B, ("sichtbar als") wird nur kompiliert, wenn Asichtbar als B(dh es gibt eine implizite Konvertierung von Ain einen Subtyp von B)
    • ein Beispiel
    • mehr Vergleichsoperatoren

Konvertieren zwischen Typen und Werten

• In vielen Beispielen sind Typen, die über Merkmale definiert werden, häufig sowohl abstrakt als auch versiegelt und können daher weder direkt noch über eine anonyme Unterklasse instanziiert werden. Daher ist es üblich, nulleinen Platzhalterwert zu verwenden, wenn eine Berechnung auf Wertebene mit einem bestimmten Interesse durchgeführt wird:

  • zB val x:A = null, wo Aist der Typ, den Sie interessieren

• Aufgrund der Typlöschung sehen parametrisierte Typen alle gleich aus. Darüber hinaus sind (wie oben erwähnt) die Werte, mit denen Sie arbeiten, in der Regel alle null, sodass eine Konditionierung des Objekttyps (z. B. über eine Übereinstimmungsanweisung) unwirksam ist.

Der Trick besteht darin, implizite Funktionen und Werte zu verwenden. Der Basisfall ist normalerweise ein impliziter Wert und der rekursive Fall ist normalerweise eine implizite Funktion. In der Tat werden bei der Programmierung auf Typebene Implikationen stark genutzt.

Betrachten Sie dieses Beispiel ( entnommen aus metascala und apocalisp ):

sealed trait Nat
sealed trait _0 extends Nat
sealed trait Succ[N <: Nat] extends Nat

Hier haben Sie eine Peano-Codierung der natürlichen Zahlen. Das heißt, Sie haben einen Typ für jede nicht negative Ganzzahl: einen speziellen Typ für 0, nämlich _0; und jede ganze Zahl größer als Null hat einen Typ der Form Succ[A], wobei Ader Typ eine kleinere ganze Zahl darstellt. Der Typ, der 2 darstellt, wäre beispielsweise: Succ[Succ[_0]](Nachfolger wird zweimal auf den Typ angewendet, der Null darstellt).

Wir können verschiedene natürliche Zahlen für eine bequemere Referenz aliasisieren. Beispiel:

type _3 = Succ[Succ[Succ[_0]]]

(Dies ähnelt der Definition von a valals Ergebnis einer Funktion.)

Nehmen wir nun an, wir möchten eine Funktion auf Wertebene definieren, def toInt[T <: Nat](v : T)die einen Argumentwert annimmt, der einer Ganzzahl ventspricht Natund diese zurückgibt, die die natürliche Zahl darstellt, die in v's Typ codiert ist . Wenn wir beispielsweise den Wert val x:_3 = null( nullvom Typ Succ[Succ[Succ[_0]]]) haben, möchten wir toInt(x)zurückkehren 3.

Zur Implementierung verwenden toIntwir die folgende Klasse:

class TypeToValue[T, VT](value : VT) { def getValue() = value }

Wie wir unten sehen werden, wird es TypeToValuefür jede Natvon _0bis zu (z._3 , und jedes wird die Wertdarstellung des entsprechenden Typs TypeToValue[_0, Int]speichern (dh wird den Wert speichern 0, TypeToValue[Succ[_0], Int]wird den Wert speichern 1usw.). Hinweis: TypeToValuewird durch zwei Typen parametrisiert: Tund VT. Tentspricht dem Typ, dem wir Werte zuweisen möchten (in unserem Beispiel Nat), und VTentspricht dem Werttyp, den wir ihm zuweisen (in unserem Beispiel Int).

Nun machen wir die folgenden zwei impliziten Definitionen:

implicit val _0ToInt = new TypeToValue[_0, Int](0)
implicit def succToInt[P <: Nat](implicit v : TypeToValue[P, Int]) = 
     new TypeToValue[Succ[P], Int](1 + v.getValue())

Und wir implementieren toIntwie folgt:

def toInt[T <: Nat](v : T)(implicit ttv : TypeToValue[T, Int]) : Int = ttv.getValue()

Um zu verstehen, wie es toIntfunktioniert, betrachten wir einige Eingaben:

val z:_0 = null
val y:Succ[_0] = null

Wenn wir anrufen toInt(z) , sucht der Compiler nach einem impliziten Argument ttvvom Typ TypeToValue[_0, Int](da zes vom Typ ist _0). Es findet das Objekt _0ToInt, ruft die getValueMethode dieses Objekts auf und kehrt zurück 0. Der wichtige Punkt ist, dass wir dem Programm nicht angegeben haben, welches Objekt verwendet werden soll. Der Compiler hat es implizit gefunden.

Nun wollen wir überlegen toInt(y). Diesmal sucht der Compiler nach einem impliziten Argument ttvvom Typ TypeToValue[Succ[_0], Int](da yes vom Typ ist Succ[_0]). Es findet die Funktion succToInt, die ein Objekt des entsprechenden Typs ( TypeToValue[Succ[_0], Int]) zurückgeben und auswerten kann. Diese Funktion selbst verwendet ein implizites Argument ( v) vom Typ TypeToValue[_0, Int](d. H. A.TypeToValue wenn der erste Typparameter eins weniger hat Succ[_]). Der Compiler liefert _0ToInt(wie in der toInt(z)obigen Auswertung ) und erstellt succToIntein neues TypeToValueObjekt mit Wert 1. Auch hier ist zu beachten, dass der Compiler alle diese Werte implizit bereitstellt, da wir keinen expliziten Zugriff darauf haben.

Überprüfen Sie Ihre Arbeit

Es gibt verschiedene Möglichkeiten, um zu überprüfen, ob Ihre Berechnungen auf Typebene das tun, was Sie erwarten. Hier sind einige Ansätze. Machen Sie zwei ArtenA und B, die Sie überprüfen möchten, sind gleich. Überprüfen Sie dann Folgendes:

• Equal[A, B]
  • mit: Merkmal Equal[T1 >: T2 <: T2, T2]( entnommen aus apocolisp )
• implicitly[A =:= B]

Alternativ können Sie den Typ in einen Wert konvertieren (wie oben gezeigt) und eine Laufzeitprüfung der Werte durchführen. ZB assert(toInt(a) == toInt(b))wo aist vom Typ Aund bist vom Typ B.

Zusätzliche Ressourcen

Den vollständigen Satz verfügbarer Konstrukte finden Sie im Abschnitt Typen des Scala-Referenzhandbuchs (pdf) .

Adriaan Moors hat mehrere wissenschaftliche Artikel über Typkonstruktoren und verwandte Themen mit Beispielen aus Scala:

• Generika höherer Art (pdf)
• Typkonstruktor-Polymorphismus für Scala: Theorie und Praxis (pdf) (Doktorarbeit, die die vorherige Arbeit von Moors enthält)
• Typ Konstruktor Polymorphismus Inferenz

Apocalisp ist ein Blog mit vielen Beispielen für die Programmierung auf Typebene in Scala.

• Programmierung auf Typebene in Scala Typebene ist eine fantastische Führung durch einige Programme auf Typebene, die Boolesche Werte, natürliche Zahlen (wie oben), Binärzahlen, heterogene Listen und mehr enthält.
• Mehr Scala Typehackery ist die obige Lambda-Kalkül-Implementierung.

ScalaZ ist ein sehr aktives Projekt, das Funktionen bereitstellt, die die Scala-API mithilfe verschiedener Programmierfunktionen auf erweitern. Es ist ein sehr interessantes Projekt, das eine große Anhängerschaft hat.

MetaScala ist eine Bibliothek auf Typebene für Scala, einschließlich Metatypen für natürliche Zahlen, Boolesche Werte, Einheiten, HList usw. Es ist ein Projekt von Jesper Nordenberg (sein Blog) .

Der Michid (Blog) hat einige großartige Beispiele für die Programmierung auf Typebene in Scala (aus anderen Antworten):

• Metaprogrammierung mit Scala Teil I: Addition
• Metaprogrammierung mit Scala Teil II: Multiplikation
• Metaprogrammierung mit Scala Teil III: Teilfunktionsanwendung
• Metaprogrammierung mit Scala: Bedingte Kompilierung und Abrollen von Schleifen
• Scala-Typ-Level-Codierung des SKI-Kalküls

Debasish Ghosh (Blog) hat auch einige relevante Beiträge:

• Abstraktionen höherer Ordnung in Scala
• Statische Eingabe gibt Ihnen einen Vorsprung
• Scala impliziert Typklassen, hier komme ich
• Refactoring in Scala-Typklassen
• Verwenden verallgemeinerter Typeinschränkungen
• Wie Skalas Systemwörter für Sie eingeben
• Auswahl zwischen abstrakten Typmitgliedern

(Ich habe einige Nachforschungen zu diesem Thema angestellt und hier ist, was ich gelernt habe. Ich bin noch neu darin. Bitte weisen Sie auf Ungenauigkeiten in dieser Antwort hin.)

Neben den anderen Links hier gibt es auch meine Blog-Beiträge zur Meta-Programmierung auf Typebene in Scala:

• Metaprogrammierung mit Scala Teil I: Addition
• Metaprogrammierung mit Scala Teil II: Multiplikation
• Metaprogrammierung mit Scala Teil III: Teilfunktionsanwendung
• Metaprogrammierung mit Scala: Bedingte Kompilierung und Abrollen von Schleifen
• Scala-Typ-Level-Codierung des SKI-Kalküls

Wie auf Twitter vorgeschlagen: Shapeless: Eine Untersuchung der generischen / polytypischen Programmierung in Scala von Miles Sabin.

• Sing , eine Metaprogrammierbibliothek auf Typebene in Scala.
• Der Beginn der Programmierung auf Typebene in Scala

Scalaz hat Quellcode, ein Wiki und Beispiele.