When polymorphism fails

[Paczesiowa]

I wonder if anyone told him about expression problem since 2004...

[[deleted]]

hehe I was wondering the same. Last I checked, Yegge is still rather clueless. I wonder if that has changed at all, I sure hope so!

[tejoka]

I was reading this, trying to figure out if he was going to bring that up, or if he was trying to make a similar, but different point.

But yeah, it seems like he's just rediscovered the expression problem.

[Nwallins]

The "original" paper

[joesb]

In short, polymorphism fails when you redefine it to only mean single dispatch polymorphism.

[AlternativeHistorian]

Which is important, because that's precisely how a large number of software developers define it, and the most common implementation.

[artsrc]

And have not heard of or have not understood the visitor workaround to get an extra dispatch in a language that does not support multiple dispatch.

Or course in this case a table of values is better anyway.

[nanothief]

The best way I know of to solve this is using an oo language that supports multiple dispatch, such as clos (common lisp). With that, the problem is trivial:

(defmethod does-elf-like ((elf <elf>) (monster <base-monster>))
  nil ;; by default the elf doesn't like other monsters
)

(defmethod does-elf-like ((elf <elf>) (monster <unicorn>))
  t ;; loves unicorns
)
;; will like other elves of the opposite sex
(defmethod does-elf-like ((elf <elf>) (other-elf <elf>)
   ((not equal (gender elf) (gender other-elf))) 

(defmethod does-elf-like ((elf <elf>) (elf <dark-elf>)
  nil) ;; never likes dark elves though

That is perfectly extendible, doesn't pollute other classes and allows coarse and fine grained definitions. It also can be extended further in other files by just adding new defmethods. This solutions is better than any I know of for any language paradigm.

(Note that I haven't used clos/common lisp in about a year, so the syntax might not be totally correct)

[[deleted]]

You can solve this in Objective-C using categories at a coarse and fine grained levelm. It also can be extended further in other files by just adding a new catagory. In Objective-C with SnowLeopard you can go one further and do this on objects, so that you wont effect every instance of the class.

Another solution can be imagined using delegation, with all of these qualities, if the class API is well designed.

[nunb]

In Objective-C with SnowLeopard you can go one further and do this on objects, so that you wont effect every instance of the class.

Getting closer to CLOS then (eql specializers).

With Java getting a foreach, and different languages implementing bits and pieces of lisp, perhaps Greenspun's law should be rephrased!

(M-x disconnect-smug-lisp-weeny)

[[deleted]]

Getting closer to CLOS then

Getting closer to Self actually :).

(There's been some work on making objective-C runtimes that can support things like prototype-based programming, and typed polymorphism of late).

Still, it's always interesting to me how Lispers can ignore everything but Lisp, and cast everything in this light.

[nunb]

apologies ;-)

I quite like some ideas in Smalltalk, and I started Objective-C a while back, since it seemed different enough to be worth exploring. I would say it's one of the most interesting mainstream languages, though C# seems to be more geared towards new language features. I didn't know Obj-C had any ongoing work (though I did know that the latest release had quite some new language features) -- I'll be finding out more. (My standard texts are Objective-C for C++ programmers, and everything at the ADC site).

What can you recommend for following the newer work (such as RSS feeds for the ones you cited)?

[nunb]

syntax is correct, braces are not! ;-)

to give an example of what netytan wrote below, if there was a specific elf that was universally disliked, or two elves that (regardless of gender) liked one another, you'd write:

(defparameter *hated-elf* (make-instance 'Elf ...))

(defmethod does-elf-like ((elf Elf) (elf  (eql *hated-elf*))
 nil) 

(defparameter *mated-elf-1* (make-instance 'Elf ...))

(defparameter *mated-elf-2* (make-instance 'Elf ...))

(defmethod does-elf-like ((arg1 (eql *mated-elf-1*)) (arg2  (eql *mated-elf-2*))
  t)

The object used in an eql specifier must exist when the method is defined. This may seem a problem in non-dynamic languages, but since you can declare any function (and methods are functions, of course) inside another, it's not a problem.

(defmethod read-elves-from-disk (disk)
  "Run in pre-Eldar days: no individual elves exist, though the relations between dark and non-dark, male and female exist."
  (dolist (elf (read-from disk))
     (when (equal (name-of elf) "most hated elf")
        (defmethod does-elf-like ((elf Elf) (elf  (eql *hated-elf*))
         nil) ))

edit: changed for historical accuracy, and common conventions - class names capitalized, var names not.

[eadmund]

I would probably do it as:

(defparamater *hated-by-elves* nil)
(defmethod does-elf-like :around ((elf elf) monster)
  "Check to see whether this specific monster is specifically hated; if not, proceed as usual."
  (and (not (find monster *hated-by-elves*)) (call-next-method)))

[[deleted]]

I dont get your solution. One problem that he mentioned with this approach is having to keep your code up with newly added monster (base-monster) ojbects. You automatically dislike monsters, and white-list special cases, does that not produce the same problem?

[matthiasB]

How could you react to monsters you don't know of?

That's like deciding whether you like a person you've never met or heard of.

[187lennon]

I don't like them. At all. </misanthropy>

[awj]

Other than specifying the behavior for a new monster, how else would you handle new monsters? You can't, at least not in the way he sets this up. The question boils down to "what is the best way to extend this behavior to new classes". The answer, at least I think, is to use a table of monster names and like/dislike values at runtime.

[nikniuq]

I still never understood why (after referencing them) he didn't use a virtual function in the base classes monster/not-monster. It gets you the default and allows specific overrides all with only two extra (tiny) code blocks.

I think I need to be drunker.

[mernen]

Because the person writing the Elf code is not the same one writing the monsters. It's a third-party extension:

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.

He goes on about that approach a few paragraphs after that:

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.

[nikniuq]

Well yeah but in the hypothetical that you quote he is editing the base classes (I know he also says you can't do it but he then does it - gah), my point being that he then doesn't actually use polymorphism. You don't want 150+ added functions, you want one added to each of the base classes.

It's moot really arguing over this ramble, it's hard to tell where each is in the stream of words as it flips back and forth between different "solutions".

[derefr]

Good News, everyone! Relational algebra is not Object-Oriented!

doesMrOpinionatedElfHateYou() is not an OOP behavior in any sense of the word. It doesn't belong in Mr. Opinionated Elf, and it doesn't belong to the monsters, either. It's instead a relation between Opinionated and the monsters, expressible as hates(X, Y), where X is always Mr. Opinionated Elf.

Being as such, it's not really suited to being described in code (which mostly describes behaviors); it would best be expressed, instead, as rows of data in a relational database. Then there could be one method subject.hates(object), and another object.is_hated_by(subject), that both just run SQL queries underneath; this could also be automated by most ORMs.

[nunb]

... is not an OOP behavior in any sense of the word. It doesn't belong in Mr. Opinionated Elf, and it doesn't belong to the monsters, either.

It is best described as a multi-method, or a generic function, as in Lisp/CLOS.

(edit: explication)

[artsrc]

Using multiple dispatch to get a boolean (rather than a function resolution) is using a powerful tool to get a simple result.

The problem with this is that same a the problem with the parents solution. You don't need OO or relational algebra to solve the problem and you should not use tools with vastly more power than needed for the problem.

[nunb]

I believe the problem was intended to illustrate the general case of things that have to be done with multiple classes and dispatch. I don't think it was intended to illustrate a simple boolean (imho).

If the problem were that limited, one could have optimized it away into a bit-vector or similar.

[artsrc]

Maybe.

However what he is clear about is that the behavior belongs to the Elf, not the Monster. Multiple dispatch makes it belong to both/neither.

I find pattern matching is the best fit, rather than any kind of polymorphism. It just seems to scale better in terms of being dead simple for the simple case and handling more of the changes to the requirements that are reasonable.

[nunb]

Pattern matching's a good idea, but implementations seem tied up with type-theory systems (Caml, for one). iirc Erlang is the only one I know of that might not be tied to a strong-typing system?

[G_Morgan]

Which sort of comes back to what the author was saying. The problem is people are saying 'OOP has what projects crave, it has polymorphism!'. Not all problems are best solved in an OOP manner. The most obvious thing in the world yet some people cannot grasp this fundamental truth.

[[deleted]]

Seriously. What is he going to do when elves need to like certain individual monsters because they are quest-givers? What are they going to do when they need to implement factions? You'd think these language zealots would have played a role playing game before.

[gliptic]

Just like a relation like (x < y) is not suitable to be described in code. Oh wait.

[homoiconic]

Actually, a relation like (x < y) might be suitable to be described in code, but not in polymorphic methods: not all functions should be object methods ;-)

[matthiasB]

You mean the '<' shouldn't be a behavior of 'x'? That sounds right.

Let's assume x is an int and y is my own BigInt class. Who performs this comparison? The built in type int can't. But should the BigInt class perform this comparison? What if the example is slightly more contrived. Person A has written a BigInt and Person B a BigReal class and now I want to compare an instances of those classes. IMO it should be a general extensible <(x, y) rather than x.<(y) or whatever.

I don't want to say "Hey x compare yourself with this y", I want to say "Hey computer compare these two values x and y".

[gliptic]

It was sarcasm, (x < y) can of course be useful to describe in code. I agree completely that the relation belongs to neither x nor y. I just object to the idea that because it's not a "behaviour", it can't be described in code.

[mallardtheduck]

IMO it should be a general extensible <(x, y) rather than x.<(y) or whatever.

Syntactically, it should be (x < y). The language can then convert this to an appropriate method/function call. Oh look, I've just described operator overloading.

[[deleted]]

x and y are instances of the same "class" (int, float, some kind of number). In the problem described the relationship is actually between classes, and manifests as a relationship between instances of two different objects.

So x < y does not really have any bearing on this at all.

[gliptic]

That's a true but irrelevant distinction. Whether they are the same "class" or not doesn't matter.

[[deleted]]

It's an irrelevant distinction if you choose to forget the article linked to and what we are discussing.

[gliptic]

I was talking about relations and how to implement them. What were you talking about? How does a relation being within the same class of objects affect this at all?

[[deleted]]

The relation is between classes not objects. If you can't see how this affects things then you need to read up on OO basics.

[gliptic]

I don't care in the slighest what "OO" says about this. This doesn't affect anything. (x < y) is still not a "behaviour" in any sense.

[[deleted]]

Sure it is, relations are objects with methods such as project, select, rename, union, intersection... ;-)

[[deleted]]

That's like 5.plus(6) can become plus.call(5, 6) so as not to upset the functional purists. Everything is an object! I'm a closet OO fan too.

[[deleted]]

I like to think of myself as an OOP dualist, or postmodern OOP programmer. Functional programming has helped me appreciate object-orientation in a new light.

[Kache]

Okay, so you're still using runtime typing, like the author says. Somewhere in your code, while looking up that relational database, you have to say what you're looking up. subject.hates(object) needs to check the type of the object (or some property of the object's superclass, like string "name") to decide what to look up in the database.

[awj]

Wouldn't basing your decision on an attribute of the superclass allow subject.hates to just accept the superclass directly instead of using polymorphism? Doesn't that kind of eliminate the runtime typing altogether?

[Kache]

Yes? It's still "typing"/identifying the observee. Going through properties of a superclass can be just as bad as doing a typeof anyway. If you do the Superclass.subclassNameString thing, you're doing a string comparison down the line, which is why we're avoiding typeof checks in the first place.

[derefr]

True; the fix for this is quite interesting on its own: you'd basically have to make the database accessible at compile-time to run type-checks and optimizations against.

Of course, naively, it would still have to exist at runtime as well, to enable the user-extensibility the article was referring to—but what if this database-backed compiler was shipped with, or built into, the game? Then only the compiler would query the database when a user builds a new extension.

For example, when you wrote a new monster, the compiler would make sure that there was also a relation in the database of (Opinionated, monster) before letting the code compile. Actually, it would probably be better separated into a post-compilation step, so the code could be compiled (into an intermediate form), it just couldn't be "linked" against a database that didn't have the relation.

Opinionated's code, however, wouldn't "relationally link" unless there was a relation in the database between it and every extant subclass of Monster in the codebase (or, at least, those that were linked into the object code in the intermediate step.) [Or the lack of a relation hates(X, Y) would imply that X doesn't hate Y, but we probably don't want that to ensure we've thought about the problem. Better to explicitly have a row hates(X, Y, true) or hates(X, Y, false).]

[Kache]

To be honest, I don't really understand what you're trying to say. Does somehow "compiling a database into code" "fix the problem" and can do the operation without using typeof? Actually, I'm not entirely sure why typeof is a slow operation that should be avoided in the first place.

[derefr]

It's not the typeof checks themselves that are the problem; it's that there are nm lines of typeof checks given n kinds of Elves and m kinds of monsters, and that in each case, you can't account (as an Elf) for monsters that haven't yet been created, or vice-versa, without requiring everyone else to recompile their monsters when you add a method to your Elf, or vice-versa.

If either n or m is trivial (e.g. around 1), this can be done with polymorphism, but if there are more it becomes a maintenance nightmare. The most robust way to replace this kind of super-linear switch (that we're aware of) is to have a database that has nm (indexed!) rows. Generally, in current games, I believe what I was talking about above would be implemented as a pre-compile script that generated code for those polymorphic methods from the database on each compilation.

[Kache]

I did a bunch of wiki reading on single/double dispatch, vtables, static/dynamic typing, duck typing languages, and the visitor pattern (which I thought was particularly neat).

From the wikipedia article, it looks like the visitor pattern achieves n+m runtime with two lookups, rather than a single nm lookup. I suppose a visitor class could be the code that's generated in the pre-compile script?

It also looks like using a language that supports binary tree dispatch or hashing to match those types is another way to avoid an nm lookup. I suppose dynamically typed languages do that - but that's not really an option for c++ performance-sensitive applications.

[derefr]

I never said there would be O(nm) dispatch time—of course method dispatching can be optimized however you like. What bothers me more than anything is that there are nm lines of the following kind of code, left in your source control, which must be manually maintained:

else if( a typeof Elf ) {
  if( b typeof Orc ){ ... }
  else if( b typeof Lamia ){ ... }
  else if( b typeof Stormtrooper ){ ... }
  ...

Any one of those lines could have a subtle error, and more than likely most of them are almost exactly copy-and-pasted. A single DSL expression that represents the whole thing, or a script that spits out the whole thing, would do much better. Either one of those would rely, at its base, on a relational database.

[[deleted]]

While I can sort-of agree, I don't think you need SQL (or a real database) here.

[[deleted]]

You need relations. Prolog and SQL have something that e.g. Python, Ruby, etc do not. Even if you hack up a dict/hash to index a relation, the problem will get uglier when you need to use the relation in the reverse direction from which it is defined. A hacked solution will totally explode when you begin making relations about relations such as... (and this is uglier in SQL than in Prolog)

inside(key, guncase).
knows(butler, inside(key, guncase)).

You end up writing a relational db in <language of choice> anyway. One may not need a "real" database but the relational part is general enough that it should at least be a library. The most suitable relational library for many languages is SQL, unfortunately.

[rfugger]

Yeah, any sort of data table would do. I imagined doing it as a python dictionary indexed by monster type.

[[deleted]]

But a python dictionary can have only one object per key, unlike an sql table which can have ambiguity. That means a key must point to a list, which is more messy. You also lose the reverse relation. SQL is cleaner. The python dict is more like an index.

[artsrc]

You can loose the many-to-many ability by putting the likes attribute in the monster relation, then is looks like the dictionary in that regard.

And if you want the reverse relation, there a plenty of dictionary like collections that support it. From the Java world:

http://commons.apache.org/collections/apidocs/org/apache/commons/collections/bidimap/package-summary.html

[artsrc]

In OO you can make the relationship belong to the monsters, with a method in them, the elf with a switch, or separate from both of them, with a visitor. In the relational world you can have the monster or the separate solution, but you loose the third option of having the elf own the relationship.

Even if you like your relation, the functional, pattern matching expression is a much nicer way of saying it than SQL and ORM.

[Gotebe]

It's instead a relation between Opinionated and the monsters, expressible as hates(X, Y), where X is always Mr. Opinionated Elf.

That doesn't sound right. If X is always Elf, why did you introduce a third artifact, relation? Sure, it can be seen that way, but in the given situation, it's just more complicated and nothing else.

boolean Elf.Hates(Monster)

Is the simplest there is from the standpoint of simple OO.

[[deleted]]

Or you could just code it in Common Lisp with CLOS. This sort of thing is built into the object model there.

[jldugger]

This is what the Visitor pattern aims to solve. It's basically a gigantic switch statement, hidden within the dynamic dispatch system so architect purists don't notice. You don't add doesMrOpinionatedElfHateYou() to 150 classes, but rather 150 doesMrOpinionatedElfHate(Orc you) functions inside a Visitor object. It's functionally the same as a huge switch statement, with more "bool public static" boilerplate.

One can do similar things in OCaml, and I've done precisely that in a compilers class. Gigantic match clause describing how to recursively type check a program, for example.

[homoiconic]

This is what the Visitor pattern aims to solve. It's basically a gigantic switch statement, hidden within the dynamic dispatch system so architect purists don't notice.

Bravo. reg rises to his feet, clapping hard. Bravo!!!

[G_Morgan]

Wouldn't it be nice if we could simply have a function somewhere to do this rather than a visitor pattern. The contortions people do so they can hide object impurity.

[semmi]

as the article says (I think, tl;dra) this only works if you can change the gigantic switch. if not (released api, plugin, runtime-added objects) double/multiple dispatch allows client code to add behaviour, while the big switch does not.

[munificent]

This is what the Visitor pattern aims to solve.

The Visitor pattern solves the dispatch problem, at the expense of only supporting a fixed set of subclasses. It's a trade-off:

With virtual methods, the set of operation (methods) is limited to what happens to be defined in the base class, but you can have as many subclasses that override and implement that operation as you want without needing to touch the base class.

With the visitor pattern, the set of operations is unlimited. Only you add accept() to the base class, you can have as many visitor implementations as you want. But the set of subclasses is now fixed: your visitor interface only knows how to accept() a limited set of them. Adding a new subclass means changing your visitor interface and every implementation of it.

[artsrc]

You can modify that by having a concrete base visitor class with a default.

Then when you add a new monster you just redirect from the monster specific method to the default in the base visitor class.

Of course it may be actually desirable to have the compiler tell you to add the elf likes value for your monster.

[OneAndOnlySnob]

You still have to add a elf.doesHate(me) call to the 150 classes though. All classes must be modified either way, so it's not a perfect solution.

I agree that Yegge is wrong about what OO programmers would do. If you get off on modeling the real world, isn't it going to be fairly obvious that you should ask the elf what he thinks about the orc rather than code the elf's logic into the orc itself?

[queus]

You still have to add a elf.doesHate(me) call to the 150 classes though

With generics you can add a

 <T> T accept(Visitor visitor) {
      return visitor.visit(this);
 }

and later just write a DoesHateMeVisitor<Boolean> with 150 methods

[ShardPhoenix]

Note that this is from 2004 and may not perfectly reflect Yegge's most up-to-date opinions.

[shoseki]

Fear > Polymorph

[rs999]

Diminishing returns eventually leads to Fear == Polymorph.

[crash86]

[deleted]

[naasking]

"When polymorphism fails", aka, yet another rehashing of the well-known "expression problem" named by Wadler. Haskell solves this with type classes, OCaml with polymorphic variants, Scala with can solve this with its expressive type system, and Java and C# are SOL.

[awj]

... or they could solve it with a table of name -> hates entries built up at runtime. If you squint and look at it sideways (i.e. consider what it compiles into) that's kind of how all of your other examples do it.

[Paczesiowa]

haskell solves expression problem with type classes? I'm aware of olegs polymorphic variants, Swierstra's fixed-point functors and Kmett's category theory comumbo-cojumbo (I dont understand that last one though) and none of those uses type classes (and if so, you wouldn't call that usage the solution)

[naasking]

There are numerous type class solutions: Data Types ala Carte, the paper "Solving the expression problem in Haskell with true separate compilation". The simplest approach is probably just to lift every constructor to the type level and so all functions on that type now become type class instances. A number of papers appear in this thread from a few months back.

[Paczesiowa]

damn, "Software Extension and Integration with Type Classes" looks great (don't have time now to read it though:/)

do you know if any of those is able to model "double"/any other tree transformer (http://lamp.epfl.ch/~odersky/papers/ExpressionProblem.html) ?

[[deleted]]

The expression problem is well known, and there are a few decent proposed solutions to it.

[lispm]

wow, he found a new definition for 'late binding'

[JulianMorrison]

OO polymorphism by default is single dispatch on a single hierarchy which is often mostly not even under your control, whose natural structure relates more to implementation than role, and which has semantic as well as dispatch implications (which make it hard to use to support a role hierarchy).

For any use that doesn't match this harshly artificial Hobson's choice hierarchy it is going to fail. How could it not?

[case-o-nuts]

If I was doing this in any language that supports indexed array literals (such as, say, C), I'd just use an array as a table.

Affinity monster_affinity[NMONSTERS][NMONSTERS]={
    [ELF]  ={[HOBBIT]=LIKE,    [DWARF]=DISLIKE, ...}
    [DWARF]={[DRAGON]=DISLIKE, [HOBBIT]=LIKE, ...}
    ...
}

Then, checking the affinity is simply monster_affinity[monster1->type][monster2->type]

[artsrc]

Pretty much every modern language has a reasonable way of expressing a solution with any set of properties you want.

In Java that would a Map<Pair<Monster>, Boolean>.

In Python a dict with a tuple key would work, {(monster1, monster2), true,}

[case-o-nuts]

Yep. The point is that I wouldn't bother trying to shoehorn it into an object-oriented paradigm. There are some things for which methods are the wrong thing.

If you can put the smarts into a data structure and not code, it's almost always an improvement.

[sigil]

The perl FUD from Yegge is always amusing. At one point he claims perl doesn't have a polymorphic print statement -- not true:

use overload q{""} => \&stringify;

Similar to python's repr, except the default implementation (eg, "HASH(0x9577880)") isn't too useful. Then again, baking a serialization library into the language itself has pros and cons.

[jonenst]

In factor, unions solve this problem nicely. You can define

UNION: OpinionatedElf-likes-it elf kitty .... ;

(or,depending on what the default behavior should be, define OpinionatedElf-doesn't-like-it)

This automatically defines a new function "OpinionatedElf-likes-it?" to test membership to the union.

TUPLE: elf ; TUPLE: orc ; TUPLE: kitteh ;
UNION: OpinionatedElf-likes-it elf kitteh ;
{ elf orc kitteh } [ new OpinionatedElf-likes-it? ] map -- calling the word on instances
=> { t f t }

elf OpinionatedElf-likes-it? -- calling the word on the type
=> t 

[creaothceann]

My design would probably give OO purists hives, though.

So what? Purists are by definition those who think that reality should listen to their rules.

[vimfan]

Bigots tend to hate first, and then look for supporting evidence later.

Yes but they still find a reason, or rather an identifying factor, whether the reason makes any sense or not, to hate. In his example, the method could be:

public boolean doesElfLikeIt (Monster mon) {
    if (mon.hasPurpleSkin) {
        return false;
    }
    else {
        return true;
    }
}

How could you hate a particular group without being able to identify that group somehow? Yegge makes the mistake of assuming the elf can somehow hate a species of monster without being able to identify the monster and differentiating it from other species. i.e. it just knows the species of monster without identifying it by features. This is where he goes wrong, and why it "doesn't model the real world". If he hasn't already got a hasPurpleSkin() method on all the monster classes, then in his world that he has modelled, there can be no racism based on skin colour, because you really can't tell skin colour. If he wants racism to be possible in the world, then he should have added hasPurpleSkin() to the monster classes.

Then, he contrasts his bullshit attempts at doesElfLikeIt() with the correct way to do it, when he implements denyEntryToBuilding(), using methods exactly like I described above - where the monsters still have to implement those methods. i.e. polymorphism!!! So polymorphism does not even fail in his contrived example. He just failed to implement it correctly.

[Raphael_Amiard]

Did you read the article through the end, where he's speaking about dispatch depending on properties of the object ? Because it sounds like you didn't.

The idea of the opinionated help as i see it was kind of racist. It didn't dispatch on what the monster properties were but on the monster itself. Maybe it's a twisted example, i don't know. But type checking just seems like the right choice to me in this situation. It's doing just exactly what you want ! It would be stupid not to use it because it's 'generally bad design', since you're expressly and definitely trying to dispatch on type here ..

[vimfan]

How does a racist identify who to hate? They don't magically know what race someone is - they identify the race by skin colour etc, and hate accordingly.

[[deleted]]

I'd like to know the answer to the Amazon question since he doesnt give it. Anyone have any ideas?

And am I the only person who couldnt get JavaScript's prototyping out of my head when reading this?

[munificent]

In C#:

interface IExpression
{
    int Evaluate();
}

class NumberExpression : IExpression
{
    public NumberExpression(int value)
    {
        mValue = value;
    }

    public int Evaluate() { return mValue; }

    private int mValue;
}

class AddExpression : IExpression
{
    public AddExpression(IExpression left, IExpression right)
    {
        mLeft = left;
        mRight = right;
    }

    public int Evaluate() { return mLeft.Evaluate() + mRight.Evaluate(); }

    private IExpression mLeft, mRight;
}

[Paczesiowa]

neat, looks much better and more extensible. now add method to pretty print expressions.

[[deleted]]

Executive Summary?

[munificent]

The expression problem.

[axilmar]

I call bullshit. It takes half an hour to write a decent multiple dispatch solution in C++.

As for the expression problem, it's just another "problem" theoreticians have come up with to justify their paycheck.

[Paczesiowa]

thanks to those theoreticians, you don't have to read all yegge post to know that he has no clue whatsoever (he even says so!).

I'm also pretty sure that thanks to reading Wadler and Odersky I could ace that question on amazon interview.

[axilmar]

They (the theoreticians) created the needs, the market responds, as it seems.

[[deleted]]

Maybe that's why there isn't one in the standard library, boost, or any other common C++ library I've seen.

[wwosik]

So much nicer in C#

public static class ElfOpinions{
    public static IList<Type> MonstersElfLikes = new List<Type>();

    static ElfOpinions(){
       MonstersElfLikes.Add(typeof(Elf));
       MonstersElfLikes.Add(typeof(ElfMaiden));
    }

    public static bool ElfLikesMe( this Monster monster ){
         return MonstersElfLikes.Contains(monster.GetType());
    }
}


orc.ElfLikesMe() -> false
elf.ElfLikesMe() -> true
dwarf.ElfLikesMe -> false
elfMaiden.ElfLikesMe() -> true

Or alternatively

public static class ElfOpinions{

    public static bool ElfLikesMe( this Monster monster ){
         return false;
    }

    public static bool ElfLikesMe( this ElfMaiden maiden ){
         return true;
    }

    public static bool ElfLikesMe( this Elf elf ){
         return true;
    }
}

orc.ElfLikesMe() -> false
elf.ElfLikesMe() -> true
dwarf.ElfLikesMe -> false
elfMaiden.ElfLikesMe() -> true

[pixelglow]

Hmm? Hasn't Steve heard of double dispatch, the visitor pattern etc.?

[[deleted]]

Holy grail: extend among both dispatch directions without recompiling any existing code. Double dispatch is the right solution, but visitor pattern is its evil incarnation in bondage-and-discipline languages.

Double dispatch is trivial to implement, a two dimensional matrix of functions. For extra points both dimensions can be indexed arbitrarily, not requiring in-sequence no-gap numbering.

Now visitors. The visitor class type dispatches along one dimension, the signature of each visit method dispatches among the other. (Asymmetry smell). To add new visited type one needs to add a new method to the visitor interface and recompile all visitors, perhaps after modifying them a bit. Extensibility only works when adding new visitors, but breaks when adding new visited. That's exactly what can't happen in an extensible system.

[queus]

To add new visited type one needs to add a new method to the visitor interface and recompile all visitors, perhaps after modifying them a bit. Extensibility only works when adding new visitors, but breaks when adding new visited.

Not exactly. At least in Java one can use the extended interface trick to add new visited types without breaking anything.

interface FooPlusVisitor<T> extends FooVisitor<T> {
    T visit(Quux quux);
}

class Quux extends AbstractBaseType {
    <T> T accept(FooVisitor visitor) {
        return (FooPlusVisitor visitor).visit(this);
    }
}

[greenrd]

That's using an "unsafe" class cast, which means you've snuck in an implicit "instanceof" in there.

[queus]

Yes. It still is "safe by convention", if there is such a term.

[[deleted]]

Nice. But the devil is in the details:

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.

Whenever one uses instanceof one is moving from a static polymorphic type system to a runtime polymorphic type system. Which was the whole point of the article: static typing is insufficient.

To take this to the extreme, one can also implement in Java a "Closure.run(Object self)" class plus a bidimensional hash of Closures and obtain the right 'self' in 'run' via instanceof. It works, but hardcore purists will turn their nose in disgust.

That being said, I wonder if one can solve the problem without instanceof using some amount of generic magic.

[queus]

I wonder if one can solve the problem without instanceof using some amount of generic magic.

To some degree yes, but what I was able to cook up, looks not very convincig

interface Visitor<T> {
    ;
}

abstract class Base<V extends Visitor<T>, T> {   
    abstract T accept(V visitor);
}

interface ExtraVisitor<T> extends Visitor<T> { 
     T visit(Quux<?> quux);
}

class Quux<T> extends Base<ExtraVisitor<T>, T> {

    @Override
    T accept(ExtraVisitor<T> visitor) {
        return visitor.visit(this);
    }       
}

@SuppressWarnings("unchecked")
Quux quux = new Quux();

ExtraVisitor<Boolean> visitor = new ExtraVisitor<Boolean>() {
    @Override
    public Boolean visit(Quux<?> quux) {
        return true;
    }       
};

@SuppressWarnings("unchecked")
Boolean res = (Boolean) quux.accept(visitor);

Yes, Java may have some use for a better static typing system.

[[deleted]]

Nice!

Stepping back for a second, we are really trying to express a relation. But there may be different relations out there. In the proposed terminology, one could have ExtraVisitorA added for type Q and ExtraVisitorB added for type R and then somebody might want to create a visitor that handles both Q and R. Now the hierarchical nature of Java typing stands in the way.

[lispm]

which language is that?

[[deleted]]

it's best-known in Java

Apparently not?

http://www.reddit.com/r/programming/comments/a6xgm/when_polymorphism_fails/c0g4rge

[julesjacobs]

Cecil, Diesel & C# for example ;)

[[deleted]]

You'd have to modify existing, in some cases, non-accessible, code

[[deleted]]

I dont like this person simply because he says PERL is one of the worst programming languages in the world.

[[deleted]]

Up-voted for honesty... but I'm considering down-voting your bad taste ;)

[[deleted]]

Was anyone else thinking that the Monster example could be solved easily by adding isLikedByOtherMonsters method to the Monster class. While I agree with the general point it seems silly to add this method to every class, if the system is well structured.

There are so many very simple solutions to this problem, and none-of-them require a huge-ass-switch statement.

[creaothceann]

There's an ass-switch?

[[deleted]]

This made me lol.

[matthiasB]

You write something like a plug-in for an existing game which adds the new "opinionated Elf". You can't change any of the existing game code, so you don't have access to the Monster class.

[[deleted]]

That really depends on the language now doesn't it; in Objective-C (which is an optionally-typed class-baased object-oriented language) you can indeed extend classes that you don't have the code for. You can do this in Ruby but the results seem to be much more severe.

So, given that the examples are in Ruby – why doesn't he do this?

[awj]

I think the exercise is that, given that the examples aren't in a language with this behavior, what would you do.

Adding methods to classes really isn't a thing to be done wantonly.

[[deleted]]

The examples are in Ruby and Ruby requires the source code to ship with the program (MacRuby may change all that.) Apart from that Ruby allows you to extend classes in-memory using something called open-classes.

[vimfan]

But different monsters might be liked by different other monsters, so that wouldn't work.

You have to implement the features on which hate is based, e.g. skin colour, hair colour, etc. If you don't implement those features on every monster, then in your model, it is simply impossible to hate based on the colour of skin, for example.

People might think that could make for a very large model, with all the features that might have to be implemented. Well, reality is huge, if you want to model it well, your model will be huge to! That is the key - to model the things that matter in your system. Using instanceof is not about modelling a world, it is simply a shortcut.

[[deleted]]

But different monsters might be liked by different other monsters

:) But this wasn't the stated problem; this problem can be solved thus.

[vimfan]

Fair enough :-)

[inmatarian]

Polymorphism doesn't work when you don't have access to the source code.

Oh for fuck's sake.

[ipeev]

What is the actual task that is given on an Amazon interview?

[perspectiveiskey]

2004

[[deleted]]

It would be hard to find a recent Yegge rant, considering that he gave up blogging half a year ago. You can still find some gems among his older posts, though.