Structure sharing in incremental systems

Henning Christiansen
Department of Computer Science
Roskilde University, P.O.Box 260, DK-4000 Roskilde, Denmark

The set of attributes in a syntax tree maintained by a syntax-directed editor is a typical example of a system of interdependent variables: The value of each variable is defined by an expression which may involve other variables in the system. Similar systems appear, for example, in the implementation of logic programming languages and in object-oriented systems. This paper describes a structure sharing representation of such general systems based on a systematically derived, alternative interpretation of the defining expressions. Structure sharing yields a compact data reporesentation and implies an efficient incremental maintenance of consistency when the system develops over time. However, these systems may concern not only structural objects but also atomic entities determined by arbitrary functions; hence only a partial use of structure sharing is meaningful. The propagation of changes in these hybrid, shared and non-shared systems is measured by an abstract interpretation, the so-called flow algebra. The flow algebra is useful for scheduling updating algorithms as well as for proving their correctness. With respect to syntax-directed editors based on attribute grammars, the results in the present paper provide an immediate improvement of existing incremental algorithms. The structure-sharing is also shown to apply for non-incremental, parsing-based systems.

Structured Programming, 10/4, pp. 169-186, 1989.