Composition and Compilation in Functional Programming Languages

Functional programming languages, such as Backus ' FP, and high level expression oriented languages, such as APL, are examples of programming languages in which the primary method of program construction is the process of composition. In this paper we describe an approach to generating code for languages based on compositions. The approach involves nding an in-termediate representation which grows in size very slowly as additional terms are composed. In particular, the size of the intermediate representation of a composed object should be consider-ably smaller, and easier to interpret, than the sum of the sizes of the internal representations of the individual elements. We illustrate this technique by showing how to generate conventional code for Backus ' language FP. The general technique, however, is applicable to other languages, as well as other architectures.