TY - GEN

T1 - Guarded Dependent Type Theory with Coinductive Types

AU - Bizjak, Ales

AU - Grathwohl, Hans Bugge

AU - Clouston, Ranald

AU - Møgelberg, Rasmus Ejlers

AU - Birkedal, Lars

PY - 2016

Y1 - 2016

N2 - We present guarded dependent type theory, gDTT, an extensional dependent type theory with a ‘later’ modality and clock quantifiers for programming and proving with guarded recursive and coinductive types. The later modality is used to ensure the productivity of recursive definitions in a modular, type based, way. Clock quantifiers are used for controlled elimination of the later modality and for encoding coinductive types using guarded recursive types. Key to the development of gDTT are novel type and term formers involving what we call ‘delayed substitutions’. These generalise the applicative functor rules for the later modality considered in earlier work, and are crucial for programming and proving with dependent types. We show soundness of the type theory with respect to a denotational model.

AB - We present guarded dependent type theory, gDTT, an extensional dependent type theory with a ‘later’ modality and clock quantifiers for programming and proving with guarded recursive and coinductive types. The later modality is used to ensure the productivity of recursive definitions in a modular, type based, way. Clock quantifiers are used for controlled elimination of the later modality and for encoding coinductive types using guarded recursive types. Key to the development of gDTT are novel type and term formers involving what we call ‘delayed substitutions’. These generalise the applicative functor rules for the later modality considered in earlier work, and are crucial for programming and proving with dependent types. We show soundness of the type theory with respect to a denotational model.

KW - guarded dependent type theory

KW - later modality

KW - clock quantifiers

KW - guarded recursive types

KW - coinductive types

U2 - 10.1007/978-3-662-49630-5_2

DO - 10.1007/978-3-662-49630-5_2

M3 - Article in proceedings

T3 - Lecture Notes in Computer Science

SP - 20

EP - 35

BT - Foundations of Software Science and Computation Structure

PB - Springer

ER -