[Python-3000] Refactoring tool available (work in progress)

Talin talin at acm.org
Fri Dec 15 19:31:17 CET 2006


Guido van Rossum wrote:
> I'm not sure how thinking about it as an algebraic solver helps -- is
> there any existing code I can borrow?

I suppose it depends on how complex your rules are going to be. The 
matching algorithms used in solvers are specialized for some fairly 
difficult cases. Two examples I can think of are (a) where the 
'constants' of the match expression are leaves, rather than roots of the 
expression being matched, and (b) where subtrees of the match expression 
have multiple ambiguous matches.

An example of the latter is handling the associative rule, i.e.:

   "?a + ?b"

can against:

   x + y + z

either as:

   (x + y) + z

or as:

   x + (y + z)

However, if you aren't dealing with those kinds of cases, then probably 
you don't need to go that route.

Code-wise, I wouldn't want to offer what I have, because it's pretty 
rough and unformed. But the general theory is that the matcher for each 
sub-expression returns a generator of all possible matches. So for 
example, in the expression '?a + ?b', the '?a' matcher returns a 
generator that yields the series ({a=x}, {a=x+y}). The '+' matcher then 
passes this generator to the '?b' matcher, which essentially filters the 
output of '?a' - that is, it either removes results from the list that 
are inconsistent with its own situation, or returns results augmented 
with its own bindings. In this case, it would yield ({a=x,b=y+z}, 
{a=x+y,b=z}). The '+' matcher then yields the output of '?b' to the 
caller. If the entire expression doesn't match, then the result is 
generator that immediately ends, yielding no values.

(Also, the code I have could be greatly improved by porting to 2.5, with 
the new 'yield as expression' feature. It would require a total rewrite 
though.)

-- Talin



More information about the Python-3000 mailing list