2017 · 22 citations · 11 references
ComputingComputer ScienceAlgebraFormal MethodsProgramming LanguagesAbstract AlgebraCompositional SemanticsType CheckingType SystemsDependent TypesMonadic EffectsMonadic SemanticsMonadsParametricityType TheoryTyped Lambda Calculus
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, non-termination, 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.
11
Notions of computation and monads
Eugenio Moggi · Information and Computation · 1991 · 1.7K citations
Philip Wadler · 1989 · 776 citations
Types, Abstraction and Parametric Polymorphism.
John Reynolds · IFIP Congress · 1983 · 771 citations
General Recursion via Coinductive Types
Venanzio Capretta · Logical Methods in Computer Science · 2005 · 140 citations · Full text
Computing, Computer Science, Algebra +12