Further Results

The need to specify a refined binding-time type system yields some additional results:

1.

Offline partial evaluators typically treat operators in a duovariant manner. Either they operate on static base values or they operate on dynamic values. In consequence, many useful higher-order functions (such as map, filter, or reduce) cannot be provided externally as operators but have to be interpreted by the specializer. This is inefficient, it causes annoying and artificial binding-time problems for the unwary, and it forces programmers to work around the limitations.

Our type system allows for the specification of completely static, unmemoized function types which may be passed to and returned from operators. The type system also deals with the inherent representation problem.

2.

For similar reasons, partial evaluators usually do not cater to static higher-order input values and constants of functional type. We can deal with them, provided their type is given.

3.

Our binding-time type system determines which functions and data are completely static and which may be memoized. The specializer can take advantage and employ the more expensive encoding as memoized data only when necessary. For example, using the encoding of our specializer [31], two function calls are necessary to call a memoized function, whereas an ordinary function needs just one call.

4.

We present a simple and flexible approach to deal with variadic functions. The binding-time annotations of programs that do not use variadic functions do not get worse than with a binding-time analysis which only considers fixed-arity functions.

Sometimes, our binding-time analysis marks functions as static even if they may cause arity mismatches. However, these will only occur during specialization if the original program already had these problems.