Name
Abstract | ||
|---|---|---|
Guarded recursion in the sense of Nakano allows general recursive types and terms to be added to type theory without breaking consistency. Recent work has demonstrated applications of guarded recursion such as programming with codata, reasoning about coinductive types, as well as constructing and reasoning about denotational models of general recursive types. Guarded recursion can also be used as an abstract form of step-indexing for reasoning about programming languages with advanced features. Ultimately, we would like to have an implementation of a type theory with guarded recursion in which all these applications can be carried out and machine-checked. In this paper, we take a step towards this goal by devising a suitable reduction semantics. We present Clocked Type Theory, a new type theory for guarded recursion that is more suitable for reduction semantics than the existing ones. We prove confluence, strong normalisation and canonicity for its reduction semantics, constructing the theoretical basis for a future implementation. We show how coinductive types as exemplified by streams can be encoded, and derive that the type system ensures productivity of stream definitions. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/LICS.2017.8005097 | 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) |
Keywords | Field | DocType |
denotational models,guarded recursion,programming languages,clocked type theory,reduction semantics | Discrete mathematics,Computer science,Type theory,Coinduction,Mutual recursion,Semantics,Recursion | Conference |
ISBN | Citations | PageRank |
978-1-5090-3019-4 | 5 | 0.44 |
References | Authors | |
24 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Patrick Bahr | 1 | 63 | 8.82 |
| Hans Bugge Grathwohl | 2 | 35 | 2.88 |
| Rasmus Ejlers Møgelberg | 3 | 204 | 16.63 |