Simon Peyton-Jones (Microsoft Research Cambridge) researches the implementations and applications of functional programming languages. He was heavily involved in the design of the Haskell programming language and the development of the Glasgow Haskell Compiler (GHC). We talk about seeing functional programming go from intellectual revolution to practical reality and the importance of investing in programming education.
JY: Tell us about yourself. How did you get here?
SPJ: I first came across computers when I was about fourteen. Our school had one computer, it was a so-called IBM School's Computer, it had 100 memory locations each of which could contain a 10-digit decimal number. A lot of programming was about trying to fit the program into that space. There was one computer for the whole school and there were only two people in the school who cared about this machine. So, my friend Thomas Clarke (he's now at Imperial College) and I spent a lot of time hacking on this. Then we started to build our own computers.
It was also about the time the Intel 4004 came out, the first microprocessor, so that was very exciting. We traveled on a bus to Swindon to a neighbouring technical college that had an Elliot 803, which was the size of several large washing machines. But we had it all to ourselves. It was in the days of punch-tape when, if you wanted to edit your program, you would put your current program on a paper-tape in teletype, run it through (punching a new tape), stop at the bit you wanted to change, type new stuff, carry on copying...
I already knew I would probably dabble in computing for the rest of my life some way or another. Then I went to Cambridge. At that time Cambridge University hadn't yet decided that computing science was a valid subject: you couldn't do a three-year Computer Science degree. So I did mathematics to begin with, and then I discovered mathematics was too difficult. Cambridge mathematicians are kind of a breed apart. Incredibly intelligent people. So, eventually I changed to Electrical Sciences after two years, which was like an electrical engineering degree, and then did a one year postgraduate Diploma in Computer Science. That's my sole formal education in Computer Science. That was in 1979 to 80.
I didn't consider staying for a PhD. I just went and got a job at a small electronics company. But two years later I discovered that actually having to deliver things that customers want is quite hard, and the company was always bankrupt, and I was always stressed. By accident I ended up getting a job as a lecturer at the University of College London in Computer Science. I had one paper to my name and I did not have a PhD, but I got a permanent tenured job as a faculty member at UCL in 1982 or thereabouts.
JY: Was it common to teach without a PhD?
SPJ: There was still the idea that people would work to get their PhD before they got a faculty position, but this was a time in which the Computer Science department was expanding very rapidly and there wasn't enough supply. I think I was incredibly lucky to be looking for a job at that exact time.
JY: What was the one paper?
SPJ: Oh, maybe I had two. One was about the project I did for my Diploma, a comparison of the relative efficiencies of SK combinators and lambda expressions. I built an SK interpreter and a lambda interpreter and ran various programs and saw which went faster. I think it appeared in 1982 This was my first real conference, and John Hughes was giving his first paper then as well so it was an awesome experience. John McCarthy was giving a talk, and Jon L White, and all of these seriously famous people—and then I was giving this talk about a paper that I now regard as completely misplaced. (Misplaced because you can’t draw many conclusions about efficiency from comparing naive interpreters.)
And the other paper that I had was about a little operating system that my boss and I wrote while I worked in my first job. There was only 5 people at this company so it was really small, but we wrote the paper and managed to get it published.
JY: How did you find your way back into functional programming research?
SPJ: Now I had a job as a lecturer and my boss, my Head of Department said to me, "Well Simon, I'll give you a light teaching load so you can get your research started." But of course I had not been a PhD student so I had no idea how to do research. I would sit there in my office with a blank sheet of paper and a sharp pencil and wait for great ideas to come. Of course, nothing did. Then an undergraduate would knock at the door and say, "Simon, do you have a moment?" I'd welcome them in as a distraction from this difficult business of doing research.
Eventually one of my colleagues, a really good guy, called John Washbrook, said to me, "Simon, you should just get on and do something no matter how humble and simple." In the end the first thing that I did was I wrote a parser generator for a functional language SASL, so it was a bit like Yacc. I called it “Yacc in SASL.” That got published in 1985 in Software Practice and Experience.
At the time, I was very inspired by David Turner's papers about SK combinators. I was in London, he was in Canterbury, so I asked him to be an informal mentor. Since I didn't have an adviser he was my sort of remote advisor. I would go to see him every few months and we would have a chat over coffee. That was incredibly helpful to me because I did feel a bit uncertain about what to do.
JY: How did you decide that functional programming was what you wanted to do research on?
SPJ: That was at Cambridge while I was getting my Diploma. There was a very eccentric professor there called Arthur Norman and he was big on computer algebra at the time. He gave a short series of lectures about functional programming, which I had never heard of, in which he showed some functional programs. He even built things like circular lists, which didn't seem even possible given you don't have any side effects. The second thing was David Turner's papers about SK combinators and the amazing idea that you could take lambda expressions and translate them into this big mess of S's and K's and it would evaluate to the same thing.
And all of that occurred at the same time that John Backus was winning the Turing Award and giving his talk called “Can Programming Be Liberated From the von Neumann Style?" In his talk he introduced FP, his functional programming language, and cast it in a big picture. He said, "This is the way to write programs, and moreover not only will it revolutionize programming but we should even build new computers to execute these programs." This was a call to action. We already thought functional programming was cool, but here was this extremely famous guy saying "It's not only cool it's the Right Thing to do." There were a bunch of people at Cambridge, John Hughes, Thomas Clarke, Jon Fairbairn, myself, and a few others who all got excited about functional programming at the same time. It was one of those coincidental things. We all just caught fire.
JY: What were the big open problems in functional programming when you were getting into it?
SPJ: Functional programming is a radical and elegant attack on the whole enterprise of writing programs. It's very different from the "do this and then do that” programming mentality. You have to rewire your brain in quite a different way. For a long time it was well understood theoretically—there was lots of stuff about semantics and it had these very deep foundations in logic. But in terms of a practical programming medium it seemed like a completely virgin field. Then with David Turner’s work, and with the whole ML effort at Edinburgh, people suddenly started to say, "Actually, these languages could be not just elegant, and beautiful, and mathematically cool—but also useful. You might actually be able to write interesting programs using them." That was the movement that I got involved in.
JY: I wanted to talk about how Haskell came about.
SPJ: In the late 80's there were a number of separate researchers who were doing stuff with lazy functional programming. I was one, John Hughes was another, Paul Hudak was another, Thomas Johnsson and Lennart Augustsson at Gothenburg, Arvind and his dataflow colleagues at MIT, Joe Fasel Los Alamos was another, Rinus Plasmeijer at Nijmegen, and so on. There were maybe a dozen all together.
We would meet each other at conferences and we came to realize that we were all building little programming languages and they all basically looked the same. We thought, "Oh, we should do something very modest, very humble. We should just agree a common syntax so that we can run each other's programs." We had SASL and Miranda, David Turner's languages for guidance, so we thought we'll just cohere around some syntactic least common denominator. We wanted a basis for teaching and research just to avoid unnecessary diversity. We weren't thinking of Haskell as a way to solve research problems at all, more as a substrate for research.
We met and decided, "We should form a committee and design a language." So we did, and we then physically met in person. This wasn't before email, but it was certainly before the web and collaborative working and so-forth. We physically met on several occasions to design the language. The surprising thing is that it turned into a research project.
JY: How did that come about?
Several things that happened that were quite serendipitous and unexpected. We knew it was going to be lazy, we knew it was going to have parametric polymorphism like ML does, and we knew it would have algebraic data types and pattern matching. That was all part of the consensus of what we were starting from. Type classes, on the other hand, were entirely new.
The IFIP Working Group 2.8 (for Functional Programming) in 1992.
We had spent some time debating what we were going to do about functions like read, show, serialization, and equality. They're not parametrically polymorphic, but they are a bit polymorphic, because they should work on a lot of types. And then, out of the blue, Phil Wadler and his student Steve Blott produced, fully formed, the idea of type classes. I still have the email which he sent: it was almost like a little paper to the then committee. We were bowled over: "Oh, this is how we could deal with all of those awkward problems." At that stage, we had a choice make. We could keep thinking of Haskell embodying a current consensus, as we had been. But we didn’t do that. Instead we said, "Type classes may be new, but they solve a really nasty, awkward problem that's a wart on the face of our beautiful language. Let’s embrace them." So we incorporated type classes wholeheartedly, and they turned out to be one of Haskell's big contributions to the world.
For reasons like this—monadic I/O is another example—Haskell ended up being significantly more innovative and ambitious that we had originally intended. But that was largely accidental.
JY: How did Haskell become a platform for answering research questions?
SPJ: I got involved in building a compiler for Haskell, the Glasgow Haskell Compiler, GHC. A lot of the research that I subsequently did revolved around the question "What does a good compiler for this look like?"
So, did Haskell itself answer any questions? I'm not sure I'd put it like that. I'd more say that the spur of having an actual concrete programming language with an actual concrete implementation that aspires to be something that people could use for practical purposes, that spur drove innovation both in the language design, because we would say, "Oh, but look you can't do this and we ought to be able to." And also in the language implementation because we'd think, "This is way too slow." It wasn't the language that answered any questions, it was more its existence of it and its implementation drove a lot of research innovation.
JY: What was the biggest surprise about putting Haskell out there?
SPJ: I had always assumed that the more bleeding edge changes to the type system, things like type-level functions, generalized algebraic data types (GADTs), higher rank polymorphism, and existential data types, would be picked up and used enthusiastically by PhD students in search of a topic, but not really used much in industry. But in fact it turns out that people in companies are using some of these still-not-terribly-stable extensions. I think it's because people in companies are writing software that they want to still be able to maintain and modify in five years time. As you scale up, and as your ambition about timescale increases, so maybe you'll invest more in the static guarantees you get from a type system, and then you push the type system harder. You see people out in industry writing blog posts about catamorphisms and categorical connections, and plenty of stuff that I don't understand. Somehow, the level of abstraction offered by a sophisticated type system lets you get much more ambitious in terms of the intellectual complexity of what you can deal with.
JY: As you were doing all of this work, what was the relationship of the functional programming work to what other people were interested in at POPL at the time?
SPJ: Initially I always thought of POPL as being a conference that was for people cleverer than me, so it was quite a while before I even submitted a paper to POPL. But when I did I found a community that was completely aligned with the kind of things that I cared about. It's right there in the title isn't it? Principles of Programming Languages, so it cares about being principled and it cares about elegance and economy of effort. Try to get the job done with as little machinery as possible. Indeed, I feel that most of my research life is about saying, "It has to be simpler."
I always felt I was more of a theory user, not a theory developer, whereas I'm a compiler developer, not just a compiler user. So I always felt slightly out of my class at POPL. I still do.
JY: What is an important problem our community can work on solving in the next five or ten years?
SPJ: Education. If we're to get the principles, and elegance, and modularity, and economy of effort, and abstractions that POPL contributors value so highly, if we are to get them actually part of the fabric of the software that holds our digital lives together, the way to do that is by instilling those values into our undergraduates, and so then they will become the developers of the future, and CTO's of startups. So, there's a big inertia to overcome, but over time it'll happen. As I often say, when the limestone of imperative programming has worn away, the granite of functional programming will be revealed underneath.
JY: Could you talk about your K12 education efforts too?
SPJ: I've been working on this for about 10 years. There didn’t seem to be any connection with the subject that my kids were learning at school and the subject that I think is so fascinating that I've devoted my professional life to it. So we started a guerrilla movement Computing at School to try and reform our computing curriculum. Rather to our astonishment, we were very successful. The English National Curriculum now explicitly says that all children should learn computer science from primary school onwards as a foundational discipline in the way that they do maths or physics. And for the same reasons: that is, not because they're going to become mathematicians and physicists, but because an elementary understanding of these foundational concepts enables you to be an empowered citizen in a complicated world.
Simon and teachers at Westminster City School.
Now the challenge is actually turning that aspiration into a vibrant reality in every classroom. Even if you had well trained teachers and plenty of time would be difficult enough, but with teachers who are willing but nevertheless underqualified for this particular task it's a real challenge. We're messing it up in numerous ways, partly because we don't really know what we're doing. We've got reasonable amount of experience of teaching CS in university (but not nearly as much as we have in say maths; remember, you could barely do it at Cambridge when I was an undergraduate), but much less experience at school level. We need to study pedagogy and then support and equip those teachers. And that's a big, big challenge, one to which I am devoting a fair amount of effort. I hope that the POPL community would, as individuals and maybe collectively, lend their cycles to that aspiration because I think the POPL community has a handle on the the abstractions that we'd like our children to learn.