Improving programs by the introduction of recursion

ABSTRACT

A new technique of program transformation, called “recursion introduction,” is described and applied to two algorithms which solve pattern matching problems. By using recursion introduction, algorithms which manipulate a stack are first translated into recursive algorithms in which no stack operations occur. These algorithms are then subjected to a second transformation, a method of recursion elimination called “tabulation,” to produce programs with a very efficient running time. In particular, it is shown how the fast linear pattern matching algorithm of Knuth, Morris, and Pratt can be derived in a few steps from a simple nonlinear stack algorithm.

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: Bird, R.S. Speeding up programs. Computer J. 17, 4 (1975), 337-339.
• 3: 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]
• 4: Bird, R.S. Programs and Machines-An Introduction to the Theory of Computation. John Wiley, London, 1976.
• 5: Brown, S., Gries, D., and Szymanski, T. Program schemes with pushdown stoves. SIAM J. Comptng. 1 (1972), 242-268.
• 6: Ashok Kumar Chandra, On the properties and applications of program schemas, 1973
• 7: Darlington, J., and Burstall, R.M. A system which automatically improves programs. Proc. 3rd Int. Conf. on Artif, Intell., Stanford U., Stanford, Calif., 1973, pp. 479-485.
• 8: Donald E. Knuth, Structured Programming with go to Statements, ACM Computing Surveys (CSUR), v.6 n.4, p.261-301, Dec. 1974 [doi>10.1145/356635.356640]
• 9: Knuth, D.E., Morris, J.H., Jr., and Pratt, V.R. Fast pattern matching in strings. Res. Rep. CS-74-440, Comptr. Sci. Dept., Stanford, U., Stanford, Calif., 1974.
• 10: Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
• 11: James H. Morris, Jr., Another recursion induction principle, Communications of the ACM, v.14 n.5, p.351-354, May 1971 [doi>10.1145/362588.362598]

INDEX TERMS

Keywords:
computational induction, optimization of programs, pattern matching algorithms, program transformation, recursion elimination, stacks