Higher-Order and Symbolic Computation, 16(1/2)5-6
Olivier 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
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 , and the second kind consists
in the applications of schema equivalences `a la Walker-Strong .
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
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
His dedication to research and teaching is for us all an example to
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.
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.