JARE - Java Automated Reasoning Engine
Dr. Thomas R. Ioerger
Table of Contents
- Introduction
- Syntax of Jare Language
- Using JareShell
- List of Features
- Calling Jare from Java
- How Jare Works
- 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:
- JareEngine.java - implements back-chaining and procedural attachments
- JareCommon.java - common base class that contains utility routines (includes parser)
*** changed to JareParser.java as of v1.8 ***
- JareEnv.java - implements variable binding environments via hashtables (includes unifier)
- JareShell.java - a interactive command-line prompt for typing in queries
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:
- (teaches bill ai-course)
- (has-phd bill)
- (sister judy ?sis)
- (loves jude (mother-of judy)) - loves is a predicate, mother-of is a function
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:
- quit - exits JareShell - note: no parentheses
- (query conjunction) - finds all solutions and prints out query with each set of bindings
- (query-all conjunction) - same as query
- (query-one conjunction) - finds first solution and prints out query with bindings substituted in
- (set-trace on/off) - prints out goal stack and binding environment with each iteration
- (assert predicate) - adds fact to knowledge base
- (retract predicate) - retracts ALL clauses whose head unifies with given
predicate (may have constants and/or variables)
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:
- (bind ?x 5) - bind values to variables in the global environment
- (load filename) - reads in new clauses and adds them to the KB
- (show) all rules, or those matching a predicate name?
- (next) - for after (query-one)
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:
- (= ?x ?y)
- (< ?x ?y)
- (> ?x ?y)
- (<= ?x ?y)
- (>= ?x ?y)
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:
- (+ ?x ?y ?z)
- (- ?x ?y ?z)
- (* ?x ?y ?z)
- (/ ?x ?y ?z)
- (mod ?x ?y ?z)
- (pow ?x ?y ?z)
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:
- (cons ?x ?y ?z) - (cons x (list a b) (list x a b))
- (first ?x ?y) - (first (list x a b) x)
- (rest ?x ?y) - (rest (list x a b) (list a b)
(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:
- (empty ?x)
- (length ?x ?n)
- (nth ?x ?n ?y) - ?n is the position, starts counting from 0
- (second ?x ?y)
- (third ?x ?y)
- (member ?x ?y) - checks to see if ?x is in the list ?y
- (reverse ?x ?y)
- (append ?x ?y ?z) - e.g. (append (list 1 2) (list a b) (list 1 2 a b))
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:
- JareEngine engine = new JareEngine();
- engine.readKBfile("file.kb");
- Vector Q = parse("(avg-temp houston winter ?x)");
- JareEnv solution = engine.query(Q);
- System.out.println("?x = "+(String)solution.lookup("?x"));
- System.out.println(treeToString(solution.subst(Q));
- 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
- Parsing
- Unification
- Binding Environments
- Back-chaining
- Negation
- Saving Search State
- Procedural Attachments
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:
- 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
- else if the computer can win, it puts a piece there
- else if the board is empty, the computer selects the center square
- else it tries to setup for a win by getting two in a row (not implemented)
- else it picks the center square if it is open anyway
- 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.