Hi John:

following up on our brief discussion with Doug yesterday, it makes sense
to add traversal methods that may have any return type to AspectJ.

The input to declare will then be:

1. Traversal strategy
2. Return type R
3. combination method
   R combine(R [] args) { ... }

When the return type is void, no combination method is given.
R may be either a collection class or a primitive type
such as int, float, or a wrapper class of any of those classes.

As we discussed, only need to generate traversal methods and the
advice on the traversals we can program through AspectJ advice.

Does this generalization make sense to you?

-- Karl

================
Shriram Krishnamurthi was visiting us on Jan. 11 and he proposed
the following extension to DJ, called DJ-F(unctional):

http://www.ccs.neu.edu/research/demeter/DJ/docs/api/edu/neu/ccs/demeter/dj/package-summary.html

Add a new kind of visitor class called FunctionalVisitor
to DJ that inherits from Visitor and that has the following
additional interface:

Object around(Object obj, Class cl, Subtraversal s) {}
X combine(X [] args)

Subtraversal supports the interface:

Object apply(String edgeName);
// calls the traversal on the edge with the given name
// for classes that have parts

Object apply(int index);
// calls the traversal on the edge with the given index
// for collection classes 

Benefits of the new DJ-F with the visitor class FunctionalVisitor:

1. Get a system that subsumes attribute grammars.
   It is better than attribute grammars because of the use
   of strategies to control traversals.
2. The resulting system is better than the approach by Ovlinger and Wand
   http://www.ccs.neu.edu/research/demeter/biblio/traversal-automata.html
   which does not use strategies but writes the traversals 
   explicitly.
3. Get a system that supports functional programming and traversal
   strategies. No longer need to do everything by side-effect.
   The examples such as container capacity checking, finding free variables
   in lambda expressions, writing interpreters become simpler.
   According to Shriram all examples in Mitch's book could be
   elegantly written in this style.
4. Shriram has a collection of reusable FunctionalVisitors.
   With parameterized classes a la DJ we can make those visitors more reusable.
5. Shriram says there is a strong connection to monads.
6. If combined with the capabilities of the ContextVisitor, the 
   FunctionalVisitor can access inherited attributes from up
   the stack using the history field of the current join point.

   
Disadvantages of DJ-F:
1. only slightly larger interface.


We are now ready to absorb Shriram's ideas because DJ is now
at a stage where such extensions can be easily added.


Example:

Container = "(" 
  <contents> List(Item) <capacity> Capacity ")" .
Item : Container | Simple.
List(S) ~ {S}.
Simple =  <name> Ident <w> Weight.
Capacity = <i> Integer.
Weight = <i> Integer.

CheckingVisitorDJ = <iV> SummingVisitorDJ <violations> int extends Visitor.
SummingVisitorDJ = <total> int extends FunctionalVisitor.

Main = .

Instead of using the old visitor:

SummingVisitorDJ {
// how to use:
// to sum all get_y() parts of type int belonging to class X
// change "Weight" to "X", change "get_i().intValue()" to "get_y()"
// Java does not support this parameterization
{{
  public void start() { total=0; System.out.println("begin"); }
  public void before(Weight o) { 
    total += o.get_i().intValue(); 
    System.out.println("before Weight"); }
  public Object getReturnValue() {return new Integer(total);}
}}
}

we now use the new one:

SummingVisitorDJ {
{{
  int combine(int [] args) {
    // add them together
  }
  public void start() { total=0; System.out.println("begin"); }
  public int around(Weight o, Subtraversal s) { 
    System.out.println("before Weight"); 
    return o.get_i().intValue(); 
  }
  public Object getReturnValue() {return new Integer(total);}
}}
}

The CheckingVisitor is an extension of the SummingVisitor.

// BEHAVIOR
//========================================================================

Container {
{{
  int checkCapacityDJ(TraversalGraph whereToGo) {

    CheckingVisitorDJ cV = new CheckingVisitorDJ();		

    Integer res = (Integer) whereToGo.traverse(this, 
      new Visitor[] { sV, cV });
    return res.intValue();
  }
}}
}
							
CheckingVisitorDJ {
{{
  // default combination mechanism
  int combine(int [] args) {
    // add them together
  }
  public void start() { violations=0; System.out.println("begin"); }
  public void before(Container o) {
    System.out.println(" start new container ");}

  public int around(Weight o, Subtraversal s) { 
    System.out.println("before Weight"); 
    return o.get_i().intValue(); 
  }
  public int around(Container host, Subtraversal s) {
    int cap = host.get_capacity().get_i().intValue();
    int diff = s.apply("contents");
    if (diff > cap)
      { this.set_violations(get_violations() + 1);
	System.out.println(" total weight " + 
	diff + " but limit is = " + cap + " OVER CAPACITY "); };
    System.out.println(" end container "); 
    return diff;
  }
  public Object getReturnValue() {return new Integer(violations);}
}}
}

Design guideline:
Shriram wrote in 1999:
If a traversal needs to switch types, I think the traversal should
simply halt at that point, and a new traversal should take over.  The
type represents the coherent action being performed.  The switch in
types suggests a switch in action.  I believe this is a design
principle that will reduce surprises.

-- Karl
PS.
Shriram's message of March 1999 is enclosed:

Hi Mitch and Johan:
enclosed  is Shriram's approach to functional style adaptive
programming. The description of his solution is at the end.
Some earlier messages by Doug and me are also included. He writes:
about your paper with Johan:
------------ begin quote
I too worried for a while that "recursive programming seems to require
that we are explicit at all stages", but I am less convinced now: I
think a useful set of recursive solutions *can* be described in a
"partial" manner.  That puts me in the "least modification" camp.  It
seems like these are then dual approaches.  One of my design goals
when thinking about this problem was to create something that would be
a simple, conservative extension of Demeter.  It doesn't look at first
glance like theirs is as simple.    

-- Karl
=================

From shriram@cs.rice.edu Tue Mar  9 12:24:29 1999
From: Shriram Krishnamurthi <shriram@cs.rice.edu>
To: lieber@ccs.neu.edu
Subject: rudimentary questions

Dear Karl,

The Demeter/Java user manual Web pages have me slightly confused.
Since this is a draft, maybe my questions will help as you revise this 
document?

1. In "Invoking an Adaptive Method", you present the hand-coded
version of searchForEmployee.  Yet this section suddenly begins to
discuss two things that haven't been defined:

- SearchVisitor -- Should this really be EmpSearchVisitor?  I hope
  this is only a simple typo.

- start and finish -- This is the first I'm seeing of this
  terminology.  There's start/finish, before/after, and what I have
  also called prefix/suffix (vertex) wrappers.  Are these all the
  same?  Are they all different?

2. I don't see why equals in Name has to use casts.  The code that
invokes it -- in "after Employee" -- calls it on emplname, which is
defined earlier to be of type Name.  This looks like it needlessly
subverts the type checker.

3. I don't understand the semantics of returning values.  It says
visitors fed to adaptive methods with return types must have either a
return_val or a return method.  So:

3.1 What is the type of the return method?  It says "with the given
    return type", which is clearly only 1/2 of a type description.
    Is this just a setter, or are you doing something clever like
    threading control?

3.2 Where does your EmpSearchVisitor get its return_val field?  The
    class dictionary merely says

      EmpSearchVisitor = <emplname> Name.

    Should there perhaps have been an explicit visitor declaration
    here somewhere?  Is it correct to assume that the code as
    presented would not compile?

As suggestions, it would also be nice to see examples of

- multiple visitors

  Since visitors influence the flow of control -- subtraversal.apply() 
  -- it seems like this can get *really* hairy: who gets invoked, whom 
  they invoke, how many times traversals can happen, etc.  Since just
  about everything is stateful, you then have to start reasoning about 
  effects and re-entrancy.

- return values

  I conjecture that it would be extremely ugly to write programs that
  synthesize values.  This is because the visitor would have to
  carefully evaluate each return_val and store it away, and then
  invoke the computation that works on all these values in the after.
  Naturally, I find my functional version extremely elegant for these; 
  maybe you have work-arounds that avoid the mess described above.

Thanks.

'shriram

From shriram@cs.rice.edu Tue Mar  9 13:46:23 1999
From: Shriram Krishnamurthi <shriram@cs.rice.edu>
To: Karl Lieberherr <lieber@ccs.neu.edu>
Cc: dougo@ccs.neu.edu
Subject: Re:  rudimentary questions

Is it possible to summarize this example which depends on start's and
finish's?

I think of the traversal as a functional which you can trigger by
providing it a visitor.  In this case, start and finish is just
something you wrap around the invocation of the function.  More
importantly, it sounds like your start and finish are there purely for
side-effect, which tells me they are an artifact of a world where all
communication happens through effects.  (Even your way of returning
values doesn't correspond to what I would call "returning".)  Thus, I
would be really interested in seeing what happens when I re-cast your
example into my functional style.  I'm curious whether start and
finish are an artifact of the problem or the solution.

'shriram

From lieber@ccs.neu.edu Tue Mar  9 14:00:30 1999
Date: Tue, 9 Mar 1999 14:00:27 -0500 (EST)
From: Karl Lieberherr <lieber@ccs.neu.edu>
To: lieber@ccs.neu.edu, shriram@cs.rice.edu
Subject: Re:  rudimentary questions
Cc: dougo@ccs.neu.edu

Hi Shriram:

I was asked how your approach differs from Mitch's and Johan's proposal:

http://www.ccs.neu.edu/research/demeter/biblio/traversal-automata.html

You are probably best to answer this question.

-- Karl

>From shriram@cs.rice.edu Tue Mar  9 13:46:23 1999
>From: Shriram Krishnamurthi <shriram@cs.rice.edu>
>To: Karl Lieberherr <lieber@ccs.neu.edu>
>Cc: dougo@ccs.neu.edu
>Subject: Re:  rudimentary questions
>
>Is it possible to summarize this example which depends on start's and
>finish's?
>
>I think of the traversal as a functional which you can trigger by
>providing it a visitor.  In this case, start and finish is just
>something you wrap around the invocation of the function.  More
>importantly, it sounds like your start and finish are there purely for
>side-effect, which tells me they are an artifact of a world where all
>communication happens through effects.  (Even your way of returning
>values doesn't correspond to what I would call "returning".)  Thus, I
>would be really interested in seeing what happens when I re-cast your
>example into my functional style.  I'm curious whether start and
>finish are an artifact of the problem or the solution.
>
>'shriram
>

From shriram@cs.rice.edu Tue Mar  9 15:08:23 1999
From: Shriram Krishnamurthi <shriram@cs.rice.edu>
To: Karl Lieberherr <lieber@ccs.neu.edu>
Cc: dougo@ccs.neu.edu
Subject: Re:  rudimentary questions

At first glance, it looks like parts of our solutions are extremely
similar (which should not be surprising).  But, where they dislike the
"surprise path" problem of traversals -- I am not dismissive of that
concern -- I think it is still an intersting experiment to build on
top of AP, whose main value I see is precisely the work put into
compiling traversal strategies.

I too worried for a while that "recursive programming seems to require
that we are explicit at all stages", but I am less convinced now: I
think a useful set of recursive solutions *can* be described in a
"partial" manner.  That puts me in the "least modification" camp.  It
seems like these are then dual approaches.  One of my design goals
when thinking about this problem was to create something that would be
a simple, conservative extension of Demeter.  It doesn't look at first
glance like theirs is as simple.

The first paragraph of their future work suggests problems that I
think can already be solved with the existing Demeter framework, so it 
can also be solved in any conservative extension.  This would point to 
a difference.  (I'd have to study their paper in detail to figure out
why they have that problem.)

Comments?

'shriram

From dougo@ccs.neu.edu Tue Mar  9 16:21:13 1999
From: Doug Orleans <dougo@ccs.neu.edu>
Date: Tue,  9 Mar 1999 16:21:11 -0500 (EST)
To: Karl Lieberherr <lieber@ccs.neu.edu>,
        Shriram Krishnamurthi <shriram@cs.rice.edu>
Subject: Re: response to Sriram

 > >The Demeter/Java user manual Web pages have me slightly confused.
 > >Since this is a draft, maybe my questions will help as you revise this 
 > >document?

Yes, thanks.  Unfortunately it's still a ways from being finished, but 
feedback is always useful.

 > >1. In "Invoking an Adaptive Method", you present the hand-coded
 > >version of searchForEmployee.  Yet this section suddenly begins to
 > >discuss two things that haven't been defined:
 > >
 > >- SearchVisitor -- Should this really be EmpSearchVisitor?  I hope
 > >  this is only a simple typo.

Yes, it's a typo.

 > >- start and finish -- This is the first I'm seeing of this
 > >  terminology.  There's start/finish, before/after, and what I have
 > >  also called prefix/suffix (vertex) wrappers.  Are these all the
 > >  same?  Are they all different?

Karl answered this already-- start and finish methods happen at the
start and finish of the entire adaptive method, while before and after 
methods (which used to be called prefix and suffix wrappers) happen
when the traversal gets to or leaves specific classes.

 > >2. I don't see why equals in Name has to use casts.  The code that
 > >invokes it -- in "after Employee" -- calls it on emplname, which is
 > >defined earlier to be of type Name.  This looks like it needlessly
 > >subverts the type checker.

This is a tricky Java thing.  The equals method on Object takes an
Object as argument, so all its overridden versions must also;
otherwise they won't be called when equals is invoked on the object
cast to Object.  E.g. with

    class Foo {
	public boolean equals(Object foo) { return false; }
	public boolean equals(Foo foo) { return true; }
    }

Then if foo is a Foo, foo.equals(foo) returns true, but
((Object) foo).equals(foo) returns false.  The latter case can happen
when foo is used as a key in a Hashtable, for example.

 > >3. I don't understand the semantics of returning values.  It says
 > >visitors fed to adaptive methods with return types must have either a
 > >return_val or a return method.  So:
 > >
 > >3.1 What is the type of the return method?  It says "with the given
 > >    return type", which is clearly only 1/2 of a type description.
 > >    Is this just a setter, or are you doing something clever like
 > >    threading control?

Another problem with missing documentation...  When you define a
return method on a standalone visitor class (i.e. not inside an inline 
adaptive method), you need to provide the type:

    FooVisitor {
	return int (@ 42 @)
    }

This is just syntactic sugar for

	int get_return_val() { return 42; }

When it's used inline, the return type is filled in with the return
type of the adaptive method.

 > >3.2 Where does your EmpSearchVisitor get its return_val field?  The
 > >    class dictionary merely says
 > >
 > >      EmpSearchVisitor = <emplname> Name.
 > >
 > >    Should there perhaps have been an explicit visitor declaration
 > >    here somewhere?  Is it correct to assume that the code as
 > >    presented would not compile?

Yep, this is another bug.  It should be

      EmpSearchVisitor = <emplname> Name <return_val> Employee.

 > >As suggestions, it would also be nice to see examples of
 > >
 > >- multiple visitors
 > >
 > >  Since visitors influence the flow of control -- subtraversal.apply() 
 > >  -- it seems like this can get *really* hairy: who gets invoked, whom 
 > >  they invoke, how many times traversals can happen, etc.  Since just
 > >  about everything is stateful, you then have to start reasoning about 
 > >  effects and re-entrancy.

Indeed.  This is so hairy that I never use it :)

 > >- return values
 > >
 > >  I conjecture that it would be extremely ugly to write programs that
 > >  synthesize values.  This is because the visitor would have to
 > >  carefully evaluate each return_val and store it away, and then
 > >  invoke the computation that works on all these values in the after.
 > >  Naturally, I find my functional version extremely elegant for these; 
 > >  maybe you have work-arounds that avoid the mess described above.

Yes, values have to be built up by side effect, which in some cases
involves keeping an explicit Stack of values, and yes it can get
ugly.  I had an idea for declaring a visitor to be "recursive", in
which case every edge call would involve making a new visitor object
(similar to making a new activation record-- a visitor is like a frame 
of bindings), but I never really fleshed out the idea.  I'd like to
see your solution.

--Doug

From dougo@ccs.neu.edu Tue Mar  9 16:27:35 1999
From: Doug Orleans <dougo@ccs.neu.edu>
Date: Tue,  9 Mar 1999 16:27:33 -0500 (EST)
To: shriram@cs.rice.edu
Cc: Karl Lieberherr <lieber@ccs.neu.edu>
Subject: Re:  rudimentary questions

Shriram Krishnamurthi writes:
 > Is it possible to summarize this example which depends on start's and
 > finish's?

The usual workaround for doing things at the start and finish of a
traversal was to attach before and after methods to the source class
of the traversal; this doesn't work if the source class is visited
more than once, though (if there is a cycle in the class graph).
In this case start and finish methods are the only way to do it.

 > I think of the traversal as a functional which you can trigger by
 > providing it a visitor.  In this case, start and finish is just
 > something you wrap around the invocation of the function.  More
 > importantly, it sounds like your start and finish are there purely for
 > side-effect, which tells me they are an artifact of a world where all
 > communication happens through effects.  (Even your way of returning
 > values doesn't correspond to what I would call "returning".)

Yep.

--Doug

From shriram@cs.rice.edu Wed Mar 10 03:10:27 1999
From: Shriram Krishnamurthi <shriram@cs.rice.edu>
To: Doug Orleans <dougo@ccs.neu.edu>
CC: Karl Lieberherr <lieber@ccs.neu.edu>
Subject: a functional perspective

Doug,

Here're some examples I worked through in detail in person with Karl.
If I incorrectly use a word like "strategy" or "traversal", sorry.

Overall Solution:

* Retain strategies as unchanged as possible.  We want to reuse the
  knowledge about compiling traversals, but change the behavior of what
  happens at each node during the traversal.  That is, we want to modify 
  the visitors.

* The specification must include code corresponding to *each kind of
  node* the computation may encounter on the the traversal.  (More on
  this below.)

* Each traversal has a "type".  The type is a pair, consisting of the
  "downward" and "upward" types.

  The code that corresponds to a node has the form

    \ <down> . <child> ... . <body>                 [where \ = lambda]

  <down> = var(s) of type "downward type"
  <child> ... = specified below
  <body> = any old code, return type "upward type"

(For notational simplicity, I'll assume the instance variables of a
node are bound for the visitor.  In practice, you could send the node
as an argument to the visitor.)

Where do these "child" arguments come from?  That's what the traversal
strategy compiler gives us.  It analyzes the class graph to figure out
which paths to take and, at a given node, which children to
*potentially* visit.  Now it turns these traversals into something
that the visitor at that node has control over.

Let me try to explain this with concrete examples.  I'll base my
examples on the following (extremely simple) graph, for illustration
purposes:

			      Container
				  |
			 --------------------
			|                    |
		       Leaf                Node
		      int wt             int cap
			                 Container l, r

Strategy:

  from Container to Leaf

1. Sum up all the weights in the Leaf's.

  Type: <(), int>
  Actions:
  Leaf -> \ () . () . wt
  Node -> \ () . L, R . (+ L R)

2. Check whether any Node has more weight than its cap(acity).

  Type: <(), <int, bool>>
  Actions:
  Leaf -> \ () . () . <wt, NONE>
  Node -> \ () . L, R . <(+ (fst L) (fst R)),
                         (and (snd L) (snd R)
                              (<= (+ (fst L) (fst R)) cap))>

  You can have numerous variants on this problem by adopting different 
  meanings for "more weight than" and "check".  I think it's quite
  easy to see how to encode those variants with this framework.

3. Generate a list of all weights and their depths.

  Type: <int, list(<int, int>)>
  Actions:
  Leaf -> \ depth . () . (list <depth, wt>)
  Node -> \ depth . L-comp, R-comp .
              (append (L-comp (add1 depth))
                      (R-comp (add1 depth)))

Note the difference in the type of the <child> arguments in 3 above.
Previously they had type "upward type".  Now they have type
computation("upward type").  This brings us to:

- In principle, the child arguments should be "lazy".  This is what
  gives you real power.  For instance, you can look at the down argument
  and decide which order in which to evaluate the children.  Or you
  could evaluate the left branch, and if the capacity is already too
  great, you don't need to traverse the right branch.  Etc.  But in
  practice, you will have many cases where you want to visit everyone
  and just collect up the results of visiting them.

  One convenient way to handle this issue would be to let programmers
  to tag individual actions as "strict" or "lazy".  A strict action
  propagates its "downward" arguments unchanged, has its children
  automatically evaluated, and gets as arguments values of "upward
  type".  A lazy action gets to make all evaluation choices, and gets
  as arguments the computations.  It must invoke these to get results.

  Note that this is a completely local modification, and requires no
  global knowledge or cooperation with other actions.

- This model is too restrictive.  The whole point is sometimes the
  user may not know (or want to know) all the kinds of intermediate
  nodes.  In such cases, the user can say "otherwise" for the node
  type.  Typical values attached to "otherwise" would be:

    identity = send the child values upward (if there are multiple
      children, this presupposes some sort of "multiple value return"
      mechanism)

    void = I'm doing it all w/ effects down below, so traverse all and 
      ignore values
      (Note: this corresponds to current adaptive programming.)

    append/flatten/etc = these are intermediate nodes that use
      standard combinators to collect up answers

  Therefore, another way to write the third version above is

  Leaf -> \ depth . () . (list <depth, wt>)
  Node -> \ depth . children ... .
            (apply append children)

  Then no matter how many additional types of nodes you add, leaves
  will always return a list, and the intermediate nodes will append
  together as many as it gets.

- Augmentations like before and after become simple combinators.  For
  instance,

    after (f, am) =
      \ down . child ... .
	let V = f (down, child ...)
	  am ()
	  V

  Now it becomes very easy to write arbitrarily complex behavior
  compositions, rather than just plain before's and after's.

As a sidebar, I can translate this approach very nicely to a
functional language, by using the correspondence between classes and
datatypes.  Then it just begs to be fitted together with all the
standard combinators for collecting data.

'shriram