Online-and-offline partial evaluation: A mixed approach

This paper presents a hybrid method of partial evaluation (PE), which combines the power of online PE and the efficiency of offline PE, for a typed strict functional language. We begin with a naive online partial evaluator, and make it efficient without sacrificing its power. To this end, we (1) use state (instead of continuation) for let-insertion, (2) take a so-called cogen approach, and (3) decrease unnecessary computations - such as unnecessary let-insertions and unused values/expressions - with a type-based use analysis, which subsumes various monovariant binding-time analyses. Our method yields the same residual programs as the naive online partial evaluator, modulo inlining of redundant let-bindings. We implemented and compared our method and existing methods, both online and offline. Experiments show that our method is at least twice as fast as any other method (e.g., more than 7 times as fast as Thiemann's cogen approach to offline PE in the specialization of the power function, thanks to the reduction of unnecessary let-insertions) when they yield equivalent residual programs.