JARE - Java Automated Reasoning Engine

Dr. Thomas R. Ioerger


Table of Contents

  1. Introduction
  2. Syntax of Jare Language
  3. Using JareShell
  4. List of Features
  5. Calling Jare from Java
  6. How Jare Works
  7. Example: Tic Tac Toe

Introduction

Jare is an environment for doing logical inference in Java. In Jare a knowledge base can be encoded in the form of first-order Horn clauses. The inference engine itself is based on back-chaining. Jare serves a similar purpose to Jess. However, in comparison, Jare's knowledge representation is little more restrictive (e.g. no templates, no assert/retract actions), and its inference engine makes different efficiency tradeoffs that the forward-chaining Rete engine used by Jess. In actuality, it is much more like Prolog.

The current source code for Jare is here:

(Note: as of v1.8, Jare moved its parser code into JareParser class (from JareCommon), and made utility functions static. They can be called by prefixing "J.", a wrapper class. Also, Jare now throws exceptions on parse errors.)

The tar file contains some java files and a makefile, along with some installation notes and accessory files. Untar it and read the README and INSTALL files. There are four main files worth mentioning:

Jare is currently NOT public-domain software; a license must explicitly be obtained from the developer, Tom Ioerger (ioerger@cs.tamu.edu). Jare is only intended to be used for internal research projects at TAMU.

Jare was developed using JDK 1.2.1 on Solaris (2.7), though it should work in other environments. To run the shell, type the following command in Unix:

 
java Jare.JareShell sample.kb
where sample.kb is any knowledge base file conforming to Jare syntax. As an example, see this sample.kb.


Syntax of Jare Language

Jare uses a LISP-oriented syntax, with nested lists (lots of parentheses) and infix notation (where the first element in each list is often the name of a predicate, and operator, etc.). Capitalization and white-spaces generally do not matter. Comments are indicated by semi-colons (';'), which cause disregard of all the remaining characters on the line. (see sample.kb)

The basic unit of expression in Jare is a predicate. As is first-order logic, predicates have a predicate name followed by a list of arguments, called terms. However, the predicate name is written inside the parentheses as the first member of the list. Terms can either be constants (symbols or numbers), variables, or functions. Variables are indicated by symbols prefixed with a '?', such as ?x or ?temp. Functions are like predicates, in that they are lists with function names and arguments, though they occur as arguments inside other functions or predicates. Here are some examples:

Predicates can also be negated by enclosing them in another list, whose first element is 'not'. Predicates and negations of predicates together are called "literals." Predicates without negations are sometimes called "positive literals," while negated predicates are sometimes referred to as "negative literals."
     (not (warm december)) - a negative literal
Sentences in Jare are based on Horn clauses, which are made out of one or more predicates. When a Horn clause contains a single literal, it acts as a fact (note, it has an extra set of enclosing parentheses). Facts by themselves cannot be negated. Here are examples of two facts:
     ((warm july))
     ((cold december))
When 2 or more literals are included, the Horn clauses can be read as a rule. Specifically, the first literal is known as the "head" (or consequent) of the rule, and remaining literals are called the "body" (or antecedents). A rule can be understood by reading in a "backwards" way by saying "if" after the head. For example, consider the following rule, which says that something is a good deal IF it has high quality and a low price:
     ((good-deal ?x) (quality ?x high) (price ?x low)) 
The antecedents are implicitly conjoined ("and-ed" together). There is no way to encode disjunction (except that multiple rules are alternatives to each other). The head of each rule must be a positive literal, but any of the other members of the clause (antecedents) may be negated. Note that there are no quantifiers; any variables are assumed to be universally quantified (read: forall).

It is of central importance that the head of each clause be a positive literal (i.e. does not contain 'not'). In particular, facts must always be positive literals.


Using JareShell

Here is a brief list of commands you can run in the shell: Here is a transcript of a Jare session showing examples of several queries on the sample knowledge base:
[dilbert]# java Jare.JareShell sample.kb
Welcome to JARE - Java Automated Reasoning Engine
Dr. Thomas R. Ioerger, Copyright 2000
Version 1.6 (11/10/00)
Type 'quit' to exit.

reading: list.kb
reading: sample.kb
>(query (dog fido))
((dog fido))

>(query (cat fido))
fail

>(query (animal fido))
((animal fido))

>(query (animal ?a))
((animal fido))
((animal fifi))
((animal tweety))
((animal opus))

>(assert (dog rex))
asserting: [dog, rex]

>(assert (dog poochie))
asserting: [dog, poochie]

>(retract (bird ?x))
retracting: [bird, ?x]

>(query (animal ?a))
((animal fido))
((animal fifi))
((animal rex))
((animal poochie))

>quit
[dilbert]#
Commands that I would like to add in the future are:


List of Features

In this section, I discuss several important features implemented in Jare. The first is negation. While technically, Horn clauses are not supposed to contain negative literals, Jare allows antecedents in a rule to be negated. Syntactically, a negative literal is written by enclosing a predicate in another list with 'not' as the prefix (an example is shown above). The semantics of negation is handled exactly like Prolog: through negation-as-failure. That is, an antecedent (not (P)) is found to be true exactly when (P) cannot be proved. Jare recursively starts a new search for a proof of (P), and then continues the original proof if and only if no solution for (P) is found. Note that the proof of (P) is carried out in the current binding environment (with current substitutions), but the fact that the original proof proceeds only if the proof of (P) fails means that the binding environment itself will not be modified. As an example, here is a rule with a negative antecedent. It says that something is a week-day if it is a day but not a weekend. Days could be 7 facts enumerating Sat, Sun, Mon, .... Each will be tried, but those that satisfy weekend (i.e. Sat and Sun) will be filtered out as solutions.
((week-day ?x) (day ?x) (not (weekend ?x)))
The next major feature of Jare is procedural attachments. Procedural attachments are predicates with special pre-defined meanings that are essentially implemented in Jave code. Currently, there are two classes of procedural attachments: math operations, and list operations.

Math operations include two types: relations (e.g. equality) and functions (e.g. +). Relations are generally 2-argument predicates. Both arguments must be bound (i.e. you can't evaluate a relation on a free variable; Jare will signal an error if you try), and both arguments must be numeric. Here is a list of relational predicates:

Straight inequality may be implemented as: (not (= ?x ?y)). Note: Jare attempts to convert anything that begins with a +, -, ., or digit into a float, and math operations are carried out on these (so 6.0 and 6 are equal). (However, +, -, and ., may still be used as symbols themselves.) The predicate 'eq' can be used for comparing equality of symbols.

Math functions generally take 3 arguments. They can be used to verify relations if all 3 args are bound, or any one of the three may be left unbound and Jare will fill in the answer (expect mod and pow, for which only the third argument can be unbound). The implemented math functions are:

Here are some examples of using these math predicates:
>(query (+ 1 2 3))
((+ 1 2 3))

>(query (+ 2 3 ?x))
((+ 2 3 5.0))

>(query (+ 3 ?x 4))
((+ 3 1.0 4))

>(query (mod 9 4 ?x))
((mod 9 4 1.0))
Another class of procedural attachments are provided for support of list operations. In Jare, lists can be represented as terms within predicates by using a special function 'list' that can have any length. For example, the list of a, b, and c, is (list a b c), and the empty list is just (list). Currently, procedural attachments are provided only for basic operations, such as 'cons', 'first', and 'rest'. These allow you to construct and deconstruct lists. Then a larger set of additional list predicates is defined over this through axioms in list.kb, which is automatically loaded into Jare on startup.

Cons works as follows. You must give it an object and a list, and it returns a new list with the object stuck in the front. Hence cons takes a total of 3 arguments. If the 3rd argument is bound, cons verifies its correctness (i.e. succeeds if it is correct, else fails). More interestingly, if the 3rd arg is unbound, Jare binds the answer (new list) to it. First and Rest extract the corresponding elements from a list, returning an object or a list, respectively. Again, if the second argument is bound, its correctness is checked, else the variable is bound to the answer. Here are the basic list predicates with examples:

(Yes, I know: a more elegant solution would have been to allow cons to accept an unbound argument for any of the 3 positions, so that it alone would have to be pre-defined, and First and Rest could be derived from it through axioms.) The additional list predicates defined through axioms include: Generally, only the last argument can be unbound for these predicates.

Some other important procedural attachments that I have not implemented yet but would eventually like to are: (rand ?x), and type predicates such as (numberp ?x). Other useful math predicates would be: sqrt, log, exp, and round... For lists, I would like to add intersect.


Calling Jare from Java

Although an interactive shell is provided with Jare, it can be invoked to do inference from any Java program. It should be noted that the current code is setup to be in package 'Jare'. So in your other programs, you might want to "import Jare.*;". However, if you don't want to use packages, you can just comment the package statements out. If you want to use the utilities in the class JareCommon, you can extend your program classes from it. This is especially useful for inheriting functions such as 'parse'.

Here are the basic steps for calling Jare from Java:

  1. JareEngine engine = new JareEngine();
  2. engine.readKBfile("file.kb");
  3. Vector Q = parse("(avg-temp houston winter ?x)");
  4. JareEnv solution = engine.query(Q);
  5. System.out.println("?x = "+(String)solution.lookup("?x"));
  6. System.out.println(treeToString(solution.subst(Q));
  7. solution = engine.next(); ... Here is what is going on. The first two lines create a new engine and initialize it by reading in a knowledge base (file with Horn clauses in syntax described above). Lines 3 and 4 are the heart of the procedure. To make queries to Jare, they must first be converted from strings into Vectors (actually, nested vectors, i.e. trees), which can be done by the parse() method in JareCommon. This vector-representation of the query string is then passed to the engine via the query() function, which returns a environment containing a variable binding list from the first proof it finds (or null, if the query is false). You can lookup values for specific variables in the environment (as shown on line 5). Also, a very common use is to be able to apply solutions to the original query to substitute in the values for any bound variables, and then print it out (which requires converting from a vector back to a string, using the treeToString() function in JareCommon). Finally, additional solutions may be retreived by calling next(), which simply picks up the back-tracking search for more proofs (of the query) where it left off (will return null when no more solutions are left).

    There are various other things you can do, such as bind variables to values in environments, retract clauses from engines, etc.


    How Jare Works


    Example: Tic Tac Toe

    To demonstrate the capabilities of Jare, I have made up a knowledge base (tictactoe.kb) that allows it to play tic tac toe. The point of this is to give an example of how backward-chaining inference can be used to make non-trivial decisions, such as would be necessary of an intelligent agent sensing the state of its environment and taking actions to achieve its goals. Of course, tic tac toe can be implemented in many other ways; this is just a very different programming model.

    In this implementation, we represent tic tac toe boards using a list of 3 lists of rows. Pieces are representated as 'x' (for player), 'o' (for computer), and '-' (for empty). The rows are list from top down. So for example, '(list (list - - x) (list - o -) (list x o x))' represents the following board:

        - - x
        - o -
        x o x
    
    The top-level function that plays the game is 'move'. This is a binary predicate that takes a board as an input argument, and returns a new board with the computer's move as an output argument. For example:
    >(query (move (list (list - - x) (list - o -) (list x o x)) ?b))
    ((move (list (list - - x) (list - o -) (list x o x)) 
           (list (list - o x) (list - o -) (list x o x))))
    
    After the query is submitted and the solution is returned, the shell prints out the query with any resulting substitutions in the environment, e.g. the new board for ?b. In this case, the computer has found a move that wins the game, by placing a piece in the top row:
        - o x
        - o -
        x o x
    
    The Move predicate serves two essential functions as an interface. First, it does some legality checking. For example, it makes sure that the input board has 3 rows of 3 pieces, and that the number of player's and computer's pieces differ by at most 1. Also, it checks to see whose turn it is, and whether either player has won. Then Move goes through the following decision-making process:
    1. if the opposing player is in a position to win (i.e. has two in a row/col/diag with a blank), the computer must block it
    2. else if the computer can win, it puts a piece there
    3. else if the board is empty, the computer selects the center square
    4. else it tries to setup for a win by getting two in a row (not implemented)
    5. else it picks the center square if it is open anyway
    6. else it makes a 'random' move (just search for an empty space in linear order, for now)
    This cascade of decisions is implemented through various clauses for defining the Move predicate. As with Prolog and other such real-world implementations of theorem-provers, the clauses are searched in order from top-down until one matches for which a proof can be completed. Hence it is important to list the clauses in the same order as the decisions above.