Smart Traversal


Some computations involve only a few functors, but to access them a traversal of a complex data structure must be specified.

Assume that in an abstract syntax a type Expr is defined with a functor

   id(IDENT, POS)
which is used to represent an application of an identifier at a given position. We wish to describe the task of printing all identifier applications together with their coordinates. For this purpose we use a predicate

   ListApplication(Id, Pos)
each time we encounter a term id(Id, Pos).

For example,

   'rule' VisitExpr(id(Id, Pos)): ListApplication(Id, Pos)
In order to list all identifier applications, we have to inspect the whole abstract syntax by a recursive traversal. For example, when we process a term if(Cond, Then, Else)), all three constituents can contain identifier applications. We have to write

   'rule' VisitStmt(if(Cond,Then,Else)):
      VisitExpr(Cond) VisitStmt(Then) VisitStmt(Else)
and similar rules for all other functors.

This can be abbreviated using sweep predicates.

A sweep predicate traverses the data structure given as its argument. When an explicitly written rule is applicable this rule is taken. Otherwise a default rule is used that visits recursively the constituents of the argument. Hence rules such as

   'rule' VisitExpr(id(Id, Pos)): ListApplication(Id, Pos)
must be specified, but rules such as

   'rule' VisitStmt(if(Cond,Then,Else)):
      VisitExpr(Cond) VisitStmt(Then) VisitStmt(Else)
need not be written.

A sweep predicate is declared as being of of category 'sweep'. It is a generic predicate in the sense that it works on all term types, the parameter is specified as being of type ANY (which is used as a generic type name).

The cross-reference application discussed above is completely specified by the following declaration

   'sweep' Visit(ANY)
      'rule' Visit(id(Id, Pos)): ListApplication(Id, Pos)
Assuming that we specified the grammar by a predicate Program, we can list all applications of identifiers by writing

   'root' Program(-> Pgm) Visit(Pgm)