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.