On Program Synthesis Knowledge. AIM-306

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.