Effective function cache management for incremental attribute evaluation
J.A.B.V. Saraiva, M.F. Kuiper, S. Doaitse Swierstra · 1996
This paper presents an effective strategy for function cache management in the context of incremental attribute evaluation. The evaluators we study consist of pure functions which are memoized to achieve incremental evaluation. To prevent unbounded growth of the function cache a strategy for managing this cache is needed. Our strategy only keeps in the cache the functions used in the reevaluation of the current input. This strategy has the following properties: it efficiently handles Higher-order Attribute Grammars, it works well when a sequence of modications on the input exhibits some locality of work and measurements show that for sequences of typical tree transformations the evaluator consumes only a fraction of memory with our strategy than with a complete memoization, and is even slightly faster.