From: rcarter@wpi.WPI.EDU (Randolph Carter <Joseph H. Allen>)
Subject: Re: Simplification
Organization: Worcester Polytechnic Institute
Date: Wed, 29 Jul 1992 07:28:26 GMT

ppc1@cec1.wustl.edu (Peter Pui Tak Chiu) writes:
>hi everyone,

>i have a real naive question:

>        how to do symbolic simplification using scheme, lisp or anything...?

>what i mean is symbolic simplification like MATHEMATICA.

>here are some examples:

>          (* a (+ b (/ c a))) ==> (+ (* a b) c)
>          (+ (* a b) (* a c)) ==> (* a (+ b c))

I did this with a depth-first recursive algorithm on a parse tree.  At each
level the parse tree gets transformed into a vectors of terms and then gets
transformed back into a parse tree.  The parse tree used all binary and
unary operators, not lists of multiplied or added terms (I found that to be
harder).  Sorry, I'm a C programmer so I can't give lisp examples of this. 
Some pseudo-code:  

	TREENODE simplify ( TREENODE x )
	TREENODE y
	TREENODE terms[]	Vector of terms and constant multipliers
	TREENODE consts[]
  		if(x.type=='+')
			x.left=simplify(x.left)
			x.right=simplify(x.right)
			n=0 (latest term)
			clear(terms)
			settoones(consts)
			while(y=extractaddterm(&x))
				m=extractmultconst(&y)
				q=findterm(terms,y)
				if (found matching term)
					consts[q]+=m
				else (add new term)
					consts[n]=m, terms[n]=q, ++n
                        for(x=0;x!=n;++x) (rebuild parse tree)
				x=cons(x,+,cons(consts[x],*,terms[y]))

		else if(x.type=='*')
			x.left=simplify(x.left)
			x.right=simplify(x.right)
			.... (similer to above but treat exponants as * is
			     treated above)

Where: extractaddterm removes one term from a bunch of things added
together.  for example it might transform (+ x (* a b)) into (x) and return
(* a b).  findterm searches using some pattern matching algorithm which is
insensitive to communitive equivelencies (not easy).  extractmultconst is
like extractaddterm but extracts a constant out of things mutiplied
together.  It would be better for 'extractmultconst' to work with 'findterm'
and extract matching combinations of multipliers (so you can simplify
abc+abd into ab(c+d)), but you need some heuristics or human intervention to
choose which terms to group in: abc+dbc+abe  (when I did this, only the
common 'b' would be factored out.  But you could use the mouse to specify a
subset of the equation to run the simplifier on.  this way you could
simplify ab(c+e)+dbc if you wanted to. (and then simplify on the whole
equation again to get b(a(c+e)+d) )).

I believe mathmatica does something like this (it always stored its
equations as parse trees), except that it might have a directing list of
simplifications which it pattern matches the tree to.  I think macsyma
stores equations as vectors of broken down and sorted terms (so it does this
but doesn't convert back to a parse tree until any other proceedure is
executed), but this is a guess, as I was never able to understand all of
that scarcely-commented lisp and I never found (or looked very hard for)
papers describing the whole thing. 

One thing I'd like to try (this might already be used, actually) is to add
type verification to a general purpose pattern matching like that used in
mathmatica.  This way you could give an integration formula and specify that
in: itegrate(a*b^c)->a*b^(c+1)/(c+1), c is not to equal '-1' in some kind of
auxilliary equation.

I'm interested in seeing the email replies you get to your question.
-- 
/*  rcarter@wpi.wpi.edu */      /* Amazing */             /* Joseph H. Allen */
int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
+r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2
]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}