Name
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]. |
Year | DOI | Venue |
|---|---|---|
1981 | 10.1145/567532.567536 | POPL |
Keywords | Field | DocType |
ordinary language,program improvement,generalized procedure,program transformation technique,internal specialization,recursive program,individual program element,expression procedure,program synthesis tool,extended language,general-purpose specialization technique,systematic development | Ordinary language philosophy,Programming language,Program transformation,Program synthesis,Computer science,Expression procedure,Theoretical computer science,Equivalence (measure theory),Parsing,Recursion | Conference |
ISBN | Citations | PageRank |
0-89791-029-X | 36 | 5.10 |
References | Authors | |
6 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| William L. Scherlis | 1 | 340 | 63.64 |