Online Type-Directed Partial Evaluation

Abstract

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.