Guarded recursion in Agda via sized types

Niccolò Veltri, Niels van der Weide

Publikation: Artikel i tidsskrift og konference artikel i tidsskriftKonferenceartikelForskningpeer review

Abstract

In type theory, programming and reasoning with possibly non-terminating programs and potentially infinite objects is achieved using coinductive types. Recursively defined programs of these types need to be productive to guarantee the consistency of the type system. Proof assistants such as Agda and Coq traditionally employ strict syntactic productivity checks, which often make programming with coinductive types convoluted. One way to overcome this issue is by encoding productivity at the level of types so that the type system forbids the implementation of non-productive corecursive programs. In this paper we compare two different approaches to type-based productivity: guarded recursion and sized types. More specifically, we show how to simulate guarded recursion in Agda using sized types. We formalize the syntax of a simple type theory for guarded recursion, which is a variant of Atkey and McBride’s calculus for productive coprogramming. Then we give a denotational semantics using presheaves over the preorder of sizes. Sized types are fundamentally used to interpret the characteristic features of guarded recursion, notably the fixpoint combinator.
OriginalsprogEngelsk
Artikelnummer32
TidsskriftLeibniz International Proceedings in Informatics (LIPIcs)
Vol/bind131
Sider (fra-til)32:1–32:19
ISSN1868-8969
DOI
StatusUdgivet - 2019

Emneord

  • Type Theory
  • Coinductive Types
  • Productivity Encoding
  • Guarded Recursion
  • Sized Types

Fingeraftryk

Dyk ned i forskningsemnerne om 'Guarded recursion in Agda via sized types'. Sammen danner de et unikt fingeraftryk.

Citationsformater