Recursion over objects of functional type

Abstract

This paper presents an extension of the simply typed λ-calculus that allows iteration and case reasoning over terms of functional types that arise when using higher order abstract syntax. This calculus aims at being the kernel for a type theory in which the user will be able to formalize logics or formal systems using the LF methodology, while taking advantage of new induction and recursion principles, extending the principles available in a calculus such as the Calculus of Inductive Constructions. The key idea of our system is the use of modal logic S4. We present here the system, its typing rules and reduction rules. The system enjoys the decidability of typability, soundness of typed reduction with respect to the typing rules, the Church–Rosser and strong normalization properties and it is a conservative extension over the simply typed λ-calculus. These properties entail the preservation of the adequacy of encodings.