Floyd - Evans language(ID:5533/flo015)Symbolic manipulation languageSymbolic language system, attempting to overcome the limitations of what Floyd called "algebraic command languages" (then ALGOL, IT, FORTRAN, UNICODE) and examine a more direct approach to symbolic manipulation. Floyd (1961) is an important and much cited paper. Related languages
References: Analogously, the traditional flowchart serves well as a descriptive language for numerical algorithms, but does not lend itself to description of symbol manipulation algorithms in such a way that the intent of the process is clear. It will be the purpose of this paper to present a more suitable notation for description of compilers and other complicated symbol manipulation algorithms. The algorithms used in formula translation consist principally of the following elements: (1) A set of linguistic transformations upon the input string, together with conditions determining the applicability of each transformation. (2) A set of actions, such as the generation of machine language coding, associated with each transformation. (3) A rule for transfering the attention of the translator from one portion of the input string to another. The notation presented here greatly simplifies the representation of the first and third elements. For illustrative purposes, a compilation process for a small subset of ALGOL is described below. The subset consists of assignment statements constructed from identifiers, the five binary arithmetic operators ( ^, × , / , + , - ), the two unary arithmetic operators (+, -), the replacement operator ( := ) , parentheses, and the library functions of one variable (sin, exp, sqrt, etc.). The assignment statement Σ to be translated is initially taken in the augmented form |- Σ -| , where the characters |- and -| serve as termination symbols and a is a pointer which indicates the portion of the statement where the translator's attention is currently focused. The following productions and the associated generation rules respectively decompose the original statement in accordance with its structure, and simultaneously create coding to implement the statement. Coding will be represented by ALGOL statements with at most one operator, to avoid reference to particular computers. in [ACM] JACM 8(4) October 1961 view details in [ACM] JACM 10(03) July 1963 view details in Goodman, Richard (ed) "Annual Review in Automatic Programming" (4) 1964 Pergamon Press, Oxford view details DOI in [ACM] CACM 7(02) (Feb 1964) includes Papers presented at a Working Conference on Mechanical Language Structures, Princeton, N. J., August 1963 view details in [ACM] JACM, 14(4) 1967 view details in [ACM] JACM 17(1) January 1970 view details in SIGPLAN Notices 5(07) July 1970 view details in [ACM] CACM 13(08) (August 1970) view details in The Computer Journal 17(1) February 1974 view details Introduction In 1965, Golomb and Baumert described a technique called backtrack programming, which is useful in writing programs to search for specific configuration vectors in large multi-dimensional spaces. Two years later Floyd presented detailed information on how such a technique could be implemented in a computer. Floyd also suggested that programming languages could be enhanced if they contained features enabling their users to utilise backtrack programming. In this work we describe an implementation of Floyd's ideas that can be programmed in a short time and utilises FORTRAN as a base language. More specifically, the objectives of this paper are: 1. To propose a set of FORTRAN-like primitives that can be used to express Floyd's non-deterministic algorithms. 2. To describe a syntax-directed translator that transforms programs written in the extended FORTRAN containing the new primitives into standard (deterministic) FORTRAN programs. One such translator can be easily implemented in FORTRAN if one makes suitable conventions about the form in which programs should be input. These conventions do not semantically restrict the set of extended FORTRAN programs that can be processed by the translator. It is shown that a simple finite-state grammar can be used to drive the translation. 3. To present examples of the usage and translation of nondeterministic FORTRAN algorithms. In what follows, the main features of Floyd's paper will be briefly reviewed. His example of an algorithm to solve the eight queens problem is also used to illustrate the usefulness of non-deterministic programs. This problem consists of placing eight queens on a chessboard in such a way that there is only one queen in each row, column, or diagonal of the board (see Fig. 1). A series of steps describing an algorithm to find one$ solution to the problem is the following: 1. consider the first column; 2. choose a row, i.e. a number from 1 to 8; 3. test if a queen can be placed in the current column and row. If so, go to Step 4; otherwise backtrack (i.e. 'undo' the actions that have been taken) to the previous point where a new choice can be made (Step 2); 4. place the queen in the current row and column position and list the row number for future display when a solution is found ; 5. test if all queens have been placed. If so, report the successful solution of the problem by displaying the list prepared in Step 4 and then stopping; otherwise consider the next column and go to Step 2. Notice that the actions that have to be 'undone' in case the test of Step 3 fails may entail removing one or more previously placed queens and erasing their row numbers in the list of Step 4. The translation of the above algorithm into a computerlike language can be easily accomplished by observing that the sum or difference of the indices of an element in a diagonal is constant. A convenient way to perform the test of Step 3, making use of this property, is to represent the chessboard by three one-dimensional arrays a, b, and c, whose bounds are respectively 1 to 8 (the number of rows), 2 to 16 (the smallest and largest values of the sum of the indices of a row and column), and -7 to 7 (the smallest and largest values of the difference of the indices of a row and column). A 'one' in ai, b,, and c, indicates that the ith row, jth left diagonal, and kth right diagonal are occupied. A 'zero' indicates that the corresponding row and diagonals are free. The test of Step 3 in the above algorithm is then translated into: Fig. 2 presents, in flowchart formythe algorithm just described to solve the eight queens problem. Notice that the terms CHOICE, FAILURE, and SUCCESS introduced in some of the boxes of Fig. 2 correspond to the expressions 'choose', 'backtrack', and 'report successful solution' used in the informal description of the algorithm. The reader may want to verify that the execution of the algorithm in Fig. 2 reaches the box SUCCESS if the variable row in the box row c choice (8) takes the sequence of values 8, 4, 1, 3, 6, 2, 7, 5 (see Fig. 1). The objective of Floyd's paper is to provide detailed information on how a flowchart describing a non-deterministic algorithm (such as that of Fig. 2) can be translated into a standard deterministic flowchart representing a program executable by a computer. We transcribe in Fig. 3 some of Floyd's transformation rules that enable one to automatically perform such a translation. These rules make use of three stacks M, W, R (for memory, write, and read) and a temporary variable T; an f denotes an arbitrary expression, an X an arbitrary variable, and a P an arbitrary conditional. Each row in Fig. 3 corresponds to one transformation rule: a non deterministic command in column 2 is transformed into a deterministic forward part under column C+ and a backtracking part under column C-. The forward parts of the commands specifying CHOICE, SUCCESS, and FAILURE are directly linked to their backtracking counterparts. The following comments are helpful in understanding the transformation rules presented in rows (a) to (i) of Fig. 3: (a) The assignment of an expression to a variable is preceded by stacking the previous value of that variable so as to recover it when backtracking. In two special cases, stacking is unnecessary: (1) the expression f is a function of X having a known inverse and recovery of X consists of assigning this inverse to the variable; (2) the programmer knows that the previous value of the variable is not needed when backtracking and specifies stacking as unnecessary. (b) There is no loss of information in the execution of a branch command; therefore, no special provisions are needed for backtracking. (c) A fork, i.e. the merging of two program paths into a single path is translated in the following manner: in the forward part of the program a marker (a 0 or a 1) is stacked in each of the merging paths, so as to enable the program to recapture the proper path when backtracking. (d) The starting point of the forward part of a program corresponds to the halting point of its backtracking part. (e) A CHOICE command is translated into a test which initially commands the program to take the forward direction of execution with X = f, the previous value of X being stacked as in the case of assignments. Subsequent returns to the CHOICE command when backtracking result in re-executing the forward part with a decreased value of X until it reaches the value 0; in the latter case, the original value of X is restored, and backtracking continues to the command preceding the CHOICE command. (f) When a SUCCESS command is reached, the contents of stack W (used in the write command) are displayed and one of two actions may take place depending on the programmer's option: the program either stops or proceeds in its backtracking mode. The latter option is useful when one wishes to compute all solutions that can be obtained by a non-deterministic algorithm. (g)The forward part of a program is directly linked to its. backtracking part. (h) The value of an output variable is stacked in win the forward part and unstacked when backtracking. (i) Two pointers 'max' and 'min' are introduced to keep track of the last element actually read (max) and the element that should be considered when the next non-deterministic read command is activated (min). The transformation rule as. presented in Fig. 3 is a corrected version of the one given by Floyd. His transformation rule for the read command contains a flaw which can best be shown through an example. Suppose the following sequence of commands is. executed : in ACM Computing Reviews 16(02) February 1975 view details |