Working on inheritance

Anyone who has studied Factor's object system in depth will already be familiar with one form of inheritance already provided: union classes and the closely related mixin classes.

So why am I working on another form of inheritance? How is it implemented, and what does it buy me? And on a related note, isn't inheritance evil because some famous Java guys said so on their blog? Well, I'll try to answer these questions in this post.

First, a recap of existing facilities. A union class has members; methods defined on the union class dispatch on instances of all members of the class. Mixin classes are like unions except they are extensible; new member classes can be added after the fact. I've blogged about Factor mixins previously.

Declaring your class an instance of a mixin is a form of behavior inheritance; in C++, you might inherit an abstract class which only contains methods. You can test if an object is an instance of a mixin class, or define methods on the mixin class which then apply to instances of all members of the mixin.

This is very nice, and mixins are very powerful. We use them for protocols -- declaring that your class is a sequence, for example, and also for sharing behavior; if you declare your class is an immutable sequence, you get default methods for set-nth and set-length which throw "sequence is immutable" exceptions. Some mixins are a combination of both; the growable sequence mixin is used to share code between vectors, bit vectors, byte vectors, float vectors and string buffers. It expects instances to provide certain generic words, and using those words it implements the entire sequence protocol.

However, mixins alone are not enough. There are cases where what you really want to do is inherit from another concrete class; that is, you want to inherit some state (tuple slots) as well as behavior. So far, this niche has been occupied by delegation. When you call a generic word on an object, if the object's class doesn't have a method for that generic word, the method call is forwarded to the delegate. This works well in many cases but not only is it inefficient (with a long delegation chain, you basically end up with a linear method search) but it suffers from the slicing problem: if an object A delegates to B, then methods defined on B no longer receive the instance of A on the stack, they receive the instance of B; and if this instance is stored somewhere in a collection, the "A-ness" of the object is "sliced off". Delegation is also impossible to analyze statically because an object's delegate can be changed at any time, dynamically. Finally, delegation wastes memory. Each tuple has a delegate slot that is empty in the great majority of cases, and if you have several objects composed in one long delegation chain that represent one domain entity, you end up wasting the space used by each object's header (and delegation slot).

Delegation is still useful in many cases. Once the core delegation feature is removed, you'll still be able to write code which manually forwards method calls to slot values, however in most cases this isn't necessary, and is also discouraged because it leads to ugly, Java-style code. A real replacement can be found in extra/delegate, which is Daniel Ehrenberg's delegation library. It is more flexible than core delegation because you can specify which slot to forward methods to on a per-generic word (or per-protocol) basis; there is no distinguished "delegate" slot. It also offers a solution to the slicing problem where one tuple can "mimic" another. Dan has a blog entry describing his delegation system in more detail.

Most people in the Factor community nowadays take it for granted that a powerful delegation mechanism can be implemented as a library in Factor. What's more interesting is that while delegation can be done as a library, inheritance is something that really needs core support. This shows that it is more fundamental.

I should emphasize that tuple inheritance is a work in progress: I will post another blog entry when it makes its way into the git repository and is ready for prime time.

So how does it look? The syntax is pretty simple:

TUPLE: vehicle occupants ;
TUPLE: car < vehicle engine ;
TUPLE: aeroplane < vehicle cargo ;
TUPLE: checked-luggage owner ;

If the tuple class name is followed by <, the next token is a class name to inherit from. Tuples without an explicitly-given superclass inherit from the tuple class.

To be consistent, I changed the syntax for predicate classes:

PREDICATE: even < integer 2 mod 0 = ;

The old syntax looked liked so, but it didn't gel with the new tuple inheritance syntax:

PREDICATE: integer even 2 mod 0 = ;

Unlike with tuples, predicate class definitions must specify a superclass; there is no implicit default.

The new slot accessors I've been taking about work nicely with inheritance:

: sort-cargo ( aeroplane -- seq )
    [ occupants>> ] [ cargo>> ] bi
    [ [ owner>> = ] with subset ] curry map ;

Before you would have to qualify each slot with the class you were reading it from, so you had to know that occupants was in vehicle but cargo was in aeroplane:

: sort-cargo ( aeroplane -- seq )
    [ vehicle-occupants ] [ aeroplane-cargo ] bi
    [ [ checked-luggage-owner = ] with subset ] curry map ;

While in some sense the longer slot accessors made code more explicit, peppering them all over a source file just made things look visually cluttered and made code less generic than it could be: with new slots, I can write something that works on a ship or an aeroplane, provided both have a cargo slot; they don't even need to inherit from a common superclass.

Before, testing if a tuple was an instance of a class was very straightforward: you read the tuple header, and compare this with a class instance. Now it is not so easy, because if you have an instance of aeroplane, well, it is still a vehicle, even though its header is different. I used a neat trick to implement class tests in constant time. I did not invent this trick, I read about it elsewhere and I forget where, and I probably would not have been able to think about it myself, but it is really quite straightforward. It only works for single inheritance, though. Each class object stores a sequence containing all of its superclasses. The first element is the tuple class, the last element is the class itself. To test if a class object A is a subclass of a given class object B, you first check if A's superclass chain is at least as long as B's. If not, then A cannot possibly be a subclass of B, since if it were, its superclass chain would be at least as long. So we assume that A's superclass chain is at least as long as B's. Now if A is a subclass of B, then B's superclass chain must be a prefix of A's; in fact, suppose B's superclass chain has length n; then the nth element of B's superclass chain must equal B, and since B's superclass chain is a prefix of A's, that means that the nth element of A's superclass chain must be equal to B also. So you perform these two checks: compare the superclass chain lengths, and check if an element at a constant index is equal to B. If both tests succeed, then A is a subclass of B. To extend this to a predicate on objects which tests if an object X is an instance of B, you simply first get an object's class, then check if this class is a subclass of B. Very nice trick: if anyone knows of a way to generalize this to multiple inheritance, let me know.

Finally, there are some programmers who like to repeat this mantra that "implementation inheritance is evil"; they write blog posts with a handful of contrived examples, then a statement along the lines of "all future languages must not have inheritance", finishing off with a bang. These people have limited experience with programming languages and their arguments boil down to three core forms, neither of which is sound:

• Problems come up when inheritance is used to model "has-a" relationships instead of "is-a" relationships. Code becomes less clear and less reusable than it needs to be in this case. But this is not a fundamental flaw of inheritance, it simply reflects a lack of thinking on the part of the designer. The dual problem, of course, is of course abusing delegation to model "is-a" relationships: if you abolish inheritance, you end up writing lots of boilerplate methods which simply forward calls to other objects, and you get the related issues with performance, space usage, and the "slicing problem". This is what happened in Factor; I was using delegation to model "is-a" as well as "has-a", and in the former case it was simply the wrong thing to do.
• The other problem cited is using inheritance purely as a means to share code. This is indeed an abuse of inheritance; just because two types support the same operation doesn't mean there is necessarily a formal relationship between them. However, this only comes up in statically typed languages with type systems that are very much behind the state of the art; if you have a static type system with parametric polymorphism, structural subtyping, and so on, writing generic statically-type-safe is easy, and in a dynamically-typed language such as Factor it is a complete non-issue. As long as you have a set of types which have methods on a certain generic word, or slots with the same name, your code doesn't ever have to care about what the actual type of the object is.
• There are issues specific to the implementation of inheritance in a single language: memory management in C++, the interactions between inheritance and constructors in Java, and so on. These concerns are irrelevant to me, except as a case study of the mistakes of those that have come before.

Incidentally, the same people like to rail against multiple dispatch, macros, singletons, dynamic scope, etc. I'm trying to avoid dogma here and isolate the essence of each language feature, implementing it without unnecessary limitations and avoiding odd quirks, staying out of the way until you need it (if at all). Factor is a great vehicle for this because it starts with a simple but extensible core consisting of highly orthogonal primitives; new abstractions can be built up effortlessly. My goal is to have the Factor programmer be free to choose the best abstractions for expressing their problem without needing a 500-page book of "gotchas" and "best practices" on hand, and without having to memorize awkward "design pattern" workarounds resulting from short-sightedness on my part. If I ever add a single language feature which requires that one consult a huge FAQ to understand some arcane interaction, then it means that I have basically failed.

Factor is going to give you mixin inheritance, tuple inheritance and fine-grained automatic delegation as an additional library; all will be documented, and the library will give good examples of idiomatic usage of all three to help beginners learn when each technique is appropriate. The limited and poorly-designed core delegation feature is going away. Exciting times ahead!