Using Transformations in the Implementation of Higher-Order Functions

Abstract

Traditional functional languages do not have an explicit distinction between binding times. It arises implicitly, however, as typically one instantiates a higher-order function with the arguments that are known whereas the unknown arguments remain to be taken as parameters. The distinction between ''known'' and ''unknown'' is closely related to the distinction between binding times like ''compile-time'' and '' run-time''. This leads to using a combination of polymorphic type inference and binding time analysis for obtaining the required information about which arguments are known.

Following the current trend in the implementation of functional languages we then transform the run-time level of the program ( not the compile-time level) into categorial combinators. At this stage we have a natural distinction between two kinds of program transformations: partial evaluation which involves the compile-time level of our notation and algebraic transformations (i.e. the application of algebraic laws) which involves the run-time level of our notation.

By reinterpreting the combinators in suitable ways we obtain specifications of abstract interpretations (or data flow analyses). In particular, the use of combinators makes it possible to use a general framework for specifying both forward and backward analyses. The results of these analyses will be used to enable program transformations that are not applicable under all circumstances.

Finally the combinators can also be reinterpreted to specify code generation for various (abstract) machines. To improve the efficiency of the code generated, one may apply abstract interpretations to collect extra information for guiding the code generation. Peephole optimizations may be used to improve the code at the lowest level.