LORD: LISP-Oriented Resolver And Data Base

Introduction

The AI problems require incorpora­ tion ~f new features into the traditio­ nal programming systems. These features include: the availability of powerful vehicles for creation and amendment of structured data elements - lists, sets, texts; comfortable and efficient forma­ lism for representation of knowledge in different problem domains; new techni­ ques for "non-algorithmic" progra-ing style, such as pattern - driven proce­ dure invocation and automatic backtrack­ ing; the availability of standard proce­ dures for the associative search in Data­ Base; automatic logical inference, etc.

Some of these features could be found in LISP, REFUL, ~NOBOL, and also in "big" language systems such as PL/1, APL, ALGOL-68. At the same tim~ there exists a growing tendenc~ !or the design of new languages combining the best techniques and most su1t~d for AI appli­ cations (1).

The system descr1b~d hPrPin - Lisp­

Oriented Resolver and Pata-lla,P - is designed at the Computing Center of the USSR Academy of Sciences with the purpo­ se to provide an efficient instrument tor different AI applioations(2) · The system is designed on the ~sis of some essential ideas being derived at the different scientific groups and materia­ li~ed in the imple·entation of some expe­ rimental systems, vim., PLANNER, CONNI­ VER, LISP-?0, SAIL, QLISP, POPLER 1.5.

r.eneral System Organimation and Data-Base

The LORD system consists of three relatively independent parts: Resolver, Semantic Memory and Metaprocessor. Each of these parts uses similar techniques tor memory allocation, function storage and call meohanisas, lexical analysis procedures etc. The Data-Base (DB) is the common ground for keeping and retrie· 'WLl. of both program and data elements.

DB baa a fixed number of hierarohi­ cal levels. The largest section of DB is an area. Each area is identified by its name and may contain an arbitrary number of sets. A set consists of records each of which contains a full characteristic of an object. Usually, such an object is generated and used within the boundar i es of a specific user task. The access t o the objects is performed by means of bash function (standard of individual for each set).

Objects may have several different properties, and each property bas its own value (sometimes a list of values) . List of references to the properties is stored in the body of the record corres­ ponding to the given object. Rach pro­ perty in its turn is stored as a separate object with property indicator used as an object name.

Thus in the hierarchical DB we have the following levels associated with system notions:

Data-Base divisions LORD notions

area problem domain

set context

reoo rd object

field property

contents of the

field value of the property

The LORD access language is provi­ ded with functions for establishing the name of the problem domain and the name of the working context. Special referen­ ces are generated during the creation of new objects and addition of new pr~r­ ties to the existing objects. According to these references the objects and the values of their properties may be deri­ ved from DB later.

In many AI applications it is necessary to create the hierarchy of contexts (and even the hierarch¥ of problem domains). This is provided by automatic bookkeeping of special "set of references" containing the objects which values are pointers at the diffe­ rent DB sections. The hierarchy of con­ texts or problem domains is represented by interconnections of the objects in this reference set.

Semantic Memory

One of the most important problems in AI systems is accumulation of infor­ mation representing "knowledge" about some problem domai~. There are two di­ stinct approaches to the techniques of knowledge representation. One way 1s to use a set of expressions describing separate facts or hypotheses. Single expression may represent the relation between two objects or between an object and its properties, or between two or more different facts. Another approaCh is based on the utilization of a set of procedure·~ Procedure execution checks the existence of definite relations binding specific objects, properties or facts.

These two approaches, "relational" and "procedural", are often intermixed in actual implementations. Semantic Memory in the LORD system is intended to serve the same purpose. Accumulation of knowledge about different problem doma­ ins, structuring of accumulated infor­ mation according to predetermined heir­ archy, and retrieval of relevant notions and facts - these are the main functions provided by Semantic Memory.

The examples of simple expressions processed by the Semantic Memory: (PRODUCT :IS-SET= (CARS, OIL, CRAIN) )(A1) (PRODUCT :HAS-PROPERTY: SHORTA�E)~ (PRODUCT :BECOME-AN-OBJECT-OF: BLACK-MARKET-OPERATION) (A2)

After processing ?f these expres­ sions special DB sections are filled. These sections are named NOTION - LIST and FACT - LIST.

1. New objects: PRODUCT, CARS, ··· appear in the NOTION-LIST if they were not put there earlier.
2. Expressions A1 and A2 are placed into the FACT-LIST, and identifiers A1 and A2 become the names of the correspon­ ding objects, text of the expression be­ comes the value of the main object pro­ perty.
3. )) Each object in the NOTION-LIST is accompanied by the property list. One of the properties has the value showing the object type, another property is evaluated into a list of references to all facts containing the given object. Examples of objects being stored in the NOTION-LIST:

PRODUCT ·-+ type SET,facts (A1 A2) OIL ~ type SET-ELEMENT, facts (A1) SHORTAGE -type PROPERTY, facts (A2)

Besides the above mentioned sections there is also RELATION-LIST in DB. In a sense this list is a subset of NOTION­ LIST, - all system and user defined re­ lations are kept in this sections, e.g., IS-SET, HAS-PROPERTY etc.

Semantic Memory performs processing of the input expression and all the ne­ cessary changes in the DB. Furthermore, the Semantic Memory processor provides answering simple questions of the type:

(OIL :IS-SET-ELEMENT-OF: ?X) (?)

The answer is based on binding the pattern variable ?X with the object PRODUCT, which results from the analysis of the property list of the object OIL and "backward" processing of the fact A1.

Besides filling DB with the ~imple facts, expressions describing complex structures may also be input to the Semantic Memory. One form of comlex ex­ pression could be the definition of the function which governs the ·aintainance of Semantic Memory. An example of such

a function is:

(PROPERTY-TRANSFER :IS-FUNCTION-OF:

(?Y, ?P),

:TYPE: WHEN-ADDED,

:PATTERN= (?Y :HAS-PROPERTY: ?P),

:BODY: ( * FIND ( $Y :IS-SET-ELEMENTOF: ?X);

"'FIND ( JX :HAS-PROPERTY:$P)~

This function acts as an analogous IF-ADDED function in CONNIVER, i.e., evaluates operators in the function body when the fact matching the giYen pattern is added to the Semantic Memory. Here ?Y, ?P, ?X, ?R, ?Q are pattern-variables and S Y, f P, ··· are the c orrespon­ ding values, obtained by pattern-varia­

bles after successful matching.

Therefore the apperance of the fact (OIL :HAS-PROPERTY: SHORTAGE) in the presence of A1, A2 and A3 implies automatic addition of the fact: (OIL :BECOME-AN-OBJECT-OF:

It is worth noting that A3 has the same format as expressions defining the usual relations, e.g., A1 and A2. That is why A3 may be amended in the same way as any other fact in the Semantic Memory. For example, the following question may be asked:

(PROPER'll'f-TRANSFER :IS-FUNCTION-OF: ?W, :TYPE= ?X, =~ATTEHN: ?Y, :BODY: ?Z) (?)

In order to ~erive an answer pat­ tern-variables ?W, ?X, ?Y, ?Z get as values the corresponding texts picked up from A). Thisfeature gives a convenient ability to investigate and modify the system by its own means.

Standard object types are establiSbed at the time of system creation, e.g., constant, object, relation name, function name, etc. A user may also introduce his own types using existing relations, their logical compositions

and modalities.

Any fact and notion have a limited scope - DB context. We call it "static" context as opposed to "dynamic" context being dealt with in control structures discussed in ~e next paragraph. The Semantic Memory access language contains operations for manipulating statio con­ texts - rearrangement of the context tree, removing contexts, uniting them with each other, generating new contexts. As it was mentioned, these operations are performed by processing the special reference set.

Resolver

While the Semantic Memory is used mainly for storing and retrieval of facts, functions, objects and their pro­ perties, the Resolver serves for evalua­ ting the procedures carrying out diffe­ rent kinds of logical inference, search­ ing AND/OR trees, reduction to disjunc­ tive normal form and other general or specific functions.

The Resolver may be considered as an extension of LISP containing new fa­ cilities both in the input language and in processor implementation. A brief list of these facilities follows. Notation

One of the doubtless requirements for Resolver implementation is the abi­ lity to process programs written in stan­ dard LI0P [J]. At the same time special preprocessor can accept and translate into standard LISP-notation the expres­ sions written in ALGOL-like input langu­ age, e.g.,

BEGIN NEW X,Y; X:: '(1 )); Y::

X CONS CDR(X); RETURN(Y) END

The given notation is similar to that of MLI3~2 [5] and is characterized by the absence of superfluous parenthe­ ses, infix notation of most operators and usual mathematical notation for function calls.

The operator and function set is provided with the priority system which facilitates writing and reading complex ~xpressions.

A-points and backtracking

Resolver has the ability to back­ track programs which implies restoring of program and data state in some previously passed point and choosing and initiating an· alternative path of solution as in (5]· A-point (alternation point) is set up by the call for one of special func­ tions: REP (repetition), ALT (alternati­ on) and OPT (option). Generation of fai­ lure and return to the last A-point is produced by the function FAIL which is called directly or indirectly, e.g., on unsuccessful pattern matching. Backtrac­ king mechanism compels talking about "dynamic" con text defined b.v ace ess link, binding link, control link and process state in the sensa of Bobrow (1).

The numbers of generated and elimi­ nated alt.ernative branches (dyns.mic con­ texts) are fixed as values of special system variable APOINT. There is a possi­ bility to transfer new values to the "hi­ gher" dynamic contexts. This is accompl­ ished by the following generalized assi­ gnement operator:

(SETQ u (n1 n2 ··· np) v) , where n1, n2, ··· , np stand for A-point numbers (possibly expressions evaluated to numbers) indicating the dynamic con­ texts, where variable u has to accept the new value v. The particular form of this operator:

(SETQ u v)

changes the value of u in the current dynamic context. Another particular case:

(SETQ u (GLOBAL) v)

changes the value of u in the whole pro­ gram.

Indirect function calls and debugging aids

One of the most important trends in modern "non-procedural" programming is the use of indirect function calls. In LORD this is achieved by means of pattern - directed function call, suspension of function evaluation and "by-passing" of

functions.

The idea and implementation of pat­ tern-directed function call are analogo­ us to the corresponding facilities of PLANNER and CONNIVER (4]. The main point is the inclusion of function call pattern into the function definition expression. Resolver performs only one type of pat­ tern call, namely: a function with a pat­ tern is called when some variable is as­ signed a value which represents an object matching the function pattern. This WHEN­ ASSIGNED type of call is used for initia­ tion of relevant procedures when specific information appears in the current dyna­

mic context.

Two other types of call, WHEN-ADDED and WHEN-REMOVED, relate to the Semantic Memory processor, i.e., to addition and removing the structures matching the function pattern.

The suspension of function evalua­ tion is performed by the operator (STOP f m) which interrupts evaluation of the function f containing this operator. The control is transfered to the dynamic con­ text, embracing the call of function f. The argument m is a message (a value of interrupted function f) being sent to the embracing program. If later the ope­ rator (CONT f) is met then evaluation of f will be resumed from the point of in­ terruption. This tool permits the syn­ chroni~ation of computational processes; moreover, combined with conditional ex­ pressions it may be used for organi~ation of alternative branches.

"By-passing" of function calls faci­ litates debugging operations. It is im­ plemented by substitution of a debugging function g everywhere instead of "suspec­ ted" function f. The substitution is per­ formed after evaluation of the expression (BYPASS f p g) · Predicate p is evaluated each time when function f is called. By­ passing is taking place only if p is true.

Other debugging aids are: setting-up the maximum number of calls for the spe­ cified function, establishing the "alarm clock" for the current dynamic context,

etc.

Interaction with Semantic Memory

The Resolver interacts with Semantic Memory processor by means of functions ADD, REMOVE, FIND, CHECK and others, which perform storing and removing expre­ ssions from the DB, associative search by a given pattern in the static context, check for the presence/absence of defini­ te object properties etc. While the Re­ solver is dealing with atoms, lists and texts, Semantic Memory may contain ob­ jects of different types, such as set, tree, arbitrary structure. The Semantic Memory processor is capable of perform­ ing such actions as union and intersec­ tion of sets, check for membership, etc.

Special types of predicates in Re­ solver - existential and universal quan­ tifiers - are also implemented with the use of FIND and CHECK operations in the Semantic Memory. The corresponding exp­

ressions in Resolver:

(EXIST (x1 x2 ··· ) e c) and (FORALL (x1 x2 ··· ) e c) ,

where x1, x2, ··· -quantifier variables, e - expression, evaluating the conditions of quantifier application, c - static context.

There is also an aggregate operator:

(FOREACH x p e),

implying the execution of expression e for each object x in Semantic Memory satisfying predicate P·

Metaprocessor and function compilation

Resolver and Semantic Memory accept the expressions satisfyin~ formal syntax. In the meantime the idea of giving the user the ability to create his own versi­ ons of input language becomes more and more popular. For thispurpose LORD system contains Metaprocessor which is similar to· the one designed for MLISP2 (5].

Metaprocessor manipulates the seque­ nce of grammatical rules which have the following format:

DEF f (x1, x2, ··· ):(syntax>

MEAN <semantics> ,

wher f stands for metavar1able name or program name; x1,x2, ··· -parameters;

<syntax) defines the formal structure of an input phrase; (semltics) - seque­ nce of functions to be evaluated by the Resolver or the Semantic Memory processor.

A set of these rules defines a for­ mal context free grammar which describes the specific version of the input langu­ age. It is worth noting that this could be a simple "functional" language, where each name f corresponds to the program composing the (semantics) · Such a pro­ gram could be initiated either by functional expression f(x1, x2, ··· ) or by some phrase oorrespondLng to the g1vea (S7Jltax> ·

On the other hand, the nontrivial language with deep phrase structure could be defined by means of metava~~ables used in the syntax of some rules. Thus a special language system could be imple­ mented, which finally is interpreted by means of LORD Resolver and Semantic Memory.

The role of (semantics> could be il­ lustrated by the following example. Suppo..,. se we would lik· to create a LISP-dialect to be translated into standard LISP 1.5 program. In this case the sequence of grammatic rules will define the general syntax of the LISP - dialect expression With the topmost rule looking as follo­ ings

DEF f (x1, x2, ··· ) =

(general-syntax-of-LISP-dialect­ expression)

MEAN ( GENER<file,, (OUtput-string>­ LISP<file:>)

where (output-string~ contains pieces of LISP 1.5 program icorporating x1, x2, values provided by syntax analyser.

< semantics> in this example includes

two macrocalla:the first one generates LISP 1.5 text in the specified file, the second one calls LISP 1.5 translator with generated file as a source of input.

I11. the similar way we could define any context free input language with semantic interpretation provided by the programming language which exists in the computer already.

All fumctions composing the seman­ tics are compiled into macro-assembler language and then into machine code. The modules of compiled code are stored in the Data-Base. The LORD Monitor calls them from the DB according to Resolver and Semantic Memory functioning.

B~sides DEF expressions Metaprocessor· accepts also special command operators serving in on - line interaction with the LORD system - this includes editing text files, switching to different ope­ ration modes, choosing input/output channels, etc. [6J.

Conclusion

The design of a new system capable of successful competing with conventional widespread programming languages such as LISP or PL/1 is a hard and fascinating task. The ground for optimism, lies, on the one hand, 1n the fact that many of the ideas comprised by the LORD project are tested to some degree 1n experimental systems such as CONNIVER, MLISP 2, POPLER 1.5. On the other hand, people connected with this project are involved in system implementation as well as in developing methods of its usage for solving practi­ cal AI problems. In particular these problema are connected with system ana­ lysis research for business and environ­ ment control, construction of information retrieval systems and natural language processing.

The necessity for intelligent systems of this kind is urgent, and even the prototype design will make a valuable contribution to the experience of const­ ructing and usage of AI systems.