In cases where it is relatively expensive in resources to compute functions, it may be advisable to expand the programmed versions of those functions to contain a store, or cache, of values already computed. Then, if the same argument is presented to a function twice or more, recomputations can be replaced by (hopefully) less expensive searches for the corresponding value in the cache. The organization of the cache can vary according to the nature of the function and its use. In principle, any result one finds in a textbook or paper on data structures is appropriate if it decreases the computing resources that a function with a cache needs.

The paper considers these observations against the background of functional, or applicative, programming; here, the possibilities of recursion and multiple tasking make it difficult or impossible for the programmer even to use bindings of values to variables as convenient ways to avoid the recomputation problem mentioned above.

The primary emphasis is on extensions to a specimen functional programming language in order to support caching of already computed results. The extensions include the idea of a caching functional, which allows the programmer to select details of data structuring for implementations of functions with caches. Questions of purity of implementation are also considered, i.e., whether or not particular features or primitives themselves can be implemented in an applicative language.

The contribution of the paper to functional programming is twofold: as well as proposing language extensions, it covers issues of caching that are necessary to address if functional programming is to be computationally efficient in practice. Given that one of the chief virtues of functional programming is the absence of side-effects, it is worth mentioning that the authors’ choice of example (Jacobi method for numerical solution of partial differential equations at points of a coordinate grid) to illustrate both of the contributions has the side-effect of drawing attention to the wide difference between “necessary” and “sufficient.”

Aside from functional programming, the paper can be read as a useful tutorial on the design choices that face any programmer of functions that may benefit from the caching of values.