Oege de Moor and Ganesh Sittampalam
Revised October 2003, 24pp.
Acar, Blelloch and Harper proposed a new algorithm for change propagation, which maintains a dynamic dependence graph augmented by time stamps. The crux of their algorithm is that the time stamps can be maintained using the ordered list structure of Dietz and Sleator, yielding only constant time overheads on a full run, and O(log n) overheads on incremental update operations, where n is the number of steps in the full run. Like any pure form of change propagation, it performs well for ``deep'' changes in an input structure, for instance near the terminals of a syntax tree. This contrasts with the use of memoisation, which performs well for ``shallow'' changes near the root. In this paper we present a combination of change propagation and memoisation that works equally well for deep and shallow changes. It takes O(log n) overheads for a full run, and O(log2 n) per update operation. The extra space requirements of the combination with memoisation are a constant factor compared to pure change propagation.