An Algebraic Foundation for Adaptive Programming

摘要

An adaptive program is an object-oriented program which is abstracted over the particular class structure. This abstraction fosters software reuse, because programmers can concentrate on specifying how to process the objects which are essential to their application. The compiler of an adaptive program takes care of actually locating the objects. The adaptive programmer merely writes a traversal specification decorated with actions. The compiler instantiates the specification with the actual class structure and generates code that traverses a collection of objects, performing visits and actions according to the specification. Previous approaches to compiling adaptive programs rely on standard methods from automata theory and graph theory to achieve their goal. We introduce a new foundation for the compilation of adaptive programs, based on the algebraic properties of traversal specifications. Exploiting these properties, we develop the underlying theory for an efficient compilation algorithm. A key result is the derivation of a normal form for traversal specifications. This normal form is the basis for directly generating a traversal automaton with a uniformly minimal number of states.