Previous Up Next

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*; 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 && java TermList
Original subject
Insertion with term-graph rules from Gom

This formalism is presented in

Previous Up Next