Towards Partial Evaluation of Full Scheme

Peter Thiemann¹

Date:

Abstract:

We present a binding-time analysis for Scheme which enables an offline partial evaluator to successfully treat Scheme's reflective features eval, apply, and control operators like call/cc. Additionally, our analysis empowers the specializer to select the most efficient representation for each object. This removes some limitations of previous specializers regarding the use of higher-order primitive operations. The theoretical development is backed by an implementation.

Keywords:

partial evaluation of reflective language features, meta-computation

The programming language Scheme [22] is an ideal vehicle for meta-computation, specifically for partial evaluation. Part of the appropriateness of Scheme for meta-computation tasks derives from its reflective features: eval, which reflects the external representation of, say, a procedure to a functional value, apply, which reflects lists to argument lists, and call/cc², which makes the continuation of the current expression available as a procedure. The continuation can be viewed as a reified object from the meta-interpreter (supposedly written in CPS).

Much work in partial evaluation has been done in the context of Scheme [3,6,7,5,8]. However, its reflective features have been neglected so far. In order to overcome this drawback, we present a binding-time analysis and a specialization algorithm for a large functional subset of Scheme. The subset includes eval, apply, and call/cc. Additionally, our new analysis supports variadic functions and includes a representation analysis which treats external and built-in operators more liberal than previous analyses. The latter analysis improves the efficiency of the specializer by enabling it to choose the most efficient representation for functions and objects of algebraic datatypes. These features are unique to our specializer.