Higher-Order and Symbolic Computation, 14(2/3)99-100
EditorialOlivier Danvy and Julia L. Lawall
|
This double issue presents a collection of selected articles from
PEPM'00, the 2000 ACM SIGPLAN Workshop on Partial Evaluation and
Semantics-Based Program Manipulation, which took place on January 22
and 23 in Boston, Massachusetts [1]. The articles were subjected to
the usual process of journal reviewing. They address a wide range of
topics: three of the articles focus on various forms of partial
evaluation, while the remaining two address other aspects of program
analysis. "A Hybrid Approach to Online and Offline Partial Evaluation" by Eijiro Sumii and Naoki Kobayashi shows how to make online partial evaluation more efficient, by using side-effects to improve the performance of let insertion, by performing specialization using a cogen approach, and by preceding specialization by an analysis that is akin to useless-variable elimination and that determines where let insertion may be needed. Techniques similar to the latter two are commonly used in offline partial evaluation. This article shows how they can be adapted to an online setting, without sacrificing the precision of online partial evaluation. "The Second Futamura Projection for Type-Directed Partial Evaluation" by Bernd Grobauer and Zhe Yang explores the second Futumura projection, a classical approach to automatic compiler generation, in the context of type-directed partial evaluation. Unlike ordinary partial evaluation, which operates on a source program, type-directed partial evaluation is applied to a compiled program. This feature complicates the instantiation of the second Futumura projection. "Regular Tree Languages as an Abstract Domain in Program Specialisation" by John Gallagher and Julio Peralta investigates the use of regular trees to describe the structure of intermediate values and thus increase the amount of information that can be exploited during specialization. While the authors present their work in the context of online partial evaluation of logic programs, their approach should also be applicable to other forms of partial evaluation. "Type-Based Useless-Variable Elimination" by Naoki Kobayashi presents a simple yet powerful type-based technique for identifying useless variables. The technique is proved optimal among possible type-based approaches. "Calculating Sized Types" by Wei-Ngan Chin and Siau-Cheng Khoo uses Presburger formulas and the Omega calculator to effectively and precisely characterize the sizes of data structures manipulated by recursive functions. This analysis can be used to detect properties such as complexity, termination, and array bounds, which can be used by a variety of program-optimization techniques, including partial evaluation. We would like to extend our thanks to the reviewers for their timely and careful assistance. Reference 1. Lawall,J.L. (ed.). ACM SIGPLAN Workshop on Partial Evaluation and Semantics-based Program Manipulation (PEPM'00), SIGPLAN Notices, 34(11). |
![[picture of journal cover]](../LISP.JPG)