Alfred Aho

Alfred Aho was just digging out from the end-of-semester overload, wrapping up his legendary course, Programming Languages and Translators.

“It’s my favorite course, and this is the text we use,” Aho said, reaching over to a bookcase in his office at Columbia University. He procured the “purple dragon book” — the latest edition of his “Principles of Compiler Design,” arguably the best-selling compiler textbook worldwide (a compiler is a tool for translating programs from one language to another). Co-authored with Stanford’s Jeff Ullman and published in 1977, the first edition became known as the “green dragon book,” and subsequent editions with additional co-authors evolved through the “red dragon book” to the latest printing in purple in 2007.

“What made me famous in the eyes of my children was that the previous edition of this book was shown in the movie ‘Hackers,’” Aho continued. “The über-hacker was demonstrating to a young Angelina Jolie and her companion how to become a great hacker, and said, ‘You have to read these ten things,’ and the dragon book was flashed on the screen for about 10 seconds. I just about fell out of my chair when I saw that.”

Aho is not one to readily fall out of chairs. His demeanor is calm, collected and precise, and he chooses his words carefully. Born in Canada, he got his start as a computer scientist at the University of Toronto. He migrated to Princeton for his doctoral studies with John Hopcroft (now at Cornell). “When I came to Princeton, I met Jeff Ullman in the registration line, and then I met John Hopcroft, and I said, ‘I must be on a different planet!’”

With Hopcroft as his adviser, Aho began his career-long habit of asking questions. Hopcroft had just arrived at Princeton and was faced with two doctoral students but only one research problem. Hopcroft gave the problem to his other student — fortunately for Aho, because it was a problem that ended up taking 30 years to solve. “Hopcroft said, ‘You find your own research problem,’” Aho recalled. “And I spent the first six to nine months of my third year tearing my hair out, looking for a suitable topic.”

Taking inspiration from MIT’s Noam Chomsky and his work in formal grammars for languages, Aho found his thesis question: How can we extend the power of grammars — which, in their essence, are rewrite rules governing sentence construction — to describe the structure of programming languages?

Or, as Aho described his question slightly more technically:

“Can we find a way of describing more of the syntactic structure of programming languages than we can with context-free grammars, but at the same time preserving many of these grammars’ desirable properties?” Context-free grammars are grammars that generate sentences using syntactic constructs no matter what comes before or after, hence without context.

“To this end I discovered a new class of grammars with a new kind of rewrite rules, that I called the ‘indexed grammars,’” Aho explained. “These grammars could specify all of the syntactic constructs of context-free grammars, and they could also specify a number of non-context-free constructs found in programming languages.” Aho’s indexed grammars were more general, and thus more powerful.

Since he obtained his doctorate at a time when there were few computer science departments in academia, a research lab seemed the natural place to land when it was time to look for a job. “At that time,” Aho recalled, “Bell Labs was a researcher’s nirvana. I joined this fledgling group called the Computing Sciences Research Center. There were only a handful of us in there, but this collection of people ended up having a profound impact on the field of computer science, and on the whole industry of computer science. This is the lab that invented Unix and C.”

It was the perfect environment for Aho to develop his penchant for asking questions, now taking his inspiration from Stanford’s Don Knuth and his invention of LR parsing — that is, finding the structure of computer input from left to right, character by character, and figuring out the meaning without backtracking and reconsidering previous conclusions. Aho, teaming up with Ullman and Stephen Johnson, optimized and applied Knuth’s algorithm in a tool they named Yet Another Compiler Compiler (a compiler compiler is a tool for making compilers). Commonly referred to as yacc, it is still the tool of choice for creating parsers for programming languages.

“What I really liked about Bell Labs was that you were surrounded by brilliant people from a variety of disciplines,” Aho said. “If you ever had a question about mathematics or physics, you could go to the world expert in that area and get an answer instantly. It was also a very problem-rich environment. People were thinking about all sorts of new areas, new things to work on, and sometimes if you had a perspective or an idea on how to attack a problem that some of the other researchers didn’t, it led to a wonderful opportunity to do some collaboration.”

With his Bell colleagues Peter Weinberger and Brian Kernighan, he designed the programming language AWK. “I just recently got a book from a German biologist who has been very fond of using AWK to study problems in genetics,” Aho said. “He has huge files, and he’s using AWK programs to look for patterns in DNA sequences. He said the reason he’s using AWK is because it’s so easy to learn and so effective for solving the kinds of problems he’s interested in.” What began as a practical tool — just something Aho and his colleagues could use to solve routine data-processing problems — took on a life of its own. The name AWK, drawn from the last names of the three designers, also came about unintentionally — when Bell colleagues saw the trio working so hard and often in each other’s offices, they took to walking by the open doors and saying, “AWK! AWK! AWK!” But the law of unintended consequences had happy collaborative results.

“When you work closely with people you get to know how they think, and that is really scary — scary in a wonderful way,” Aho said.

Working with Aho, his colleagues came to learn that questions are crucial to how Aho thinks.

“He asks questions — what are the five most important things of some sort, or the 10 most difficult problems — he would go around and ask,” Weinberger said.

The K in AWK concurs. “He’s always asking questions about the big picture,” Kernighan said. “In some ways it’s almost a cliché that he comes up with questions like ‘What are the top 10 advances in computing?’ or ‘What are the top 10 programming languages?’ or similar David Letterman-like topics. They’re arbitrary and artificial, of course, but they start people thinking and discussing what makes something good or worth doing, which is important.”

Aho’s tenure at Bell Labs included stints in management as a department head, as well as director and vice president of the Computing Sciences Research Center from 1997 to 2002. Even as a manager, he found time to indulge his passion for queries. After the business part of the day was over, as people stayed late into the evening and even turned up on weekends, just for the computer access, Aho was wont to appear unexpectedly at an open office door.

“Al would come by very late in the day,” recalled Margaret Wright, now at the Courant Institute of Mathematical Sciences, “and he’d sit down, asking first if it was OK. And then he’d say, ‘I’ve been thinking about this… What do you think?’ And it would be a really interesting, kind of offbeat question. He had developed a novel/unusual perspective and he wanted to talk about it. And we’d end up having an hour conversation, where he’d say, ‘Here’s what I’ve been thinking. What do you think about that, and how important is this feature?’ and so on. I thought it was remarkable that this very high-ranking person who had plenty to do would take the time to have an impromptu technical discussion about an unexpected topic. And I’m not the only person this happened to. People in the computing science center would ask each other, ‘Have you had a visit from Al lately?’ and the answer was usually ‘Yes,’ causing everyone to chuckle. We all found these conversations charming, and I think they are one of the reasons people liked him a lot. Because he was right up to the minute; he was always interested in new things.”

Nearly 15 years at Columbia as the Lawrence Gussman professor in the computer science department has certainly kept him at the cutting edge. “I had this life plan that I formulated a long time ago, that I wanted to spend the last third of my career in academia, teaching and working with students,” Aho said. He pursued his new career with his usual energy, winning the “Great Teacher Award” from the Society of Columbia Graduates in 2003.

The Programming Languages and Translators course he established more than a decade ago is now legendary — this year 160 students vied for 100 spots. In designing the course, Aho drew inspiration again from Knuth, who once said, “The best theory is motivated by practice, and the best practice by theory.” The students assemble in teams of five, and each team writes an innovative programming language and a translator.

“Al has a remarkable thirst for teaching and learning,” said Krysta Svore, a doctoral student of Aho’s who is now a Microsoft researcher in the Quantum Architectures and Computation Group. One of his unique qualities, she recalled, is his curiosity, and a well-informed curiosity at that. “That is to say, he can meet a professor in a very different area of computer science, and still engage and ask some of the most key questions in the field. He is broad as well as deep in subjects. It is rare to encounter someone who can ask the best question in almost any lecture. He taught me to be a great scientist, to spend time asking the right question instead of just focusing on the answer.”

When asked what question he might pursue if he were just now embarking on his dissertation, Aho produced several in characteristic fashion.

“You may have heard of the Church-Turing Hypothesis — that anything that can be computed on a very simple model of a computer called a Turing machine. Do you believe that the Church-Turing hypothesis is true?… Do you think human beings are biological computers?

“So this gives rise to some very interesting questions. Could we write a computer program to simulate human qualities — like consciousness, free will? Now, the problem with these questions is that the medical profession doesn’t know how to define consciousness. They have no clue as to what free will really is.… Wouldn’t you like to know how consciousness works?”