On 5/8/07, Robert Dodier <robert.dodier at gmail.com> wrote:
>
> On 5/7/07, Stavros Macrakis <macrakis at alum.mit.edu> wrote:
>
> > This is because the pattern-matcher works strictly left-to-right, doing
> no
> > backtracking.
>
> Maybe this is a design decision that we could revisit.
> Maybe somehow we could adapt algorithms applied to regular
> expressions for strings. Just daydreaming at this point.
>
The state of the art in pattern-matching and unification has moved very far
since the Maxima pattern-matcher was written. Of course, backtracking
pattern-matching already existed then, and it was a conscious design
decision not to use it, presumably because of the potential exponential-time
blowup.
Matching trees is not quite the same thing as matching strings, but a simple
backtracking matcher is not a big deal. The main challenge would probably
be slotting it into the existing code. I won't promise to look at it, but I
probably will fool around with it a bit....
It would be nice if someone wanted to investigate more modern unification
algorithms, some of which handle associativity and commutativity nicely.
-s