Incremental graph evaluation (attribute grammar)
Roger Hoover · 1987
There are many computer applications that can be made incremental. After a small perturbation to the computation at hand, intermediate values of a previous evaluation can be used to obtain the result of the new computation. This requires less time then reevaluating the entire computation. We propose the use of a directed graph to represent computations that we wish to make incremental. This graph, called a dependency graph, represents an intermediate computation at each vertex. Edges between vertices represent the dependence of intermediate computations on other intermediate computations. A change to the computation can be represented as a change in the dependency graph. Given a dependency graph and a dependency graph modification, we wish to update all intermediate computations to be consistent with the intermediate computations on which they depend. This thesis is a study of the updating process, known as incremental graph evaluation. Graph propagation is a simple technique that restores a modified dependency graph to consistency. We briefly review a number of propagation algorithms that have been used for incremental evaluation and introduce several new graph propagation algorithms. We show that by performing graph propagation on an improved, but equivalent, dependency graph, incremental graph propagation can be accelerated. The improvement is obtained by replacing indirect communication in the dependency graph with direct communication. Since the indirect communication is inherent in many dependency graphs, the time required by incremental graph evaluation can be decreased substantially. We present algorithms to incrementally maintain a data structure, called a structure tree, which we use to explicitly represent the indirect communication. We apply the structure tree algorithms to explicitly represent two types of indirect communication, copy rule chains and aggregates, which frequently occur in dependency graphs. The explicit dependencies are updated to reflect changes in the dependency graph. Propagation over the improved dependency graph is optimal with respect to these classes of indirect communication, resulting in a substantial, practical improvement in the speed of incremental graph evaluation.