Higher-Order and Symbolic Computation, 14(2/3)101-142
A Hybrid Approach to Online and Offline Partial EvaluationEijiro Sumii, Department of Information Science, Graduate School of Science, University of Tokyo, Hongo 7-3-1, Bunkyo-ku, Tokyo 113-0033, Japan
Naoki Kobayashi, Department of Computer Science, Graduate School of Information Science and Engineering, Tokyo Institute of Technology, Oookayama 2-12-1, Meguro-ku, Tokyo 152-8552
|
Abstract: This article presents a hybrid method of partial
evaluation (PE), which is exactly as precise as naive online PE and
nearly as efficient as state-of-the-art offline PE, for a statically
typed call-by-value functional language. PE is a program transformation that specializes a program with respect to a subset of its input by reducing the program and leaving a residual program. Online PE makes the reduction/residualization decision during specialization, while offline PE makes it before specialization by using a static analysis called binding-time analysis. Compared to offline PE, online PE is more precise in the sense that it finds more redexes, but less efficient in the sense that it takes more time. To solve this dilemma, we begin with a naive online partial evaluator, and make it efficient without sacrificing its precision. To this end, we (1) use state (instead of continuations) for let-insertion, (2) take a so-called cogen approach (instead of self-application), and (3) remove unnecessary let-insertion, unnecessary tags, and unnecessary values/expressions by using a type-based representation analysis, which subsumes various monovariant binding-time analyses. We implemented and compared our method and existing methods--both online and offline--in a subset of Standard ML. Experiments showed that (1) our method produces as fast residual programs as online PE and (2) it does so at least twice as fast as other methods (including a cogen approach to offline PE with a polyvariant binding-time analysis) that produce comparable residual programs. Keywords: online partial evaluation, state-based let-insertion, cogen approach, binding-time analysis |
This article can be downloaded [here].
![[picture of journal cover]](../LISP.JPG)