Program improvement by internal specialization

ABSTRACT

We investigate the specialization of programs by means of program transformation techniques. There are two goals of this investigation: the construction of program synthesis tools, and a better understanding of the development of algorithms.By extending an ordinary language of recursion equations to include a generalized procedure construct (the expression procedure), our ability to manipulate programs in that language is greatly enhanced. The expression procedure provides a means of expressing information not just about the properties of individual program elements, but also about the way they relate to each other.A set of four operations for transforming programs in this extended language is presented. These operations, unlike the transformation rules of Burstall and Darlington and of Manna and Waldinger, preserve the strong equivalence of programs.This set of operations forms the basis of a general-purpose specialization technique for recursive programs. The practical value of this technique has been demonstrated in the systematic development of many programs, including several context-free parsing algorithms. We outline here the development of Earley's algorithm by specialization.This paper is an informal exposition of part of the results of the author's Ph.D. thesis [Scherlis80].

REFERENCES

• 1: {Burstall71} R. M. Burstall, J. S. Collins, and R. J. Popplestone, Programming in POP-2. Edinburgh University Press, 1971.
• 2: 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]
• 3: {Darlington78a} J. Darlington, "A Synthesis of Several Sorting Algorithms." Acta Informatica, Vol. 11, Page 1, 1978.
• 4: Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
• 5: Jay Earley, High level operations in automatic programming, Proceedings of the ACM SIGPLAN symposium on Very high level languages, p.34-42, March 28-29, 1974, Santa Monica, California, United States
• 6: {Green78} C. C. Green and D. R. Barstow, "On program Synthesis Knowledge." Artificial Intelligence, Vol. 10, Page 241, 1978.
• 7: {Katz78} S. Katz, "Program Optimization Using Invariants." IEEE Transactions on Software Engineering, Vol. SE-4, No. 5, September, 1978.
• 8: {Kott78} L. Kott, "About R. Burstall and J. Darlington's Transformation System: A Theoretical Study." Program Transformation, B. Robinet, ed., Dunod, 1978.
• 9: {Manna79} Z. Manna and R. Waldinger, "Synthesis: Dreams ⇒ Programs." IEEE Transactions on Software Engineering, Vol. SE-5, No. 4, July 1979.
• 10: {Paige77} R. Paige and J. T. Schwartz, "Reduction in Strength of High Level Operations." Fourth Symposium on Principles of Programming Languages, January 1977.
• 11: William Louis Scherlis, Expression procedures and program derivation, 1980
• 12: {Wegbreit73} B. Wegbreit, "Procedure Closure in EL1." Center for Research in Computing Technology, Harvard University, May 1973.
• 13: Ben Wegbreit, Goal-directed program transformation, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.153-170, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811549]