CONNIVER(ID:606/con032)AI language for automatic theorem proving. An outgrowth of PLANNER, based on coroutines rather than backtracking. Allowed multiple database contexts with hypothetical assertions. Structures: Related languages
References: in [AFIPS] Proceedings of the 1972 Fall Joint Computer Conference FJCC 41 view details in Courant Symposium on High Level Level Languages, Computer Science Department of the Courant Institute of Mathematical Sciences, May 22, 1972 view details in Courant Symposium on High Level Level Languages, Computer Science Department of the Courant Institute of Mathematical Sciences, May 22, 1972 view details in ACM Computing Reviews 15(04) April 1974 view details The PLANNER concept was developed by Hewitt at MIT starting in 1967 (Hewitt 1971, 197Z), and Sussman and Winograd built a first implementation, MICRO-PLANNER, which contained a subset of PLANNER features. These projects established the basis of the currently popular concept of procedural representation of knowledge. CONNIVER is a recent attempt by Sussman at MIT to remedy some observed shortcomings in the practical use of PLANNER, while preserving its good ideas. in [ACM] ACM Computing Surveys (CSUR) 6(3) September 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 Control structure in CONNIVER is based on the following potpourri of constructs: [...] The standard CONNIVER co-routine scheme is particularly culpable in this respect. The scheme (which is adopted from PAL and GEDANKEN) consists in returning a "generalized tag" from a program so that at some later time another program can communicate with it by executing CONNIVER expressions of the following form: (csetq n vl T) ; assign n the value vl where (hopefully!) n is the name of a local variable in the Landin style ; generalized tag T or some program that called the program which created T (go T) ; execute a PAL-GEDANKEN style nonlocal goto back into the middle of the ; program that created T and resume execution at the point after the tag Unfortunately, the above mechanism will cause non-reproducible timing errors in the presence of parallelism. Two processes communicating with T in parallel will occasionally lose when the following sequence of events occurs: Process1 Process2 (csetq n vl T) (csetq n v2 T) (go T) (go T) The above kind of bug can occur even in the absence of parallelism if the programmer who codes the routine with the "generalize" tag. T is not very careful. The value of the variable n will be clobbered if a subroutine is called which desires to communicate with T. This may destroy the previous message to T before it has been read. Dijkstra has remarked that the use of the goto is associated with badly structured programs. We concur in this judgment but feel that the reason is that the goto is not a sufficiently powerful primitive. The problem with the goto is that a message cannot be sent along with control to the target. It is exactly this property of actor transmission that makes it into a universal communication primitive. Suitability for a Programming Apprentice: The side-effects in the CONNIVER control structure primitives force the programming apprentice to go through the trauma of McCarthy frame shift on every function call. Very complicated deductions must be performed to determine simple properties (such as whether a local variable still has the same value as before). in ACM Computing Reviews 16(02) February 1975 view details in ACM Computing Reviews 16(02) February 1975 view details Planners are specialized production-system programs. In a production system the control responsibility for rule selection may be contained within the rules, lie outside the rules or be some combination of the two. Backtrack-control information in Prolog, for example, is found in the clauses. A lack of domain-specific control knowledge can lead to inefficiency in planning. Early examples of control information incorporated into the rules are PLANNER, QA4 and CONNIVER. The STRIPS model was one of the first applications of forward production. In the STRIPS model the world consisted of blocks that could be moved around by a simplified robot hand. Blocks could be cleared, placed on top of each other and the robot hand could be emptied. Several precondition formulas (used as implicational rules) constrained production-rule firing. A database described the world to which additional structures were appended. Forward production rules modeled robot actions which altered a global database. The STRIPS approach generates plans in advance but error in execution can cause plan failure. Improvement is obtained by applying partially executed, and previous plans, via plan splicing or dynamic replanning. These techniques provide an error execution recovery scheme. Domain specific knowledge must be incorporated in any planner that plans for real-world problems on a local level. in ACM Computing Reviews 16(02) February 1975 view details |