Skip to content

Fran Allen: 1932-2020

August 8, 2020

We lost a great computer scientist.

Frances Allen was one of the leaders who helped create the field of compilers research. Fran was an elite researcher at IBM, and won a Turing Award for this pioneering work. Allen also collected other awards.

Perhaps the coolest award is one that Fran could never win: The Frances E. Allen award created this year by the IEEE:

For innovative work in computing leading to lasting impact on other fields of engineering, technology, or science.

Today we will talk about Fran, who sadly just passed away.

I consider Fran a friend, although we never worked together—our areas of interest were different. One fond memory of mine is being on panel a while ago with Fran. What a delightful presence.

Fran always seemed to be smiling, always with that smile. The following images come in large part from interviews and lectures and award events-the fact that it is so easy to find them is a testament to her public engagement as well as scientific contributions.

Compliers were Key

There was a time when compliers were the most important program available on any new computer. Perhaps on any computer. Here is proof:

  1. Computers are there to solve problems.

  2. We must write programs to solve problems.

  3. Details of the computer and instructions, are complicated, which make writing programs hard.

  4. Thus, automating the writing of programs is important.

  5. QED: we must have compliers.

Okay this is not really a “proof”, but there is some truth to the argument. Fran was at IBM and worked on some of the early compliers, including FORTRAN and related languages. IBM wanted to sell computers, well actually in the early days rent them. One potential roadblock, IBM realized, was that new computers could be hard to program. Thus to ensure that companies rented new machines as fast as IBM could manufacture them was important. This created the need for compliers and even more for optimizing compilers.

In order to ship more machines, the code that a complier created had to be efficient. Hence, a stress on Allen was to figure out how compliers could generate high quality code. This led Fran and others like John Cocke to discover many complier techniques that are still used today. A short list of the ideas is:

  • Branch prediction

  • Register allocation

  • Control flow graphs

  • Program dependence graphs

  • And many more.

What is so important is that Allen’s work was not just applicable to this machine or that language. Rather the work was able to be used for almost any machine and for almost any language. This universal nature of the work on compliers reminds me of what we try to do in theory. Allen’s research was so important because it could be used for future hardware as well as future languages.

Register Allocation

Guy Steele interviewed Allen for the ACM here. During the interview Fran talked about register allocation:

I have a story about register allocation. FORTRAN back in the 1950’s 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 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. Greg immediately recognized that he could apply this solution to the register allocator issue. It was a wonderful kind of serendipity.

Compliers Create Theory

The early goal of creating compliers lead directly to some wonderful theory problems. One whole area that dominated early theory research was language theory. In particular understanding questions that arise in defining programming languages. Syntax came first—later semantics was formalized.

Noam Chomsky created context-free grammars to help understand natural languages in the 1950s. His ideas were used by John Backus, also a Turing award winner from IBM, to describe the then new programming language IAL. This is known today as ALGOL 58, which became ALGOL 60. Peter Naur on the ALGOL 60 committee called Backus’s notation for ALGOL’s syntax: Backus normal form, but is now called BNF-Backus-Naur form.

Theorists worked on, I confess I did, many questions about such languages. Existence problems, decidability problems, efficient algorithms, and closure properties were just some of the examples. Not clear how much of this theory effected compiler design, but I would like to think that some was useful. Theorist should thank the complier researchers. I do.

For instance the 1970 STOC program had many papers on language related topics—here are some:

  • A Result on the Relationship between Simple Precedence Languages and Reducing Transition Languages. Gary Lindstrom

  • The Design of Parsers for Incremental Language Processors: Ronald Book, Sheila Greibach, Ben Wegbreit

  • Tape- and Time-Bounded Turing Acceptors and AFLs. David Lewis

  • Closure of Families of Languages under Substitution Operators. William Rounds

  • Tree-Oriented Proofs of Some Theorems on Context-Free and Indexed Languages. Barry Rosen

  • On Syntax-Directed Transduction and Tree Transducers. Alfred Aho, Jeffrey Ullman

  • The Analysis of Two-Dimensional Patterns using Picture Processing Grammars. Jean-Francois Perrot

  • On Some Families of Languages Related to the Dyck Language. Joseph Ullian

  • Three Theorems on Abstract Families of Languages. Joseph Ullian

By the way Abstract Families of Languages or AFLs was created by Seymour Ginsburg and Sheila Greibach in 1967 as a way to generalize context free languages.

Open Problems

Fran was asked by Steele in that interview: Any advice for the future?

Yes, I do have one thing. Students aren’t joining our field, computer science, and I don’t know why. It’s just such an amazing field, and it’s changed the world, and we’re just at the beginning of the change. We have to find a way to get our excitement out to be more publicly visible. It is exciting, in the 50 years that I’ve been involved, the change has been astounding.

Thanks Fran. Much of that change is due to pioneers like you. Thanks for everything.

5 Comments leave one →
  1. August 8, 2020 10:39 am

    Computer science have such amazing connections, nice article.

  2. Recovering Quantum Mechanic permalink
    August 8, 2020 1:52 pm

    s/compliers/compilers/ ?

  3. August 8, 2020 2:16 pm

    may she rest in peace …

  4. August 9, 2020 6:56 pm

    Given how often my computer fails to comply with my wishes, having a complier would be really useful.

    More importantly, thanks for educating me about Fran.

  5. David J. Littleboy permalink
    August 10, 2020 1:56 am

    In that interview, Ms. Allen talks about teaching Fortran:

    “I had a pretty unhappy class, because they knew they could do better than any high-level language could.”

    That attitude continued for a long time. One story (apocryphal, perhaps) from the ’70s was that one of Data General’s competitors published an ad claiming “Our Fortran compiler is better than your assembler programmers”, getting all sorts of assembler types seriously bent out of shape, seeing red, and frantically attempting to prove said ad as ridiculous as they knew it to be. All failed. It turned out the machine in question had an undocumented double-indexing instruction that the compiler knew about.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s