JEOPS - The Java Embedded Object Production System

User's Manual

Version: beta 1 - July 2, 1999
Author:
Carlos Figueira Filho


Table of Contents
Overview Quick Description
Rule Syntax A first example: fibonacci numbers
Accessing the working memory Putting it all together
Internal Architecture The Conflict Set
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, without whom this whole work would never had happened (thank's for struggling with the JavaCC, man!). 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.

Back to top

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]:
The first idea is extended to include also some of Java's primitive types (int and boolean), because of their importance in Java programming. In a future version of the system other primitive types will also be supported. The second one was restricted to a subset of the Java language in order for my group to finish our project in the time allowed by our professor. Also, this restriction may be dropped in a future version.

These statements indicate that JEOPS respects the encapsulation of the objects, as one doesn't 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. Supposing that Salesman, Customer and Product are Java classes, previously defined by the programmer, a rule that says that "If a salesman is selling a product the customer needs, for a price the customer can pay, that the deal will be closed."

rule trade {
  /* In this rule, one agent will buy a product from another agent. */
  declarations
    people.Salesman s;
    people.Customer c;
    products.Product p;
  preconditions
    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 also be read as "For any object s, instance of Salesman (a class defined in the package people, for any c instance of Customer (also defined in package people), and for any p instance of Product (that is defined in package products), 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.

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.

Back to top

Rule syntax

JEOPS rules can be written in any text editor. The rules used to create knowledge bases are stored in simple text files, so feel free to choose the editor that best fits to your likes.

The syntax of the rules, given in a simplified BNF, is the following:
Rule ::= "rule" "{" <Rule Body> "}"
Rule Body ::= <Declarations> <Local Declarations>? <Preconditions> <Actions>
Declarations ::= "declarations" (<class name> <ident> ("," <ident>)* )*
Local Declarations ::= "localdecl" (<class name> <ident> "=" <expression>)*
Preconditions ::= "preconditions" (<expression>)*
Actions ::= (Action)+
Action ::= "assert" "(" <expression> ")"
         | "retract" "(" <expression> ")"
         | "modified" "(" <expression> ")"
         | <expression>
where <expression> can be any expression in (our subset of) the Java language. 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();
  preconditions 
    upperRoom.isSafe();
    agent.hasNotVisited(upperRoom);
  actions
    agent.moveTo(upperRoom);
}
The local declaration section is only 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. We felt, though, that offering this facility to the user would be valuable for the usability of our system.

The preconditions 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 fireable, 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, all expressions in (our subset of) Java language can be used, such as method calls that may update the state of the objects. Also, 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 modify (to inform the engine that the internal state of an object has been modified).

Back to top

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 fibo) was defined with the following attributes:
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).

rule BaseCase {
  // if n == 1 or n == 0, then the value is n.
  declarations
    jeops.examples.Fibonacci f;
  preconditions
    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
    jeops.examples.Fibonacci f;
  preconditions
    f.getValue() == -1;
    f.getN() >= 2;
    f.getSon1() == null;
  actions
    jeops.examples.Fibonacci f1 = new jeops.examples.Fibonacci(f.getN() - 1);
    jeops.examples.Fibonacci f2 = new jeops.examples.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
    jeops.examples.Fibonacci f, f1, f2;
  preconditions
    f1 == f.getSon1();
    f2 == f.getSon2();
    f.getValue() == -1;
    f.getN() >= 2;
    f1 != null;
    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.

Back to top

Accessing the working memory

The working memory can also be accessed directly within the rules, as could be seen in the fibonacci example above. To include new objects within the actions block of a rule, you can use the assert statement, as seen in the GoDown rule. In this way,
assert(obj)
would insert the object represented by obj into the object base, and it would be available for firing the rules.

To remove objects that are no longer needed from the object base, you should use the retract statement, as in the rule GoUp. As you may have figured out,
retract(obj)
would remove the object represented by obj from the object base, and no rule would fire for that object anymore. For performance reasons, you should always dispose from your object base those objects that aren't needed anymore. That's because the inference engine won't have to try that object (and all its combinations with the remaining objects) for instantiating the rules.

When methods are invoked in objects in the rules, and they alter the state of them, these modifications are reflectes directly into the objects in the knowledge base. That's because the objects used in when the rules are fired are the same as those stored in the Knowledge Base (in RAL/C++ [Forgy, 1994], shadow objects are used in the "rules world"). Though, the inference engine must be informed that the object state was changed, so that the filtering mechanism knows that rules that were in the conflict set using that object might not be fireable anymore, and that rules which were not in the conflict set might become fireable by using that object.

We inform the engine that an object internal state has been altered through the modified statement. In this way, one the statement
modified(obj)
indicates that the object represented by obj has been modified by some action, so it should be reconsidered when firing the rules.

Back to top

Putting it all together

Well, we've seen how easy it is to define the rules, that the philosophy behind JEOPS is the best one in the world, but one point is still not clear: unless the Java language was changed last month and no one has told me, every java application must have a main method to run. And I don't intend to force Sun to change the language structure, so you still need a main to run any standalone program. So, where is it? Well, let's stop playing kid games here and go to the real work, at last.

Everything we've seen so far may have been a little new to you. If you managed to get to this point without running away of the JEOPS, congratulations! Unless you can't program in Java (which I think has very little chances to be true, since you're already trying to develop intelligent applications using this language - it would be a step too big for one's legs to go into Java directly into IA), you're now able to write any program using JEOPS. (Well, this is the commercial part; actually there is a little changing in your mind that must take place in order for you to begin thinking in terms of rules and objects, but it's nothing that time can't heal).

Enough of this crap by now. What we've seen is the way to tell the knowledge base how it is going to manipulate the objects it stores (through the rules definition). What is missing now is how we create the knowledge base so we can work with it. Let's get back to our fibonacci example. Below is a test class that is defined to use the rules as described above (assuming they're stored in a file called "fibo.rules"). The program below is everything you need to use the whole power of JEOPS to compute the numbers in fibonacci's series (I know, it is being very underused, but every language book starts with a Hello, world!, and I won't have the audacy to change this metodology).

import jeops.engine.KnowledgeBase;
import jeops.examples.Fibonacci;

/**
 * A test class for the best inference engine for Java.
 *
 * @author Carlos Figueira Filho <a href="mailto:csff@di.ufpe.br"
 *          >csff@di.ufpe.br</a>
 * @version 1.0   09 May 1999
 */
public class TestFibo {
    public static void main(String args[]) {
1        Fibonacci f = new Fibonacci(6);  // What is the 6th
                                          // element of the series?
2        KnowledgeBase kb = new KnowledgeBase("fibo.rules");
3        kb.assert(f);
4        kb.run();
5        System.out.println("fibo(6) = " + f.getValue());
    }
}
Wow! Now that the worst has been gone, to actually use the system doesn't seem to be a hard task... And it is really that easy to use. Here are the steps the program above takes:
  1. Here we create the (only) object that is going to be inserted into the knowledge base. For this example, it's a Fibonacci object (as defined before) with the n field initialized to 6.
  2. Meet JEOPS knowledge base. It's constructor receives the name of the file that contains the rules.
  3. In order to the inference engine be able to work with the fibo object we've just created (in step 1), it must be inserted into the knowledge base.
  4. And now let the engine do it's job...
  5. 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 fibo 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 a method invocation.

Before we move any further, I think it is valuable to present some inside information about JEOPS, so that you'll be able to fully understand how it works.

Back to top

Internal Architecture

By now, no one doubts that JEOPS is a good shot anymore. But how does it work from inside? I think now would be a good time to present it so that once you understand its inner structure, you won't be so suspicious about how the magic happens.

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. Its left ventricle, where the facts the agent knows are stored, is the Object Base, and we shall call the right ventricle Rule Base. Together, they work helping the heart to beat as it should. (for those of you who have a minimum knowledge about human anatomy, sorry if I made a mistake; I may be very good at programming, but my biology skills are close to nothing, I just thought this analogy could help). But as the heart needs a brain to command it (as involuntary actions, which we don't know - nor need to - how it happens). And that's exactly what the JEOPS engine does: working under the covers, you don't have to worry about object matching, rule compilation, among other things. But as I've promised, here's this let's lift the covers and present JEOPS as it came to the world...

The conflict set depicted in the bottom of the knowledge base is the meeting point between the rule and object bases. In the 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. Actually, only referenced to the objects in the object base are stored in the conflict set. I'll go back to the conflict set a little later.

The knowledge base is created by passing to its constructor the name of the file that contains the rule definitions, as shown before in the fibonacci example. When created, its object base is initially empty. Eventually, you may also pass a Rule Sorter to the constructor, that will define the policy the engine will use to choose which rule to fire. I'll return to this point in the conflict set section.

The assert method is used to add new objects to the knowledge base. When an object is added, the engine searches the rules in its rule base to see if that object can make it fireable (possibly using the other objects previously stored in the object base). If there is such a rule, it is added to the conflict set.

When you've put all objects you want the base (the previous knowledge of the agent), issuing the run method starts the whole magic: as long as there are rules in the conflict set, the engine keeps firing those rules.In other words, as long as there is something for the agents (represented by the objects) to learn, JEOPS guarantees that they indeed will learn those things.

To get information from the knowledge base, the agent can use the objects method to retrieve all 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 knowledge base interface still defined two other methods: retract and flush. The first one can be used to remove a given object from the knowledge base, and the latter removes all objects from the base.

Back to top

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 fireable) 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 fireable. 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.

JEOPS has some predefined classes that implement different policies for choosing which rule is to be fired at any given moment. The predefined classes (a.k.a. Rule Sorters) are:

  • DefaultRuleSorter
    The default rule sorter used in the inference engine when no other one is specified. This sorter doesn't specify any particular ordering for the rules, and it will return (probably) the first fireable rule it can find.
  • LRURuleSorter
    A rule sorter that will fire the least recently used rule. If there is more than one rule in the conflict set, the engine will choose one rule that was fired longer before than the others.
  • MRURuleSorter
    A rule sorter that will fire the most recently used rule. It's the opposite of the last one, where some rule might be fired over and over if there are objects that match its declarations and evaluate its preconditions to true.
  • OneShotRuleSorter
    A rule sorter that won't allow the same rule be fired more than once, no matter which objects have been chosen to match its declarations.
  • PriorityRuleSorter
    A rule sorter that will choose the rule with a higher prioriry than another with a lower priority. The priority of a rule is defined by the order it appears in the rule file.
  • The conflict resolution policy is defined using the setRuleSorter(RuleSorter) method in the knowledge base. This method should be invoked only when there are no objects in the current conflict set, or they can be lost and the result of a call to the run() method can be impredictable. As a rule of thumb, you can assume that the conflict set is empty after the initialization of the knowledge base, or either after the flush() method has been called, or right after a successful call to run().

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

    1        Fibonacci f = new Fibonacci(6);  // What is the 6th
                                              // element of the series?
    2        KnowledgeBase kb = new KnowledgeBase("fibo.rules");
    2.5      kb.setRuleSorter(new jeops.engine.MRURuleSorter());
    3        kb.assert(f);
    4        kb.run();
    5        System.out.println("fibo(6) = " + f.getValue());
    

    Back to top

    Concluding Remarks

    JEOPS is currently under development. In such way, we'd really appreciate to hear from you about problems, bugs, suggestions, features you'd 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@di.ufpe.br. We hope you can find in JEOPS the tool you need for your application. Good luck!.

    Back to top

    References

  • Forgy, C. (1994). RAL/C and RAL/C++: Rule-Based extensions to C and C++. In Proceedings of the OOPSLA'94 workshop on Embedded Object-Oriented Production Systems (EOOPS). Paris: Laforia
  • JDK(TM) 1.1.x Documentation, http://java.sun.com/products/jdk/1.1/docs.html. Visited on March, 28, 1999.
  • Pachet, François (1995). NéOpus User's Guide. Paris: Laforia


    This page was last updated by Carlos Figueira Filho on February 5th, 2000.