FORTRAN-based non-deterministic language(ID:7403/for076)

Non-deterministic language based on Floyd-Evans', but derived from FORTRAN

Related languages
Floyd - Evans language => FORTRAN-based non-deterministic language   Derivation of

  • Cohen, J. and Carton, Eileen "Non-deterministic FORTRAN" pp44-51 view details
          in The Computer Journal 17(1) February 1974 view details
  • Fleck, A.C. review of Cohen 1975 view details Abstract: This paper describes an implementation of nondeterministic programming facilities by means of the technique suggested by Floyd [3]. The facilities are exactly those described by Floyd!
    and the discussion relates to their addition to FORTRAN.
    In this reviewer's opinion, the reader will have difficulty with this paper unless he has a reading of Floyd's paper freshly in mind.
    Many details are omitted, with a reference to that paper in their stead. Even one of the two examples presented (the eight queens problem) is taken directly from Floyd. The author" also point out an erTor in Floyd's implementation scheme.
    The syntax of the added language features is given in BNF
    No attempt is made to give a formal definition of the semantics. In fact even the informal definition is through examples (again, as is the case in Floyd). The authors provide section which briefly treats the process of the generation of the object code suggested by Floyd in the translation to a deterministic program. An indication is given of some simplifying assumptions that were made so that the syntax analysis could be accomplished by finite state techniques. A state graph is given for guiding the parsing; the graph resented may be desirable for exposition, but it is not minimal; its 57 nodes may be reduced to 21. This is the one section the reviewer found that really adds anything to Floyd's presentation, but, again, so many details are omitted that the presentation is difficult to follow.
    This reviewer found a conspicious absence of comparison with other work. There are now several implementations of nondeterminism (for instance, PLANNER [ 4 ] , ECL [ 6 ] , REFARF [ 2 ] , and MLISP2 [ 1 ] ) to serve as a basis for such comments. Also, an implementation can be used to shed further light on the sensitive issue of performance (see [ 5 ] and [ 7 ] and, again, comparison with other implementations would have been of interest.

    [1] Canfield, D. C., and Enea, H. J. Backtracking in MLISP2, Proc. IJCAI 3, (1973), 677-685.
    [2] Pikes, R. E., "REF-ARF: A system for solving problems stated as Focedures," Artificial Intelligence 1, 1 (1970), 27-120; CR 12, 1 (Jan. 1971), Rev. 20,486.
    [3] Floyd, R. W., "Non-deterministic algorithms", J. ACM 14, (1967) 636-644 CR 9, 6 (June 1968), Rev. 14,507.
    [4] Hewitt C., "PLANNER: a language for proving theorems in robots", Proc. IJCAI 1, 1969, 295-301; CR 12, 4 (April 1971), Rev. 20,968.
    [5] Knuth, D. E., "Estimating the efficiency of backtrack programs", Stanford Univ. Report, Computer Science Dept., Aug. 1974, 29 pp.
    [6] Prenner, C. J., Spitzen, J. M., and Wegbreit, B., An implementation of backtracking for programming languages", Proc. ACM Nat. Conf., 1972, 763-771.
    [7] Sussman, G. J., and McDermott, D. V., "From PLANNER to CONNIVER - a genetic approach", Proc. AFIPS 1972 FJCC, Vol. 41, Part 2, 1171-1179.

    Extract: 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