Hi Crista:

I am glad we have this discussion. I am very well aware of
your reservations to more expressiveness in strategies.
I know that you would prefer _only_ single edge strategies with bypassing
and only-through constraints. Indeed, Demeter/Java now supports
this style (and more). Doug decided to put this in and I think he was influence
by you.

Also Jens Palsberg is on your side in promoting simpler strategies.
See http://www.ccs.neu.edu/research/demeter/pub-impls/adapt-perl.html
which is Demeter/Perl5 which Jens and Peter designed.

But there is a whole group out there who believes in both
positive and negative expression. If you have only negative expression
you might end up with a confusing and brittle set of bypassings.
That is why Boaz and I, with strong support from Doug and Johan,
came up with the strategy graphs where the positive information is
now a graph. Doug and Johan liked the new strategies and they decided
to put them into Demeter/Java.

Since you "threaten" to throw out several months of our work,
we need to justify strategy graphs: A list like this should be in our paper.

1. Since each task we implement needs a subgraph of classes,
   it is natural to "approximate" this subgraph with
   another graph, a strategy graph, which maps out the
   "corner stones" or the "overall topology" of the subgraph.

2. Negative expression alone is not robust. If we have:
   from A bypassing {X} to C
   and we add another path through Y from A to C, we will likely need
   from A bypassing {X,Y} to C.
   An expression like:
   from A through {WhatWeWant} to C
   is more robust in such situations.

3. If we want positive expression than the right semantics for
   a strategy is a path set in the class graph and not
   only a subgraph of the class graph.

4. With strategy graphs we can easly express non-confusing throughs:
   from A through B to C
   can be replaced by:
   from A
     bypassing {A,B,C}
     through B
     bypassing {A,B,C}
   to C

   This strategy graph says that we cannot have extra As.Bs and Cs.
   We have one A and one B and one C.

More below.

>From lopes@parc.xerox.com Tue Aug  5 21:19:03 1997
>Sender: Cristina Lopes <lopes@parc.xerox.com>
>From: Cristina Lopes <lopes@parc.xerox.com>
>To: Karl Lieberherr <lieber@ccs.neu.edu>
>Cc: dem@ccs.neu.edu, lopes@parc.xerox.com
>Subject: Re:  traversals
>
>What I'm arguing is that the traversal language should be less
>powerful in order to be more clear. As you have it now, you're trying
>to reach the objects (which are, indeed, what you want) but you have
>only handles on classes (the class and variable names). Therefore, you
>loose in three ways: 
>1) the subject matter of the language is confusing (classes?
>   objects?); 

It is not confusing in flat class graphs. See the last paragraphs before
3. Definition of traversals 
in ftp://ftp.ccs.neu.edu/pub/people/lieber/strategies.ps
There is a natural correspondence between class graph paths
and object graph paths.

>2) you cannot reach arbitrary object paths, which, ultimately, should
>   be the goal; (e.g. a_instance1 b1_instance5 a_instance8 etc.) The
>   only predicate for selection is the history on the types of the
>   traversed objects, which seems to be a weak predicate, and albeit
>   not very common in practice (as you said). 

You are right. To reach arbitrary object paths, you need vistors
with around methods.

With the strategies we approximate the object paths we need and 
then with the visitors we do the fine-tuning.
See the latest version of Demeter/Java for how around methods
are used to select the desired object paths:
ftp://ftp.ccs.neu.edu/pub/people/dougo/demjava-sources

>3) in general, your semantics prevents you from doing separate
>   compilation of strategies and classes. 
>
>> I think that for 90% of the combinations of strategies and class graphs
>> occurring in practice you are right: 
>> we could translate the strategy into a new one
>> which has only one strategy edge and bypassings.
>> 
>> But there are many cases which could not be translated this way.
>> For example, look at the example on page 18 of
>> ftp://ftp.ccs.neu.edu/pub/people/lieber/strategies.ps
>
>Thanks for pointing out that example, which I consider a prototype of
>the semantic confusion I was talking about. (we had this discussion
>many times before...:)

Remember that flight to one of the OOPSLA conferences...

Can Doug and/or Johan address separate compilation for strategy graphs, please?

>
>In your example, are these valid _object_ paths?
>- A E B1 A C1
>- A E B1 A C1 D F A E B2 A C1 D
>- A E B1 A C2 D F A E B1 A C1 D
>- A E B1 A C2 D F A E B1 A C1 
>
>According to your def. 4.4, the first is not; the other three...  I
>don't know, which D objects are valid? This is even more confusing,
>because, your traversal is performed in all cases, and the wrappers,
>if any, are executed. Without run-time look ahead your implemention is
>not correct, in the sense that is doesn't quite do what the semantics
>says (in particular, def. 4.4)

Here you join forces with Mitch. Our traversals are curious and optimistic
(not cautious or pessimistic):
if there is a possibility of having success, let's explore!
Only if there is no possibility of having success a path will be
avoided.

The second path:
>- A E B1 A C1 D F A E B2 A C1 D

is allowed since it satisfies 
from A through B1 through C1 to D

You are right, this is confusing. If we want to remove the confusion,
add bypassing {B1, ... ,Bn,C1, ... ,Cn,D}
to all strategy graph edges.
Then all your paths become illegal.

Based on your input, maybe we should change the example
and also add a strategy edge from D to A.

>
>And the confusion propagates to the implementation. The reason why
>you get into trouble (i.e. exponential growth of methods) is that your
>semantics of strategies is based on object graphs. (That's the first
>sentence of your section 4.1) Therefore, for cyclic class graphs you

As mentioned, there is a natural correspondence between paths
in object and flat (or simple: see definition 2.1) class graphs.

>may end up having to generate a method for each possible combination
>of object traversal _histories_ (in order to solve the problem "have
>we traversed any Bi and Ci yet?").

A good summary of the issue.

>
>(BTW, I didn't understand your proof of theorem 6.1)
>
Given your statement above, what is not clear?

>Now consider this alternative _form_ and _semantics_ of strategies:
>strategies are given as (from vertex, to vertices, bypassing
>elements), and they identify _subgraphs_ of the given class graph (as
>opposed to identifying paths); no guarantees are made wrt the actual
>objects that are reached, except that, if they are indeed reached then
>the paths to them are made exclusivly within the resulting class subgraph. 
>
>So, your example of page 18 would not be _expressable_ in this form in
>the first place! You would have to express it in a different way,
>maybe with several strategies.
>
>-Crista
>

This is what we started with but it turned out not to be
good enough in complex situations.

-- Karl