Digital Digressions by Stuart Sierra

From programming to everything else

Objects Are Not Abstract Data Types

Posted on by Stuart

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.

18 Replies to “Objects Are Not Abstract Data Types”

  1. The new Go language has an even simpler solution. Types that are just storage, methods attached to type names (alias the type and you can create completely different methods), and interfaces that don’t need to be explicitly implemented or injected – they just apply retroactively and automatically to any type that supports the listed methods.

  2. We already tried that, it was called COM. If you really want to play that game try out VB 4 thru 6. During that era VB would allow any object to implement any other object’s interface. We gladly gave that up for a Java-like class system because, in no uncertain terms, it sucked.

    Take a step back and think about this would mean for version 2 of your application. What would happen if you wanted to add another function to a protocol? You either break all the classes implementing that protocol or you go the COM routes and start including version numbers in your protocol names.

  3. It seems that Deftypes and protocols will change how one programs in clojure. If that is correct, are there any articles or tutorials for someone who is still going through the Book or just finished it on how to make use of them (unlearn stuff in the book to use them)?

    Also, is it correct that deftypes and protocols will help someone who cannot think except in object to make the transition to analyse problems and design programs (in clojure) in a functional way?

    Thanks

  4. You might want to check out Haskell if you haven’t already, as almost everything you’ve just talked about has been core to the way Haskell has been defined.

    Cheers,
    OA

  7. Jonathan Allen writes: “What would happen if you wanted to add another function to a protocol?”

    It remains to be seen in practice. But my answer is: you don’t. You create a new protocol with the new method, and add implementations of that method for the datatypes/classes that need it. Protocols are much more flexible than classes in this way.

  8. Ali writes: “are there any articles or tutorials for someone who is still going through the Book or just finished it on how to make use of them (unlearn stuff in the book to use them)?”

    Not yet. The implementation of datatypes and protocols is still being developed. I’m sure that once it is finished there will be a raft of articles describing how to use it.

    Probably the only thing you will have to unlearn is defstruct, which will be replaced with deftype.

    Protocols should provide a good migration path from object-oriented to functional design.

  9. So this proposal is basically a restricted Java class and a Java interface?

    Which is not a surprising choice – James Gosling has said that he would have liked to make Java’s original type system interface based, but they ran out of time to do the necessary research.

  10. “Not yet. The implementation of datatypes and protocols is still being developed. I’m sure that once it is finished there will be a raft of articles describing how to use it.”

    any idea what the ETA is on this?

  11. polypus wrote: “any idea what the ETA is on this?”

    Don’t hold your breath. I’m guessing it will be 2-3 months from now.

  12. Noel Grandin wrote: “So this proposal is basically a restricted Java class and a Java interface?”

    Not really restricted, because you can do all the same things you can do with Java classes/interfaces. Just a different approach, and more flexible because you can modify datatypes/protocols dynamically.

  15. I wrote the article “On Understanding Data Abstraction, Revisited” mentioned above. I also responded to Liskov when she presented her talk at OOPSLA a few days before my presentation. In my article I completely refute Liskov’s negative comments about object-oriented programing. I identify a notion of pure OO in which only *interfaces* are used as types. In this approach, there is no conflation of “concrete representation of a type with the interface used to access it”. The problem comes from using classes as types. The overall point of my article is:
    * CLU introduced the idea of user-defined abstract data types (ADT)
    * Objects are NOT abstract data types (they are fundamentally different)
    * Java supports a blend of ADT and object-oriented programming
    (but the ADT support is weak)
    * Abstract data types and objects both have advantages and disadvantages
    Adding ADT forms to Java will improve some things, but make other things worse. Be careful!
    * Haskell type classes are a form of abstract data type (but without much information hiding)
    Once you get the pure form of both concepts clear, then the various hybrids are easy to recognize. Unfortunately, most people only know Java, which is a mixed up hash of both forms, so using Java as your foundation leads to confusion. I’m sorry my article is not quite as accessible as I had hoped it would be. Since there seems to be so much interest in the topic, I’m thinking about writing something that is easier to digest.

Comments are closed.