Higher-Order and Symbolic Computation, 16(1/2)5-6
EditorialOlivier Danvy, Fritz Henglein, Harry Mairson and Alberto Pettorossi
|
This double issue of HOSC is the first of two double issues dedicated
to the memory of Bob Paige (1947-1999). Bob's scientific interests were many, and his achievements were many as well, witness his research retrospective, which starts this special issue. In particular, Bob strongly contributed to the development of new techniques for the derivation of algorithms and programs using the transformational methodology. Starting from specifications written in a set theoretical language, using suitable algebraic or logical formulas, the programmer should transform them, possibly in various steps, into runnable algorithms with high performances. An automatic or semiautomatic system may help him in this task. There are, basically, two kinds of transformation steps: the first kind consists in the applications of rules according to suitable strategies `a la Burstall-Darlington [1], and the second kind consists in the applications of schema equivalences `a la Walker-Strong [2]. Bob's many research papers provide new insights into these two approaches to transformational programming and, in particular, he contributed to the development of techniques which allow us to derive and improve algorithm efficiency, while preserving correctness. Such derivations and improvements were obtained by suitable modifications of the recursion structure and/or choices of the data structures employed. When proposing new techniques, Bob always strived for generality, in the sense that these techniques should not be ad-hoc tricks. On the contrary, they should have a large range of applicability for a large class of specifications or programs. Only general ideas could become the basis for an automatic system for program development. Bob's APTS system is indeed the incarnation of most of the techniques he proposed (cf. Leonard and Heitmeyer's contribution in this issue). Only general techniques may become part of a new programming methodology and this was what, ultimately, Bob was looking for and wanted to propose. Bob's colleagues and friends are all very happy to have been working and sharing ideas with him. In particular, his colleagues at the Courant Institute in New York, the members of the IFIP Working Group 2.1, and the people at the various Universities he visited, including the University of Copenhagen and the University of Wisconsin. All his friends and colleagues, enjoyed Bob's talks and presentations. His ideas and his visions on program development and programming methodology were a source of enthusiasm, strength, and inspiration. His dedication to research and teaching is for us all an example to follow. The articles in this issue of Higher-Order and Symbolic Computation were contributed and formally reviewed, and they reflect the variety of research interests of Bob's scientific work. "Universal Regular Path Queries" describes the development of an algorithm that abstracts a version of model checking for flow graphs with annotations corresponding to inferred properties. This article shows that such an algorithm can be derived systematically in the spirit of Bob Paige's work. "Dynamic Programming via Static Incrementalization" describes a (semi)automatic program transformation that optimizes recursive programs amenable to dynamic programming. "Program Synthesis from Formal Requirements" describes a project to translate a requirements specification, expressed in SCR notation, into C. Two translation strategies are discussed in the paper. Both were implemented using Bob Paige's APTS programtransformation system. "Computational Divided Differencing and Divided-Difference Arithmetics" uses an approach conceptually similar to the Computational Differentiation technique in order to compute precisely the set of finite, divided differences of a sampled function F(x): F[x0, x1] = (F(x0) - F(x1))/(x0 - x1). The second double issue of HOSC dedicated to Bob's memory will also contain technical contributions, as well as a non-technical retrospective. References 1. Burstall, R.M. and Darlington, J. Some transformations for developing recursive programs. In Proceedings of the International Conference on Reliable Software, Los Angeles, USA, 1975, pp. 465-472. 2. Walker, S.A. and Strong, H.R. Characterization of flowchartable recursions. In Proceedings 4th Annual ACM Symposium on Theory of Computing, Denver, CO, USA, 1972. |