Hostname: page-component-8448b6f56d-42gr6 Total loading time: 0 Render date: 2024-04-19T18:16:21.678Z Has data issue: false hasContentIssue false

Type-based termination of recursive definitions

Published online by Cambridge University Press:  03 February 2004

G. BARTHE
Affiliation:
INRIA Sophia-Antipolis, 2004 route des Lucioles, BP 93, F-06902 Sophia-Antipolis Cedex, France
M. J. FRADE
Affiliation:
Dep. de Informática, Universidade do Minho, Campus de Gualtar, P-4710-057 Braga, Portugal
E. GIMÉNEZ
Affiliation:
Trusted Logic, 5 rue du Bailliage, F-78000 Versailles, France and Instituto de Computación, Universidad de la República, Julio Herrera y Reissig 565, 11300 Montevideo, Uruguay
L. PINTO
Affiliation:
Dep. de Matemática, Universidade do Minho, Campus de Gualtar, P-4710-057 Braga, Portugal
T. UUSTALU
Affiliation:
Dep. de Informática, Universidade do Minho, Campus de Gualtar, P-4710-057 Braga, Portugal and Institute of Cybernetics, Akadeemia tee 21, EE-12618 Tallinn, Estonia

Abstract

This paper introduces $\lambda^\widehat$, a simply typed lambda calculus supporting inductive types and recursive function definitions with termination ensured by types. The system is shown to enjoy subject reduction, strong normalisation of typable terms and to be stronger than a related system $\lambda_{\mathcal{G}}$ in which termination is ensured by a syntactic guard condition. The system can, at will, be extended to support coinductive types and corecursive function definitions also.

Type
Paper
Copyright
2004 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)