Coupling rules to an object-oriented program5644770Abstract A method of coupling rules to a data domain of an object-oriented computer program. During run time, the coupling permits the computer to use rules to directly access user-defined objects for both the matching and the action phases of the inferencing process, Inferencing is implemented with an inference class object and user-defined class object are derived from a working memory element class. Claims What is claimed is: Description TECHNICAL FIELD OF THE INVENTION
______________________________________
rule has.sub.-- right.sub.-- neighbor( )
priority 7;
premise
{
Cell x( ) <x>, y( ) <y>, generation( ) <gen>,
alive( ) TRUE;
Cell x( ) {<x> + 1, y( ) <y>,generation( )
<gen>, alive( ) TRUE;
}
action
{
{cout << "the cell at ", << <x>, << <y>,
<< " has a living right neighbor";};
}
}
______________________________________
Each condition element within the rule's premise includes the name of a class from which the rule will inference, which in this example is Cell. The premise is formed by the keyword premise. Any number of condition elements follow the premise keyword. Each condition element is separated by a semicolon. The first identifier in the condition element specifies the class, which is followed by any number of accessor-value pairs separated by commas. Any accessor function that is defined for the class may be used. A condition element may be a pattern constraint on a class or a user-defined predicate. The following example is of a premise having two pattern constraining condition elements:
______________________________________
premise
Cell x( ) 0, y( ) 0, alive( ) TRUE;
Cell alive( ) TRUE, generation( ) >1000;
}
______________________________________
In this example, the first condition element is satisfied if there is some class instance of Cell in the working memory whose accessor functions x(), y(), and alive() return 0, 0, and TRUE. The second condition element is satisfied if there are any cells that are alive after 1000 generations. Any legal C relational predicate is allowed. They are: ==, !=, >, >=, <, <= In the case of noncommutative binary predicates, the argument for the left side of the predicate is derived from the working memory using the accessor function. The argument for the right side of the predicate is the value returned by the expression in the condition element. The expression may be a constant, a variable, or the value returned by the C++ expression. Pattern variables are distinguished by the use of angle brackets, i.e., <pat.sub.-- var>. The first appearance of a pattern variable in a rule binds the variable to the value returned by the accessor function. As the inference engine searches through the working memory, the variable may be bound to the value present for each instance of the class that has been passed to the rule-set. The scope of a pattern variable is limited to the rule in which it is bound. In the has.sub.-- right.sub.-- neighbor rule example set out above, the pattern variables <x> and <y> will bind to each cell in the bacteria simulation for which "alive" is true. The rule is satisfied for two cells in the same row, and those two cells are one column apart, and the generation is the same. This is expressed in the rules system language as binding <y> to the same row value for two cells, and specifying that one cell is at location <x> and the second is at position {<x>+1}. Any valid C++ expression is permitted in the value field of a condition element. Bound pattern variables may be embedded within the C++ expressions. The value returned by an accessor function may be required to satisfy a number of constraints. Below are two premises of two different rules. The first is satisfied if a cell holds a living bacteria, and that same cell held a living bacteria sometime earlier but not at initialization (generation =0). The second is satisfied if a cell has either a left neighbor or a right neighbor.
______________________________________
rule lives.sub.-- two.sub.-- cycles.sub.-- after.sub.-- start
premise
{
Cell x( ) <x>, y( ) <y>, generation( ) <gen>,
alive( ) TRUE;
Cell x( ) <x>, y( ) <y>, generation( ) < <gen>
!= 0, alive( ) TRUE;
}
. . .
}
rule has.sub.-- left.sub.-- or.sub.-- right.sub.-- neighbor( )
{
premise
{
<cell>:Cell x( ) <x>, y( ) <y>, generation( ) <gen>,
alive( ) TRUE;
Cell x( ) {<x> + 1} .vertline. .vertline. {<x> - 1}, y( ) <y>,
generation( ) <gen>, alive( ) TRUE;
}
. . .
}
.
______________________________________
The class instances that are matched and bound to a condition element may be labeled using a condition element variable. In the example above, the condition element variable <cell> is used to identify, to the rule's action, the class instance that matched that condition element in the premise. Condition element variables can also be used as additional pattern constraints. The value of a condition element variable is a pointer to the bound class instance. Thus, condition element variables can be used to guarantee that two condition elements match two different class instances. In the next example of a rule, the rule is satisfied if a cell has any neighbor, left, right, up, down, or diagonally. The first condition element binds pattern variables <x> and <y> to the x,y position of a cell. The second condition element is satisfied by any cell that is within +1 or -1 of the position of the cell bound to the first condition element. However, the cell that is bound to the first condition element will also satisfy the second condition element unless the programmer provides more specificity. One means of providing specificity is to test the condition element variables and verify that they are bound to different cells. Because in any one generation, there is only one instance of cell per x,y position, this test assures that the same cell is not used to satisfy both condition elements.
______________________________________
rule has.sub.-- some.sub.-- neighbor( )
premise
{
<cell1>: Cell x( ) <x>, y( ) <y>, generation( )
<gen>, alive( ) TRUE;
<cell2>: Cell x( ) <x> .vertline. .vertline. {<x> + 1} .vertline.
.vertline.
{<x> - 1}, y( ) <y> .vertline. .vertline. {<y> + 1} .vertline. .vertline.
5
{<y> - 1}, generation( ) <gen>, alive( )
TRUE, <cell1> != <cell2>;
}
. . .
}
.
______________________________________
As stated above, user-defined predicates are another type of condition element that may appear in the premise of a rule. The predicate must have return type Boolean. All the pattern variables used as arguments to the predicate must be bound. The predicate must have been declared extern and made available to the C++ compiler via an include file specified in the rule-set file. As an example of user-defined predicates, the rule premise above may also be expressed as follows:
______________________________________
Boolean neighbor.sub.-- p (int x1,int y1,int x2,int y2,Cell
*cell1, Cell *cell2)
{return (((x1 == x2) .vertline. .vertline. x1 == (x2 + 1) .vertline.
.vertline. x1 == (x2 -
1)) && ((y1 == y2) .vertline. .vertline. y1 == (y2 + 1) .vertline.
.vertline. Y1 == (y2 -
1)) && cell1 != cell2));
rule has.sub.-- some.sub.-- neighbor( )
{
premise
{
<cell1>: Cell x( ) <x1>, y( ) <y1>,
generation( ) <gen>, alive( ) TRUE;
<cell2>: Cell x( ) <x2>, y( ) <y2>,
generation( ) <gen>, alive( ) TRUE;
neighbor.sub.-- p(<x1>, <y1>, <x2>, <y2>, <cell1>,
<cell2>);
}
. . .
}
.
______________________________________
As indicated above, the rule system permits the use of C++ code in the action part of the rule.
______________________________________
rule action.sub.-- example( )
premise
{
Cell x( ) max <grid.sub.-- size>;
}
action
{
int i;
for ( i = 0; i < <grid.sub.-- size>; i++)
{
make (Cell, i, i, 0, TRUE);
}
}
}
______________________________________
The action of a rule acts like a C++ function of type void. The parameters to this function are the condition element variables used in the premise of the rule. The values of these parameters are the values bound to those variables by the instantiation that has been selected for firing. The bound variables may then be used in any appropriate code of the action. The rule system will substitute the correct values into the action when the rule is fired. The rule system provides several functions that can be embedded in a rule's action and used to manipulate the class instances that form the working memory. The make() function creates and initializes a new instance of a named class by calling the class's constructor and passing it the list of arguments. The newly created class instance becomes part of the current rule-set's working memory. An example of the function call for make() for the named class, class.sub.-- id is: make (class.sub.-- id, argument.sub.-- list); A remove() function removes a class instance from working memory, but does not free the instance's memory. The deletei() function removes a class instance from working memory and then calls the class's destructor. Examples are: remove (<ce.sub.-- var>); deletei (<ce.sub.-- var>); The modify() function updates the specified values of the class instance that was matched by the premise. The particular class instance is identified by a condition element variable. The inference engine is notified that the class instance has been altered and the matcher must update its internal state to be consistent with those changes. Also, a halt() function, callable from the action function, may be used to terminate execution of the rule-set and return control to the calling program with a return value of False. The rule-set may be re-invoked and the execution continued from the next selected instantiation. An example of the use of make(), modify(), remove(), and halt() is set out in the following rule example. The rule finds a position with a living cell for two successive generations, creates a new living cell for a third generation, kills the second generation cell, removes the first generation cell from working memory, and stops the execution.
______________________________________
rule action.sub.-- examples( )
premise
{
<cell1>: Cell x( ) <x>, y( ) <y>, generation( )
<g1>, alive( ) TRUE;
<cell2>: Cell x( ) <x>, y( ) <y>, generation( )
{<g1> + 1}, alive( ) TRUE;
}
action
{
make (Cell, <x>, <y>, {<g1> + 2}, TRUE);
modify (<cell2>, alive( ) FALSE);
remove (<cell1>);
halt( );
}
}
______________________________________
User-Defined Class Headers To set up the user-defined objects for use by the rules system, the programmer modifies their class definitions so that they inherit from a working memory element class. As explained below, by inheriting from the working memory element class, the rules system can determine at run time the class type of a given instance. Thus, although the invention is not dependent on a particular object-oriented language, a characteristic of the language is run time type checking. In the preferred embodiment, the rules system has two working memory element classes, which provide flexibility in the manner in which the rules system uses user-defined objects. The two classes, Wme.sub.-- All and Wme, are the same, except for the manner in which they make data available to the rules system. The Wme.sub.-- All class provides a means for the programmer to specify that all instances created for this class be made available for inferencing. Thus, the programmer can simply specify that a class be derived from Wme.sub.-- All, and then each instance of that class will be available for the rule system to inference from. The Wme class is provided for those cases in which only selected instances of a user-defined object are to be made available for inferencing. These two means for passing user-defined class instances to a rule set via a working memory are referred to herein as implicit and explicit passing, respectively. Both classes provide the rules system with a means for associating a time stamp with a user-defined class object. They also provide a means for tracking various state information. Both classes use a list called the External Input Port (EIP), which is a global structure that holds all data that is to be made available at inference time. When a class instance derived from Wme.sub.-- All is created, the constructor for the Wme.sub.-- All class is called. This constructor puts a pointer to the newly created user-defined class object onto the EIP. In addition, any time a destructor is called on a user-defined class object that is derived from Wme.sub.-- All, the destructor for Wme.sub.-- All ensures that if that data is on the EIP, it will be removed. When a class instance is derived from Wme, two global functions enable the application developer to selectively add and remove data from the EIP. These two functions are add.sub.-- to.sub.-- eip() and remove.sub.-- from.sub.-- eip(). Each of these functions takes a pointer to an object that has been derived from Wme. Thus, in the application program, when an item of data is needed by the rules system, the application program should call the add.sub.-- to.sub.-- eip() and pass the pointer to that data. Both of the functions may be called from anywhere within the application program, including from within the action of a rule. The following example is of a user-defined class, Cell, derived from Wme:
______________________________________
class Cell: public Wme
{
private:
int c.sub.-- xm c.sub.-- y, c.sub.-- generation;
Boolean c.sub.-- alive;
public:
int x( );
int y( );
int generation( );
Boolean alive( );
cell( );
not cell( );
}
______________________________________
where cell() is a constructor and not cell() is a destructor. As is usual in C++ programming, the class has private and public data and methods or functions that may be called. At run time, Cell is instantiated to create an object. The derivation from Wme makes this object available for inferencing. Rule Calling Sequences FIG. 2 illustrates the run time process of using a computer to couple rules to an object-oriented program. To use the invention to perform this coupling, a program developer inserts a rule calling sequence into the object-oriented program. The following example is of a rule calling sequence that uses the Wme class to explicitly pass user-defined object instances to a rule-set.
______________________________________
# include <LAMPS/lamps.h>
main( )
Rule.sub.-- Set *my.sub.-- rule.sub.-- set;
Generic *wme.sub.-- list;
// any C++ application code
my.sub.-- rule.sub.-- set = new Rule.sub.-- Set;
my.sub.-- rule.sub.-- set -> init.sub.-- infer("life");
my.sub.-- rule.sub.-- set -> add.sub.-- to.sub.-- eip (new Cell
(1,1,0,TRUE));
my.sub.-- rule.sub.-- set -> inference( );
// any C++ application code
}
______________________________________
As illustrated in the above example, and by step 21 of FIG. 2, an included header defines the inference class Rule.sub.-- Set. In step 22, an instance of Rule.sub.-- Set is identified and initialized. Step 23 is invoking a rule-set object, which can occur at any time from within C++ code or from other rule-set objects. When a rule-set is invoked, the particular set of instances that form its initial working memory are specified. A file containing a set of rules, such as the rule-set file described above, initializes a rule-set object. In the above example, memory is allocated for an instance of Rule.sub.-- Set using new, as with any C++ object. The rule-set is initialized by passing the name of a set of rules to the instance, using an init.sub.-- infer() function. In the example, my.sub.-- rule.sub.-- set is bound to the rule-set called life. Step 24 instantiates the user class. In step 25, user-defined class instances are marked for use by the rule-set using the add.sub.-- to.sub.-- eip() function. As explained above, this function explicitly adds an object to the working memory of a rule-set. An alternative embodiment includes all instances implicitly. Thus, step 26 depends on whether the instance is to be derived explicitly or implicitly. In step 26, an inferencing process is invoked by calling inference(), which returns a Boolean value. A return value TRUE means that inferencing terminated when there were no longer any satisfied rules. A return value FALSE means the inferencing terminated when a halt() function was executed in the action of a rule. Illustrative Inference Engine Data Structures FIGS. 3-6 illustrate various objects used by the computer at run time to connect user-defined objects of an object-oriented program to the rules. The particular data structures described herein are an illustrative example of implementing the inference engine, using the inference class and the working memory element class described above, as well as classes representing condition elements and rules. In this section of the patent application, for purposes of example, the inference class is designated as Rule-Set as in the preceding sections. The user defined class instance that is derived from the class Wme or Wme.sub.-- All is pointed to by the Alpha Directory Element or ADE. The condition element and rules objects are designated Cond.sub.-- Elem and Rules, respectively. Included within FIGS. 3-6 are a number of vectors and tables. The zeroth entry of each is set to zero, thus the first entry is at index one. This explains why certain values in the description below seem to be offset by a value of one. Because an object of the Rule-Set class is associated with a rule-set, "rule-set" as used below refers to the current rule-set. Likewise, because an object of the Rules class or Cond.sub.-- Elem class is associated with a particular rule or condition element, respectively, "rule" and "condition element" refer to the current rule and the current condition element. FIG. 3 illustrates the inference class object, designated Rule-Set, which is created at runtime by the application program, for each rule-set that the application program uses. Once created and initialized, Rule-Set contains both the code and data needed to perform a forward chaining rule evaluation. Rule-Set has the following private data elements: The rs.sub.-- working.sub.-- memory field is a pointer to a linked list. Each element of the linked list contains a pointer to an instance of the ADE class, which is explained below in connection with FIG. 4. All data on this list is what working memory is defined to be and is in descending time stamp order. The rs.sub.-- ces field is a pointer to a vector of instances of the Cond.sub.-- Elem class. Each condition element instance reflects information about a particular condition element within the premise of a rule. Therefore, this vector contains data for each of the condition elements that make up all the premise of all the rules in the rule-set. The rs.sub.-- rules field is a pointer to a vector of instances of the Rules class. The vector contains the needed information about the premise and action of each rule in the rule-set. The rs.sub.-- ce.sub.-- tbl field is an array of condition element indices. The format of the data in the table is that of many zero-terminated lists of condition element indices placed back to back. Each instance of the Rules class in the Rules vector attached to the rs.sub.-- rules field has an r.sub.-- ce.sub.-- index field that indexes into this table. At that point in the table, starts a zero-terminated list of all condition element indices that make up the premise of the rule. The rs.sub.-- rule.sub.-- tbl field is an array of rule indices. The format of the data in the table is that of many zero-terminated lists of rule indices placed back to back. Each instance of the Cond.sub.-- Elem class in the Cond.sub.-- Elem vector attached to the rs.sub.-- ces field has a ce.sub.-- rule.sub.-- ndx field, which is an index into this table. At that point in the table, starts a zero-terminated list of all the rule indices that use this condition element. The rs.sub.-- premise.sub.-- tbl is an array of the address of each executable procedure associated with each condition element. Each instance of the Cond.sub.-- Elem class in the Cond.sub.-- Elem vector attached to the rs.sub.-- ces field has a ce.sub.-- premise.sub.-- ndx field, which is an index into this table. There is only one index per condition element. The rs.sub.-- action.sub.-- tbl field is an array of the address of each executable procedure associated with the action of the rule. Each instance of the Rules class in the Rules vector attached to the rs.sub.-- rules field has a r.sub.-- action.sub.-- ndx field, which is an index into this table. There is only one index per rule. The rs.sub.-- dominant.sub.-- tuple field contains the pointer to the current dominant tuple. The phrase "dominant tuple" refers to the ADE instance that currently has the numerically largest time stamp of all the as yet unprocessed ADE's. Once an ADE has been processed, i.e., it has become a dominant tuple and all the rules that use the condition element it is attached to have been tested, it cannot be selected as a dominant tuple again. FIG. 4 illustrates the ADE class. It is through ACE instances that the system has the ability to access instance data from user-defined object classes. Each of the following fields is a private element of ADE: The ade.sub.-- time.sub.-- stamp field is set by the system so that each item of user data has a unique identifier (id). The value assigned by the system to any given ADE is the next available integer in a sequence. The ade.sub.-- flags field contains bits used to represent the state of a flag. The ade.sub.-- ce.sub.-- ndx field has a value that represents the index into the Condition Element vector for the condition element to which this ADE is assigned. If the data is appropriate for more than one condition element, another ADE is created to point to the same user data and that new ADE is linked into the condition element's alpha list. The ade.sub.-- ordered.sub.-- rules field is given a value only once during the lifetime of the ADE. This occurs when the ADE becomes the dominant tuple. The value will be a pointer to a vector of rule id's. The system determines which rules need to inference on this item of data. If more than one rule does, the system determines the order in which the rules will be tried. Once the order is set, it cannot be changed for this ADE. The system processes each rule in turn. When the last rule id in the vector is processed, the vector is removed and the ade.sub.-- order.sub.-- rules field is set to NULL. A flag in ade.sub.-- flags is set to indicate that all rules that use this data have already been processed, thus preventing this ADE from becoming a dominant tuple again. The ade.sub.-- ce.sub.-- state field works in conjunction with the ade.sub.-- ordered.sub.-- rules field. This field is a pointer to a Condition Element state vector associated with the current rule id. As each rule is processed, the previous value of this field is deleted and a new vector is created. The vector's length is one more than the number of condition elements that make up the premise of the current rule, because the zeroth position is set to zero. The purpose of this state vector is to keep track of where the system is in processing the alpha memories associated with each condition element in the rule's premise. This field is further explained below in connection with the Ce.sub.-- state class. The ade.sub.-- user.sub.-- data field points to an instance of one of the user's or programmer's class instances. This class instance is derived from the Wme or Wme-All classes described above. Referring now to the Ce.sub.-- state class of FIG. 4, while an ADE is the dominant tuple, the field ade.sub.-- class.sub.-- state in each ADE class instance will point to its current Ce.sub.-- state vector. This state information is for the rule currently being pointed to in the ade.sub.-- ordered.sub.-- rules vector. The Ce.sub.-- state vector maintains state information about where the system is in processing the alpha memories associated with each condition element in the premise of the rule. Each condition element in the premise of the rule has an entry in this Ce.sub.-- state.sub.-- vector. When the system is finished matching the alpha memories against the current rule, the system will remove this vector. A Ce.sub.-- state class instance has the following four private data members: The cs.sub.-- ce.sub.-- id field holds the id of the condition element whose state information is kept in this Ce.sub.-- state class instance. The cs.sub.-- state field represents the current state in processing the alpha memories for this condition element. The cs.sub.-- initial.sub.-- ts field holds the time stamp of the ADE that is the first one on this condition element's ce.sub.-- alpha list that has a time stamp less than the dominant tuple's. The ADE's are kept in descending time stamp order, therefore, all ADE's after the initial ADE have time stamps less than that of the dominant tuple. The cs.sub.-- current ts field holds the time stamp of the ADE that is current being used in the match phase. FIG. 5 is a diagram of the Cond.sub.-- Elem class and vector. The condition element vector contains a fixed number of instances of the Cond.sub.-- Elem class. The number of instances is determined when a rule-set is translated during the rules translating step of FIG. 1. The space for this vector is allocated when the private member function Rule-Set::read.sub.-- data() encounters the data record (A1) that holds the sizes for all vectors and tables as determined by the translator. The following list is of the private data members of the Cond.sub.-- Elem class, whose instances make up this vector. The ce.sub.-- alpha field is a pointer to a linked list of instances of the ADE class. These instances actually exist on the linked list, rs.sub.-- working.sub.-- memory, within the Rule-Set class object. Therefore, each node in the ce.sub.-- alpha list points to an already existing ADE class instance and its associated data. The ce.sub.-- rules.sub.-- ndx field is an index into the table rs.sub.-- rule.sub.-- tbl, which is within the Rule-Set class object. At this index point in rs.sub.-- rule.sub.-- tbl, starts a zero terminated list of rule id's that use this condition element within their premise. At minimum, there is one rule id followed by a zero. The ce.sub.-- rule.sub.-- cnt field represents the number of rules that use this condition element. The ce.sub.-- class.sub.-- type contains either the index to the next condition element of the same class type as this condition element, or a zero if it is the last one in the list. When the translator translates the rule-set, it ensures that condition elements for each class type are linked. The Rule-Set::read.sub.-- data() private member function encounters a record in the data file, which contains the names of each class type and the index to the first one of that type in the Condition Element vector. The ce.sub.-- premise.sub.-- ndx field is the index into the rs.sub.-- premise.sub.-- tbl of the Rule-Set class object. At this index within this table is an index to the address of the function that, when branched to, executes the code associated with this condition element. FIG. 6 is a diagram of the Rules class and vector. The rules vector contains a fixed number of instances of the Rules class. The number of instances is determined when the rule group is translated. The space for this vector is allocated when the private member function RuleSet::read.sub.-- data() encounters the data record (A1) that holds the sizes for the vectors and tables, as determined by the translator. The following list is of the private data members of the Rules class, whose instances make up this vector. The r.sub.-- ce.sub.-- ndx field is an index into a table called rs.sub.-- ce.sub.-- tbl, which is one of the private data elements in a Rule-Set class object. Starting at this index in rs.sub.-- ce.sub.-- tbl is a zero-terminated list of the condition element id's that make up the rule's premise. These id's are the index into the Condition Element vector, which derive from the rs.sub.-- ces private data element in the Rule-Set class object. The r.sub.-- action ndx field is an index into a table called rs.sub.-- action.sub.-- tbl, which is one of the private data elements in the Rule-Set class object. At that index in rs.sub.-- action.sub.-- tbl is the address of the function that should be branched to in order to execute the action of this rule. The r.sub.-- flags field contains bits used to represent the state of a flag. The r.sub.-- ce.sub.-- cnt field contains the count of the number of condition elements in the premise of the rule. This field helps differentiate which rule to try next when more than one rule is to be chosen from. The rule having the most condition elements tends to be the most specific, and therefore, tends to be the rule chosen to have its premise evaluated. Other Embodiments Although the invention has been described with reference to specific embodiments, this description is not meant to be construed in a limiting sense. Various modifications of the disclosed embodiments, as well as alternative embodiments will be apparent to persons skilled in the art. It is, therefore, contemplated that the appended claims will cover all modifications that fall within the true scope of the invention.
|
Same subclass Same class Consider this |
||||||||||