Gibt es einen Grund, warum Scala abhängige Typen nicht explizit unterstützt?

Es gibt Weg abhängige Typen und ich denke , dass es möglich ist , fast alle Funktionen solcher Sprachen als Epigramm oder Agda in Scala zum Ausdruck bringen, aber ich frage mich , warum Scala nicht unterstützt dies ausdrücklich mehr , wie es sehr gut funktioniert in anderen Bereichen (zB , DSLs)? Fehlt mir etwas wie "es ist nicht nötig"?

Abgesehen von der syntaktischen Bequemlichkeit bedeutet die Kombination von Singleton-Typen, pfadabhängigen Typen und impliziten Werten, dass Scala die abhängige Typisierung überraschend gut unterstützt, wie ich versucht habe, in formlos zu demonstrieren .

Die eigentliche Unterstützung von Scala für abhängige Typen erfolgt über pfadabhängige Typen . Diese ermöglichen es einem Typ, von einem Auswahlpfad durch ein Objekt- (dh Wert-) Diagramm wie folgt abhängig zu sein.

scala> class Foo { class Bar }
defined class Foo

scala> val foo1 = new Foo
foo1: Foo = Foo@24bc0658

scala> val foo2 = new Foo
foo2: Foo = Foo@6f7f757

scala> implicitly[foo1.Bar =:= foo1.Bar] // OK: equal types
res0: =:=[foo1.Bar,foo1.Bar] = <function1>

scala> implicitly[foo1.Bar =:= foo2.Bar] // Not OK: unequal types
<console>:11: error: Cannot prove that foo1.Bar =:= foo2.Bar.
              implicitly[foo1.Bar =:= foo2.Bar]

Meiner Ansicht nach sollte das oben Genannte ausreichen, um die Frage zu beantworten: "Ist Scala eine abhängig getippte Sprache?" positiv: es ist klar, dass wir hier Typen haben, die sich durch die Werte unterscheiden, die ihre Präfixe sind.

Es wird jedoch häufig beanstandet, dass Scala keine "vollständig" abhängige Typsprache ist, da es keine abhängigen Summen- und Produkttypen gibt, wie sie in Agda oder Coq oder Idris als intrinsische Elemente zu finden sind. Ich denke, dies spiegelt in gewissem Maße eine Fixierung auf die Form gegenüber den Grundlagen wider. Dennoch werde ich versuchen zu zeigen, dass Scala diesen anderen Sprachen viel näher ist, als normalerweise anerkannt wird.

Trotz der Terminologie sind abhängige Summentypen (auch als Sigma-Typen bezeichnet) einfach ein Wertepaar, wobei der Typ des zweiten Werts vom ersten Wert abhängt. Dies ist direkt in Scala darstellbar,

scala> trait Sigma {
     |   val foo: Foo
     |   val bar: foo.Bar
     | }
defined trait Sigma

scala> val sigma = new Sigma {
     |   val foo = foo1
     |   val bar = new foo.Bar
     | }
sigma: java.lang.Object with Sigma{val bar: this.foo.Bar} = $anon$1@e3fabd8

Tatsächlich ist dies ein entscheidender Teil der Codierung abhängiger Methodentypen, die erforderlich ist, um vor 2.10 aus der 'Bakery of Doom' in Scala zu entkommen (oder früher über die experimentelle Scala-Compileroption -Ydependent-Methodentypen).

Abhängige Produkttypen (auch bekannt als Pi-Typen) sind im Wesentlichen Funktionen von Werten bis zu Typen. Sie sind der Schlüssel zur Darstellung statisch großer Vektoren und der anderen Aushängeschilder für abhängig typisierte Programmiersprachen. Wir können Pi-Typen in Scala mithilfe einer Kombination aus pfadabhängigen Typen, Singleton-Typen und impliziten Parametern codieren. Zuerst definieren wir ein Merkmal, das eine Funktion von einem Wert vom Typ T bis zu einem Typ U darstellen wird.

scala> trait Pi[T] { type U }
defined trait Pi

Wir können dann eine polymorphe Methode definieren, die diesen Typ verwendet,

scala> def depList[T](t: T)(implicit pi: Pi[T]): List[pi.U] = Nil
depList: [T](t: T)(implicit pi: Pi[T])List[pi.U]

(Beachten Sie die Verwendung des pfadabhängigen Typs pi.Uim Ergebnistyp List[pi.U]). Bei einem Wert vom Typ T gibt diese Funktion eine (n leere) Liste von Werten des Typs zurück, die diesem bestimmten T-Wert entsprechen.

Definieren wir nun einige geeignete Werte und implizite Zeugen für die funktionalen Beziehungen, die wir halten möchten.

scala> object Foo
defined module Foo

scala> object Bar
defined module Bar

scala> implicit val fooInt = new Pi[Foo.type] { type U = Int }
fooInt: java.lang.Object with Pi[Foo.type]{type U = Int} = $anon$1@60681a11

scala> implicit val barString = new Pi[Bar.type] { type U = String }
barString: java.lang.Object with Pi[Bar.type]{type U = String} = $anon$1@187602ae

Und jetzt ist hier unsere Pi-Typ-Funktion in Aktion:

scala> depList(Foo)
res2: List[fooInt.U] = List()

scala> depList(Bar)
res3: List[barString.U] = List()

scala> implicitly[res2.type <:< List[Int]]
res4: <:<[res2.type,List[Int]] = <function1>

scala> implicitly[res2.type <:< List[String]]
<console>:19: error: Cannot prove that res2.type <:< List[String].
              implicitly[res2.type <:< List[String]]
                    ^

scala> implicitly[res3.type <:< List[String]]
res6: <:<[res3.type,List[String]] = <function1>

scala> implicitly[res3.type <:< List[Int]]
<console>:19: error: Cannot prove that res3.type <:< List[Int].
              implicitly[res3.type <:< List[Int]]

(Beachten Sie, dass wir hier den <:<Subtyp-Zeugen-Operator von Scala verwenden, anstatt =:=weil res2.typeund res3.typeSingleton-Typen sind und daher genauer als die Typen, die wir auf der RHS überprüfen).

In der Praxis würden wir in Scala jedoch nicht damit beginnen, Sigma- und Pi-Typen zu codieren und dann von dort fortzufahren, wie wir es in Agda oder Idris tun würden. Stattdessen würden wir pfadabhängige Typen, Singleton-Typen und Implizite direkt verwenden. Sie finden zahlreiche Beispiele dafür, wie sich dies in formlosen Spielen auswirkt : Typen mit Größe , erweiterbare Datensätze , umfassende HL-Listen , Verschrottung Ihrer Heizplatte , generische Reißverschlüsse usw. usw.

Der einzige verbleibende Einwand, den ich sehen kann, ist, dass bei der obigen Codierung von Pi-Typen die Singleton-Typen der abhängigen Werte zum Ausdruck gebracht werden müssen. Leider ist dies in Scala nur für Werte von Referenztypen möglich und nicht für Werte von Nichtreferenztypen (insbesondere z. B. Int). Das ist schade, aber keine intrinsische Schwierigkeit: Scala Typprüfer intern die Singleton Arten von Nicht-Referenzwerten dar, und es gibt ein gewesen Paar von Experimenten direkt ausdrückbar zu machen. In der Praxis können wir das Problem mit einer ziemlich standardmäßigen Codierung der natürlichen Zahlen auf Typebene umgehen .

Auf jeden Fall glaube ich nicht, dass diese geringfügige Domain-Einschränkung als Einwand gegen Scalas Status als abhängig typisierte Sprache verwendet werden kann. Wenn dies der Fall ist, könnte das Gleiche für die abhängige ML gesagt werden (die nur Abhängigkeiten von natürlichen Zahlenwerten zulässt), was eine bizarre Schlussfolgerung wäre.

Ich würde annehmen, dass es daran liegt, dass (wie ich aus Erfahrung weiß, abhängige Typen im Coq-Proof-Assistenten verwendet zu haben, der sie vollständig unterstützt, aber immer noch nicht auf sehr bequeme Weise) abhängige Typen eine sehr fortgeschrittene Programmiersprachenfunktion sind, die wirklich schwer zu erreichen ist richtig machen - und kann in der Praxis zu einer exponentiellen Zunahme der Komplexität führen. Sie sind immer noch ein Thema der Informatikforschung.

Ich glaube, dass Scalas pfadabhängige Typen nur Σ-Typen darstellen können, aber keine Π-Typen. Dies:

trait Pi[T] { type U }

ist nicht gerade ein Π-Typ. Per Definition ist der Π-Typ oder das abhängige Produkt eine Funktion, deren Ergebnistyp vom Argumentwert abhängt und den universellen Quantifizierer darstellt, dh ∀x: A, B (x). Im obigen Fall hängt es jedoch nur vom Typ T ab, nicht jedoch von einem Wert dieses Typs. Das Pi-Merkmal selbst ist ein Σ-Typ, ein existenzieller Quantifizierer, dh ∃x: A, B (x). Die Selbstreferenz des Objekts fungiert in diesem Fall als quantifizierte Variable. Wenn es jedoch als impliziter Parameter übergeben wird, wird es auf eine normale Typfunktion reduziert, da es typweise aufgelöst wird. Die Codierung für abhängige Produkte in Scala sieht möglicherweise folgendermaßen aus:

trait Sigma[T] {
  val x: T
  type U //can depend on x
}

// (t: T) => (∃ mapping(x, U), x == t) => (u: U); sadly, refinement won't compile
def pi[T](t: T)(implicit mapping: Sigma[T] { val x = t }): mapping.U 

Das fehlende Teil hier ist die Fähigkeit, das Feld x statisch auf den erwarteten Wert t zu beschränken und effektiv eine Gleichung zu bilden, die die Eigenschaft aller Werte darstellt, die den Typ T bewohnen Es entsteht eine Logik, in der unsere Gleichung ein zu beweisender Satz ist.

Nebenbei bemerkt, im realen Fall kann der Satz höchst trivial sein, bis zu dem Punkt, an dem er nicht automatisch aus dem Code abgeleitet oder ohne erheblichen Aufwand gelöst werden kann. Man kann sogar die Riemann-Hypothese auf diese Weise formulieren, nur um festzustellen, dass die Signatur nicht implementiert werden kann, ohne sie tatsächlich zu beweisen, für immer zu schleifen oder eine Ausnahme auszulösen.

Bei der Frage ging es darum, abhängig typisierte Funktionen direkter zu verwenden, und meiner Meinung nach wäre ein direkter abhängiger Typisierungsansatz von Vorteil als das, was Scala bietet.
Aktuelle Antworten versuchen, die Frage auf typentheoretischer Ebene zu argumentieren. Ich möchte es pragmatischer gestalten. Dies könnte erklären, warum Menschen in Bezug auf die Unterstützung abhängiger Typen in der Scala-Sprache gespalten sind. Wir haben vielleicht etwas andere Definitionen im Sinn. (um nicht zu sagen, man ist richtig und man ist falsch).

Dies ist kein Versuch, die Frage zu beantworten, wie einfach es wäre, Scala in etwas wie Idris zu verwandeln (ich stelle mir das sehr schwer vor) oder eine Bibliothek zu schreiben, die direktere Unterstützung für Idris-ähnliche Fähigkeiten bietet (wie singletonsVersuche, in Haskell zu sein).

Stattdessen möchte ich den pragmatischen Unterschied zwischen Scala und einer Sprache wie Idris hervorheben.
Was sind Codebits für Ausdrücke auf Wert- und Typebene? Idris verwendet denselben Code, Scala verwendet sehr unterschiedlichen Code.

Scala (ähnlich wie Haskell) kann möglicherweise viele Berechnungen auf Typebene codieren. Dies wird von Bibliotheken wie gezeigt shapeless. Diese Bibliotheken machen es mit einigen wirklich beeindruckenden und cleveren Tricks. Ihr Code auf Typebene unterscheidet sich jedoch (derzeit) erheblich von Ausdrücken auf Wertebene (ich finde, dass diese Lücke in Haskell etwas enger ist). Mit Idris kann der Ausdruck auf Wertebene auf der Typebene AS IS verwendet werden.

Der offensichtliche Vorteil ist die Wiederverwendung von Code (Sie müssen Ausdrücke auf Typebene nicht getrennt von der Wertebene codieren, wenn Sie sie an beiden Stellen benötigen). Es sollte viel einfacher sein, Code auf Wertebene zu schreiben. Es sollte einfacher sein, sich nicht mit Hacks wie Singletons befassen zu müssen (ganz zu schweigen von den Leistungskosten). Sie müssen nicht zwei Dinge lernen, Sie lernen eine Sache. Auf einer pragmatischen Ebene brauchen wir am Ende weniger Konzepte. Typensynonyme, Typfamilien, Funktionen, ... wie wäre es nur mit Funktionen? Meiner Meinung nach gehen diese vereinheitlichenden Vorteile viel tiefer und sind mehr als syntaktische Bequemlichkeit.

Betrachten Sie den verifizierten Code. Siehe:
https://github.com/idris-lang/Idris-dev/blob/v1.3.0/libs/contrib/Interfaces/Verified.idr
Die Typprüfung überprüft die Beweise für Monaden- / Funktor- / Anwendungsgesetze und die Beweise sind tatsächlich Implementierungen von Monade / Funktor / Anwendbar und nicht irgendeiner äquivalenten äquivalenten Typstufe, die gleich oder nicht gleich sein kann. Die große Frage ist, was wir beweisen.

Das gleiche kann ich mit cleveren Codierungstricks tun (siehe unten für die Haskell-Version, ich habe keine für Scala gesehen)
https://blog.jle.im/entry/verified-instances-in-haskell.html
https: // github.com/rpeszek/IdrisTddNotes/wiki/Play_FunctorLaws,
außer dass die Typen so kompliziert sind, dass die Gesetze schwer zu erkennen sind. Die Ausdrücke auf Wertebene werden (automatisch, aber immer noch) in Dinge auf Textebene konvertiert, und Sie müssen dieser Konvertierung ebenfalls vertrauen . In all dem gibt es Raum für Fehler, was dem Zweck des Compilers, der als Proof-Assistent fungiert, irgendwie widerspricht.

(EDITIERT 2018.8.10) In Bezug auf die Unterstützung von Beweisen ist hier ein weiterer großer Unterschied zwischen Idris und Scala. In Scala (oder Haskell) gibt es nichts, was verhindern könnte, dass unterschiedliche Beweise geschrieben werden:

case class Void(underlying: Nothing) extends AnyVal //should be uninhabited
def impossible() : Void = impossible()

während Idris ein totalSchlüsselwort hat, das das Kompilieren von Code wie diesem verhindert.

Eine Scala-Bibliothek, die versucht, Code auf Werte- und Textebene zu vereinheitlichen (wie Haskell singletons), wäre ein interessanter Test für die Unterstützung abhängiger Typen durch Scala. Kann eine solche Bibliothek in Scala aufgrund pfadabhängiger Typen viel besser gemacht werden?

Ich bin zu neu für Scala, um diese Frage selbst zu beantworten.