Report Number: CS-TR-77-639
Institution: Stanford University, Department of Computer Science
Title: On program synthesis knowledge
Author: Green, Cordell C.
Author: Barstow, David R.
Date: November 1977
Abstract: This paper presents a body of program synthesis knowledge
dealing with array operations, space reutilization, the
divide and conquer paradigm, conversion from recursive
paradigms to iterative paradigms, and ordered set
enumerations. Such knowledge can be used for the synthesis of
efficient and in-place sorts including quicksort, mergesort,
sinking sort, and bubble sort, as well as other ordered set
operations such as set union, element removal, and element
addition. The knowledge is explicated to a level of detail
such that it is possible to codify this knowledge as a set of
program synthesis rules for use by a computer-based synthesis
system. The use and content of this set of programming rules
is illustrated herein by the methodical synthesis of bubble
sort, sinking sort, quicksort, and mergesort.