Guarded Cubical Type Theory

Lars Birkedal; Aleš Bizjak; Ranald Clouston; Hans Bugge Grathwohl; Bas Spitters; Andrea Vezzosi

doi:10.1007/s10817-018-9471-7

Guarded Cubical Type Theory

Lars Birkedal, Aleš Bizjak, Ranald Clouston, Hans Bugge Grathwohl, Bas Spitters, Andrea Vezzosi

Department of Computer Science

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

13 Citations (Scopus)

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öf 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 C× D, where C is the cube category, and D is any small category with an initial object. We then show that the category of presheaves on C× ω provides semantics for GCTT.

Original language	English
Journal	Journal of Automated Reasoning
Volume	63
Issue	2
Pages (from-to)	211-253
Number of pages	43
ISSN	0168-7433
DOIs	https://doi.org/10.1007/s10817-018-9471-7 https://doi.org/10.1007/s10817-018-9471-7
Publication status	Published - 2019

Keywords

Cubical type theory
Guarded recursion
Homotopy type theory

Access to Document

10.1007/s10817-018-9471-7Licence: Unspecified
10.1007/s10817-018-9471-7

https://arxiv.org/pdf/1611.09263.pdf

Cite this

@article{f5cc73266f21402ab3f2488c0b2d43c9,

title = "Guarded Cubical Type Theory",

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{\"o}f 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 C× D, where C is the cube category, and D is any small category with an initial object. We then show that the category of presheaves on C× ω provides semantics for GCTT.",

keywords = "Cubical type theory, Guarded recursion, Homotopy type theory",

author = "Lars Birkedal and Ale{\v s} Bizjak and Ranald Clouston and Grathwohl, {Hans Bugge} and Bas Spitters and Andrea Vezzosi",

year = "2019",

doi = "10.1007/s10817-018-9471-7",

language = "English",

volume = "63",

pages = "211--253",

journal = "Journal of Automated Reasoning",

issn = "0168-7433",

publisher = "Springer",

number = "2",

}

TY - JOUR

T1 - Guarded Cubical Type Theory

AU - Birkedal, Lars

AU - Bizjak, Aleš

AU - Clouston, Ranald

AU - Grathwohl, Hans Bugge

AU - Spitters, Bas

AU - Vezzosi, Andrea

PY - 2019

Y1 - 2019

N2 - 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öf 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 C× D, where C is the cube category, and D is any small category with an initial object. We then show that the category of presheaves on C× ω provides semantics for GCTT.

AB - 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öf 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 C× D, where C is the cube category, and D is any small category with an initial object. We then show that the category of presheaves on C× ω provides semantics for GCTT.

KW - Cubical type theory

KW - Guarded recursion

KW - Homotopy type theory

UR - http://www.scopus.com/inward/record.url?scp=85049045653&partnerID=8YFLogxK

U2 - 10.1007/s10817-018-9471-7

DO - 10.1007/s10817-018-9471-7

M3 - Journal article

SN - 0168-7433

VL - 63

SP - 211

EP - 253

JO - Journal of Automated Reasoning

JF - Journal of Automated Reasoning

IS - 2

ER -

Guarded Cubical Type Theory

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this