Index of /~russell/aima-java/src/aima/logic
Conversion of logic/algorithms
Conversion of logic/algorithms
The http://kretek.cs.berkeley.edu/~aima-java/msb
directory contains a (work-in-progress) JAVA conversion of the LISP code
originally found in logic/algorithms. Currently only the unify
function has been translated. However, a lot of supporting code has
also been written which should speed up future translations.
The code has been put in the msb
subdirectory since my use of packages may be at odds with the current scheme
in use on kretek (I have no particular attachment to the scheme I came
up with.... tell me where this code
should really go, and I'll put it there). If you want to grab
the entire tree structure in one fell swoop, just download the gzip'ed,
tar file msbAIMA.tar.gz.
The DottedPair and Expression classes
The main problem in translating the unification code was in deciding the
data structure over which unification should occur. A choice was
made to unify over the same basic data structure types as in LISP, to provide
the same flexibility in pattern matching. This meant creating a new
class called DottedPair
which implements the functionality of LISP cons cells. Under this
scheme, JAVA Objects are considered as LISP-like atoms.
A LISP-like version of NIL, representing the empty list, was also implemented:
its value is retrieved by calling the static method DottedPair.getNull().
This special "NULL" object is not the JAVA null pointer, but is
a true DottedPair object, which like in LISP, has a first/car
and rest/cdr that is equal to itself. For convenience (see
the documentation) an additional Expression
class was defined which provides a set of static methods which operate
on arbitrary JAVA Objects. These routines apply runtime
casting, as appropriate, to invoke DottedPair
methods when the passed arguments are to be interpreted as compound
objects, but avoids such casting when the arguments are atomic in nature.
Since the DottedPair
and Expression
classes are fundamental, they were put in the aima.utilities
package.
The Variable, Bindings, and Unify classes
The code for unification is contained in static methods defined on the
Unify
class. These methods return an object of a class which implements
the Bindings
interface. Currently two implementations of the Bindings
interface exist: ListBindings
(an association-list implementation) and HashBindings
(A hashtable implementation). Depending on the application, one of these
two implementations may be more appropriate. To represent variables
in unification expressions, a Variable
class was defined. All of these classes and interfaces were put in
the aima.logic.algorithms
package.
Parsing
A parser analogous to the LISP read() function was defined on the Expression
class. A parser is also defined on the Unify
class which performs the additional action of converting atomic elements
(with the appropriate leading character.... currently the '?' character)
into Variable
instances in the resulting parsed expression.
Examples
The public static void main() method in most of the classes contains
code which tests out the class. So, just look at the main()
method to get a feel for how these classes work.
To Do....
Left to do:
-
Implement an infix parser to augment the prefix parser already written.
This infix parser would facilitate the entry of logical formulae.
-
Implement the routines to convert to CNF.
-
Implement the Horn-clause reasoning system.
-
Implement a resolution-based reasoning system.
-
"Beanify" those elements of this code that seem worthwhile to have as Javabeans.
Questions, comments? contact: Michael
Braverman