@TECHREPORT{ap-f-ap-p:bryan-ahmed-theo,
AUTHOR = "Bryan Chadwick and Ahmed Abdelmeged and Therapon Skotiniotis and Karl Lieberherr",
TITLE = "{ Abstraction of Communication in Traversal-Related Concerns }",
YEAR = "2007",
INSTITUTION = "Northeastern University, Boston",
MONTH = "December",
NUMBER =  "NU-CCIS-07-75
}

Paper | DemeterF Homepage.

Notes by Karl:

Possible titles:

The Pulse of Objects.

Holistic Processing of Objects.

AP-F is an answer to the question: how should objects be processed? The first approach, called traditional, is to traverse the object manually and to keep track of temporary information in variables global to the object and in fields of the traversed object. The second appraoch, called the visitor approach is imperative as the traditional approach: traverse the object manually using one set of methods and execute imperative code in a second set of methods to update variables global to the object and in fields. The third approach, called the adaptive approach, avoids writing the traversal code and instead uses a traversal specification whereToGo together with a schema and an object whatToDo. This results in writing code in the form: schema.traverse(whatToTraverse, whereToGo, whatToDo). The whatToDo object can be organized in two fundamentally different ways: imperative or functional. In the imperative case, we have before and after and around methods in a visitor object that change the state of fields and global variables. In this paper we study a functional, adaptive approach to process objects. This approach has grown from a suggestion by Shriram Krishnamurthi some 10 years ago to combine AP with FP and resulted in a workshop publication:

@INPROCEEDINGS{func-vis1:pengcheng-shriram,
AUTHOR = "Pengcheng Wu and Shriram Krishnamurthi and Karl Lieberherr",
TITLE = "{Traversing Recursive Object Structures: The Functional Visitor in Demeter}",
BOOKTITLE = "2003 SPLAT Workshop: Software Engineering Properties for 
Languages and Aspect Technologies ",
YEAR = "2003",
ADDRESS = "Northeastern University, Boston (AOSD 2003)",
NOTE =  "http://www.daimi.au.dk/~eernst/splat03/"
}

AP-F, in its pure form, makes whatToDo a stateless function object. AP-F can be viewed as a normalized form of AP with visitors because any AP-F program can be translated into an AP program using visitors. But the converse is not true. However, we have not found the normalization to be a limitation. To the contrary, the AP-F style is currently our most promising approach to AP and to follow the Law of Demeter without violating the DRY principle. We have used AP-F and DemeterF in two courses, Principles of Programming Languages where we implemented interpreters and type checkers, and in Managing Software Development, where we implemented an algorithmic trading game based on financial derivatives using raw materials and finished products http://www.ccs.neu.edu/home/lieber/evergreen/specker/sdg-home.html.

AP-F improves on functional visitors in an important way. A key motivation behind AP is to specify code succinctly. AP has done this since its inception to specify traversal code that is enhanced by a whatToDo object and to specify copy code but without a convenient way to personalize the copy functionality. AP-F has added three convenient ways to personalize a copy: it uses multimethods to select a method to override the default copy method. It uses apply methods to transform what the copy method returns. It uses update methods to provide access to information higher up in the object when it is needed. The apply and update methods are also multimethods

Adaptive functional programming has been explored by the functional programming community. @inproceedings{ acar02adaptive, author = "Umut A. Acar and Guy E. Blelloch and Robert Harper", title = "Adaptive functional programming", booktitle = "Symposium on Principles of Programming Languages", pages = "247-259", year = "2002", url = "citeseer.ist.psu.edu/article/acar01adaptive.html" } It is different from our adaptive programming. In adaptive functional programming, an adaptive computation adapts its output to match changes to the input while in AP we adapt a program when the schema changes.

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

The goal of the Demeter work is to let as little structural information as possible spread as narrowly as possible. (A good design principle in general not only for structural information.)

To achieve little spreading of structural information, we 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 (type unifying) and TP type preserving) as special cases. We need to be careful about the terminology we introduce:

f / apply   / transformer 
b / combine / builder
a / update  / augmentor

f / apply    / transformer 
b / build    / builder
a / augment  / augmentor

http://citeseer.ist.psu.edu/kastens92modularity.html

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.

Applications:

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

Eclipse Modeling Project, Eclipse Generative Modeling technology.