zbMATH — the first resource for mathematics

Intuitionistic ancestral logic as a dependently typed abstract programming language. (English) Zbl 06484965
Paiva, Valeria (ed.) et al., Logic, language, information, and computation. 22nd international workshop, WoLLIC 2015, Bloomington, IN, USA, July 20–23, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-47708-3/pbk; 978-3-662-47709-0/ebook). Lecture Notes in Computer Science 9160, 14-26 (2015).
Summary: It is well-known that concepts and methods of logic (more specifically constructive logic) occupy a central place in computer science. While it is quite common to identify ‘logic’ with ‘first-order logic’ (FOL), a careful examination of the various applications of logic in computer science reveals that FOL is insufficient for most of them, and that its most crucial shortcoming is its inability to provide inductive definitions in general, and the notion of the transitive closure in particular. The minimal logic that can serve for this goal is ancestral logic (AL).
In this paper, we define a constructive version of AL, pure intuitionistic ancestral logic (iAL), extending pure intuitionistic first-order logic (iFOL). This logic is a dependently typed abstract programming language with computational functionality beyond iFOL, given by its realizer for the transitive closure operator TC, which corresponds to recursive programs. We derive this operator from the natural type theoretic definition of TC using intersection type. We show that provable formulas in iAL are uniformly realizable, thus iAL is sound with respect to constructive type theory. We further outline how iAL can serve as a natural framework for reasoning about programs.
For the entire collection see [Zbl 1319.03010].
03B70 Logic in computer science
Full Text: DOI