super-combinators a new implementation method for applicative languages
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]. The simplest machine language we shall consider consists of constants combined by function application. This is the language of constant applicative forms (cafs) . Some of the constants are basic functions.
combinational implementation method applications language functional functional programming systems hardware graph reduction structure code compilation algorithm paper efficiency relationships scheme account