A Modular Tool Kit for Knowledge Management

A Modular Tool Kit For Knowledge Management

Gilles M. E. Lafue Reid G. Smith

Schlumberger -Doll Research Old Quarry Road Ridgefield, CT 06877-4108 USA

This paper describes a rule interpretation system, a semantic in­ tegrity manager. a task representation system, and a file manager lor storing and retrieving objects. These tools implement the inter ­ pretation of the declarative representations lor the entities they manage: rules. integrity constraints. tasks. files. The salient fea­ tures of Strobe needed for the. presentation of the tools are tn tro duced in the next section. Each tool is then described. ftrst through examples of the declarations it supports- drawn primanly from Crystal - and then by showing the objects that implement 11.

ABSTRACT

We describe an integrated programming environment for develop­ ing knowledge-based systems. The environment contains a variety of general -purpose tools: a rule interpretation system, a semantic integrity manager, a task representation system and a file manager. Although the tools l1ave different origins (e.g .. rule­ based systems, database management, process control) , an object-oriented foundation lends modularity and consistency to the tool kit.

I. INTRODUCTION

By now the value of powerful tool kits for developing knowledge­ based systems is well-understood . Such tools act as substrates- computational bases that allow system builders to concentrate on the problems of acquiring and formalizing domain knowledge. In this paper we discuss a number of specific tools that we have found to be useful. We also argue for the utility of an object-oriented foundation that ties the individual tools together in a coherent fashion.

The foundation for our tool kit is an object-oriented knowledge representation system called Strobe (5, 6]. It has been used in a variety of applications. most recently in Crystal (9], a system that supports interactive manual and automatic interpretation of well logs, (i.e .. measurements made in boreholes) . This system was developed for two main classes of users: end -users (le .. log interpreters) doing interactive well-log interpretation. and inter­ pretation program developers. It combines graphic display and manipulation of logs with graphic editors and menus. It controls distnbuted execution of interpretation programs either on the Xerox workstations or on Ethernet-connected Vaxes. These programs have been written from a variety of computational perspectives (e.g .. statistical . pattern recognition , symbolic) and in a variety of programming languages. Strobe and Crystal provide the glue that binds these heterogeneous components together.

The Crystal knowledge bases incorporate a number of subsystems that are neither specific to the Crystal application nor to well-log interpretation. These subsystems are the tools of a modular , general-purpose knowledge-management tool kit that can be used to extend Strobe. Each tool is incorporated into a basic Strobe knowledge base by adding slots to one of the initial domain­ independent objects, or by adding one or a few objects. Each tool is modular in that it doesn't require modifying slots or functions defined by other tools.

II. STROBE

A Strobe knowledge base is a collection of objects of two types: classes, which can be specialized, and individuals which cannot. Objects are organized into taxonomic hierarchies (which may be tangled) along which properties are inherited (alternative in­ heritance paths are also supported) .

A Strobe object has properties called slots, and a slot has properties called face ts. Both slots and facets may be inherited. Some facets. namely. Value and Oaratype. are system-defined and exist lor all slots; others are user -defined. Message-passing and event-oriented computation are supported.

Strobe supports multiple knowledge bases in the same address space. Also, messages can be sent to objects in any knowledge base, even if that knowledge base is on another machine con­ nected by Ethernet. (Indeed, any Strobe operation can be per formed across the network.) To further support distribution and computational heterogeneity, Strobe had been implemented tn a variety of languages: lnterlisp-0 on Xerox workstations. Mainsail . Commonlisp and C on Vaxes. This paper concentrates on the lnterlisp-D version.

lnterlisp-0 Strobe has a display-oriented editor called Impulse [4] . This editor is itself built as a collection of Strobe objects. As a result , it can be specialized to suit the needs of Strobe applica­ tions, based on the types of declarations supported by the tools discussed here. An example of such a specialization is presented in [9] .

A. User-defined Datatypes

A datatype in Strobe is itself implemented as an object. Datatyping provides another form of inheritance in that a slot may inherit some of its facets, typically operations, from its datatype. More precisely, receivers for messages sent to facets may be inherited from slots in the datatype object. Such slots are characterized by the fact that their name starts with the atom " DATUM ". For in stance. a message sent to the Put facet of a slot is forwarded to the DATUM-Put slot of the object implementing the datatype of the slot if no receiver can be found through standard taxonomic in­ heritance.

B. User-defined Facets

User-defined facets are useful for meta-data encoding. They have been used extensively i·n Crystal to support communication be­ tween knowledge bases. By agreeing on the meaning of a rela­ tively small number of facets, knowledge bases can interpret each other's objects and slots without detailed knowledge of each other's doma1n of application (e. g .. object and slot names). For example, a part of an entity may be identified based on a Role facet set to Part rather than on the name of the part . Each of our tools defines some facets and incorporates an interpreter for them.

C. Initial Objects

A Strobe knowledge base starts with a few general objects which are organized in the generalization hierarchy shown in Figure II 1. DATA TYPE is the ancestor of all data type objects. Initially, it comes with a few slots that contain functions for implementing basic operations such as putting a value into a slot, getting, printing or editing a slot value. The message handlers for some of these slots (e.g., OATUM- Ed it or DATUM- Print) are defined in the descen­ dants of OA TA TYPE: BITMAP, TEXT, LISP (for lnterlisp-D functions and lambda expressions). EXPR (for arbitrary s­ expressions) and OBJECT (for slots whose value points to Strobe objects).

Ill. RULE INTERPRETATION

The rule interpreter [7] included in our tool kit applies rules in a forward-chained manner. The rule syntax supports a number of types of match variable instantiation in the left-hand side. In ad­ dition. the system provides support for user extensions to the syn­ tax. A form of rule compilation can be used to generate code and speed up rule application. Rules can be grouped into Rulesets and control structures defined for attempting and firing rules as­ sociated with rulesets. Uncertainty is currently handled according to the EMYCIN model [10] . There is also a simple mechanism for generating natural language rule translations. Finally, and most important, rules written for this system can access domain knowledge encoded as Strobe objects. 2

1 Figures showing objects are to be read as follows. General information about the object (such as its synonyms, whether it is a class or an individual, its immediate generalizations) is shown first . Slots are then shown indented with respect to the object information, and when shown, the facets of a slot are indented with respect to the slot name. The value (if any) is printed following the slot name. Names in curly brackets are synonyms for the slot with which they are associated .

A. Declarations For Rule Interpretation

Each rule in the system is itself a Strobe object- an instance of the class Rule. Figure 111 -1 shows a sample rule (taken in concept from the Dipmeter Advisor · system [8]) .

Clauses may refer to Strobe objects (e.g., via the THE function, in Figure 111 -1, which accesses a slot of an object) as well as other Lisp data structures. They may also bind variables that can be accessed during the matching and execution of the rule. We have defined an initial rule language of approximately 50 left-hand-side predicates and 10 right -hand-side actions. The rule language may be augmented as desired by end-users by defining lnterlisp func ­ tions (and translation templates, if desired).

To match Normal Fau 1 t 9 against the database, the rule inter­ preter attempts to find a normal fault zone and a zone charac­ terized by a signal pattern known as a red pattern, such that the two zones together satisfy the predicates associated with Condit i on2. The rul e interpreter attempts to match the rule by sequentially instantiating the match variables. As each match vari ­ able is instantiated, the truth value of the clause is tested. If true. then the instantiation process continues. but if false. then the process backtracks to the last variable instantiated that has un­ tried values in its domam and reinstantiates it to its next value 3

2 The ability to integrate rules and structured objects as well as the ability to extend the rule syntax in a flexible way are not easily managed in existing rule interpreters. like OPSS [1] . We have opted for the flexibility end of the flexibility/ speed spectrum.

Mark of Schlumberger

3 Note that there may be several zone pairs for which the conditions are satisfied. To find them all , some form of iteration is required . This is pertormed aulomatically, as desired, by the rule interpreter.

There are several forms of quantified·condition clauses. In the standard case. the domwn of a match variable is the set of in· stances of a specified class (as in Figure 111·1 ). Alternatively, it can be the set of instances of a class and of all its subclasses. Other possibilities can be defined by the user. Another type of quantified·condition clause that we have found useful is illustrated by the rule in Figure 111 ·2. This rule expresses the fact that a tidal flat is characterized by a number of signal patterns known as blue patterns, that have alternating azimuth. We do not know a priori how many such patterns there will be- their number depends on the thickness of the flat. Set quantification in a single rule appears to provide a useful match to the way that variable thickness units are conceptualized and detected by our domain specialists.

Rules are grouped into Rulesets . A ruleset defines the control structure to attempt and fire the rules it contains. It can eliminate the need tor clauses often found in flat rule systems that are aimed at setting the context for rule application. Figure 111·3 shows a ruleset used for stratigraphic interpretation of dipmeter data.

The simplest ruleset contains a single list of rules called NORMAL -RULES. These rules are attempted one at a time accord· ing to their order in the list. Each time a rule fires, the content of the CONTROL-STRATEGY slot determines whether scanning is to continue with the next rule (Cant inueAfterF iring) or is to begin again with the first rule (ReStar tA fterF i r i ng) 4 This iteration continues until no rules can be successfully fired . (This default termination condition can be overridden in particular rulesets.)

A ruleset can also contain the following lists of rules. FIRE -ONCE-RULES can only be fired once for each invocation of the ruleset. They can be used to initialize the execution of a ruleset. FIRE- ALWAYS-RULES are attempted on each iteration regardless of the control strategy. They can be used to respond to the firing of other rules (e.g., to update dependent relationships). Unlike NORMAL-RULES and FIRE - ONCE - RULES, FIRE-ALWAYS­ RULES can be fired more than once with the same match variable bindings within a single ruleset invocation.

To assist in explanation and debugging, the execution history of each ruleset invocation is recorded as an instance of the ruleset class. It retains information such as the rules that were attempted and fired (together with their match variable bindings and the ob· jects created or modified as a result of their firing) .

B. Rule Interpretation Subsystem

The rule interpreter is Implemented via the Ru 1 e object and the Ru 1 ese t object (Figure 111-4! !.Not all of their slots are shown.)

An additional feature has proved quite useful for hypothesis test· ing. In applying a ruleset (or a ru le), the caller is allowed to pass in a set of bindings. These bindings are analogous to lambda bind· ings and allow ruleset invocation to be considered as a form of function invocation. Match variable bindings may be included in this list, in which case, the rule interpreter tries to fill in the remain· ing instantiations.

4 The ReS tar tA f terf iring option is useful when the actions of an individual rule could interact with the conditions of other rules. It is often used in combina· lion with a rule ordering that places the most specific rules before the most general rules. The Cont inueAfterfiring option is useful when individual rule actions are independent or additive. (It is the default strategy.)

Object: r ·ida 11 Type : Individual Generalizations: Ru I e IF: (Condit ion! Condilion2) THEN: (Act ion! Action2 Action3 Acti on4) Condition! : (THERE ·EX ISTS :X Transit ion/l nner Shelflone ($· (THE Influence : X) 'Wave/TideDominated )) Condition2: ( THERE·EXI STS-SET :l OluePattern ($Wlffll N ( $NEW :Z) :X ) ($ABOVE ($LAST :l) ($NEW :Z) Overlap Gap ) ($OPPOSITE-DI REC TION (THE Azimuth ($NEW :Z)) (l HE Az imuth ($LAST :Z)) rol) FI NALLY($> (L fNG TH :l) 1)) Action! : ($CREATE :ll as a fidalflatLone Action2: {$ASSIGN f op o f U to be (THE Dept h ($FIRST :Z))) Action3 : {$ASS I GN Bottom of ll to be (THE Depth ($LAS 1 :Z))) Action4 : ($ASS I GN Ax i s o f :/./ to be ( THI Azimu th (SL AST :Z))) TRANSLATION: . l F: ( l ) there ex i st s an instance of t he class Transit ion / lnnerShe! flone (:X) such that the I nfluence of : X " Wave/T ideDomi nated , and (2) t here exi s t s a set o f 1nstances o f the class BluePa tte rn ( : z) such that the cu r rent candidate for :Z I S with in X. and such that the l ast item o f :l i s above the current candidate for· : Z wit.h'ln [Overlap,Gap) , and such t hat the Atimuth of t he cur r ent candidat e for ·z IS opposite to the ALimuth o f the las t item of :Z with in ro l degr·ees. and such t hat the s ize of the se t :Z > 1 I'HEN : (I) create a Tidal f l atZone I : ZZ) ( 2) the fop o f :Zl _the Dept h o f the f i r s t item o f ( 3) the Bottom o f :ll the Dept h of the last ( 4) the Axis of : zz the Azimuth of the l ast Figure 111 -2: Tidal Flat Rule Object : DEEP-MAR!NE - RULESEl Type: I NO IV !DUAL Generalizations: Ru 1 eset i t em item :l of :Z o f : I NORMAL·RULES: MARINE-20 MAR I NE-21 MARI NE -2 2 MARI NE-23 MAR ! NE-24 MARINE-27 CONTROL·STRATEGY: ReStartAf terf i r iny Figure 111·3: Deep Marine Ruleset Object: Ru I e Type : CLASS Gene ralizations : ROO r IF: THEN: RULESET: TRANSLATE: frans l a t eRu le TRANSLATION: Apply : ApplyRule Match: Ma tchRu I e MatchAII : MatchRu l eA 11 Execute: Execut eRu I e Object : Ru 1 ese t Type: CLASS Generalizations : ROOT NORMAL·RULES: FIRE·ONCE·RULES: FIRE·ALWAYS·RULES : CONTROL· STRATEGY : TERMINATION ·CONDITION: KNOWLEDGE· BASE: Apply : ApplyRul ese t

IV. SEMANTIC INTEGRITY MANAGEMENT

The integrity management system allows the user to define con· straints on slots of objects, and to define actions to be taken in case of constraint violation or satisfaction (with appropriate defaults). The system analyzes the constraints and derives the in· formation it needs to check them at run time (i.e. , the constraint variables and the operations that require checking). Currently, our constraint language is a combination of lnterlisp·D and Strobe.

A. Declarations For Integrity Management

We distinguish several types of integrity constraints. A single-slot constraint involves a single-slot. A datatype constraint applies to all slots having a particular datatype. A multi-slot constraint in­ volves several slots, in one or several objects. Since slots can be set-valued. constraints are divided into element constraints (that apply to the elements of a slot value) and set constraints (that apply to a slot value as a set).

Two alternatives for encoding a constraint are supported: (i) as slots of an object and (ii) as facets of a slot. In this section. we discuss constraints encoded as objects. For a presentation of slot encoding, and criteria for choosing between the two alternatives. see [2] and [3].

Figure IV-1 shows the object that defines a well location in terms of a town. county, state. country and continent. The Cant inent slot is subject to a (single-slot) constraint that its value must belong to the set of names enumerated in the Candidates facet . The constraint is implemented in the Cant i nentCons tra i nt ob­ ject (Figure IV-2) whose Condition slot encodes the constraint definition and Correction slot the correction of violations (here, simply an error message).

Object: We I I Loca t i on Type : C 1 as s Generalizations : ORJ ECT Well : TOWN: {fown shi p) COUN : (Cou nt y Par i sh} STAT: {St a t e Province} NATI : ( Nat ion Country} CONT: {Conl inent} Datatype: EXPR Candidates: (Europe North-America South - America Asia Afr ·ica Australia) PutEiementConditions: Cant inentCon stra int AddEiementConditions: Conti nen tCons train t

Object : Cont inentCon s tra i nt Type : Class Gene ralizations: Sing I eS 1 o tCon s t ra i"n t Condition : (MEMBER Value Candidates) Correction: (Error Value "i s not one of : " Candidates ) SetOrEiementConsl rain!: E 1 emen t ConstrainedObject: Well Location ConstrainedSiot: Continent Facets: Candidates

Figure IV-3 shows the Measurement datatype object and one of its constraints: the Internal Un i tsConstra i nt, implemented in the object shown in Figure IV-4. The constraint states that if slots whose datatype is a measurement specify the units for their values-their internal units-the values they are assigned must be in those units. The Correction slot contains the code to make the conversion if necessary.

Object: Measurement Synonyms: DimensionedQuant ity Type: C I as s Generalizations : IJATATYPE UnitsConversion: lnte rnaiU nitsConst rain!: In te rna I Un it sCons train t Datatype: DatatypeConstraint PutEiementConditions : In te rna 1 Un it sCon strain t AddEiementConditions : In t erna I Un i tsCons train t

Object: lnternaiUn i t sCons t r aint Type: C I ass Generalizations: llat atypeCo ns tra int Condition : ( EO ( f etch UN I I S of Va lue ) ln te rnaiUn i t s) Correction: (MI SSAGE Da tatype · Un i t sConver s ion ( U Sl ( f e t ch UN!I"S o f Value ) lnternaiUnit s ) } SetOrEiementConsl raint : E I emen t DatatypeObject : Measurement ConstraintSiot : In t e rna I Un i t sCon s tra i n t Facets: lnt erna IUn it s

Figure IV-5 shows the Condition slot of an object that implements a multi -slot constraint involving several objects. The constraint is between different regions, or components. of a geological fault. referred to as the upper and lower distortion regions (or blocks) and the breccia region (the zone between the blocks charac­ terized by crushed rocks) . It states that the upper distortion region of a fault is above its breccia region which , in turn. is above its lower distortion region. It assumes that there exist (,) F au 1 t objects with UpperD i start ion Region , LowerD i start ion ­ Region and BrecciaRegion slots. and (ii) Distort ionReg ion and BrecciaRegi on objects with Fault , Top and Bottom slots_

Object: DistortionBrecciaConstraint Type: Clas s Gene ralizations: Mu 1 t iS 1 o t Con s train t Condition: (OR<* (THE Fault DistortionRegion) (THE Fault BrecciaRegion ) ) {if ( = Oistorti onRegion (IHE UpperDistortionReg i on (THE Fault BrecciaRegion) ) ) then ($ABOVE (THE Bottom DistortionRegion) (THE Top BrecciaRegion) ) ) {if ( = DistortionRegion (THE LowerD i stortionRegion (THE Fault BrecciaRegion))) then ($ABOVE (THE Bottom BrecciaRegion) (THE Top DistortionRegion)})}

The user fills the Condition slot and optionally, the Correction and Action slots (the latter states a side effect of constraint satisfaction). These slots can contain function names, lambda ex­ pressions or s-expressions. They can reference slots and facets as free variables rather than by using Strobe access functions. In single-slot and datatype constraints, Value refers to the current slot value. In multi-slot constraints involving several objects, the THE function references slots in relation to their objects.

The checking declarations generated and used by the system basically consist of identifiers of the constraint variables to allow (i) insertion of triggers from the variables to the constraints at analysis time and (ii) efficient binding of the variables at run time.

A single-slot constraint object has a ConstrainedObject slot and a ConstrainedS/ot slot A datatype constraint object has a DatatypeObject slot and a ConstraintS/at slot Since these con­ straints can involve facets other than Value (e.g .. Internal Units in Internal Un i t sCons tra i nt) such facets are declared in a Facets slot. A Slots slot in a datatype constraint declares the slots of the datatype object involved in the constraint. and in a multi -slot constraint , it declares the constrained slots together with their respective objects.

A trigger associated with a slot is implemented by a facet that points to single or multi -slot constraints. The facet name indicates the operations on the slot that require checking (Put, Add, Remove) 5 . It also indicates whether the constraints are set or ele· ment constraints. This allows the user to reset the order in which constraints are checked (e.g .. element constraints before set constraints) and the system to efficiently order the constraints to check at run time. For example, the PutE/ementConditions facet of the Continent slot (Figure IV-1) indicates that Conti nen tCons tra i nt must be checked when a value is put in the slot.

A trigger associated with a datatype object is a slot that points to the constraints for the datatype. Its name encodes the same infor· mation as trigger facets. The AddEiementConditions slot of Measurement shows that In tern a lUn i tsCons train t must be checked when a value is added to a slot whose datatype is some measurement.

B. Integrity Management Subsystem

The integrity management system consists of slots added to the DATA TYPE object (Figure IV-6) and of constraint objects. The con· strain! objects are organized in a taxonomic hierarchy. The Constraint object is shown in Figure IV-7.

The DATUM-Put, DATUM-Add, and DATUM-Remove slots of DA TATYPE contain the operations for which integrity may be checked. These operations are also declared in the OperationsWithlntegrity slot of Constraint. DefaultOperations declares the default operations for which integrity is checked.

Object: DATATYPE Type : Class Generalizations: ROOf DATUM·Edit: DATUM· Print: DATUM-Get : sys/mge tvalue DATUM·Put : DatatypePut DATUM-Add: DatatypeAdd DATUM-Remove: Data typeRemove DATUM·AnalyzeConst raints : Data typeAna 1 yzeCons train ts ConstraintCheckingOrde r: (Data typeE I em en tCon strain t s El ementConstraints OatatypeSetConstraints SetConstraints)

Object: Constraint Type: Class Generalizations: DAr A TYPE Specializations: (Singl eS l ot.Constraint DatatypeConstraint Mu It ·S lotConstra int) OperationsWithlntegrJty : 1l'ut Add Remove) DefaultOperations : ( Pu t A<Jd)

Analyze:

Verify :

Figure IV-7: The Constraint Object

The DA TUM-AnalyzeConstraints slot of DATA TYPE and the Analyze slot of Constraint provide alternative ways of analyzing constraints. The former is a message handler for analyzing con· straints encoded in slots. The latter is a message handler for analyzing constraint objects. For example. an AnalyzeConstraints message sent to the PutE lementCond it ions slot of Measurement results in filling the DatatypeObject , ConstraintS/at and Facets slots of Interna1UnitsConstraint. An Analyze message to the Interna 1 Un i tsConstra i nt ol;lject results in fill · ing the same slots as well as the PutE/ementConditions and AddEiementConditions slots of Measurement.

5 Currently, the identification of the operations that may cause a constraint violation is based on heuristic, rather than formal, analysis, and can be overridden by the user.

The Verify slot in Constraint verifies whether a hypothetical value for a slot violates the constraints that apply to the slot. Instead of executing the corrections associated with the violated constraints, it returns an association list of the names of those constraints and the bindings of their variables. The ConstraintCheckingOrder slot declares the default order in which constraints are checked and can be reset in any datatype.

V. TASK REPRESENTATION

Declarative task representation has been successfully used to capture component function and structure in a number of domains: hardware design, fault detection, well-log interpretation Our motivation for task declaration is to provide a structure within which (i) a knowledge-based system can reason about tasks, (ii) a unified mechanism can control task execution, and (iii) code writ· ten from a variety of computational perspectives and in a variety of programming languages can be integrated. An example is described in [9] . It shows how the Crystal knowledge base respon· sible for the user interface interprets information about tasks to guide the user through their execution and how it prompts him for the necessary input. To date, we have concentrated on task/subtask relationships, data description and control flow.

A. Declarations For Task Representation

In our formalism, task declarations are mad~ in subclasses of the Module object. The execution history of a task is recorded as an instance of its class (analogous to ruleset invocation) . Figure V-1 shows some of the slots of a task called E i gen which represents a principal component analysis on the logs identified in the Act i velogs slot for the well identified in We 11 from TopDepth to BottomDepth. Among the outputs are principal component logs. represented by the PCLogs slot.

A task can be a substask of another task, which is called its abstraction. It points to that abstraction via a slot whose Role facet is set to Abstraction. For example, the Facio 1 og slot of an E i gen instance points to an instance of a module, called Facio 1 og · - a program that finds zones of similar log responses in a well , and whose first subtask is the principal component analysis carried out by E i gen. Conversely, a task points to its subtasks via slots whose Role facet is set to Expansion. Slots representing expansions also have an Order facet that indicates the relative (partial) order in which each expansion is normally to be executed. (E i gen has no expansions.)

The slots representing input and output parameters of a task are denoted by a Role facet set to Port and a Direction facet set to In, Out or (In Out) . These slots also have an Order facet that indicates to the system the relative (partial) order in which each input parameter should get its value. The Origin facet identifies where the value for the slot can be obtained. It may (i) identify the user (which in Crystal causes the user interface knowledge base to take charge); (ii) specify a slot of another object; or (iii) indicate that the task will compute the value itself. The Default facet con­ tains an s-expression that evaluates to a default value, and the Candidates facet evaluates to a set of possible values. These two facets are used by the user interface knowledge base in its prompting of the user (e.g., by presenting a menu if there are candidate values). Other facets are discussed in [9].

Mark of Schlumberger

The other facets associated with an input port are for integrity management. The Act i velogs slot, for example, is subject to an

Object: E igen Type: Class Generalizations: Modu 1 e Faciolog: Datatype: Faciolog Role: Abstraction Well: Datatype: Well Role: Port Direction: In ActiveLogs: Datatype: Log Role: Port Direction: In Order: 2 Origin: User Cardinality: (I 30) Candidates: (MESSAGE Well 'Logs) Condition: (MEMBER Va I ue Candidates) Facets: Candidates Operations: (Put Add ) Correction: (Retry Value .. isn't in .. Well) SetCondition : (~ 1 (for Log in Value count Log when (Generalization? Log 'Gammanay))) SetCorrection: (lletry .. You cannot select mor e than one Gamma Ray log ... ) SetOperations: (Put Add) Top Depth: Datatype: Depth Role: Port Direction: In Order : 4 Origin: User PutMultiSiotConditions: TopBo L tomCons train t Default: (MESSAGE ActiveLogs ·ropDepth) BottomDepth: Datatype: Depth Role: Port Direction: In Order: 4 Origin: User PutMultiSiotConditions: TopBo t tomCons tra i nt Default : (MESSAGE Act iveLogs ' BottomDepth) TopBottomConstraint : (> BottomDepth TopOepth) Datatype: Lisp Role: MultiSlotCondition Slots: (TopDepth BottomDepth) Correction: (Retry .. Bottom depth must be greater than top depth ." ) PC Logs: Datatype: Log Role: Port Direction: Out

element constraint that each value be drawn from the logs as­ sociated with the Well , and to a set constraint such that no more than one log can be of type GammaRay. Furthermore, its Card ina I i ty is limited to 30.

B. Task Declaration Subsystem

The mechanism to control task execution is implemented in the Modu 1 e object (Figure V-2). (Only some slots are shown.)

Object: Modu 1 e Type : Class Generalizations: OBJECT Code: Datatype: Lisp File: Address: {crystal$node}crysta1Sdisk <crystal .users > RemoteExecutionObject: Host: crystal$node KB: VLDB ReturnControl : Control: ModuleControl Datatype: Lisp· Iterate: NIL Interactive: T PauseOnEntry: NIL

The computation carried out by a task may execute either on the Xerox workstation or on a remote machine, in a language other than lnterlisp-0. In the former case, the computation is specified in the Code slot, which typically contains a function name. In the latter case, it is specified in the RemoteExecut ionObject slot. The value of that slot points to a Strobe object on the remote machine (identified in the Host facet) which is responsible for call ­ ing the foreign language program. That object (written in Mainsail. Commonlisp, or C Strobe if it resides on a Vax) exchanges input and output parameters with the current module object written in lnterlisp-D Strobe.

The ReturnContro 1 slot identifies where control is to be passed next (in terms of a host. knowledge base. object, slot and facet).

A task executes when its Con tro 1 slot receives a message. This slot contains the function that implements the task execution con­ trol mechanism. Basically, that function (i) acquires the input parameters; (ii) instantiates and executes expansions as required . if there are expansions. or else, executes the task computation: and (iii) passes control to the next module. Dynamic alteration of control flow is supported by resetting ReturnContro 1 slots on the fly. Note also that the Contra 1 slot has facets to modify con ­ trol flow (e.g., to iterate through a task or to pause for interaction before starting a task). Of course, the default values for these facets defined in the Modu 1 e object can be overridden in its specializations.

VI. FILE MANAGEMENT

Strobe manages objects in virtual memory. At the end of a session, all objects in a knowledge base are generally stored on the same file. Subsets of objects from a knowledge base may also be loaded and stored. The file management tool extends this basic capability in that (i) it allows more generality in specifying the sub­ sets of objects (by description as well as by name), and (ii) it keeps track of the files on which such collections are stored. Our goal is to provide DBMS-like facilities to cope with increasing numbers of objects as knowledge bases scale up.

A. Declarations For File Management

The filing mechanism is implemented via file indexes. A file index is defined as a conjunction of slot names. It maps values of that conjunction into file names. For example, a file index may be defined by the conjunction (We 11 Creat i onDate) and an index value may be (We11A 23-0ct-84). The object implementing that file index associates (We 11 A 2 3 -Oct -8 4) with the name of one or several files that contain objects whose We 11 slot value is We 11 A and whose Creation Date slot value is 23 -0ct - 84.

Figure Vl-1 shows a file index whose conjunction, defined in the Index slot, is (We 11 Creat i onDate) . The slots IndexVa 1 ue 1. IndexVa 1 ue2 and IndexVa 1 ue3 represent index entries, i.e., tuples of the mapping between index values and file names. The Value facet of such a slot is an index value, e.g., (WellA 23 - 0ct-84), and its Files facet points to the files that contain objects corresponding to its value 6 . Slots implementing index entries are created and managed automatically by the system and are of no more concern to the user than the implementation of

6 An index value may point to several files because it is our policy to avoid duplication of objects on several files. As a result, an object corresponding to two index values (for two different indexes) is stored in only one of the two correspond­ ing files. and that file must be pointed to by the other index value.

8-trees in a DBMS. The user need only be concerned with loading and storing objects, not with the system's implementation of those operations.

Object: We 1 II ndex Type: [ndividual Generalizations: F i 1 e [ ndex Index: (Well CreationDate) lndexValuel: (WeiiA 23-Dct - 84) Datatype: EXPR Files: Wei1A obs; 1 lndexValue2: (Well A 2-Dec-34) Datatype: EXPR Files: (Wei lA obs: I true ohs; l) lndexValue3: (WeiiB 2-Dec-R4) Datatype: EXPR Files: We11B .obs: I

B. File Management Subsystem

The file management subsystem is implemented in the F i lelndex object (Figure Vl-2). Its specializations are individual user-defined objects representing file indexes such as We 11 Index. Address specifies the host, device. and directory where the files are actually found. LoadObjects contains a func· tion that takes an index value as argument and loads the objects corresponding to that index value. Similarly, StoreObjects stores the objects corresponding to an index value.

Object: F i 1 e Index Type: C1 ass Generalizations: ROOT Index: Address: {crystal$node}:crystal$disk <crystal .wells > LoadObjects: Fi1e[ndexload0bject.s StoreObjects: F i1 e [ ndexS to reOb j ec ts

VII. CONCLUSION

We have described the implementation of knowledge manage­ ment tools for Strobe knowledge bases and presented examples of the capabilities they offer. Each tool is confined to a few general domain-independent objects which can be added to an initial knowledge base. The addition of a new tool is modular in that it consists only of defining new objects or new slots of an existing object. Figure Vll-1 shows the initial taxonomic hierarchy of a knowledge base incorporating all tools described in this paper.

Implementation of the tools has been unified through an object· oriented foundation. This foundation also helps to unify access to the tools- through invocation via message. This is a simple, yet powerful concept that helps to integrate objects, rules, tasks. and procedures.

Tool kits such as ours offer a number of alternative styles of pro­ gramming: Rulesets, modules, constraints, .and procedures. While they do help integrate these various styles, criteria for selecting among the alternatives for any given task are not always clear. For instance, a computation to be carried out as the result of an operation on a slot could be encoded as a constraint (possibly with maintenance actions), or as a ruleset, or as a module whose invocation is triggered by a demon associated with that slot. Our intention, then, is to use the tool kit both as a development vehicle for knowledge-based systems and as an ex­ ploration vehicle for seeking selection principles.

ACKNOWLEDGMENTS: We gratefully acknowledge the Crystal team for providing the context for this work. Eric Schoen built Impulse, parts of the task representation system and lower-level tools such as the networking and Strobe Vax execution environ­ ment. Robert Young made a number of valuable suggestions.