Three patterns are behind Adaptive Programming:

Class Graph
Structure-Shy-Object
Adaptive Visitor (Structure-Shy-Behavior)

We discuss them in turn:

Pattern name: Class Graph

Purpose:

Classes and their structural relationships 
are used in numerous ways during software
development. Therefore, it is important that they be stored explicitly
in one place from where they can be accessed.
To make your application more robust to changes in class structure,
automate the definition of class graph induced operations such as
copying, displaying, printing, checking etc. 
Couple the rest of the application only loosely to the class graph
so that it is robust to class graph changes.


Also known as:

Class Diagram, Class Dictionary

Applicability:

For every application one or several class graphs are needed.


Implementation:

A variety of formalism are available to define class graphs
from the 30 plus design methods.

Provide the class graph induced operation implementations by a tool
which translates the class graph.


Related Patterns:

Structure-shy Object.
The Reflection pattern [Siemens]: the class graph may be 
viewed as a meta object.


Known Uses:

Demeter Tools, Rational Rose, etc.


References

Chapter 6 in [DEM] describes the pattern in detail.
For further references, check the bibliographic section of
that chapter.

Exercise

Develop a textual language to describe class graphs.
As source of ideas use existing OO methods such as Booch, OMT
or Fusion. Write a grammar for your language using your
favorite grammar notation.
====================================================================

Pattern name: Structure-Shy Object 

Purpose:

To make object descriptions independent of class names and robust
to changes of class structure, augment the 
class graph to make it a grammar for parsing objects. 


Also known as:

Object Parsing, Grammar, Syntax Tree


Motivation:

During evolution of an application class structures frequently change
which implies updates to application objects. There is a strong need
to use object representations which are robust under class structure changes.
The creational patterns in [GOF] also recognize this need.
The Structure-Shy Object pattern is a useful additional creational pattern.
It is one of the most effective creational patterns.


Applicability:

The pattern is useful to object-oriented designs of any kind.
It is especially useful for reading and printing objects in
user-defined notations.

An example of a poor design which can be improved by Structure-Shy Object is
a design which contains many constructor calls to build
composite objects.

Structure-Shy Object is very helpful when you design a new language 
over which you have syntactic control
and which you need to implement using classes.

Structure:

The pattern extends the application class structure so that each object
knows about a parse and print function.
An extension to the class structure definition defines
the syntax of the objects.


Example:

Consider class definitions for fruit baskets:

A Class named:  Basket 
   Which is a concrete class containing the following parts:  
      A labeled part with label: contents which is of class  Apple 
End of class definition. 

A Class named:  Apple 
   Which is a concrete class containing the following parts:  
      A labeled part with label: v which is of class  DemNumber 
End of class definition. 

We use the shorter class dictionary notation:

Basket = <contents> Apple.
Apple = <v> DemNumber.

To describe a specific fruit basket, we would like to use the following
description:

object AppleBasket

basket apple weight 35 end

and to automatically produce the corresponding object:

: Basket ( 
   < contains > : Apple ( 
      < v > : DemNumber "35" ) )

To achieve this, we decorate the class dictionary with syntax:

Basket = "basket" <contents> Apple "end".
Apple = "apple" "weight" <v> DemNumber.

What is the benefit? The basket representations are very robust!

Consider the following class dictionary:


A Class named:  Basket 
   Which is a concrete class containing the following parts:  
      The string:  "basket" 
      A labeled part with label: contains which is of class  List 
         With parameters:  class  Thing 
      The string:  "end" 
End of class definition. 

A Class named:  Thing 
   Which is an abstract class that is a:  
      class  Fruit  or a  class  Basket 
      Each of which has the following common parts:  
      End of common parts. 
End of class definition. 

A Class named:  Fruit 
   Which is an abstract class that is a:  
      class  Apple  or a  class  Orange 
      Each of which has the following common parts:  
         A labeled part with label: weight which is of class  Weight 
      End of common parts. 
End of class definition. 

A Class named:  Apple 
   Which is a concrete class containing the following parts:  
      The string:  "apple" 
End of class definition. 

A Class named:  Orange 
   Which is a concrete class containing the following parts:  
      The string:  "orange" 
End of class definition. 

A Class named:  Weight 
   Which is a concrete class containing the following parts:  
      The string:  "weight" 
      A labeled part with label: v which is of class  DemNumber 
End of class definition. 

A Class named:  List 
   Having the following parameters:  S 
   Which is a repetition class containing:  
          Multiple occurances of the following:  
            Instances of the class: class  S 
End of class definition. 

In class dictionary notation:


Basket = "basket" <contains> List(Thing) "end".
Thing : Fruit | Basket.
Fruit : Apple | Orange *common* <weight> Weight.
Apple = "apple".
Orange = "orange".
Weight = "weight" <v> DemNumber.
List(S) ~  {S} .

The same basket description AppleBasket 
now defines the object:

: Basket ( 
   < contains > : Thing_List { 
      : Apple ( 
         < weight > : Weight ( 
            < v > : DemNumber "35" ) ) } ) 


Consequences:

Use of the Structure-Shy Object pattern leads to more robust and shorter
object descriptions. It also results in easier testing of class
structures before programming starts.

The price we pay is that the syntax needs to be added carefully
into the class dictionary to guarantee unique readability of the object
descriptions. A variety of parsing conditions can be used like 
the LL(1) parsing conditions. Any class dictionary can be made to satisfy
the LL(1) conditions by adding more syntax to it. Therefore,
using the Structure-Shy Object pattern does not limit the object oriented
design space.

Using the Structure-Shy Object pattern has a positive effect on class design.
It allows to test class structures for completeness in representing
test objects. The class designer gets early feedback regarding
structural completeness.

The Structure-Shy Object pattern is very easy to use by someone who knows
the concept of a grammar and how a grammar is used to parse sentences.
It is even easier to use by language designers who design
application specific little languages.


Implementation:

A variety of formalism are available to define grammars.
Use the one you are familiar with and change it to make
it also a class definition formalism defining both the classes
and a grammar. We have used EBNF (Wirth) and modified it
to make it simultaneously a class definition notation.

There are two ways to implement the parsing: a parser generator 
like YACC can be used or a generic parser can be written.
Various parsing strategies can be used, like LL, LR, LALR
with LL(1) being the best in most cases.

Use of a generic parser is recommended. It requires automatic
generation of functions to access data members by index.
Consider the Reflection pattern [Siemens] to implement the
generic parser.


Related Patterns:

The Builder pattern and other creational patterns in
[GOF] also attempt robust object definitions.
The Interpreter pattern [GOF] uses a similar idea but fails to
propose it for general object-oriented design. 
The Structure-Shy Object pattern is useful in conjunction with the Prototype
pattern; it can be used to create the prototype in a structure-shy way.


Known Uses:

Demeter Tools, T-gen, applications of YACC, Beta and many more.


References

Chapters 11 and 16 in [DEM] describe the pattern in detail.
For further references, check the bibliographic section of
those chapters.

Exercise:

Use your favorite grammar notation and modify it to also make
it a class graph notation.
===================================================================

Pattern name: Adaptive Visitor

Intent

Improve the Visitor pattern from [GOF] and make it more versatile.
Succinctly represent an operation to be performed on the elements of an object
structure. Adaptive Visitor gathers the code describing the traversal
in one place with minimal dependency on the class structure.

Also Known As:

Structure-shy behavior


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 operations 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 Adaptive Visitor 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 Adaptive Visitor 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.

        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, where 
        changes to the class structure are costly.)

Solution

Use succinct traversal specifications. 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


Consequences

        Adaptive Visitor makes adding new operations easy, even with
        modified traversals. 

        The Adaptive Visitor pattern uses uses a 
	powerful iterator that not only iterates
        through lists but through any kind of object structure.


Implementation

The implementation of the Adaptive Visitor pattern can be done like
the implementation of propagation patterns. 
An alternative implementation is in terms of context objects.


Known Uses

The Adaptive Visitor pattern is used extensively in the implementation
of the Demeter Tools/C++. 


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 programs.
==========================================================================
References


T-gen:
@ARTICLE{graver:tgen,
AUTHOR = "Justin O. Graver",
TITLE = "T-gen: a string-to-object translator generator",
JOURNAL = joop,
YEAR = 1992,
PAGES = "35-42",
MONTH = "September 1992",
VOLUME = 5,
NUMBER = 5
}

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"
}

Siemens:
@BOOK{buschmann:pattern-oriented,
  AUTHOR = "Frank Buschmann et al.",
  TITLE = "Pattern-oriented Software Architecture",
  PUBLISHER = "John Wiley and Sons", 
  YEAR = "1997", 
  SERIES = "",
  VOLUME = "",
  NOTE = "ISBN = 0-471-95869-7"
  }

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" 
}
===================================================================