Chapter 4 Term-graph rewriting
Using the Gom option --termgraph, it is possible to automatically
generate from a signature the extended version for term-graphs. As the Tom
terms are implemented with maximal sharing, so are the term-graphs. Term-graphs
can be specified using label constructors.
import testlist.m.types.*;
import testlist.m.*;
import tom.library.sl.*;
import tom.library.utils.Viewer;
public class TestList {
%include{sl.tom}
%gom(--termgraph) {
module m
abstract syntax
Term = a()
| b()
| c()
| d()
List = doublelinkedlist(previous:List,element:Term,next:List)
| nil()
| insert(element:Term,list:List)
sort List: graphrules(Insert,Identity) {
l:doublelinkedlist(previous,y,insert(x,v:doublelinkedlist(&l,z,next)))
->
l1:doublelinkedlist(previous,y,
l2:doublelinkedlist(&l1,x,v:doublelinkedlist(&l2,z,next)))
}
}
public static void main(String[] args) {
List abcd = (List)
`LabList("1", doublelinkedlist(nil(),a(),
LabList("2",insert(b(),
LabList("3",doublelinkedlist(RefList("1"),c(),
doublelinkedlist(RefList("3"),d(),nil()))))))).expand();
System.out.println("Original subject");
Viewer.display(abcd);
System.out.println("Insertion with term-graph rules from Gom");
try {
Viewer.display(`TopDown(List.Insert()).visit(abcd));
} catch(VisitFailure e) {
System.out.println("Unexcepted failure!");
}
}
}
Users can define a system of term-graph rules and it is automatically compiled
in a basic Tom strategy. These term-graph rewriting rules can then be
integrated in a more complex strategy using Tom strategy combinators. As a
consequence, all Tom features are available for term-graphs.
polux@huggy$ tom TermList.t && javac TermList.java && java TermList
Original subject
Insertion with term-graph rules from Gom
This formalism is presented
in http://hal.inria.fr/inria-00173535/fr.
