At 9:50 AM -0700 7/11/02, John Porter wrote:
>Dan Sugalski wrote:
>> lookup is O(n) since we precompute the dispatch table.
>
>Oh. So the cost of computing the table is amortized over all the
>mm calls that go to the table for resolution. Could be Bad,
>for the typical small Perl program.
More the cost of computing the table is relative to the number of
classes that insert multimethods, but yeah there is a cost for each
method added.
>Then there's the issue of the size of the table.
>Considering that, in the worst case (for fastest lookup time)
>the table is exponential in the number of types, this
>could be Bad.
There are ways to make the tables smaller. In the two-arg case we're
considering for PMCs specifically, it can be reduced to a
one-dimensional table bounded by the first and last type that has a
specific method specified.
So, if add for type 77 only has mm specified for types 1000 and 1001,
we can shrink the table to two elements with a start offset. That
trades space for speed, though, since lookups will be slightly slower.
>But clearly, for predefined types (e.g. I/N/S/P) and binary
>ops, a predefined table of size 16 isn't unreasonable.
>
>Ooh, but wait. There's also the issue that, in general, the
>*number of tables* is O(n) in the number of ops! Ouch!
>(But this is true regardless of the resolution method.
>Even if we used some kind of heuristic or "type dominance
>graph", there would O(nOps) of them.
>[Note, those should actually be Theta, but I'm not sure how
>to draw that portably.]
Well, the number of tables is relative to the number of potential
methods we allow to be multimethods. In general that's potentially
unbounded, but for the specific case of PMC vtable methods it's a
fixed number.
It gets more interesting for general methods and subs, but we can
deal with that a bit later.
> > We look for
>> the entry in the table based on the type of the left and right side.
>
>I would point out that the mm problem pertains to more than just
>binary ops...
Sure, but for vtable methods we only care about the binary ops, since
we don't have any trinary ops, and the unary ops don't need mm
dispatch.
> > What we're really doing is left-side-wins always. It's just that, in
>> the case of all the perl types, they then do a multimethod lookup for
>> the ultimate routine to execute.
>
>Well then you're still left with a mm lookup problem.
>I think it's *this* mm resolution problem that we're talking about.
Yep. Luckily it's a bounded and relatively simple problem. :)
> > > In the example of int-vs-float, the rulebase (it's really just
> > > a DAG) decides that float wins. So a float.method gets an int
>> > argument; the int isn't promoted to a float.
>>
>> Ah. In that case it's really a subset of multimethod dispatch,
>
>"a subset of"?
>It *is* multimethod dispatch, but for just a pre-defined
>subset of cases. Is that what you mean?
Yes.
> > > > If we can't find a match, or ... no clear winner,
> > > > we throw an exception.
>> >
>> > You don't like the idea of falling back to left-side-wins?
>>
>> Oh, I like it, but at that point we've already decided to do a MM
>> lookup, so there's really no going back.
>
>O.k., I agree that "if there is no clear winner" we should throw.
>But yet, it seems to me that "left side wins" is a resolution
>technique that always yields a clear winner, in which case we'd
>never throw.
If we did that, yes. Unfortunately while left side wins yields a
clear winner, it doesn't necessarily yield the correct winner. If we
have:
a->b, and c->d
methods add(a, d) and add(b, c)
but are presented with add(b, d), then neither method is specifically
correct, and neither is really less correct than the other. In that
case, while LSW is a way to break the ties, it doesn't really break
them definitively correctly.
The right thing is to have a tiebreaker fallback method, one that we
call when we have no clear winner, even if that method is further
away in our n-dimensional space, and have it decide. The default
tiebreaker will just pitch an exception (which is a clue the
programmer should put in code to deal with the problem :) but it's
certainly valid for a class to install a different tiebreaker method,
and that may do LSW resolution. (In the example it'd dispatch to
"add(b,c)" since the left side is 'better' in that one)
That's the plan, at least. Plans, of course, are subject to change.
--
Dan
--------------------------------------"it's like this"-------------------
Dan Sugalski even samurai
[EMAIL PROTECTED] have teddy bears and even
teddy bears get drunk
