Pattern name: Structure-shy Traversal

Intent

Succinctly represent an operation to be performed on the elements of an object
structure. Structure-shy Traversal gathers the code describing the traversal
in one place with minimal dependency on the class structure.
Commit only to a navigation strategy and specify navigation details
later.  Improve the Visitor pattern from [GOF] and make it more versatile.

Also Known As:

Adaptive Traversal,
Structure-shy Walker,
Traversal Strategy


Motivation

For an operation to be performed on an object structure, usually many of the
objects involved are accidental and not of inherent importance.
Those objects have only simple traversal behavior and their methods
are quite small. Statistics of object-oriented systems show
that a large fraction of the methods in an application are very short.
Those short methods are usually for object traversal.

When several traversals have to be performed on an object structure,
the tiny methods become a nuisance since they encode the details
of the class structure into the methods. 
This leads to software
which is heavily redundant and not reusable when
the object structure changes.

When writing a program it would be ideal if we could look into
the future to see how the program would evolve. We could then
write the persistent parts of the program and reuse it to create
the transient versions of the program. 
When we use Structure-shy Traversal we make
a guess at how we think that the program will evolve.
We write navigation specifications which we think will be robust
over the versions of the program. This way we try to capture
the persistent architecture of the program and we write the
architecture in
such a way that it is easy to construct implementations of
the architecture which are the evolutionary versions of
the program. The architecture will help us to preserve
integrity of the program as we move from version to version.



Applicability

Use the Structure-shy Traversal pattern when

        An object structure contains at least two classes of objects
        and you want to perform operations involving a group of objects.
        You want to avoid polluting the classes with many simple
        methods.

 	You want to plan for expected and unexpected evolution.

        The classes defining the object structure may change often
        and you may often want to define new operations over the structure.
        (Notice here the difference from 
	the Visitor Pattern from [GOF], where 
        changes to the class structure are costly.)

Solution

Use succinct traversal specifications for expressing the
traversal strategy. Candidates are:

from A to B

from A CONSTRAINT to B
  where CONSTRAINT is a path constraint like 
  "bypass edge e"
  "at C through edge f"
  via C 
  etc.

join two traversals

etc.

Consequences

	Program becomes shorter, and more reusable in many cases. A paradox!

	Program will adapt to many changes in class structure.

        Structure-shy Traversal makes adding new operations easy, even with
        modified traversals. 

        The Structure-shy Traversal pattern uses a 
	powerful iterator that not only iterates
        through lists but through any kind of object structure.


Implementation

The implementation of the Structure-shy Traversal pattern can be done like
the implementation of traversals with propagation patterns. 
See
http://www.ccs.neu.edu/research/demeter/biblio/dem-book.html
for explanation (chapters 7, 8, 9, 15).

For an adaptive implementation in C++ of traversal specifications
(from-to and bypassing) see:
http://www.ccs.neu.edu/research/demeter/sources/DemeterJava/sourceC++/Java
Demeter/Java Source (in Demeter/C++).

For Perl implementations for Perl and C++, see:
Demeter/Perl in Perl.
Small Demeter/C++ in Perl.

For adding behavior to the traversals, see the 
Selective Visitor pattern.

Succinct traversals can be specified in different ways:

- using primitives from-to, join, merge
  This leads to "positive" traversals specifications and to
  the consistency problem. It can be resolved by either using
  restrictions on the allowed customizers or by using a
  complex compilation algorithm. See the TOPLAS '95 
  (http://www.ccs.neu.edu/research/demeter/biblio/compile-ap.html)
  and ESOP' 96 papers.
  (http://www.ccs.neu.edu/research/demeter/biblio/compile2-ap.html)


- using primitive from-constraint-to, where constraint is a bypassing
  constraint. This does not lead to a consistency problem. 

- adding join to the previous primitives. Can be compiled
  without consistency problems. 

- adding "from A 
	    at B through e1, ... ,en
          to C" to the previous primitives
  does not cause consistency problems. The meaning is that
  at class B we must go through the given edges. All other
  edges are bypassed.
  See the meta-object protocol paper:
  http://www.ccs.neu.edu/research/demeter/biblio/ap-reflect.html




Known Uses

The Structure-shy Traversal pattern is used extensively in the implementation
of the Demeter Tools/C++ and in applications written with the
Demeter Tools [DEM].

The database community has been working on structure-shy queries.
Those are queries that are relatively independent of the structure
of the schema.
See the thesis by Coleman Harrison reachable from URL:

http://www.ccs.neu.edu/home/lieber/theses-index.html

The functional programming community has been working on
polytypic programming. See

http://www.cs.chalmers.se/~johanj/polytypism.html

and [POLYTYPIC].

--------------------------------------------------
The area of ontological commitment is related to structure-shy
behavior. Put simply, an ontology consists of a set of 
objects and relationships
between them. For more detail:
http://www-ksl.stanford.edu/kst/what-is-an-ontology.html

T. Gruber writes in [Gruber 1993, Report KSL 93-04,
Knowledge Systems Laboratory, Stanford]:
"An ontology should make as few claims as possible about 
the world being modeled to allow the agents committed to the ontology freedom
to specialize and instantiate the ontology as needed."
This is called minimal ontological commitment.

For more info on ontological commitment see:

http://www-ksl-svc.stanford.edu:5915/
--------------------------------------------------

In summary, the Structure-Shy-Traversal pattern has been 
reinvented several times: In databases, attribute grammars,
functional programming and software engineering. The software engineering
community has developed the concept to 
considerable depth [EFF-IMPL1, EFF-IMPL2] and:

http://www.ccs.neu.edu/research/demeter



Sample Code

Traversal
CESM = from Company via Employee via Salary to Money
ESM = from Employee via Salary to Money

// print names of all employees who earn more than $100000
operation void select_more_than_100000
  // traverse and do additional work using visitors
  this -> CESM() 
    // first visitor
    // broadcast the employee name down;
    // it is available in member n of a BROADCAST object b
    ::+ b:BROADCAST <n, name, Name>:ESM
    // second visitor
    // select desired objects using work done
    // by earlier visitors
    ::+ SELECT <Money, val > 100000,cout  << b->n>

// visitor definitions are like class definitions
class BROADCAST  <v,i,T> {
  T* v; 
  source(thisTraversal)::{v=i;}}

class SELECT <c,cond,action> {
   c::{if (cond) action}}



Exercise:

Define a notation to express adaptive traversals.


References

DEM:
@BOOK{karl:demeter,
AUTHOR = "Karl J. Lieberherr",
TITLE = "Adaptive Object-Oriented Software:
The Demeter Method with Propagation Patterns",
PUBLISHER = "PWS Publishing Company, Boston",
YEAR = "1996",
NOTE = "ISBN 0-534-94602-X"
}



POLYTYPIC:
@INPROCEEDINGS{jeuring:structure-shy?,
AUTHOR = "Johann Jeuring",
TITLE = "Polytypic pattern matching",
BOOKTITLE = "Conference Record of FPCA '95,
SIGPLAN-SIGARCH-WG2.8 Conference on 
Functional Programming and Computer Architecture",
YEAR = "1995",
ADDRESS = "San Diego",
PAGES = "238--248",
EDITOR = "",
PUBLISHER = ""
}
http://www.cs.chalmers.se/~johanj/polytypism.html


EFF-IMPL1:
@ARTICLE{lieber-palsberg-xiao94,
AUTHOR = "Jens Palsberg and Cun Xiao and Karl Lieberherr",
TITLE = "Efficient Implementation of Adaptive Software",
JOURNAL = toplas ,
YEAR = 1995,
PAGES = "264--292",
MONTH = mar,
VOLUME = 17,
NUMBER = 2
}

EFF-IMPL2:
@INPROCEEDINGS{gener-comp:jens-boaz-karl,
AUTHOR = "Jens Palsberg and Boaz {Patt-Shamir} and Karl Lieberherr",
TITLE = "A New Approach
to Compiling Adaptive Programs",
BOOKTITLE = "European Symposium on Programming",
YEAR = "1996",
ADDRESS = "Linkoping, Sweden",
PAGES = "280-295",
EDITOR = "Hanne Riis Nielson",
PUBLISHER = "Springer Verlag"
}

GOF:
@BOOK{gang-of-4,
AUTHOR = "Erich Gamma and Richard Helm and Ralph Johnson and John Vlissides",
TITLE = "Design Patterns: Elements of Reusable Object-Oriented Software",
PUBLISHER = "Addison-Wesley",
YEAR = "1995"
}

==========================================================================


To other patterns of pattern language for AP


To Demeter home page


To Design Patterns Home Page