"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 C<foo> is
called), but it doesn't change the semantics (i.e. the fact that it's
legal and possible to call C<foo> 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 {...} # A B
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. In this latter case, an LSP/Meyer-analog
genuinely *is* being violated, because the program's *semantics* change:
from "dispatch to some multisub" to "crash and burn".
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.
Indeed, as Coplien points out in the above-mentioned article,
multiple dispatch is the longstanding linguistic *solution* to the
inherent symmetry-breaking introduced when method selection depends
on more than one invocant.
> 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.
(That's not to say that there can't be metrics under which empty
intermediate classes *don't* have any effect on multiple dispatch
behaviour. For example, you might postulate a metric that measures the
"distance" from a derived class back to its base case by the number of
base-class methods that the derived class redefines. But, though this
sounds more precise, it really isn't any better than simple Manhattan
distance in most cases, since those redefined methods may be completely
irrelevant to the particular multimethod being dispatched and therefore
not a reliable distance measure in *its* particular dispatch space.)
To summarize:
* LSP/Meyer requires high level semantics and type relationships be
preserved, *not* that specific dispatch behaviour be preserved.
* So LSP specifically doesn't prohibit changes in a dispatch target
when a hierarchy changes, unless that change in target terminates
normal flow control.
* LSP applies to singly dispatched method calls, not to
multiple dispatch.
Damian
