“isa” relationships and inheritance

General

Think you know what “polymorphism” means? Well, the Object-Oriented textbooks have been keeping a dirty little secret from you. Polymorphism isn’t just the base/derived reuse capability you know from modern languages. That is just one limited way that these languages support polymorphism. If you’ve done any template metaprogramming or used the C++ STL much, you might be seeing another way to support it.

This page examines how C++/Java style polymorphism by inheritance works, and why it is too limited.

Substitutability

Code that is originally written to use some class may be passed an object of another class and we expect this to be acceptible to the compiler and to work properly. This is a feature of many modern languages. Let’s take a look at just how it works, including a peek under the hood.

Listing 1

class B {
public:
   virtual int m1 (int)
      {
      cout << "Base m1 called" << endl;
      }
    int m2 (double)
      {
      cout << "m2 called" << endl;
      }
   }

class C : public B {
public:
   int m1 (int)
      {
      cout << "Derived m1 called" << endl;
      }
   }

void foo (B& object)
 {
 object.m1();
 object.m2();
 }

// ... later ...
C myobject;
foo (myobject);

In this sketch code, (Listing 1), what happens when foo is given an object of a type other than what it was written for?

The implementation binds the parameter object to the instance of C, and proceeds to run the same code that was compiled with the assumption that object points to an instance of B. This is not surprising that it works, because the way base/derived classes work is to extend the original. For regular (non-virtual) functions and private data access, everything works the way it did before, simply ignoring that more instance data has been added to the end of the record. In C++, this shows up in that you can’t store derived objects by value (as opposed to pointers) in an array, for example.

The call to m1 is a little more interesting. The virtual function provides for overrides by derived classes, so the version of m1 actually called is the one for class C. Once in there, it knows about the full C-ness of the object and can do more than was imagined by foo when it was written with knowledge of only B.

The way the overridden function is efficiently called is by using a virtual function table. Part of the data for the object is a pointer to this dispatch table, and by putting a different function address into the same slot, it allows overrides with simple fixed generated code, rather than a fancy dictionary lookup as with untyped languages.

There are two things we are taking for granted here, and we are so used to it that you might not even notice most of the time.

  1. The derived object physically contains a region that is a perfectly good base object when viewed on its own.
  2. The replacement virtual functions seem the same to the caller.

Now let’s violate those assumptions and see what happens.

Signature Matching

Listing 2

   double C::m1 (double)
      {
      cout << "Derived m1 called" << endl;
      }

Let’s change the definition of C::m1 so the signatures don’t match. (Listing 2)

The newer class wants to work with doubles instead of ints, which does not seem like an unreasonable thing to do. After all, the new class extends the old, and maybe allowing fractional settings is one of the ways in which it is extended.

Well, C++ gives a compile-time error. The signature must match exactly; you cannot change the parameter type from an int to a double.

Try another language: Java? Nope. C#? Get real. Eiffel? Sometimes, but not this time. Smalltalk or Javascript? Doesn’t do parameter types at all. Perl 5? Same, more or less.

The problem is that the code in foo was compiled to call m1 a certain way, and changing it is just not going to allow the compiled code to work.

But there’s more to it than that. We could make a wrapper around it, and call that instead. Suppose that our extension kept the signature of m1 the same (it has to), but provides a m1_frac as well that new code can use. The implementation of m1 just calls m1_frac. Perhaps the strict rules can be relaxed, and allow automatic wrapping when types can be somehow converted.

Not just any change mind you, but just those that can be automatically wrapped by conversions, and maybe not even all of those.

Normally we have no issues playing fast and loose with numeric types. Convert an int to a double? No problem. An int to a float might give cause to think though, in case 2,000,000,099 gets rounded off to a 23-bit mantissa and munges 0111 0111 0011 0101 1001 0100 0110 0011 into 0111 0111 0011 0101 1001 0100 xxxx xxxx and becomes 2×109. Converting a double to an int? Well, obviously need to throw away the fraction, and also worry about overflow, since the double might return eighteen trillion or something.

Listing 3

// I can do it myself...
double fun1 (double);
int in = 3;
int out = fun1 (in);

// so why can't foo do it on my behalf?

But, in general you decide when you want to use a double in code that expects an int, and vice versa, and make the decision as to acceptability. So maybe the language should write this wrapper for you, if you wanted it to. Sure, make it a warning, just like double-to-int is at any other time.

There is a little matter of who decides what is acceptible. You might get a warning only when C::m1 is written with the double return value, the same as when writing out=fun1(in) directly. But the user of foo with an object C might want to have it brought to his attention when he calls foo—the earlier warning is just noise and there might be lots of cases not to worry about or never used like that. That will be another article.

Covariance and Contravariance

So table that thought and consider the cases that always work OK. This is often called “Covariance and Contravariance” as in this article on Wikipedia. Basically, the rules for supplying different signatures in an override are:

  1. Parameters may be more general than the original.
  2. Return values may be more restrictive than the original.

Following these two rules ensures that the new function can drop-in where the old one was and there won’t be any conversion problems.

Often, a derived class would want to use the new more-derived class in the ways that the base class used the base class. This naturally shows up in parameters and return values, and is why this is called Covariance, meaning to vary in the same direction.

Listing 4

class B {
   method m3 (B $self: B $other --> B) { ... }
   }

class C is B {
   method m3 (C $self: C $other --> C) { ... }
   }

Since C is an improved B, you naturally want to make functions that work with C’s the same way older functions worked with B’s. Here m3 operates between two instances of the class and returns a third. It is perfectly reasonable to want to redo it in C so it operates between two instances of that derived class and returns a third.

Upgrading the return type is no problem, as code that calls B::m3 (and gets C::m3 instead) will receive something that “isa” B in return. But what about the parameters? The calling code will want to pass in B’s, and the new code is expecting C’s.

Now there are times when this works out, because the B’s are all really C’s already, but the compiler will not be able to check this for you. In untyped languages, you just watch for mistakes at run time.

The actual rules of substitutability for pre-compiled base/derived code requires that parameters be contravariant, that is, varying in the opposing direction (with the exception of the invocant self which is known to be the right type because of the way dispatching works). The override could accept more than the original and not be bothered by existing users thinking they are getting the old function, but it cannot accept less without run-time checking to ensure that you are really actually changing out all the objects, even though the type system cannot tell.

“isa” or isn’t it?

In the previous listing, class C is derived from class B. But, there is no “isa” relationship from C to B. Get used to it. If you only do things that you could have done in C++, then you will be assured of “isa” relationships. If you violate the two rules concerning what you can override, then it lets you do that, but you lose the simple substitutability.

If you want to make sure you write code that follows the old rules, you can use instead of is :subtype when deriving, and the compiler will complain if you voilate the rules.

Listing 5

class B {
   method m3 (CLASS $other --> CLASS) { ... }
   }

class C is B {
   # don't override m3 yet.
   }

# testing...
my B $x = C.new;  # nope!

Let us revisit this example source code. Originally, class B was sprinkled with instances of B, and class C was sprinkled with occuraces of C. Rewriting this (Listing 5) with the intent of removing explicit references to its own name, something more happens.

Previously, I included an explicit parameter for the invocant to make it clear that the function operated on two values of the class’s type. This time I leave it off, because the keyword self can always be used, and there is no reason to name the type. But the other explicit references to the class’s own name have been replaced with the automatically supplied symbol CLASS. Here, CLASS refers to B, of course.

Now as written, without overriding any methods yet, what is the relationship between C and B? The assignment to $x fails, because there is not an “isa” relationship between C and B. The reason is because the inherited method C::m3 automatically changed all the occuraces of CLASS to C for you! You get the same effect as the first example, already. Use of C will give you C’s back from calls to m3, without having to downcast.

Changing the Structure

Earlier we mentioned there were two assumptions being taken for granted. The other one, to jog your memory, is “The derived object physically contains a region that is a perfectly good base object when viewed on its own.” The deal with changing B’s to C’s automatically in the base class should give you an idea where this is going.

Listing 6

class B {
   has CLASS $!priv1;
   has Int $!priv2;
   has Q $!priv3;
   ...
   }

class C is B { ... }

Type names used inside classes are virtual.

That sentence takes a whole paragraph because it is so profound. Look at it again and ponder it for a bit before continuing.

This time (Listing 6), don’t worry about signatures of methods and just look at the private data. The ! twigil declares $!priv1 et al. to be private with no automatically generated accessors.

So the instance of B contains another (reference to) B. What happens in C? Same as before: the B is changed to a C. That goes beyond the CLASS symbol—type names are virtual in general. Now $!priv2 is safe because global types are except, so Int stays Int for good. But Q is fair game. When the block of class B is compiled, the meaning of type Q was looked up according to scope rules. When class C is defined, which might be in another file in another module, it will forget the old Q and search afresh. It might find a different type named Q, in that other module.

So, looking at the internal structure of C, there is nothing inside it that resembles a stand-alone B object. So much for old assumptions that worked for object-oriented languages for decades!

Conclusion

A subtype is one that can be substituted for another in already written and compiled code. You are used to derived classes being subtypes.

It’s only so because there are rules to ensure that. Lift those rules, and you change the nature of the beast. In Perl 6, derived types don’t have to be subtypes.

But don’t fear code reuse. How much type checking you have is pretty flexible and optional. And there are other mechanisms for strong-typed polymorphism including the use of generic types, and new language features that bring the power of generics to update the old ”isa” concept.

See Advanced Polymorphism in Perl 6 — Features of a second-generation type system (PDF) or (ODT) if that intrigues you.