[Python-3000] GF dispatch code in C++

Talin talin at acm.org
Sat Dec 2 08:29:39 CET 2006

I'm not sure anyone would be interested in this or not. A few months 
back, I wrote a generic function dispatcher based on the Chambers/Chen 
paper for my embedded mini-language, Saga. It's written in C++, although 
it makes fairly minimal use of C++ features.

This code is an independent creation from PJE's RuleDispatch, which I've 
never looked at.

The limitations of the current code are:

   -- It only tests vs. types, not arbitrary predicates, although it 
could probably be extended to do that (as pointed out in the 
Chambers/Chen paper.)

   -- For purposes of reducing memory consumption, it only allows the 
dispatch to be based on the first 6 arguments or less of the function 
(obviously the number 6 can be adjusted via a compile-time constant.)

   -- It's written against the Saga code base, not Python, although it 
shouldn't be too hard to port one to the other.

The dispatching is pretty fast. Each time a new method is added, it 
rebuilds a discrimination tree (which is stored in a flat array).

The tree is constructed by repeatedly partitioning the set of methods by 
selecting some 'pivot' test against one of the method's arguments. In 
other words, each method has a set of 'tests' which are run against the 
input arguments to determine if that method should be called. For any 
given test, the set of all methods can be divided into three groups:

   -- methods which require that the test succeed
   -- methods which require that the test fail
   -- methods which don't care one way or another

To prevent a combinatorial explosion of states, test cases which lead to 
identical partitionings are folded together. It also uses a heuristic 
that tries to minimize tree size by choosing a pivot test that results 
in the least number of 'don't care' cases.

Ambiguous cases and failure cases are properly handled. In the case of 
an ambiguity, it attempts to find the 'most specific' method (the one 
whose tests are a subset of the tests of all the other methods), and if 
no such method can be found, it dispatches to a function that raises an 
'ambiguity' exception.

Anyway, if anyone would like to fool around with this code, drop me a 
note and I'll mail it to you. It's fairly well commented. You won't be 
able to compile and run it out of the box (since I'm not going to 
include the entire project source tree), but it could be used as a 
starting point for experimentation.


And along other lines, I'd also be interested if anyone would like to 
take a crack at porting my Python implementation of PEP 3101 into C. 
That is the only thing preventing 3101 from being tested out in the real 

The python code can be found here:


-- Talin

More information about the Python-3000 mailing list