AUTHOR = "Bryan Chadwick and Therapon Skotiniotis and Karl Lieberherr",
TITLE = "{Functions and Traversals in Combination}",
YEAR = "2007",
INSTITUTION = "Northeastern University, Boston",
MONTH = "October",
NUMBER =  "NU-CCIS-07-07

Paper | DemeterF Implementation.

Notes by Karl:

First a description of the significance of the work of Bryan and Ahmed (and Theo).

The goal of the Demeter work is to reduce active calling and instead use passive triggering. This makes modules more reusable. Both DemeterF and DemeterP use interesting new passive triggering techniques.

Both specifications as well as implementations of functional and object-oriented approaches suffer from two major problems: they explicitly mention by name the subterms or subobjects that need to be traversed (explicit traversal problem) and they explicitly mention parameters that are passed down to subterms or subobjects, whether or not they are relevant to the current term or object (explicit argument problem). The reason for the two problems is a low-level use of "follow the structure" or "follow the grammar" idea that goes back to Frege's Begriffsschrift (1879): the meaning of a phrase is a function of the meaning of its constituents. Examples of works that suffer from both the explicit traversal and the explicit argument problem are EoPL3 by Friedman and Wand and HtDP by Felleisen et al.

We pursue two structure-shy approaches that deal with the explicit traversal and explicit argument problem. Both use the idea that a traversal is specified separately from the interesting code and that the traversal has the meaning of transforming an object into another object. A program P(T) parameterized by a data type T is structure-shy if it is immune to some interface changes of T. This strengthens information hiding: traditional information hiding protects against changes to the implementation of T while structure-shy programming, in addition, protects against some changes to the interface of T.

The first approach by Chadwick et al., called DemeterF (F for functional), is a functional approach where a traversal is parameterized by 3 objects: a transformer, a combiner and an augmentor. If the combiner is not used at all, i.e., the default combiner that copies the object is sufficient, the structure-shyness is excellent. We only need to write transform methods and augment methods for the objects where a non-identity transformation or augmentation takes place. This avoids the explicit argument problem. If the combiner needs to be modified in a type-unifying way then often several combine methods need to be written. The combine methods don't refer to names of subobjects; instead they assume that results flow back to them from the subobjects. This avoids the explicit traversal problem. In addition we achieve better structure-shyness by using pattern matching to select the correct combine methods to be called. Often "generic" combine methods can be written that don't depend on the detailed structure of the objects being traversed.

The 3 objects, transformer, combiner and augmentor, could be appropriately called aspects, a term used in aspect-oriented programming (AOP). The methods in those objects are not called directly by the programmer but they are called as a side-effect of the execution of a program. In DemeterF, it is the execution of a traversal that will trigger the execution of the methods. For example, the combine method "R combine(X x)" will be executed when the traversal is done with visiting an X object.

The combine methods need to be "complete" to properly propagate information up the objects. "Complete" means that they cover all combinations of signatures that can occur. This depends on the class graph / data types and the traversal strategy. The completeness can be checked dynamically (complete for a given input) or statically (complete for all possible inputs).

The second approach by Abdelmeged et al., called DemeterP (P for interPosition) is based on traditional structure-shy programming combined with interposition visitors that contain interposition variables. In addition, composition of interposition visitors is predominant. Basic building blocks of visitors are a copier visitor (corresponding to the combiner above) and an editor visitor (corresponding to the transformer above). The role of the augmentor above is played by interposition variables that are updated during the traversal.

Benefits of both approaches: Code for classes that have default behavior does not have to be written. Uninteresting traversal and parameter passing code is eliminated. The code becomes immune to structural extensions where the default behavior is sufficient or where the current behavior properly generalizes.

How can we detect whether for a structural extension the default behavior is sufficient or the current behavior properly generalizes? Demeter Interfaces. The constraints that we write in Demeter interfaces try to detect situations where the default behavior is not sufficient or where the current behavior does not properly generalize.

What is new with respect to traditional AP? The default behavior is now richer. Instead of having simple traversals that are modified by simple aspects (visitors with before and after methods), we have now traversals that are modified by customizable copying visitors and other aspects that enhance the traversal.

end of description of significance.

This paper introduces a new traversal component model that supports TU and TP as special cases. We need to be careful about the terminology we introduce:

f / apply   / transformer 
b / combine / builder
a / update  / augmentor
Do we need both the second and third column? Could we use:
f / apply    / transformer 
b / build    / builder
a / augment  / augmentor


http://eli-project.sourceforge.net/ is important related work on attribute grammars. This work introdcues structure-shyness into attribute grammars.

Ralf Laemmel writes in his Scrap your XML-plate paper.

in section 5: "... the AP setup is specifically meant to enable powerful meta-data-aware optimization that lets traversals cease as early as possible. Generic functional programming (including SYB) should feel some urgency about catching up with AP in this area".

AP is not only good for optimization but also for flexible expression of where to go in a value. The optimization is a nice benefit but what is more important is that strategies allow us to flexibly choose subobjects. For example, when Bryan writes a structure-shy interpreter, he needs a traversal that goes everywhere, except into the then and else part of an If expression and the body part of a lambda expression.

Acording to Therapon Skotiniotis, FP should not only catch up with AP, but AP should also catch up with FP. This paper achieves some of the catch up and our ECOOP 2006 paper on Demeter interfaces also plays catch up in another direction.

Our ECOOP 2006 paper is addressing a fundamental problem with SYB: when you scratch your boiler plate your code might work with a new data type of the same kind but sometimes it does not. Our paper formalizes static conditions that need to hold for the SYB program to work.


M2M transformations (model to model transformations), QVT (Query/Views/Transformations), ATLAS transformation language.

M2T transformations (model to text transformations), MOF models to text, MOFScript.

Eclipse Modeling Project, Eclipse Generative Modeling technology.