[Prev][Next][Index][Thread]
Re: MI: why?
Bruce Tobin <btobin@columbus.rr.com> wrote:
> > See "Predicate Dispatching: A Unified Theory of Dispatch," by Michael
> > D. Ernst, Craig Kaplan, and Craig Chambers, at:
> >
> > http://www.cs.washington.edu/research/projects/cecil/www/Papers/gud.html
>
> Darned interesting.
>
> > The downside, of course, is that method dispatch becomes undecidable.
>
> Oh. That seems like a big problem. So the implementation never
> finishes running any programs, or does this just translate, in practice,
> to lousy performance?
Basically, all it means is that it's not possible to guarantee from
just the static program text that every method call will dispatch. That
is, it means that you can't prove that for all legal programs that you
will never get a "message not understood" error. (That's because you
can execute arbitrary predicates at method dispatch, and predicting
an arbitrary function's value is equivalent to the Halting problem.)
This is clearly not a huge problem for ST'ers or Dylan programmers,
because these languages already specify that message-not-understood
errors can happen at runtime. It -does- makes it harder to do things
like method prediction and inlining, but it's possible to argue that
the expressive benefits are worth the cost. For Dylan there's probably
a fairly big penalty, since it goes to some lengths to make dispatch
elimination possible, but I don't know enough about how well modern
Smalltalk implementations do dynamic-dispatch elimination to say if it
would hurt them any.
If you added it to something like Python, though, there wouldn't be
any performance hit because it doesn't do any optimization to make
harder. :) Also, Erik Ernst wrote me in email that there are
interesting decidable subsets of predicate dispatch, but I'll let him
explain the details.
Neel
Follow-Ups:
References: