Subject: [Fwd: the state of the art of predicate dispatching]
From: Craig Chambers (chambers@cs.washington.edu)
Date: Tue Jul 10 2001 - 12:27:22 PDT
FYI.
"Aaron M. Ucko" wrote:
>
> Doug Orleans <dougo@ccs.neu.edu> writes:
>
> > 1. Publications: As far as I can tell, there are still only two
> > published papers on predicate dispatching: "A Unified Theory of
> > Dispatch" from ECOOP98, and "Efficient Multiple and Predicate
> > Dispatching" from OOPSLA99. Am I missing anything? Aaron, did you
> > finish your master's thesis on adding predicate dispatching to
> > CLOS? Is it available online?
>
> I finished my thesis in May; the code has some rough edges (documented
> in the paper) but the essentials work. MIT technically owns the
> rights, but my supervisor (Howard Shrobe, hes@ai.mit.edu) verbally
> approved releasing it. I have placed the paper online at
>
> http://web.mit.edu/amu/thesis.ps.gz
>
> and the code online at
>
> http://web.mit.edu/amu/pd-code.tar.gz
>
> > 2. Code: The GUD implementation is avalable from the Cecil project
> > site, but there is no source code. Can this be made available?
> > How about the code from Aaron's thesis and Greg's DVML project?
> > I've been working on a toy implementation in Scheme, but I'd like
> > to compare notes because I'm pretty sure some of my algorithms are
> > not the best. In particular, neither of the papers really went
> > into enough detail about the predicate implication algorithm-- I am
> > currently doing the "brute force" approach, i.e. checking every
> > consistent truth assignment for the atoms of (or (not P1) P2),
> > which works, but seems pretty ugly.
>
> My code constructs a predicate corresponding to (or (not P1) P2) and
> uses a handful of transformations (in normalize-or.lisp) to attempt to
> reduce it to *true*. Because it starts out by rewriting the predicate
> in disjunctive normal form, it has the potential to take exponential
> time, but it typically performs much better in practice.
>
> > 3. Functionality: The biggest thing that seems to be missing from
> > predicate dispatching as described in the two papers is
> > call-next-method/resend. Has anyone thought of an elegant way to
> > handle this? I think it boils down to providing a way to select a
> > subset of the methods that were applicable to the current set of
> > arguments, such that there is another single most specific method
> > in this subset. Basically some generalization of Cecil's directed
> > resend is what I'm aiming for.
>
> My code supports call-next-method; every method call passes along a
> list of remaining potentially applicable methods, sorted based on
> implication. (Potentially applicable based on explicit argument
> types; architectural limitations prevent more filtering.)
>
> It chooses arbitrarily in the case of ambiguity, which is reasonable
> in situations where all applicable methods will give equivalent
> results but some are more efficient or yield more useful forms.
> (Consider symbolic mathematics, for instance.)
>
> > Thanks for reading. I look forward to your responses. If you'd
> > rather not be in this discussion, let me know and I'll take you off
> > the address list.
>
> Although I have finished my thesis and will be starting unrelated work
> (bioinformatics) in August, I would still like to stay in the
> discussion; predicate dispatching is interesting technology, and I
> want to see what becomes of it.
>
> --
> Aaron M. Ucko, KB1CJC <amu@mit.edu> (finger amu@monk.mit.edu)
_______________________________________________
Cecil mailing list
Cecil@cs.washington.edu
http://majordomo.cs.washington.edu/mailman/listinfo/cecil
This archive was generated by hypermail 2b25 : Tue Jul 10 2001 - 12:28:05 PDT