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

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