Planner-BESM-6 Systems Implementation Methods

1. Introduction

Newer programming languages [1,2] in­ tended for use in Artificial Intelligence research have introduced many new facili­ ties that make much more easy the const­ ruction of sophisticated AI systems. The­ refore practical implementation of these languages and creating efficient methods for this are the necessary and important tasks for AI progress.

Among the new languages PLANNER [ 31 has gained the widest popularity. PLANNER was the first language introducing a ma­ jority of the new concepts and methode. Now PLANNER attracts much attention: many papers propose methods of its translati­ on, there are some practical implementa­ tions of it and others are being created.

PLANNER-BESM-6 system is an interpre­ ter. In some important aspects this sys­ tem differs from other PLANNER systems. The system has been designed to be an ef­ ficient practical tool, so the efficiency of the language implementation, which is the heel of Achilles for PLANNER, has be­ en given more attention rather than aiming to implement all without exception features of PLANNER. Some features which are not the main within the language but require the superfluous memory and time for their implementation have not been introduced into the input language of this system. For example the input langu­ age uses only recursive and backtrack re­ gimes and prohibits actors' utilization in matching patterns. This has enabled to use methods that increase the efficiency of the system work.

Together with the well-known techni­ ques (coo~dinates in data base organiza­ tion [3,~ , context number for fail­ pointe [5) and so on) PLANNER-BESM-6 sys­ tem uses some new methods. This paper briefly describes three of such methods. Backtracking is implemented with a single stack and without copying information in the stack. Lists are represented as ar­ rays of pointers which contain the length of lists; the garbage collection used for this representation requires no addition­ al space. Restrictions on variable values are accomplished with structures that are not fully defined.

2. Implementation of backtracking

There are some schemes for implemen­ ting backtrack control. For example the paper [51 proposes a scheme with two stacks. ~ut this scheme requires multiple transfers of information from one stack to another. The scheme of (6) usee one stack and is intended for implementation of various control regimes. This general scheme has been used to implement langu­ age POPLER 1.5 [7] which has sophistica­ ted control structure. However, being adapted only to backtracking, this scheme spends the superfluous space and time be­ cause it requires multiple copies of ac­ tivation frames.

PLANNER-BESM-6 system uses also one stacK for keeping frames of activations but no copying is needed, so this scheme requires less memory and time than the above schemes. The scheme is as followes [8] ·

There is a list called 'archive' that rou~hly corresponds to 'failist' of sche­ me L61 · Archive eaves information on changes of variable binding, data base and eo on, made by the program. For each changed object archive keeps its location in memory and its previous state. Using this the system will restore the previ­ ous states of the objects when a failure occurs within the program.

Stack contains information needed for fUnctions' elaboration. Upon entry to a fUnction certain storage, called a frame of the fUnction activation, is allocated in the end of stack. Any frame occupies always one continuous piece of stack spa­ ce. The head of a frame contains activa­ tion name a pointer Ar to archive and links of this frame: a pointer I (see be­ low), a pointer AL which specifies the variable bindings accessible within this frame, a pointer CL to the calling frame, and return address Rt to the caller (thus a continuation point is saved in the cal­ led frame). A frame may also contain in­ formation on exit actions of the activa­ tion. Another space of a frame holds tem­ porary intermediate results and local va­ riables' bindings, if any, of the functi­ on. During the whole activation the size of its frame is constant (while the con­ tents of frame may vary), so the size is fixed on activation entry and then does not vary.

If a function hasn't set any fail­ point during its elaboration and if the function exits, then the frame of this function is removed out of stack, i.e. e pointer a to the end of stack will again point to a cell upper this frame. If during an activation a failpoint has been set, then the activation frame is retained in stack. In this case the poin­ ter s ie, not changed. A consequence of this is that the frame of active function is not always located in the end of stack. For this reason there is another pointer r which always points to the frame of function that is active now. The active function uses this pointer in order to access i te own frame. Vlhen a new frame is created, the value of r becomes a link CL, and then r begins to point to the head of the new frame; later, when the function exits, CL will be transfered to r. Therefore without failpoints the poin­ ters s and r are changed synchronous­ ly, which corresponds to normal recursive regime.

~~en a function has to set a fail­ point, it allocated information on this failpoint in the last cell of its frame and then fixes a pointer f to this cell (the third stack pointer - f - always pointe to a cell of the last existing failpoint). This information consists of address PF of the previous failpoint cell and 'reaction address' RA that is an address of the interpreter instractions which will perform certain actions when a failure returns control to this failpoint. Fig. 1 shows the contents of the frame for (AMONG (4 IJCAI (USSR TBILISI) 1975)] in the moment when this function has set a failpoint before returning the first selected value - 4.

It is possible by comparing the poin­ ters r and f to determine whether or not a function has set a failpoint and hence to determine whether or not a frame of the function should be retained in stack. If on a function exit r < f then the function has a failpoint so the poin­ ter s is not changed, otherwise a va·­ ries. Fig. 2 shows the states of stack and pointers s, r and f at different moments of the elaboration of a function F which calls functions G, H and I in turn, the function G setting a failpoint and I calling a function J which genera­ tes a failure: a) G exits; b) H exits; c) J generates a failure; d) control is returned to G.

~ben a failure occurs, the interpre­ ter cleans stack up to the frame which keeps the last failpoint (the value of f is transfered to e) and then returns control to the reaction on failure within this failpoint. Since information on the failpoint is located in a frame of acti­ vation that has set the failpoint, the reaction gets an access to all informa­ tion of this frame, in particular to in­ formation needed for redoing the elabora­ tion of the function. Using this informa­ tion the reaction restores the pointer r, restores access environment with link CL, and then with scanning archive it resto­ res previous values of variables, pre­ vious state of data base and so on. Due to these actions the state of execution is restored. The further actions of re­ action are different for different func­ tions. For example, function AMONG will chop the next element off the list stored in its frame and then will return t~is element as new result. But if the list is empty then the function will destroy its failpoint (address PF will be transfered to pointer f) and failure will propagate upper.

An addition is necessary to the des­ cribed scheme. Let us consider the elabo­ ration of (AND e1 e2 e3 e4] · This func­ tion calls its arguments in turn until false occurs. AID sets no failpoint so it cannot catch a failure on its own. How­ ever its arguments may set failpoints and generate a failure. Hence AND cannot ma­ nage transfers of control among its argu­ ments. For example, let e1 sets a fail­ point and e) generates a failure that re­ turns control to e1. If the repeated com­ putation of e1 succeeds then control is returned to AND again, but this function will not know that it should call e2 and not e4.

This mistake is easily rectified. When a function calls another function, the calling one gives some information (a pointer I) to the called one to keep it. When the lower function finishes it returns this pointer together with its result. As a rule, I is a pointer to the list of arguments followed the argument evaluated now. The returned pointer in­ forms the calling function which argument should be evaluated at the next step. Hence the correct work of the calling function is not broken by transfering control from one argument to another.

All functions of PlANNER for back­ track regime, in particular non-local go­ to and failures directed to a point, were implemented within the bounds of the des­ cri'bed scheme.

). List representation

In PlANNER the main operations on lists are more complex than, for example, those in LISP. There are scanning lists from both the ends, selecting any element or segment from list, matching list-pat­ terns. The usual list representation (as in LISP systems) is not effective for elaborating these operations. For example a match of lists requires easy determi­ ning the list lengths but it is impos­ sible with this representation. On the other hand, the operation cons, effici­ ently implemented with this-representa­ tion, is not typical for PlANNER. More­ over the usual list representation leads to scattering list cells all over the me­ mory, which is inconvinient for the pa­ ging of virtual memory used in PIANNER­ BESM-6 system.

In view of this, PIANNER-BESM-6 sys­ tem uses a different list representation, namely, a list is represented as an array of pointers (see Fig. 1). A pointer to a list consists of three parts: the initinl address of array, the length of array and a type indicator (each data type has its own indicator). A list length used in a pointer makes easy to match patterns and to scan lists from the end. Successive location of list elements makes easy to select any element or segment. Due to such representation lists and tuples are not distinquiehed. In addition, this re­ presentation partially (on the highest level) localizes list cells in memory.

A pointer to integer is the same in­ teger with fixed exponent which is also an indicator of type 'integer'. Pointers to other data types consist of two parts, viz., type indicators and references to property cells of data. Free space of these pointers is used for various aims, for example to list all labels of functi­ on PROG.

The list representation described re­ quires the free space of list memory to be one continuous segment. The interpre­ ter fills this space from bottom to top, hence the garbage collector must pack re­ levant pointers and move them down, modi­ fying references of these pointers. Mul­ tiple references to inside of lists make difficulties for this moving and for re­ ference changing, so the garbage collec­ tion used in PLANNER-BESM-6 system takes three stages. But this garbage collection is simple and doesn't require additional space, and this differs it from other me­ thode of garbage collection with packing.

The first stage is to mark cells of lists needed for the further runnig of program. This is performed as in LISP systems, besides the total amount of marked cells is counted.

The second stage is linear scanning list space from top to bottom and chang­ ing all references down (i.e. references to cells with larger addresses). This changing is performed as follows.

Let a current examined cell a is marked and also contains a reference to cell b ( b > a ; in this stage all refe­ rences up are ignored). Then the garbage collector interchanges both the referen­ ces of cell a and b, and if this referen­ ce to cell b is the first one from top then both the cells a and b is marked by '+' (this marker is distinct from the marker used in the first stage). Then cell a+1 will be examined.

If a current examined cell b contains the marker '+' then at this moment the cell b contains also the initial address of list of cells a 1 , a,, o·· , a

( ai < ai+ 1 , an< b ) whH~h have n had

the references to cell b before. At this moment address b' which should be as­ signed to pointer of cell b is known: b' is defined by the total amount and the amount of already examained marked cells. So the garbage collector in scanning the chain of cells en' ··· , a 2 , a 1 puts the address b' into them. The last cell a 1 of this chain is marked and contains the reference that has before been placed in cell b, so this reference is transfered to cell b, marker 1 +' is removed out of cells a 1 and b, and then the contents of cell b is treated on common base.

In PLANNER-BESM-6 system the list space is placed in the bottom of memory, hence all references from other spaces to this space are references down. In order to avoid scanning other spaces in the se­ cond stage, all references of those spa­ ces to the list space are treated in the first stage as described above.

The third stage of the garbage col­ lection is linear scanning the list space from bottom to top, moving all marked pointers (to the space bottom) and chang­ ing all references up. This stage is si­ milar to the previous stage but each re­ ference up is moved to new location first and then its new address is used.

4. Restrictions on variables

Matching two patterns is used in function MATCH or during theorems' invo­ cation. One of problems here is the im­ plementation of restrictions on variable values. When a pattern matches another pattern some variables get no values but their future values are constrained. Fot example on elaboration of [MATCH *X *Y J (prefix '*' means 'to assign value to va­ riable') no variable gets a value but their future values will be equal. An­ other type of restrictions appears in matching a variable with a list which contains variables. For example on elabo­ ration of (MATCH *X (*Y A .Y)] the fu­ ture value of X will be a list with three elements, the second of which is atom A, two others are equal and are the future value of Y (prefix '·' means 'to get va­ lue of variable').

Since the input language of PLANNER­ dESM-6 system prohibits actors' utiliza­ tion in matching two patterns, restric­ tions on variable values may be of the above types only. This restrictions are implemented in such manner.

New data type 'semi-defined structu­ re' is introduced. This is a structure a part of which is not defined, namely, a inner (not accessible to users) variable without a value or a list some elements of which are semi-defined structures. If a variable gets no a fully defined ('re­ al') value in matching then its value (SD-value) will be a semi-defined struc­ ture. This SD- value is constructed with the pattern which has been confronted to the variable: all variables of the pat­ tern are substituted by their values, in particular by 3D-values, wherever pos­ sible; the rest of variables get refe­ rences to some inner unassigned variables as values, and then these references are inserted into the pattern. Thus any va­ riable has a value always but SD-value is not accessible to users.

In matching SD-value behaves as well as 'real' value: object confronted to a variable with SD-value must match SD-va­ lue. A consequence of this is that a va­ riable may get only the 'real' value that matches the existing SD-value. In general case, any new restriction on variable va­ lue is immediately checked on compatibi­ lity with the existing SD-value, and if they do not conflict then their 'inter­ section' will be the new SD-value of the variable. This check often allows to de­ fine the full value of variable in proper time. For example this takes place for [MATCH (*X .X) ((·YA) (B *Z))).

Cross-references among 'real' variab­ les are accomplished by SD-values since in general case each inner variable is referenced by some semi-defined structu­ res. If a semi-defined structure is fil­ led in fully or partially then all or so­ me inner variables referenced by this structure get values, and hence some other semi-defined structures are also filled in fully or partially. Since cross-references among 'real' variables are accomplished indirectly, through in­ ner variables the existence of which doesn't depend on the existence of 'real' variables (but depends on amount of refe­ rences to them), so it is not necessary to retain 'real' variables in memory only because of the program has defined links among other 'real' variable by those. So when a theorem has set no failpoints then its frame is removed out of stack even if there are cross-references among global variables through its local variables, because the existing inner variables are holding this links.