# [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

```