Characterization and elimination of redundancy in recursive programs

ABSTRACT

Many well-known functions are computed by interpretations of the recursion schemaprocedure 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.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: R. S. Bird, Notes on recursion elimination, Communications of the ACM, v.20 n.6, p.434-439, June 1977 [doi>10.1145/359605.359630]
• 3: R. S. Bird, Improving programs by the introduction of recursion, Communications of the ACM, v.20 n.11, p.856-863, Nov. 1977 [doi>10.1145/359863.359889]
• 4: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 5: Chandra, A. K. {1973}. Efficient compilation of linear recursive programs, Conference Record, IEEE 14th Annual Symposium on Switching and Automata Theory, pp. 16-25
• 6: Darlington, J., and Burstall, R. M. {1976}. A system which automatically improves programs, Acta Informatica 6, No. 1, pp. 41-60
• 7: Lewis, H. R. {1977}. A new decidable problem, with applications, Proceedings, IEEE 18th Annual Symposium on Foundations of Computer Science, pp. 62-73
• 8: Paterson, M. S., and Hewitt, C. E. {1970}. Comparative schematology, Record of Project MAC Conference on Concurrent Systems and Parallel Computation, pp. 119-127
• 9: Rangel, J. L. {1974}. The equivalence problem for regular expressions over one letter is elementary, Conference Record, IEEE 15th Annual Symposium on Switching and Automata Theory, pp. 24-27
• 10: Strong, H. R. {1971}. Translating recursion equations into flow charts, JCSS 5, No. 3 (June), pp. 254-285