Mathematical Structures in Computer Science



Paper

Modelling general recursion in type theory


ANA BOVE a1 and VENANZIO CAPRETTA a2
a1 Department of Computing Science, Chalmers University of Technology, 412 96 Göteborg, Sweden Email: bove@cs.chalmers.se
a2 Department of Mathematics and Statistics, University of Ottawa, 585 King Edward Ave., Ottawa, ON, K1N 6N5, Canada Email: venanzio.capretta@mathstat.uottawa.ca

Article author query
bove a   [Google Scholar] 
capretta v   [Google Scholar] 
 

Abstract

Constructive type theory is an expressive programming language in which both algorithms and proofs can be represented. A limitation of constructive type theory as a programming language is that only terminating programs can be defined in it. Hence, general recursive algorithms have no direct formalisation in type theory since they contain recursive calls that satisfy no syntactic condition guaranteeing termination. In this work, we present a method to formalise general recursive algorithms in type theory. Given a general recursive algorithm, our method is to define an inductive special-purpose accessibility predicate that characterises the inputs on which the algorithm terminates. The type-theoretic version of the algorithm is then defined by structural recursion on the proof that the input values satisfy this predicate. The method separates the computational and logical parts of the definitions and thus the resulting type-theoretic algorithms are clear, compact and easy to understand. They are as simple as their equivalents in a functional programming language, where there is no restriction on recursive calls. Here, we give a formal definition of the method and discuss its power and its limitations.

(Received February 13 2003)
(Revised January 8 2005)