%0 Conference Paper %1 Pennings92 %A Pennings, M. %A Swierstra, D. %A Vogt, H. %B Proceedings of the 4th International Symposium of Programming Language Implementation and Logic Programming, Leuven, BE: PLILP '92 %C Berlin, DE %D 1992 %E Bruynooghe, M. %E Wirsing, M. %I Springer-Verlag %K functional higher incr order vari.FP %P 130--144 %T Using Cached Functions and Constructors for Incremental Attribute Evaluation %X A technique is presented for the efficient incremental evaluation of attribute grammars. Through its generality, the applied approach may be affective too in the evaluation of higher order attribute grammars. The authors' approach is an extension of a simpler algorithm for incremental evaluation, where functions, corresponding to visit sequences, are cached. Consequently, attributes are either found in the cache or they are recomputed, so there is no longer need to represent the attributed tree explicitly. One may share common subtrees, avoiding repeated attribute evaluation, thus solving a typical HAG problem. The authors propose the following change: instead of explicitly representing the tree and calling visit sequence functions to compute the attributes, the tree is represented through a set of visit functions corresponding to the successive visits. These functions are constructed using the visit sequences as building blocks. This technique has two major advantages. Firstly, a visit function characterizes precisely that part of the tree that would actually have been visited in the previous approach, thus increasing the number of cache hits. Secondly, copyrules may be removed during the construction phase. This results in shortcircuiting copychains and in minimizing the number of recomputed functions. %@ 3-540-55844-6

@inproceedings{Pennings92, abstract = {A technique is presented for the efficient incremental evaluation of attribute grammars. Through its generality, the applied approach may be affective too in the evaluation of higher order attribute grammars. The authors' approach is an extension of a simpler algorithm for incremental evaluation, where functions, corresponding to visit sequences, are cached. Consequently, attributes are either found in the cache or they are recomputed, so there is no longer need to represent the attributed tree explicitly. One may share common subtrees, avoiding repeated attribute evaluation, thus solving a typical HAG problem. The authors propose the following change: instead of explicitly representing the tree and calling visit sequence functions to compute the attributes, the tree is represented through a set of visit functions corresponding to the successive visits. These functions are constructed using the visit sequences as building blocks. This technique has two major advantages. Firstly, a visit function characterizes precisely that part of the tree that would actually have been visited in the previous approach, thus increasing the number of cache hits. Secondly, copyrules may be removed during the construction phase. This results in shortcircuiting copychains and in minimizing the number of recomputed functions.}, added-at = {2009-05-10T18:36:57.000+0200}, address = {Berlin, DE}, author = {Pennings, M. and Swierstra, D. and Vogt, H.}, biburl = {https://www.bibsonomy.org/bibtex/223b5ae0d73d0c9ba01a244f36871db16/dparigot}, booktitle = {Proceedings of the 4th International Symposium of Programming Language Implementation and Logic Programming, Leuven, BE: PLILP '92}, description = {Attribute Grammar}, editor = {Bruynooghe, M. and Wirsing, M.}, interhash = {a8ddf3c5c65db6d607757d34f69bfdcb}, intrahash = {23b5ae0d73d0c9ba01a244f36871db16}, isbn = {3-540-55844-6}, keywords = {functional higher incr order vari.FP}, pages = {130--144}, publisher = {Springer-Verlag}, timestamp = {2009-05-10T18:37:07.000+0200}, title = {Using Cached Functions and Constructors for Incremental Attribute Evaluation}, year = 1992 }