The Refinement Paradigm: The Interaction of Coding and Efficiency Knowledge in Program Synthesis
- 1 September 1981
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. SE-7 (5) , 458-471
- https://doi.org/10.1109/tse.1981.230854
Abstract
A refinement paradigm for implementing a high-level specification in a low-level target language is discussed. In this paradigm, coding and analysis knowledge work together to produce an efficient program in the target language. Since there are many possible implementations for a given specification of a program, searching knowledge is applied to increase the efficiency of the process of finding a good implementation. For example, analysis knowledge is applied to determine upper and lower cost bounds on alternate implementations, and these bounds are used to measure the potential impact of different design decisions and to decide which alternatives should be pursued. In this paper we also describe a particular implementation of this program synthesis paradigm, called PSI/SYN, that has automatically implemented a number of programs in the domain of symbolic processing.Keywords
This publication has 10 references indexed in Scilit:
- Transformational Implementation: An ExampleIEEE Transactions on Software Engineering, 1981
- An experiment in knowledge-based automatic programmingArtificial Intelligence, 1979
- Synthesis: Dreams → ProgramsIEEE Transactions on Software Engineering, 1979
- On program synthesis knowledgeArtificial Intelligence, 1978
- Automatic data structure selectionCommunications of the ACM, 1978
- A Transformation System for Developing Recursive ProgramsJournal of the ACM, 1977
- Selection of representations for data structuresPublished by Association for Computing Machinery (ACM) ,1977
- Goal-directed program transformationPublished by Association for Computing Machinery (ACM) ,1976
- Abstraction and Verification in Alphard: Introduction to Language and MethodologyPublished by Springer Nature ,1976
- Program development by stepwise refinementCommunications of the ACM, 1971