Lambda the Ultimate

Shriram Krishnamurthi's excellent book, Programming Languages: Application and Interpretation (PLAI), long available in PDF form, is now available in paperback.

There's also a paid download available, "in case you want to reward the author in kind". A free PDF of the latest version is still available, which "really is the entire book, with no strings attached." The book is now licensed under a Creative Commons license which allows it to be adapted ("remixed") to fit a course.

Here's an overview of the book's approach:

This book unites two approaches to teaching programming languages, one based on a survey of languages and the other on writing definitional interpreters.

Each approach has significant advantages but also huge drawbacks. The interpreter method writes programs to learn concepts, and has at its heart the fundamental belief that by teaching the computer to execute a concept we more thoroughly learn it ourselves. While this reasoning is internally consistent, it fails to recognize that understanding definitions does not imply we understand the consequences of those definitions. For instance, the difference between strict and lazy evaluation, or between static and dynamic scope, is only a few lines of interpreter code, but the consequences of these choices is enormous. The survey of languages school is better suited to understand these consequences.

The book is used as the textbook for the programming languages course at Brown University, taken primarily by 3rd and 4th year undergraduates and beginning graduate (both MS and PhD) students. It seems very accessible to smart 2nd year students too. The book has been used as a textbook at over a dozen other universities as a primary or secondary text.

Erik Ernst, The expression problem, Scandinavian style. MASPEGHI 2004.

This paper explains how higher-order hierarchies can be used to handle the expression problem. The expression problem is concerned with extending both the set of data structures and the set of operations of a given abstract data type. A typical object-oriented design supports extending the set of data structures, and a typical functional design supports extending the set of operations, but it is hard to support both in a smooth manner. Higher-
order hierarchies is a feature of the highly unified, mixin-based, extension-oriented kind of inheritance which is available in the language gbeta, which is itself a language that was created by generalizing the language Beta.

MASPEGHI, in case you wonder, stands for MechAnisms for SPEcialization, Generalization and inHerItance. On the site you'll also find the presentation related to the paper. And oh, gbeta is here.

I wonder what the Scala guys have to say about all this...

The Expression Problem Revisited - Four new solutions using generics. Mads Torgersen. ECOOP'04.

...Over the years, many approaches to this problem have been proposed, each having different characteristics of type safety and reusability. While many of these rely on exotic or problem specific language extensions, this paper investigates the solution space within the framework of the soon-
to-be mainstream generic extensions of C# and the Java programming language.

Four new solutions are presented which, though quite different, all rely on techniques that can be used in everyday programming.

Same issue, same department (Daimi, Aarhus), different approaches.

Compared to the previous post, this paper is longer and thus perhaps easier to follow; the approach is more mainstream - and the code (in Java!) is downloadable.