Re: rule sets and patterns, was ...Re: [ Homological Algebra in Maxima]

Well, occasionally people take a break from email!

Carl McTague wrote:
> Hi Professor Fateman,
> 
> thanks for replying!  I was starting to worry nobody cared.
> 
> On Fri, Jun 13, 2003 at 11:21:42AM -0700, Richard Fateman wrote:
> 
>>Some of your stuff could be done with pattern matching,
>>via tellsimp and matchdeclare
>>some of it is not sufficiently defined, e.g.
>>
>>tor(a+b,g) --->  tor(a,g) +  something.
>>
>>Does b have to be nonzero?  if not, this is an infinite
>>loop.
> 
> 
> Is it really?  If I understand correctly, it would only lead to an
> infinite loop if the system likes to introduce +0s.  In any case, I
> think math'a's built in reductions for addition take precedence to my
> function definitions and this problem doesn't really arise (ie the +0s
> vanish before the above rewrite is ever even applied).

Mathematica would loop also, I think, if you wrote
tor(a_+b___)     ... that's  3 underscores.

with macsyma's pattern matcher it is possible to consider
that 5 matches a+b  with   a=3, b=2.    Or even a=105 and b=-100.

If you want to match the argument only if it syntactically looks
like a sum, then that is different from the "semantic" match
attempted by macsyma.  Whether this is more or less useful
depends on the context.  Mathematica's pattern matcher is
very impressive, but can lead to surprising results, and substantial
inefficiencies if used naively.  Simple examples tend to work
nicely, and that makes it appealing.

> 
> 
>> is tor(x+y+45) possible?
> 
> 
> Certainly.  
> 
> Tor[a + b + c, G] => Tor[a, G] + Tor[b, G] + Tor[c, G]

I assumed that was the case, but the 3-argument " +"  is
syntactically different in Macsyma representations.

> 
> In all the little term rewriting systems I've written by hand I
> usually do + as a nested binary operation, so x+y+45 might for
> instance be represented as x + (y+45) and the pattern works fine.

> However, I certainly get the sense that math'a implements a long sum
> as a single list
Yes
> rather than nested binary operations and I'm not sure
> how the pattern matcher chooses to apply my binary rewrite to such a
> list (I can certainly think of a few ways).
It actually thinks of (almost) all ways, using backtracking.
   However, the way I
> specified the rule (as the sum of two terms) is in fact the way that
> the math'a book suggests implementing linearity: "x_ + y_ a sum of two
> *or more* terms" (section 2.3.13)

Yes, but learn about  y__  and y___   2 or 3 _
The treatment of n-ary operators ... initially only + and * is tricky and
involves knowing that 0 is the identity under +, but 1 is the identity
under *.

Macsyma allows you to implement linearity by simply saying a function
is linear, presumably wrt its first argument. Thus f(3*a+4*b+c) is 
automatically simplified to 3*f(a)+4*f(b)+f(c)  if you have done
declare(f,linear).   You'll have to read the details by describe(linear)..

> 
> Anyway, I certainly am not insisting that I implement the rewrites
> within maxima the exact same way as I did in math'a.  I was just
> providing the math'a code to try to illustrate as concretely as
> possible what I'm trying to do.

Yep.

> 
> 
>>you can write functions like  tor(a,g):= if inpart(a,0)="+" then
>>  map(lambda([r],tor(r,g)), a) else ....
>>
>>which is not quite pattern replacement syntax, but may actually
>>do the job a lot better.
> 
> 
> Will this actually work?  So I would code up a bunch of conditions
> checking for special reducible cases, but then what do I put at the
> end if none of them match?  I can't do tor(a,g), can I?  Wouldn't that
> lead to infinite recursion?
at the end you can do  'tor(a,g)

the 'tor  is the "noun" form for tor.
OR you could use another name for the reduced tor.
RJF


> 
> Thanks,
>   Carl