1998 Symposium on Partial Evaluation.
The partial-evaluation community is concerned with specializing programs. Our thesis is that whereas the most efficient programs are the ones that are specialized to the task at hand, actual programs are overly general, and this generality impedes their efficiency. For a simple example, consider any kind of formatting function. Would anyone bother writing in C the following three lines:
fputs(x, fp); fputs(" is not ", fp); fputs(y, fp);
instead of writing the following equivalent one line?
fprintf(fp, "%s is not %s", x, y);
The problem with this one-liner is that unless the compiler displays some intelligence, the analysis of the control string "%s is not %s" happens at run time. We can very precisely quantify the intelligence that is required here: the compiler should specialize the library function fprintf with respect to the control string, in effect transforming the one-liner above into the original three lines. Such a specialization is what partial evaluation is all about.
Literals offer a rich source of opportunities for program specialization, one that can be fueled, for example, with runtime case analyses over compile-time constants--a favorite programming technique among partial-evaluation practitioners. Many other opportunities, of course, exist, such as relatively short-lived runtime invariants, which enable specialization through runtime code generation, and successive (and possibly related) invariants, which link partial evaluation with incremental computation.
The goal of partial evaluation is thus to specialize programs with respect to any kind of invariant, at any stage of their development. Several articles in this symposium illustrate this goal.
The partial-evaluation community is developing various specialization techniques across programming-language paradigms: imperative, object-oriented, functional, logical, etc. We are furthermore building mostly automatic tools to carry out program specialization: partial evaluators. Our activities link theory and practice in an effective way: on the one hand, we must understand the semantics of the languages, their type structure, and their static-analysis principles; and on the other hand, we must find practical solutions and solve challenging implementation problems. Several articles in this symposium illustrate these points.
The idea of specializing programs is as old as Computer Science. There is no year without an enterprising data miner (typically a Ph.D. student) unearthing bibliographic references documenting this idea in a particular field: scientific computing, pattern matching, algorithmics and data structures, computer graphics, interpreters and compilers, etc.
The partial-evaluation community welcomes all contributions to the area of program and data specialization: foundational issues, transformation techniques, new approaches, and applications. As documented below, there is a regular series of ACM SIGPLAN-sponsored meetings on Partial Evaluation and Semantics-Based Program Manipulation (PEPM).
We hope that this symposium will contribute to documenting our field and fostering new activities, and we would like to thank the editorial board of Computing Surveys for hosting it.
2. THIS SYMPOSIUM
The Symposium on Partial Evaluation is a collection of concise articles characterizing the state of the art, stating challenging problems, and outlining promising directions for future work. The contributions were strictly referred. They span a wide range of topics from all areas of partial evaluation and semantics-based program manipulation. The authors explain relevant trends in partial evaluation in both general and technical terms, and state problems that are likely to have a potential impact on the future development of the area. The contributions cover three topics: foundational issues, transformation techniques, and computational practice.
A brief topical summary of the contributions follows.
2.1 Principles, Foundations, and Frameworks
Basin  considers the derivation of optimized programs using logical frameworks. The idea is to discover inductive programs using a theorem prover and a suitable inductive theory. Finding the specialized programs boils down to applying higher-order unification to the source program and the theorems.
Field et al.  propose a general framework for partial evaluation based on equational programming. Starting from an algebraic-specification view of the world, the authors develop a framework that likewise is suitable for partial evaluation and abstract interpretation, simply by choosing a suitable interpretation.
Klimov  considers two fundamental operations on programs, namely program specialization and program composition, which are both equivalence transformations. He points out that both transformations are essential for a wide spectrum of transformation tasks, gives an in-depth analysis of their relation, and states challenging problems for further work.
The "offline" partial-evaluation strategy common to procedural languages amounts to analyzing the binding times of a source program prior to specializing it. Specialization in logic programming, called partial deduction, has quite different techniques and objectives. It determines binding times "online" during specialization and it exploits the full power of unification. An up-to-date survey of partial deduction, recent achievements and prospects, can be found in the contribution by Leuschel et al. .
Mogensen  shows past research in partial evaluation from a new angle, namely as directed towards the removal of "inherited limits." Inherited limits are resource bounds set by the source program that cannot be overcome by a specializer, and hence they are inherited by the specialized program. Ideally a specializer should be free of any limits that restrict its behavior. Inherited limits should be removed as the specializer becomes more and more sophisticated.
Partial evaluation and unfold/fold program transformation share common objectives, but have been developed according to different methodologies. Pettorossi and Proietti  consider the relation between these two techniques and argue that partial evaluation should be studied in the latter framework (which also subsumes other transformations as deforestation, partial deduction and tupling). The authors stress the need for algorithmic strategies in order to retain the advantages of automatic program transformation.
Takano et al.  give a brief account on the state and some recent achievements of program transformation in calculational form. Briefly put, their approach rests on packaging recursion in a specialized set of recursion combinators. By applying general theorems about combinations of these combinators, they achieve specialization and composition transformations, most prominently loop fusion. The authors argue that the calculational approach allows cheap implementations from software components and, hence, to increase modularity of software systems.
Recent work by Davies and Pfenning has shown that modal logic provides a sound foundation for binding-time analysis as used in offline partial evaluation. Wickline et al.  continue on that approach and propose to use modal logics as a basis for runtime code generation.
2.2 Towards Stronger Transformation Techniques
In the last decade, much research effort has been devoted to the combination of the functional and logic programming paradigms. The semantics of the integrated language is usually based on narrowing, a combination of unification for parameter passing and reduction as evaluation mechanism. Alpuente et al.  introduce the problems specific to partial evaluation of functional-logic programs and discuss techniques to solve them.
Many logic programming applications require support for modularization and structuring of large knowledge bases. Bugliesi et al.  discuss ways for overcoming the runtime overhead in modular programming based on partial deduction and abstract interpretation.
Constraint programming is a powerful paradigm which combines constraint solving with logical deduction. Constraint languages are clean and high-level, but inefficient. Etalle and Gabrielli  suggest online techniques for partial evaluation of concurrent constraint programs.
A trace grammar describes all possible execution paths of a program. Gallagher and Lafave discuss the fundamental role of trace information and grammar for controlling program specialization . They argue that trace information is beneficial for program specialization independently of a particular language paradigm (functional, logic, imperative, etc.).
A current trend is to make specializers aware of computational effects. Hitherto, most specializers simply ignored effects like store updates and exceptions. The recent interest of the functional programming community in monads has provided sound foundations for this enterprise, as reported by Hatcliff .
Hughes  proposes an original approach to specializing typed functional programs. The approach is based on assigning nonstandard types to program phrases so that the types express all the specialization-time information. This way, the flow of information is not restricted to the flow of program execution, but the information is propagated via unification of types.
Lafave and Gallagher  identify features of generalized partial computation that constraint-based partial evaluation cannot achieve. The open problems are illustrated using McCarthy's 91-function, a difficult specialization problem.
Tabled execution is an alternative approach to the evaluation of logic programs that has advantages in some cases. Sagonas and Leuschel  consider extending the well-known methods for partial deduction to tabled execution. They state some achievements so far and point out interesting open problems in this field.
2.3 Software Development and Computational Practice
One of the future challenges lies in integrating partial evaluation in different phases of the software development process (specification, implementation, verification, maintenance, reuse, etc.) and the extension of specialization towards "real-world" tasks.
Program comprehension is one of the most tedious and time-consuming phases of the software life cycle. Studies suggest that 50% of the software maintenance effort is devoted to the understanding of the maintained software. Blazy and Facon  use partial evaluation for program comprehension. The aim is not efficiency of programs but the reduction of their structural complexity.
Cazenave  describes an exciting application of partial deduction to programming the game of Go. The partial deduction algorithm is parameterized over a set of meta-programs that define the specialization strategy. This way, the specializer derives from a specification of Go in first-order logic an efficient program that plays Go quite effectively.
Tempo is a successful specializer for the C programming language. Consel et al.  give an overview, document the current state of affairs, and outline perspectives and future work. In a second contribution, Consel et al.  discuss the role of partial evaluation in software engineering. Applications include the automatic implementation of domain-specific languages and common software-design patterns.
Draves  uses partial evaluation to automatically generate very fast specialized code for reformatting data at the bit level.
Finite-state verification techniques and partial evaluation have been developed in separate communities. Despite this, there is a significant overlap involving specific program analysis and transformation methods. Dwyer et al.  identify techniques common to finite-state verification and partial evaluation, suggesting novel lines of work.
Traditional specializers work in an offline fashion, in that program specialization is completely separated from execution of the specialized program. Recent work on runtime specialization by Leone et al.  shows that binding-time-analyzed assembly code can give rise to highly efficient runtime specializers.
Waddell and Dybvig  observe that the partial-evaluation process is usually not perspicuous enough for the casual user. Therefore, they have developed a system that allows them to visualize all stages of the process, starting from the binding-time analysis up to identifying the individual parts of the source program in the specialized program. This tool, which has analogs in the program-slicing community, should prove precious to partial-evaluation novices.
3. FURTHER PARTIAL-EVALUATION RESOURCES
Good starting points for the study of partial evaluation are Jones, Gomard, and Sestoft's textbook [Jones et al. 1993], Consel and Danvy's tutorial notes [Consel and Danvy 1993], Mogensen and Sestoft's encyclopedia chapter [Mogensen and Sestoft 1997], and Gallagher's tutorial notes on partial deduction [Gallagher 1993]. Further material can be found in the proceedings of the Gammel Avernaes meeting (PEMC) [Bjorner et al. 1988; Ershov et al. 1988], in the Proceedings of the ACM Conferences and Workshops on Partial Evaluation and Semantics-Based Program Manipulation (PEPM) [Hudak and Jones 1991; Consel 1992; Schmidt 1993; Sestoft and Sondergaard 1994; Scherlis 1995; Consel 1997; Danvy 1999], and in special issues of various journals [jfp 1993; jlp 1993; lasc 1995; TCS 1998]. A comprehensive volume on partial evaluation appeared in the Lecture Notes of Computer Science series [Danvy et al. 1996]. Sestoft maintains an online bibliography [Sestoft].
ALPUENTE, M., FALASCHI, M., AND VIDAL, G. 1998. A unifying view of functional and logic program specialization. This symposium.
BASIN, D. 1998. Logical framework based program development. This symposium.
BJORNER, D., ERSHOV, A. P., AND JONES, N. D. Eds. 1988. Partial Evaluation and Mixed Computation (Amsterdam, 1988). North-Holland.
BLAZY, S. AND FACON, P. 1998. Partial evaluation for program comprehension. This symposium.
BUGLIESI, M., CIAMPOLINI, A., LAMMA, E., AND MELLO, P. 1998. Optimizing modular logic languages. This symposium.
CAZENAVE, T. 1998. Controlled partial deduction of declarative logic programs. This symposium.
CONSEL, C. ED. 1992. Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation PEPM '92 (San Francisco, CA, June 1992). Yale University. Report YALEU/DCS/RR-909.
CONSEL, C. ED. 1997. Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation PEPM '97 (Amsterdam, The Netherlands, June 1997). ACM Press, New York.
CONSEL, C. AND DANVY, O. 1993. Tutorial notes on partial evaluation. In Proc. 20th Annual ACM Symposium on Principles of Programming Languages (Charleston, South Carolina, Jan. 1993), ACM Press, New York, pp. 493-501.
CONSEL, C., HORNOF, L., LAWALL, J., MARLET, R., MULLER, G., NOEL, F., NOYE, J., THIBAULT, S., AND VOLANSCHI, N. 1998. Tempo: Specializing systems applications and beyond. This symposium.
CONSEL, C., HORNOF, L., LAWALL, J., MARLET, R., MULLER, G., NOYE, J., THIBAULT, S., AND VOLANSCHI, N. 1998. Partial evaluation for software engineering. This symposium.
DANVY, O. ED. 1999. Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation PEPM '99 (San Antonio, Texas, Jan. 1999). To appear.
DANVY, O., GLUCK, R., AND THIEMANN, P. Eds. 1996. Dagstuhl Seminar on Partial Evaluation 1996, Volume 1110 of Lecture Notes in Computer Science (SchloB Dagstuhl, Germany, Feb. 1996). Springer-Verlag, New York.
DRAVES, S. 1998. Partial evaluation for media processing. This symposium.
DWYER, M., HATCLIFF, J., AND NANDA, M. 1998. Using partial evaluation to enable verification of concurrent software. This symposium.
ERSHOV, A. P., BJORNER, D., FUTAMURA, Y., FURUKAWA, K., HARALDSSON, A., AND SCHERLIS, W. Eds. 1988. Special Issue: Selected Papers from the Workshop on Partial Evaluation and Mixed Computation, 1987 (New Generation Computing, vol. 6, nos. 2, 3) (1988). Ohmsha Ltd. and Springer-Verlag.
ETALLE, S. AND GABBRIELLI, M. 1998. Partial evaluation of concurrent constraint languages. This symposium.
FIELD, J., HEERING, J., AND DINESH, T.B. 1998. Equations as a uniform framework for partial evaluation and abstract interpretation. This symposium.
GALLAGHER, J. 1993. Tutorial on specialisation of logic programs. In D. Schmidt Ed., Proc. ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation PEPM '93 (Copenhagen, Denmark, June 1993), ACM Press, New York, pp. 88-98.
GALLAGHER, J. AND LAFAVE, L. 1998. Towards language-independent algorithms for program specialization. This symposium.
HATCLIFF, J. 1998. Foundations for partial evaluation of functional languages with computational effects. This symposium.
HUDAK, P. AND JONES, N. D. Eds. 1991. Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation PEPM '91 (New Haven, CT, June 1991). ACM. SIGPLAN Notices 26(9).
HUGHES, J. 1998. Type specialisation. This symposium.
JFP. 1993. Journal of Functional Programming 3(3), special issue on partial evaluation. Neil D. Jones, editor.
JLP. 1993. Journal of Logic Programming 16 (1,2), special issue on partial deduction. Jan Komorowski, editor.
JONES, N. D., GOMARD, C. K., AND SESTOFT, P. 1993. Partial Evaluation and Automatic Program Generation. Prentice-Hall.
KLIMOV, A. 1998. Program specialization vs. program composition. This symposium.
LAFAVE, L. AND GALLAGHER, J. 1998. Extending the power of automatic partial evaluators. This symposium.
LASC. 1995. Lisp and Symbolic Computation 8 (3), special issue on partial evaluation. Peter Sestoft and Harald Sndergaard, editors.
LEONE, M. AND LEE, P. 1998. Dynamic specialization in the Fabius system. This symposium.
LEUSCHEL, M., MARTENS, B., AND DE SCHREYE, D. 1998. Some achievements and prospects in partial deduction. This symposium.
MOGENSEN, T. 1998. Inherited limits. This symposium.
MOGENSEN, T. AE. AND SESTOFT, P. 1997. Partial evaluation. In A. Kent and J. G. Williams Eds., Encyclopedia of Computer Science and Technology, Volume 37, pp. 247-279. 270 Madison Avenue, New York, New York 10016: Marcel Dekker.
PETTOROSSI, A. AND PROIETTI, M. 1998. Program specialization via algorithmic unfold/fold transformations. This symposium.
SAGONAS, K. AND LEUSCHEL, M. 1998. Extending partial deduction to tabled execution: Some results and open issues. This symposium.
SCHERLIS, W. Ed. 1995. Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation PEPM '95 (La Jolla, CA, June 1995). ACM Press, New York.
SCHMIDT, D. Ed. 1993. Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation PEPM '93 (Copenhagen, Denmark, June 1993). ACM Press, New York.
SESTOFT, P. Bibliography on partial evaluation. Available through URL ftp://ftp.diku.dk/pub/ diku/dists/jones-book/partial-eval.bib.Z.
SESTOFT, P. AND SONDERGAARD, H. Eds. 1994. Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation PEPM '94 (Orlando, Fla., June 1994). ACM, New York.
TAKANO, A., HU, Z., AND TAKEICHI, M. 1998. Program transformation in calculational form. This symposium.
TCS. 1998. Theoretical Computer Science, special issue on partial evaluation. Charles Consel, editor.
WADDELL, O. AND DYBVIG, R.K. 1998. Visualizing partial evaluation. This symposium.
WICKLINE, P., LEE, P., PFENNING, F., AND DAVIES, R. 1998. Modal types as staging specifications for run-time code generation. This symposium.
OLIVIER DANVY BRICS, University of Aarhus
ROBERT GLUCK DIKU, University of Copenhagen and
PETER THIEMANN University of Nottingham
Authors' addresses: O. Danvy, BRICS, University of Aarhus, B3.24, Aarhus, Denmark, e-mail: email@example.com; R. Gluck, DIKU, University of Copenhagen, Copenhagen, Denmark, e-mail: http:// www.diku.dk/~glueck; and P. Thiemann, Department of Computer Science, University of Nottingham, Nottingham, England, e-mail: http://www.cs.nott.ac.uk/~pjt.
|Printer friendly Cite/link Email Feedback|
|Author:||DANVY, OLIVIER; GLUCK, ROBERT; THIEMANN, PETER|
|Publication:||ACM Computing Surveys|
|Date:||Sep 1, 1998|
|Previous Article:||A survey of approximately optimal solutions to some covering and packing problems.|
|Next Article:||Concurrency and Distribution in Object-Oriented Programming.|