Reducing recursion to iteration by algebraic extension. (English) Zbl 0596.68010
Programming, Proc. Eur. Symp., Saarbrücken/FRG 1986, Lect. Notes Comput. Sci. 213, 111-118 (1986).
Summary: [For the entire collection see Zbl 0578.00005.]
Heterogeneous absolutely free algebras with a finite number of carriers and constructors have been proved very fruitful since the specification, through systems of equations, of iterative functions on such algebras may be automatically translated into terms of second order typed lambda- calculus. Since many definitions of functions on data structures are given by systems of recursive (but not iterative) equations it follows that reducing recursion to iteration becomes even more suitable.
In this paper we recall the definition of the family D of algebraic data systems (without parameters) and of the class I of iterative functions over D. We next define a primitive recursive scheme for functions whose domain is any finite cartesian product of components of D, generalizing the well known scheme for functions over the set N of nonnegative integers. Let PR be the family of functions obtained by replacing the iterative scheme by the primitive recursive scheme inside the definition of I. We prove that \(PR=I.\)
The method of proof essentially consists in adding new carriers and new constructors. Especially in the case of homogeneous algebras the heterogeneous algebras resulting from the extension become meaningful from the computer science point of view, as it is pointed out in the paper by examples. The relationship with the case of N is further discussed.
Heterogeneous absolutely free algebras with a finite number of carriers and constructors have been proved very fruitful since the specification, through systems of equations, of iterative functions on such algebras may be automatically translated into terms of second order typed lambda- calculus. Since many definitions of functions on data structures are given by systems of recursive (but not iterative) equations it follows that reducing recursion to iteration becomes even more suitable.
In this paper we recall the definition of the family D of algebraic data systems (without parameters) and of the class I of iterative functions over D. We next define a primitive recursive scheme for functions whose domain is any finite cartesian product of components of D, generalizing the well known scheme for functions over the set N of nonnegative integers. Let PR be the family of functions obtained by replacing the iterative scheme by the primitive recursive scheme inside the definition of I. We prove that \(PR=I.\)
The method of proof essentially consists in adding new carriers and new constructors. Especially in the case of homogeneous algebras the heterogeneous algebras resulting from the extension become meaningful from the computer science point of view, as it is pointed out in the paper by examples. The relationship with the case of N is further discussed.
