SPACE-EFFICIENT MEMO-FUNCTIONS

A number of memoisation techniques io eliminate computational redundan cy from a large and automatically detectable class of nonlinear functi ons are introduced. The techniques make use of memo-tables and memo-fu nctions to improve the run time efficiency of functions exhibiting com mutative redundancy. A memo-function remembers all the arguments to wh ich it has been applied, together with the corresponding results from them, by storing them in a memo-table. The schemes discussed use a sep arate transient memo-table for each high-level application of the func tion. This contrasts with the technique of full memoisation, in which memo-tables are persistent. A basic memoisation scheme is introduced t hat is further refined to give a number of other more efficient strate gies to reduce the growth of these tables during evaluation. These str ategies make use of the nature of the dependency graph of functions ex hibiting commutative redundancy to make intelligent decisions concerni ng memo-table insertion and deletion operations. More precisely, the l evel of sharing of nodes in the dependency graph of functions is used to expedite the deletion of obsolete memo-table entries. When compared to contemporary program transformation schemes, the techniques presen ted achieve comparable improvements in efficiency while being mechanic al. In addition, these techniques are more generally applicable and re quire less compile-time deductive capacity than the corresponding prog ram transformation schemes. The paper also outlines an application of one of the techniques to Queueing Networks.