This paper presents a semantics of self-adjusting computation and proves that the semantics are correct and consistent. The semantics integrate change propagation with the classic idea of memoization to enable reuse of computations under mutation to memory. During evaluation, reuse of a computation via memoization triggers a change propagation that adjusts the reused computation to reflect the mutated memory. Since the semantics integrate memoization and change-propagation, it involves both non-determinism (due to memoization) and mutation (due to change propagation). Our consistency theorem states that the non-determinism is not harmful: any two evaluations of the same program starting at the same state yield the same result. Our correctness theorem states that mutation is not harmful: self-adjusting programs are consistent with purely functional programming. We formalize the semantics and their meta-theory in the LF logical framework and machine check our proofs using Twelf.
Dependence graphs record the dependencies between data in a computation and rely on a change-propagation algorithm to update the computation when the input is modified (e.g., @cite_9 @cite_17 ). Dependence graphs are effective in some applications, e.g., syntax-directed computations but are not general-purpose because change propagation does not update the dependence structure. Memoization (also called function caching) (e.g., @cite_15 @cite_3 @cite_16 ) applies to any purely functional program and therefore is more broadly applicable than static dependence graphs. This classic idea dating back to the late 1950's @cite_20 @cite_1 @cite_0 yields efficient incremental computations when executions of a program with similar inputs perform similar function calls. It turns out, however, that even a small input modifications can prevent reuse via memoization, e.g., when they affect computations deep in the call tree @cite_5 . Partial evaluation based approaches @cite_11 @cite_7 require the user to fix a partition of the input and specialize the program to speedup modifications to unfixed part faster. The main limitation of this approach is that it allows input modifications only within a predetermined partition.
@cite_11 @cite_7 @cite_9 @cite_1 @cite_3 @cite_0 @cite_5 @cite_15 @cite_16 @cite_20 @cite_17
2007009457 2014832211 2166089338 1965784613 2171901695 2035829578 1999707021
It is a common occurrence in a programming environment to apply a software tool to a series of similar inputs. Examples include compilers, interpreters, text formatters, etc., whose inputs are usually incrementally modifed text files. Thus programming environment researchers have recognized the importance of building incremental versions of these tools — i.e. ones which can efficiently update the result of a computation when the input changes only slightly. An incremental algorithm is one that takes advantage of the fact that the function it computes is to be evaluated repeatedly on inputs that differ only slightly from one another, avoiding unnecessary duplication of common computations. We define here a new notion of incrementality for reduction in the untyped λ-calculus and describe an incremental reduction algorithm, Λ inc . We show that Λ inc has the desirable property of performing non-overlapping reductions on related terms, yet is simple enough to allow a practical implementation. The algorithm is based on a novel λ-reduction strategy that may prove useful in a non-incremental setting as well. Incremental λ-reduction can be used to advantage in any setting where an algorithm is specified in a functional or applicative manner. Publisher Summary This chapter discusses the mathematical theory of computation. Computation essentially explores how machines can be made to carry out intellectual processes. Any intellectual process that can be carried out mechanically can be performed by a general purpose digital computer. There are three established directions of mathematical research that are relevant to the science of computation—namely, numerical analysis, theory of computability, and theory of finite automata. The chapter explores what practical results can be expected from a suitable mathematical theory. Further, the chapter presents several descriptive formalisms with a few examples of their use and theories that enable to prove the equivalence of computations expressed in these formalisms. A few mathematical results about the properties of the formalisms are also presented. It would be useful if computers could learn from experience and thus automatically improve the efficiency of their own programs during execution. A simple but effective rote-learning facility can be provided within the framework of a suitable programming language. Dependence graphs and memoization can be used to efficiently update the output of a program as the input changes dynamically. Recent work has studied techniques for combining these approaches to effectively dynamize a wide range of applications. Toward this end various theoretical results were given. In this paper we describe the implementation of a library based on these ideas, and present experimental results on the efficiency of this library on a variety of applications. The results of the experiments indicate that the approach is effective in practice, often requiring orders of magnitude less time than recomputing the output from scratch. We believe this is the first experimental evidence that incremental computation of any type is effective in practice for a reasonably broad set of applications. We address the problem of dependency analysis and caching in the context of the l-calculus. The dependencies of a l-term are (roughly) the parts of the l-term that contribute to the result of evaluating it. We introduce a mechanism for keeping track of dependencies, and discuss how to use these dependencies in caching.