Guarded Dependent Type Theory with Coinductive Types

Ales Bizjak, Hans Bugge Grathwohl, Ranald Clouston, Rasmus Ejlers Møgelberg, Lars Birkedal

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


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.
Original languageEnglish
Title of host publicationFoundations of Software Science and Computation Structure : 19th International Conference, FOSSACS 2016, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2016, Eindhoven, The Netherlands, April 2-8, 2016, Proceedings
Number of pages16
Publication date2016
Publication statusPublished - 2016
SeriesLecture Notes in Computer Science


Dive into the research topics of 'Guarded Dependent Type Theory with Coinductive Types'. Together they form a unique fingerprint.

Cite this