On Not Understanding Data Abstraction, Revisited

We have a technical reading group (aka ‘Nerd Club’) at work. Last week we tackled the paper On Understanding Data Abstraction, Revisited by William Cook. We learned about it through a talk by Kevlin Henney that takes its title from a clause in the paper: It Is Possible to Do Object-Oriented Programming in Java. I really enjoyed reading the paper, but fear I’ve failed to understand important parts of it. Failing to understand isn’t so unusual for me, particularly for papers that have more than a tiny bit of theory, but this one has me frustrated because I’m sure I’m close.

The paper shows that there are two common forms of data abstraction, abstract data types (ADTs) and objects, and that they are different and complementary. The final sentence reads:

Understanding the fundamental differences between objects and ADTs can help in choosing to use them wisely.

and so my goal is to understand those fundamental differences. The paper first characterises the two kinds of abstraction somewhat theoretically, and then talks about their implementation in practical programming languages: Java, Haskell and Smalltalk.

What I understood

I haven’t totally failed to understand. It’s a good paper and there’s loads of great stuff that I can say I got:

  • ADTs have a visible signature and an invisible representation.
  • ADTs use type abstraction: the type name is visible but the representation is not.
  • complex operations are those which need to access the invisible details of more than one value.
  • simple operations are those which are not complex, i.e. that need access to the invisible details of only one (or zero) values.
  • In theory, ADTs with just simple operations can can be written more simply and with more extensibility as objects.
  • Autognosis: an object should only access other objects through their public interfaces.
  • ADTs alone can support complex operations. Objects have to fudge them by exposing more details in the interface – a trade-off against flexibility.
  • An interesting characteristic function example for objects.
  • Objects are recursive values.
  • The Extensibility Problem: objects facilitate adding new representations; ADTs facilitate adding new operations.
  • A pure object-oriented programming style: client code mentions class name only in constructor calls.

The paper presents a pure object-oriented programming style based on autognosis and class names appearing only after keyword new. It’s a fresh and clear perspective on familiar OO advice such as program to interfaces, not implementation and the dependency inversion principle. Kevlin’s talk picks up on this aspect and shows some interesting consequences, particularly for equals(...). Doing objects right is hard and I won’t claim to understand it, but putting it in this section reflects that it’s a struggle I’m long familiar with.

(I note that the InfoQ editorial team didn’t know quite what to do with the pure OOP-style, calling Kevlin’s talk philosophical and that it explains his view on OOP (emphasis mine).)

What I’m happy to let slide (for now)

I’ve no formal background in maths or theory, and so I’m happy to let some of the theoretical details slide. My knowledge of Haskell and Smalltalk is near non-existent, so I can leave the lessons in those sections until I pick up those languages, too. There are several things I’d like to come back to in the future, and some hints for further reading:

  • Objects don’t use type abstraction, as the representation as a record of functions is known. They use procedural abstraction instead.
  • Existential types are related to ADTs.
  • Universal types are related to parametric polymorphism (e.g. generics).
  • Existential and Universal types are all that there is.
  • The theoretical relationships between the ADT signature and the object interface.
  • The theory relating simple ADTs to objects.
  • Types and Programming Languages by Benjamin C. Pierce.
  • Suggestion that Martin Odersky has solved the Extensibility/Expression problem.
  • How inheritance can add new operations to objects.
  • How/if the Visitor pattern (simulating double-dispatch) can be used to more cleanly handle complex operations for objects.

What I don’t understand: ADTs in Java

The paper is geared towards an audience that understands ADTs well. In my not-at-all-academic-computer-science experience I’ve come across them only in passing. A close reading of the text leaves me confused about exactly how to write them in Java (or any language in which they’re not the only option), and about the space that falls between pure objects and true ADTs.

The summary of section 5.2 ADTs in Java has some simple guidance when a class name is used as a type, it represents an abstract data type. On the surface, and taken together with a class name may only be used after the keyword new, from section 5.1 Object-Oriented Programming in Java, it suggests that were I to accidentally use the class name when I should have used an interface I’ll have a valid ADT. That doesn’t seem right1. There must be a space in-between where I’m just doing objects badly, or at least in a not very object-oriented way. Section 5. Reality supports my intuition:

It turns out that statically typed object-oriented languages all support both pure objects and also a form of abstract data types. They also support various hybrids.

To understand more I need to see an implementation, so I’ve tried to write an ADT in Java. Section 5.2 ADTs in Java offers a Java-like syntax for two signatures: ASet and CSet. The text doesn’t directly reference the two classes, and doesn’t make clear the relationship between them, but I think they’re intended as two equally valid encodings for an ADT. Of the two encodings ASet looks the most ADT-like, so I coded it using the list of integers representation given in Figures 1 and 2 of the paper.

My implementation is in the files ASet.java, RepType.java, Empty.java and Pair.java. Take a quick glance and see they are a reasonably faithful port of the CLU code shown in Figure 12. I’ve summarized the structure with a diagram:

ASet ADT class diagram
Figure 1. Class diagram for ASet ADT implementation

The key for this pseudo-UML class diagram, generated with the wonderful yUML, is here:

Key for class diagrams
Figure 2. Key for class diagrams

ASet has static implementations of the constructor and operations, and RepType, Empty and Pair form my version of the CLU rep, as suggested by

Object oriented languages do not always support the sums-of-products data structures found in other languages, but such types can be simulated using an abstract class with a subclass for each variant in the sum type.

Also as suggested, the implementations of the operations use instanceof and casts for pattern matching, e.g.

public static ASet union(ASet a, ASet b) {
    if (a.rep_ instanceof Empty) {
        return b;
    }
    else if (a.rep_ instanceof Pair) {
        final Pair rep = (Pair) a.rep_;
        return insert(union(up(rep.rest), b), rep.first);
    }
    else {
        throw new IllegalStateException("Someone changed my rep without letting me know!");
    }
}

By following the instructions in the paper and porting the CLU code as faithfully as possible, I think this is as close to a true ADT as I can come in Java. I’m uncomfortable coding in this style, as it seems I’ve been trained to dislike type checks by the predominant OO-style. I’ll try to put that aside and give ADTs a chance. Still, those fall-through cases which throw IllegalStateExceptions are something of a code smell. Java’s static type checker can’t make sure I don’t miss a subtype in my attempt at a typecase – I guess this is a consequence of using a language with no typecase construct and having to simulate it with a runtime technique.

Now I want to try the CSet version. It’s very similar, but the operations are performed by making member calls on the value, rather than by passing the value as a parameter to static functions. Such an interface feels more object-y, so this may help investigate the space between ADTs and objects. The code for CSet is at CSet.java. It’s very similar to ASet, and we can see the structure here:

CSet ADT class diagram
Figure 3. Class diagram for first attempt at CSet implementation

With this more object-like interface for clients, it feels natural to see what happens if we make the CSet class its own representation, rather than holding a reference to a RepType object. The code for this version is at CSet.java, and the effect on the structure is shown below:

CSet is its own representation class diagram
Figure 4. Class diagram after making CSet its own representation

The CSet class becomes abstract, and the instanceof tests now happen against this rather than rep. That shonky typecase that I’m trying to ignore really sticks out now, and I can’t help but push the contains and union methods down onto the subclasses. That results in the new code in file CSet.java, and the following structure:

CSet after pushing down insert, contains and union
Figure 5. Class diagram after pushing CSet‘s operation methods down to the subclasses

With the instanceofs gone I’m starting to relax, and the style is now more familiar. Notice that I pushed the insert method down too. As its implementation depended only on CSet and not the details of Empty or Pair I could have left it alone. Yet by pushing it down I’ve realised an “optimisation” for Empty by eliminating an unnecessary call to contains(int). Now that the two subclasses have a bit more meat on them, it seems right to pull them out into separate files. I can make the classes public, making the static ADT constructor empty() redundant. Finally, I may as well convert CSet from a pure abstract base class (ABC) into an interface. See the code at CSet.java, Empty.java and Pair.java, and the new structure below:

CSet after conversion to interface
Figure 6. Class diagram after converting CSet from abstract base class to interface

Since class names are now only used as constructors, we clearly have an object-oriented data abstraction. We started with ASet in Figure 1, a reasonable ADT implementation. CSet in Figure 3 is so similar that it must belong firmly in the ADT camp. The next step in Figure 4 blurs things a little, but it still feels like a valid ADT to me. Starting from the other end, Figure 6 shows the same representation in object-oriented guise. Figure 5 doesn’t feel significantly different: the details of converting an interface into an ABC and the treatment of insert seem trivial, putting Figure 5 in the object-oriented camp too. I’d soften the paper’s definition of object-oriented programming to read a non-abstract class name may only be used after keyword new.

The big transition from ADT to OO must then happen between Figures 4 and 5: the point at which we swap typecases implemented with instanceof for polymorphism. This coincides with a switch in stance on the Extensibility problem. In Figure 4 the operations are implemented in one place, and apply to all representational variants, making it simple to add a new operation. In Figure 5 the details of each operation are broken up and scattered to the subclasses, making it easier to add a new representational variant (or an entirely new representation) than to add an operation.

Looking at it another way, only the final object-oriented version of CSet feels stable, in the sense that I feel pressure to refactor all the other CSet versions towards that one. This could be a symptom of being unfamiliar with the ADT style, but the poor typecase code does give me a large incentive to change it. ASet has the same typecase code, but its interface makes it feel a bit more stable. To pin it in place it’d actually need to implement a complex operation, and have a scaffold of naming and comments that clearly mark it as an ADT. Even then I’m tempted to look at whether an OO-style visitor could work instead.

Conclusion

The paper admits that

the fundamental distinctions […between objects and ADTs…] are obscured, but not eliminated, in real programming languages

and so I’m not too upset at failing to fully grasp ADTs. The implementation of ADTs in Java seems very unfamiliar, and requires the use of instanceof testing as the poor-relation of a proper typecase seen in other languages. It’s possible that my bias against instanceof is because the predominant Java style is object-oriented, and lots of advice holds that such tests are bad. I might be applying my prejudice to an inappropriate context, but I still feel that I’d need to make a strong case for implementing an abstraction as an ADT in Java. While the paper’s author and Kevlin point out that it is possible to do object-oriented programming in Java, I think I’ve discovered that it’s not really possible to implement ADTs in Java.

Footnotes

1. Though part of me is desperate to try it in on in a code review:

Reviewer:
Why didn’t you use the interface here?
Me:
Oh… err, well, it’s because I’m using an ADT style.
Reviewer:
Me:
You know, it’s the encoding of a final coalgebra XF(X) into the polymorphic λ-calculus. See?
Reviewer:
Oh, yeah, of course. Sorry.
Me:
Nah, just kidding. Let’s fix that up.

2. The sense of the contains test in the CLU insert implementation in Figure 1 of the paper is wrong. There’s a bit of extra whitespace where I imagine that a ‘!‘ or ‘not‘ should go.

2 thoughts on “On Not Understanding Data Abstraction, Revisited”

  1. Hi Mick,

    Thanks for writing about your experience with the paper. I feel I really should expand it into something that is more accessible to a wider audience (book?), with more examples. But I’m not sure when I will find time to do it. My impression is that you have understood the key ideas of the paper very well. The theory is just formalization of these ideas.

    You are right that Java doesn’t provide good support for writing ADTs. But you might get more of a sense of the motivation for ADTs if you implemented an two more operations on your sets: intersection and is_empty. When implementing these operations, it is necessary to inspect the representation of two objects. Doing so requires either more methods to expose the internals, or else using “instanceof”. I haven’t coded up the full example, but I think there isn’t really any clean way to implement Object-Oriented sets with these operations (without an iterator). Alternatively, you have to add an iterator to the interface. ADTs have no problem, because it is standard for them to inspect multiple objects.

    One thing that bugs me, which you hint at in your comments on Kevlin’s talk (which I *love*, by the way), is when people say that this is somehow my personal view of objects. I’ll agree that it is a purist view, but I think my description captures the essence of objects in a way that many other descriptions do not.

  2. Hi William,

    Thanks for your comments. I’d be interested in an expanded text, and a little bird tells me you may have just committed to writing it with Kevlin. If you could use a set of numpty-programmer eyes on a draft, I’d be happy to try and help.

    I’ll try adding those extra operations – I think I see what you’re driving at, but am sure it’ll be instructive to actually do it.

    On the purist view of objects, it bugs me too. My gut feeling is that your description brings out the essential truth hidden in decades’ worth of writings about objects. I’m just not well enough informed to say that’s really the case. (So I’m left taking parenthetical side swipes at InfoQ editors, who probably feel just the same.)

Leave a Reply

Your email address will not be published. Required fields are marked *