Hi Will:

an interesting discussion we have here.

>From will@ccs.neu.edu Tue Jan  6 17:28:40 1998
>From: William D Clinger <will@ccs.neu.edu>
>Reply-To: will@ccs.neu.edu
>Organization: Northeastern University
>To: Karl Lieberherr <lieber@ccs.neu.edu>
>CC: wand@ccs.neu.edu, dem@ccs.neu.edu, jcurry@ccs.neu.edu, lblando@ccs.neu.edu,
>        palsberg@cs.purdue.edu, will@ccs.neu.edu
>Subject: Re: Not jumping to conclusions [was: Eliminating the professor's code]
>
>Karl wrote:
>> I know what you mean by pre-order and post-order but what does
>> in-order mean for an object?
>
>>From Knuth, Volume 1, second edition, page 316:
>
>    Three principal ways may be used to traverse a binary tree:
>    we can visit the nodes in preorder, inorder, or postorder.
>    These three methods are defined recursively.  When the binary
>    tree is empty, it is "traversed" by doing nothing, and
>    otherwise the traversal proceeds in three steps:
>
>        Preorder traversal                  Inorder traversal
>
>    Visit the root                      Traverse the left subtree
>    Traverse the left subtree           Visit the root
>    Traverse the right subtree          Traverse the right subtree
>
>                         Postorder traversal
>
>                     Traverse the left subtree
>                     Traverse the right subtree
>                     Visit the root
>
>I was abusing the word "in-order" to mean a combination of preorder,
>inorder, and postorder, in which you
>
>    Visit the root (phase 1)
>    Traverse the left subtree
>    Visit the root (phase 2)
>    Traverse the right subtree
>    Visit the root (phase 3)
>

This is a good example and shows a need for a strategy
sequencing operator which we don't have yet:
We define two strategies gauche and droite.

gauche =
{-> Root Left
 -> Left *} in pre-order // for example

droite =
{-> Root Right
 -> Right *} in post-order // for example

your =
seq(gauche, droite)

The code for the 3 phases goes into the methods (expressed in visitors):
your.gauche.Root.before: phase 1
your.droite.Root.before: phase 2
your.droite.Root.after : phase 3

seq is an operator for sequencing strategies; the arguments
must have the same source.

>
>This is for binary trees.  Abstract syntax trees have variable
>degree, so the number of visitors that need to be defined depends
>upon the kind of node being traversed.  Often each phase of the
>visit must use information that is obtained by other phases, so
>the visitors must communicate.  Often the order in which subtrees
>are traversed depends upon information that is obtained by
>traversing other subtrees.
>

Mira has proposed a solution to improve communication between
visitors. You just say next.return() to get the result
of a collaborating visitor during the traversal.

>
>It seems to me that these complications dilute the advantages of
>Demeter-style adaptive programming over conventional code.  I think
>Lars was making this point also; for example, his complaint about
>"rampantly imperative visitors" reflects the difficulty of getting
>separate visitor phases to communicate without resort to side effects,
>whereas it is easy to avoid side effects when writing conventional
>code for the same traversal.
>
I see: that is what Lars meant. Again, I think Mira's work
on Rondo helps with this.
>
>Mira wrote:
>> As I understand it,
>> in general the core of the AP is to separate the definition of a
>> computation into a succinct description of the data structure involved
>> in the computation (which is generally a graph) together with the data flow
>> over this structure and the specific computations to be performed
>> in the interesting nodes of the structure. The main point here is
>> that only interesting nodes are mentioned in both the description of the
>> data structure and computations. Interesting nodes are those that
>> "actively" play a role in the computation, as opposed to those
>> that are "accidentally" ivolved mainly for further transmitting
>> the computation and data.
>
>This paragraph remains true if we substitute "attribute grammars" for
>"AP".  It sounds as though it would be useful to compare attribute
>grammars with adaptive programming.  For example:
>

The idea of grammar-shy attribute grammars is slowly evolving in the
attribute grammar community.

@ARTICLE{kastens:waite,AUTHOR = "U. Kastens and W. M. Waite",
TITLE = "Modularity and reusability in attribute grammars",
JOURNAL = "Acta Informatica",YEAR = 1994,PAGES = "601-627",MONTH = "",
VOLUME = 31,NUMBER = ""

Here is a quote:

Direct formulation of remote dependence reduces the size of an attribute grammar, but an even more important characteristic is that it abstracts from the intermediate tree structure. It is invariant with respect to modifications of that structure, a requirement for reuse of attribute grammar modules from libraries. 


>
>Attribute grammars (as usually defined) require the data structure
>to be a tree, whereas adaptive programming allows arbitrary graphs;
>on the other hand, adaptive programming (as defined in Demeter?)
>requires the propagation patterns to be almost-regular, whereas

An interesting word here: "almost-regular". Maybe you mean the traversal
specifications with Jens in the TOPLAS paper which have
a regular flavor. But with the Boaz paper

ftp://ftp.ccs.neu.edu/pub/people/lieber/strategies.ps

strategies are general graphs.

>attribute grammars can express any computable traversal pattern.
>
>Will
>

-- Karl