On program synthesis knowledge

摘要

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 by the methodical synthesis of bubble sort, sinking sort, quicksort, and mergesort.