Bob Paige, an active member of WG 2.1, died on October 5, 1999 at the age of 52. The members of WG 2.1 wish to extend their condolences to Bob's family, and to acknowledge his many contributions to the work of our group. I am writing for the group as both a member and Bob's long-time personal friend. I'm sure many of the group's members feel a deep sense of personal as well as professional loss.
Bob died of mesothelioma, a cancer of the cells that make up the lining around the outside of the lungs and inside of the ribs, or around the abdominal organs. The only known cause of mesothelioma is exposure to asbestos fibers. Asbestos manufacturers knew about the hazards of asbestos seventy years ago but were not forthcoming with this information.
Bob was ill for three and a half years. That afforded him the opportunity to write a retrospective reflecting upon his work and its relation to the objectives of WG 2.1. He writes, ``The common goal was a transformational program development methodology that would improve productivity of designing and maintaining correct software with an emphasis on algorithmic software.'' In its broad strokes, his retrospective raises many of the issues debated in WG 2.1. He asks how calculational is algorithm development, and whether working examples, developing theories, building systems, or defining notations was the best approach to making progress in a developing field.
Bob obtained strong results following each of these approaches. His research program showed remarkable stability and consistency that led to a steady stream of results, one building upon another, increasing the scope of problems that his system could compile to efficient code. His most recent project was to bootstrap his own 10,000 line system and generate 100,000 lines of efficient C code.
He fixed a specification language loosely based on SETL and was able to characterize classes of specifications and prove results about automatic transformation of these classes into efficient code. The classes were set-theoretic formulations of database query languages augmented with fixed-point operations. This language was suited to expressing and transforming a wide variety of combinatorial, algorithmic problems.
In his thesis work he generalized Earley's method of finite differencing to the high-level language context and demonstrated its broad applicability. He effectively applied finite differencing to database problems such as integrity control and view maintenance. I found particularly useful his work with his student Jiazhen Cai on fixed point convergent algorithms and its application to program analysis.
The program transformation community prides itself on discovering new algorithms by systematic application of transformational methods. Bob had great success contributing to the derivation of new algorithms for Horn clause satisfiability, real-time simulation, DFA minimalization, query optimization, and planarity testing.
I met Bob in graduate school at NYU. Prior to becoming a graduate student, he worked for the NYU systems group and helped implement a timesharing capability that allowed terminals to be attached to the CDC 6600. In those days being a system programmer was an exalted position and Bob was known as a very good one. In graduate school my interest was firmly in theory. Bob was in Jack Schwartz's SETL group and, unfortunately, I had little interaction with the group. But Bob and I were office mates for many years, and developed a friendship based on taking advantage of the cultural, sporting, and culinary opportunities afforded by New York City on a graduate student budget. These activities included finding the best cannelloni to be had in NYC and fending off bears backpacking in the Adirondacks. Bob was an accomplished musician, passing up a career as a professional musician for one in Computer Science.
After graduation in 1979 I headed to California and he to Rutgers. In New Jersey Bob met his wife Nieba. When Bob spent a year in California we were able to rekindle our friendship. I truly cannot think of a happier pairing of two good-natured and warm individuals than Bob and Nieba. They went on to have two children, Jane now twelve and John now eight. In California we had an opportunity to collaborate on the problem of optimizing iteration structures. Bob eventually returned to NYU and spent time in Wisconsin, Purdue, Yale, Copenhagen and Aarhus.
Bob's dedication to his work was especially evident to me after he became sick. I met him at a POPL meeting in Paris - most people in his condition would have been in bed. I spoke to him a few weeks before his death. The conversation was reflective, especially about the future direction of Computer Science and the status of his work. This is also evident in his retrospective, where he writes:
Over the last few years, I've felt that, finally, there was enough evidence and know-how to put together much of our work into a formal program development methodology that could achieve my goals of 20 years ago. Although I was too sick to carry this work out, I'm happy that my student Deepak Goyal has done it in his Ph.D. thesis.
Bob's work is being carried forth by his graduate students and Annie Liu, a WG 2.1 member who has taught Bob's method for algorithm design and analysis as a complete graduate course in Fall of 1999. A festschrift in his honor is being prepared by the journal Higher-Order and Symbolic Computation. The POPL 2000 meeting and proceedings were dedicated to his memory.