Stavros Macrakis wrote:
>>The message "v u partitions product" is a warning that
>>the pattern matcher will try to partition a product, but
>>actually doesn't exhaustively try all possible partitions.
>
>
> I wonder when it would be sensible to try all possible partitions.
> Perhaps some sort of constraint-propagation pattern matching engine (as
> opposed to straight backtracking) could reduce the combinatorial
> explosion to a reasonable level. Surely the AI people have improved
> their algorithms since you worked on the pattern-matcher N years ago.
> For that matter, perhaps even straight backtracking is OK for some
> problems. There must be research on this?
>
> -s
>
I beleive that the commercial macsyma pattern matcher has been
rewritten from what I wrote 30 years ago, but still doesn't do
backtracking.
I wrote a backtracking algorithm for mathematical expressions
that mimics most of Mathematica's behavior, at least so far
as I could determine, in MockMMA.
The research on this topic is probably separable into two
streams. The AI version just organizes exponential search
to try to avoid exponential time in some cases. Programming
hacks. The theory people talk about unification with
commutative operators and identity and tell you how really hard
it is. Unification is not pattern matching exactly, but
it is related, and it is what theorists write about. The
papers tend to be: removing generality makes it easier. adding
generality makes it harder. parallelism makes it faster sometimes.
I do not expect the following problem to be done by pattern
matching, though of course it could be expressed that way.
matchdeclare(u,primep);
matchdeclare(v,true);
defmatch(factorpat,u*v);
factorpat(35) --> u=5, v=7
The example which started this thread was not actually much
different from this. the pattern matcher would have to
factor exp(x+y) to exp(x)*exp(y) to make the match work.
Why not have the pattern matcher factor integers as well?
RJF