# Re: Algorithm

## anton@mips.complang.tuwien.ac.at (Anton Ertl)5 Jul 1998 21:34:16 -0400

From comp.compilers

Related articles
Algorithm arao@ececs.uc.edu (Amit M. Rao) (1998-07-05)
Re: Algorithm anton@mips.complang.tuwien.ac.at (1998-07-05)
Re: Algorithm arao@ececs.uc.edu (Amit M. Rao) (1998-07-05)
| List of all articles for this month |

 From: anton@mips.complang.tuwien.ac.at (Anton Ertl) Newsgroups: comp.compilers Date: 5 Jul 1998 21:34:16 -0400 Organization: Institut fuer Computersprachen, Technische Universitaet Wien References: 98-07-044 Keywords: theory, question

"Amit M. Rao" <arao@ececs.uc.edu> writes:
> I am looking for an algorithm that enumerates all possible expression
> trees obtained by applying the commutative law to an expresssion tree.

A natural application of Prolog. Here's the program:

tree_com(A=B,A1=B1):- tree_com(A,A1), tree_com(B,B1).
tree_com(A+B,A1+B1):- tree_com(A,A1), tree_com(B,B1).
tree_com(A+B,B1+A1):- tree_com(A,A1), tree_com(B,B1).
tree_com(A*B,A1*B1):- tree_com(A,A1), tree_com(B,B1).
tree_com(A*B,B1*A1):- tree_com(A,A1), tree_com(B,B1).
tree_com(T,T):-atom(T).

And here's the query and its solutions for your example:

?- tree_com(a = b * c + d, X).

X = a=b*c+d ? ;

X = a=c*b+d ? ;

X = a=d+b*c ? ;

X = a=d+c*b ? ;

no

- anton
--
M. Anton Ertl Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html
--

Post a followup to this message