Applicative caching
Robert Keller, M. Ronan Sleep · ACM Transactions on Programming Languages and Systems · 1986
The “referential transparency” principle of applicative language expressions stipulates that a single value exists for all occurrences of an expression in a given context (where a context is a set of bindings of variables to values). In principle, each such value therefore need to be computed only once. However, in applicative language systems supporting recursive programming or tasking notions, the bindings are not all precomputed and explicit. As a result, textual recognition of all multipleoccurrences is precluded, with the unfortunate consequence that such occurrences are recomputed. We elaborate upon the early notion of “memo function” for solving this problem. We suggest syntactic and semantic constructs providing programmer control for avoiding recomputation, which is incorporated into a “building-block” approach.
Cited by 33 works. doi:10.1145/5001.5004 Open-access PDF
Authors
References
- The Design and Analysis of Computer Algorithms
- Cooperating Sequential Processes
- The Mechanical Evaluation of Expressions
- Trie memory
- A Transformation System for Developing Recursive Programs
- The next 700 programming languages
- A lazy evaluator
- CONS Should Not Evaluate its Arguments.
- Programming Languages
- Introduction to Mathematical Theory of Computation