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.

The term "procedural semantics" has been used in a variety of ways, not

all compatible, and not all comprehensible. In this paper, I have chosen

to apply the term to a broad paradigm for studying semantics (and in fact,

all of linguistics). This paradigm has developed in a context of writing

computer programs which use natural language, but it is not a theory of

computer programs or programming techniques. It is "procedural" because

it looks at the underlying structure of language as fundamentally shaped

by the nature of processes for language production and comprehension. It

is based on the belief that there is a level of explanation at which there

are significant similarities between the psychological processes of human

language use and the computational processes in computer programs we can

construct and study. Its goal is to develop a body of theory at this

level. This approach necessitates abandoning or modifying several

currently accepted doctrines, including the way in which distinctions have

been drawn between "semantics" and "pragmatics" and between "performance"

and "competence".

The paper has three major sections. It first lays out the paradigm

assumptions which guide the enterprise, and elaborates a model of

cognitive processing and language use. It then illustrates how some

specific semantic problems might be approached from a procedural

perspective, and contrasts the procedural approach with formal structural

and truth conditional approaches. Finally, it discusses the goals of

linguistic theory and the nature of the linguistic explanation.

Much of waht is presented here is a speculation about the nature of a

pradigm yet to be developed. This paper is an attempt to be evocative

rather than definitive; to convey intuitions rather than to formulate

crucial arguments which justify this approach over others. It will be

successful if it suggests some ways of looking at language which lead to

further understanding.