tial chunk of SetL code, four and a half
pages, that implements the algorithm.

I liked SETL and was amazed that they got some good compiling applications out of it. In the context of multicores and all the new challenges that we’ve got, I like it a lot—it’s one instance of specifying the problem at such a high level that there’s a good possibility of being able to target multiple machines and to get high performance from programs that are easy to write.

I have a story about register allocation. FORTRAN back in the 1950s had the beginnings of a theory of register allocation, even though there were only three registers on the target machine. Quite a bit later, John Backus became interested in applying graph coloring to allocating registers; he worked for about 10 years on that problem and just couldn’t solve it. I considered it the biggest outstanding problem in optimizing compilers for a long time. Optimizing transformations would produce code with symbolic registers; the issue was then to map symbolic registers to real machine registers, of which there was a limited set. For high-performance computing, register allocation often conflicts with instruction scheduling. There wasn’t a good algorithm until the Chaitin algorithm. Chaitin was working on the PL. 8 compiler for the 801 system. Ashok Chandra, another student of Knuth’s, joined the department and told about how he had worked on the graph coloring problem, which Knuth had given out in class, and had solved it—not by solving the coloring problem directly, but in terms of what is the minimal number of colors needed to color the graph.

the stretch look-
ahead was designed
on bar napkins,
particularly in the
old Brauhaus in
Poughkeepsie.

Greg immediately recognized that he could apply this solution to the register allocator issue. It was a wonderful kind of serendipity.

anything else we should know about
John Cocke?

He had a major impact on everybody. Let me talk about his style of work. He didn’t write anything, and giving a talk was exceedingly rare and painful for him. He would walk around the building, working on multiple things at the same time, and furthered his ideas by talking to people. He never sat in his office—he lost his tennis racket one time for several months and eventually found it on his desk. If he came into your office, he would start drawing and pick up the conversation exactly where he had left off with you two weeks ago!

So he was very good at co-routining!

Yes, he could look at a person and remember exactly the last thing he said to them. And people used to save his bar napkins. He spent a lot of time in bars; he liked beer. He would draw complex designs on napkins, and people would take the napkins away at the end of the evening. The Stretch look-ahead was designed on bar napkins, particularly in the Old Brauhaus in Poughkeepsie.

You also knew andrei ershov.

He did some marvelous work in the Soviet Union. Beta was his compiler, a really wonderful optimizing compiler. He had been on the ALGOL committee.

he had an earlier project that he called
alpha, not to be confused with the al-
pha language you did for Stretch, right?

No, it was totally unrelated. But later we read his papers. Then in 1972 he couldn’t travel, because he wasn’t a party member, so he had a workshop in Novosibirsk and invited a large number of people. It was broader than compilers, but there was a big focus on compilers, and we picked up some things from his work.

Ershov also worked with people in
China. When the curtain came down
between the Soviet Union and China,
the Chinese group then didn’t have
access to Ershov’s work. Jack and I
were invited to China in 1973 to lec-
ture. Mao was still alive, and a lot of
the institutes and universities were
pretty much closed. There was a sci-
ence institute in Peking and in Shang-
hai, where we gave talks on compilers,
and we looked at the machines there,
which were really quite primitive. The
compiler they were running on the
machine in Peking was on paper tape.
I recognized, looking at the code, that
it was essentially Ershov’s compiler.
So the people in China were really
quite concerned about being cut out
of the advances in computing. This
is a conjecture I’ve only recently ar-
rived at, why we in particular in the
U.S. were asked to come: it was a con-
nection through the technology that
the three groups shared. We were very
involved with Ershov and his group.
He and his family wanted to leave the
Soviet Union, and they lived with us in
our home for about a year.

You actually had two projects called
“experimental Compiling System.”
what was the second one like?

Its overall goals were to take our work on analysis and transformation of codes, and embed that knowledge in a schema that would advance compiling. I wish we had done it on Pascal or something like that.

PL/I was that difficult a language?

Yes, it was the pointers and the condition handling—those were the big problems. This was another bold project, and my interest was mostly in the generalized solution for interprocedural analysis—but also putting what we knew into a context that would make writing compilers easy and more formal, put more structure into the development of compilers. We already had a lot of great algorithms which we could package up, but this was to build a compiler framework where the methods that we already had could be used more flexibly.

Did lessons learned from this project
feed forward into your PtRaN work?

The interprocedural work did, absolutely, and to some extent the work on binding. It sounds trivial, but constant propagation, getting that right, and being able to take what you know and refine the program without having to throw things away and start over.