AUTHOR = "Bryan Chadwick and Karl Lieberherr",
TITLE = "{Functional Adaptive Programming}",
YEAR = "2008",
INSTITUTION = "CCIS/PRL, Northeastern University, Boston",
MONTH = "October",
NUMBER =  "NU-CCIS-08-75

Paper | DemeterF Homepage.

Notes by Bryan and Karl:

This paper presents a significantly improved version of DemeterF and it adds a high-level description of the new DemFGen. DemeterF became simpler (only update and combine methods) and it acquired new features based on user feedback and the use of its own technology. (DemeterF is now implemented in DemeterF).

Currently, DemeterF is the best implementation of the visitor pattern: every other implementation is either hard wired (traversal wise) or forces you to encode traversal order in side effects.

When we write the functional visitors we make assumptions about the structure. To do this we need to either use names to refer to fields (this is standard) or we rely on the ordering of the fields and refer to them indirectly by number (this is non-standard and used by DemeterF). Like with higher-order functions, we really get to name the fields whatever we want (method argument names), but part of the contract is that the traversal passes them in the right order (given by the field order) to our "functions". To rely on the ordering makes programs dependent on the ordering of fields. On the other hand, we rarely have to refer to fields by name.

When fields are permuted, the combine method arguments need to be permuted with the same permutation to keep the program functioning identically. As in the standard approach, the constructors need to be updated by permuting the arguments.

When a new, but unused, field is added in the middle, the combine methods get a new argument added at the same position (unless the argument list did not "go that far").

Therefore, new, unused fields should be added at the end of existing fields to avoid updates to combine methods. Those updates, can however be done automatically with IDE support.

The "optional" fields (arguments which are not needed) are simply a convenience and can be eliminated (simple change). But, they give the programmer quite a bit of flexibility.

One of the major benefits of DemeterF (which actually leads to the parallelizability) is that when programming functionally, the order of sub-traversals doesn't matter, since we say how to combine the results. This also allows us to optimize the traversal and gives the implementor more flexibility.

There are situations where the order of subtraversals matters. Consider the implementation of an if-then-else-expression in some programming language. We use traversal control, to avoid traversing the then and else expressions before the if expression is evaluated.

The benefit of plain imperative visitors is the fact that we only need single dispatch, then we can emulate double dispatch.