A model of guarded recursion with clock synchronisation
- Aleš Bizjak,
- Aalborg University,
Research Output:
Journal Article or Conference Article in Journal
Journal article
Peer-reviewOpen access
Publication Information
Output type
Research Output:
Journal Article or Conference Article in Journal
Journal article
Peer-reviewOriginal language
EnglishPages from-to (Number of pages)
Pages 83-101Journal (Volume, Issue Number)
Electronic Notes in Theoretical Computer Science (Volume 319)Publication milestones
- Published - 2015
Publication status
Published - 2015
ISSN
1571-0661Publication IDs
- Scopus: 84951830208
Abstract
Guarded recursion is an approach to solving recursive type equations where the type variable appears guarded by a modality to be thought of as a delay for one time step. Atkey and McBride proposed a calculus in which guarded recursion can be used when programming with coinductive data, allowing productivity to be captured in types. The calculus uses clocks representing time streams and clock quantifiers which allow limited and controlled elimination of modalities. The calculus has since been extended to dependent types by Møgelberg. Both works give denotational semantics but no rewrite semantics.
In previous versions of this calculus, different clocks represented separate time streams and clock synchronisation was prohibited. In this paper we show that allowing clock synchronisation is safe by constructing a new model of guarded recursion and clocks. This result will greatly simplify the type theory by removing freshness restrictions from typing rules, and is a necessary step towards defining rewrite semantics, and ultimately implementing the calculus.
In previous versions of this calculus, different clocks represented separate time streams and clock synchronisation was prohibited. In this paper we show that allowing clock synchronisation is safe by constructing a new model of guarded recursion and clocks. This result will greatly simplify the type theory by removing freshness restrictions from typing rules, and is a necessary step towards defining rewrite semantics, and ultimately implementing the calculus.
Publication metrics
PlumX, opens in new tab
Captures
4
Citations
13
Access to documents
Accepted author manuscript, 376.78 KB
