Higher-Order and Symbolic Computation, 12(4)307-308

Editorial

Olivier Danvy and Carolyn Talcott

This issue of HOSC is the first of a two-part series dedicated to the general topic of partial evaluation. This series grew out of PEPM'99, the 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, which took place in San Antonio, Texas on January 22nd and 23rd, 1999 [1].

PEPM'99 brought together researchers working in the areas of semantics-based program manipulation and partial evaluation. The workshop focused on techniques and supporting theory for the analysis and manipulation of programs. Technical topics included, but were not limited to:

Program manipulation techniques: program transformation, program specialization, type specialization, syntax-directed partial evaluation, type-directed partial evaluation, normalization, continuations, reflection, rewriting, run-time code generation.
Program analysis techniques: abstract interpretation, static analysis, binding-time analysis, attribute grammars, constraints.
Related issues in language design and models of computation: imperative, functional, logical, object-oriented, parallel, distributed, mobile, secure.
Programs as data objects: staging, meta-programming, incremental computation, mobility, tools and techniques, prototyping and debugging.
Applications: systems programming, scientific computing, algorithmics, graphics, security checking, simulation, compiler generation, compiler optimization, decompilation.

The articles in this special issue reflect this diversity.

In their article "Combining Program and Data Specialization", Sandrine Chirokoff, Charles Consel, and Renaud Marlet describe the integration of program and data specialization within their partial evaluator Tempo. They describe both the principle and practice of program and data specialization, and report a series of benchmarks to document their combination.

In their article "Certifying Compilation and Run-Time Code Generation", Luke Hornof and Trevor Jim address how to certify code generated at run time. Their work combines the concepts of `certifying compilation' by George Necula and Peter Lee and of `run-time specialization' by Charles Consel et al. in the Compose group. The authors build on two existing software artifacts, Charles Consel's Tempo system and Greg Morrisett's Popcorn compiler, and obtain that dynamically generated code is (type) safe and very fast to execute, even when loaded over a network. To this end, they develop a type-safe dialectof C, Cyclone, and type-safe assembly language, TAL/T.

The third article of this issue is a pearl: a slightly revised version of Prof. Yoshihito Futamura's original article "Partial Evaluation of Computation Process--An Approach to a Compiler-Compiler" [2] that initiated twenty years of work on self-applicable partial evaluation [3]. Yet, for all its striking insights, this article is virtually impossible to find in its original form--only as a copy of a copy of a copy. We are thus delighted to make it more widely available here. In addition, Prof. Futamura kindly agreed to write an introduction to this reprint. And in the course of writing this introduction, an unexpected fact about triple self-application came into light. Indeed, triple self-application is not mentioned inthe 1971 article, and according to published record, it was discovered later on by Prof. Andrei Ershov for mixed computation and by Prof. Valentin Turchin for supercompilation. Nevertheless, Prof. Futamura did envision triple self-application as early as 1972: it is mentioned in a progress report dated January 1973, the introduction of which is reproduced here.

References

1. Danvy, O. (Ed.). ACM SIGPLAN workshop on partial evaluation and semantics-based program manipulation, Technical report BRICS-NS-99-1, University of Aarhus, San Antonio, Texas, January 1999.

2. Futamura, Y. Partial evaluation of computation process--an approach to a compiler-compiler. Systems Computers Controls 2(5) (1971) 45-50.

3. Jones, N.D., Sestoft, P., and Søndergaard, H. MIX: a self-applicable partial evaluator for experiments in compiler generation. Lisp and Symbolic Computation 2(1) (1989) 9-50.

June 2003 - hosc@brics.dk