Demeter/Java:
Adaptive Programming with Traversals and Visitors

by Doug Orleans
for Dr. Karl J. Lieberherr

Adaptive programming using the Demeter Method is a programming methodology (with tool support) that lets you work less, but achieve more. By specifying as little as possible about your program, you can make it

• more general and flexible
• easier to maintain
• easier to understand

The Demeter Method has three steps, performed iteratively:

• Derive a class graph. Start with the program requirements, and create a set of classes that best captures the necessary structure of your program data.
• Derive traversal methods. For each use case (program operation), find the subgraph of classes that need to collaborate to implement the behavior, and specify a path directive that visits the classes in the subgraph in the proper order.
• Derive visitor methods. Attach specific behavior (written in the underlying object-oriented language, such as Java) to certain classes that are visited along each traversal. This is the ``meat'' of your program, where things actually get done.

Using the Demeter system, you specify structure and behavior succinctly and separately. The path directives only mention the classes at the endpoints of the traversal, and the visitor methods are only specified on the classes where the behavior needs to be performed; in this way, the class graph, traversal methods, and visitor methods are only loosely coupled, allowing the program to automatically adapt to evolutionary changes in the structure or the behavior.

In the current version of the tool, Demeter/Java, behavior is encapsulated in methods on visitor classes, allowing object-oriented reuse through inheritance and polymorphism. Visitor classes are defined separately from traversal methods, so they can be reused in different combinations. (The idea of visitor classes comes from the Visitor pattern in the widely-used book Design Patterns, by Gamma, Helm, Johnson & Vlissides.)

A class graph is specified with a class dictionary file, with the filename extension .cd. You can define three kinds of classes in a class dictionary:

• Construction class (also known as concrete class), specified with a list of its part classes (data member types).

• Alternation class (also known as abstract class), specified with a list of its alternates (subclasses). An alternation class definition may also specify a list of part classes that are common to all its subclasses.

• Repetition class (also known as collection class), specified with its contained class.

A class dictionary may also be annotated with syntax strings, which are used to construct a parser that can read a text stream representing data and build corresponding object graphs. Object graphs can also be printed as text using the same syntax.

Class definitions may refer to classes (for example, as a part class) that are not defined in the class dictionary; the class must be defined in another source file or library package. This is useful for built-in Java classes such as Integer or String.

Program behavior is specified in a behavior file, with the filename extension .beh. You can define three kinds of behavior methods:

• Verbatim method -- this is passed directly through to Java.

• Traversal method -- this consists of a path directive, which describes a path through the class graph to follow, and an argument list, which specifies what types of visitor objects can use the traversal. The path directive is a list of target nodes in the class graph, with an optional set of nodes and edges to bypass.

• Visitor method -- this is a Java method that is executed when a traversal visits an object of the specified class. There are two kinds of visitor methods: before methods, which are executed immediately upon visiting the object, and after methods, which are executed after the traversal is finished traversing all the outgoing edges from the object. The object that is currently being visited can be referred to in the body of a visitor method by the variable host.

Visitor classes are defined in the class dictionary, just as any other class. There's nothing special about a visitor class except that it has before and after methods.

A visitor class may have data parts that can be referred to in the visitor methods; these are useful for transporting data from one part of the traversal subgraph to another.

A visitor class may itself define a traversal method, which could be called with other visitor objects; traversing a visitor may often be necessary if the visitor class has composite data members.

Here's an example class dictionary file:

// A construction class.
Computer = <parts> EquipmentList.

// A repetition class.
EquipmentList ~ { Equipment }.

// An alternation class with common parts,
// and some empty construction classes.
Equipment : Card | Drive | FloppyDisk | CompositeEquipment
    *common* <netPrice> Currency "discount" <discountPrice> Currency.
Card = "card".   Drive = "drive".   FloppyDisk = "floppy".

CompositeEquipment : Cabinet | Chassis | Bus
    *common* "(" <parts> EquipmentList ")".
Cabinet = "cabinet".   Chassis = "chassis".   Bus = "bus".

// Some visitor classes.
PricingVisitor = <total> Currency.
InventoryVisitor = <inventory> Inventory.

Here's an example behavior file to go with it:

Computer {
  traversal allEquip(PricingVisitor price, InventoryVisitor inv) {
    bypassing -> CompositeEquipment,parts,* to Equipment;
  }
}

PricingVisitor {
  before Equipment (@ total = total.add(host.get_netPrice()); @)
  // Chassis are on sale...
  before Chassis (@ total = total.add(host.get_discountPrice()); @)
}

InventoryVisitor {
  before Equipment (@ inventory.accumulate(host); @)
}

(example behavior file continued)

Main {
(@
  static public void main(String args[]) throws Exception {
    Computer comp = Computer.parse(System.in);

    PricingVisitor price = PricingVisitor.parse("$0");
    InventoryVisitor inv = InventoryVisitor.parse("");

    comp.allEquip(price, inv);

    System.out.println("Price = $" + price.get_total());
    System.out.println("Inventory: " + inv.get_inventory());
  }
@)
}

Notice a few things about this example program:

• Two visitors are executed ``in parallel'' as the object graph is traversed; that is, as each object is traversed, both visitor objects' methods are executed. This can be more efficient (and can make the code simpler) than performing multiple traversals.
• The ability to create composite objects by parsing them from files or strings is much simpler than having to explicitly construct all the layers of the object. More importantly, it lets the program automatically adapt to changes in the class graph.

Directions for future development:

• Syntactic sugar, to make the language easier to use
• Dynamic traversal specifications (defined at runtime)
• Support for distributed object graphs
• Parallelism: multiple visitors, collection class traversal
• Graphical development tools

• About this document ...