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