Re: simplification of formula (compiler? sorta...)

>say I have 2x+3x+5=2+7, I'd like to encode the algorithm to simplify
>2x+3x=5x. That kind of thing...


I suggest the following books for this sort of thing:
      Computer Algebra with LISP and REDUCE
      F Brackx & D Constales


      Computer Algebra
      J H Davenport et al


I also suggest you look into implementations of functional languages
that use rewrite rules (Mathematica-like rather than LISP-like).


I have done this sort of thing in C++ but I don't think my code would
suit your purpose because it is very specific to my application (no
division, no function call, no power, limited symbols). But I will
share my experience. I used the obvious tree representation and wrote
a very general routine to perform pattern matching and substitution. I
supplied a list of rewrite rules (i.e. pattern => replacement)such as:


      A * 0 => 0
      1 * A => A
      A * N => N * A
      ..etc.. A = any expression, B = any number


The routine took an expression and tried each rewrite rule. To reduce the
number of rewrite rules (and hence speed up the pattern matching) I decided
not to have a minus operator. Expression such as X - Y was coded as
X + (-1 * Y).


To facilitate pattern matching such as of this form:
      A1 * N + A2 * N A1, A2 = any possibly distinct numbers
I represented the tree like this
                +
            / \
          * *
        / \ / \
      A1 \ A2 \
                \ /
                      N


i.e. The node for N is shared. During pattern matching N will be
replaced with an actual expression (with some kind of mark to allow
backtracking). The problem of ensuring that the expression that is
matched to the first N is the same with the expression that is matched
to the second N becomes trivial.


I found that the ordering of the rules make a lot of different to the
speed and space requirement (yes! lots and lots of garbage to collect,
and the sharing of nodes complicate garbage tracking). I also found
that the time and space exploded with larger expression that I
resorted to a lot of direct surgery to the expression tree instead of
totally relying on the general rewrite routines.


Of course my representation was not efficient. The text book uses
lists and trees to represent expressions.


Are you writing a new functional language? :)


(My terminal is used by several users. Sometimes they
  forget to remove this auto signature)
Nor Jaidi jaidi@ubd.edu.bn
Department of Mathematics
Universiti Brunei Darussalam
Brunei 2028
--

Return to the comp.compilers page.
Search the comp.compilers archives again.