And/Or(ID:5707/and004)

Simple tree-like programming/specification language  

Simple tree-like programming/specification language
References:
  • Harel, David "And/Or Programs: A New Approach to Structured Programming" view details Abstract: A simple tree-like programming/specification language is presented. The central idea is the dividing of conventional programming constructs into the two classes of and and or subgoaling, the subgoal tree itself constituting the program. Programs written in the language can, in general, be both nondeterministic and parallel. The syntax and semantics of the language are defined, a method for verifying programs written in it is described, and the practical significance of programming in the language assessed. Finally, some directions for further research are indicated. DOI Extract: Introduction
    1. INTRODUCTION
    In this paper we present a programming/specification language based on the concept of alternating and and or subgoals. The general notion of and/or alternation is well known and occurs in mathematical logic (alternation of quantifiers), game theory (and/or game trees), and artificial intelligence (and/or problem solving trees). Recently, in [3] and [13], alternation was introduced into theoretical computer science as a powerful tool in classifying the computational complexity of classes of problems, and applications of it were illustrated and envisioned. It is from [3] that our second quotation above is taken. The language proposed here serves as a natural application of this concept to the discipline of structured programming (cf. [4]) from which the first quotation is taken.

    It is commonly claimed that as much as the efficiency of a program is important (e.g., in terms of its consumption of resources such as time or space), its clarity, readability, and manageability are also to be a major concern of its author. To this end various disciplines have been advocated, including the use of structured programming and flowcharting. The former is an aid in synthesizing the program in a stepwise top-down fashion, and the latter is a tool for pictorially describing it.

    One of the apparent problems with structured programming as it stands is in the fact that the history of the subgoaling process which produced the final program is not captured by the final text. Except for some consistent indenting of the program text (e.g., in Algol or PL/I) no "information-at-a-glance" pictorial description of the design structure of the program is present. Consequently, it is not always easy to carry out a modification without a considerable amount of insightful preparation. Thus, for example, if the first step of synthesizing a simple compiler was in refining the compilation process into the two subgoals of parsing and coding, this fact will not always be obvious from glancing at the final program text of the compiler; not until the text has been appropriately partitioned in a visual way, say by circling the two components. A complete logical structuring of the program text will consist typically of a nested set of such circles. In other words, the depth and structure of the stepwise composition of the program are not visible in the final product.

    Similarly, the virtues of the visual representation supplied by flowcharts, while illustrating the flow of control, are of little help in capturing the structure of the logical design even when so-called "structured flowcharts" are employed {these corresponding essentially to indented textual programs), and a similar process of nested encircling has to be carried out. This situation is most problematic at later stages, i.e., when the program is to be constantly maintained and often modified. Cumbersome documentation then becomes a necessity.

    The and/or programming language described in Section 3 is designed with this problem in mind; i.e., in the final tree-like progam the flow of control of a particular implementation of that program is secondary to its logical structure. It is precisely the structure of this natural stepwise synthesis of the algorithm that the tree captures. Each node of the tree represents the program consisting of the subtree rooted in that node, with its immediate descendants representing its decomposition into subgoals. Thus, in the above example, parse and code would be natural choices for the offspring of the node (in this case the root of the tree} denoted by compile. As will become clear, the "layers" in which the program is arranged, these being in the heart of the idea of structured programming (cf. [4, pp. 48-49]), correspond to the levels of the tree.

    The resulting language possesses such pragmatic niceties as readability and ease of modification as well as considerable flexibility in choosing an implemen tation. This flexibility will be seen also to be the main drawback of our language; the flow of control can be obtained from the program text only by some moderate amount of analysis. Also, the language gives rise to rather natural versions of some of the standard methods for proving the correctness of programs. The programs, in general, admit both nondeterminism and a kind of parallelism, features which are lately being considered essential in many types of programming.

    Section 2 contains an informal introduction to the language, and Section 3 presents the syntax and semantics. In Section 4 we illustrate how and/or programs are to be verified, while Section 5 is devoted to discussing the advantages the language offers the implementer and programmer. Some directions for future work are discussed in Section 6.
          in TOPLAS 2(1) January 1980 view details