Lisp S-expression optimization

Opium <>
15 Feb 2001 00:32:01 -0500

          From comp.compilers

Related articles
Lisp S-expression optimization (Opium) (2001-02-15)
Re: Lisp S-expression optimization (2001-02-17)
| List of all articles for this month |

From: Opium <>
Newsgroups: comp.compilers
Date: 15 Feb 2001 00:32:01 -0500
Organization: Semi-livid
Keywords: Lisp, optimize, question
Posted-Date: 15 Feb 2001 00:32:01 EST


The question is how to optimize a lisp s-expression in the parse -
tree phase. I'm playing around with a C++ program that randomly
generates lisp s-expressions: basically I tell it what functions I
want, give it pointers to function declarations and the number of
arguments each function has and then it randomly creates a parse tree
with the functions chosen at random and with variable names (also
chosen randomly) as leaf nodes.

The problem is that most of the time the s-expression is not in its
simplest form eg. if I had the AND and OR functions, a simple ((a AND
b) or c) could wind up as something horendously long (but after some
mathematical simplification would end up as previously stated).

The situation gets a little more complex when you have branching
functions (like the if..then..else) since the if-then-else construct
is just another function with 3 parameters.

So the question becomes, how do I (for a given set of functions)
process the s-expressions generated so that they are all in their
simplest form?

I've been wracking my head for a while on this one.
Any help appreciated

Post a followup to this message

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