## Fran Allen: 1932-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:

- Computers are there to solve problems.
- We must write programs to solve problems.
- Details of the computer and instructions, are complicated, which make writing programs hard.
- Thus, automating the writing of programs is important.
- 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.

## A Brilliant Book on Combinatorics

*And Razborov’s brilliant proof method*

Stasys Jukna is the author of the book *Extremal Combinatorics With Applications in Computer Science*.

Today we talk about Jukna’s book on extremal combinatorics.

## Mathematical Search

*A flying start from nearby Rochester*

Anurag Agarwal and Richard Zanibbi are tenured faculty in Mathematics and Computer Science, respectively, at RIT. They partner with Clyde Lee Giles of Penn State and Douglas Oard of U.Md. on the MathSeer project. If the name reminds you of CiteSeer, no surprise: Giles co-originated that and still directs it.

Today we note last month’s release of a major piece of MathSeer called MathDeck and show how to have fun with it.

## Ron Graham, 1935–2020

*Ron Graham passed away, but he lives on…*

Cropped from tribute by Tom Leighton |

Ron Graham just passed away Monday at the age of in La Jolla near UCSD.

Today Ken and I wish to say a few words about Ron.

## Intellectual Fireworks?

*Some different ideas for marking the Fourth*

“Founding Frenemies” source |

John Adams and Thomas Jefferson did not use Zoom. Their correspondence, from 1777 up to their deaths hours apart on July 4, 1826, fills a 600-page book.

Today, Independence Day in the US, we consider the kind of intellectual fireworks represented by the correspondence.

## Taking a Problem Down a Peg

*By blowing up its objects*

Composite crop of src1, src2 |

Joshua Greene and Andrew Lobb proved last month that every *smooth* Jordan curve in the plane and real , there are four points on the curve that form a rectangle with sides of ratio .

Today we explain how this result relates to Otto Toeplitz’s famous “square peg conjecture,” which is the case when the curve need not be smooth.

## Some Real and Some Virtual News

*Gossip and more.*

Composite of , src1, src3 |

Jessica Deters, Izabel Aguiar, and Jacqueline Feuerborn are the authors of the paper, “The Mathematics of Gossip.” They use infection models—specifically the Susceptible-Infected-Recovered (SIR) model—to discuss gossip. Their work was done *before* the present pandemic, in 2017–2019. It is also described in a nice profile of Aguiar. Their analogy is expressed by a drawing in their paper:

Not just for today, but for the summer at least, Ken and I want to share some gossip, share some problems, and ask our readers a question.

## P<NP

*Some thoughts on P versus NP*

Norbert Blum is a computer science theorist at the University of Bonn, Germany. He has made important contributions to theory over his career. Another claim to fame is he was a student of Kurt Mehlhorn, indeed the third of Mehlhorn’s eighty-eight listed students.

Today I wish to discuss a new paper by Blum.