JEOPS - The Java Embedded Object Production System

User's Manual

Version: 2.0 beta 1 - June 2, 2000
Author: Carlos Figueira Filho

Table of Contents
Overview	Quick Description
What Is New	Rule Syntax
A First Example: Fibonacci Numbers	Accessing the Working Memory
Internal Architecture	The Conflict Set
The Modified Problem	Sample Applications
Concluding Remarks	References

Overview

JEOPS is a proposal for an extension of the Java Programming Language with a mechanism for embedding first-order, forward-chaining production rules into Java applications. It was created to provide the declarative expressiveness of production rules to a language whose popularity is growing steadily since its creation, but still lacks such a mechanism, that in our opinion is a necessary condition to the development of large or complex intelligent systems.

The JEOPS system (formerly called JEPS) was based on an undergraduate project, a simple inference engine to the Java language, developed by the author of this manual and Carlos Cordeiro. The project was then continued by me, supported enthusiastically by Professor Geber Ramalho, who has been orienting me in the developing of this tool until now.

The previous verson of JEOPS was composed of a set of classes that read the rules from a text file and interpreted them as needed. In fact, that version was performing the work of the Java compiler, interpreter and the inference engine itself, so its complexity grew to a certain extent that it became harder and harder for me to improve it. In addition, as the rules were interpreted, they did not take advantage of the JIT mechanisms that most modern Java interpreters provide.

In order to overcome the above mentioned problems, we decided to create a new version of JEOPS, with a new philosophy. Instead of doing the work of Java compilers and interpreters, JEOPS now works as a pre-compiler, that translates a rule base file into a java file that implements the inference engine, according to the rules of the original file.

In its new version, JEOPS is not a set of classes that emulated a production system in Java anymore. Its working philosophy has been changed. Instead of an API that could be used as any regular java class, JEOPS works now as a pre-compiler, translating a rule base into a java class that implements the rules in Java. It resembles how the famous grammar generator JavaCC works. With this new philosophy, its limitation of java types and expressions that can be used was dropped: in the previous version, only Object, int and boolean expressions could be used. Another limitation that disappeared was that now every Java piece of code can be used in the rule action part, while the former version allowed only method calls and (local) variable attribution. More details can be seen in the remaining of this manual.

Quick Description

JEOPS adds the power of production rules to Java (1.1.x and above). Production rules may be described as "condition-action" patterns, as they are expressed in our rule syntax. The system was designed based in two main ideas [Pachet, 1995]:

Any Java object can be matched in any JEOPS rule;
Any Java expression can be used in the condition and action parts of JEOPS rules.

These statements indicate that JEOPS respects the encapsulation of the objects, as one does not need to know the internal structure of an object to use it in a rule - method calls should be used instead. And using Java expressions in the rule definition, the time required for Java programmers to learn JEOPS is substantially minimized, due to the reduced "Impedance Mismatch", as occurs in other inference engines like CLIPS/C++ or JESS/Java.

Here is an example of a JEOPS rule, that says that "If a salesman is selling a product the customer needs, for a price the customer can pay, than the deal will be closed.". Supposing that Salesman, Customer and Product are Java classes, previously defined by the programmer (or even by third-parties), that rule base would be stated as follows:

/**
 * Simple rule for trading.
 */
rule trade {
  /* In this rule, one agent will buy a product from another agent. */
  declarations
    Salesman s;
    Customer c;
    Product p;
  conditions
    c.needs(p);  // he won't buy junk...
    s.owns(p);
    s.priceAskedFor(p) <= c.getMoney();
  actions
    s.sell(p);
    c.buy(p);
}

This rule can be read formally as "For any object s, instance of Salesman, for any c instance of Customer, and for any p, instance of Product, if the needs method call with parameter p for the object c returns true, the owns method call with parameter p for the object s returns true, and if the result of the invocation of the method priceAskedFor with parameter p in object s is less than or equals to the result of the method getMoney in the object c, then execute the methods sell and buy in objects s and c respectively with p as parameter". These methods must have been defined in the appropriate classes.

In other words, if there are objects in the knowledge base for the declarations, and all the expressions in the conditions evaluate to true when the variables are instantiated with those objects, then the body of the actions field will be executed.

JEOPS also takes object inheritance into account when choosing the objects to fire the rules. In this way, an object of class Chocolate, that is a subclass of Product, may also be used to make the conditions of the rule above true. Accordingly, if a declaration is of some interface type instead of a regular class, any object whose class implements that interface can be used.

What Is New

There have been many major changes in JEOPS from version 1 to version 2. This section tries to briefly present them, so that users of the previous version can have a taste of what's changed. For those who are just entering in JEOPS world, this section can always be useful as a good history book.

The main change occurred in the phylosophy of the system. As described before, JEOPS changed from an API for inference to a pre-compiler. Though the idea of the utilization of the knowledge base remained the same, the operational procedures have changed considerably. The "howto" will be explained later.

JEOPS 2 removes the restriction of the former version that only expressions containing int, boolean and Object subexpressions could be used. The only restriction that still remains is that arrays are not allowed in declarations. We plan though to remove it briefly. Without these restrictions, the following expressions are now valid in JEOPS.

		country.getUnemploymentRate() > 12.5;
		person.getMiddleInitial() == 'E';

Another new feature that was already mentioned is that this version allows the programmer to declare objects not only of class types, but of interface types as well. One could not expect it to be different, and we assumed that as a flaw in the original version.

Yet another restriction that was dropped was that the programmer could not directly access public fields of objects (only through methods). As a side effect, one can also access constant types defined by some interface. For instance, these expressions can now be used in rule actions.

		System.out.println("Hello world!");
		f.charAt(f.length() - 1) == File.separatorChar;

JEOPS 2 also supports import and package statements. The former is more a syntatic sugar, but as it is a part of Java language, we thought it would be useful. Package statements did not make sense in the first version, because the rules could be stored in any file. As rules now become classes, we felt the necessity to support this constructor.

As rule bases acquired the status of classes, it now makes sense to define both fields and methods in their bodies. The example of the 8-queens problem illustrates an use of a field of the rule base. It is used to count the number of solutions already found by the knowledge base, and is incremented at every new solution.

Rule Syntax

JEOPS rule bases can be written in any text editor. A rule base can be seen as a special kind of Java class, where one can define methods, attributes, and rules. Hence, the syntax of rule bases is very similar to that of regular classes. The only difference relies in the syntax used to define the rules.

The syntax of the rules, given in a simplified BNF, is the following:

Rule ::= "rule" "{" <Rule Body> "}"
Rule Body ::= <Declarations> <Local Declarations>? <Conditions> <Actions>
Declarations ::= "declarations" (<class name> <ident> ("," <ident>)* )*
Local Declarations ::= "localdecl" (<class name> <ident> "=" <expression>)*
Conditions ::= "conditions" (<expression>)*
Actions ::= (Action)+
Action ::= "assert" "(" <expression> ")"
         | "retract" "(" <expression> ")"
         | "modified" "(" <expression> ")"
         | <block>

where <expression> can be any valid expression of the Java language, and <block> can be any valid block of Java. The following rule exemplifies the structure given above:

rule walkInWumpusWorld {
  /* If the agent is in a room with a neighboring room that
     he knows is safe, then he should go to that room, if
     he hasn't visited it yet. */
  declarations
    agents.Agent archer;
  localdecl
    places.Room currPos = archer.getCurrentPosition();
    places.Room upperRoom = currPos.getUpperNeighbor();
  conditions
    upperRoom.isSafe();
    agent.hasNotVisited(upperRoom);
  actions
    agent.moveTo(upperRoom);
}

The local declaration section is used as abbreviation for long expressions. In the example above, for example, the expression archer.getCurrentPosition().getUpperNeighbor() could have been used instead of upperRoom in the condition and action sections. Another facet of the localDecl section will be explained later in the Modified Problem section.

The conditions section is formed by a series of boolean expressions. If all expressions evaluate to true for a given set of objects, then the rule is said to be firable, and is added to the conflict set, where one of the rules is chosen to be fired (which means to execute the statements of its action section).

In the actions section, as stated in the Quick Description, the user can write anything that could occur in a regular java method. In addition, three new constructs have been added to manipulate the objects stored in the knowledge base, which are assert (to include new objects in the object base), retract (to remove objects from the object base) and modified (to inform the engine that the internal state of an object has been modified).

A First Example: Fibonacci Numbers

As found in the user's manual of the NéOpus system, we'll begin with an example that shows the recursive effect of first order, forward chaining programming. Although it is an awfully inneficient algorithm for computing fibonacci numbers, it's a good benchmark for first order engines.

A class Fibonacci (inside the package jeops.examples.fibonacci) was defined with the following attributes:

An integer n - we want to calculate the n^th fibonacci value.
An integer value - the n^th fibonacci number, initially (-1).
Two Fibonacci sons - used for the recursive computation

The methods for accessing the fields in the Fibonacci class follow the JavaBeans conventions, i.e., for an integer field named value, there are two accessor methods, int getValue() and void setValue(int).

import jeops.examples.fibonacci.Fibonacci;

public ruleBase FibonacciBase {

  rule BaseCase {
    // if n == 1 or n == 0, then the value is n.
    declarations
      Fibonacci f;
    conditions
      f.getN() <= 1;
      f.getValue() == -1;
    actions
      f.setValue(f.getN());
      modified(f);   // Yes, I modified f
  }

  rule GoDown {
    // if n >= 2, create two sons for the object
    declarations
      Fibonacci f;
    conditions
      f.getValue() == -1;
      f.getN() >= 2;
      f.getSon1() == null;
    actions
      Fibonacci f1 = new Fibonacci(f.getN() - 1);
      Fibonacci f2 = new Fibonacci(f.getN() - 2);
      f.setSon1(f1);
      f.setSon2(f2);
      assert(f1);    // Let's tell our knowledge base
      assert(f2);    //   that these two sons exist.
      modified(f);
  }

  rule GoUp {
    // if both subproblems are solved, so let's solve this one
    declarations
      Fibonacci f;
    localdecl
      Fibonacci f1 = f.getSon1();
      Fibonacci f2 = f.getSon2();
    conditions
      f1 != null;
      f2 != null;
      f.getValue() == -1;
      f.getN() >= 2;
      f1.getValue() != -1;
      f2.getValue() != -1;
    actions
      f.setValue(f1.getValue() + f2.getValue());
      retract(f1);  // I don't need
      retract(f2);  //   them anymore...
      modified(f);
  }
}

The same idea may be used to solve other recursive functions, such as factorial or the Towers of Hanoi. This example, yet simple, is very good in showing the power (and simplicity) of the inference engine in dealing with this kind of problems.

In order to translate this rule base file into a Java file, so that it can be used in an application, the user must compile the rule base file. This compilation is performed by using the jeops.compiler.Main class, and it is shown in the following picture:

Going back to the example, assuming that the fibonacci rule base is stored in the file named FibonacciBase.rules, we can then compile the rules file into a java file. Before that, as we use the class Fibonacci inside the rules, we must first compile that class before compiling the rules:

javac jeops\examples\fibonacci\Fibonacci.java

After that, the command

java jeops.compiler.Main FibonacciBase.rules

will generate a file called FibonacciBase.java. This is the actual implementation of the knowledge base that is driven by the rules defined in the FibonacciBase.rules file. With that, one could define a simple program that used that knowledge base to reason about the fibonacci series, with a code that would be similar to that:

import jeops.examples.fibonacci.Fibonacci;

public class TestFibonacci {

  public static void main(java.lang.String[] args) {
    int n = Integer.parseInt(args[0]);

    Fibonacci f = new Fibonacci(n);
    FibonacciBase kb = new FibonacciBase();
    kb.assert(f);
    kb.run();
    System.out.println(f.getN() +
                "th number of the fibonacci series = " +
                f.getValue());

  }
}

As we can see, it is quite a simple task to invoke a knowledge base and put it to work. Here are the steps the above main method takes:

Here a Fibonacci object (as described before) is created. This is the object that is going to be inserted into the knowledge base for the reasoning. Its value can be defined in the command-line by the user.
A knowledge base is created in the same way as any other Java object...
In order to the inference engine be able to reason based on the object that was created, we must insert it into the knowledge base.
And now let the inference engine do its job...
As we still hold a reference to the object that was inserted into the base, we can use it to retrieve what it has "learned".

The last observation is probably the most important one: as we can insert our agent (the Fibonacci object) into the knowledge base, every modification that is made into that object as the rules are being fired are kept when the kb.run() method returns. In this way, retrieving the new information that the "agent" has learned becomes as simple as performing a method invocation.

Accessing the Working Memory

As could be seen in the previous example, there are two ways by which the working memory can be accessed by the programer. It can be done from outside the knowledge base or within the rules themselves.

In order to access the working memory from outside the knowledge base, there are four main methods defined in the class jeops.AbstractKnowledgeBase that allows the user to insert objects into, remove objects from the knowledge base, and to notify it of changes that happened in the object. These are the methods:

assert(Object): Inserts the given object into the knowledge base. The object (reference) is stored into the working memory, and the inference engine tries to match the declarations of the rules with the given object to verify if new elements can be added to the conflict set.
flush(): Removes all objects from the knowledge base. As a result, the working memory gets empty, as well as the conflict set (because there are no objects to be matched with the rule declarations).
modifiied(Object): Notifies the knowledge base that the given object has been modified. It is necessary because that modification can make the conditions of some rule to become true, and the inference engine needs to be notified to re-test that object with the rules. In the applications we have seen so far, the modified method is seldom used from outside the knowledge base: it is often used within the rules (as described below).
retract(Object): Removes the given object from the knowledge base. The (reference to the) object is removed from the working memory, and all the elements of the conflict set that used that object as one of the rule conditions are removed.

An example of this kind of access can be seen in the class TestFibonacci shown above. The Fibonacci object is asserted into the knowledge base via a simple method invocation.

Within the rules, the user can use the same methods as from outside the knowledge base to access the working memory. Several examples of this kind of utilization can be seen in the actions field of the rules BaseCase, GoUp and GoDown. As we have been doing in the whole system, we tried to make the rule body to resemble as much as possible to the Java world, so that the final result is a system that is easy to use.

A final remark on the retraction of objects from the knowledge base. For performance reasons, one should always free the working memory from the objects that are not needed anymore. In doing that, the inference engine will not have to test the matching of that object (and all its combinations with the remaining ones) with the rule conditions.

Internal Architecture

At this point, one can already use JEOPS for developping simple applications - more issues are presented in the remaining of this manual. Nevertheless, we think that it is time to open the heart of the system, so that the user can know more precisely what is going on "under the hoods". The picture below presents a simplified view of JEOPS architecture.

The picture above shows the main building blocks that make up JEOPS. The heart of the system (which is indeed the brain of the expert system that is using it) is the knowledge base. It is composed basically by three main blocks. The Object Base is the working memory, where the facts the agent knows are stored. The Rule Base, compiled from the (text) rule base file, is the place where all the information about the rules is stored, such as their declarations, conditions, actions, and several other control information. Finally, the conflict set is the meeting point between the rule and object bases. conflict set are stored the rules that can be fired at a certain moment in time, as well as the objects that have been matched to the rule declarations.

The object base is simply a collection of objects. It could be simply implemented as a Java Vector, but we decided to store the objects in a structure from where we could retrieve the objects of a given class in a more efficient way. Hence, the object base is implemented with a hashtable that maps fully-qualified names of the classes to the set of objects belonging to that class. With that, we can efficiently retrieve all objects that belong to a given class, which is necessary in the matching stage of the inference engine. The object base is also responsible for storing the inheritance relationships between the class of the objects stored in it, so that when the inference engine asks for all objects of class Person, it will return both the direct instances of this class and the instances of its subclasses (i.e., its indirect instances).

The rule base, compiled from the ".rules" file, is actually a subclass of jeops.AbstractRuleBase. This class defines methods so that the knowledge base can deal with all rule bases in the same way. These include methods for retrieving control information such as the number and names of the rules, for testing rule conditions and firing rules, given their indexes within the rule base.

Although we do not think that the information given above will be very valuable to the regular user, we presented it for the sake of the completeness of this manual. We think that only those interested in altering the system will be really interested in the inner structure of the rule and object base. In contrast, the inner details of the conflict set can be of a great help to the regular user, if there is the necessity of a different conflict resolution policy other than those already defined.

The conflict set depicted in the bottom right could also be drawn outside the box of the knowledge base - the user has the power of defining its own conflict resolution policy and use it in its knowledge base. It will be presented in more details in the Conflict Set section.

The knowledge base, that has the same name as the rule base defined in the .rules file, have two constructors. One of them has no parameters, and the other receives an instance of a ConflictSet. If the user does not specify which conflict resolution policy the system must use, JEOPS has a default policy (defined in the jeops.conflict.DefaultConflictSet class) to be used in this case. This policy does not provide any warranties at all about the conflict resolution method. It is the most efficient strategy, though, and it can be very useful in cases where conflict resolution is not a major concern.

The interation between the user and the knowledge base is performed by using the methods presented in the Working Memory section. The remaining method that is depicted in the architecture os the system is probably the most important one: run(). This is the method that, when invoked, puts the inference engine to work, reasoning on the objects of its working memory until the conflict set gets empty. This method was shown in the example of the fibonacci series.

To get information from the knowledge base, the agent can use the objects method to retrieve all the objects of a given class that are stored there. Another way of retrieving the information gathered during the execution of run method is to store the information needed in the internal state of the agent object, as done in the fibonacci example.

The Conflict Set

The conflict set of the knowledge base is like the warming up area for the batters in a baseball game. Over there, the players (or the rules) are waiting with their sticks (the set of objects that made that particular rule firable) just for the coach's calling. When called by the coach, the player go for the home base with their stick to try to hit a home run. In the same way, when invoked by the engine, the rule with its particular object matching tries to run (well, just as a batter doesn't always hit a home run, a rule may also fail to complete its task, by raising an exception - but with a very smaller frequence than not hitting a HR). Also, as a player might be warming up with more than one stick at a time, as well as the rule may be in the conflict set with more than one set of objects that make it firable. But when it's showtime, the player gets only one of his sticks to the field...

Well, this isn't exactly the reality, there is a certain order in which the players are called for the game. There is a certain policy the coach have to obey (according to the game rules) that prohibits him from calling, for example, the same player several times in a row when there are other ready players waiting for their moment in the field. In the same manner, you can define your own policy to make the engine decide by one rule or another.

In JEOPS, the user has the ability of choosing the conflict resolution policy to be used in the knowledge base. In most of the cases, the user will not need to use any complex policy, and the predefined classes will be enough. JEOPS has some predefined classes that implement different policies for choosing which rule is to be fired at any given moment. The predefined classes, all defined in the package jeops.conflict, are the following:

DefaultConflictSet: The conflict set used when none is specified. Its conflict resolution policy is not specified. In other words, any of the instantiations can be returned, and it was implemented to be as efficient as possible.
LRUConflictSet: A conflict set that will choose the least recently used rule. If there is more than one rule in the conflict set, it will choose one that was fired before the remaining ones.
MRUConflictSet: A conflict set that will choose the most recently used rule. If there is more than one rule in the conflict set, it will choose one that was fired after the remaining ones.
NaturalConflictSet: A conflict set that will not allow a rule to be fired more than once with the same objects. This conflict set requires a large amount of memory to store the history of rule firing, so it must be used with care. It also tends to get inefficient when the history grows.
OneShotConflictSet: A conflict set that will not allow a rule to be fired more than once, even for distict objects.
PriorityConflictSet: A conflict set that will give priorities to the rules. Rules defined first in the rule base file will have higher priorities than rules defined after that.

There are some cases, though, where these predefined policies are not enough for the application being developed. JEOPS allows the user to define the desired conflict resolution policy by creating a class that implements the methods defined by the interface jeops.conflict.ConflictSet. The required methods are the following:

void insertElement(ConflictSetElement): Inserts a rule instantiation, given a conflict set element that holds the rule index as well as the objects bound to the rule declarations.
ConflictSetElement nextElement(): Returns the next rule to be fired among those that have been inserted into the conflict set. It is performed according to the policy defined in the conflict set.
boolean isEmpty(): Checks whether the conflict set has any elements.
void flush(): Removes all rules instantiations from the conflict set, as well as cleaning any history that might have been stored.
void removeElementsWith(Object): Remove all elements from this set that uses the given object in its instantiations. This method is needed because if an object that was bound to some rule declaration is retracted from the working memory, that rule cannot be fired with that object anymore, so it must be removed from the conflict set.
Vector getModifiedObjects(Object)

In order to minimize the effort required for the creation of a new implementation of a conflict set, we have created a base class that provides many of the services required. This class, jeops.conflict.AbstractConflictSet, is a superclass of every conflict set implementation provided by JEOPS.

As there is no restriction on the implementation of the conflict set, the user can implement his/her own, based on the desired conflict resolution policy. This conflict set can then be passed to the constructor of the knowledge base.

For example, supposing we want the fibonacci example to use a different conflict set policy other than the default, we could use:

import jeops.conflict.PriorityConflictSet;
import jeops.examples.Fibonacci;

public class TestFibonacci {

  public static void main(java.lang.String[] args) {
    int n = Integer.parseInt(args[0]);

    Fibonacci f = new Fibonacci(n);
    FibonacciBase kb = new FibonacciBase(new PriorityConflictSet());
    kb.assert(f);
    kb.run();
    System.out.println(f.getN() +
                "th number of the fibonacci series = " +
                f.getValue());

  }
}

There is also another way of defining the conflict set policy for a knowledge base: the setConflictSet(ConflictSet) method of the knowledge base class can be invoked. It should not be used, though, when the knowledge base current conflict set is not empty, because it will loose its contents, causing unpredictable results. A knowledge base is guaranteed to have an empty conflict set after its creation, after a call to flush(), or after a natural exit from the run() method.

The Modified Problem

The integration of production rules in object-oriented systems brings the advantage of providing means of doing declarative programming, which is very useful for reasoning. Nevertheless, in order to be used in complex (i.e., real) applications, the production system must perform its task with a minimum of efficiency. Hence, it is not possible, at each inference cycle, to check every rule against every object. The solution is to check the rules only against objects that were inserted into, removed from or modified in the working memory. The first two conditions (insertion and deletion) can be checked easily. The last one is still an open issue (known as the Modified Problem, according to [Pachet, 1995]), because one cannot know when an object has been modified simply by looking at the methods that were invoked in it - objects are encapsulated entities. In this case, a notification mechanism must provided to the system be able to include the modified object in the matching process. And that is the funcion of the modified constructor of JEOPS.

However, this problem is not simply solved by this notification mechanism. Let us use the fibonacci example in the figure below to show how this problem may come to happen. The Fibonacci object in the left had been tried with the rule GoUp in some previous cycle, but as the value of the right object (its son1) was still undefined (i.e., -1), the object in the left could not be matched with the declaration of the rule GoUp. Eventually, the object in the right will have its value computed (when the rule GoUp fires for this object), and the inference engine will be notified of this change. However, the object of the left was also modified, and the system needs to be notified of this modification. This is what we call the "Transitive Modified Problem"

In JEOPS, we used the local declarations field as the place the user can give a hint to the system about the dependencies between the objects. Going back to the rule GoUp, by saying that the objects f1 and f2 are functions of the object f, then when there is a modification in one of the objects bound to f1 and f2, the object bound to f will also be marked as modified.

Sample Applications

We present now some sample applications developed using JEOPS. They are intended to both show the expressive power that can be obtained from JEOPS, and to further exemplify what has been shown in this manual. All the examples have been packaged with JEOPS, and they are stored in the packages jeops.examples.*.

Towers of Hanoi: A solution for the towers of hanoi problem, whose goal is to pass a certain amount of discs from one pin to another, obeying some restrictions.
The 8-Queens Problem: How to place 8 queens in a chess board, such as no queen can be attacked by the others?

Concluding Remarks

JEOPS is currently under development. In such way, we'd really appreciate to hear from you about problems, bugs, suggestions, features you would like to see in future versions, anything that you feel would help us in improving this product over and over. Please e-mail these comments/suggestions to me at csff@cin.ufpe.br. We hope you can find in JEOPS the tool you need for your application. Good luck!.

References

JavaCC, http://www.metamata.com/javacc/. Visited on April, 28, 2000.

Pachet, François (1995). On the embeddability of production rules in object-oriented languages. In Journal of Object-Oriented Programming, Vol. 8, n. 4, July/August 1995, pp. 19-24

This page was last updated by Carlos Figueira Filho on June 12^th, 2000.