People of Programming Languages

An interview project in conjunction with POPL 2018  

 

JY: Tell us about yourself. How did you get here?

TR: When I finished college, I swore to myself I would never go to graduate school. My father had a friend who was a banker. The banker had just loaned money to a small company in Ithaca, New York, where I had grown up, to create a computer for astrologers. This was 1977. The banker had these people do a business plan, and he found that there were something like 6,000 professional astrologers in the United States at the time. There are seven different schools of astrology. They were going to build a dedicated box with a switch to select which of the seven schools to use.

They hired me in November 1977. They didn't have a computer, but wanted me to work on some of the algorithms. My boss said, "You still look like an undergraduate; just go up to Cornell where they have an open card reader.” They gave me the program on a thick stack of punch cards. My work involved solving an equation to subdivide the path of the sun from horizon to horizon into 12 stations—that is, into 12 equally spaced intervals along the sun’s path. The program was solving the equation by iteration. The reason I am going into so much detail, is because fast forward 10-30 years later and what am I working on? I'm solving equations by iterative methods.

In college, I had taken a numerical-analysis course, and had learned that iterative methods could diverge. I started to think about it and I figured out that in fact the program could diverge. So I went to my boss, and I said, "Jim. Did you know this equation can diverge?" He said, "Oh that'd be terrible! Can it happen?" I said, "Yes." And he said, "What are the conditions?" I said, "Well, if you're born above the Arctic Circle, in the part of the year with the midnight sun, there is no intersection of the horizon and sun’s daily path.” I was proud I could give a physical interpretation. He said, "Don't worry, Tom. Our customers are not Laplanders and Eskimos. I think we're okay."

Fortunately, after three days Tim Teitelbaum, who was then a young, untenured assistant professor, said, "Look, the department has finally bought its first computer, a PDP 11/45, and I think we should create a tool that has a screen-oriented editor and an interpreter in it. I'm looking for help.” And Dick said, "Well, Tom just showed up. He's not doing anything. He's yours."

Tim was actually about to be fired because he had not done much in the way of research in the four or five years he'd been at Cornell. But he had done a great job teaching the introductory programming class, and so he'd been renewed on a year-to-year basis. He didn't have any students, but what that meant for me was that I had a private tutor for a year. It completely changed everything. And it got him started on research and eventually he got tenure.

After a year, Tim said, "What you're doing is not all that different than what the graduate students are doing, but at the end they’ll have a degree and you won't. So why don't you enroll?" And so I did, with the intention of getting a masters degree. But then I had a good result, which was the main result of my PhD thesis, at which point he said, "Well forget about that masters thesis. Just write it up as a PhD and then you're done." Which is what I did.

I was then involved with Susan Horowitz, as I was for 34 years, who was another one of Tim's students. We went with Tim on his sabbatical to Inria in 1982/83, and then came back to Ithaca for another two years while Susan was finishing her degree. Then we both got positions here at Wisconsin; we both moved up through the ranks; and we had sabbaticals of our own. I've had some excellent students, and it's been really great. That's how I got here.

JY: What were you working on with Tim that first year?

TR: We were building what was called the Cornell Program Synthesizer. It was an integrated programming environment. At the end of a year, Cornell converted all of their 500 or 600 students in the introductory programming class from being on punch cards to being on the programming environment that we created for them. It's essentially like going from punch cards to Eclipse in the space of one year. To write programs, it gave you templates for all the constructs, and also did things like check some non-context free syntactic conditions like, "Are all your variables declared? Are your variable declarations consistent with the uses in the program?" And then you could press execute. That invoked the interpreter, and you could set things up so that you could watch variables change value, do single-stepping, and the cursor was a kind of “bouncing ball” moving through the program to show the program counter.

JY: What were the main challenges of that work?

TR: This computer was very severely memory limited. 56 kilobytes. Kilobytes. Not megabytes. Kilobytes. Eight kilobytes was stolen for a micro operating system that Alan Demers, one of Tim's colleagues, wrote. We had 48k bytes of memory. So you couldn't write very big programs, but it was enough so that you could do the programs for an introductory programming class. It also had a bitmap display, so there could be assignments that exposed them to a little bit of graphics.

We wanted to create similar kinds of systems for other languages, and that became the project that I worked on next, the Synthesizer Generator, which I was going to do for a master’s degree. The Generator was to be kind of like the parser generators yacc or bison, but for creating editors. One thing that was challenging was the problem of how you make an editor show whether the program’s variables are declared consistently with the way the variables are used in the program. In the Cornell Program Synthesizer there wasn’t really incremental type checking—we had just used brute force, and completely reanalyzed each procedure whenever there was a change to any variable declaration. The approach I took in the Synthesizer Generator was to use attribute grammars for specifying things like type-correctness conditions, and attributed trees as the underlying data-structure in the editor. I developed an algorithm for updating a tree’s attribute values after each modification to the tree. The interesting thing about that algorithm is that it does essentially as little work as possible—in other words, it is asymptotically optimal. That got to be a very well-known result in our field in the 80s and early 90s, and inspired a number of other people to work in the area.

JY: And was that the main result of your thesis that you were talking about?

TR: Yes; the thesis was titled “Generating Language Based Environments.” It had that algorithm and a couple of other attribute-grammar-related algorithms. It also had a short chapter about one application that we used it for, which was proof checking. We built editors that allowed you to create proofs in various logics and programming logics, and the attributes would indicate inconsistencies in the proof that you were building. Today we have Coq and nuPRL, but that was a forerunner. The paper about it was at POPL in 1984.

JY: How do you decide what the next problem is to work on?

TR: I've rarely written a proposal in which I put my finger on the nub of the key problem ahead of time. And those in which I did were problems that I'd already done years of work on. It's a process that I can't explain. I just fall into some things. I try to go to talks on a wide variety of topics. Not just PL talks, but ones in all sorts of fields—anything that sounds interesting. Sometimes there's a connection; sometimes I don't understand what's going on.

JY: Has your relationship with the community shifted over the years? If so, how?

TR: Certain things have shifted. I went from the work on incremental attribute evaluation in the 80s to slicing and then data-flow analysis in the 90s. All of those were topics that at least some part of the POPL community was interested in. The work on incremental attribute evaluation also got me interested in incremental algorithms in general. With Ramalingam, who was a student in the late 80s/early 90s, I worked on incremental graph algorithms. We tried to submit that work to all sorts of places, including POPL, and various theory conferences. Nobody liked what we were doing. That was kind of discouraging, but if you look at the papers that came out of that work, they're actually ones in which the highest citation counts are in the last five years or so. That's an example of when I was not in sync with the POPL community.

JY: Is this related to your “POPL drought?”

TR: That came later. I had a few papers in the mid to late 90s that appeared at POPL—for instance, the papers on shape analysis with Mooly Sagiv and Reinhard Wilhelm. Then I became the POPL Program Chair in 2000. But the very next year started a drought for me, which lasted sixteen years. There was an interlude when two papers were accepted, but it was basically a sixteen-year drought.

Looking back on it, it seems a little weird. Although it also makes me think of something in the new Star Wars movie, which I went to see last night. At one point Yoda says, "The best teacher, failure is." Anyway, it wasn't for lack of trying—or, in my opinion, that I’d stopped doing interesting work. Some of it was strange refereeing—I can think of two papers, in particular. Another thing that could have been part of it is that in the 80s and 90s we didn't really do that much in the way of reporting on experimental results. POPL moved in that direction to some degree, and so possibly there was a bit of a mismatch with what my students and I put in our papers. Another thing was that I started to do a lot of work on machine-code analysis beginning in 2001, and we were starting to try to publish that around 2003. POPL didn't seem interested in the kind of approach that we were taking, using abstract interpretation. They accepted a bunch of things by other people based on type theory, separation logic, Coq proofs, and stuff like that. There just wasn’t any interest in the approach we were taking.

Another issue could be related to what Alex Aiken calls the "attack surface of a paper." If a paper has too many ideas in it, it increases the chances that a reviewer will find something to object to and get the paper rejected. The paper that actually ended the drought in 2016, "Newtonian program analysis via tensor product," had that kind of exposure. It gives a new algorithm for interprocedural analysis, along with experiments comparing it against a standard algorithm and a not-so-standard algorithm. Our algorithm was somewhat better than the latter, but much worse than the former. Before submitting to POPL, I asked one senior member of the PL community what he would do in such circumstances; his advice was, "Submit it without any experiments." I couldn't bring myself to do that; I submitted it with both experiments, and crossed my fingers. Someone who was on the Program Committee that year told me that the PC chair, Rupak Majumdar, had a very interesting policy. When a paper had both a strong supporter and a strong detractor, his attitude was, "We should accept this paper because it will get participants talking at the meeting." I don't know whether that policy was applied to our paper, but I think it is a very interesting take on what makes for a good conference paper, as well as on how to handle the dynamics of a PC meeting.

Fortunately the verification community also changed direction, from analyzing hardware to also analyzing software. So we shifted to publishing in a different set of conferences. And at some point I decided I just had to stop caring. Fortunately, Google lets people find things that are published regardless of venue, so in some sense it doesn't really matter what the venue is. Eventually good ideas bubble to the surface.

JY: I was hoping you could talk about GrammaTech and how that came about.

TR: GrammaTech was originally founded by Tim Teitelbaum and me to commercialize the Synthesizer Generator, the attribute grammar-based system that had come out of my PhD thesis. I was a post-doc at Cornell from ‘83 to ‘85. In those days you didn't download software. You mailed a check to Cornell, and we sent you a tape. That was our software-distribution system, and so we knew exactly who was using the system. In about 1987, Ralph Wachter at ONR, who was funding Tim, said that while we had over 300 companies and universities using the system, it was not something he could continue to support as a research project. He asked us if we wanted to form a company, and suggested that we apply for an SBIR grant. The government runs the SBIR (Small Business Innovation Research) program to support tech transfer out of universities.

We incorporated, wrote a proposal to the SBIR program, and got that. An SBIR grant comes in two phases. There's a six-month first phase, then there's usually a gap until they decide about the second phase, and if you get that, it lasts two years, at which point you're supposed to be ready for commercialization.

Then what we found was that the world didn't really want what we had produced. One company, Ford Aerospace, took the Synthesizer Generator and built an Ada editor with it, but they didn't want to be in the support business, so they gave the thing back to us. Suddenly we were in the Ada business. It kind of limped along for a while, and then what happened was the mandate to use Ada in DOD software went away. That sort of knocked the legs out from the companies that, like GrammaTech, were doing Ada work. By this time we'd grown—this was around 2000 or 2001—we'd grown to maybe ten people or so.

Then we just wrote a whole bunch of SBIR proposals. What was amazing about this was that GrammaTech wrote eleven proposals, and in the next 18 months they all got funded. The normal thing is that the SBIR program funds about one-out-of-eight to one-out-of-twelve proposals. That success led to a much bigger research program. Then Dave Melski, who is one of my former students from Wisconsin, joined GrammaTech in 2002, and he and Tim, and now Alexey Loginov (another one of my former students) have really built up the research side of the company. About half the company is doing that, and I think we just went over 80 people.

JY: Has the experience changed how you view the role of academic languages research versus what companies could and should be doing?

TR: It's given me more exposure to projects that are more grounded in reality. The machine-code analysis research at Wisconsin actually came out of a project that GrammaTech started. Our longest-serving employee, Paul Anderson, had written a proposal to the Air Force about information-flow analysis of machine code. He wanted to put together the IDA Pro disassembly tool, as a front end, and the CodeSurfer dependence-graph-based program slicer, as a back end, and somehow get these two tools to cooperate. In the meantime Somesh Jha, Bart Miller, and I at Wisconsin wrote a very similar proposal to ONR. Ralph Wachter at ONR was funding both of these efforts, and didn't want to pay for the same thing twice, so he got us all working together.

JY: How has your view on what makes a good problem changed over the course of your career?

TR: If I look at it from the point of view of personal satisfaction, I don't think it's changed. The ideal is something where there's some nice mathematical technique or formalism that is new to me, and has a nice fit with the problem, and I get to learn it as I go along.

One change is that I’ve learned more about problems that can have impact. One of the most impactful of my projects is the stuff that we did on machine-code analysis. During that period of time, it felt like, “Hey, this is what I've been training to do all my life, and I finally found the right problem!” It was a great fit for the skills that I had and the knowledge that I had, and the students who were at Wisconsin at the time. Another thing that was an incredible example for everybody in the community was the SLAM project, a model checker for detecting bugs in critical software that is now in Microsoft’s Windows Driver Development Kit. When Tom Ball first described it to me, you could see that all the pieces were coming into place. It was something where the problem that was facing the company—namely, crashes in the Windows operating system for which Microsoft was being blamed, even though they weren't really responsible for the problematic software—was creating an incredible headache for Microsoft. What Tom and Shriram Rajamani found was that the computers at the time were fast enough and had enough memory so that some great ideas from the research community, plus some great things that they devised themselves, could be brought to bear on the problem—not make it go away exactly, but go a long way toward making it okay for Microsoft. Sometimes a problem fits exactly with the technology of the time like that. That's the ideal situation, but it doesn't come along all that often.