Polymorphism & inheritance



There's a general sense that having a big, complicated inheritance system is what gives us polymorphism. Sure, there are flexible languages with untyped variables and "duck type" functions. Those are polymorphic-ish, but different somehow, maybe? It seems as if the invention of inheritance gave us true polymorphism. It turns out, no. Simple typeless polymorphism and the fancy inheritance kind -- the same thing.

It turns out that inheritance adds type-checking to polymophism. Ah! That makes sense -- if you want a strongly-typed language, also with polymophism, then you need inheritance to maintain your strong typing. But inheritance doesn't improve the actual polymorphism.

Polymorphism review

When we say polymorphism is great we're really saying polymorphic functions are great, which they are. Those are functions which can do whatever it is they do to multiple types. For example, a function which can sort a list of whatever. Or, more typically, a function which can manipulate groups of any UI elements as long as they all have activate(), disable() and so on. It won't do exactly the same on buttons as on labels or sliders, but that's the point. A polymorphic function can adapt little bits to use the correct version of activate().

That all sounds like how computers should always work. How else would it happen? Polymorphism seems so obvious that we shouldn't even need a word for it. But we have one, since it wasn't. In the most common languages nothing was polymorphic: we needed an integer-array sorting function, another to sort doubles, and so on. Each type we added needed a new sorting function. Our UI-handling function -- same thing -- another copy for each type of UI element. It was totally obvious was a huge waste this was -- we knew they were copy&paste of each other, and could imagine combining them in a single "sorts all types" function, but the tech wouldn't allow it.

The origin of the problem is that we prefer strong type systems -- where everything gets a single known, fixed type. Strongly typed systems can be great. They catch many common problems early, saving so much debugging time. They're also fast and efficient -- the compiler can do lots of work ahead of time, resulting in an optimized executable. For example, they run functions using a great trick called static dispatch.

When the computer sees if(A[i]<A[j]) it figures out whether the < is string-compare, integer-compare or whatever. But, with static dispatch, the compiler does the thinking -- not the runtime. The executable is a preset jump to string-compare. That runs blazingly fast, but can't be polyomorphic. If we somehow gave it a list of integers the executable would keep calling string-compare. It has to. And static dispatch is used everywhere.

The solution is simple -- move the thinking from the compiler step into the executable. That's dynamic dispatch. The running program sees if(A[i]<A[j]) and looks up the type of A. It decides which < to use as it runs, every time it runs. That's slower, but gives us polymorphism.

We can now give a better definition of a polymorphic function. It's a function which can do a general thing to lots of types which has small tweaks for each particular type -- how to compare items, or the exact way activate() works. These will be plug-ins, but built into each type. It can automatically find and run these, using dynamic dispatch.

Polymorphism without inheritance

Here's a sample polymorphic Python function. It doesn't do much, hopefully just enough to be "a general thing which many types might want to use". It works with any type that has price() and isTaxable() members:

def costWithTax(item) {
  p=item.price(); // Python doesn't declare variables
  if(item.isTaxable()) p*=globalTaxRate;
  return p;

Let's check the rules for whether this is polymorphic. It accepts several types for item since Python variables can always be any type. Each type can have their own versions of price() and isTaxable() since Python allows adding members willy-nilly. price() and isTaxable() are called using dynamic dispatch since all members in Python are called that way. So this is fully polymorphic.

Those Python rules seem like massive overkill. Maybe 2% of all functions should be polymorphic, but Python makes it so 100% are, even if you will never use them that way. In other words, Python uses slow dynamic dispatch when it's almost never needed. But this also means you need zero extra work when it is. Python just is polymorphic, to where you don't even need to know that word.

Polymorphism with inheritance

With inheritance we're in the strongly-typed world where each variable has one exact type. We'll need a trick to get multi-type variables; that trick is subclassing. It ends up being surprisingly simple -- take any hand-made class as input and you're polymorphic. That's because if a function takes the Animal class, Animal could have Sheep and Cow subclasses which the function will also accept, and viola -- it's polymorphic. Here's the inheritance version of costWithTax (assume our made-up Animal class has price() and isTaxable() members):

double costWithTax(Animal a) { // <--only change, takes Animal
  double p=a.price();
  if(a.isTaxable()) p*=globalTaxRate;
  return p;

Onto the how this is polymorphic. First, it takes multiple types because of subtyping -- Sheep, Cows and so on. That's fewer than the Python version, which takes all types, but it's good enough for now.

Next item: each subtype can, by overriding, provide its own version of the two functions. They might merely inherit from Animal, or it might involve a complicated look-up through parents and grandparents (or not -- that stuff is usually precomputed into a jump-table). But ultimately each type freely decides on its own price() and isTaxable() members.

Finally, it uses dynamic dispatch, probably. In the inheritance world normal functions use static dispatch, switching to dynamic when we have a class with subclasses. Or at least Java does it that way. C++ and C# require you to explicitly enable dynamic dispatch with the virtual keyword. That makes them "virtual functions", which is just a fancy way of saying they use dynamic dispatch.

All-in-all, this is polymorphic in the same way the Python version is. Sure, it required more complicated reasoning, and inheritance does extra stuff we're ignoring, but the way the polymorphism works is the same.

Fixing pure inheritance with interfaces

Using the Animal class in costWithTax is clearly terrible. It limits the function to only Animal's, when any class with price() and isTaxable() should be able to use it.

I used Animal since it's standard old-style inheritance. That likes to create big trees, which is a huge pain since most things aren't big trees. The modern solution is thin interfaces and multiple inheritance. To do that, first we create a class with the bare minimum requirements for costWithTax:

class Buyable {
  virtual double price() { return 0; } // will be overridden
  virtual bool isTaxable() { return false; } // ditto 

It's purpose is to be the type costWithTax accepts, which we'll use it for:

double costWithTax(Buyable b) { // <--change to Buyable
  double p=b.price();
  if(b.isTaxable() p*=globalTaxRate;
  return p;

Ignoring this interface for now, as a practical matter any class wanting to use costWithTax needs to have price() and isTaxable(). The interface provides a way for type-checking to enforce that: a class needs to inherit from Buyable to legally use costWithTax, which in turn requires the class to overload those 2 members, which allows the IDE to yell at you if you don't. If you like your IDE to give lots of hints, this interface is just terrific.

Technically a class inherits these interfaces, but we don't think of it that way. When you inherit for real you get all of the stuff from your superclass, then you can add or override. When you "inherit" from an interface you don't get anything useful, instead you're required to write all of the functions in it.

Mentally we divide them actually inheriting, and "I confirm to this interface":

// Robot really inherits from Machine:
class Robot : Machine, Buyable, Comparer { ... }
// also works with     ^^^^^^^  ^^^^^^^^  these interfaces

In older C++, interfaces are simply classes repurposed that way, but Java makes them formal, using the keyword interface. Technically Java has you inherit from (at most) one class, and then implement interfaces (still the exact same syntax and semantics as inheriting). So that's fun.

Basically, the idea of interfaces completely fixes inheritance-based polymorphism. We can write our polymorphic functions, give them an interface, and slap it onto any class that wants to use them. We're as flexible as duck-type, we just need to type more.

Duck type

Sometimes we call simple polymorphism "duck typing". It's from the expression "if it walks like a duck and talks like a duck...". It means we don't care what something is, we care what it does. That often simplifies things.

Suppose some other polymorphic function uses only price() (and not isTaxable()). We might create a new interface for that with just price(). Or, to save time, we might keep the input as a Buyable (assuming everyone implements price() and isTaxable() as a set anyway). Or we might redo everything as 1-function interfaces then add a new rule for a "combination of interfaces" type. Yeesh. With duck-typing we don't worry about any of that -- a class with price() can use functions needing price(), and that's that.

A drawback of not having formal interfaces is not being able to re-use names. With a formal interface system we can use the interface as a namespace, like Buyable.price() together with klm.price(). Of course we've been faking that for decades with names like buy_price and klm_price, so it's not much of a drawback.

So what's inheritance actually for?

So, inheritance-based polymorphic functions merely add an interface. But they don't even do that. Duck-type has the same interfaces, we just don't write them in code. Inheritance gives us formal interfaces -- things the compiler can read and complain about.

With formal interfaces the coder can hover over Buyable in a heading and read a pop-up with what's in it. We can get nice dropdowns full of only classes using that interface. We can get more wavy red error-lines (which is much better than a run-time error). A smarter IDE can be a real help. Meanwhile, our duck-type version has us looking inside the body to see what sub-functions we need.

More interface methods w/Scala

Scala (a type of Java) uses basic strong-typing and inheritance, but walks a little towards duck-type with two new interface ideas. First, here's a Scala Buyable interface and costWithTax using it:

// a Scala Buyable interface:
type buyable = { def isTaxable():Boolean, def price():Double }

// costWithTax in Scala:
def costWithTax(item : buyable) : Double = { ... }

The first new rule says we don't need to formally inherit from an interface to use it. This Painting class can be used with costWithTax without mentioning buyable:

class Painting { // <--doesn't mention buyable

  def isTaxable():Boolean { ... } // <--but confirms to it!
  def price():Double { ... }

That's barely a change -- we no longer need to declare Painting as a :buyable. But that means we're technically no longer using inheritance. When Painting calls costWithTax it's using the duck-type "I have the functions you need" rule.

Idea two is anonymous interfaces. A function can write down its interface, with no name, directly in the heading, in Scala:

// an anonymous interface:
def costWithTax(
      item : { def isTaxable():Boolean; def price():Double }
    ) :Double {

We started out with inheritance and an interface, but with this trick we've gone all the way to duck-typing. We don't have interface names anywhere -- just a duck-type function with the requirements written on top. For extra fun, let's flip our thinking and imagine this is our main way of writing polymorphic functions. Using a named interface is really just a shortcut for when lots of functions have the same interface. In other words, we can think of these new rules as weaker inheritance, or as stronger duck-typing.

C++ goes one better

C++ mostly uses standard inheritance-style polymorphism, but has a feature to do it duck-type. It's a language letting us use polymorphism either way. Of course C++ functions take a single type and use static dispatch. We'll need a special syntax for duck-type. Here it is in costWithTax as a C++ template function:

double costWithTax<T>(T item) {
  double p=item.price();
  if(item.isTaxable() p*=globalTaxRate;
  return p;

The <T> after the name lets us know it's polymorphic. It says T is a fill-in-the-blank type. Then it says the input is type T. So this is a long way to say item can be any type. It seems awkward but it's so we can replace T with a real type and have it look like a normal function.

Amazingly, this is also type-checked statically. In other words, if you call it with a type without price(), you get a red-underline right away. It turns out the only reason Python can't do that is its crazy rule allowing you to add and remove members as it runs.

Another fun fact -- these fake dynamic dispatch. C++ actually creates a copy for every type you need. Each copy is a completely normal non-polymorphic C++ function. Even so, it acts like a duck-type polymorphic function and that's what matters.

Inheritance plopped right on top

The language TypeScript is a great example of this thesis -- inheritance is merely type-checking dropped on top of duck-type polymorphism. That's because TypeScript is an add-on to javascript which does exactly that.

Javascript has the same typeless variables and duck-type functions as Python. Since it's the only language which runs on a browser, there are piles of strongly-typed languages compiling into it. TypeScript technically is one of those, but it's literally javascript with a type system added. Seriously. To convert your javascript to TypeScript, add formal interfaces and types. Leave your functioning code completely unchanged. To compile TypeScript into perfect javascript, remove all of the type information.

TypeScript is working proof that both polymorphism approaches are the same. Write any inheritance-based polymorphic function in TypeScript uisng an interface and inheritance. Then convert it into javascript by removing the type information. You've got the get the exact same function, running the same way, but now it's duck-type javascript.

TypeScript also borrows Scala's anonymous interfaces, since it's just a nice feature:

// using an anonymous interface:
def costWithTax(p : { price():Double; isTaxable():Boolean })

Passing along the parts

The great thing about polymorphic functions is how they can automatically look up the subfunctions. The caller can pass in a Sheep and be done -- dynamic dispatch will find Sheep.price() and Sheep.isTaxable()all by itself. This is great. The drawback is how every Sheep uses the standard Sheep.price() every time. But in most cases that's not a problem.

But some functions work best with options, for example, sorting. We don't want to be stuck with a class's built-in compare. Typically we'll pass in our own, for example sorting strings by length: sort(A, (a,b)=>a.len<b.len). In theory, we could convert costWithTax to that style:

// passing in the sub-functions:
def costWithTax(item, priceFunc, taxFunc) {
  if(taxFunc(item)) p*=globalTaxRate
  return p

To make that less rediculous, imagine we have a list of items, and that price() and isTaxable() change depending on the market. Maybe for a junk dealer the price is based on weight, and only items containing lead are taxed. In general, this trick is best with arrays. Extreme examples are generic functions such as AppyToAll or "add all of these together somehow": M2=applyToAll(M, m=>m.trim()).

Functions like this essentially have the interface built-in. You obviously need price and tax functions since there are two slots where you're required to put them. But you don't need to personally have them. These functions are beyond inheritance and duck-typing.

Concluding thoughts

Having one type of polymorphic function with two flavors is good. It makes it easier to switch between language styles. If we're used to inheritance-based polymorphism, we can think of duck-type the same, except the interfaces are in our head. If you use javascript and all of those interfaces in Java are intimidating, they're just writing down what you already have.

The big result is no matter what, take time designing a nice interface. That's at least 60 years old, which seems comforting.




Comments. or email adminATtaxesforcatses.com