When Polymorphism Fails
Every OOP fan is almost by definition a fan of polymorphism. Lots of otherwise good books (e.g. Fowler's Refactoring) go so far as to say if you use runtime type checks, e.g. Java's "instanceof" operator, then you're probably an evil person who threatens little children with switch statements.
Generally speaking, I would agree that the use of "instanceof" and its ilk are usually a sign of weak OOP design skills. Polymorphism is preferable to runtime type checks, resulting in cleaner and more maintainable code. However, I think there's at least one situation, almost common enough to merit being a pattern of its own, where you simply can't use polymorphism. I'd love to, and if you know how, please tell me, but I just don't think it's possible, at least not with more or less static languages like Java and C++.
In case you're (somewhat) unfamiliar with OOP terminology, polymorphism is a pretentious name for the concept of late binding. Late binding is a pretentious name (you'll see a pattern here if you dig far enough) for deferring the decision for which method to call until runtime, when the target is inspected to see if it responds to the message.
In performance-oriented languages like C++, Java and OCaml, methods are given numbers, and for each class a method table is built out and scanned at runtime. In languages oriented towards runtime flexibility, method lookups are typically done by hashing on the method name. Otherwise the two approaches are pretty much equivalent.
Virtual methods don't, by themselves, yield polymorphism. The polymorphic part comes into play when you have multiple subclasses of a given class, each implementing their own version of the polymorphic method, and each handling it differently. As an extremely trite textbook example, if you go to the zoo, you'll see that all of the animals have different ways of handling the createBadSmell() message. Well, they're pretty similar in some respects; I guess it's more a question of magnitude. I still can't decide whether the hippo's performance beat out the giraffe's, but ask me about it sometime.
As an example of polymorphism in action, let's look at the classic "eval" interview question, which (as far as I know) was brought to Amazon by Ron Braunstein. The question is quite a rich one, as it manages to probe a wide variety of important skills: OOP design, recursion, binary trees, polymorphism and runtime typing, general coding skills, and (if you want to make it extra hard) parsing theory.
At some point, the candidate hopefully realizes that you can represent an arithmetic expression as a binary tree, assuming you're only using binary operators such as "+", "-", "*", "/". The leaf nodes are all numbers, and the internal nodes are all operators. Evaluating the expression means walking the tree. If the candidate doesn't realize this, you can gently lead them to it, or if necessary, just tell them.
Even if you tell them, it's still an interesting problem.
The first half of the question, which some people (whose names I will protect to my dying breath, but their initials are Willie Lewis) feel is a Job Requirement If You Want To Call Yourself A Developer And Work At Amazon, is actually kinda hard. The question is: how do you go from an arithmetic expression (e.g. in a string) such as "2 + (2)" to an expression tree. We may have an ADJ challenge on this question at some point.
The second half is: let's say this is a 2-person project, and your partner, who we'll call "Willie", is responsible for transforming the string expression into a tree. You get the easy part: you need to decide what classes Willie is to construct the tree with. You can do it in any language, but make sure you pick one, or Willie will hand you assembly language. If he's feeling ornery, it will be for a processor that is no longer manufactured in production.
You'd be amazed at how many candidates boff this one.
I won't give away the answer, but a Standard Bad Solution involves the use of a switch or case statment (or just good old-fashioned cascaded-ifs). A Slightly Better Solution involves using a table of function pointers, and the Probably Best Solution involves using polymorphism. I encourage you to work through it sometime. Fun stuff!
Ironically (as you'll see later), the polymorphic solution is ideal if you want to make an extensible system. If you want to add new functions to your system without having to recompile everything - and in particular, without having to add more and more cases to your Giant 500-Case Case Statement, then you'll want to use polymorphism.
So polymorphism, so far anyway, seems kind of useful. By far the most useful, uh, use, of polymorphism is the polymorphic print statement. If you've programmed in Java, Python, Ruby, or another "real" OO language, then you probably take polymorphic print statements for granted. You tell an object to print itself, and by golly, it does. Each object tells you exactly what you need to know about its internal state. Very useful for debugging, tracing, logging, and maybe even documentation.
If you're using a twisted facade of an OO language like C++ or Perl, with object orientation bolted on like a pair of $2500 rims on a 1978 Subaru Legacy, then you're stuck with using a debugger, or Data::Dumper, or some such. Sucks to be you!
(Rhetorical question: Why did we have to pick C++ and Perl? They're two of the worst languages in the world! You might as well use Pascal and Cobol, for cryin' out loud.)
Incidentally, the polymorphic print statement is the primary reason I've been rather quiet about OCaml lately. OCaml, for reasons I haven't fully grokked yet, but which appear to be along the lines of "criminal insanity of the designers", doesn't provide a polymorphic print statement, so you can't actually print out arbitrary objects to the console for debugging purposes. I hope that this was necessary to achieve OCaml's legendary C++-beating performance, because any other reason would be a face-smashing insult to usability. At least they have a debugger that can step backwards in time. You'll need it.
So! We like polymorphism. Polymorphism is the opposite of micromanaging. You tell objects to do something, without telling them how to do it, and they dutifully comply by spending the day watching Strong Bad clips online. Those silly objects! Gotta love'em.
But polymorphism, like all good protagonists, has a Dark Side. In polymorphism's case, it's not quite as bad as the dark side exhibited by, say, Anakin Skywalker, but it's a dark side nonetheless.
Using polymorphism in your code has an unspoken but very significant requirement: you have to be able to add it in later. At least in static languages like Java and C++, if you add a polymorphic method, you have to recompile the classes for which you implement the method. That means you have to have the source code, and be able to modify it.
There is a certain class of system for which this isn't possible, at least as far as I can tell. That class would be: extensible systems.
Let's say, hypothetically, that you're building a fancy system that allows your end-users to add code. This is a nontrivial task for lots of reasons, including security, thread-safety, and others as well. But these systems exist! For instance, there are online games that allow users to add in their own code, without having access to the original source code. Most multiplayer online games are actually moving in this direction - execs (no pun intended) have realized that users can and do create good content, so the games are opening up their APIs and letting users extend the systems by writing their own monsters, spells, and so on.
Something tells me that Web Services is in a similar boat.
Any time you create a user-extensible system, you need to do about three times as much as work, the extra 2x being work to arrange your internal APIs and classes so that they can be modified by end-users.
Java's Swing is a good example of this. Any time you build an extensible system, you'll run into the Inventor's Paradox, which you can read about elsewhere, but the gist of it is that you can't predict in advance what changes your users will want to make to your system. You can go to any length — even expose every single line of code in your system as its own virtual function — and your users will inevitably run into something that they can't specialize. It's a real pisser, and I don't pretend to have an answer for it. Swing handles it by creating lots of hooks, which makes it a monstrously large API to master.
To make this concrete, let's go back to the online game scenario. Let's say you've done your best to expose APIs and classes for creating and manipulating spells, monsters and other in-game objects. Let's say you've got a big installed base of monsters. I'm sure you can imagine some.
Now let's say one of your users wants to come in and write a little OpinionatedElf monster. This is a contrived example, similar to the Halting Problem in the way it proves its point, but situations like it can happen in practice.
Let's say the OpinionatedElf's sole purpose in life is to proclaim whether it likes other monsters or not. It sits on your shoulder, and whenever you run into, say, an Orc, it screams bloodthirstily: "I hate Orcs!!! Aaaaaargh!!!" (This, incidentally, is how I feel about C++.)
The polymorphic approach to this problem is simple: go through every one of your 150 monsters and add a doesMrOpinionatedElfHateYou() method.
Gosh. That sounds insanely stupid. But it's the true polymorphic approach, right? If you have a bunch of similar objects (in this case, monsters), and they're all supposed to respond differently to some situation, then you add a virtual method to them and implement it differently for each object. Right?
Obviously it doesn't work worth a damn in this case, and even if you could do it (and you can't, since the user writing this little elf has no access to the source code), it would smack of Bad Design. Clearly there's no reason to put such a specific method on every monster object in the game. What if we later decide the OpinionatedElf is a copyright violation, and he has to be removed? You'd have to go back and remove that method from 150 classes.
As far as I know (and I don't claim to be a good designer, just one who would like to know the right answer), the right way to solve this is using runtime typing. The code would look something like this:
public boolean doesElfLikeIt ( Monster mon )
{
if ( mon instanceof Orc ) { return false; }
if ( mon instanceof Elf ) { return true; }
... <repeat 150 times>
}
Admittedly, you could be an OO Freak, and create 150 helper classes for the OpinionatedElf, one per monster. That doesn't really solve the root problem, though, which is that the discriminating behavior is all in the caller, not the callee. That's where it belongs - in the caller, that is.
There are some higher-level languages that solve this a bit more elegantly, and I do stress "a bit". In Ruby, for instance, you can add methods to other classes, even built-in ones, even if you don't have the source code. For instance, you could put the following code into the OpinionatedElf file:
class Orc def doesElfLikeMe; return false; end end class Troll def doesElfLikeMe; return false; end end class ElfMaiden def doesElfLikeMe; return true; end end ...
Ruby actually loads all the classes you specify, if they're not loaded already, and adds your method to each of them. This is a pretty nifty feature, in general.
Here though, I think there are pros and cons to this approach. What's happening is that in Ruby (and most other high-level languages), methods are just entries in a hashtable, one per class, and you're going in and stuffing your entry into the hashtable for each subclass of Monster. The advantages are:
all of the OpinionatedElf code is encapsulated in his file
the code isn't added unless the elf file is loaded
anyone else in the system can ask the target whether the elf likes them or not
The downside is that you need a default behavior if your elf doesn't recognize a monster that's been added since his code was written. If someone adds a Gremlin, your elf will be stuck screaming something like "Gosh, what's THAT?" until you can update his code to include a case for gremlins.
I guess if you could somehow enumerate all the classes in the system, and check if they derive from Monster, then you could do this whole thing in a few lines of code. In Ruby, I bet you can... but only for the already-loaded classes. It doesn't work for classes still sitting on disk! You could solve that, but then there's the network...
But needing a default behavior isn't all that bad. There are worse downsides. Thread-safety is one; it bothers me a lot — I don't think Ruby's semantics for thread-safety are well-defined in this case. Is there a class lock? What does the lock do with threads executing in instances of pre-Elf class? I don't read Japanese well enough to know whether the proof is in the spec or the implementation.
But the real problem, the one that really gets me, is that your code is going in and distributing itself across all the classes in the system. It feels like a violation of encapsulation.
In fact it's even deeper than that. It feels like Bad Design. Here we have a situation in which an observer is making some sort of judgement call, and we're sticking the judgement code into the observee. It's as if I went around to all the employees on the floor and handed them little badges, telling them: "Please hold on to this badge. It says whether I like you or not." It's not the way things work in the real world, and OOP is supposed to model the world.
Well! Now that I've put it that way, polymorphism doesn't seem like so much of a silver bullet anymore. Even in a non-extensible system, if you have some sort of decision to make based on the type of the target, it may not make sense to put the decision into the target.
A more practical, down-to-earth example is authentication. Let me ask you: if you were designing a permissions system, would you design it by having a virtual doYouHaveAccess() method, and have all possible comers implement the method? I.e., would you have the security guard ask everyone if they're allowed in the building?
Absolutely not. You'd have your code do some runtime checks:
public boolean denyEntryToBuilding ( Person p )
{
return ( p.hasNoBadge() ||
p.isSuspiciousLooking() ||
p.hasMachineGun() );
}
But wait - none of those things was overtly a class check. I didn't say "p instanceof MachineGunBearer", for instance. What's up with that?
Well, the "type" of an object is, for all intents and purposes, the union of its class (which is pretty much hardwired, like genetics) and its properties, which might or might not be changed at runtime.
It's a separate essay, but I think this implies that type is best represented via properties rather than classes, because of the inherent inflexibility of classes. But in "traditional" languages like C++ and Java, this makes code sharing a bit harder, because of the lack of support for syntactic delegation. If that didn't make sense, it's OK: I'm on my 3rd glass of wine, and nearing the pass-out point. Let's just say it's the subject of another article.
In the meantime, I hope I've made my main point clear, which is that polymorphism only makes sense when the polymorphic behavior is really a behavior of the target. When it's the behavior of the observer, you need runtime typing.
Well, I hope you've learned something in today's Drunken Blog Entry. I know I have. For one thing, I learned that Google's search engine is actually smart enough to correct "anikin skywalker" to say "Did you mean anakin skywalker?" Those hoity-toity bastards. It's not like they own the copyright.
I also learned that the correct length for a blog entry is exactly 2 glasses of wine. If you go any longer than that, you'll start ranting semi-incoherently. Your typing really goes to hell, too.
See you next week for the next installment of...
Stevey's Drunken Blog Rants(tm)
(Published August 25, 2004)
Comments
> polymorphism only makes sense when the polymorphic behavior
> is really a behavior of the target. When it's the behavior
> of the observer, you need runtime typing.
Is it runtime type-checking that is called for, or does it just look like that because Java overloads "instanceof" to test for type — and interface?
In Objective C, for example, you could use protocols (i.e. "interfaces") to implement the marker interface pattern. Objc Categories (a way of packaging extensions to a pre-existing class) would enable you to pretty cleanly extend the relevant monster classes from the comfort of the Elf interface file. You could then test it like so...
if ([creature conformsToProtocol: @protocol(AnnoysElves)]) { ... }
Perhaps this approach would avoid inadvertently conforming to @protocol(AnnoysMartinFowler).
Posted by: Riley at September 22, 2004 04:55 AM
Yeah, using Objective C protocols and marker interfaces is similar to Ruby's approach (Ruby stole the best stuff from -every- language...). In Ruby you can modify any class; they're always "open", and Ruby's been switching to something they call "duck typing", which is exactly the difference between conformsToProtocol() and instanceof. They call it respond_to?, but it's the same basic idea: they don't care what the overall type of an object is, just whether it responds to a message with the right signature. There's always the chance that it can be mistaken identity, but with reasonably specific method names you can avoid that pretty well.
I'm not sure if it would appease Fowler and friends, though, since it's either violating encapsulation (by mucking with classes at runtime), or polymorphism (by not mucking with them). I don't think they've addressed this situation in the books; maybe we should just ask him about it. :)
Posted by: Steve Yegge at September 22, 2004 05:06 AM