1 - Introduction

Summary

The functional programming style is closely related to the use of higher-order functions. In particular, it suggests that many function definitions are instances of the same general computational pattern and that this pattern is defined by a higher-order function. The various instances of the pattern are then obtained by supplying the higher-order function with some of its arguments.

One of the benefits of this programming style is the reuse of function definitions and, more importantly, the reuse of properties proved to hold for them: usually a property of a higher-order function carries over to an instance by verifying that the arguments satisfy some simple properties.

One of the disadvantages is that the efficiency is often rather poor. The reason is that when generating code for a higher-order function it is impossible to make any assumptions about its arguments and to optimize the code accordingly. Furthermore, conventional machine architectures make it rather costly to use functions as data.

We shall therefore be interested in transforming instances of higher-order functions into functions that can be implemented more efficiently. The key observation in the approach to be presented here is that an instance of a higher-order function is a function where some of the arguments are known and others are not. To be able to exploit this we shall introduce an explicit distinction between known and unknown values or, using traditional compiler terminology, between compile-time entities and run-time entities.