Norman H. Cohen
- 1 AHO, A.V., HOPCROFT, J.E., AND ULLMAN, J.D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974. Google Scholar
- 2 BIRD, R.S. Tabulation techniques for recursive programs. ACM Comput. Surv. 12, 4 (Dec. 1980), 403-417. Google Scholar
- 3 BIRD, R.S. Improving programs by the introduction of recursion. Commun. ACM 20, 11 (Nov. 1977), 856-863. Google Scholar
- 4 BURSTALL, R.M., AND DARLINOTON, J. A transformation system for developing recursive programs. J. ACM 24, I (Jan. 1977), 44-67. Google Scholar
- 5 CHANDRA, A.K. Efficient compilation of linear recursive programs. In Conference Record, IEEE 14th Annual Symposium on Switching and Automata Theory (Iowa City, Iowa, Oct. 1973), pp. 16-25.Google Scholar
- 6 COHEN, N.H. Source-to-Source Improvement of Recursive Programs. Ph.D. dissertation, Division of Applied Sciences, Harvard Univ., Cambridge, Mass., May 1980.Google Scholar
- 7 COHEN, N.H. Characterization and elimination of redundancy in recursive programs. In Conference Record of the 6th Annual ACM Symposium on Principles of Programming Languages (San Antonio, Tex., Jan. 29-31, 1979), pp. 143-157. Google Scholar
- 8 DARLINGTON, J. Program transformation and synthesis: Present capabilities. Res. Rep. 77/43, Dept. of Computing and Control, Imperial College of Science and Technology, London, Sept. 1977.Google Scholar
- 9 DARLINGTON, J., AND BURSTALL, R.M. A system which automatically improves programs. Acta Inf. 6, 1 (Mar. 1976), 41-60.Google Scholar
- 10 FRIEDMAN, D.P., WISE, D.S., A~D WANO, M. Recursive programming through table look-up. In SYMSAC '76; proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation (Yorktown Heights, N.Y., Aug. 10-12, 1976), R.D. Jenks (Ed.), pp. 85-89. Google Scholar
- 11 HILDEN, J. Elimination of recursive calls using a small table of "randomly" selected function values. BIT 16, 1 (1976), 60-73.Google Scholar
- 12 LEWIS, H.R. A new decidable problem, with applications. In Proceedings, IEEE 18th Annual Symposium on Foundations of Computer Science (Providence, R.I., Oct.-Nov. 1977), pp. 62-73.Google Scholar
- 13 MICHIE, D. "Memo" functions and machine learning. Nat. 218, 5136 (Apr. 6, 1968), 19-22.Google Scholar
- 14 PATERSON, M.S., ANO HEWITr, C.E. Comparative schematology. In Record of the Project MAC Conference on Concurrent Systems and Parallel Computation (Woods Hole, Mass., June 2-5, 1970), pp. 119-127.Google Scholar
- 15 PIPPENCER, N. Pebbling. Res. Rep. RC 8258, IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., May 1980.Google Scholar
- 16 STRONG, H.R. Translating recursion equations into flowcharts. J. Comput. Syst. Sci. 5, 3 (June 1971), 254-285.Google Scholar
- 17 SWAMY, S., A~D SAVAGE, J.E. Space-time tradeoffs for linear recursion. In Conference Record of the 6th Annual ACM Symposium on Principles of Programming Languages (San Antonio, Tex., Jan. 29-31, 1979), pp. 135-142. Google Scholar
- 18 VUILLEMIN, J. Correct and optimal implementations of recursion in a simple programming language. J. Comput. $yst. Sci. 9, 3 (Dec. 1974), 332-354.Google Scholar
Index Terms
- Eliminating Redundant Recursive Calls.
Recommendations
Complete inlining of recursive calls: beyond tail-recursion elimination
ACM-SE 44: Proceedings of the 44th annual Southeast regional conferenceA compiler optimizing transformation called complete inlining to inline and eliminate recursive calls is presented. The complete inlining can eliminate the recursive calls that cannot be eliminated by tail-recursion elimination. It can inline the ...
Reducing Latency via Redundant Requests: Exact Analysis
Performance evaluation reviewRecent computer systems research has proposed using redundant requests to reduce latency. The idea is to run a request on multiple servers and wait for the first completion (discarding all remaining copies of the request). However there is no exact ...
Queueing with redundant requests: exact analysis
Recent computer systems research has proposed using redundant requests to reduce latency. The idea is to run a request on multiple servers and wait for the first completion (discarding all remaining copies of the request). However, there is no exact ...
Reviews
Jiri Horejs
The methods of tabulating results of recursive calls to avoid their recomputations are surveyed in [1]. The reviewed paper considers a rather special, theoretically simple, yet practically significant (as demonstrated by numerous examples) class of programs represented by the schema: f( x) :9I = if p( x) then a( a) else b ( x), f)( c( x)). f( d( x))). Under some constraints (like commutativity of c and d), small tables, which save exactly the results to be used later, can be designed systematically with no heuristic involved. The method thus permits the user to automatically transform considered programs to their (partially equivalent) nonredundant counterparts. The interested reader may find it useful to also consult [2], which is not referred to in this paper.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments