Programming Languages: Application and Interpretation
Copyright © 2003, Shriram Krishnamurthi
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License
Version 2007-04-26

What level is this book for? At what levels has it been used?

At Brown, I use this book for a course targeted at third- and fourth-year college students and first year graduate (master's and PhD) students. The class features a healthy smattering of both advanced PhD students and second-year college students. The book has also been used at over thirty other institutions, in everything from all-graduate-student classes to high school courses. I'd be happy to discuss the accessibility of different parts of the book.

What are the book's prerequisites?

The book assumes relatively little of the student. It helps to have mathematical maturity of the sort that a traditional discrete mathematics course tries to bestow. The book sometimes mentions the Halting Problem. Motivated students have not been significantly affected by not having had this material before. I continue to remove unnecessary dependencies whenever I encounter them.

The book does assume that a student can write rudimentary programs in Scheme. Unlike some other texts it does not begin with a Scheme tutorial because each instructor will tend to have their own preferred way of teaching Scheme. On the Web, you can find a handy list of introductory Scheme programming texts. If you need help choosing amongst these, do contact me.

My own course does not expect knowledge of Scheme. I teach it in three introductory Scheme lectures: one on the rudiments, starting with simple expressions up to first-order functions, including recursion; the second on conditionals and data structures; and the third on higher-order functions. This is accompanied by homework problems along with their solutions, so students can grade themselves. My course staff holds several extra office hours during this period so that students can get one-on-one help with the language.

How much of the book do you cover?

In one semester (about fourteen weeks) I cover the entire text, along with several extended assignments. But that might be a fairly brutal pace for some. So...

How easy is it to use just parts of the book?

Very! Some people cover quite a bit less, picking and choosing chapters, and still have a satisfying experience. I have thus removed as many dependencies between chapters as possible, and continue to remove them where reasonable. Thus, for instance, you may find one or two chapters the perfect way to wrap up an introductory programming course in which students have already learned some Scheme.

Even in programming languages courses, some users have excerpted select chapters and used them either exclusively or in conjunction with other texts or approaches. To facilitate such modular reuse, I have adopted a license that permits you to “remix” portions of the material to suit your needs. If you would like a specialized textbook consisting of just some subset of chapters, contact me and I would be happy to oblige.

Are there more assignments than are in the book?

As of this writing (2007-04-26), yes. There are several additional problems in the homework assignments and exams from prior versions of my course. (You will not find exams since 2003 because I stopped administering exams in the course.) Eventually these will all be incorporated into the appropriate places in the text itself.

What's in the future for this book?

I edit the book every time I teach from it, and sometimes even when I'm not teaching this material. I therefore expect to produce a new version roughly every year, at least until the flow of innovation begins to staunch. Specifically, I want to flesh out the details of the material on programming-by-search; integrate an outstanding approach to teaching garbage collection, which is currently only described as the background to an extended assignment; explain software contracts; and discuss programming interactive systems.

Dude, where's the object-orientation?

Oops, I forgot!

Just kidding. There are three reasons I left out object-oriented programming from this book. Before I tell you my reasons, let me just say that if it really, really matters to you, and you do not agree with the reasons below, and—this is crucial—you can answer well the third item (which is a question), then I'll consider writing a chapter on object-orientation for you.

Okay, now for my reasons. These are predicated on the belief that these days, most students are already exposed to a hearty dose of OOP (via Java) in their first two years of college.

  1. First, the positive answer. I want to expose students to an exciting world populated by strange and wondrous languages. I hope that something they see will spark their imagination, making them question the way they've programmed in the past and enticing them to try new ways in the future. Discussing OOP in this book would not be exposing them to one such new thing; it would just be explaining an “old” thing.
  2. Second, having seen so much OOP (usually Java), they have already formed fairly strong mental models both of what OOP is and of how it works. On the one hand it feels redundant to go over this all over again; on the other hand, they probably have sufficiently strong views on OOP that no matter what this course does, it won't have much effect.
  3. Third, it's a simple matter of fitting a large number of topics within a limited amount of time. What would you leave out? And by leaving it out, are you not violating one or both of the above tenets?
I do actually have some ideas on how to introduce OOP into the mix. These ideas are definitely non-standard, so the odds are you still wouldn't be satisified. Woe is me!

Speaking of OOP, I just noticed: you don't seem to cover traditional paradigms anywhere in your book. Why not?

Plainly, I think the notion of language “paradigms” is nonsensical. Programming languages are not plants. You can read a brief essay about it.

How do you compare this book to Friedman, Wand and Haynes's Essentials of Programming Languages (EoPL)?

I loved EoPL as a student. My book nevertheless grew out of a great frustration from viewing EoPL as a teacher.

Concretely, I think EoPL does a poor job on several crucial topics, most notably:

The material on types is so caught up in mechanics (especially of type inference) that I think it fails to provide very much insight into types. It fails to pass from information to wisdom.

Garbage collection isn't discussed at all in any meaningful way. I find that students are generally woefully uninformed about garbage collection, having lots of wrong ideas in their heads. The programming languages course at most universities is the only chance to rectify some of these misconceptions (especially since many faculty colleagues actively cause the misconceptions). This is one place where I have found having them implement collectors, which PLAI does using a radical innovation, is actually really helpful; it takes a lot of the mystery out of GC. I think we also have a responsibility to discuss some of the systems aspects of GC, especially provide a meaningful comparison to manual memory management.

All this plainly points to a goal that I think diverges considerably from that of EoPL: I want to reach out and communicate with the hacker, not just the theoretician. That is, I believe about 90% of my students have no interest in going on to study programming languages, while about 10% would love to pursue the subject. I feel that the 10% would be satisfied no matter what I taught, so long as the material is good and taught with feeling: it's the follow-up courses they're really after. But that 90% will rapidly tune out if the course does not speak to them.

Trying to communicate with this 90% made me re-examine the course's philosophy. Is the EoPL interpreter-based culture the right one? I think it works wonderfully for the 10% (like it did for me)—but I want a course for people not like me! By entirely abandoning the survey-of-languages approach, the interpreter style fails to deliver for students who want to see the concrete, and consequences, before the abstract, and principles.

PLAI therefore weds the two approaches, always looking at examples (such as programs in actual languages) before writing interpreters or their equivalent. This has the following benefits:

In short, many more humans learn by induction than by deduction, so a pedagogy that supports it is much more likely to succeed than one that suppresses it.

My goal is to not only teach students new material, but to also change the way they solve problems. I want to show students where languages come from, why we should regard languages as the ultimate form of abstraction, how to recognize such an evolving abstraction, and how to turn what they recognize into a language. I want to do all this concretely, accessibly, through examples. That's where this book is going.

The text is also more colloquiual than many other academic texts. I don't intend to beat students with a cudgel, whether that of formality or that of stifling precision; that is best done in a semantics course where they have already committed to studying this material in depth. Speaking of precision, I also believe that we learn best from mistakes, so I develop most ideas gradually and incrementally, presenting each “obvious” version and showing why it fails, using that failure to iterate. At this level my goal is to engage and excite students—to help them understand why I love this material so much. I cannot do that while wearing a bowtie.

If you're a purist, you will probably read the criticisms above and view them as positive endorsements for EoPL. If this is you, congratulations: you've learned that PLAI is probably not the right book for you. But in the process, do also make sure your students aren't similar to the person who wrote this in a review of EoPL on

This situation makes it essential to supplement the book with programming assignments in actual languages (Java, ML, Prolog), so students can see what all the trouble is for, and what's really exciting about the ideas in the book. Otherwise, reading this book is like learning how to build a car without ever having seen one!
That could almost be a plug for PLAI.

How do you compare this book to those by Sebesta / Tucker / Mitchell / Scott / Pierce / ...?

Phew, that's a lot! Tell me which particular one you're interested in; I'll re-examine it, then compose a response.

Why can't you get a normal publisher like all the other authors do? Was nobody willing to publish your book?

Some very respectable presses were indeed interested. I consider this self-publication an experiment. But you should also ask yourself why the imprimatur of a publisher, who provides virtually no useful technical evaluation (as evidence, see all the junky textbooks on the market), is more important than the qualifications of the author (in my case, my publications are part of my credentials). My essay on books as software discusses my perspective in more detail.

What's with these “versions”? Why don't you call them “editions” like everyone else does?

You can ignore the distinction as pedantry. But if you do care, look at my essay on books as software.

What's that on the cover?

It seems fashionable to use an image of a rock inscribed in ancient languages on the cover of a programming languages textbook. So this one is a photograph of the base of the Gomateshwara statue at Shravanabelagola.