When Polymorphism Fails | Hacker News Reader

When Polymorphism Fails

sites.google.com

44 pointsraju22 comments

"In case you're (somewhat) unfamiliar with OOP terminology, polymorphism is a pretentious name for the concept of late binding."

Actually, they are two related, but different concepts. Polymorphism generally refers to http://en.wikipedia.org/wiki/Subtype_polymorphism but there are other types. In short, it involves virtualizing an interface. Late binding, aka "Dynamic Binding", on the other hand, makes no assumption of an interface and does not necessarily imply polymorphic behavior.

Excellent point there are many types of polymorhism (hehe) ad hoc, subtype etc.

As a functional programmer when I hear polymorphism I default to parametric polymorphism. This guy is not talking about polymorphism at all but instead the limitation of late binding via dyanmic/single dispatch.

     As a functional programmer when I hear polymorphism I 
     default to parametric polymorphism. This guy is not 
     talking about polymorphism at all but instead the 
     limitation of late binding via dyanmic/single dispatch.

It doesn't matter what type of polymorphism you're referring to, all it matters is what polymorphism does ... the ability of a certain piece of code to run with any data types provided they implement some kind of contract.

Late binding / runtime dispatching is giving you an implicit polymorphism that's more powerful that all those types you mentioned since the contract is also implicit.

You are right that Stevey talks about the limitations of single-dispatching. Multimethods are designed precisely for the problem he describes.

Multimethods are very powerful, problem is they come with great runtime penalty and there aren't too many use-cases for multimethods.

Otherwise, because in both Python and Ruby you can override the dispatching mechanism and generate code at runtime, you can add multimethods to them.

For example in Python you can use the "peak.rules" package: http://pypi.python.org/pypi/PEAK-Rules

Then you don't need to add methods to every possible Callee type, you just add a multimethod on (Caller, Callee) + a generic one on (Caller, object) which returns a default for unknown cases.

It's cleaner because you can add that multimethod anywhere (either in the Caller's package or in the Callee's package) and it also doesn't break encapsulation, and without the runtime penalty I would prefer it to a big switch ... simply because you might not have the ability to modify the Caller's package.

In the example with monsters, perhaps the issue is that all the different monster types are classes instead of data. For instance, I would instead implement something like

  class Monster
    attr_reader :type
    def initialize(type, likes = {})
      @type = type
      @likes = likes
    end

    def likes?(x)
      @likes[x.type]
    end
  end

  orc = Monster.new(:orc)
  troll = Monster.new(:troll)
  elf = Monster.new(:elf)
  elf_maiden = Monster.new(:elf_maiden, :elf => true)

  puts troll.likes?(elf)
  puts elf_maiden.likes?(elf)

If you have 150 subclasses, it is a code smell in the first place, and perhaps by addressing the root problem, issues like the one Steve mentions won't occur in the first place.

I believe this solution is somewhat implied, yet not spelled out, in the summary:

> 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.

It is rather unfortunate that the article switches from a self-admitted unsatisfactorily solved monster example into a completely different example.

In more general terms, what OOP is meant for and what it handles perfectly is exposing functionality of an isolated data structure. When, however, it comes to interaction between separate objects OOP poses dilemmas like those described in the post.

As a classical example, when you define a basic API for a graphical object you usually have no doubt on where and how to define draw(), getBoundingRectangle() etc. as long as the methods operate within the object, i.e. use the properties of one isolated object. Doubts arise though when it comes to things like removing a child object from its parent, for example. Should it be parent.removeChild(child) or child.removeFromParent()? Or both? Or perhaps environment.remove(parent, child)?

And Steve's authentication example is probably the most compelling one. How can you trust a polymorphic call to visitor.hasMachineGun()?

So yes: "It's not the way things work in the real world, and OOP is supposed to model the world." The world is not just objects, it's also interaction and interoperability that makes it an interesting place.

The gem of the article was the articulation of "an object's type is the union of its class and properties". That's how it is, I just hadn't seen it in writing before. It also strikes a chord with what I felt bad about in his examples: nothing really helps if your game has 150 monster classes.

You could attack from the outside by putting the method in Elf class and overloading by the parameters:

    public boolean doesElfLikeIt ( Elf mon ) { ... }
    public boolean doesElfLikeIt ( Orc mon ) { ... }
    public boolean doesElfLikeIt ( Monster mon ) { ... } // default

if your language can do that. Otherwise you'll have to do it manually, i.e. threatening little children with switch statements. But classes are amorphic, it's like trying to reshape glass that's once burned. Having a single Monster class and codifying its type mostly in its properties (which themselves may be instances of other classes) seems like a much better way.

This is called the Expression Problem (http://en.wikipedia.org/wiki/Expression_Problem). Once you have a program, you want to be able to extend it in multiple ways: adding new classes or adding new methods to every class. In Haskell this is sometimes solved using attribute grammars. They are very similar to aspect-oriented programming, which is another way to solve the problem.

I have seen both AG's and AOP used. Sometimes it is a very elegant solution (for example, when writing a compiler), but it can also quickly lead to messy code.

> adding new classes or adding new methods to every class

Common Lisp lets you do both. These are not problems with polymorphism, these are problems with brain-damaged implementations of polymorphism.

Agree with pwim that 150 subclasses is way too many. OO Principal Favor Composition over Inheritance easily kicks in here. But even with fewer subclasses we still have to define the likes/dislikes of N monsters with N-1 other monsters. Further, every time a new monster is added, N monsters like/dislike logic has to be updated.

Maybe we are looking at the system/problem from the wrong perspective?

Maybe the likes/dislikes between monsters isn't actually so arbitrary. Perhaps, it is the characteristics of one monster that other monsters don't like or do like. If this is the case (which makes sense as in the real world we judge other things based on characteristics and behavior), then the like/dislike behavior can be encapsulated.

Further, using something like Strategy pattern, you can come up with a set of algorithms that define the likes/dislikes between monsters. That way you can compose that specific behavior of a monster at run-time further reducing your class count.

The Expression Problem strikes again!

There's a guy giving a good lecture on it: http://professor-fish.blogspot.com/2010/08/lecture-series-on... (I think he even has a solution in Haskell)

It seems like half the papers ever written about Haskell contain a solution to this problem... This includes most papers about monads and monad transformers.

> But it's the true polymorphic approach, right?

Wrong. I guess that's the end of this article. You don't add a method to a type in every case some other type wants to know something about it.

  class Creature
    def doesElfLikeMe; false; end

    # or
    def method_missing(*a)
      if a.first.to_s =~ /LikeMe$/
        false
      else
        super
      end
    end
  end

  class Orc < Creature; end
  class ElfMaiden < Creature; def doesElfLikeMe; true; end; end
  # Orc.new.doesElfLikeMe # -> false
  # ElfMaiden.new.doesElfLikeMe # -> true

anyone care to comment on whether multiple dispatch or multimethods (e.g., in CLOS) solves this problem more elegantly?

Indeed. Good old Steve misses the point again...

yes. that is quite simply even with ruby, the wrong way to tackle that problem.

The classic OOP solution to that class of the problem is the visitor pattern, so yes, multiple dispatch to the rescue.

Actually, the visitor pattern doesn't actually solve anything - it just moves the problem around. At best, it makes your code more complicated in return for getting a compiler error when you forget to implement something.

Example: if you have 150 monsters then you would need a MonsterVisitor with 150 visit() methods. Now when you add a new monster, you have to add another visit() method and perhaps implement it in each visitor (unless you implement a default instead). And this doesn't work at all if you load new monsters at runtime, unless they always get the default behavior.

There's little advantage over switch statements with defaults so long as you have a way of remembering where all the switch statements are when you need to update something.

Uh, no. The pattern has trade offs, that doesn't make it useless, it most certainly solves problems.

I only skimmed the article but it looks like he is more or less talking about the expression problem brought up by Philip Wadler some time ago. Definitely multiple dispatch can solve this problem but if we stick to the original definition of the problem it breaks on the requirement for static type safety (which probably doesn't matter to you heh).

GADTs in haskell and I think Scala can solve this cleanly. Active Patterns in F# may also provide a clean solution for the full problem.

Yes, you can solve it quite simply with an active pattern, or type union. The fundamental problem with the problem is that it's a relational problem and polymorphism largely solves hierarchical problems. This type of problem also solves easily in prolog. The solution to the problem in java is to create some kind of relation class that abstracts the state of the relationship to between individuals/groups.

Reply on news.ycombinator.com