In the Loop: John Reynolds
John C. Reynolds has been a professor of computer science at Carnegie Mellon University since 1986. He retired from active teaching Jan. 1. A graduate of Purdue University, Reynolds earned his Ph.D. in theoretical physics from Harvard University.
His main research interests have been the design and definition of programming languages and the specification of program behavior.
A past editor of the Communications of the ACM and the Journal of the ACM, Reynolds was appointed a fellow of the ACM in 2001 and won the ACM SIGPLAN Programming Language Achievement Award in 2003. Reynolds was honored with the Lovelace Medal of the British Computer Society in 2010.
He spoke to Link Editor Jason Togyer.
What made you decide to retire?
I’m suffering from some health problems and I wasn’t sure I would be able to teach in the spring. But now that I’ve found out how much work it is to retire—you’d think that if there was one thing that would be made simple, it would be retirement—it’s a little scary!
Where did you grow up, and how did you get interested in science?
I grew up in the Chicago suburbs, in Glen Ellyn, Ill. My mother had been a schoolteacher and my father was in advertising. It was apparent by the time I got to school that my first love was music, and I thought I might become a musician—I played piano and trumpet. But somehow, science became more and more interesting. I wound up being one of the winners of the annual Westinghouse Science Talent Search, went to Purdue and did my graduate work at Harvard in theoretical physics.
One of your teachers at Purdue was Alan Perlis?
Yes—he left Purdue for Carnegie Tech in 1956, at the same time I graduated. While he was there he taught the one and only course in computing. It was half a semester on how to build them, and half on how to program them. One day, he walked into class and said, “I’m going to show you how to build a divider.” He started sketching this long equation on the board. Finally, one student said, “Professor, that won’t work with a negative quotient.” So he made some changes, and another student said, “Professor, now it won’t work with a positive quotient.” He made some more changes, and someone said, “It won’t work with a positive divisor!” Perlis said, “Well, that just goes to prove that you cannot design a divider on a Monday morning. Class dismissed!”
What was the state-of-the-art then?
Strictly machine language. This was before even Fortran. Perlis at that time was working on one of the first compilers.
When you got to Harvard, was it more up-to-date than Purdue?
Harvard at the time was under the spell of Howard Aiken, which means its computer system was completely obsolete. Fortunately, IBM had set up an installation at MIT that could be used by a consortium of other universities, and I had access to that.
How does one go from theoretical physics to computing?
Well, my Ph.D. was called “Surface Properties of Nuclear Matter,” but it was actually a big number-crunching program. I think I was the first person in theoretical physics at Harvard who used a computer to do his thesis, and that probably impressed the faculty more than they should have been impressed. I describe it as “an uninteresting computation of an unimportant quantity in a bad approximation”!
Where was your first stop after Harvard?
From 1961 to 1970 I worked at Argonne National Laboratory. While in grad school, I had worked at Argonne during the summers, because it was close to my home, and I went to Argonne after Harvard because they would have been happy with me to either stay in physics or move to computing. By that time, I had gotten very interested in compilers and programming languages, and one of the first things I designed was a compiler—actually, a compiler for compilers called COGENT, because the kinds of programming languages that we had then were not suitable for symbolic manipulation. We needed list processing, that sort of thing.
You moved from Argonne to Syracuse in 1970. Why?
There was a much larger group of people to whom I could talk about my research. That meant both having many more colleagues but also having students, and frankly, I found that if you want to want to discuss something with somebody, your primary criteria is going to be, is this person interested in what I have to say? And whether they’re a student or faculty is entirely secondary.
What eventually brought you to CMU?
Initially, what attracted me were the reputation, and the high quality research I saw here. You have to have people with whom you share common goals on the one hand, but on the other you have to have people who bring different skills and talents and complement each other. At CMU, many of the people were working on functional programming languages, while I tended to work on imperative programming languages. I think that’s made my research stronger in that I haven’t limited myself to one side or the other.
What attracted you to working on the semantics of programming languages?
The fact that I could design the rules of the language based on a few essential principles that were very easy to implement and learn. Looking back, I think I have a terrible memory, and probably the big thing that excited me about math was that there were general principles by which you could derive things, and it didn’t have the ad-hoc nature of, say, history.
Along with Jean-Yves Girard, you’re credited with inventing polymorphic lambda calculus. How did you come to be working on the same thing at the same time in different places?
Jean-Yves is a first-rate logician. He took that concept and explained it much more deeply than I could have from a theoretical standpoint. He proved that every program you could write in the calculus will always finish, but some such programs will take an incredibly long time to finish—which doesn’t sound that unusual now, but was unheard of then. My contribution was to show that it could be useful to pass types around as parameters, and my real discovery was that you could type-check a polymorphic language statically, in other words, catching errors between different types of data.
Polymorphism—the ability to handle many different data types with the same programming language—has become ubiquitous, and your work, along with Girard’s, has been credited with leading to most of the modern computer languages. Would you agree with that?
Oh, I’m not sure I’ve had all that much influence on polymorphism, and there are plenty of programming languages that I haven’t influenced at all. The idea of polymorphism was really conceived by Christopher Strachey back in 1967, that if you have a sorting program and it will work for any “something,” it is polymorphic, and he’s the reason that Britain is still the leader in the field. In the latest James Bond film, there is a point at which a computer displays some kind of a graph that suddenly gets three times larger, and the “geek” character says, “Good heavens, it’s gone polymorphic!” When we saw that, my wife and I burst out laughing! So maybe I’ve had a tremendous influence on pop culture?
Where do you think your work has been influential?
Polymorphism, to some extent, but also my work on definitional interpreters—defining the limits of a programming language by writing an easy-to-understand interpreter—and defunctionalization, which has been useful in reducing higher-order functions to simpler abstractions. Those have had a fair amount of influence. And third, separation logic—which is an extension of the normal predicate calculus that you use in Hoare logic—to determine the correctness of a program.
What advice would you have for a student just starting out in computer science?
There are so many things that need to be said! One is that many grad students feel they have to completely master their field before they can do anything. Quite apart from the amount of time that would take, it’s stultifying. It shouldn’t be your goal to learn everything. It should be your goal to discover things that other people have to learn.
Are you pursuing any hobbies in retirement?
I still play piano from time to time. But it’s a problem because if you reach some level of technique and then you let it go, it’s really painful to get it back. It’s a bit of an uphill struggle, but I would like to start playing again. Both my wife and I also love going to musical and dance performances, and I’m doing a pretty good job catching up with my reading.