Super-combinators a new implementation method for applicative languages
R. J. M. Hughes · 1982
There is a growing interest nowadays in functional programming languages and systems, and in special hardware for executing them. Many of these implementations are based on a system called graph reduction (GR), in which a program is represented as a graph which is transformed, or reduced, by the machine until it represents the desired answer. The various graph reduction implementations differ in the structure of the “machine code” (the program graph) and the compilation algorithms necessary to produce it from a source language. This paper describes a new implementation method using super-combinators which is apparently more efficient than its predecessors. Consideration of the new method also helps clarify the relationships between several other graph-reduction schemes. This paper is necessarily brief, but a fuller account can be found in [Hughes].