Comment créer une fonction Haskell qui introduirait un nouveau type?

Question

J'écris actuellement un analyseur d'expression. J'ai fait l'analyse lexicale et syntaxique et maintenant je vérifie les types. Je l'expression dans une structire de données comme celui-ci (version simplifiée):

data Expr = EBinaryOp String Expr Expr 
      | EInt Int 
      | EFloat Float 

Et maintenant je besoin d'une fonction qui convertirait à un nouveau type, dites TypedExpr, qui contiendrait également des informations de type. Et maintenant mon problème principal est, comment ce type devrait ressembler. J'ai deux idées - avec paramètre de type:

data TypedExpr t = TEBinaryOp (TBinaryOp a b t) (TExpr a) (TExpr b) 
       | TEConstant t 
addTypes :: (ExprType t) => Expr -> TypedExpr t 

ou sans:

data TypedExpr = TEBinaryOp Type BinaryOp TypedExpr TypedExpr 
       | TEConstant Type Dynamic 
addTypes :: Expr -> TypedExpr 

J'ai commencé avec la première option, mais je suis tombé sur des problèmes, parce que cette approche suppose que vous connaissez le type de l'expression avant de l'analyser (pour moi, c'est vrai dans la plupart des cas, mais pas toujours). Cependant, je l'aime bien, car cela me permet d'utiliser le système de types de Haskell et de vérifier la plupart des erreurs au moment de la compilation.

Est-il possible de le faire avec la première option?
Lequel choisiriez-vous? Pourquoi?
À quels problèmes dois-je m'attendre avec chaque option?

Answer 1

Le type de votre fonction

addTypes :: Expr -> TypedExpr t 

est faux, parce que cela signifierait que vous obtenez un TypedExpr tpour tout t vous aimez. En revanche, ce que vous voulez réellement est unt particulier qui est déterminé par l'argument de type Expr.

Ce raisonnement montre déjà que vous allez au-delà des capacités du système de type Hindley-Milner. Après tout, le type de retour de addTypes doit dépendre de la valeur de l'argument, mais dans Haskell 2010, les types peuvent ne pas dépendre de valeurs. Par conséquent, vous avez besoin d'une extension du système de type qui vous rapproche de les types dépendants. Dans Haskell, les types de données algébriques généralisées (GADT) peuvent le faire. Pour une première introduction aux GADT, voir également my video on GADTs. Cependant, après vous être familiarisé avec les GADT, vous avez toujours le problème de l'analyse d'une expression non typée en une expression typée, c'est-à-dire.écrire une fonction

addTypes :: Expr -> (exists t. TypedExpr t) 

Bien sûr, vous devez effectuer un certain type vous vérifier, mais même alors, il est pas facile de convaincre le compilateur Haskell que vos chèques de type (qui se produisent au niveau de la valeur) peut être levé au niveau du type. Heureusement, d'autres personnes ont déjà pensé, voir par exemple le message suivant dans la liste de diffusion haskell-café:

Edward Kmett.
Re: Vérification manuelle du type pour fournir des instances de lecture pour les GADT. (a été Re: [Haskell-cafe] Lire par exemple pour GATD)
http://article.gmane.org/gmane.comp.lang.haskell.cafe/76466

(Quelqu'un sait-il d'un officiellement publié/référence bien rédigé?)

Answer 2

Depuis que vous faites l'analyse lors de l'exécution, pas le temps de compilation, vous ne pouvez pas ferroutage hors du système de type de Haskell (sauf si vous importez les modules correspondants et appeler manuellement vous-même.)

Vous voudrez peut-être se tourner vers les exemples ML de contrôleurs de type TAPL pour un simple calcul lambda pour l'inspiration. http://www.cis.upenn.edu/~bcpierce/tapl/ (sous implémentations). Ils font un peu plus que votre analyseur d'expression, puisque vous ne supportez pas lambdas.

Answer 3

J'ai récemment commencé à utiliser tagless-final syntax pour DSL embarqués, et je l'ai trouvé pour être beaucoup plus agréable que la méthode GADT standard (vers laquelle vous vous dirigez, et Apfelmus décrit).

La clé de la syntaxe finale sans balise est qu'au lieu d'utiliser un type de données d'expression, vous représentez des opérations avec une classe de type. Pour les fonctions comme votre eBinaryOp, je l'ai trouvé préférable d'utiliser deux classes:

class Repr repr where 
    eInt :: repr Int 
    eFloat :: repr Float 

class Repr repr => BinaryOp repr a b c where 
    eBinaryOp :: String -> repr a -> repr b -> repr c 

je ferais des fonctions de BinaryOp séparées plutôt que d'utiliser une chaîne bien. Il y a beaucoup plus d'informations sur Oleg's web page, y compris un analyseur qui utilise le système de type de Haskell.