License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSCD.2018.23
URN: urn:nbn:de:0030-drops-91938
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9193/
Go to the corresponding LIPIcs Volume Portal

Mannaa, Bassel ; Møgelberg, Rasmus Ejlers

The Clocks They Are Adjunctions Denotational Semantics for Clocked Type Theory

pdf-format:
LIPIcs-FSCD-2018-23.pdf (0.6 MB)

Abstract

Clocked Type Theory (CloTT) is a type theory for guarded recursion useful for programming with coinductive types, allowing productivity to be encoded in types, and for reasoning about advanced programming language features using an abstract form of step-indexing. CloTT has previously been shown to enjoy a number of syntactic properties including strong normalisation, canonicity and decidability of type checking. In this paper we present a denotational semantics for CloTT useful, e.g., for studying future extensions of CloTT with constructions such as path types.
The main challenge for constructing this model is to model the notion of ticks used in CloTT for coinductive reasoning about coinductive types. We build on a category previously used to model guarded recursion, but in this category there is no object of ticks, so tick-assumptions in a context can not be modelled using standard tools. Instead we show how ticks can be modelled using adjoint functors, and how to model the tick constant using a semantic substitution.

BibTeX - Entry

@InProceedings{mannaa_et_al:LIPIcs:2018:9193,
  author =	{Bassel Mannaa and Rasmus Ejlers M\ogelberg},
  title =	{{The Clocks They Are Adjunctions Denotational Semantics for Clocked Type Theory}},
  booktitle =	{3rd International Conference on Formal Structures for  Computation and Deduction (FSCD 2018)},
  pages =	{23:1--23:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-077-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{108},
  editor =	{H{\'e}l{\`e}ne Kirchner},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9193},
  URN =		{urn:nbn:de:0030-drops-91938},
  doi =		{10.4230/LIPIcs.FSCD.2018.23},
  annote =	{Keywords: Guarded type theory, Coinduction, Presheaf model, Clocked type theory, Dependent adjunction}
}

Keywords: Guarded type theory, Coinduction, Presheaf model, Clocked type theory, Dependent adjunction
Collection: 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI