Abstraction problems in combinatory logic: A compositive approach

AbstractThe problem of the translation of λ-terms into combinators (bracket abstraction) is of great importance for the implementation of functional languages. In the literature there exist a lot of algorithms concerning this topic, each of which is based on a particular choice of a combinatory basis, its cardinality, and an abstraction technique. The algorithm presented here originated from a modification of the definition of abstraction given by Curry in 1930, and has the following interesting properties: 1.(i) it employs a potentially infinite basis of combinators, each of which depends on at most two parameters and is, therefore, directly implementable;2.(ii) it gives compact code, introducing a number of basic combinators which is proportional to the size of the expression to be abstracted and invariant for one- and multi-sweep abstraction techniques;3.(iii) it gives the result in the form RIM1… Mn, where R is a regular combinator expressed as a composition of basic combinators, I is the identity combinator, and M1,…, Mn are the constant terms appearing into the expression subjected to the translation process.It appears that a slight modification of the algorithm yields a combinatory equivalent of Hughes' supercombinators