Inheriting type safety

Tony λ has written another post explaining type systems to “blub” developers. Although I'm a blub programmer myself I thought I'd attempt to provide some background and examples of what he's talking about for those who might find his explanation confusing.

First off though the article on inheritance he seems to be complaining about. The author is describing the difference between two kinds of inheritance, but he doesn't have any good vocabulary to explain it and Tony isn't cutting him any slack. What he's talking about in Tony's terms is the difference between structural and nominal sub-typing and explaining that because Java only allows one of them there are all sorts of things that are difficult to do in the language.

In terms familiar to most programmers it's the difference between the Java sort of type checking and dynamic languages. Java's type system is based on the descent of the classes (what I call inclusional polymorphism — because the type of the sub-class is “included” within the type of the super-class — but is really nominal sub-typing, based on the name of the type) and ducktyping (what I would call operational polymorphism — because only the operation used need be present — but is really a form of structural sub-typing, based on the structure of the type).

What Tony is complaining about is that many programmers who haven't seen proper type systems think that you can either have type checking and have interfaces that you derive from, or you have dynamic languages which are essentially an un-typed free for all. As Tony explains in, what to me are rather confusing terms, this isn't true. Many languages can deliver the benefits of type checking whilst also giving you the programming freedom that dynamic languages give.

Tony seems to favour Java for his examples, but I'm going to switch to a different “blub” language that will allow us to explore more of what he's explaining whilst still using blub syntax.

struct I {
    T i();
};

struct J {
    U j();
};

struct K : public I, public J {};

struct L : public I, public J {};

K and L both inherit from both I and J. The problem with this comes when we want to write some code that requires both i() and j(). We now have to choose which of K and L to use as the type to pass in to our function:

void process( K k ) {
    k.i();
    k.j();
}

So what happens when we have some other thing derived from L? We cannot pass that to process() without a lot of fiddling about — the Adapter.

We have type safety, but not at the right level. process() really wants “I with J”, but choosing one of K or L to describe that is as close as we can get with a language like Java.

Now, what if we were using a dynamic language? Written in terms of C++ we could define process() like this:

template< typename T >
void process( T t ) {
    t.i();
    t.j();
}

This seems to completely solve our problem. We can now pass in any K or L, or indeed anything else that implements both I and J. The problem is that we've turned off the type checking in order to do it.

struct NotI {
    T i();
};

struct NotJ {
    U j();
};

struct NotK : public NotI, public NotJ {};

struct NotL {
    T i();
    U j();
};

We can also pass any instance of NotK or NotL to process(). This is hardly a step forwards in terms of type safety!

The question is, can we have it both ways? Is there a way of ensuring that we are actually getting an “I with J”? Luckily at least one blub language does allow this:

template< typename T >
void process( T t ) {
    t.I::i();
    t.J::j();
}

We are now allowing any type to be passed in, but we have qualified the names i() and j() in such a way that if we try to pass in a NotK or a NotL the compiler will give us an error. What we've done is to specify to the compiler the type of i() and j() that we want to use, and because it has that information it can check every use for us.

Here are the sorts of errors a C++ compiler gives if you try to pass a NotK to the new, type safe, version of process():

error C2039: 'I' : is not a member of 'NotK'
error C2662: 'I::i' : cannot convert 'this' pointer from 'NotK' to 'I &'
error C2039: 'J' : is not a member of 'NotK'
error C2662: 'J::j' : cannot convert 'this' pointer from 'NotK' to 'J &'

Now that's type safety!

This is probably relevant.