Matthias Felleisen, Trustee Professor at Northeastern University, developed the reduction-based (aka evaluation context) variant of operational semantics, worked on the full abstraction problem for PCF, and co-created the Racket programming language with Matthew Flatt and PLT. We talk about his accidental path to computer science, the relationship between his K-12 outreach projects, his books, and his research, and how programming languages research can have the most impact.
JY: Tell us about yourself. How did you get here?
MF: I got into computer science by accident. I came to the United States on a Fulbright scholarship in 1980 and Fulbright placed undergraduates into universities that they thought were a good match. As a business major with some interest in computing, I was supposed to go to Tucson, Arizona, which had one of the top tier MIS programs. I went into these classes and after two lectures, I was bored out of my mind. I looked around and I found computer science courses were more interesting and more challenging for me. A really cool part about the challenge, socially, was that one of the seminars consisted of seven people, and there were five women and two men, and one of them was me. I came from a major where there were 350 men and one woman in there.
I liked computer science a lot and got a Master's, went back, finished my undergraduate degree in Germany, and came to the United States for a PhD. I discovered because POPL because it was in New Orleans, and that sounded like a great city to me, but I couldn't go. That was, I think, 1985. In 1986, I went to my first POPL. My advisor, Dan Friedman, took me along so I could discuss my first submission (to Logic in Computer Science, LiCS) with Mitch Wand. I went to all the talks but didn't understand a word. I was completely lost after about a year in grad courses. I told myself "I want to understand this stuff one day." Then, ten years later, I went to POPL and understood every word. Now, 30 years later, I go to POPL, and I don't even go to talks anymore. I just go because I want to meet certain colleagues.
JY: I wanted to talk about how Racket came about.
MF: Several different stories played a role.
One, I was helping a babysitter, she was 15 or 16. When we returned from an outing, she was struggling with some Algebra homework. I sat down with her and realized I could develop a systematic problem-solving method for programming but usable in math courses.
Two, in 1995, coming back from POPL, one of my grad students (Cormac Flanagan, UCSC) asked, "If functional programming is all that cool, why does nobody care?" We spent the entire time flying back from SFO to Houston discussing this question. By the time I got off the plane, I said, "I'm going to ditch my research and I'm going to launch an outreach project that goes to high schools and teaches them an integrated course on doing the algebra, geometry, math. I will build software for that. My graduate students will write their dissertations out of the meta research on how to build these languages, and these teaching models, and I will run the outreach."
We started the next day. I called everybody in my office, I explained my vision, and my student Shriram (Krishnamurthi, now at Brown) jumped up and down, saying, "This is amazing, this is so cool! I always wanted to be part of such a project.” Everybody was won over and we got started.
We needed two things. We needed a programming language for kids that would be close to the notation in algebra textbooks and a support system, and integrated development environment (IDE). Two of us went off to design this language, and Matthew Flatt, now at Utah was going to build an IDE. We started with Scheme because it lets you prototype complete languages easily and quickly. A few weeks later, Matthew came back and presented a new, GUI-based Scheme implementation. In the meantime, I had set up a summer workshop for teachers and off we went.
Five years later, Matthew he sent the rest of us a really cool message: "This is the first time I used DrRacket for real programming, not just for kiddie programming." Racket had really become a programming language in which we could really build actual systems.
JY: Could you give us some context on what your research was at the time that made you confident that you could find better research problems for all of your students in this space?
MF: I was not confident at all. I pretend. In 1988, I was distracted into plain theory by a very senior researcher who was very influential at the time, Albert Meyer. My dissertation research came about in 1985, when my advisor wrote down a one-line, completely, totally wrong equation on the blackboard, claiming something about continuations, and I said, "It's not true." But it was the germ that became my dissertation, the approach to semantics that many now call Evaluation Context Semantics. I prefer Reduction Semantics. And then Albert Meyer gave the keynote at LICS 88 said, "This Felleisen stuff is all syntax, not semantics."
I didn't even know what he meant at first until it dawned on me, "Oh my God, he means to have no model for my calculus." I exchanged email with him, and I said, "Why do you think we need a model? Why should it be fully abstract?" I actually hadn't wanted to do theory, I wanted to do this mixture of theory and building language tools at Rice, but because the most senior person had called me out, I decided to pursue the full abstraction problem.
JY: What are some examples of long-term goals you think we could reach for as a community?
MF: One of our long-term goals should be to develop an understanding of the pragmatics of programming languages, something we neglected since Jim Morris wrote his wonderful dissertation. The other one is a framework for comparing programming language designs, probably both in terms of pragmatics and expressive power.
Many of our papers come with a language design. We don’t need quantitative assessments, but some systematic qualitative assessment of why a design is good is important. Right now, we don't know how to do it. Without we can't convince a programmer of language design.
JY: Could you tell us about your books?
MF: The goal for How to Design Programs was to deliver a curriculum to beginners that turned (beginning) programming into a systematic activity. I didn’t want them to come up with programs by random clicking and dragging stuff. I didn’t want them to say “done” when the parser says it's good. I didn’t want them to rely on haphazard runs on some inputs and eye-balled outputs. What I want to have is a systematic process so a teacher can check intermediate products. I also want to gradually increase the complexity of data, from scalars to data representations that need mutually referential definitions, say file systems or abstract grammars. I had discovered the idea as grad student, which is when my advisor forced me to rewrite The Little Lisper.
I threw away the entire first draft of my book in 1996 because I discovered that I had fallen into the trap of presenting programming as a process of “copy examples, modify, experiment." I started over, telling myself, "All I am allowed to do is show how to build one piece at a time. If I have the first three pieces of the program, how do I create the next one? And how do I relate this next step to the preceding ones? How do I increase the complexity of data over time?"
I wrote the book on the web where my MIT Press editor (for The Little Lisper) discovered it. He flew to Houston and told me he wanted to publish it. I said I would publish it, but only if I could keep a copy of the book on the web, because we had schools, like in El Paso, where these kids couldn't even afford to buy a book. I believe HtDP is the first major textbook that has been published on the web for 20 years now, and it has been published as a real book. too. The second edition is about to appear, and it went through the same process. I am very happy with this approach to book writing.
JY: Any interesting POPL stories?
MF: In the spring of '94, Zena (Ariola) invited me to visit Oregon and I agreed to come out for almost three days. On the way out, I realized we had no current common research topic. Since I knew she was working on lazy languages, I decided to finally figure out how a calculus of the kind I had developed for my dissertation could characterize Haskell’s laziness. For the next three days we worked out the conventional theorems. Zena had a broader arsenal of proof techniques and she volunteered to fill in the gaps. A couple of months later we had written a draft POPL submission. I was on my way to Belgium and Germany to give talks there. Martin Odersky was in Karlsruhe and he showed me two things: Pizza (his generic Java dialect) and a calculus that, at first glance, was identical together with a half-written POPL submission that had the same title as ours. I almost fell off my chair. It was too late to coordinate.
Peter Lee was POPL program chairman back then. The committee was stunned to get such similar papers. They didn’t recognize that their calculus differed from ours in one key axiom. Peter proposed to ask the authors to merge their papers.
We struggled for weeks to merge our papers. Eventually I proposed a deal: one shared page for the intro, a complete equal split of space thereafter, alphabetical authorship (this would place Zena first), and the youngest (John Maraist, the Odersky student) would give the talk and Phil (Wadler, the other senior author) would pay me a Scotch. Zena and I condensed our results to the 5.5 pages.
So POPL comes around. Maraist gives the talk. As expected when you merge two papers, there were some disagreements before the two papers. So I get up right after Marist finishes and ask the session chair for time to rebut the speaker’s claims. The audience laughed but it made sure that everyone remembered the talk and the paper and it got tons of attention.
JY: How do you think the POPL community should be relating to real software engineers doing real programming?
MF: I think it would be good if some of our POPL attendees were to go out, before they get a PhD, and work for two or three years on actual systems, in the real world, where real people build real stuff. They should live on the web stack, build a telescope controller, build a medical device, or develop games. When they then come back, they bring this experience back into the PhD program. That does not mean we should conduct research on the latest industrial fashion programming language or IDE tools (analysis algorithms). Rather we should use the experience to inform our own research development efforts. We must build languages and software development support for real developers not for ourselves.
Which brings me to another important idea. I think too few of my colleagues in academia including programming languages, do not build software that is used by many people and for which they are responsible over a long time. There is no harsher tester than a middle school kid who uses your language. Or developers at some start-up who chose your language because they believe it will help them be productive developers. Too few of us have papers with artifact stamps that rely on systems with a long history. Getting a stamp for an interpreter that’s written in an afternoon is an embarrassment. So let’s build real systems, get others to use them, respond to bug reports, and use the experience to improve the productivity of software developers. I think this is where programming-language research can, and probably should have, its largest impact.