home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / programm / 2129 < prev    next >
Encoding:
Text File  |  1992-07-29  |  4.0 KB  |  95 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!centerline!noc.near.net!wpi.WPI.EDU!rcarter
  3. From: rcarter@wpi.WPI.EDU (Randolph Carter <Joseph H. Allen>)
  4. Subject: Re: Simplification
  5. Message-ID: <Bs53FE.DpI@wpi.WPI.EDU>
  6. Sender: news@wpi.WPI.EDU (USENET News System)
  7. Nntp-Posting-Host: wpi.wpi.edu
  8. Organization: Worcester Polytechnic Institute
  9. References: <1992Jul25.114854.27062@wuecl.wustl.edu>
  10. Date: Wed, 29 Jul 1992 07:28:26 GMT
  11. Lines: 82
  12.  
  13. ppc1@cec1.wustl.edu (Peter Pui Tak Chiu) writes:
  14. >hi everyone,
  15.  
  16. >i have a real naive question:
  17.  
  18. >        how to do symbolic simplification using scheme, lisp or anything...?
  19.  
  20. >what i mean is symbolic simplification like MATHEMATICA.
  21.  
  22. >here are some examples:
  23.  
  24. >          (* a (+ b (/ c a))) ==> (+ (* a b) c)
  25. >          (+ (* a b) (* a c)) ==> (* a (+ b c))
  26.  
  27. I did this with a depth-first recursive algorithm on a parse tree.  At each
  28. level the parse tree gets transformed into a vectors of terms and then gets
  29. transformed back into a parse tree.  The parse tree used all binary and
  30. unary operators, not lists of multiplied or added terms (I found that to be
  31. harder).  Sorry, I'm a C programmer so I can't give lisp examples of this. 
  32. Some pseudo-code:  
  33.  
  34.     TREENODE simplify ( TREENODE x )
  35.     TREENODE y
  36.     TREENODE terms[]    Vector of terms and constant multipliers
  37.     TREENODE consts[]
  38.           if(x.type=='+')
  39.             x.left=simplify(x.left)
  40.             x.right=simplify(x.right)
  41.             n=0 (latest term)
  42.             clear(terms)
  43.             settoones(consts)
  44.             while(y=extractaddterm(&x))
  45.                 m=extractmultconst(&y)
  46.                 q=findterm(terms,y)
  47.                 if (found matching term)
  48.                     consts[q]+=m
  49.                 else (add new term)
  50.                     consts[n]=m, terms[n]=q, ++n
  51.                         for(x=0;x!=n;++x) (rebuild parse tree)
  52.                 x=cons(x,+,cons(consts[x],*,terms[y]))
  53.  
  54.         else if(x.type=='*')
  55.             x.left=simplify(x.left)
  56.             x.right=simplify(x.right)
  57.             .... (similer to above but treat exponants as * is
  58.                  treated above)
  59.  
  60. Where: extractaddterm removes one term from a bunch of things added
  61. together.  for example it might transform (+ x (* a b)) into (x) and return
  62. (* a b).  findterm searches using some pattern matching algorithm which is
  63. insensitive to communitive equivelencies (not easy).  extractmultconst is
  64. like extractaddterm but extracts a constant out of things mutiplied
  65. together.  It would be better for 'extractmultconst' to work with 'findterm'
  66. and extract matching combinations of multipliers (so you can simplify
  67. abc+abd into ab(c+d)), but you need some heuristics or human intervention to
  68. choose which terms to group in: abc+dbc+abe  (when I did this, only the
  69. common 'b' would be factored out.  But you could use the mouse to specify a
  70. subset of the equation to run the simplifier on.  this way you could
  71. simplify ab(c+e)+dbc if you wanted to. (and then simplify on the whole
  72. equation again to get b(a(c+e)+d) )).
  73.  
  74. I believe mathmatica does something like this (it always stored its
  75. equations as parse trees), except that it might have a directing list of
  76. simplifications which it pattern matches the tree to.  I think macsyma
  77. stores equations as vectors of broken down and sorted terms (so it does this
  78. but doesn't convert back to a parse tree until any other proceedure is
  79. executed), but this is a guess, as I was never able to understand all of
  80. that scarcely-commented lisp and I never found (or looked very hard for)
  81. papers describing the whole thing. 
  82.  
  83. One thing I'd like to try (this might already be used, actually) is to add
  84. type verification to a general purpose pattern matching like that used in
  85. mathmatica.  This way you could give an integration formula and specify that
  86. in: itegrate(a*b^c)->a*b^(c+1)/(c+1), c is not to equal '-1' in some kind of
  87. auxilliary equation.
  88.  
  89. I'm interested in seeing the email replies you get to your question.
  90. -- 
  91. /*  rcarter@wpi.wpi.edu */      /* Amazing */             /* Joseph H. Allen */
  92. 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)
  93. +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
  94. ]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}
  95.