[Zope3-dev] N-Tuple Adapters

[Shane Hathaway]

Phillip J. Eby wrote:
> At 09:42 AM 6/3/03 -0400, Shane Hathaway wrote:
> 
>> BTW I got my answer to the original questions from one of Steve's 
>> links: to speed up multiple dispatch, you use a decision tree.  Then 
>> speed becomes a matter of building efficient trees.  It seems like it 
>> could be complex but very fast.
> 
> Actually, building efficient trees for such things is either NP-hard or 
> NP-complete, I forget which.  If you browse Citeseer for topics related 
> to multiple and predicate dispatching, there are some papers that 
> purport to prove how hard it is to build a perfect dispatch decision 
> tree.  (I say purport because I can't follow the math, myself.)

But we can limit the scope greatly by dispatching based exclusively on 
type checking.  I don't think it's possible to reliably sort arbitrary 
predicates unless we make this restriction anyway (and we have to sort 
predicates since they are configured by independent sources.)  The tree 
doesn't have to be perfect, it only has to be reasonably efficient.

> OTOH, there are a few papers that claim to have good practical 
> performance, like the Ernst and Chambers papers on predicate dispatching 
> for the Cecil language.  Be warned, however, that the algorithms are 
> *really* complex, and they are mostly designed for static typing 
> scenarios.  In other words, they assume the compiler has information 
> available about all predicates and consequents at tree building time.  
> To date, I haven't seen any algorithms oriented towards incremental tree 
> building.

Well, I'm not going to pursue this for now.  It was only a diversion 
from Real Work. ;-)  Thanks for a nice discussion and a little more 
knowledge.

On a more practical note, maybe Zope 3 should use PEAK's implementation 
of adapters.  However, it seems like it would conflict with Jim's 
current work on C code for interfaces.

Shane