|
|
|
@inproceedings{DBLP:conf/popl/Cohen79,
author = {Norman H. Cohen},
title = {Characterization and Elimination of Redundancy in Recursive Programs},
booktitle = {POPL},
year = {1979},
pages = {143-157},
ee = {db/conf/popl/Cohen79.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Many well-known functions are computed by interpretations of the recursion schema
procedure f(x);
if p(x)
then return a(x)
else return b(x,f(c1(x)), ..., f(cn(x)))
Some of these interpretations define redundant computations because they lead to multiple calls on f with identical argument values. The existence and nature of the redundancy depend on properties of the functions ci. We explore four sets of assumptions about these functions. We analyze directed acyclic graphs formed by merging the nodes of the computation tree for f(x) which are known to be equal for each set of assumptions. In each case there is a transformed program which computes f(x) without redundancy, provided that certain additional assumptions about p, a, and the ci are satisfied. The transformed programs avoid redundancy by saving exactly those intermediate results which will be needed again later in the computation. These programs are all valueless recursive procedures which leave intermediate and final results in specified global locations; in each case recursion can be eliminated without use of a stack. We compare the storage requirements of the transformed programs, discuss the applicability of these transformations to an automatic program improvement system, and present a general criterion for establishing the existence of redundancy.
Copyright © 1979 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.