////////////////////////////////////////////////////// // // XProlog.java: the successor to Winikoff's WProlog // ================================================= // Latest version v.1.4 (Feb 2003) // // Author: Jean Vaucher // Email: vaucher@iro.umontreal.ca // URL: www.iro.umontreal.ca/~vaucher/XProlog/ // // ZIP of all files: www.iro.umontreal.ca/~vaucher/XProlog/XProlog.zip // ------------------------------------------------------------------- // // This Prolog was developped to be used the handle the knowledge // and reasoning needs of Java based Agents. It should be reasonably // fast and compact so that every agent could have its own KB and // inference engine. // // Initially, we tried several "freeware" Prologs available on the web. // Winikoff's WProlog turned out to be not only to be easy to use but also // remarkably fast. However, it was weak in several areas: // - no assert/retract // - no arithmetic // - primitive syntax with no operators... not even the cut "!" // - wasteful of memory // // Our solution was to start with WProlog and to replace, modify and add parts // as required. The result is "XProlog". // // XProlog seems a happy conpromise between simplicity and efficiency and it has // been used several times as a starting point for extensions. // // Third party extentions: | | YProlog: Boris van Schooten, University of Twente (2005) | URL: wwwhome.cs.utwente.nl/~schooten/yprolog/ | | Improved the database: functionality, efficiency | & easier access from Java Programs | // ------------------ Modification History ---------------------------- // // Feb 2003 - v.1.4 (J. Vaucher) // // - Noted that "print", "println" and "nl" exist in README // // May 2002 - v.1.3 (J. Vaucher) // - added OR: ( a,b,c... ; c,d,e) // - and IF: ( a,b -> c,d ; e,f) or ( -> true_part) // - sequences: ( a ,b c, d ) // // May 2002 - v.1.2 (J. Vaucher) // // - Added predicates to allow communication between multiple // Prolog engines: self, send, receive, broadcast... (see below) // - Corrected some bugs where "is", "send" etc would fail // when used inside rules because the code for binding variables // and testing wether variables were bound didn't follow the "ref" // chains to the ends. // - Added debugging aids. When "stepping" you can answer "s" to // skip over a goal or "q" to quit stepping. // // Version 1.0 (april 2002) // - changed Parser to use one generated by JavaCC // - implemented the CUT (and "!" operator) // - added assert/retract // - added step/trace // - added integer arithmetic: +, -, *, /, % // and comparisons: ==, !=, >, <, >=, =< // - reduced memory use and improved running speed about x2 - x3 // // Current weakness: // 1) the Applet interface was removed. // 2) you can't define new OPERATORS // // ------------------------------------------------------------------ // WProlog : the original software by Michael Winikoff // URL: http://goanna.cs.rmit.edu.au/~winikoff/wp/ // // Version 1.0: 27/9/96 - 16/10/96 // Version 1.1: 20 January 1997 // Version 1.2: 2 April 1997 // Version 1.2.1: 19 August 1999 (fixed bug with unification of variable // to itself. ///////////////////////////////////////////////////////////////// Quick introduction =================== 1) Download and unzip the ZIP file from: www.iro.umontreal.ca/~vaucher/XProlog/XProlog.zip % unzip XProlog 2) Look at Prolog examples: - util.pro : which contains the classic "append" and "member" predicates - path.pro : my benchmark program; depth-first exploration of maze. 3) Try XProlog with "util.pro". Start XProlog and load the file % java -jar XProlog.jar util.pro - List the predicates [Note: in the examples below, DON'T type the prompt "?-" ] ?- listing. ?- listing(full). % to see the loaded primitives - try unifications. ?- X = t(1,fred). ?- t(_,X) = t(1,fred). ?- X=t(1,fred), X=t(Z,Z). % should fail - try "append" ?- append( A,B, [red,white,blue]). % answer "y" to get more answers - try "member" ?- member( Num, [1,2,3,5,7,8,22,17]), Num>4, Num<10. - add facts and list them ?- member( W, [marie,helen,jane]), assert( woman(W)), fail. ?- listing( woman(_)). ?- woman(jane). ?- woman(sue). % should fail - Benchmark program: load it then try it. ?- consult( 'path.pro'). ?- solve(p(8,8),L). % if this work in 5 sec or less, ?- solve(p(2,2),L). % try this - Quit. ?- quit. Operation ========= All the classes are in the XProlog.jar file. You can start operation with: % java -jar XProlog.jar Optionally, you can specify a Prolog file to be consulted on start-up: % java -jar XProlog.jar path.pro if you wish to recompile and execute: % javac *java % java Go path.pro The jar file was built as follows: % jar cmf manifest XProlog.jar *class XPROLOG syntax and primitives ============================== Generally conforms to Edinburgh Prolog notation. Atoms: identifiers starting with lower case letter (i.e. red, green ) string within single quotes (ie. 'path.pro' ) [ Useful to consult files ] Integers: like 123 or 0003 Variables: identifiers starting with capital letter ( X, Yes ) or '_' [Note: each '_' stands for a different variable] Lists: [] or [1,2,3] or [1,2,3 | Tail ] Comments: anything starting with the "%" character to the END-OF-LINE Primitives =========== These cannot be redefined by the user. Debugging --------- * trace and notrace : to turn on and off a minimal trace facility * step / nostep : to turn on and off the step mode. In step mode, you can answer "s" (skip) to avoid detailled tracing of a goal or "q" to drop out of step/trace or "a" to abort. Basic ----- > true : goal which always succeeds. > fail : always fails. Note: other unknown predicate also fail but in "trace" mode, those predicates provoke a special error message; not so with 'fail'. > = : unification operator ( X=t(_,_) ) > ! : the CUT operator > call(X)... or simply X : try to reduce the X goal > not( X ) : suceeds if X fails > var(X) : succeeds if X is not bound to any constant; and can thus be unified with anything > quit : end the program Output ------- > print( X ) : converts X to String and prints it > nl : skips to next line > println( X ) : ...obvious... Control predicates ------------------ IF: ( -> ; ) ( -> ) where , and are all sequences of goals. Behaves like IF...THEN...ELSE... or IF...THEN... OR: ( ; ) Knowledge Base -------------- * consult( File ): reads in predicate definitions from "File". The new definitions overide old definitions * assert( Term ) * asserta(Term) : usual meaning. Only works for facts not for rules. * retract( Term ): retracts first matching fact... and others on backtracking. * retractall( functor/arity ): retracts all clauses * listing : prints "user" facts and rules in the knowledge base * listing(full) : prints "primitive" predicates as well * listing( F/N ): prints clauses with Functor "F" and arity "N" Get/Set (not standard Prolog) ------------------------------- These predicates implement "variables": * set( Name, Value) adds an entry to the database with Name = Value and * get( Name, X ) will retrieve the value of "Name" and seek to unify it with X Example: set(a,1), ..., get(a,A),... Note 1: setting a new value for "name" wipes out the old value Note 2: both Name and Value can be terms of any complexity; the printable String of the "name" term is used as the Key to the database [and should not contains free variables] This could be used to implement an arrays with O(1) access time as follows: X=13, Y=40, set( p(X,Y), -1) ,..... get( p(13,40), VAL), ..... Arithmetic ---------- Works with "long" integers. The operators are: +,-,*,/ and mod. Arithmetic expressions can include integer, variables bound to integers and "rnd()" which returns a random integer between 0 and . Arithmetic expressions are evaluated as operands of comparison operators and as the RHS of "is" the assignment operator. Comparison operators do not necessarily match those of standard Prolog. They are: == (equal), != (not equal), >,<, >= and <=. Examples: X is 3*2+rnd(100), X >= (Y*10+1) mod 3, ... Agent Communication =================== XProlog allows multiple agent "engines" to be created. XProlog assigns each engine an identifier and allows messages to be sent from one agent to another. To implement this, we provide each engine with an input queue for terms which serve as "messages" as well as a central "PostOffice" which keeps pointers to the input queues of each agent. The following predicates are provided: - self( ID ) : returns in ID the agent identifier (an integer) - send( Dest, Message) : puts a copy of the term "Message" on the input queue of agent with integer identifier Dest. - broadcast( M ) - shout(M) sends message M to every agent except sender - receive( Src, M ): removes first message off the queue if there is one, fails otherwise. Then unifies "Src" and "M" with the source and content of the message. If either unification fails, the message is lost. - dumpq : prints out the contents of the queue. Agent example ============= The java program "Play.java" is an example of a MAIN program for two agents. It assumes two Prolog agents whose programmes files are given as parameters. The first being the "environment"; the second is an 'explorer' which learns about its environment by trying to move and being informed of the results (move or bumping into something). Play first calls the "init" predicate of the first agent then in turn calls the "go" predicate of each agent 65 times. In the end it asks the explorer agent to list its database and exits. To see it as work try: % java -cp XProlog.jar Play robot_env.pro robot.pro xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx FILES ======= Archives -------- - XProlog.zip - Contains ALL that follows - XProlog.jar - All the 'class' files and a "manifest" to automatically start the class "Go" Prolog examples --------------- - util.pro : Prolog file with the classic "append" and "member" predicates - path.pro : my benchmark program; depth-first exploration of maze. Prolog Engine ------------- - XProlog.java - The "Engine" class for executing queries - Term.java - classes which represent the terms, goals and lists - KnowledgeBase.java - Augmented Hashtable to store the rules and facts - Go.java - Main program creates a Prolog engine and interfaces with the user Parser stuff ------------ - Prolog.jj : The grammar description from which JavaCC generates the following files - Parser.java - ParserConstants.java - ParserTokenManager.java JavaCC Utility files -------------------- SimpleCharStream.java Token.java ParseException.java TokenMgrError.java Agent files ------------ - Play.java: main program - robot_env.pro: a Prolog program acting as the environment - robot.pro : an explorer robot JavaCC: ====== JavaCC is a compiler compiler initially developped by Sun which we use to generate the Prolog Lexer and Parser. If you want to modify the syntax easily, you will have to get JavaCC. Available from: http://www.webgain.com/products/java_cc/ Otherwise just use (or alter) the provided source files. The input to JavaCC is the file "Prolog.jj". Generation, once javaCC is installed is done by executing: % javacc Prolog.jj This creates three Java files which depend on Prolog.jj Parser.java ParserConstants.java ParserTokenManager.java and copies in to the directory 4 general files SimpleCharStream.java Token.java ParseException.java TokenMgrError.java Once all have been compiled: "javac *java", changes to Prolog.jj only require recompiling of the first three, which can be done with: "javac Parser*java"