Guarded cubical type theory
From MaRDI portal
Publication:2319985
DOI10.1007/S10817-018-9471-7zbMATH Open1477.03034arXiv1611.09263OpenAlexW2962873201MaRDI QIDQ2319985FDOQ2319985
Authors: Lars Birkedal, Aleš Bizjak, Ranald A. Clouston, Hans Bugge Grathwohl, Bas Spitters, Andrea Vezzosi 
Publication date: 21 August 2019
Published in: Journal of Automated Reasoning (Search for Journal in Brave)
Abstract: This paper improves the treatment of equality in guarded dependent type theory (GDTT), by combining it with cubical type theory (CTT). GDTT is an extensional type theory with guarded recursive types, which are useful for building models of program logics, and for programming and reasoning with coinductive types. We wish to implement GDTT with decidable type checking, while still supporting non-trivial equality proofs that reason about the extensions of guarded recursive constructions. CTT is a variation of Martin-L"of type theory in which the identity type is replaced by abstract paths between terms. CTT provides a computational interpretation of functional extensionality, enjoys canonicity for the natural numbers type, and is conjectured to support decidable type-checking. Our new type theory, guarded cubical type theory (GCTT), provides a computational interpretation of extensionality for guarded recursive types. This further expands the foundations of CTT as a basis for formalisation in mathematics and computer science. We present examples to demonstrate the expressivity of our type theory, all of which have been checked using a prototype type-checker implementation. We show that CTT can be given semantics in presheaves on the product of the cube category and a small category with an initial object. We then show that the category of presheaves on the product of the cube category and omega provides semantics for GCTT.
Full work available at URL: https://arxiv.org/abs/1611.09263
Recommendations
Presheaves and sheaves, stacks, descent conditions (category-theoretic aspects) (18F20) Abstract and axiomatic homotopy theory in algebraic topology (55U35) Type theory (03B38)
Cites Work
- Sheaves in geometry and logic: a first introduction to topos theory
- Rings of sets
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Homotopy type theory. Univalent foundations of mathematics
- Step-indexed Kripke models over recursive worlds
- Internal type theory
- Coproducts of De Morgan algebras
- Extensional Constructs in Intensional Type Theory
- The simplicial model of univalent foundations (after Voevodsky)
- Applicative programming with effects
- First steps in synthetic guarded domain theory: step-indexing in the topos of trees
- A formalized proof of strong normalization for guarded recursive types
- Guarded dependent type theory with coinductive types
- Cubical type theory: a constructive interpretation of the univalence axiom
- A type theory for productive coprogramming via guarded recursion
- Productive coprogramming with guarded recursion
- Intensional type theory with guarded recursive types qua fixed points on universes
- A model of guarded recursion with clock synchronisation
- Axioms for modelling cubical type theory in a topos
- The Guarded Lambda-Calculus: Programming and Reasoning with Guarded Recursion for Coinductive Types
- Canonicity for cubical type theory
- Guarded cubical type theory: path equality for guarded recursion
Cited In (15)
- Transpension: the right adjoint to the Pi-type
- Temporal refinements for guarded recursive types
- Formalizing CCS and \(\pi\)-calculus in Guarded Cubical Agda
- The Guarded Lambda-Calculus: Programming and Reasoning with Guarded Recursion for Coinductive Types
- Title not available (Why is that?)
- Cubical methods in homotopy type theory and univalent foundations
- Greatest HITs: higher inductive types in coinductive definitions via induction under clocks
- Cubical Agda: a dependently typed programming language with univalence and higher inductive types
- Denotational semantics for guarded dependent type theory
- Modal dependent type theory and dependent right adjoints
- Guarded dependent type theory with coinductive types
- Intensional type theory with guarded recursive types qua fixed points on universes
- Guarded cubical type theory: path equality for guarded recursion
- Syntax and models of Cartesian cubical type theory
- A stratified approach to Löb induction
Uses Software
This page was built for publication: Guarded cubical type theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2319985)
