Using Cached Functions and Constructors for Incremental Attribute
Evaluation
M. Pennings, D. Swierstra, и H. Vogt. Proceedings of the 4th International Symposium of Programming Language
Implementation and Logic Programming, Leuven, BE: PLILP '92, стр. 130--144. Berlin, DE, Springer-Verlag, (1992)
Аннотация
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.
%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
}