FUNCTORIAL HIERARCHIES OF FUNCTIONAL LANGUAGES.

Abstract

For any set SIGMA of operation symbols we present both a concrete and and abstract development of a hierarchy L// SIGMA //,//0, L// SIGMA //,//1, L// SIGMA //,//2, . . . L// SIGMA //,//n, . . . of functional programming languages employing the elements of SIGMA as primitives. Each step in the hierarchy introduces 'function variables' (selector functions) of the next higher type. We include a basis for an operational semantics for these languages given any interpretation of the operation symbols. The main result is an abstract algebraic characterization of these languages in terms of a new kind of algebraic theory, together with a sketch of the proof that the concrete and abstract presentations are equivalent.