Abstract-We define a monadic translation of type theory, called the weaning translation, that allows for a large range of effects in dependent type theory-such as exceptions, nontermination, non-determinism or writing operations. Through the light of a call-by-push-value decomposition, we explain why the traditional approach fails with type dependency and justify our approach. Crucially, the construction requires that the universe of algebras of the monad forms itself an algebra. The weaning translation applies to a version of the Calculus of Inductive Constructions (CIC) with a restricted version of dependent elimination. Finally, we show how to recover a translation of full CIC by mixing parametricity techniques with the weaning translation. This provides the first effectful version of CIC. The gap between type theories such as CIC and mainstream programming languages comes to a large extent from the absence of effects in type theories, because of their complex interaction with dependency. For instance, it has already been noticed that inductive types and dependent elimination do not scale well to CPS translations and classical logic [1], [2] . Furthermore, the traditional way to integrate effects in functional programming using monads does not scale to dependency because the monad leaks into the type during substitution. In this paper, we propose Baclofen Type Theory (BTT), a stripped-down version of CIC, and we provide generic notion of syntactic models 1 of it that allows for a large range of effects in dependent type theory-exceptions, non-termination, non-determinism or writing operations. BTT has a restricted version of dependent elimination to overcome the difficulty to marry effect and dependency. The syntactic models are given by the weaning translation of BTT into CIC, using a variant of the traditional monadic translation. The need for this variant can be explained by analyzing the call-by-push-value (CBPV) decomposition of call-by-value and call-by-name reduction strategies. Crucially, our construction requires that the universe of algebras of the monad itself forms an algebra. A monad satisfying this property is said to be self-algebraic. We then show how very common monads satisfy this property and thus give rise to effects that can be integrated to BTT. Finally, by mixing parametricity techniques with the weaning translation, we show how to recover a translation of full CIC, giving rise to the first effectful version of CIC.
This class of translation works on all CIC but for a restricted version of dependent elimination, identical to the Baclofen type theory REF .
An effectful way to eliminate addiction to dependence
2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Computer Science