I was lucky enough to see a talk by Barbara Liskov, the grande dame of computer science. The talk was titled “The Power of Abstraction,” and it covered Liskov’s work on programming languages in the 1970s and 1980s, primarily a language called CLU.

Update 1/14/2010: Video of the same talk is available here: OOPSLA Keynote: The Power Of Abstraction

CLU had a number of interesting features that were ahead of its time — heap-based garbage collection, typed exceptions, and iterators. Many of these features made their way into object-oriented languages such as Java. But CLU itself is not object-oriented.

Object-oriented languages, Liskov said, tend to conflate the concrete representation of a type with the interface used to access it. Think of a classic Java class in an introductory OOP text. The class contains both instance fields and methods to manipulate them. Even though the fields are private, the interface is tied to a specific implementation. You can’t substitute a different implementation, not even by subclassing.

CLU provides separate structures for fields and methods. Fields are defined in types, which are more or less like C structs. Methods are defined in clusters, from which the name CLU derives. A cluster is a named set of method implementations, associated with one particular type. Users only work with clusters, not types. A cluster may be substituted by a another cluster that implements the same methods.

Why is this interesting now? Because we’re just catching up to where Liskov was in the seventies. Modern Java designs often favor interface-based APIs with no concrete inheritance and no public constructors.

This is even more interesting to me, because my favorite programming language will soon have features very similar to CLU’s types and clusters. The “new” branch of Clojure defines two new abstractions: datatypes and protocols.

A protocol is a set of function signatures, with no implementation. Conceptually, it’s similar to a Java interface. You could use a protocol to define an API to model some real-world object, such as Employee, Department, etc.

A datatype is a set of named fields, with optional type declarations. Conceptually, it’s similar to a C struct. However, a datatype can also declare support for any number of protocols, and supply methods to implement those protocols. For example, Clojure will probably have a Countable protocol with a single method count. Clojure datatypes like Lists and Vectors can provide their own implementations of count. At that level, the datatype is like a concrete class implementing several interfaces.

What’s really cool is that you can extend protocols for existing types, even Java classes. So, for example, we could implement Countable for java.lang.String by writing a count method that calls String.length(). This means you can create new protocols for Java classes that you do not control. This is like interface injection, a proposed but as-yet unimplemented feature for Java.

Protocol method calls are dispatched dynamically based on the type of their first argument, very similar to (and at the same speed as) Java method calls.