scientific article; zbMATH DE number 4094791
[For the entire collection see Zbl 0643.00024.] The paper concerns the theoretical foundations of functional programming and its connections with combinatory algebras. The focus is the description of partial and total recursive functions through combinators. First, Church algebras are introduced, allowing the combinatory expression of any element of the usual data structures (i.e., natural numbers, strings, lists, trees and forests). Second, normal combinators solving a special kind of recursive equations (called iterative equations) for functions to and from Church algebras are explicitly exhibited. Thirdly, Church algebras are shown to be isomorphically embeddable in some extensions, called *-algebras, where any kind of recursive definition for mappings is solvable. The basic definition is that of combinatory algebra with a polynomial basis, i.e., a structure \(C\equiv (X\), appl, \(\{\pi_ i^{m,n} |\) \(n\geq i>0\), \(m\geq 0\})\) where X is a set with \(Card(X)>1\), appl is the operation of application of a function to an argument, i.e., appl(f,x)\(\equiv f(x)\), and \(\pi_ i^{m,n}\) (which can be abbreviated to \(\pi_ i)\) is a basic combinator presented as closed \(\lambda\)-terms by \(\pi_ i^{m,n}=\lambda (y_ 1,...,y_ m,x_ 1,...,x_ n)\) \(x_ i(y_ 1(x_ 1,...,x_ n),...,y_ m(x_ 1m,...,x_ n))\). This algebra has some interesting subalgebras: - the L-algebra, in which each \(\pi_ i^{m,n}\) has exactly m arguments. All the elements of this algebra possess normal form. - the LN-algebra, a subalgebra of an L-algebra where each argument of \(\pi_ i^{m,n}\) \((m>0)\) begins with \(\pi_ j^{p,q}\) with \(q\geq n.\) - the LNp-algebra, a subalgebra of an LN-algebra where \(n=p\) for all the basic elements \(\pi_ i^{m,n}.\) - the LNpC-algebra (Church p-algebra), a subalgebra of an LNp-algebra with a basis having exactly p elements. It is shown that the most important data structures can be represented by Church algebras. The main theorem for Curch algebras is that \(e\in LNnC \to e(x_ 1,...,x_ n)=e[x_ 1/\pi_ 1,...,x_ n/\pi_ n]\), where \(e[x_ 1/\pi_ 1,...,x_ n/\pi_ n]\) denotes the result of simultaneously substituting \(x_ i\) for \(\pi_ i\) in e. The following theorem guarantees the explicit solution of functional iterative equations: Theorem - Let a function f from Church algebra into another Church algebra be iteratively defined by the system: \[ f(\pi_ i^{m,n}(e_ 1,...,e_ m))\quad =\quad h_ i(f(e_ 1),...,f(e_ m)),\quad i=1,..., n, \] where \(h_ 1,...,h_ n\) are given combinators. Then an explicit solution to f is: \[ f(e)\quad =\quad e(h_ 1,...,h_ n). \] Analogous results about the explicit solution of iterative equations are then given for parametric Church algebras and for *-algebras.
- An algebraic view of the Böhm-out technique
- scientific article; zbMATH DE number 3846829 (Why is no real title available?)
- scientific article; zbMATH DE number 4066867 (Why is no real title available?)
- scientific article; zbMATH DE number 63120 (Why is no real title available?)
- scientific article; zbMATH DE number 4124984 (Why is no real title available?)
- scientific article; zbMATH DE number 1339950 (Why is no real title available?)
- scientific article; zbMATH DE number 482779 (Why is no real title available?)
- scientific article; zbMATH DE number 722586 (Why is no real title available?)
- Program algebras of recursive functions
- Algorithms for Functional Programming
- scientific article; zbMATH DE number 2172859 (Why is no real title available?)
- Note on Algol and conservatively extending functional programming
- scientific article; zbMATH DE number 1405588 (Why is no real title available?)
- Intersection and union types
- Some FP algebra with currying operation
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3821565)