Re: Algorithm (Anton Ertl)
5 Jul 1998 21:34:16 -0400

          From comp.compilers

Related articles
Algorithm (Amit M. Rao) (1998-07-05)
Re: Algorithm (1998-07-05)
Re: Algorithm (Amit M. Rao) (1998-07-05)
| List of all articles for this month |

From: (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" <> 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).

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 ? ;


- anton
M. Anton Ertl Some things have to be seen to be believed Most things have to be believed to be seen

Post a followup to this message

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