[Python-3000] GF dispatch code in C++
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
-- 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
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:
More information about the Python-3000