External Polymorphism

Any mechanism for implementing polymorphism that is external to the definition of the object displaying polymorphic behavior. Switch statements based on a type code are probably the simplest of such mechanisms.

There are other, more ingenious mechanisms, available as well:

The paper "External Polymorphism -- An object structural pattern for transparently extending C++ concrete data types" by Cleeland, Schmidt, and Harrison cleverly combines dynamic binding and the template mechanism. www.cs.wustl.edu

The Generic Function (which is used by the Translator Pattern) uses a hashtable with class names as keys and corresponding functions (see Function Object Pattern) as values.

Multi Methods -- methods that are polymorphic on all of their arguments rather than one. Implemented in languages such as Common Lisp Object System, Dylan Language, Cecil Language, and Nice Language. These are useful for External Polymorphism even if having a single (polymorphic) argument, as they can be implemented without changing the underyling class.


It should be said that, while External Polymorphism is often necessary (particularly in languages with unsubclassable features) it should be avoided wherever possible. It breaks the encapsulation inherent in OOP. Better to rely on the public attributes of an object than it's type - even if that means defining enums to describe the type's features.

For example, ground-vehicle is subclassed to Car and Bus. Class Ferry checks whether type is Car or Bus to determine where to store Bus, because Bus is larger. However, a Minibus, subclassed from Bus, can fit in the same space as a Car - so a larger Bus slot is wasted. If attributes were used, this mistake would have been avoided.

A common multimethod example is Rock Paper Scissors. By using extrinsic polymorphism, you require that subclasses of Scissors always be treated as Scissors, even if they have all of the attributes and features of Rock. Rather, it would make more sense to define an enum "Rock, Paper, Scissors, Other" and simply have each class return an entry from that on request. Thus, it would be painfully obvious to subclassers how the behaviour worked, rather than having inscrutable information hidden in an externally dispatched system.

In other words: only use External Polymorphism if you are forced to - usually if you have no control over the design of the classes you work with.


A polymorphic method on an object can be thought of as a sort of super function. That is, it is one conceptual function that has several implementations that are customized according to the dynamic type of the object they are bound to. As long as the different implementations support Liskov Substitution it appears to clients as if there is only one function. Implementing this conceptual function using Internal Polymorphism causes the custom implementations to be cohesive to the types that specialize them so that when a new type is added it contains its own specialization of each polymorphic function it is associated with. External Polymorphism causes the custom implementations to be decoupled from the types upon which they are specialized and allows them to be cohesive to some other location. When a new function is added it contains its own specialization for each type it is associated with. So instead of messages being polymorphic with respect to the objects that they are sent to, we have functions that are polymorphic with respect to the object(s) that are passed to them as parameters.

In the imperative sentence: "Joey, hit that ball!", "Joey" is an active noun and "ball" is passive. Internal Polymorphism allows objects in an active role to vary their behavior based on their type. External Polymorphism allows the behavior of objects in a passive role to vary based on their type.

External Polymorphism makes it difficult to add new types because when a new type is added every relevant function that is implemented with External Polymorphism must be found and specialized for the new type. On the other hand, Internal Polymorphism makes it difficult to add new functions because every implementing type must be updated with a new function definition.

Actually, External Polymorphism makes is hard to add new types if functions need to be defined in one block, like in Functional Programming Languages with functions defined by Pattern Matching. It poses no problem if each case of a function (method) can be defined independently, like with Multi Methods and Predicate Dispatching.


Where can the "External Polymorphism" paper be found? -- Ted Neward

It's also available in MoreCPlusPlusGems starting on page 417. -- Chris Cleeland


Does anyone have an idea how to implement/fake External Polymorphism in Java? I'm tired of instanceof. -- Michael Schuerig

You could use a dialect of Java that supports Multi Methods. See for instance the Nice Language. This solution requires that you use another compiler than javac (but java bytecodes are generated). On the other hand, the advantage is that the compiler, understanding what your are doing, can provide you with a nicer syntax, meaningful error messages, and can perform more static checking.

S[from External Polymorphism] Does anyone have an idea how to implement/fake External Polymorphism in Java? I'm tired of instanceof. --Michael Schuerig

The key pieces would be a hash table and a static method. Since the static method will use it, the hash table should probably be static too. The static method takes an Object parameter and implements polymorphism by calling getClass() on the Object, using the resulting class as a key into the hash table to retrieve the implementation code and then delegating the call to that code.

The implementation code should probably be an instance of an inner class that implements an interface with a method that takes an Object parameter, converts it to it's proper type and then performs the desired operation. -- Phil Goodwin

Except there's no loop hash table lookups are much faster than the linear time it takes to loop through an array - at least if you have more than a couple of items. -- pg

But hash tables have the drawback that they don't take subtyping into account. -- ms

Hmm, yes, that's interesting, you'd either have to fill the table with all the types you were going to use (often workable) or implement a best-fit algorithm in order to determine which code to execute when an exact match can't be found. -- pg

You'd have to reimplement Multiple Dispatch. Actually, someone has already done this. See Method Thread. -- ms

I don't see the relationship. I mean, you can implement Multiple Dispatch as part of Generic Function, that would be very useful, but I don't see why you'd have to. You just need a mechanism to search for entries that match one of the antecedents of the type in question. - pg

But that is single dispatch, and in a language like Java you now have a method that is associated with two classes; it dispatches on both. -- Graham Hughes

Polymorphism is where you have a method that is associated with more than one class and dispatches at runtime based on dynamic type information. Internal Polymorphism is when that method is owned by the classes that it can dispatch to - the classes elaborate the dispatch mechanism by defining which code will finally implement the call. External Polymorphism is when some agent other than the classes owns the right to elaborate the dispatch mechanism.

Single Dispatch is a kind of Polymorphism where the dispatch mechanism works against a single dynamic type. I don't know of any Internal Polymorphism implementation that doesn't use Single Dispatch. Multiple Dispatch is where more than one dynamic type is used to make the dispatch decision. External Polymorphism allows and even seems to inspire Multiple Dispatch as well as dispatch based on information other than type information.

So if you just replace Internal Polymorphism with External Polymorphism you'll probably end up with Single Dispatch, but you will probably find yourself wanting to extend that to Multiple Dispatch later. -- Phil Goodwin

I realize now why Matz decided that Ruby would have Monkey Patching--it's a great way to implement External Polymorphism without actually having to use multimethods. (Switched To Ruby From Python -- well, more accurately, Still Love Python Trying Out Ruby.)


So is the Unix "sort" command a good example of External Polymorphism? -- Anonymous Coward


I am surprised the reflection has not entered this conversation. Here is a good example of how one can get External Polymorphism through reflection.

public class D''''''oubleDispatchReflector { // Methods public D''''''oubleDispatchReflector(); public D''''''oubleDispatchReflector(object subject, string methodName); public M''''''ethodInfo D''''''ispatchTo(object[] args); public M''''''ethodInfo D''''''ispatchTo(object arg); public M''''''ethodInfo D''''''ispatchTo(object subject, string methodName, object[] args); public M''''''ethodInfo D''''''ispatchTo(object subject, string methodName, object arg);

// Properties public string M''''''ethodName { get; set; } public object Subject { get; set; }

// Fields private string _MethodName; private object _Subject; }

public M''''''ethodInfo D''''''ispatchTo(object subject, string methodName, object[] args) { Type[] typeArray1 = new Type[args.Length]; int num2 = args.Length - 1; for (int num1 = 0; num1 <= num2; num1++) { typeArray1[num1] = args[num1].G''''''etType(); } M''''''ethodInfo info2 = subject.G''''''etType().G''''''etMethod(methodName, typeArray1); if (info2 == null) { throw new I''''''nvalidOperationException("There is no method for that signature."); } return info2; }

Subject is the Object that contains all implementations that would have be available polymorphically. MethodName is the name of the method that would have been available polymorphically.

Now first lets just focus on one arg. The arg would be the object that you are externally providing polymorphism for.

An example is base class Exception. I wish MS and Sun had implemented the Visitor Pattern on their Exception classes. But they didn't, so what is a guy to do. External Polymorphism to the rescue. I can provide a class ExceptionHandler as the Subject to DoubleDispatchReflector.

public class ExceptionHandler

{

// Methods public void Handle(Exception exception); public void Handle(IOException exception);

}

Now I can

try

{

throw new IOException("This is a test.");

} catch (Exception ex)

{

D''''''oubleDispatchReflector E''''''xtPoly = new D''''''oubleDispatchReflector(new E''''''xceptionHandler, "Handle") E''''''xtPoly.D''''''ispatchTo(ex)

}

Just to close the loop I wanted to do something like

try

{

throw new IOException("This is a test.");

} catch (Exception ex)

{

ex.Accept(new E''''''xceptionHandler)

}

So let's take it up a notch. Remember that DispatchTo accepts multiple arguments or an array of objects. Now this is where I start to get out of my experience. From my perspective some pretty wild things can be do with this. I come from a .NET background (VB, C#) so this so not something you normally see done. I am nervous to use it much as I have no wisdom to temper my application of the tool.

Have Fun -- Jay Flowers

See original on c2.com