Partial evaluation is a program specialization technique which is based on aggressive constant propagation. The aim of specialization is improving efficiency: Given a source program and the known, static part of its input, construct a residual program which accepts the remaining, dynamic part of the input and computes the same answer as the source program applied to the entire input, but more efficiently.
We deal with the offline variant of partial evaluation where--in a first pass--a binding-time analysis annotates each expression with its binding time: either ``executable'' (static) or ``suspended'' (dynamic). The second pass, the specializer, simply follows the annotations, reducing the static expressions and rebuilding the dynamic ones. In order to ensure termination of partial evaluation, the specializer memoizes certain functions (called sp-functions). Whenever the specializer calls an sp-function it specializes its body with respect to the current arguments and generates a function call. In addition, the static part of the current arguments is memoized, so that the specialized function is reused the next time the same sp-function is called with arguments that have an identical static part. Specialization is polyvariant: If the sp-function is called with arguments differing in the static part, the specializer generates a new specialized function.