1 Mar 1996 13:57:27 -0500

Related articles |
---|

simplification of formula (compiler? sorta...) colin@boxer.com (Colin Prepscius) (1996-02-27) |

Re: simplification of formula (compiler? sorta...) jaidi@ubd.edu.bn (1996-03-01) |

From: | jaidi@ubd.edu.bn |

Newsgroups: | comp.compilers |

Date: | 1 Mar 1996 13:57:27 -0500 |

Organization: | Compilers Central |

References: | 96-02-313 |

Keywords: | optimize |

*>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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.