Transformations on higher-order functions
Hanne Riis Nielson, Flemming Nielson · 1989
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 known arguments whereas the unknown arguments still are to be taken as parameters.The distinction between 'Itnouln' and 'un~%nozv7t' is closely related to the distinction between binding times, e.g. the distinction between compile-time and run-time.We shall therefore use a combination of polymorphic type inference and binding time analysis to obtain the required information.Following the current trend in the implementation of functional languages we shall then transform the run-time level (not the compile-time level) of the program into categorical combinators.At this stage we have a natural distinction between two kinds of program transformations: partial evaZuation 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 interpre-