Quelles langues de recherche ont un système typographique plus fort que Haskell et pourquoi?

14

Ici, je lis cela:

Haskell n'a certainement pas le système de type le plus avancé (même pas si vous comptez les langues de recherche), mais parmi toutes les langues réellement utilisées dans la production, Haskell est probablement au sommet.

Je demande donc deux choses:

  1. quels langages de recherche ont des systèmes de types plus puissants que Haskell;
  2. qu'est-ce qu'ils améliorent.

Je suis juste un programmeur, donc je ne connais pas beaucoup d'objets mathématiques utilisés dans la théorie des types, veuillez fournir des explications douces si vous le pouvez.

Виталий Олегович
la source
3
Ce qui est mieux"?
David Richerby
2
@DavidRicherby Je suppose que cela signifie un système de type plus puissant
Виталий Олегович
2
Une fois que vous avez prouvé qu'un système de type est complet de Turing, est- ce vraiment important? ;-)
DevSolar
7
Les machines de Turing sont complètes de Turing, pourquoi ne les utilisez-vous pas pour vos tâches de programmation quotidiennes?
gallais
4
Veuillez noter que le texte original mentionne les langues avec des systèmes de type plus avancés et ne fait aucune affirmation si «plus avancé» est meilleur ou pire pour un système de type.
Peteris

Réponses:

25

La question est quelque peu problématique, car elle repose sur une définition subjective de «mieux».

Langages de type dépendants tels que Agda , Idris et Coq ont un système de type plus fort que Haskell. Cela signifie que vous pouvez utiliser les types de ces langages pour prouver strictement plus de propriétés de votre code qu'en Haskell. Autrement dit, il y a plus de programmes incorrects qui seront interceptés.

Cependant, cela a un prix: l'inférence de type et le test de l'existence de valeurs d'un type donné ne sont plus possibles. Cela signifie que pour ces langues, vous devez annoter explicitement votre code avec les types. Essentiellement, cela se résume à écrire vos propres preuves d'exactitude pour votre code.

Ces langues sont-elles donc "meilleures" que Haskell? Ils peuvent vérifier les preuves avancées de l'exactitude de votre code, mais ils ne peuvent pas prouver automatiquement les propriétés de votre code comme le peut Haskell.

Un autre langage de recherche qui est "meilleur" que Haskell est LiquidHaskell . Il s'agit essentiellement de Haskell avec des types de raffinement boulonnés sur le dessus, analysés à partir de commentaires spéciaux.

Les types de raffinement vous permettent d'affiner les types avec des propriétés. Par exemple, au lieu d'avoir un Int, vous pouvez spécifier {i : Int | i > 0}, en donnant le type de tous les entiers positifs. L'inférence de type est décidable avec les types de raffinement, mais vous ne pouvez pas prouver avec eux autant de propriétés d'exactitude que vous le pouvez avec les types dépendants.

Il existe d'autres systèmes de raffinement, mais je ne connais pas très bien l'un d'eux.

jmite
la source
Je vous remercie! Est-il possible de prouver que le système de type Haskell est le plus solide qui permet toujours l'inférence de type?
Виталий Олегович
3
Haskell n'est certainement pas le plus fort qui permette l'inférence de type. Les types de raffinement que j'ai mentionnés permettent l'inférence de type, et de nombreuses extensions GHC sont ajoutées à Haskell, ce qui permet un système de type légèrement plus solide.
jmite
4
En plus de cela, il existe de nombreux systèmes de types, et beaucoup sont incomparables: ils seront plus forts que Haskell à certains égards, mais plus faibles que Haskell à d'autres. Il n'y a pas d'ordre linéaire des systèmes de types du plus fort au plus faible.
jmite
5
Maintenant, je veux prouver qu'il n'y a pas de système de type le plus puissant qui permette l'inférence de type. Doit résister à prouver des faits inutiles.
Andrej Bauer
1
Le fait ne me semble pas inutile. La connaissance qu'il existe un système de type le plus solide avec inférence de type serait d'un grand intérêt, surtout s'il s'avérait possible de le mettre en œuvre.
rationalis
10

La famille de langages ML (StandardML, OCaml ) est issue d'une tradition similaire à Haskell et a donc des systèmes de types similaires. Cependant, ils ne sont pas exactement les mêmes que Haskell, et certaines de leurs fonctionnalités pourraient vous convenir mieux (il n'existe pas de système de type objectivement meilleur car les systèmes de type dans les langages de programmation existent pour aider les humains ). Voici quelques fonctionnalités d'OCaml que Haskell n'a pas (mais pourrait avoir un concept similaire correspondant), ou Haskell n'a mais fait différemment:

  1. Variantes polymorphes .
  2. Objets avec sous - typage en profondeur et classes .
  3. Les foncteurs , qui sont des cartes entre les modules (Haskell a des modules), et même des modules de première classe

Et s'il vous plaît, il n'est pas nécessaire de transformer cela en une fusillade ML-Haskell, sinon je vais commencer à créer un lien vers les articles de blog de Bob Harper ;-)

Andrej Bauer
la source
9

Le langage de recherche Clean a un meilleur système de types que Haskell, car il a des types d'unicité . Les idées derrière les types d'unicité sont étroitement liées à la logique linéaire , qui est plus proche du "monde réel" limité en ressources que la logique classique.

Le langage anti-recherche Rust possède également un système de caractères avec des caractéristiques uniques qui sont plus proches du «monde réel» que les systèmes classiques de type pur. La plupart des idées qui ont influencé le système de caractères ont été publiées complètement indépendantes de Rust bien avant son existence. Mais la façon dont ces vieilles idées sont rassemblées est unique et mériterait également de véritables publications de recherche, même s'il existe des lacunes et des incohérences connues.

Thomas Klimpel
la source
3
D'une certaine manière, «publié» et «anti-recherche» ne vont pas bien ensemble.
Andrej Bauer
1
L'unicité est certainement un concept intéressant, mais l'OMI concerne davantage la sémantique, plutôt qu'une fonctionnalité de système de type en tant que telle. Et cela rend-il vraiment le système de type strictement meilleur ? Est-ce que Clean peut faire les choses les plus récentes que Haskell a ajoutées à son système de types, le polymorphisme de rang supérieur, etc.
leftaroundabout
1
@leftaroundabout Dans quelle mesure connaissez-vous les types d'unicité ou la logique linéaire? Si x a un type unique, alors f (x, x) n'est pas bien typé, par exemple. Il peut être possible d'étendre Haskell pour prendre également en charge les types d'unicité. La sémantique de déplacement en C ++ peut également être considérée comme améliorant la prise en charge des types uniques au-dessus d'un système de types existant.
Thomas Klimpel
Je suis familier avec la sémantique des mouvements C ++, c'est peut-être pour cela que mon impression d'unicité est comme «pas grand chose d'un système de type». Ce que je trouverais intéressant, c'est que les types d'unicité complets se propageant vers l'extérieur entravent-ils les autres fonctionnalités du système de type avancé?
leftaroundabout
1
@leftaroundabout Les références Rvalue sonnent comme une chose de type système pour moi. Pourquoi les types d'unicité devraient-ils entraver d'autres fonctionnalités de type avancées? Dans le pire des cas, ces fonctionnalités avancées ne s'appliqueraient tout simplement pas aux types d'unicité. Bien sûr, les fonctionnalités du «monde réel» comme les types d'unicité signifient aller plus loin que la profondeur, et le temps que vous passez pour aller plus loin ne sera plus là pour aller plus loin. Mais j'ai l'impression que les types d'unicité offrent un bel équilibre entre la théorie et la pratique, donc je pense que le temps serait bien passé.
Thomas Klimpel