Traversals of Object Structures: Specification and Efficient Implementation

We present a new approach, called strategies, to the task of traversing object structures. In our approach traversals are defined using a high-level directed graph description, which is compiled into a dynamic road map to assist run-time traversals. The complexity of the compilation algorithm is polynomial in the size of the strategy graph and the class graph of the given application. The implementation is practical and allows for dynamically creating and modifying the existing traversal strategy. A prototype of the system has been developed and is being successfully used. Previous approaches to traversal specifications were less general (corresponding to either a series-parallel or a tree graph), and their compilation algorithms were of exponential complexity in some cases. In an additional result we show that this bad behavior is inherent to the static traversal code generated by previous implementations, where traversals are carried out by invoking methods without parameters.

Click here for full paper.

Boaz Patt-Shamir
Last modified: Mon Sep 8 11:19:16 PDT 1997