How Two Bell Labs Researchers Set the Rules for the Modern Compiler – InApps 2022

Two alumni of the historic Bell Labs research facility recently have received one of the highest honors in the computer programming field.

Two @EPrinceton Ph.D. alumni have been named recipients of @TheOfficialACM‘s 2020 ACM A.M. Turing Award — often referred to as the “Nobel Prize of Computing.”

Congrats to Alfred Aho *67 and Jeffrey Ullman *66! https://t.co/mqhP1BPgrZ

— Princeton University (@Princeton) April 8, 2021

Alfred Aho, 79,  and Jeffrey Ullman, 78, were awarded the prestigious Turing Award by the Association for Computing Machinery (ACM), a 100,000-member professional group describing itself as “the world’s largest scientific and educational computing society.” Every year since 1966, the group has awarded the prize to recognize contributions “of lasting and major technical importance to the computer field,” and it’s been described as the Nobel Prize of computing — a claim the ACM takes very seriously. In 2011, Network World reported that the ACM once even approached the Nobel Foundation offering to fund a Nobel Prize for computing — and was turned down. The co-chair of the ACM’s Awards Committee told the publication that “we think the quality of our award is comparable.”

Ullman and Aho were being officially recognized for a lifetime of work on “fundamental algorithms and theory underlying programming language implementation and for synthesizing these results and those of others in their highly influential books, which educated generations of computer scientists.”

The award shows how two technology workers can make an impact on the world, leaving behind a legacy and a simple but irrefutable reminder of how we’re always building on the work of those who came before us. But it’s also heartening that the two men were recognized for their commitment to sharing what they’d learned.

Translation Technologies

In announcing the award 2020, the ACM noted the recipients’ work’s unusually large impact. While our technology today is powered by software, “virtually every program running our world — from those on our phones or in our cars to programs running on giant server farms inside big web companies — is written by humans in a higher-level programming language and then compiled into lower-level code for execution.

“Much of the technology for doing this translation for modern programming languages, under the hood, owes its beginnings to this year’s Turing Award winners.”

The ACM’s website even argues that efficient compilers “exist nowadays in large part due to the work of Aho and Jeffrey D. Ullman.” A recent article explains how the two had basically offered an early and influential roadmap for the way that these code-translating compilers should work. It starts with the code-checking “lexical analysis,” followed by the syntax-checking parser, and then a final semantic analysis of the larger whole, creating an intermediate output that can then be optimized into a high-speed machine language for your particular machine. But Ullman and Aho had first started by systematically studying all of the existing models and algorithms for both compiling and parsing, Aho recalled in an ACM interview. Then, they  synthesized what they’d learned in their 1972 book, “The Theory of Parsing, Translation, and Compiling.”

Yet they’d also continued their work and research, along the way creating some components for Unix tools Lex and Yacc that helped automate the creation of compilers. In fact, Yacc was more or less invented from watching the way Aho worked. In the 1994 book, “A Quarter Century of Unix,” their Bell Labs colleague Stephen C. Johnson recalled Aho spending hours to create a vast parsing table for the B programming language for him — but then discovering a bug, and having to erase vast parts of that table. (Only to then discover yet another bug…)

“So I said, ‘Al, why don’t you tell me what you’re doing?’ And he said, ‘Well, OK, it’s really not that hard.’ And he told me how to make the table. And I said, ‘Oh, well I can write a program to do that.’ He said, ‘Really?’ So that’s how Yacc was born.”

A Lesson from Bell: the Value of Teaching

In their ACM interview, Aho shares an important life lesson he learned at Bell Labs from Richard Hamming, a mathematician (and former Manhattan Project scientist) who’d joined Bell Labs in 1946. Hamming himself won one of the first Turing awards back in 1968, according to a biography on the ACM site, but by 1960 he’d already begun lecturing in computer science, eventually leaving Bell Labs altogether in 1976 to take a senior lecturer position at the Naval Postgraduate School at Monterey, Calif. When young Aho joined Bell Labs back in 1967, “In my first week, he told me that if you want to be a great scientist, you have to do more than great work; you have to teach others how to use your work.

“I found this combination of doing research, writing books, and teaching a very fruitful combination…”

Professor Al Aho and his long-time collaborator Jeffrey Ullman are featured in this month’s Communications of the ACM for winning the 2020 Turing award. They talk about how their work has educated generations of computer scientists. @CUSEAS https://t.co/lHnW7aeBB8

— ColumbiaCompSci (@ColumbiaCompSci) June 2, 2021

Aho came to recognize the value of collaborating — and of sharing what you’d learned. Even after Ullman had left to join academia, he’d still return to Bell Labs about once a week to continue collaborating with Aho, according to the ACM’s website. “Despite working at different institutions,” ACM reported, “Aho and Ullman continued their collaboration for several decades, during which they co-authored books and papers and introduced novel techniques for algorithms, programming languages, compilers, and software systems.”

Ultimately, the ACM noted, Aho continued working at Bell Labs for more than 30 years (where he became the organization’s vice president of computing sciences research), before finally taking a faculty position at Columbia University in 1995.

After their first book, Aho and Ullman had continued researching compilers, which led to a second book titled “Principles of Compiler Design” — a volume so ubiquitous it’s sometimes just called “the dragon book” because of the familiar dragon illustration on its front cover. Subsequent editions picked up additional co-authors, like Ravi Sethi and Monica Lam.

Even decades later, in a 2016 video, Ullman acknowledged that “I always have felt that my contribution was in the books that I wrote, and how it influenced young people to do great work of their own. Many of them have gone on to greater things than I’ve ever done.” (He points out that one of his students at Stanford was future Google co-founder Sergey Brin.)

Measuring Influence

As part of its article about this year’s Turing Award winners, the ACM also spoke to Krysta M. Svore, who leads the quantum computing group at Microsoft Research. Svore remembers taking Aho’s class when she was a student at Columbia, where she learned the ideas he and Ullman developed in the 1960s and ’70s that she’s now applying to cutting-edge research. “What they developed is still critical for writing programs across smartphones, across quantum computers, across your laptop. These technologies are very much forever critical.”

The award winners’ profile on the ACM website notes that “the impact of their work since the 1970s is so profound and so pervasive that it is easily taken for granted. Anyone who has programmed in C or any of its derivatives; anyone who has used Unix tools, such as AWK, fgrep, Lex, and YACC; anyone who has taken a compiler course; or anyone who has built a compiler by just reading the Dragon Book has been touched by the work of Aho and Ullman.”

It credits their book “The Design and Analysis of Computer Algorithms” with forging a collection of design methods from a wide range of algorithms, including divide-and-conquer, recursion, and dynamic programming, “that have long since entered the standard toolbox of computer scientists.”

This March, an announcement of Aho and Ullman’s Turing Award even included some applause from Jeff Dean, a Google Senior Fellow and senior vice president at Google AI. “Aho and Ullman established bedrock ideas about algorithms, formal languages, compilers, and databases, which were instrumental in the development of today’s programming and software landscape.”

And in the same announcement, ACM President Gabriele Kotsis called their work “especially influential. They have helped us to understand the theoretical foundations of algorithms and to chart the course for research and practice in compilers and programming language design.

“Aho and Ullman have been thought leaders since the early 1970s, and their work has guided generations of programmers and researchers up to the present day.”

InApps is a wholly owned subsidiary of Insight Partners, an investor in the following companies mentioned in this article: turing.

Feature image par Gerd Altmann de Pixabay.