Re: The Use and Abuse of Liskov (was: Type::Class::Haskell does Role)
I just realized something that may be very important to my side of the
story. It appears that I was skimming over your example when I should
have been playing closer attention:
On 7/18/05, Damian Conway [EMAIL PROTECTED] wrote:
Consider the following classes:
class A {...} # AB
class B {...} #|
class C is B {...} #C D
class D {...} # \ /
class E is C is D {...} # E
multi sub foo(A $x, B $y) { (1) }
multi sub foo(A $x, C $y) { (2) }
foo(A.new, E.new);
Clearly this produces (2) under either Pure Ordering or Manhattan Metric.
Now we change the class hierarchy, adding *zero* extra empty classes
(which is surely an even stricter LSP/Meyer test-case than adding one
extra empty class!)
We get this:
class A {...} # A B
class B {...} # / \
class C is B {...} #C D
class D is B {...} # \ /
class E is C is D {...} # E
multi sub foo(A $x, B $y) { (1) }
multi sub foo(A $x, C $y) { (2) }
foo(A.new, E.new);
Manhattan Metric dispatch continues to produce (2), but Pure Ordering
now breaks the program.
Um... no it doesn't. Pure ordering continues to produce (2) as
well. Here are the precise semantics of the algorithm again:
A variant a is said to be _more specific than_ a variant b if:
* Every type in a's signature is a subset (derived from or
equal) of the corresponding type in b's signature.
* At least one of these is a proper subset (not an equality).
A variant is dispatched if there is a unique most specific method
applicable to the given arguments. That is, there exists an applicable
variant a such that for all other applicable variants x, a is more
specific than x.
A is equal to A, and C is a proper subset of B, therefore the latter
variant is more specific than the former. Since the latter is the
unique most specific variant, and it is applicable to the argument
types, it is chosen.
How did you think pure ordering worked? Were we arguing over
different definitions of that algorithm?
Luke
Re: The Use and Abuse of Liskov (was: Type::Class::Haskell does Role)
On 7/17/05, Damian Conway [EMAIL PROTECTED] wrote: You keep using that word. I do not think it means what you think it means -- Inigo Montoya Quite. I abused Liskov's name greatly here. Sorry about that. Anyway, my argument is founded on another principle -- I suppose it would be Palmer's zero-effect principle, that states: In absence of other information, a derived class behaves just like its parent. I can argue that one into the ground, but it is a postulate and doesn't fall out of anything deeper (in my thinking paradigm, I suppose). My best argument is that, how can you expect to add to something's behavior if it changes before you start? Every SMD system that I can think of obeys this principle (if you ignore constructors for languages like Java and C++). And as I showed below, the Manhattan metric for MMD dispatch is outside the realm of OO systems that obey this principle. In fact, I'm pretty sure (I haven't proved it) that any MMD system that relies on number of derivations as its metric will break this principle. All of which really just goes to show that the standard LSP is simply not a concept that is applicable to multiple dispatch. LSP is a set of constraints on subtype relationships within a single hierarchy. But multiple dispatch is not an interaction mediated by a single-hierarchy subtyping relationship; it's an interaction *between* two or more hierarchies. I agree, now. As a matter of taste, classes that don't do anything shouldn't do anything! But here they do. But your classes *do* do something that makes them do something. They change the degree of generalization of the leaf classes under an L[1] metric. Since they do that, it makes perfect sense that they also change the resulting behaviour under an L[1] metric. If the resulting behaviour didn't change then the L[1] *semantics* would be broken. Yep. And I'm saying that L[1] is stupid. In fact, (as I believe you've already picked up on), I'm not picking on the Manhattan combinator in particular, but using a derivation metric at all! In another message, you wrote: In MMD you have an argument of a given type and you're trying to find the most specifically compatible parameter. That means you only ever look upwards in a hierarchy. If your argument is of type D, then you can unequivocally say that C is more compatible than A (because they share more common components), and you can also say that B is not compatible at all. The relative derivation distances of B and D *never* matter since they can never be in competition, when viewed from the perspective of a particular argument. What we're really talking about here is how do we *combine* the compatibility measures of two or more arguments to determine the best overall fit. Pure Ordering does it in a take my bat and go home manner, Manhattan distance does it by weighing all arguments equally. For some definition of equal. In the message that this was responding to (which I don't think is terribly important to quote) I was referring to the absurdity of number of derivations as a metric. Picture a mathematician's internal monologue: Well, B is a subset of A, C is a subset of A, and D is a subset of C. Clearly, D has fewer elements than B. This mathematician is obviously insane. Then I think about the way you're using numbers to describe this, and I picture his friend responding to his thoughts (his friend is telepathic) with: You can make a stronger statement than that: The difference of the number of elements between A and D is exactly twice the difference of elements between A and B. And now maybe you see why I am so disgusted by this metric. You see, I'm thinking of a class simply as the set of all of its possible instances. And then when you refer to L[1] on the number of derivations, I put it into set-subset terms, and mathematics explodes. Here's how you can satisfy me: argue that Palmer's zero-effect principle is irrelevant, and explain either how Manhattan dispatch makes any sense in a class-is-a-set world view, or why that world view itself doesn't make sense. Or just don't satisfy me. Luke
The Use and Abuse of Liskov (was: Type::Class::Haskell does Role)
You keep using that word. I do not think
it means what you think it means
-- Inigo Montoya
Luke Palmer wrote:
Recently I discussed MMD with chromatic, and he mentioned two things
that were very important, in my opinion:
* The Liskov substitution principal sort of means that MMD
between two competing superclasses, no matter how far, is
equal
Actually, no it doesn't mean that at all.
It means that the LSP--which proposes an operational definition of
strict polymorphic subtyping--simply isn't applicable to multimorphic
type-hierarchy interactions such as multiple dispatch.
See:
http://users.rcn.com/jcoplien/Patterns/Symmetry/Springer/SpringerSymmetry.html
for a group theoretic explanation of why that's the case.
For those of you who have not been exposed to this paradox,
here's an example:
class A {...}
class B is A {...}
class C is B {...}
class D is A {...}
multi foo(C $x, A $y) { (1) }
multi foo(A $x, D $y) { (2) }
If you call foo(C.new, D.new), (1) will be called (because it has
distance 1, while (2) has distance 2). Now suppose I refactor to
prepare for later changes, and add two *empty* classes:
class A {...}
class B is A {...}
class C is B {...}
class E is A { }
class F is E { }
class D is F {...}
Now if you call foo(C.new, D.new), (2) will be called instead of (1)
(because (1) has distance 3, while (2) still has distance 2). That is
how Liskov subtly breaks.
Liskov isn't broken here...it was never applicable here.
The LSP says that *semantics* mustn't change due to subtyping, not
that *behaviour* mustn't change. If behaviour weren't permitted to
change, then you could never redefine a method in a derived (or
intermediate) class.
For example, taking this hierarchy:
class A { method foo { (1) } }
class B is A { }
B.new.foo() # (1)
and updating it with an intermediate class:
class A { method foo { (1) } }
class Z is A { method foo { (2) } }
class B is Z { }
B.new.foo() # (2)
*doesn't* violate LSP.
Meyer gives a much more practical definition of the intent of LSP:
A derived class cannot require more, or promise less,
than a base class.
This formulation still allows for the possibility that, when a hierarchy
changes, the dispatch of a given method call may change and that a
different method may be invoked. But merely invoking a different
response after a hierarchy changes is not in itself a violation of LSP/Meyer.
In the above example, class Z *can* still be used in place of class A,
without the call to C.foo suddenly breaking.
It's the not breaking that is critical to LSP here. Using class Z
instead of class A does change the behaviour (i.e. which Cfoo is
called), but it doesn't change the semantics (i.e. the fact that it's
legal and possible to call Cfoo on a B object).
What *would* break LSP is writing this instead:
class A { method foo { (1) } }
class Z is A { method foo { die } }
class B is Z { }
B.new.foo() # Kaboom!
Indeed, this is one of the commonest ways of breaking LSP (almost
everyone does it): you replace an inherited method with one which
sometimes throws a previously-unthrown exception. Class Z is now
promising less than class A. Specifically, it's no longer promising to
return. You can no longer treat a derived object as if it were a base
object without the risk of abnormally terminating the program on some
(previously working) polymorphic method call.
Interestingly, Luke's original example is closely analogous to that
situation, only in multimorphic space. From a Liskov/Meyer perspective,
it's perfectly okay that a change in one of the parameter hierarchies
changes which multisub variant is invoked. The real problem is when a
change in one of the hierarchies causes a formerly legal multisub call
to become illegal (i.e. fatally ambiguous).
And that is one of the main reasons I advocate Manhattan Metric dispatch
over Pure Ordering dispatch. Because Pure Ordering--which imposes a much
stricter criterion for unambiguous--is far more likely to break
semantics in precisely that way.
Consider the following classes:
class A {...} # AB
class B {...} #|
class C is B {...} #C D
class D {...} # \ /
class E is C is D {...} # E
multi sub foo(A $x, B $y) { (1) }
multi sub foo(A $x, C $y) { (2) }
foo(A.new, E.new);
Clearly this produces (2) under either Pure Ordering or Manhattan Metric.
Now we change the class hierarchy, adding *zero* extra empty classes
(which is surely an even stricter LSP/Meyer test-case than adding one
extra empty class!)
We get this:
class A {...} # A B
class B {...} # / \
class C is B {...} #
