This paper efficiently solves the shortcut and subclass invariance problem discussed in [PXL]. The zigzag problem is left for future work.
The paper is of importance to programmers using class-based object-oriented languages and applying the Visitor design pattern from [GHJV]. The paper shows how the straight-forward way to implement a traversal may lead to an erroneous program. A correct implementation for from-to and from-to-stop and join is provided.
Problem SI: When doing a traversal of the form [A;B] (from A to-stop B) we might suffer from a subclass invariance violation if B is abstract. (The SI problem is defined formally in [PXL]; here we specialize SI for to-stop traversals.)
Problem SC: When doing a traversal of the form [A;B].[B,C] ((from A to-stop B) join (from B to C)) , we might in addition suffer from a shortcut.
To solve the SI problem, we use for all classes in the propagation graph the same method name, except for B we use a new method name.
To solve the SC problem, we use for all classes, except B, in the propagation graph of [A;B] a method name z1 and for all classes in the propagation graph of [B,C] a method name z2. The method for B is called z1_switch. The code for B::z1_switch (glue code) calls this.z2(). The paper uses the concept of last edges to deal with the details.
As in [PXL], we assume that abstract classes don't have wrappers (visitors). The z1_switch method does not call wrappers.
The paper improves on the solution of the SI and SC problems by pushing code in abstract classes down to concrete classes so that all code defined for abstract classes is empty (code falttening). This is an optimization which leads to slightly faster and slightly shorter programs. Many more optimizations can be done to the basic algorithm.
The reason why the paper does the code flattening (and not other optimizations) is that the resulting program does not use any overriding through inheritance, except overriding of empty methods. This simplifies the semantics of the target language and the proof of correctness with respect to the [PXL] semantics. Indeed, a variant of the [PPL] semantics can be used to define the target language.
The paper achieves the code flattening by pushing the code of abstract classes down subclass paths which satisfy the appropriate part of the traversal specification.
The paper deals with a two-phase semantics: Determine traversal order and then call the wrappers or visitors. This semantics is useful for understanding traversals but is not faithful to the way adaptive programs are used in practice. The [HS] semantics and [PSL] semantics achieve a faithful semantics. It will be the topic of a future paper to show that the compiler is also correct with respect to the faithful semantics.
For references to semantics work see: http://www.ccs.neu.edu/research/demeter/semantics/semantics-of-ap.txt
A draft version of the paper is at: /proj/asl/lieber/papers/new-state-passing-compiler/new-paper.ps