Re: Pattern Matching in CAS's

In article <1164920127.457196.193480@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
jamesahart79@xxxxxxxxx wrote:

Hello all. For some time I have been working on an interface for
computer algebra manipulation where the user can manipulate the algebra
using mouse drags, pop-up menus, as well as the regular menus. It's
still very much in the beta stages, and I've spent most of my time
developing a interface for simple arithmetic. (I have posted here a
couple of times before; search for MathDrag'n.) Because I don't want
to reinvent the square wheel, I use an external CAS for solving the
"hard" problems that have already been well-solved (factorization,
solving, evaluating special functions, integrating, etc.) I have added
the ability to interface with Mathematica and Maxima, and will probably
add others with time.

I assume that you are aware of the program Leibniz, now called
DirectMath <http://www.directmath.com/about/about.html>, by Joe Gregg?
There is an article about the making of Leibniz at

http://physics.uwa.edu.au/pub/Mathematica/MathGroup/Leibniz.pdf

At this point, I feel like I need to add pattern-matching (beyond
comparing for trivial equivalence) to my project. I have read up on
the pattern-matching capabilities of both Mathematica and Maxima, as
well as trying generic Google searches for variations on the terms
"pattern matching trees", "pattern matching", etc. While from these it
is quite clear that there has been some real, valuable research in
these areas, I don't have the expertise to understand what I do find,
and I can't find any useful introductory level material, at least not
with my searches. I have even searched Google groups, and while I
discovered some interesting threads, including many people who post
regularly to this group, I didn't get the kind of details I need.

So I have the following questions:

How hard is it to create a pattern matcher from scratch? I'm not at
all certain I want to do one from scratch, and what I do will almost
certainly be inferior to what has been done, but it has the big
advantage of being portable. Basically, if it's not too hard I would
want to make it myself. If it's near impossible to do it properly, or
would eat up a year of work, I can try to piggyback off of the CAS I'm
using.

My good friend and colleague Kevin McIsaac wrote PM a pattern-matcher
for REDUCE in 1985/6. See http://www.reduce-algebra.com/docs/pm.pdf.
There is some more information about this in the following post by Tony
Hearn in 1989 (the year that McIsaac started working for Wolfram
Research Inc.):

CHANGES TO CODE IN THE REDUCE DIGITAL LIBRARY: PM

Several years ago, Kevin McIsaac, then at the University of Western
Australia, defined a pattern matcher for REDUCE that is similar to the
pattern matcher found in SMP and now Mathematica. This pattern matcher
was further refined during a visit he made to The RAND Corporation in
1986. The design of the REDUCE-based code may be found in his paper
"Pattern Matching Algebraic Identities", published in the SIGSAM Bulletin
19 (1985) pages 4-13. I am happy to say that this pattern matcher is now
available for testing. The relevant files can be found in the new
library "pm", the contents of which can be found by sending the message
"send index for pm" to reduce-netlib@xxxxxxxxx

In order to make the testing of this code as straightforward as possible,
it has been layered on top of the existing pattern matcher. Although it
is believed that the two can coexist, this may lead to inconsistencies if
the application of both new and old-style rules is attempted. In
addition, the handling of equations has been changed in this package. I
would therefore recommend that you use only rules based on this new
pattern matcher in testing it out.

Although all the necessary support code is there, the rules need a lot
more work to be at the level of the SMP and Mathematica libraries. Any
help in filling in the missing definitions would be most appreciated!
Tutorial examples illustrating the use of the pattern matcher that users
submit will also be added to the library. In addition, there are
several ways in which this code could be optimized. Whether this
happens will depend upon how useful this model is to the REDUCE
community. Finally, rules for simplifying hypergeometric functions will
be added to the library as soon as they have been thoroughly tested.

Cheers,
Paul

_______________________________________________________________________
Paul Abbott Phone: 61 8 6488 2734
School of Physics, M013 Fax: +61 8 6488 1014
The University of Western Australia (CRICOS Provider No 00126G)
AUSTRALIA http://physics.uwa.edu.au/~paul
.

Loading