Incremental evaluation of higher-order attributes

摘要

Compilers, amongst other programs, often work with data that (slowly) changes over time. When the changes between subsequent runs of the compiler are small, one would hope the compiler to incrementally update its results, resulting in much lower rebuilding times. However, the manual construction of an incremental compiler is very hard and error prone and therefore usually not an option. Attribute grammars provide an attractive way of constructing compilers, as they are compositional in nature and allow for aspect oriented programming. In this paper we describe work on the automatic generation of incremental attribute grammar evaluators, with the purpose of (semi-)automatically generating an incremental compiler from a regular attribute grammar definition. The paper includes an informal introduction into attribute grammars, describes how to implement incremental evaluation for a simple example without higher-order attributes as well as for a larger example with higher-order attributes. Higher-order attributes are a well known extension to classical attribute grammars which for example is used to model different compiler phases or iterative transformations of an abstract syntax tree. Incrementality for attribute evaluation is achieved by maintaining additional bookkeeping about which attribute values have changed. We show benchmarks for the implementation technique dealing with higher-order attributes. The benchmarks indicate that the bookkeeping overhead in our prototype implementation comes with a serious hit on performance, further investigation into the reasons and possible remedies for this falls outside the scope of this paper.