Hi David:

the issue of regular expressions for specifying traversals 
comes up again and again.

See:
/proj/adaptive/www/related-work/software-generators/yannis-feedback.ps

for a discussion of this issue by Yannis at UT Austin.

And see the proposal below by John Lamping from Xerox PARC.

Here is my current view:

APPCs are described in terms of interface class graphs
and programming is done in terms of those graphs.
An interface class graph is easily translated into a strategy 
that does only pure traversals: Each ICG edge becomes a strategy edge
and the constraint map for each edge becomes: bypass all nodes of the ICG.

Graphs are simpler than regular expressions: that is why I like 
strategy graphs.

But some further study is needed. See both Lamping's and Yannis
Smaragdakis' reactions.

A convincing argument would be the following:

We come up with a new regular expression notation IDEAL for traversing graphs:

Each strategy can be expressed as an IDEAL expression and the 
IDEAL expression  is never longer and usually shorter.

Some IDEAL expressions can not be expressed by strategies.

IDEAL expressions can be implemented as efficiently as strategies.

-- Karl

========================= message to Boaz in 1997
Hi Boaz:

our strategy notation looks more and more to what we had
3 years ago with the big difference that we have now a fast implementation.

Another difference is that graph strategies are more general
than the regular expressions below.

-- Karl
============================
From lamping@parc.xerox.com Thu Aug 31 13:33:57 1995
Subject: Re: Boolean and Regular

We seem to be converging, but I still think that enhanced regular
expressions can express all of the operators.  Here is the enhanced regular
expression language from a while back:

Atomic expressions:

   A    The empty traversal at class A
   lnk  a link of type lnk ("any" is a special case of any link type)

For combining expressions, the usual regular expression crowd:
   .     concatenation
   \cap  intersection
   \cup  union
   *     repetition
   not   negation

Note that A is like an empty string; the traversal that just sits at class
A.  As with all empty strings, A.A = A


Here are the operators from the Karl's last message, with a translation
into enhanced regular expressions:

[A,B]			A.any*.B
through edges           any*.lnk.any*
bypassing edges         not(any*.lnk.any*)
through vertices        any*.A.any*
bypassing vertices      not(any*.A.any*)
d1 join d2              [d1].[d2]
d1 merge d2             [d1]\cup[d2]
d1 intersect d2         [d1]\cap[d2]
not d1                  not([d1])

where [x] is the translation of x into regular expressions.

Of course, \cap is not strictly necessary, as it can be expressed in terms
of \cup and not.  Furthermore, with distribution, not can be pushed down to
leaves.

The enhanced regular expressions can also express some things that I can't
see how to express with the operators, such as paths from A to B that
don't visit an A or B node except at the start and end:

  A.(any*).B \cap not(A.any.(any*).(A \cup B).(any*).any.B)

Since the enhanced regular expressions are equivalent to DFAs (enhanced
with the ability to sense node types), it would be an interesting exercise
to find a set of operators that could capture any regular expression.