Différence entre Haskell et Idris: Réflexion du Runtime / Compiletime dans les univers types

Question

Ainsi, dans Idris c'est parfaitement valable pour écrire la suite.

item : (b : Bool) -> if b then Nat else List Nat
item True  = 42
item False = [1,2,3] // cf. https://www.youtube.com/watch?v=AWeT_G04a0A

Sans la signature d'un type, cela ressemble à un typées dynamiquement de la langue. Mais, en effet, l'Idris est dépendante de typage. Le type concret de l' item b peut seulement être déterminé au cours de l'exécution.

C'est, bien sûr, un Haskell-programmeur de parler: - Le type d' item b dans l'Idris sens est donné lors de la compilation, c'est - if b then Nat ....

Maintenant, ma question: Suis-je en droit de conclure qu'en Haskell, la frontière entre l'exécution et la compile-time fonctionne exactement entre le monde des valeurs (False, "foo", 3) et le monde de types (Bool, String, Integer) alors que dans l'Idris, la frontière entre l'exécution et la compile-time va à travers les univers?

Aussi, suis-je en droit de supposer que, même avec des types dépendants en Haskell (à l'aide de DataKinds et TypeFamilies, cf. cet article) l'exemple ci-dessus est impossible en Haskell, parce que Haskell contrairement à Idris ne permettent pas de valeurs de fuite au niveau du type?

Answer 1

Oui, vous avez raison de constater que les types et les valeurs distinction dans Idris ne concordent pas avec l'compile-time-seulement contre runtime-et-compile-time distinction. C'est une bonne chose. Il est utile d'avoir des valeurs qui n'existent qu'au compile-time, tout comme dans le programme des logiques que nous avons "ghost variables" utilisé uniquement dans les spécifications. Il est également utile d'avoir le type de représentations au moment de l'exécution, permettant de type de données de programmation générique.

En Haskell, DataKinds (et PolyKinds) laissez-nous écrire

type family Cond (b :: Bool)(t :: k)(e :: k) :: k where
  Cond 'True  t e = t
  Cond 'False t e = e

et dans un avenir pas trop lointain, nous serons en mesure d'écrire

item :: pi (b :: Bool) -> Cond b Int [Int]
item True  = 42
item False = [1,2,3]

mais jusqu'à ce que cette technologie est mise en œuvre, nous avons à faire avec singleton faux dépendant des types de fonction, comme ceci:

data Booly :: Bool -> * where
  Truey  :: Booly 'True
  Falsey :: Booly 'False

item :: forall b. Booly b -> Cond b Int [Int]
item Truey  = 42
item Falsey = [1,2,3]

Vous pouvez obtenir de très loin avec un tel trucage, mais il serait tout obtenir beaucoup plus facile si nous avions la vraie chose.

Surtout, le plan de Haskell est de maintenir et de séparer forall et pi, en soutenant paramétrique et polymorphisme ad hoc, respectivement. Les lambdas et les applications qui vont avec forall peut toujours être effacé lors de l'exécution de la génération de code, tout comme maintenant, mais celles pour l' pi sont retenus. Il serait également judicieux d'avoir runtime type abstractions pi x :: * -> ... et jeter les rats nid de complexité, c'est - Data.Typeable dans la poubelle.

Answer 2

Maintenant, ma question: Suis-je en droit de conclure qu'en Haskell, la frontière entre le moment de l'exécution et de la compile-time fonctionne exactement entre le monde de valeurs (False, "foo", 3) et le monde de types (Bool, String, Entier) alors que dans l'Idris, la frontière entre l'exécution et la compile-time va à travers les univers?

Idris compile Épique (mise à JOUR: non, il n'est plus compilé Epis comme de Spearman est dit dans le commentaire ci-dessous):

Aucune vérification de la sémantique, autres que pour voir si les noms sont dans le champ d'application --- il est supposé que le langage de plus haut niveau sera effectué le typage, et en tout cas Épique ne doit pas faire des hypothèses sur le niveau supérieur de type système ou toutes les transformations que vous avez appliqué. Les annotations sont nécessaires, mais ils ne donnent des conseils pour la compilateur (je pourrais changer cela).

Donc, les types n'ont pas d'importance denotationally, c'est à dire la signification d'un terme ne dépend pas de son type. De plus, certains de la valeur de niveau, les choses peuvent être effacées, par exemple, en Vect n A (où Vect est le type de listes avec statiquement longueur connue) n (sur la longueur) peut être effacé, car

Il existe des méthodes décrites par Brady, McBride et McKinna dans BMM04 pour supprimer les indices de structures de données, en exploitant le fait que fonctions opérant sur eux déjà une copie de la indice approprié ou l'index peut être rapidement reconstruite en cas de besoin.

La chose ici est que l' pi dans Idris actes pour des types de pratiquement de la même manière qu' forall en Haskell: ils sont à la fois paramétrique (bien que, ces parametricities sont différentes) dans ce cas. Un compilateur peut utiliser les types d'optimiser le code, mais dans les deux langues de contrôle de flux ne dépend pas de types, c'est à dire que vous ne pouvez dire if A == Int then ... else ... (si, si A est dans la forme canonique, alors vous savez statiquement si c'est Int ou pas, et donc peut écrire A == Int, mais ce n'est pas affecter le flux de contrôle, parce que toutes les décisions sont maken avant l'exécution). Le type concret de l' item b seulement n'a pas d'importance lors de l'exécution.

Cependant, comme pigworker dit que c'est pas forcément paramétrique dans les types de. Comme il n'est pas nécessairement à être non-paramétrique dans les valeurs. Au niveau du Type de valeur niveau paramétrique et non-paramétrique sont complètement orthogonale de dichotomies. Voir cette réponse pour plus de détails.

Donc, Haskell et Idris sont différents dans leur manière de traiter le plan de la valeur des choses wrt runtime/compiler le contenu (parce que dans Idris, vous pouvez marquer un argument avec . à le faire effaçable), mais ils traitent les types à peu près de la même façon.