Une raison pour laquelle Scala ne prend pas explicitement en charge les types dépendants?

Il existe des types dépendant du chemin et je pense qu’il est possible d’exprimer presque toutes les caractéristiques de langages tels que Epigram ou Agda dans Scala, mais je me demande pourquoi Scala ne le supporte pas plus explicitement comme dans d’autres domaines , DSL)? Quelque chose me manque-t-il comme “ce n’est pas nécessaire”?

Outre la commodité de la syntaxe, la combinaison des types singleton, des types dépendant du chemin et des valeurs implicites signifie que Scala prend étonnamment en charge le typage dépendant, comme j’ai essayé de le démontrer dans shapeless .

Le support insortingnsèque de Scala pour les types dépendants se fait via des types dépendant du chemin . Celles-ci permettent à un type de dépendre d’un chemin de sélecteur via un graphe d’object (c.-à-d. Valeur-) comme cela,

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] =  scala> implicitly[foo1.Bar =:= foo2.Bar] // Not OK: unequal types :11: error: Cannot prove that foo1.Bar =:= foo2.Bar. implicitly[foo1.Bar =:= foo2.Bar] 

À mon avis, ce qui précède devrait suffire à répondre à la question “Scala est-il un langage dépendant de façon fiable?” dans le positif: il est clair que nous avons ici des types qui se distinguent par les valeurs qui sont leurs préfixes.

Cependant, il est souvent objecté que Scala n’est pas un langage de type “totalement” dépendant, car il ne comporte pas de types de sum et de produits dépendants, tels que ceux trouvés dans Agda, Coq ou Idris en tant qu’insortingnsèques. Je pense que cela reflète dans une certaine mesure une fixation de la forme sur les fondamentaux, néanmoins, je vais essayer de montrer que Scala est beaucoup plus proche de ces autres langues que ce qui est généralement reconnu.

Malgré la terminologie, les types de sum dépendante (également appelés types Sigma) sont simplement une paire de valeurs où le type de la deuxième valeur dépend de la première valeur. Ceci est directement représentable à Scala,

 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 

et en fait, il s’agit d’une partie cruciale de l’ encodage des types de méthodes dépendantes nécessaires pour échapper à ‘Bakery of Doom’ dans Scala avant 2.10 (ou plus tôt via l’option de compilation Scala de type -Ydependent-method types).

Les types de produits dépendants (aussi appelés types Pi) sont essentiellement des fonctions allant des valeurs aux types. Ils sont essentiels à la représentation des vecteurs de taille statique et des autres affiches pour les langages de programmation dépendant de manière dépendante. Nous pouvons encoder les types Pi en Scala en utilisant une combinaison de types dépendant du chemin, de types singleton et de parameters implicites. Nous définissons d’abord un trait qui va représenter une fonction d’une valeur de type T à un type U,

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

Nous pouvons définir une méthode polymorphe qui utilise ce type,

 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] 

(notez l’utilisation du type pi.U dépendant du pi.U dans le type de résultat List[pi.U] ). Étant donné une valeur de type T, cette fonction renverra une liste (n vide) de valeurs du type correspondant à cette valeur T particulière.

Définissons maintenant des valeurs appropriées et des témoins implicites pour les relations fonctionnelles que nous souhaitons maintenir,

 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 barSsortingng = new Pi[Bar.type] { type U = Ssortingng } barSsortingng: java.lang.Object with Pi[Bar.type]{type U = Ssortingng} = $anon$1@187602ae 

Et maintenant, voici notre fonction d’utilisation du type Pi en action,

 scala> depList(Foo) res2: List[fooInt.U] = List() scala> depList(Bar) res3: List[barSsortingng.U] = List() scala> implicitly[res2.type <:< List[Int]] res4: <:<[res2.type,List[Int]] =  scala> implicitly[res2.type <:< List[String]] :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]] =  scala> implicitly[res3.type <:< List[Int]] :19: error: Cannot prove that res3.type <:< List[Int]. implicitly[res3.type <:< List[Int]] 

(Notez que nous utilisons ici l'opérateur de sous-type <:< de Scala plutôt que =:= parce que res2.type et res3.type sont des types singleton et donc plus précis que les types que nous vérifions sur le RHS).

En pratique, cependant, dans Scala, nous ne commencerions pas par encoder les types Sigma et Pi, puis nous procéderions comme nous le ferions dans Agda ou Idris. Au lieu de cela, nous utiliserions des types dépendant du chemin, des types singleton et des implicits directement. Vous pouvez trouver de nombreux exemples de la façon dont cela se joue dans informes: les types dimensionnés , les enregistrements extensibles , les HLists complètes , les chutes de votre passe-partout , les fermetures à glissière génériques , etc. etc.

La seule objection restante est que, dans l'encodage ci-dessus des types Pi, les types singleton des valeurs dépendantes doivent pouvoir être exprimés. Malheureusement, dans Scala, ceci n'est possible que pour les valeurs de types de référence et non pour les valeurs de types non référencés (en particulier, par exemple, Int). C'est une honte, mais pas une difficulté insortingnsèque: le vérificateur de types de Scala représente en interne les types uniques de valeurs non référencées, et il y a eu quelques expériences pour les rendre directement exprimables. En pratique, nous pouvons contourner le problème avec un encodage au niveau type assez standard des nombres naturels .

En tout cas, je ne pense pas que cette légère ressortingction de domaine puisse être utilisée comme une objection au statut de Scala en tant que langage typé de manière dépendante. Si tel est le cas, alors on pourrait dire la même chose pour ML dépendant (qui ne permet que des dépendances sur des valeurs numériques), ce qui serait une conclusion bizarre.

Je suppose que c’est parce que (comme je le sais par expérience, avoir utilisé des types dépendants dans l’assistant de preuve Coq, qui les supporte complètement mais pas de manière très pratique), les types dépendants sont très difficiles à comprendre. obtenir juste – et peut causer un éclatement exponentiel de la complexité dans la pratique. Ils sont toujours un sujet de recherche en informatique.

Je crois que les types dépendant du chemin de Scala ne peuvent représenter que les types Σ, mais pas les types Π. Ce:

 trait Pi[T] { type U } 

n’est pas exactement un type Π. Par définition, le type or, ou le produit dépendant, est une fonction dont le type de résultat dépend de la valeur de l’argument, représentant un quantificateur universel, c’est-à-dire ∀x: A, B (x). Dans le cas ci-dessus, cependant, cela dépend uniquement du type T, mais pas de certaines valeurs de ce type. Le trait Pi lui-même est un type,, un quantificateur existentiel, c’est-à-dire ∃x: A, B (x). L’auto-référence d’object dans ce cas agit comme une variable quantifiée. Lorsqu’il est passé en tant que paramètre implicite, il se réduit à une fonction de type ordinaire, car il est résolu par type. Le codage pour un produit dépendant dans Scala peut ressembler à ceci:

 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 comstack def pi[T](t: T)(implicit mapping: Sigma[T] { val x = t }): mapping.U 

La pièce manquante ici est la possibilité de contraindre statiquement le champ x à la valeur attendue t, formant efficacement une équation représentant la propriété de toutes les valeurs habitant le type T. Avec nos types Σ, utilisés pour exprimer l’existence d’un object avec une propriété donnée, la logique est formée, dans laquelle notre équation est un théorème à prouver.

En passant, dans la réalité, le théorème peut être hautement non sortingvial, jusqu’au point où il ne peut pas être automatiquement dérivé du code ou résolu sans effort significatif. On peut même formuler l’hypothèse de Riemann de cette manière, seulement pour trouver la signature impossible à mettre en œuvre sans le prouver, en bouclant pour toujours ou en lançant une exception.

La question portait sur l’utilisation plus directe de la fonctionnalité typée dépendante et, à mon avis, il y aurait un avantage à avoir une approche de saisie dépendante plus directe que celle proposée par Scala.
Les réponses actuelles tentent de défendre la question sur le niveau théorique. Je veux faire un tour plus pragmatique. Cela peut expliquer pourquoi les personnes sont divisées sur le niveau de prise en charge des types dépendants dans le langage Scala. Nous pouvons avoir des définitions quelque peu différentes en tête. (pour ne pas dire on a raison et on a tort).

Ce n’est pas une tentative de répondre à la question de savoir s’il serait facile de transformer Scala en Idris (j’imagine très difficile) ou d’écrire une bibliothèque offrant un support plus direct pour des fonctionnalités similaires à Idris (comme singletons tente d’être dans Haskell).

Au lieu de cela, je veux souligner la différence pragmatique entre Scala et un langage comme Idris.
Que sont les bits de code pour les expressions de valeur et de niveau de type? Idris utilise le même code, Scala utilise un code très différent.

Scala (similaire à Haskell) peut être capable de coder de nombreux calculs de niveau. Ceci est montré par des bibliothèques comme shapeless . Ces bibliothèques le font en utilisant des astuces vraiment impressionnantes et intelligentes. Cependant, leur code de niveau de type est (actuellement) assez différent des expressions de niveau de valeur (je trouve que cet écart est un peu plus proche dans Haskell). Idris permet d’utiliser une expression de niveau de valeur au niveau du type AS IS.

L’avantage évident est la réutilisation du code (vous n’avez pas besoin de coder les expressions de niveau de type séparément du niveau de valeur si vous en avez besoin aux deux endroits). Il devrait être beaucoup plus facile d’écrire du code de niveau de valeur. Il devrait être plus facile de ne pas avoir à traiter avec des hacks comme singletons (sans parler des coûts de performance). Vous n’avez pas besoin d’apprendre deux choses que vous apprenez une chose. Au niveau pragmatique, nous finissons par avoir besoin de moins de concepts. Tapez les synonymes, tapez les familles, les fonctions,… que diriez-vous des fonctions? À mon avis, ces avantages unificateurs vont beaucoup plus loin et sont plus que pratiques.

Considérer le code vérifié. Voir:
https://github.com/idris-lang/Idris-dev/blob/v1.3.0/libs/consortingb/Interfaces/Verified.idr
Le vérificateur de type vérifie les preuves des lois monadiques / foncteurs / applicatives et les preuves concernent les implémentations réelles de monad / functor / applicative et non un équivalent de niveau de type codé qui peut être identique ou différent. La grande question est que prouvons-nous?

La même chose peut-on faire en utilisant des astuces d’encodage intelligentes (voir ce qui suit pour la version Haskell, je n’en ai pas vu pour Scala)
https://blog.jle.im/entry/verified-instances-in-haskell.html
https://github.com/rpeszek/IdrisTddNotes/wiki/Play_FunctorLaws
sauf que les types sont si compliqués qu’il est difficile de voir les lois, les expressions de niveau de valeur sont converties (automatiquement mais quand même) pour saisir des éléments de niveau et vous devez également faire confiance à cette conversion. Il y a de la place pour une erreur dans tout cela, ce qui défie un peu le but du compilateur agissant comme assistant de preuve.

(EDITED 2018.8.10) En parlant d’assistance à la preuve, voici une autre grande différence entre Idris et Scala. Il n’y a rien dans Scala (ou Haskell) qui puisse empêcher d’écrire des preuves divergentes:

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

tandis que Idris a total code de prévention des mots clés comme celui-ci de la compilation.

Une bibliothèque Scala qui essaie d’unifier le code de valeur et de type (comme les singletons Haskell) serait un test intéressant pour la prise en charge des types dépendants par Scala. Une telle bibliothèque peut-elle être beaucoup mieux réalisée à Scala en raison des types dépendant du chemin?

Je suis trop nouveau à Scala pour répondre à cette question moi-même.