Tags:Coinduction, Cubical Type Theory, Denotational Semantics, Guarded Recursion, Higher Inductive Types, Presheaf Models of Type Theory and type theory
Abstract:
We present Clocked Cubical Type Theory, the first type theory combining multi-clocked guarded recursion with the features of Cubical Type Theory. Guarded recursion is an abstract form of step-indexing, which can be used for construction of advanced programming language models. In its multi-clocked version, it can also be used for coinductive programming and reasoning, encoding productivity in types. Combining this with Higher Inductive Types (HITs) this extends to coinductive types that are traditionally hard to represent in type theory, such as the type of finitely branching labelled transition systems.
Among our technical contributions is a new principle of induction under clocks, providing computational contents to one of the main axioms required for encoding coinductive types. This principle is verified using a denotational semantics in a presheaf model.
Greatest HITs: Higher Inductive Types in Coinductive Definitions via Induction Under Clocks