Incremental computation via function caching
Incremental computation via function caching
复制标题
通过函数缓存进行增量计算
DOI：
10.1145/75277.75305
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
T. Teitelbaum
中科院分区：
文献类型：
--
作者：
W. Pugh;T. Teitelbaum
IncrementaZ Computafim是一种在输入更改时有效更新计算结果的技术。这个想法被用于在编程环境中进行语义检查，在所见即所得编辑器和许多其他应用程序中进行文档格式化。从不同的角度来看，增量计算涉及到flx&j&)、……的高效在线计算。其中F是某个程序，x0，x1，..。是一系列输入值，每个值与其前一个值仅略有不同。可以通过编写显式增量算法来实现增量计算-该算法不仅指定如何计算来自输入的输出，而且还指定当输入更改时如何更新输出。这可能很困难且容易出错，因此，如果可能，我们更喜欢使用增量式求值器-一个仅使用如何计算输入输出的描述的求值器，并负责确定在输入更改时如何正确有效地更新输出。增量属性语法评估和增量依赖图评估已被证明是产生增量评估器(DRT811[Rep821 IRep841[Ho0861 IHT861[ACR+871[Hoo871 fYS881.不幸的是，它们只适用于某些类型的问题。例如，虽然可以使用这些技术来进行增量证明验证[RA841]，但似乎不可能使用这些技术来进行增量定理证明。提出了一种新的基于函数缓存的增量式求值方法，在增量属性文法求值和增量式依赖图求值技术无法使用的情况下能很好地工作。我们的范例在许多最适合增量属性文法求值和增量依赖图求值的情况下也工作得相当好。在第7节中，我们给出了我们的技术与Rep的最优增量属性文法算法的比较。
IncrementaZ computafim is the technique of efficiently updating the result of a computation when the input is changed. This idea is used in doing semantic checking in programming environments, document formatting in WYSIWYG editors and many other applications. From a different perspective, incremental computation concerns the efficient on-line computation of flx&j&),... wheref is some program and xo, xl,... is a sequence of input values, each differing from its predecessor only slightly. It is possible to achieve incremental computation by writing an explicitly incremental algorithm-an algorithm that not only specifies how to compute the output from the input, but also specifies how to update the output when the input changes. This can be difficult and error-prone, so when possible we would prefer to use an incremental evaluator-an evaluator that uses just a description of how to compute the output from the input and is responsible for determining how to update the output correctly and efficiently when the input changes. Incremental attribute grammar evaluation and incremental dependency graph evaluation have proven to be useful and efficient paradigms for producing incremental evaluators (DRT811 [Rep821 IRep841 [Ho0861 IHT861 [ACR+ 871 [Hoo871 fYS881. Unfortunately, they are only suitable for certain kinds of problems. For example, while it it possible to use such techniques for incremental proof verification [RA841, it seems impossible to use these techniques for incremental theorem proving. We present a new paradigm for incremental evaluation based on function caching that works well in some situations for which incremental attribute grammar evaluation and incremental dependency graph evaluation techniques are unusable. Our paradigm also works reasonably well in many of those situations best suited for incremental attribute grammar evaluation and incremental dependency graph evaluation. We give a comparison of our techniques and Reps’s optimal incremental attribute grammar algorithm in Section 7.