Logical Combinators for Rich Type Systems
Résumé
We present a functional approach to design rich type systems based on an elegant logical representation of types. The representation is not only clean but avoids exponential increases in combined complexity due to subformula duplication. This opens the way for solving a wide range of problems such as subtyping in exponential-time even though their direct translation into the underlying logic results in an exponential blowup of the formula size, yielding an incorrectly presumed two-exponential time complexity.
Nous présentons une approche fonctionnelle pour concevoir des systèmes de types riches basée sur une représentation élégante et logique des types. La représentation n'est pas seulement propre, mais évite une augmentation exponentielle de la complexité en raison de duplication de sous-formules. Cela ouvre la voie pour résoudre un large éventail de problèmes tels que le sous-typage en temps simplement exponentiel, même si leur traduction directe dans la logique sous-jacente produit une explosion combinatoire de la taille de la formule, donnant une complexité en temps incorrectement présumée doublement exponentielle.
Domaines
Langage de programmation [cs.PL]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...