William L. Scherlis
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].
- {Burstall71} R. M. Burstall, J. S. Collins, and R. J. Popplestone, Programming in POP-2. Edinburgh University Press, 1971.Google Scholar
- {Burstall77} R. M. Burstall and J. Darlington, "A Transformation System for Developing Recursive Programs." Journal of the ACM, Vol. 24, No. 1, January 1977. Google ScholarDigital Library
- {Darlington78a} J. Darlington, "A Synthesis of Several Sorting Algorithms." Acta Informatica, Vol. 11, Page 1, 1978.Google ScholarDigital Library
- {Earley70} J. Earley, "An Efficient Context-Free Parsing Algorithm." Communications of the ACM, Vol. 13, No. 2, February 1970. Google ScholarDigital Library
- {Earley74} J. Earley, "High Level Operations in Automatic Programming." Symposium on Very High Level Languages, SIGPLAN Notices, Vol. 9, No. 4, 1974. Google ScholarDigital Library
- {Green78} C. C. Green and D. R. Barstow, "On program Synthesis Knowledge." Artificial Intelligence, Vol. 10, Page 241, 1978.Google Scholar
- {Katz78} S. Katz, "Program Optimization Using Invariants." IEEE Transactions on Software Engineering, Vol. SE-4, No. 5, September, 1978.Google ScholarDigital Library
- {Kott78} L. Kott, "About R. Burstall and J. Darlington's Transformation System: A Theoretical Study." Program Transformation, B. Robinet, ed., Dunod, 1978.Google Scholar
- {Manna79} Z. Manna and R. Waldinger, "Synthesis: Dreams ⇒ Programs." IEEE Transactions on Software Engineering, Vol. SE-5, No. 4, July 1979.Google Scholar
- {Paige77} R. Paige and J. T. Schwartz, "Reduction in Strength of High Level Operations." Fourth Symposium on Principles of Programming Languages, January 1977.Google Scholar
- {Scherlis80} W. L. Scherlis, "Expression Procedures and Program Derivation." Ph.D. thesis, Stanford Computer Science Report STAN-CS-80-818, August 1980. Google ScholarDigital Library
- {Wegbreit73} B. Wegbreit, "Procedure Closure in EL1." Center for Research in Computing Technology, Harvard University, May 1973.Google Scholar
- {Wegbreit76} B. Wegbreit, "Goal-Directed Program Transformation." Third Symposium on Principles of Programming Languages, January 1976. Google ScholarDigital Library
Recommendations
Static and Dynamic Program Compilation by Interpreter Specialization
Interpretation and run-time compilation techniques are increasingly important because they can support heterogeneous architectures, evolving programming languages, and dynamically-loaded code. Interpretation is simple to implement, but yields poor ...
Declarative specialization for object-oriented-program specialization
PEPM '04: Proceedings of the 2004 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulationThe use of partial evaluation for specializing programs written in imperative languages such as C and Java is hampered by the difficulty of controlling the specialization process. We have developed a simple, declarative language for controlling the ...
Comments