A connotational theory of program structure (Q579920)

This book attacks some questions of foundational character regarding the programming languages, by settling a new language independent theory of program structure. This theory uses in an extensive way the well established apparatus of recursive function theory, which leads to some significant results, that could probably have not been obtained by other approaches like the denotational semantics or the theory of program schemes. The basic frame is that of effective numberings which represent what is in essence the class of all theoretically possible programming languages. It allows a very general definition of the notion of control structure, which covers all the usual representatives of this notion (if...then...else, while...do, etc.). Hence, a main objective of this book is a detailed study of this numberings. It is shown that a semilattice structure, called the Rogers semilattice, can be embedded in the family of effective numberings, which has similar algebraical properties with the much better known semilattice of m-degrees of r.e sets. The acceptable numberings which are those effective numberings into which every other effective numbering has an effective translation play a prominent part in the book. An important problem is that of characterizing the acceptable numberings. There are some well-known such characterizations like the one of Rogers (a numbering having the s-l-l function is acceptable) or the one due to Machtey, Winklmann, and Young who showed that an effective numbering admitting an implementation of the composition operator is acceptable. Such results are largely extended in this book in an attempt to understand which control structures characterize acceptability. Several new control structures are found which taken in pair characterize acceptability. Some of these matters are also discussed from a computational complexity point of view. For example it is shown that in an effective numbering which has s-l-l as a primitive, all the other control structures can be built within a relatively low complexity bound. Another topic extensively discussed is that of the relative dependence of some usual control structures. A quite general technique is developed for control structure independence arguments by the help of which, to cite one result out of many, it is shown that conditional, for-loop, primitive recursion form an independent set in the sense that none of the three control structures can be built from the other two. An extension of this technique is used to obtain complexity independence results: for example, there are acceptable numberings in which conditional and while are efficiently represented, but in which repeat has only representations beyond an arbitrary, preassigned complexity bound. In conclusion, this monograph offers some relevant results to matters which seem to have been less focused by computer scientists in the last time. Whether the impact of the book will produce a change in this attitude is at this time an open problem. Contents: Chapter 1. Motivations, Background, and Basic Definitions, Chapter 2. Effective numberings, Completions, and Control Structures, Chapter 3. Some Special Effective Numberings, Chapter 4. Characterizations of Acceptability, Chapter 5. Independence of Control Structures, Chapter 6. General Programming Properties of Effective Numberings of Subrecursive Classes, Bibliography, Notation Index, Definition Index.