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
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
Greg immediately recognized that he
could apply this solution to the register
allocator issue. It was a wonderful kind
anything else we should know about
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
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
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.