Meet Jean Gallier.

Like many professors, Jean Gallier was never initially drawn to computer science. Coming into a technical college, he was registered as a civil engineering student. What sparked his interest was his frustration with the compilers he was using. In computer science, compilers are in charge of processing human-readable code into machine-readable code. Now, it takes no more than the push of a button. Back when Gallier was in college, it involved assembling a deck of ordered cards and feeding them into a physical compiler, which would take several minutes. The mystery of compilers fascinated Gallier and helped define his interest in computer science for the rest of his life.


At the end of Gallier’s second year in the French university system, he found out about a program for technically-inclined students to complete a Master’s degree in the US. He figured he fit the description, so he followed his passion to UCLA. “Plus, I wasn’t in a big hurry to do my military service. This was a good way to postpone that.”


At UCLA, he quickly got involved with automata theory and decidability, as well as programming in a language called PL1. After taking the programming course, Gallier became a TA for it, teaching it for the next two quarters. He also met the woman who he would later marry, just as his degree was nearing completion. The normal course of action was to return to France after getting his degree, but she wasn’t as eager to go. His professor at the time also offered up another path.

“You seem interested,” he said. “Why don’t you apply for the PhD? You already have a masters, you just keep going. We have money for you for at least the first year.”

His advisor was Leonard Kleinrock. Kleinrock was an expert in the specialized field of queueing theory, as well as one of the founders of the internet. After Gallier took his initial courses in queueing theory, he found the probability theory aspect of the material “unexciting.” Luckily, he quickly stumbled upon a new path.

“Completely by coincidence, I see some notes on a friends desk and I look at it and it was something very mysterious. With lots of Greek letters, languages, automata, all kinds of that stuff. I said ‘What is this? Who teaches this?’ and the guy says, ‘Sheila Greibach.’ So I took one of her courses. Woah that was hard. But it was beautiful. I decided I had to drop queueing theory and do something with Sheila.”

Sheila Greibach was interested in the fields of formal verification and program correctness. As a first assignment, she handed Gallier a dissertation by Leslie Valiant, a prominent computer scientist at the time.

“His dissertation was a masterpiece. Coming as a fresh student, I couldn’t do anything better than what he had done. She wanted for me to improve certain aspects and I banged my head for a year and I still remember coming to her and telling her I wasn’t able to do this. She looked at it and she said ‘That’s it?’”

His interest in formal verification led him from completing his PhD at UCLA to conducting research at Penn in the same field.

“The idea [behind formal verification] is that when people write programs, you should be able to tell if they do what they’re supposed to do. These are usually some kind of inductive techniques, but it’s extremely painful to do that manually. The hope was that you could automate the process. You’d have to come up with what’s called automated theorem provers. The complexity is very high, so it’s very hard to do practically, so people moved more to program checking rather than actual verification. The two are sort of related.”

And so began the evolution of Gallier’s interests. For a few years before he took his sabbatical, he dove deep into improving compilers, which was also tangentially related to program checking.


Gallier used his sabbatical as an opportunity to go back to France and work as a researcher at the Digital Equipment Corporation lab in Paris. During the time he was there, he worked alongside many famous computer scientists, including Turing Award winner, Leslie Lamport. “I was hoping to work there afterwards,” he confessed, but the company folded before he could return.


When he came back to Penn, he made good friends with Noam Badler, who taught a computer graphics course at the time. He convinced Gallier to teach a course on the mathematical machinery behind geometric design and splines, a “scary” new territory for him. It was through the courses Gallier was teaching that he met Ken Shoemake.

“He was kind of slightly odd, very bright person and he took the graduate version of 262. He was kind of eccentric, he always had solutions that were kind of right but not quite right. He came, he fought me, I showed him it was wrong. He claimed it was right. He came to me laughing saying ‘You’re gonna do that? You’re crazy! I know that, that’s my thing’ He said ‘I can be your TA and tell you what to do.’”

So Gallier took Shoemake on as a TA, and the eccentric student became a real resource in the graphics courses that Gallier taught. Later, Shoemake made a name for himself in computer graphics. He introduced quaternions as a computational tool to deal with rotations on screens, and his work is used regularly in movies and games alike.


On the winding path of his careerfrom automata to compilers, from formal verification to graphics, Gallier found it beneficial to write books.

“They’re comprehensive documents that cover the area thoroughly. It’s partly selfish, but if I don’t write, then I don’t really know. If I write something, then I’m forced to articulate my thoughts carefully and clearly. It’s Sheila Greibach who told me this.”

After working with Ken Shoemake in the graphics department, Gallier compiled a manuscript detailing his work in the field. Finding a publisher for the book was proving to be difficult, though. He faced rejection from several major publishers until a man named Brian Barsky took a look at the draft. Barsky was involved in computer graphics applications and medical imaging. He also sat on the board of Morgan Kaufmann Publishers, which specialized in engineering and computer science books.


Since then, Gallier has published five books, with a couple more manuscripts in the works. He has bounced around quite a bit across Penn’s CIS department during his 40 years here. To him, this is part of his philosophy.

“I personally believe that it’s not good to restrict yourself to a certain area because the best work is done when you discover something over there is useful over here.”

And that’s exactly what he does. With all his experience and connections at Penn and beyond, he is regarded as a ‘mechanic’ who knows the mathematical tools of computer science from many different practices and can apply them ubiquitously.