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. 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. 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.] > 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... > 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. > > 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? > > > 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. > One place where we make it easier on ourselves at this level is > restricting the inheritance hierarchy. Since pretty much everything > inherits directly from default it's pretty simple to predict. k00l. -- John Douglas Porter __________________________________________________ Do You Yahoo!? Sign up for SBC Yahoo! Dial - First Month Free http://sbc.yahoo.com
