Online Type-Directed Partial Evaluation

Olivier Danvy

December 1997


In this experimental work, we extend type-directed partial evaluation (a.k.a. ``reduction-free normalization'' and ``normalization by evaluation'') to make it online, by enriching it with primitive operations (delta-rules). Each call to a primitive operator is either unfolded or residualized, depending on the operands and either with a default policy or with a user-supplied filter. The user can also specify how to residualize an operation, by pattern-matching over the operands. Operators may be pure or have a computational effect.

We report a complete implementation of online type-directed partial evaluation in Scheme, extending our earlier offline implementation. Our partial evaluator is native in that it runs compiled code instead of using the usual meta-level technique of symbolic evaluation

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.