NASA Contractor Report I?80tt8

(NASA-CR-178018) IMPLEMENTATIO N OF N86-21220

ABTIPICIA1 INTELLIGENCE BUIES IN A DATA BASE

MANAGEHEN T SYSTEM (VAIB, Inc.) 64 p

HC AOVH F AOJ CSCL 09B Dnclas

G3/63 05649

n.

Stefan Feyock

Williamsburg, VA 23185

NASA Contract NAS1-18OO2

February 1986

NASA

National Aeronautics and

Space Administration

Langley Research Center

Hampton, Virginia 23665

Vsssj
PROJECT OVERVIEW

Project Goale

It appears appropriate at the outset to recapitulate the

goals of the project. They were as follows:

1. Transform the intelligent front-end prototype into a

RIM-integrated system.

2. Write a RIM-based expert system which demonstrates the

developed capability.

3. Investigate the use of rules to produce extensibility of

the intelligent front end. including the concepts of demons and

rule-manipulation rules. Innovative approaches such as syntax

programming were to be considered.

i

All of these tasks were performed successfully; the results

form the content of this report. The purpose of the present

section is to present an overview of the project's development,

leaving presentation of technical detail to subsequent sections.

Paths to the Goals

The facilities available at the beginning of the project for

achieving the above goals consisted largely of the LProlog

system, a Pascal program created by the author which embodied

Page 1
list processing facilities similar to LISP, as well as a Prolog

implementation based on these list-processing capabilities

("LProlog" denotes "Lisp-Prolog"). The initial decision to be

made before the project could progress concerned the question of

which facility was to form the intelligent front end: LProlog.

Franz Lisp [Foderaro], or the Pascal-based University of York

Prolog Implementation [Spivey]. After extensive consideration

the York Prolog interpreter was chosen. Reasons for this choice

Include power and efficiency. which gave It the advantage over

LProlog. and compactness and linguistic compatibility (Pascal

•*

talks easily to other languages and systems), which caused it to

preferred to Franz Lisp.

It is Interesting to note that hindsight has shown this

decision to be largely immaterial: the techniques developed

would have led to successful (and analogous) solutions

regardless of choice of vehicle. More precisely. It was the

concept of the escape predicate that was crucial to the

Integration of RIM with the chosen front end. and such a

function could have been Implemented In any of the candidate

systems. The chief effect of choosing York Prolog was to allow

the creation of extremely concise and elegant programming

solutions. as well as a natural Integration of RIM as a stream

object into the Prolog model. The Insight that Prolog Is useful

and natural but not indispensable has important implications for

future work: systems other than Prolog can serve as front end.

hence users who are not Prolog programmers can make use of our

Page 2
results.

As will be seen. even the present Prolog-based system can be

made quite friendly to users who have a basic knowledge of

Prolog but do not program the language at the expert level.

Subsequent sections will discuss the stream and rget procedures,

both of which are high-level facilities that are easily

understood and can be used to create powerful Intelligent

database systems. The concept of rules as views allows simple,

powerful, high-level constructs to be created from complicated

low-level ones. Finally. constructs such as coroutines and

i

demons are constructed on the basis of program templates. which

can be filled in by the programmer In a straightforward manner.

The RIM/Prolog system, named YRIM, that was constructed as

described was used to create TURBO. a RIM-integrated expert

system for det engine diagnosis. The result is a concise but

powerful system whose rules reside in Prolog but which Is driven

by time-based data stored in RIM. The most salient feature of

this program is the complete Integration of RIM and Prolog:

unless he examines the program. the user has no way of knowing

whether the data he is accessing is stored in Prolog's internal

database or in RIM. A subsequent section contains a detailed

discussion of TURBO.

The final application of our system was to the design of

STRUTEX. an expert system for structural design. A design was

developed for STRUTEX, as were YRIM programs based on that

design; lack of time. however. precluded development of a

Page 3
running Implementation.

Looking Ahead

In light of the clear appropriateness of YRIM for the

creation of TURBO. possibly the most Interesting result of the

STRUTEX exercise was to brine to light a number of areas for

which our system appears to be Ill-suited. Perhaps the greatest

difficulty arises when the appropriate role of the Prolog

portion of the system Is to act as subroutine rather than main

program; Prolog has extreme difficulties accepting such a

subordinate role. The Idea of using the coroutine capability

which was developed was considered as a possible design for

STRUTEX, but this solution appeared unduly complicated. We were

led back. Instead, to the Idea presented above: that the

techniques developed are widely applicable. and that the use of

Prolog as front end Is Interesting and productive but not

essential. The most obvious task for the future Is to explore

other front ends based on the same Interfacing concepts,

particularly front ends suited to the requirements of STRUTEX.

Page ft
THE PROLOG/RIM INTERFACE

The escape Predicate

As has been Indicated. the escape predicate Is the heart of

the Prolog/RIM Interface; moreover, we have noted that similar

predicates can serve as Interfaces between a variety of other

systems. escape would work as well. for example. as a

Prolog/graphics package Interface. or an LProlog/RIM interface,

etc. In fact. the only requirement appears to be lists or

list-like structures in the calling language (i.e. the language

calling the escape), since otherwise the operations needed to

set up and decode escape * s parameters are too cumbersome. The

fact that few languages besides those oriented toward Artificial

Intelligence feature list structures as primitives. rather than

a construct to be defined by the programmer, may account for the

fact that the escape mechanism we are about to describe is not

universal.

In YRIM the escape predicate is added to the Prolog side of

the interface; it is installed in Prolog as a new evaluable

predicate. Details of this Installation are given in the IFACE

section of the accompanying program documentation.

Page 5
Here Is the design of the -escape predicate as It was

implemented:

eBcape(X.Y)

list containing resul't returned

information on • in this argument

operations to

be performed :

The input list X is expected to be a linear list of atoms

(symbolic or numeric); the result appears bound to Y, and also

has the form of a linear list of atoms. Note that quoted strings

are legitimate atoms in Prolog, so passing a list

[floatadd. '37-. 82'. '-'10.O36']

>

Is a feasible method of implementing real addition in Prolog.

Moreover, while the information that can be passed is quite

arbitrary, the format

[<action_code>, <arg>, ^ ]

is typical.

The Interface between Pascal and Prolog consists of a set of

procedures within the Prolog implementation that move the values

of the input list elements to a parameter buffer internal to the

Pascal program on the Pascal side of the interface, whence they

may be manipulated by the Pascal program as desired. Returning

parameters to Prolog is the reverse of this process: the result

values are placed In the parameter buffer. and Interface

routines use these values to create a Prolog list and bind It to

the second parameter of escape. The reader is again referred to

Page 6
the program documentation for details.

AB Indicated above. the format [<actlon_code>, <arg>, ]

is typical for Input parameter lists. I.e. parameters to be

passed to the escape predicate In a list bound to the flr'st

parameter. This means that the appropriate format for a Pascal

program Implementing: escape Is a case statement on

<actlon_code>; in other words, the Pascal program is typically

an Interpreter interpreting commands of the form

[<action_code>. <arg>. ].

As implied by this discussion. the Pascal program that

Implements the actions taken by escape is quite arbitrary, and

can contain facilities limited only by the imagination of the

user. We have in fact implemented escape as a separately

compiled module, thus facilitating the addition and modification

of escape capabilities. This module is Included in the RIM_MOD

section of the program documentation. For the purposes of YRIM,

the cases correspond to the RIM interface operations described

in the subsequent discussion of escape.

The design and implementation of the escape evaluable

predicate. while requiring a thorough understanding of the

mechanisms and data structures underlying the Prolog

implementation, was reasonably straightforward. It is therefore

rather surprising, in view of the profound implications such a

capability has for logic programming, that this feature is not a

standard component of Prolog systems; quite the contrary, the

author is not aware of any Prolog offering such a capability.

Page 7
The possibilities opened by this device, however, are startririg:

Prolog suddenly becomes a vehicle for addressing programming

problems for which it could not even be considered before. such

as system simulation, operating system design, graphics. and

other traditional complex problem areas.

Our interests, of course, lie in the area of databases, and

so we will turn to the application of escape to the purposes of

the present project. It was decided to take the straightforward

approach of Implementing an <action_code> corresponding to each

of the RIM applications interface routines. For example, to do a

RMFIND(lji relation; out cursor)

we simply invoke the predicate escape([1,•YEAR'],C) from Prolog,

where 1 is the action code: the cursor (an Integer) assigned to

relation YEAR is returned in a list bound to C: C » [6], for

example. We can then use this cursor to do RMGETs. i.e. to

retrieve tuples from YEAR one by one: if X was bound to the

cursor found by the RMGET, escape([2,X],Tuple) returns the

retrieved tuple as a list bound to Tuple. The RIM_MOD cases

corresponding to action codes such as 1 and 2 may be found in

the RIM_MOD section of the program documentation.

This capability, of course. leads straight to the use of

Prolog to implement the Intelligent database front end that is

the subject of this project. In particular. It opens the way for

the Integration of rules into database processing. Before

describing how this is done. we first present the complete set

of escape action codes that were implemented to form the RIM

Page 8
Interface. It should be noted that the Interface refers to the

RIM Version 5 Implementation available at Implementation time,

and thus lacks a number of additional features available In

RIM Version 6. Most of these are of little slgnifIcance: one

exception Is the RIM/6 applications language routine

RMBLD(relname, attname)

that allows the user to specify that the named attribute le a

key. This operation Is Important because the WHERE

qualification to the RIM SELECT depends on Indices for

efficiency. Addition of this capability to the Interface IB

straightforward.

The simplest way to present the Implemented primitives Is to

give annotated transcripts of actual Interactive sessions with

the YRIM system. In the course of which the newly Implemented

primitives are exercised.

Here Is the RIM database DB accessed by this program:

YEAR

NAME RANK

FRED

JILL

HENRY

JACK

STUDIES

NAME

FRED

JACK

JILL

JILL

HENRY

HENRY

1

2

3

2

CLASSNO

611

620

641

646

643

646

Page 9
CLASSES

CLASS TIME ROOM

611

611

6U6

622

6U3

M1OOO

W13OO

TU11OO

TH1OOO

TU1100

LG1

LG1

G2U

R418

R22U

Comments in the run will be denoted by Ada-like "—" marks.

Unless inappropriate or obvious from context, user input will be

denoted by indentation.

run yrim -- yrim is the Prolog/Pascal/RIM dbms program

Enter name of file containing Prolog program: prog.rim

— prog.rim Implements the stream capability

-- to be discussed subsequently. It will not be needed

— here, but yrim insists on reading some Prolog file

?- escape([101,db],X). -- uses RMOPEN to open data base db.

— recall that the first argument of escape must be a

-- list, the first element of which is interpreted on

— the rim_mod side as an action code. Code 101 denotes

— RMOPEN

** escape([1O1,db],[O]) ?; -- Prolog's response. The 0 in the

— second (output) parameter is the RMSTAT return code.

-- 0 denotes successful completion of RIM operation.

— The ";" is the user's request for additional

— answers, in response to Prolog's prompt of "?"

— (i.e. "search for additional answers?")

no -- no more answers found, the above was the only one.

— We will omit Prolog's responses henceforth

-- unless they are relevant to the discussion.

?- escape([97].X) — call READSCHEMA

-- This operation does not correspond to any RIM

— operation. Routine READSCHEMA reads the relational

— schemas describing the open database into Pascal

-- arrays for easier access. This is operation is necessary

— for the success of subsequent RMGET operations.

Page 10
?- escape([11O.1.studies],X) -- RMFIND(1,'STUDIES')

-- Result of subsequent RMSTAT is returned in X.

?- escape( [llO.2.year] .X) — RMFIND( 1. 'YEAR')

-- On the Prolog side, names of constants must be in

-- lower-case, while RIM demands that everything be

-- in capitals. The interface converts automatically.

?- escape([99].X). — show RN_RIX_TABLE

-- RIM-MOD (the Pascal interface) maintains an internal

table that associates cursor numbers with relation names.

SLOT ft: 0 <FREE>

SLOT ft'. 1 <FREE>

SLOT ft: 2 <FREE>

SLOT ft: 3 <FREE>

SLOT ft: U <FREE>

SLOT ft: 5 <FREE>

-- no associations yet

?- escape([98,2,year],X) -- associate cursor ft 2 with

— relation year in RN_RIX_TABLE

?- escape([98,1.studies],X) — associate cursor # 1 with

— relation studies in RN_RIX_TABLE

?- escape([99].X). — show RN_RIX_TABLE again

SLOT ft i O <FREE>

SLOT ff: 1 STUDIES

SLOT ft: 2 YEAR

SLOT #: 3 <FREE>

SLOT #: U <FREE>

SLOT ft'. 5 <FREE>

?- escape( [113. 1] . X) . -- RMGETdn cursor_no. out tuple)

** escape([113.1].[studies.fred.6ll]) ?

-- tuple <fred,6ll> has been retrieved from STUDIES.

-- READ_SCHEMA was needed, since the program must know

— about the relations in the database in order to

-- create a neat answer like [studies,fred,611]

— from the mess RMGET returns.

?- escape([113.2],X). — RMGET(2,X); cursor 2 is on YEAR

** escape([113.2].[year.fred.1]) ?

-- tuple <fred.l> has been retrieved from YEAR

?- escape([113.1].X). — RMGET(l.X); back to rel. STUDIES

Page 11
ORIGINAL PAGE IS

OF POOR

** escape([113.1].[studies,Jack.62O]) ?

-- tuple <dack,62O> has been retrieved from STUDIES

?- escape([113.2].X). — RMGET(2.X); back to rel. YEAR

** escape([113.1].[year.Jill,2]) ?

-- tuple <Jill.2> has been retrieved from YEAR

-- Time to try something different.

-- The retrieval of tuples from relations produces

-- tuple streams. RIM also allows the treatment of the

-- schemata In. a database, and the attributes within a

— relation, to be treated as streams.

?- escape([106],X). -- call to RMLREL. which sets a cursor

-- to the schema of the first relation in the database.

-- X returns value of RMSTAT after RMLREL call.

?- eBcape([107].X). — do a RMGREL

— RMGREL(out rname. rpw, mpw, numatt, numrows)

** escape( [107] , [schema, year, no_rpw, no_mpw, 8^/09/28, 2, 4l] ) ?

-- format of answer:

-- [schema, relation name, read password status,

— modify password status, date last modified.

— number of attributes, number of rows in relation]

— The word "schema" is included as flag indicating

that the end of the stream has not yet been reached.

End-of-stream is indicated by an "eoschema"flag

(see below)

?- escape([1O7],X). — another RMGREL

-- in order to advance to next schema

** escape([1O7],[schema, studies. no_rpw, no_jmpw, 8U/O9/28, 2, 6]) ?

?- escape([107].X). -- advance to next schema

** escape([1O7].[schema, classes, no_rpw, no_mpw, 8&/O9/28, 3, 5]) ?

'?- escape( [107] , X). -- advance again

** escape([107],[eoschema]) ? — end of schemata reached

escape([1O7],X). -- do another RMGREL to see what happens

** escape( [1O7]. [schema, studies, no_rpw. no_jnpw, 8ft/O9/28. 2. 6]) ?

— RMGREL cycles!

-- Now let us examine the intra-relation cursor created

— by RMLATT and advanced by RMGATT

Page 12
?- escape( [1O8, classes] . X) . -- RMGATT(in rname)

-- sets a cursor to schema of named relation

?-escape( [109] .X) . -- RMGATT

**escape( [1O9] t [att, class, int. . novlength, 1. O, 1, nokey] ) ?

— Format of answer:

— [att . attribute name, attribute type,

— matvec: blank unless this attribute is a matrix or vector

— var: variable length attribute flag

lenl. Ien2 : see RIM manual [RIM]

— column number, key flag]

?-escape( [1O9] .X) .

— another RMGATT to advance to next column

**escape( [ 109] t [att , time, text , , novlength , 8, O , 2, nokey] ) ?

— descriptor of attribute 2 of relation

?-escape(

— advance to next column

**escape( [ 1O9] , [att , room, text ,, novlength. 8, O, 3, nokey] ) ?

— descriptor of attribute 3 of relation

?-escape( [1O9] .X).

-- advance

**escape( [109] . [eoatt ]) ?

— end of attributes reached

?-escape( [1091 ,X) .

— try it again, see what happens

**escape( [109] . [eoatt ]) ?

-- in contrast to RMGREL. RMGATT does not cycle

The above examples illustrate the operation of the

implemented operations. A number of additional operations have

been implemented; although these are Just as important as the

above, interaction with them proceeds similarly, and we will

therefore confine ourselves to descriptions.

escape([1,<relname>].X) is similar to RMFIND (code 11O), but

Page 13
more "automatic": a cursor number IB picked and allocated to

relation <relname> by the system. and entered in the

RN_RIX_TABLE. X is bound to list [Qk_ix.Cursor.IERR]). where

IERR is the result of doing a RMSTAT upon completion.

escape([96.<cursor>].X) undoes code 98 by freeing the named

cursor, i.e. removing it from t.h_e RN_RIX_TABLE.

escape( [112. <cursor>, <attribujte_name>, <direction>, ].X)

performs a RMSORT on cursor no. <cursor>. Sorting is on the

attribute designated by <attribute_name>.

<direction> ::= asc ! desc

specifies whether the sort is ascending or descending. The

<at.tribute__name>., <direction> P«a.ir m&y

 be repeated, thus

specifying sorting on additional attributes. X returns [IERR].

Here is an example of the use of this code:

escape([112.2,rank.asc], X).

Assuming cursor 2 is assigned to relation YEAR, this operation

does a RMSORT on attribute rank of relation YEAR. specifying

ascending order.

The predicate

escape([111,<cursor>, <num_booleans>.

<attribute_name>. <operator>. <value> ].X).

Implements RMWHER. the most complex of the RIM application

language operations. Our implementation simplifies this

operation substantially, since.most of the effects of RMWHER can

be achieved at the Prolog level. and specified far more clearly

and elegantly there as well. The significance of RMWHER is that

Page 14
if an attribute has an Index defined on It, then RMWHER can take

advantage of this Index. This can make the difference between a

system confined to toy-sized problems and one that can handle

arbitrary relations. Since the RIM Implementation of RMWHER

restricts this operation to using at most one keyed attribute,

it was possible to simplify our implementation by taking

advantage of this fact.

As before. the second list element is the cursor number.

<num_booleans> Is the number of boolean expressions of the form

<attribute_name>, <operator>, <value> to follow. <operator> is

any of the boolean operators listed in the RIM manual: gt, It,

etc. <value> specifies a value which must be consistent with the

type of the attribute. Here is an example:

escape([111,2.1,rank,gt,2].X).

This operation modifies cursor 2, assumed to be associated with

relation YEAR. to produce a stream limited to students of

rank > 2. As before, X returns [IERR].

It was noted that performing a RMWHER after a RMSORT did not

work (produced an empty stream) at the RIM level, while a RMSORT

performed after a RMWHER did work correctly.

Update Operations

The RIM application language Interface provides three

operations for database update: RMLOAD. which adds a tuple at

the end of the designated relation, RMPUT. which modifies the

Page 15
tuple pointed to by the designated cursor. and RMDEL. which

deletes the tuple pointed to by the designated cursor. Clearly

a cursor that points to the required tuple must exist for the

latter two operations; this cursor is positioned by means of the

RMGET operation (code 113).

The predicate

escape([lift,<cursor>.<attribute_value>, ] . X)

implements RMLOAD. For example. If 2 is allocated to YEAR,

escape([lift.2,fred.1],X) will add tuple <fred,l> as new last

tuple of YEAR. X returns [IERR].

The predicate

esc ape ( [115. <cursor>, <attribu'te_value>. ] , X) implements

RMPUT. For example, if 2 is allocated to YEAR,

escape([115,2.fred.1],X)

will replace the tuple to which cursor 2 is currently pointing

by the tuple <fred,l>. X returns [IERR].

eseape([116,<cursor>],X) Implements RMDEL. The tuple pointed

to by the designated cursor is deleted from the relation.

Appropriately the last operation to be discussed is

escape([102].X), the RMCLOS operation. which closes the current

database. Unless this operation is performed. none of the

updates performed on the database become permanent.

Page 16
YRIM Programming

The escape predicates described in the previous section are

sufficient to effect all RIM applications language operations

from Prolog. It is clear, however, that these predicates are too

low-level to be useful for routine programming, whether by

a beginner or adept Prolog programmer.

Building on the Primitives

Fortunately Prolog makes the construction of higher-level

language elements on the basis of more elementary ones extremely

easy and natural. We will illustrate this assertion by showing

how the user might do some typical retrievals using the present

system, as well as define a view. Additional enhancements to

user friendliness include significant improvements in the

tracing capability of the Prolog Interpreter. as well as a

number of additional improvements of a minor nature.

The RIM manipulation facilities based on the escape predicate

form a useable but not user-friendly set of operations. To begin

a session using a database named TURBO, for example, the user

must type

escape([1O1. turbo], X)

Page 17
to open the database, followed by

escape([97], X)

to cause the schemata describing the relations of the database

to be read. A higher-level capability is easily created:

open(Dbname) :- escape([101, Dbname]. lerr).!.

checkstatus(lerr),

escape([97]tIerr2),

checkstatus(Ierr2), !.

This operation opens the database whose name Is bound to Dbname

and readies It by readlne In the schemata for use by subsequent

operations. The checkstatus predicate can abort processing If

the status code returned by the preceding escape operation

indicates unsuccessful completion:

checkstatus(~1) :-

write(' NO MORE DATA AVAILABLE FOR RETRIEVAL ').!.fail.

checkstatus(O). /* O indicates successful completion */

checkstatus(1O) :-

write(* DATABASE FILE DOES NOT CONTAIN A RIM DATABASE '),

!.fail.

checkstatus(111) :-

write(' MORE THAN 10 RULES PER RELATION ').!.fail.

The above definitions simply reproduce the error messages listed

in the RIM manual as corresponding to each RMSTAT code. If more

specific behavior is desired, it can easily be produced in an

analogous manner. For example. in a context in which an

end-of-data condition should be reported but not cause

subsequent operations to be aborted, a predicate such as

eod(-l) :- writeC END OF DATA ENCOUNTERED ').

can be defined and used.

The above examples show a typical instance of user-created

Page 18
high-level database manipulation operations based on the

provided escape primitives. It Is clear that similar

user-friendly operations can be defined for each of the provided

escape predicates..

We now turn our attention to a number of additional

higher-level constructs, which we believe are sufficiently

user-friendly to allow the casual Prolog programmer to use the

YRIM system. Including the demon mechanisms and coroutines. The

result Is an environment which. while Prolog-based. Is

reminiscent of a one-dimensional Query-by-Example system.

Streams

One of the basic Ideas of this project was that Logic

Programming treated its rulebase as a stream of rules and facts,

and that if a database could be made to supply similar streams,

then Its complete integration into logic programming could be

achieved. One of the main results of this project has been the

implementation of such a stream capability. Here is the

(annotated) Prolog program code that implements this capability.

rmfind(Relname,Cursor,lerr) :- escape([1.Relname],[_, Cursor.lerr]).

/* returns a cursor into relation Relname */

rmget(Cursor, Tuple) :- repeat. escape([2,Cursor],Tuple).

/* returns the next tuple from the relation with which

Cursor is associated, and prompts the user to see if

he wants additional tuples. This procedure is the Prolog

image of the RIM application language interface function

RMGET, and is essentially a "manually operated" stream */

Page 19
stream(Rel) :- Rel =.. List, List = [Re1name | Relargs],

rmfind(Relname, C,_) . rmget (C. Tuple) ,

(Tuple = [e_o_r ! _], !.fail : Tuple = List).

/* Manually operated streams are fine, but for actual programming

we need program-operated, streams. The stream procedure

returns the next tuple of Rel whenever the Prolog program

executes it */

Here is an example of how stream Is used to Interface Prolog

and RIM:

year(X.Y) :- stream(year(X.Y)).

Upon including this rule in the Prolog program, the user can

type queries such as

?- year(Student.2). /* who is a second-year student? */

and receive as response

** yearUack. 2) ? :

** year(dill,2) ? :

no /* no more found */

While rather Prolog-flavored in format, this interaction is

quite comprehensible; in other words, a suitably restricted set

of Prolog procedures can serve as DDL/DML for the layman. The

main point to be noted here, however, is that there Is no

indication at all in a query such as year(Student,2) that RIM is

being accessed. rather than Prolog's internal database. The

stream predicate thus achieves a seamless integration of Prolog

and RIM.

Views

Given stream. several powerful capabilities follow. One of

these is the ability to define views. Here is a simple example.

Page 20
Suppose that we have added the rule

Btudlee(X.Y) :- stream( studies (X. Y) ).

to make the studies relation available to the programmer, and

want to find the names of the second-year students who are

taking cs646. This corresponds to a Join:

JOIN year. Students = studies. Students

WHERE year. rank = 2 and studies. class = 646

In our Prolog DML the query looks like this:

?- year (Student , 2 ), studies(Student , 646).

Note the analogy with Query-by-Example: the user is essentially

giving the system an example of the kind of response he wants to

see. The system responds:

** yearUill,2). studies( Jill . 646 ) ? ;

** year (henry. 2) . studies (henry. 646) ? ;

no

This is clear enough. but somewhat cumbersome. and the user

decides he wants to define a view. I.e. a new relation that is

defined as the above join. This is done by adding the following

rule:

new_rel ( Student ) :- year (Student , 2) , studles(Student. 646) .

The query

?- new_rel(X).

then produces the response

** new_rel(Jill) ? ;

** new_rel (henry) ? ;

no

Here is a PROJECT view corresponding to

PROJECT CLASSES OVER TIME. ROOM GIVING REL2

rel2(Tlme. Room) :- stream( classes (_. Time, Room) ).

Page 21
The following query poses the question " set all freshmen who

are taking graduate courses"

?- year(Student,1),studies(Student.Course_no),Course_no > 500.

producing the response

** year(fred.1).studies(fred.611).611 > 500 ? ;

no /* no additional solutions were found */

It Is easy to see from these examples that YRIM provides a

powerful and expressive user Interface to RIM.

Demons

At this point we have not yet transcended the capabilities of

existing database systems (although RIM itself does not offer a

view definition facility!). We now show how the Interface we

have described can be used to integrate rules with data. The

underlying idea is as follows: the user should see the rules as

being stored in the database as part of the data, regardless of

how this effect is actually produced. We have shown. however,

that if the stream predicate Is used, then the user cannot

distinguish between data coming from RIM and data coming from

Prolog's own database. In other words. all data looks to the

user as if it were stored in the: Prolog database, and thus the

rules stored in the Prolog database appear to be in the same

database as the data actually stored in RIM. We have thus

produced a virtual database that has all the RIM operations

defined on It (via escape). but Intermingles data and rules as

Page 22
freely as does Prolog. Thus a major goal of this project. the

storage of rules in RIM. is achieved in an elegant and efficient

fashion.

Once the incorporation of rules into a database has been

achieved, numerous powerful capabilities become available. One

of these is the inclusion of demons In the database. i.e. of

pattern- and data-driven processing that is triggered by

database updates. The following Prolog code template shows one

method of implementing demons:

rget( Query) :- pre< Query). /* these are preprocessing demons */

rget( Query) :- stream( Query ) . /* the relation proper */

rget (Query) :- post (Query). /* post-processing demons */

pre(Query) :- write( ' Begin pre-rule application for ').

write(Query ) . nl, fall.

/* the fall prevents spurious answers on backtracking */

/* rules to be applied before RIM processing begins, */

/* If any. here. */

pre(Query) :- wrlte( ' End pre-rule application for '),

write(Query ) , nl, fail.

post (Query) :- write( ' Begin post-rule application for '),

write(Query ) . nl, fail.

/************* ********** ********* *********** ***********/

/* rules to be applied after RIM processing begins, */

/* if any. here. */

/* here is an example of such a rule: */

post ( studies (Student , cslOl) ) :- rget (year (Student , 1) ) .

/* typical demon: all freshmen take cslOl */

post (Query) :- write( ' End post-rule application for '),

wrl te( Query ), nl. fail.

Page 23
Physically this program segment follows the definition of

stream given above. As can be seen, this segment is a template.

since it provides slots, indicated by comments, wherein the user

may insert demons, or in fact any pre- and post-processing rules

he chooses.

The rget predicate is a generalization of the stream

predicate: stream is sandwiched between the pre and post

predicates. pre and post, in turn, invoke whatever demons the

programmer specifies.

The present template specifies as demons a set of

self-explanatory printouts telling the user that pre- (post-)

processing is beginning (ending). In addition we have included

an example of a non-trivial demon, in the form of the rule

post(studles(Student, cslOl) ) :- rget (year (Student , 1) ).

The effect is to add a post-processing demon to the studies

relation. The augmented relation is queried as follows:

rget ( studies (X, Y) ).

If a more elegant form is desired, the view definition

Btudies(X.Y) :- rget ( studies(X, Y) ) .

may be Included. The guery is then

studies(X, Y).

The rget (studies (X, Y) ) predicate first Invokes

pre( studies (X, Y) ), which merely prints out the corresponding

messages, rget then Invokes stream(8tudles(X. Y) ) , which presents

the tuples of the studies relation to the user in the usual

Page
manner. Upon reaching the end of this tuple stream, rget

invokes post(studies(X.Y)). which prints out the message

Begin post-rule application for studies(X.Y)

and then activates the rule

post(studies(Student,cslOl)) :- rget(year(Student.1)).

which causes rget to be Invoked recursively with

year(student.1)) as argument. This invocation of rget proceeds

as before; If any demons had been defined for the year relation,

they would be Invoked as well. There are none, and so the call

rget(year(Student,1))

is equivalent to the call

stream(year(Student,1)).

This Is a SELECT on year where year.rank = 1. The effect is to

deduce that fred Is taking cslOl because he is a first-year

student.

While the processing we have described may appear

complicated, it should be noted that the user need not concern

himself with these details, but needs only to insert the desired

demon-defining rules in the indicated template slots. This

demon-definition capability, of course, was one of the goals of

this project.

Page 25
Coroutines

A major obstacle to the extensive use of Prolog Is its lack

of familiar control structures such as if-then-else and while

loops (or even goto, for that matter). Backtracking is the only

control mechanism provided. and while the effects of the

above-mentioned control structures can be "faked" to a large

extent by means of backtracking, the resulting constructs can be

too obscure and unnatural to permit serious software

engineering. The ideal situation (in the opinion of the author)

would be to have the main (controlling) program written in some

other language such as Pascal, and to call on Prolog only when

the service it provides so well is required: deductive database

retrieval.

It is unfortunately the case that all major Prolog

implementations known to the author (including University of

York Prolog) operate as main programs, and could be made to play

the role of subroutine only after major overhauls. A number of

list-based Prologs exist that can operate as subroutines

(including the one implemented by the author using the Al

toolkit), but are in general either too toy-like, or too closely

tied to a particular LISP implementation. or both. Another

approach was required.

The solution that was ultimately adopted retained the

original program structure whereby York Prolog is the main

program. and communicates with Pascal by means of the escape

Page 26
predicate that causes Invocation of the RIM_J1OD Pascal

procedure. or more generally of ESC_MOD, the Pascal interpreter

of action codes without the RIM specialization. Conceptually,

however, Prolog and ESC_MOD are coroutines. Recall that the

difference between a main program/subroutine and a

coroutine/coroutine relationship is that when a subroutine is

called, control is always transferred to the beginning of the

subroutine's code, and relinquished at one of the subroutine's

return statements (we Ignore the unfortunate fact that Pascal

has no explicit return). while a call to a coroutine (called a

resume) transfers control to the coroutine statement after the

one last executed before the coroutine relinquished control to

the caller.

In order to achi.eve the same effect in the ESC_MOD

subroutine. it was necessary to maintain a variable resume_pt

that kept track of the statement where execution was to resume

when control was transferred by the caller. This required the

insertion of labels at the resumption points, and a case on

resume_pt that transferred control to the appropriate statement

within what in reality is a subroutine. The required program

transformation leads to a straightforward and stereotyped

structure that, despite Its aesthetic defects. is quite easy to

use. Here it is:

procedure coroutine;

label 999. 1OOO,1OO1,1OO2.1OO3; (* resume labels *)

begin

case resume_pt of

Page 27
O: goto 10OO; 1: goto 10O1; 2: goto 1002; 3: goto 10O3;

otherwise

begin

writeln(' *** From coroutine: bad resume point: ', resume_pt:1);

halt;

end;

end; (* case *)

1000:

(* here on first invocation *)

(* start of computation *)

writeln; writeln(* ##tt coprocessor action 1; handing off to Prolog'):

(* end of computation *)

(* Now set up args to be passed to Prolog *)

no_of_args := 1;

set_str_arg(1,'procodel',8);

(* return string "procodel", length 8, as first (and only) arg *)

(* End of arg setup section *)

resume_pt := 1;

goto 999; (* return . i.e. RESUME Prolog *)

1OO1:

(* start of computation *)

writeln; writeln(* ### coprocessor action 2; handing off to Prolog');

(* end of computation *)

(* Now set up args to be passed to Prolog *)

no_of_args : = 1;

set_str_arg(1, 'procode2'.8);

(* return string "procodel", length 8, as first (and only) arg *)

(* End of arg setup section *)

resume_pt := 2;

goto 999: (* return , i.e* RESUME Prolog *)

1OO2:

{* start of computation *)

writeln; writeln(' ### coprocessor action 3; handing off to Prolog');

(* end of computation *)

(* Now set up args to be passed to Prolog *)

no_of_args := 1;

set_str_arg(l. *procode3f.8) ;

(* return string "procodel", length 8, as first (and only) arg *)

(* End of arg setup section *)

resume_pt := 1;

goto 999; (* return . i.e. RESUME Prolog *)

1O03:;

999:: end; (* coroutine *)

Page 28
As It happens. this routine Is only one of the services

Invocable from Prolog by means of action codes; all other action

codes are still available as well. Programs that call each

other as coroutines. even If only conceptually, are equals, and

essentially treat each other as objects. This Implies that

ESC_MOD can call on 'the Prolog program for services Just as the

Prolog program can call on ESC_MOD. and thus the Prolog program

will in general have a special structure as well. Here Is an

example of a structure that can cooperate with the above

program:

cycle(_) :- To_outside = [Init],

repeat, communlcate(To_outslde. From_outside).

/* dummy vble is there since It won't prompt for more If

goal Is a ground clause */

communicate(To.From) :- escape([0,To],From), execute(From,To),!

/* 0 Is escape coroutine code.

From should have format [prolog_actlon_code ! arg_list]

To Is result list, possibly same format

execute([procodel],X) :-

write(' Prolog action 1; handing off to escape *),nl.

execute([procode2],X) :-

write(' Prolog action 2; handing off to escape *).nl.

execute([procodeS].X) :-

write(' Prolog action 3; handing off to escape ').nl.

The output of these cooperating programs is left as an

exercise for the Interested reader.

We have described the interface between Prolog and RIM, and

Its use in the construction of virtual databases that contain

Page 29
rules, demons, views, and in fact any arbitrary extensions and

capabilities the user cares to program. We now turn our

attention to the application of these concepts to the

achievement of a main goal of this project: construction of

RIM-based expert systems.

Page 30
TURBO

A RIM-based Expert System

A major goal of this project has been the creation and

demonstration of an expert system capability based on the RIM

database system. It was decided to use a Prolog-based expert

system which has fault diagnosis for a turbofan jet engine as

its domain of expertise [Abbott] as a test subject. We will

present excerpts of significant portions of her Prolog-based

system, as well as their implementation in our RIM-based system.

Both the original system and our YRIM version are driven by

data from a predicate named sensed, which records engine sensor

readings along with their values and the time (measured in unit

Increments) the reading arrived. The predicate in Abbott's

Implementation is

sensed(thrust.decreasing.1)

sensed(vibration.yes.1)

sensed(egt,fluctuating,1)

sensed(epr.fluctuating,2)

sensed(nl.fluctuating.2)

sensed(n2.fluctuating,2)

sensed(fuelflow,high.ft)

sensed(egt.decreasing.5)

sensed(epr.decreasing.5)

sensed(nl.decreasing,5)

sensed(n2,decreasing. 5)

sensed(fuelflow,decreasing,5)

sensed(thrust,decreasing.5)

Our YRIM implementation is driven by the corresponding RIM

Page 31
relation:

Relation SENSED:

SIGNAL VALUE TIME

THRUST

VIBRATION

EGT

EPR

Nl

N2

FUELFLOW

EOT

EPR

Nl

N2

FUELFLOW

THRUST

DECREASING

YES

FLUCTUATING

FLUCTUATING

FLUCTUATING

FLUCTUATING

HIGH

DECR

DECR

DECR

DECR

DECR

DECR

1

1

1

2

2

2

4

5

5

5

5

5

5

Similarly, the RIM relation

CANCAUSE

CAUSE

FOREIGN_OBJ ECT

ICING

COMPRESSOR_STALL

ICING

TURBULENCE

FOREIGN_OBJECT

FUELLEAK

BAD_FUEL_CONTROL

EFFECT

COMPRESSOR_STALL

COMPRESSOR_STALL

FLAMEOUT

FLAMEOUT

FLAMEOUT

FLAMEOUT

FLAMEOUT

FLAMEOUT

appears to the user as the Prolog relation

cancause(Cause,Effect), given a view definition for canoause:

cancause(Cause, compressor_sta-il)

:- Btream(cancause(Cause.compre8sor_stall)) .

Even this simple database allows some Interesting questions

to be answered, such as

SELECT CAUSE FROM CANCAUSE WHERE EFFECT EQ COMPRESSOR_STALL

which retrieves the causes of compressor stall: foreign objects

Page 32
and icing. The formulation of this query in YRIM le

cancauseCCauee, compressor_stall).

The SUPERSEDee relation contains information about what

faults subsume others. For example. the set of symptoms that

indicate a flameout are a subset of the symptoms that Indicate a

compressor stall. The RIM relation

SUPERSED

SUPER SUB

COMPRESSOR_STALL FLAMEOUT

COMPRESSOR_STALL BAD_FUEL_CONTROL

COMPRESSOR_STALL TURBINE_SEPARATION

becomes the (virtual) Prolog; predicate supersedes (Super. Sub),

defined by the rule

supersedes(Super. Sub) :- stream(supersed(Super, Sub)).

supersedes thus appears to the user as if it were defined by

Abbott's Prolog predicates

supersedes(compressor_stall.flameout)

supersedes(compressor_stall,bad_fuel_control)

supersedes(compressor_stall.turbine_separation)

Note that the name of the RIM relation differs from the virtual

predicate defined on the Prolog side. since RIM confines

relation names to eight characters. For the same reason, a

number of the table entries have been 'de-abbreviated' for

readability.

Page 33
The Turbo Program

?

We will now dlecuBS the TURBO expert system In detail. The

program consists of three logical sections; we have marked these

divisions in the program. We first present the program as a

whole, and then discuss each logical section in turn.

/*******#*****#**********# #** #*******# ##** *****/

/* BEGIN PROGRA('• nM' • */

/******#**#*##*#*#*#**#**#*************#***************/

rmflnd(Relname.Cursor,lerr) :- escape([l,Re1name],[_. Cursor,lerr]).

rmget(Cursor, Tuple) :- repeat, escape([2,Cursor],Tuple).

stream(Rel) :- Rel =.. List, List = [Relname ! Relarge],

rmfind(Relname,C,_), rmget(C,Tuple).

(Tuple = [e_o_r ! _], !,fall ; Tuple = List).

dbstart(Dbname,lerr) :- escape([101,Dbname],lerr).

readschema(lerr) :- escape([97],lerr). /* -1 means: no more data */

turbo :- dbstart(turbo,lerr),!,lerr = [0],!,readschema(Jerr).!.

Jerr = ["!],!, nl,write(' OK, turbo has been read'),nl.

rmlrel(I) :- escape([1O6]. I).

rmgrel(X) :- escape([1O7] . X).

echemata(X) :- rmlrel(l),repeat. rmgrel(X) .

?-turbo. /* start up turbo db. The "?-" formulation causes

turbo to be activated when the program is loaded */

/******************************]************************/

/* END SECTION 1 */

/ft*****************************************************/

Page 3a
/************4^****************************************/

/* BEGIN SECTION 2 */

/ft*****************************************************/

mostrecent (Signal , Value, Timesensed. Currtlme ) : -

not ( var( Cur r time) ) ,

rmflnd (sensed, Cursor, lerr), /* allocate a cursor */

esc ape ( [111 . Cursor, 1 . time, le, Cur r time] , X) ,

/* where attr. tine <= Currtlroe */

escapeC [112, Cursor, time, desc] , X) , /* sort down */

rmget (Cursor. Tuple) ,

(Tuple = [e_o_r ! _],!. escape( [96, Cursor] ,_), fail ;

Tuple = [sensed, Signal , Value, Timesensed] , ! , escape ( [96. Cursor] , _)

).

/* Timesensed is an output parameter. Currtime is input */

holds (Signal , Value, Currtlme)

:- mostrecent (Signal. Value. Timesensed. Currtime).!.

holds (Signal . X, Currtime) :- var(X), X = normal.

/* It is meaningless to call holds (S, normal , T) , since "normal"

never appears as value in SENSED */

/* END SECTION 2 */

/* BEGIN SECTION 3 */

supersedes (X, Y) :- stream(supersed(X. Y) ) .

/* supersed is RIM's name for this relation, so we are confined

to eight characters. Prolog does not require us to be so

terse. */

cancause (X. Y) :- stream( cancause(X, Y) ) .

/* The morelikely predicate expresses the fact that a

fault is more likely if some conditions or faults that

can cause it are present at a prior time. */

morelikely (Fault, X. Time) :-

poss( Fault, Time). cancause(X. Fault ). poss(X. Time).

morelikely (Fault . X, Time) :-

poss(Fault, Time) , supersedes (Fault , X) . poss(X, Time).

/* poss(Fault, T) being true means that Fault is a possibility

at time T */

Page 35
poss(for_obj. T) :-

holds(vibrat.yes.T), holds(e«t,fluct.T), holds(epr.fluct.T).

holds(nl.fluct,T).holds(n2.fluct.T).

((holdB(fuelflow.X.T).X = normal);holds(fuelflow.fluct.T)).

/* The fault names appear in abbreviated form here. e.g.

"for_obd" instead of "forei«n_obdect". The abbreviated form

is what is actually used both in the program and the RIM

database, since this simplifies the Interface with RIM */

poss(cprstall,T) :-

holds(vibrat,yes.T).

holds(egt,X.T), X \= normal,

(holds (epr. fluct, T) ; holds (epr, deer,; T)),

(holds(nl.fluct.T) ; holds(nl.deer.T)).

holds(n2.fluet.T).

((holde(fuelflow.Y,T),Y = normal) : holds(fuelflow,fluct,T)).

((holds(thrust,Z,T),Z « normal) ; holds(thrust.deer,T)).

poss(turb_separation,T) :- /* turbine blade separation */

holds(vibrat,yes,T),

holds(epr,deer.T).

holds(thrust,deer,T).

pose(icine,T) :-

holds(oat,X.T). X \= normal. X =< 8,

holds(moisture.visible,T).

(holds(vibrat,yes.T) ; holds(epr.fixed.T)).

poss(flameout, T) :-

holds(egt.deer,T), holds(epr,deer.T),

holds(nl.deer.T).holds(n2,deer,T),

holds(fuelflow,deer,T),holds(thrust.deer.T).

poss(fuelleak.T) :- holds(fuelflow,high,T).

poss(fuelleak.T) :-

holds(nl,low,T),

holds(fuelflow,low,T).

/***********# #** ***#********####*******************/

/* END PROGRAM */

Page 36
Discussion of the Program

Section 1 of the program consists of low-level functions that

handle the RIM interface. The following rules form the familiar

but crucial definition of the stream predicate. which has been

discussed In a previous section.

rmflnd(Relname,Cursor,lerr) :- escape([1,Relname].[_, Cursor,lerr]),

rmget(Cursor. Tuple) :- repeat, escape([2.Cursor],Tuple).

stream(Rel) :- Rel = .. List, List = [Relname ! Relargs],

rmflnd(Relname.C._), rmeet(C.Tuple).

(Tuple = [e_o_r ! _]. !.fail ; Tuple « List).

The following rules illustrate how easily a friendlier interface

can be constructed from the primitives. dbstart. for example,

opens the named database and returns the status code in lerr.

readsehema, as its name indicates. reads a (the next) schema

from the currently open database.

dbstart(Dbname,lerr) :- escape([101,Dbname],lerr).

readschema(Ierr) :- escape([97].lerr). /* -1 means: no more data */

Proceeding to the next higher definitional level. we 'use the

previously defined predicates to construct the third-level

Interface predicate turbo, which opens and initiates the

database named TURBO:

turbo :- dbstart(turbo,lerr),!,lerr = [O],!.readschema(Jerr),!,

Jerr = ["!],!, nl.write(' OK, turbo has been read').nl.

?-turbo. /* start up turbo db. The "?-•' formulation causes

turbo to be activated when the program is loaded */

This ends the first part of the program. The second section

defines the crucial mostrecent predicate, which is used in

defining the holds predicate, the basic vehicle for defining the

Page 37
faults themselves.

The holds and roostrecent Predicates

We now turn to Section 2 of the TURBO program. which defines

the crucial predicate mostrecent. which in turn defines hold.

The definition of holds is a view;

holds(Signal, Value. Currtime)

:- mostrecent(Signal, Value.Tlmesensed, Currtime).!.

holds (Signal. X, Currtime) :- var(X). X <= normal.

/* It is meaningless to call holds(S,normal,T). since "normal"

never appears as value in SENSED */

Intuitively. holds(S.V.T) is true iff signal S has value V at

time T. It Is possible. however, that there Is no tuple in the

SENSED relation for <S,V.T>. Suppose, for example, that T = 48,

S = "egt". and V = "fluctuating", but that the only tuple in

SENSED for which SENSED.Signal = "egt" and

SENSED.Value = "fluctuating" is <egt,fluctuating,3>. Since egt

was sensed -to be fluctuating at time 3. and no subsequent sensor

reading refers to any different sensing of egt. It must be

assumed that the egt is still fluctuating at time US. As we

will see. the mostrecent predicate insures that holds behaves in

the required manner.

If no sensor reading at all exists for a particular signal,

it is assumed to be normal; the second part of the definition of

holds corresponds to this requirement.

Page 38
moetrecent

The predicates discussed heretofore are similar to their

counterparts in Abbott's Prolog implementation; it is the

mostrecent predicate that forms the Interface with RIM, and thus

differs completely from its Prolog version. mostrecent

retrieves the most recently (relative to a given time. usually

the present) sensed value for a signal, and the time at which it

was sensed.

•

Prolog's deficient control structures force the Prolog

programmer into a series of clumsy and inefficient constructs in

order to Implement the following loop:

for row := last row added downto first row added do

if sensed[row] contains the sought attribute values

then return row;

The RIM implementation proceeds differently:

mostrecent(Signal.Value.Timesensed,Currtime) :-

/*!*/ not(var(Currtime)), /* Current time must be an input vble */

/*2*/ rmflnd(sensed,Cursor,lerr). /* allocate a cursor */

/*3*/ escape([111,Cursor,1,time.le,Currtime],X),

/* where attr. time <= Currtime */

/*tt*/ escape([112,Cursor,time.desc],X).

/*5*/ rmget(Cursor,Tuple),

/*6*/ (Tuple = [e_o_r ! _],!,escape([96,Cursor],_),fail;

/*?*/ Tuple = [sensed,Signal,Value,Timesensed],!.

/*8*/ escape([96.Cursor],_)

).

Since this sort of Interaction between a database and an expert

system appears to be unique, we will discuss this definition in

detail.

Line 1: variable Currtime represents the time at which the

diagnosis is made. It is usually. though not necessarily, the

current time. It is thus an input variable which must be

Page 39
Instantiated when mostrecent Is invoked; since the var predicate

is true iff its argument is not instantiated. line 1 has the

desired effect.

Line 2: The rmfind predicate has been discussed in a previous

section; we recapitulate it here:

rmfind(Relname.Cursor.lerr)

:- escape([1,Relname].[_,Cursor,lerr]).

As can be seen. rmfind invokes escape with code 1, which

performs a RIM RMFIND operation on the named relation. and

returns the resulting cursor (."pointer", in RIM terms) in output

variable Cursor. lerr returns the resulting error code. The

effect of line 2 is thus to allocate a cursor to relation

SENSED, and to return this cursor as the value of variable

Cursor.

Lines 3 and ft: these two lines perform the essential part of

the required retrieval. Line 3 modifies the cursor allocated by

line 2 according to the following WHERE clause:

WHERE SENSED.TIME LE CURRTIME

so that all tuples corresponding to values sensed after Currtime

become invisible to this cursor.

Line ft corresponds to the RIM clause

SORTED BY SENSED.TIME = DESCENDING

which has the effect that the first tuple retrieved by this

cursor has the largest value in its TIME attribute. I.e. is the

most recent value sensed.

Line 5 performs the actual retrieval by effecting a RMQET

using Cursor as modified by the above WHERE and SORTED clauses;

Page ftO
line 6 IB the "failure" branch taken In case no tuple was

retrieved (In which case the signal value IB presumably normal),

while line 7 converts the retrieved tuple to the appropriate

format. given a successful retrieval. These lines are

unnecessarily obscure and "Prology" due to Prolog's lack of

simple amenities such as an if-then-else.

Finally, line 8 deallocates Cursor. a necessary operation in

view of the fact that each Invocation of holds requires its own

cursor.

It is worth reemphasizing that while the occurrence of actual

escape clauses in Prolog/RIM programs is certainly permissible,

it is never necessary. If such clauses are deemed to make the

program too obscure and unreadable. they can always be replaced

by more user-friendly constructs. For example, the clause

escape([96,Cursor],_)

could be replaced by, say. free(Cursor), and the following

definition be added:

free(Cursor) :- escape([96,Cursor]._).

We have not done this in our example. partly because of time

constraints. and partly because such specialized usages of

escape clauses did not appear to merit inventing "friendly"

forms that would never be used elsewhere.

Page
Fault Diagnosis Predicates

The third section of the program contains the definitions of

the fault diagnosis predicates themselves. As we have seen.

supersedes and cancause are simply defined in terms of the

corresponding RIM relations; the user is unaware whether

supersedes and cancause access Prolog's Internal database or

RIM.

The morellkely predicate uses supersedes and cancause to

express the fact that a fault is more likely if some conditions

or faults that can cause it are present at a prior time.

The central predicate of the TURBO system, both in Prolog and

in our RIM-based system. Is the poss ("possible") predicate.

poss relates diagnoses to symptoms which may have occured at the

present time or earlier. It is this time-oriented approach,

unusual in expert systems, which accounts for the complexity of

the mostrecent predicate. The reader is Invited to inspect this

predicate closely, since it Is a perfect example of Prolog at

Its best: these rules are readable and concise, but specify a

large amount of information, and even more computation.

The usual question posed to TURBO has the form

poss(X,2). /* what diagnoses are possible, given the symptoms

present at time T = 2? */

poss(D.T) is true iff diagnosis D is a possible fault

diagnosis at time T. The time parameter generally represents

the current time. though any arbitrary value may be used as

well. The possible diagnoses are returned as Instantiations of

Page 42

A
the query variable X:

poss( forelgn_ob;Ject, 2) ? ;

P08s(compre88or_8tall. 2) ? ;

no /* no more diagnoses */

Here IB a eample run of TURBO. User inputs follow the ?-

prompts; also, the ";" following system-generated solutions are

user requests for additional solutions.

OK. turbo has been read

?- poss(X.l).

no

/* symptoms at time 1 do not yet confirm any diagnosis */

?- poes(X,2). /* what diagnoses are possible at time = 2? */

** poss(forelgn_ob;)ect, 2) ? ;

** poss(compresBor_8tall, 2) ? :

no

/* f oreign_ob;}ect and compreseor_8tall are the (only)

possible faults at time = 2 */

?- poss(X,3). /* what about time = 3? */

** poss(foreign_ob;Ject, 3) ? ;

** poss(compres8or_8tall, 3) ? ;

no

/* no new symptoms at time 3, so no change */

?- posB(X.U).

** po8s(fuel_leak.d) ? ;

no

/* New symptom at time U: FUELFLOW HIGH. This precludes the

previous diagnoses of foreign_ob;|ect and compressor_stall,

both of which require normal fuel flow. This is a typical

example of the important role played by time in this

system: earlier data is made obsolete by subsequent data.*/

?- poss(X.5).

** poss(turb_separation, 5) ? J

** poss(flameout, 5) ? :

** poss(fuel_leak, 5) ? ;

no

/* Lots of new symptoms at time 5. This plane has real

problems. */

?- poss(X,6).

** poss(turb_separation. 6) ? ;

** poss(flameout. 6) ? ;

Page 63
** posB(fuel_leak. 6) ? :

no~ . : .

/* No new symptoms after 5. */

i . .

?- mprelikely(X,Y,5).

Iff, mprellkely(flameput, fuel_leftk, 5) ? ;

no

/* The likelihood that we have a flameout at time 5 is

Increased by the fact that w§ §!BO had a fuel leak at.

or before time 5 */

?- end.

Page
TURBO: Summary

We have used the YRIM system to construct TURBO. an expert

system for Jet engine diagnosis. The result has been a program

that Is extremely concise. but at the same time surprisingly

powerful: the time dimension Is handled appropriately, and the

tendency of faults to cause, or at least Increase the

likelihood, of other faults Is represented. Most Importantly,

the actual fault data Is stored In RIM, a fact which Is

transparent to the user. It Is Interesting to note that the RIM

retrievals Involved In constructing the mostrecent predicate are

Intuitively simpler than the corresponding Prolog program

accessing a Prolog database.

The effectiveness of our system for the construction of

powerful RIM-based expert systems thus appears to be proven.

Page ft5
STRUTEX

The previous section discussed the creation of the RIM-based

expert system TURBO. It was noted that Prolog/RIM appeared

eminently suited to this application. Since then we have been

supplied by the project monitor with a second expert system

application. which has yielded a number of Interestlne Insights

and results. This section Is largely focussed on the problems

posed by this application.

The application In question, which has been named STRUTEX, Is

an expert system application Intended to assist the user with

structural design. Time limitations. as well as the fluid and

rapidly developing nature of the STRUTEX system specifications,

precluded production of an Implementation. We present here a

design which, although based on a preliminary formulation of the

problem, appears to be appropriate for such a system.

STRUTEX is of interest for two reasons. First, its structure

Is typical, and thus solutions developed for STRUTEX may be

expected to carry over to larger systems. This consideration is

particularly significant in light of the fact that the design

which was developed for STRUTEX is based on close interaction

between RIM and the controlling language (presently Prolog), and

that the expert system rules are stored in RIM Itself. Second,

it was noted that YRIM was considerably less well-suited to the

Page 46
STRUTEX application than to the Implementation of TURBO. Several

reasons for this situation exist, chief among which Is the fact

that YRIM uses Prolog as Its main program. while STRUTEX

requires the expert system to play the role of subroutine.

Prolog, however. Is Ill-suited to such a subordinate role. and

alternate approaches had to be developed.

Here are the rules that comprise the preliminary version of

STRUTEX available at the time this problem was first addressed:

1. IF SL = 1 AND TL = 1 THEN SOLUTION « 1

2. IF SL = 1 AND SA = 1 AND TL IN {2.3.1.5} AND WC « 2

THEN SOLUTION = 2

3- IF SL = 1 AND SA = 2 AND TL IN {2.3.1.5} AND WC = 1

THEN SOLUTION = 2

A. IF SL = 2 AND SA = 1 THEN SOLUTION = &

5. IF SL = 2 AND SA = 2 AND WC = 2 THEN SOLUTION = ft

6. IF SL = 2 AND SA = 2 AND WC = 1 THEN SOLUTION = 5

7. IF SL » 3 AND SA = 1 THEN SOLUTION = 6

8. IF SL = 3 AND SA = 2 AND WC = 2 THEN SOLUTION = 6

9. IF SL = 3 AND SA = 2 AND WC = 1 THEN SOLUTION = 7

We have used the following abbreviations In these rules:

SL: structural load. Values of 1. 2. and 3 represent the

cases where the support Is respectively above, beside,

or below the load.

SA: support area (as fraction of distance between load point

and support. SA = 1 (2) denotes that this ratio Is less

(greater) than O.05-

Page tt7
TL: type of load. Values of 1, 2, 3, 4. 5 represent gravity

load, alternating load, side load, or combinations of

1, 3 and 2, 3 respectively.

WC: structure weight. WC = 1 denotes that the structure must

be as light as possible; WC - 2 indicates that weight Is

not Important.

Abbreviations such as "SL = 3" would, of course. be translated

Into a human-oriented (possibly graphic) form before

presentation to'the user.

The above rules are easily represented as a syntax program.

[Feyock]. Rule 1, for example, becomes

1. <eolution=l> ::* <sl=l> <tl=l>

while rule 2 translates to

2. <solution=2> ::= <sl=l> <sa=l> <tl=23ft5>

<tl=23*5> ::= <tl=2> ! <tl=3> ! <tl=ft> J <tl=5>

The resulting syntax program could then be fed to an appropriate

parser generator, which would automatically produce the

corresponding expert system. For the present application, this

course of action was deemed to constitute overkill, as well as

making the interface of the expert system with RIM unduly

complicated. It was therefore decided to perform the

grammar-to-expert system conversion by hand, and, in particular,

to represent the grammar in transition diagram form before

conversion. Transition diagrams have a number of desirable

properties that make them appropriate Interfaces to databases.

Moreover, transition diagrams are closely related to BNF

specifications; in fact. any grammar all of whose productions

have the form

Page 68
<non_termlnal> ::« <non_terminal> terminal

or

<non_tcrmlnal> ::= terminal

specifies a transition diagram; conversely. any transition

diagram can be specified In terms of such a grammar. Moreover,

given an arbitrary BNF grammar (such as the above syntax

program), a transition diagram grammar specifying the same

system is easily found. Details of this representational

equivalence may be found In a number of sources, such as

lories).

The representational conversions Just described were

performed on the STRUTEX rule set. Here is the resulting

transition diagram:

Pace 4 9
-"©•-SL=1— >( 2 V--TL=l--> f 3 SOLUTION = 1

-->T ft--TL=2. 3. ft. 5--

SOLUTION = 2

— SA = 2 — I/7V-TL=2. 3. ft. 5 — ^HM — WC=1 —

SOLUTION - 3

—;SL=2-->[1O -SA SOLUTION = ft

—SA=2--(12)—WG=2—+

*—WC = 1— > ((1

—SL=3—>|lft ) SA = 1 — ---

SOLUTION = 5

SOLUTION

—SA=2—(16]--WC=2—*

+ —WC=1—> ((17)) SOLUTION = 7

The most significant feature of the transition diagram (td)

representation for expert systems is the fact that most of the

information specifying a td can be stored in a relational

database in a straightforward manner. The behavior of such a

system can be arbitrarily complex; for purposes of illustration,

however, the preliminary version of the STRUTEX system we have

been discussing will serve well. Consider what the system's

Page 50
behavior must be when in an arbitrary (non-final) state such as

state 2. First, the user must be prompted for an appropriate

response. In the context of the STRUTEX application such a

prompt Is most appropriately presented In menu form:

WHICH ONE OF THE FOLLOWING IS TRUE:

1. TL = 1

2. SA = 1

3 SA = 2

TYPE THE NUMBER OF YOUR CHOICE

It is understood throughout this discussion. of course, that

locutions such as "TL = 1" are used solely as abbreviations for

what would be human-oriented utterances such as

1. TYPE OF LOAD IS GRAVITY LOAD ONLY

The user types his response (we ignore details such as

processing erroneous responses here), and the system transits to

the appropriate next state. Upon entering any state, the system

must check whether the new state is a final state; if so, the

message appropriate to that state (which would presumably be the

final diagnosis) is printed and td processing terminated.

From the above description we can determine the information

that must be stored in the relations describing the td. Here is

a possible database design:

Page 51
TD

1 "

1

1

f

1

1

f

1

1

1

1

1

1

1

1

FKOM_STATE

2

2

2

a

10

10

i

i

i

i

t

i

i

i

i

i

t

I

I

MENU_CHOICE !

1 !

2 1

3 :

1 !

i :

2 !

etc.

TO_STATE

3

ll

7

5

11

12

1

1

1

1

1

1

1

f

1

1

I

1

1

1

I

1

The TD relation represents the arrows present In the td. The

menu messages associated with each state must also be

represented:

MENUS STATE

2

2

2

!

i

i

i

MENU_CHOICE

1

2

3

! MESS/

! TL =

! SA =

! SA -

tGE

1

1

2

As Indicated above, the menu messages stored In the MESSAGE

column are not literally "TL = 1", but rather are user-oriented

text strings of arbitrary length. This fact raises an

Interesting problem which at first glance appears to be merely a

matter of fixing up the Prolog/RIM Interface. but Is actually

representative of a more fundamental principle which had not

been properly recognized heretofore. The problem arises as

follows: the MESSAGE attribute Is appropriately of type

Page 52
TEXT(VARYING).. allowing arbitrary-length character strings to be

stored. The Prolog/RIM interface, however, makes provision only

for type TEXT(8). The first impulse upon noting this difficulty

is to modify the Prolog/RIM interface to accept text strings of

arbitrary lengths. It soon becomes apparent, however, that this

modification deals with only the tip of the iceberg: closer

examination discloses a host of RIM types for which similar

modifications must be made. This task is tedious and produces

code that is not only .unaesthetic. but also quite RIM-specific.

It was the goal of this project from the beginning, however, to

develop concepts that would work well with RIM, but would have

general applicability as well.

The above considerations led to a reappraisal of the YRIM

Interface design. It became apparent that the role of Prolog in

this design was to provide control structures that allowed AI

programming to be done on the basis of RIM. To permit such

programming it is necessary for certain information to pass back

and forth between RIM and Prolog (or whatever other language

Implements the superstructure). It is not necessary, however,

*

that all .information present in either system be transmittable

to the partner; all that is needed is that the control

information that directs the other partner what to do with the

information in question be transmittable. To take a concrete

example, it is not necessary to transmit text strings of

arbitrary length from the MESSAGE relation in RIM to Prolog for

subsequent presentation to the user. All that is required is

Page 53
that Prolog be able to transmit to RIM the control Information

that directs RIM to present the text strings in question to the

user.

This concept of passing control information rather than data

back and forth between the superstructure language and the

database system is expected to greatly Increase the power and

flexibility of our system. and is an appropriate topic for

future research. For the present we return to the presentation

of the STRUTEX td.

It is our intent to begin with the simplest possible

Implementation of the STRUTEX td, and to defer the addition of

bells and whistles. It was also considered desirable to

investigate questions regarding which side of the Prolog/RIM

interface should store which information. It was decided that

for the initial implementation the TD relation should reside in

RIM. while the Information displayed as stored in the MENUS

relation was to be stored and manipulated as part of the Prolog

database. As it happened, our design makes these considerations

transparent not only to the user but also to the Prolog

programmer: the information is sought in the Prolog database

first; RIM is accessed only if this seek is unsuccessful. Here

is a draft version of our td-based expert system "runner":

Page 5ft
dotransition :-

retrieve(currcntstate(/* out */ Currstate)).

/* retrieve performs a database access as described */

/* relation currentstate Is currently maintained

on the Prolog side */

do_action(/* In */ Currstate. /* out */ Response),

retrieve(td(/* In */ Currstate. Response,

/* out */ Nextstate)).

/* this currently accesses RIM relation TD */

update(currentstate(/* in */ Currstate), /* to */

currentstate(/* In */ Nextstate)).

/* update updates the referenced relation */

/* conceptually currentstate Is a one-row, one-column

relation that always contains the current td state */

currentstate(/* state */ 1).

/* State 1 is the start state */

do_aetion(/* In */ State, /* out */ Response)

:- menu(State), read(Response).

menu(/* state */ 1) :'-

wrlte(' Welcome to STRUTEX '). nl, /* new line */

write(' Here are your options: '), nl.

write(' 1. SL = 1 •), nl,

write(• 2. SL = 2 •), nl,

write(' 3. SL = 3 '), nl.

write(' Type the number of your choice: ')•

/* Could ultimately actually draw a graphic of the

referenced structural layout */

/* Here is the database access procedure: */ .

retrieve(Query) :- Query, !. /* look in Prolog db first */

retrieve(Query) :- stream(Query). /* then look in RIM */

/* The stream procedure has been described in an earlier

section. That's really all there is to it! */

The short procedure that Implements the loop

repeat dotransltloh until Currstate in flnalstates

has been omitted, since Prolog's lack of such control structures

forces the use of inelegant expedients to produce the looping

Page 55
effect.

Although the expert system implemented by the above td IB

only a small prototype. the simplicity and elegance of the

database access procedure retrieve is striking, and provides

evidence of the soundness of the original Interface design.

YRIM Programming: Summary

Several Important points have been Illustrated by the above

programs:

1. YRIM completely Integrates RIM and Prolog. Our system

not only communicates with RIM efficiently. but allows RIM

operations to appear In a form Identical to Prolog operations.

It Is thus not only possible but easy to define operations that

make It Impossible for the user to tell whether he Is accessing

data stored In Prolog's Internal database, or In RIM.

2. The resulting programs are powerful. The use of a

Prolog-based system allows Queries to be posed that transcend

those answerable by rule-based systems based on less powerful

languages.

3. The programs written using this system are extremely

concise. This point has been in evidence programs described in

previous sections, particularly TURBO and the dotransition

program described above. In view of the power of these short

programs it is clear that this brevity is a result of the

expressive power of the underlying system rather than the role

Page 56
of these programs as demonstration vehicles: programs using this

system will always be significantly more concise than programs

expressed by other means.

Page 57
CONCLUSION AND FUTURE RESEARCH

It ±B time to step back from the welter of technical detail

that has been described In order to obtain an overview of what

has been accomplished. As has been Indicated. a seamless

Integration of RIM and Prolog has been achieved, making the fact

that he Is accessing an external database completely transparent

to the user. Since the RIM database IB therefore

Indistinguishable from the Prolog database, a virtual database

Is produced In which tuples stored In RIM and rules stored In

Prolog are freely Intermingled. This virtual database thus

places all the power of Prolog at the RIM programmer's disposal

(and conversely. gives all the power of RIM to the Prolog

programmer). An Immediate consequence of this result Is that

since It Is possible to write rule-based systems In Prolog, It

Is possible to write them In the Prolog/RIM system YRIM; since

It Is possible to create "demons" in Prolog. it IB possible to

create them in YRIM, and since view definition, backtracking

search of a problem space, and in fact the whole arsenal of AI

techniques, are available in Prolog, they are available in YRIM

as well. Furthermore, it is evident that our approach could

have produced a similar Integration of RIM and LISP or RIM and

LProlog: In this case. RIM relations would have been available

to the programmer as lists rather than predicates.

Page 58
In view of the success and general applicability of thie

approach, what remains to be done? We have alluded above to the

problems encountered when considering the application of YRIM to

STRUTEX. Let us examine these issues in more detail, referring

to the latest incarnation of STRUTEX available to us as an

example. The main program can certainly be translated into YRIM

with no difficulty:

strutex :- grfxec(O), dbexec(O),

load, surface, support,

grfxec(9)t dbxec(9).

grfxec and dbxec would be defined in terms of escape

predicates, e.g.:

grfxec(N) :- escape([N],lerr).

New cases to handle the new action codes engendered by grfxec

and dbxec would have to be added to RIM_MOD. Such an extension

is straightforward, but represents only the tip of the iceberg.

Consider routines LOAD, SURFACE, and SUPPORT. While these

routines do contain interactions that have a classical expert

systems flavor, major portions are devoted to double-precision

computation, storage of temporaries and results in COMMON. and

manipulation of the RIM database. Manipulation of RIM from

Prolog is straightforward, of course: the escape predicates

described in this report do exactly that. But these predicates

are generally concerned with passing control information to RIM

that prompts RIM to transmit data to Prolog, which is then

manipulated by Prolog, and may be passed back to RIM as updates.

This is where the problem arises: the manipulations must be

Page 59
operations which the c&llinc language (Prolog in YRIM) can

perform easily. Prolog was able to perform the operations

involved in TURBO, which were almost entirely manipulations of

symbolic data. STRUTEX requires extensive operations on

numbers. and double-precision floating point numbers at that.

This, to put it mildly, is not Prolog's forte: many Prolog

implementations (including York Prolog) do not feature

floating-point numbers at all.

We have previously mentioned a solution to this problem:

escape codes can be created to perform such operations; calls

such as

escape([floatadd.'2.337'.'-88.6'].X)

can then perform the required manipulations. But this expedient

is extremely cumbersome. Note that the "numeric" arguments in

this call are actually strings; string/number and number/string

conversions must therefore take place on both sides of the

interface.

-The reader will have spotted a more serious difficulty,

however: uncontrolled proliferation of escape codes. If many of

the operations that Pascal and FORTRAN do easily are to be

performed on data that has been passed to Prolog, then an

ever-growing set of escape codes will be required to pass this

data back to the other side of the interface with appropriate

instructions for action to be taken. The results of these

actions will then need to be converted into a form Prolog can

accept and passed back to Prolog, which presumably will soon

Page 60
pass them back yet again for more manipulation.

All this buck-passing has the flavor of a badly organized

bureaucracy. The problem arises from the fact that an AI

language Is being required to perform non-symbolic operations

for which It Is not designed. The appropriate organization for

STRUTEX is the opposite of the present system's: rather than an

AI language calling on a Pascal/FORTRAN/RIM system for

non-symbolic conputations whose arguments and results it is

ill-equipped to handle, a Pascal or FORTRAN program should be in

control, and should call the AI system as subroutine whenever

symbolic computations are required.

It should be noted that this requirement for reorganization

is a result not of design defects in YRIM, but rather of the

balance between symbolic and non-symbolic computation that

prevails in a given application. The organization of YRIM is

perfect for a largely symbolic expert system application such as

TURBO, but inappropriate for a computation-intensive program

such as STRUTEX. We have advocated for some time the concept of

expert rules being callable as subroutines as needed by

non-symbolic programs, and have in fact developed elsewhere

implementations of some of these ideas.

What is proposed for future research, then, is an

investigation of design concepts appropriate for integrating

experlse into largely non-symbolic programs such as STRUTEX. One

possible approach has already been described in our discussion

of a transition-diagram-based design for STRUTEX. A number of

Page 61
related techniques appear promising, including investigations

into the representation and storage (in RIM) of code sequences,

generalizing the action codes currently transmitted by escape

predicates. While it would be premature to commit ourselves to

any detailed proposal here, it is definitely envisioned that the

resulting system will no longer be dependent on Prolog, and will

be easily integrable into applications such as STRUTEX.

Page 62
REFERENCES

Abbott, K., Exploration of Expert Systems Concepts for Onboard

Diagnosis of Faults in a Turbofan Aircraft Engine, 1985 American

Control Conference, June 1985, Boston, MA.

Feyock, S., Syntax Programming, Proceedings of the AAAI 1984

National Conference, August, Austin, Texas

Foderaro, F., Franz Lisp User's Guide, IR1, California State

University, Los Angeles, CA, November 1981.

Gries, D.. Compiler Construction for Digital Computers, J. Wiley

a Sons, 1971.

Spivey, J., Portable Prolog User's Guide, Dept. of Computer

Science, University of York, Heslington, York, England, October

1983.

BCS RIM Version 6 User Guide, Boeing Commercial Aircraft

Company: Central Scientific Computing Complex Document Z-3,

Nasa/Langley Research Center, May 1985

Page 63