Section 1 - General notes Section 2 - Querying Section 3 - Some code syntax Section 4 - Using Prolog under Unix Section 5 - Explanation of some Prolog code ****************************************************************** Section 1 - General notes The files can loaded into the interperter from the prompt " ?- " with the consult directive. It's format is consult(filename). There are no quotes used. Don't forget the period. If you don't have the file in the same directory as the Prolog interperter you can direct the interperter to look for the file in a directory by enclosing it with single quotes. ex : ?- consult(family). ex : ?- consult('a:\family.pro'). How Prolog works. Prolog works by establishing facts and rules. Something that we know to be true. Then query's are made from these facts. In a simpler form Prolog can be thought of as establishing a database and then asking questions from it. These facts, rules, and query's can be made from the prompt by the user (interactive programming) or be read from a source code file. More common are the facts and rules being established in the source code and the user makes the query's from a command prompt. Basics of facts and rules. Facts and rules are very similiar but have one crucial difference. A fact is something that is always unconditionally true. A rule specify's things that are true if some condition is satisfied. The following example are facts. It says the the parents of liz are tom and pam. ex : parent(tom, liz). tom pam parent(pam, liz). \ / liz Some examples of rules. ex : offspring(Y,X) :- parent(X,Y). For all X and Y, Y is an offspring of X if X is a parent of Y. The first part of the rule is referred to as the head and the second as the body. In the above example offspring(Y,X) is the head and parent(X,Y) is the body. Some more complex rules. ex : mother(X,Y) :- parent(X,Y),female(X). For all X and Y. X is the mother of Y if X is a parent of Y and X is a female. ex : sister(X,Y) :- For any X and Y, parent(Z,X), X is a sister of Y if parent(Z,Y), (1) both X and Y have the same parent,and female(X). (2) X is a female A diagram of the above Z example. / \ / \ X====>Y Some basics of queries, goals, and unification. 1. Prolog queries work by pattern matching. The query pattern is called a goal. If there is a fact that matches the goal, then the query succeeds and the listener responds with 'yes.' If there is no matching fact, then the query fails and the listener responds with 'no.' 2. Prolog's pattern matching is called unification. In the case where the database contains only facts, unification succeeds if the following three conditions hold. 3. The predicate named in the goal and database are the same. Both predicates have the same arity. All of the arguments are the same. ****************************************************************** Section 2 - Querying Most of the query's and assertions used with the program is within the source code. For instance if you look at the family.pro file included with the Dos version of the interperter that was recommneded you'll find the instructions as follows. ex : A simple query ?- sisterof(alice,X). ex : A more complex query ?- sisterof(alice,X), loves(X,wine). ex : You can redefine X to be a name. ?- sisterof(alice,harry). A good example to understand Prolog's database/query application is the bicycle.pro source file. It establishes the parts of the bike and then the user can query this database to see what parts are needed to build general defitions of the bike. ex : To load the file ?- consult(bicycle). ex : To find the parts required to make the hub of the bike. ?- partsof(hub,P). ex : To find all parts needed to make the bike. ?- partsof(bike,P). Another good example included with that Dos interperter is the Prolog source sort.pro . It has the various sorts such as quicksort, insertion sort, and the bubble sort. Good example to see how something that we know from functional languages works in a natural language like Prolog. The specifics for the assertions and running the various functions can be derived from the source. ex : To load the file ?- consult(sort). ex : To define a list ?- List = [a,b,c]. ex : To run a function ?- insort(List, Sortlist). Another ?- quisort(List,Sortlist,[]). To add facts or build them in the interperter use the assert command. ex : ?- asserta( ) Adds the clause X as the first clause for its predicate. Like the other I/O predicates,it always fails on backtracking and does not undo its work. ex : ?- assertz() Same as asserta/1, only it adds the clause X as the last clause for its predicate. ex : ?- retract(X) Removes the clause X from the database, again with a permanent effect that is not undone on backtracking. To set the trace feature to on and off. To pause the display output use Ctrl-S and to resume use Ctrl-S. ex : ?- trace. ex : ?- notrace. To exit the system for the Dos Ada interperter. ex : ?- exitsys. ****************************************************************** Section 3 - Some code syntax - There is much more, but these are common. Functors are structures in Prolog. They combine multiple components into a single object. ex : date(25, april, 1999). date date(25, april, 1999) / | \ / \ | / / | \ / \ | / 25 apr 1999 functor arguments Lists are a powerful data structure in Prolog and is used in many of the more complex programs. It can defined as follows. In the source code it declared as follows. ex : loc_list([apple, broccoli, crackers], kitchen). To ask for this list now we can. ex : ?- loc_list(X, kitchen). It will return. X = [apple, broccoli, crackers] An example of a nil list is done with the []. ex : list([], mylist). Here are some predicates you might see when doing input/output. write/1 This predicate always succeeds when called, and has the side effect of writing its argument to the console.It always fails on backtracking. Backtracking does not undo the side effect. nl/0 Succeeds, and starts a new line. Like write, it always succeeds when called, and fails on backtracking. tab/1 It expects the argument to be an integer and tabs that number of spaces. It succeeds when called and fails on backtracking. An anyonomous variable can also be declared with an underscore. ex : train(_). Here is a list of built in procedures not appearing elsewhere in this text and a description of what they do. == This is a literal equality. True if the terms are identical, have the same exact srtucture, and all corresponding arguements are the same. =.. Symbol is used decompose terms. ex : ?- f(a,b) =..L. L = [f,a,b] arg Extracts a term similiar to =.. ex : arg(N, Term,A) is true if A is the Nth arguement in Term. assert The assert commands add clauses to the prolog database. asserta assertz atom A built in predicate similiar to var, nonvar, integer, real, and atomic. atom(X) would return true if X were an atom. atomic A built in predicate similiar to var, nonvar, integer, real, and atom. atomic(X) would return true if X were an integer or atom. bagof Used when backtracking, puts all generated objects collected into a list. call Used when some versions of Prolog will require that a goal be an atom or structure with it's principal functor as an atom. ex : Goal =.. [Functor | Arglist]. call(Goal) findall Similar to bagof, difference is that all objects are collected regardless of different solutions that are not shared. get Used for writing and viewing characters from files. get0 put name Relates atoms and their ASCII encoding. nl Starts a newline at output, takes no arguements. nonvar nonvar(X) would succeed if X is a term other than a variable. spy Specifies that a predicate be traced. Usage is spy(P) from the nospy prompt. reconsult Similiar to consult except that if there are clauses that have already been redefined the old definition will supersede the new ones. see Used to redirect the current input stream to another file. Format is see(Filename). Some notes on arithemitic operations in Prolog. Comparison operators. X > Y X is greater than Y X < Y X is less that Y X >= Y X is greater than or equal to Y X =< Y X is less than or equal to Y X =:= Y Xthe values of X and Y are equal X =\= Y the values of X and Y are not equal ****************************************************************** Section 4 - Using Prolog under Unix Some notes for using a Prolog interperter under Unix. Everything here was tested under Linux but should be applicable to other Unix operating systems you may be running ie. Solaris, SCO, etc. SWI Prolog is available for Linux and is freeware under the GPL license unlike it's Winblows version. This is a really good interperter outputting decent error messages and having an online help system for the syntax that works really well. Installation is straightforward. It defaults to your usr/local directory to install the files. It can be downloaded from www.freshmeat.net like everything else that is Linux based. It also might be neccessary to edit your ld.so.conf file to reflect the change in enviroment path parameter if you haven't done so. This interperter for some reason makes the files be renamed with a .pl extension although it says it isn't neccessary. If the file is renamed with the .pl extension you don't have to specify that when loading the source file. Make sure that you check the source of the file that you want to run through the Prolog interperter before you do so. Many of these can only work on a Dos based system because their use of the ANSI graphics. At any time the help system can be accessed by using the following. ex : ?- help(topic). So far the only way that I have found to exit the interperter is to use the CTRL-C to break out of the interpertation where you can access a menu. From there you can type e to exit, g to list the goals, t to trace the program. ****************************************************************** Section 5 - Explanation of some Prolog code We will take a look at some basic prolog code here to try and explain what is happening and how see how the query's are being made. The notation to signify Notes X could not be used in the source code without being enclosed in comments /* */. ---------------------------------------- This is the code for family.pro. ---------------------------------------- /* To analyze the family structure of the family of Queen Victoria. English friend of mine notes there wasn't a Harry. I put him in. <------ Note 2 Answers the compelling question: Who is X the sister of? Ask: ?-sisterof( alice, X ). or ?-sisterof( alice, harry ). or ?-sisterof( alice, X ), loves( X, wine ). as an example of a complex question. <------- Note 3 or even: sisterof( alice, X ), loves( X, wine ), loves( alice, wine ). */ sisterof( X, Y ) :- parents( X, M, F ), <------------ Note 3 female( X ), parents( Y, M, F ). parents( edward, victoria, albert ). <------------ Note 4 parents( harry, victoria, albert ). parents( alice, victoria, albert ). female( alice ). <------------ Note 5 loves( harry, wine ). <------------ Note 6 loves( alice, wine ). <------------ Note 7 ---------------------------------------- 1. The first thing that you should notice is that comments are enclosed by the /* blank */ notation just like the C language does. 2. For most of the code they give you example query's. Others can be derived though with a little work. ex : ?- sisterof(X,Y). This will give you all the combinations of X and Y that are used in this program. 3. The first real lines of code define what sisterof is. It says that the parents of X are going to be M and F. The next line defines female as being X. X will always then have to be female in this program unless you change it. The next lines define the parents of Y. This is called a compound query. The comma is read as an and. 4. The following 3 lines are assertions as to the names of the child's (X or Y) parents are. 5. This says that alice is a female. Remember that X must always be a female so alice will now be X throughout this program. 6. The next two lines are used to make more complex expressions with the program. In english it means that harry and alice both love wine. This can be used to derive complex query's. 7. Notice that there isn't any indication of where this program is ending or beginning. The Prolog interperter will read the source code one line at a time until it reaches and EOF marker that is transparent to the user. ---------------------------------------- This is the code for bicycle.pro ---------------------------------------- /* Describe the parts required to make a bicycle. Firt the elementary parts are given (basicpart). Then a description of various subassemblies. Ask: ?-partsof( hub, P ). to get all the basic parts required to make a hub. Ask: ?-partsof( bike, P ). for the whole bike. */ basicpart( rim ). <-------- Note 1 basicpart( rearframe ). basicpart( gears ). basicpart( nut ). basicpart( spoke ). basicpart( handles ). basicpart( bolt ). basicpart( fork ). assembly( bike, [quant( wheel, 2 ), quant( frame, 1 )] ). <-------- Note 2 assembly( wheel, [quant( spoke, 20 ), quant( rim, 1 ), quant( hub, 1)] ). assembly( frame, [quant( rearframe, 1), quant( frontframe, 1 ) ] ). assembly( frontframe, [quant( fork, 1 ), quant( handles, 1 )] ). assembly( hub, [quant( gears, 1 ), quant( axle, 1 ) ] ). assembly( axle, [quant( bolt, 1 ), quant( nut, 2) ] ). partsof( X, [X] ) :- basicpart( X ). <-------- Note 3 partsof( X, P ) :- assembly( X, Subparts ), partsoflist( Subparts, P ). partsoflist( [], [] ). <--------- Note 4 partsoflist( [quant( X,N ) | Tail ], Total ) :- <-------- Note 5 partsof( X, Headparts ), partsoflist( Tail, Tailparts ), append( Headparts, Tailparts, Total ). append( [], L, L ). <-------- Note 6 append( [X|L1], L2, [X|L3] ) :- append( L1, L2, L3 ). ---------------------------------------- 1. The following definitions define the various parts of the bike to be a basicpart. 2. This joins the various parts into lists that can be easily referenced. 3. Establishes a rule such that X is in the list of [X] if X is a basicpart. 4. Estalishes the list as being empty (nil). 5. Partsoflist is being defined as a compound rule. The vertical bar | being used sperates the list into different parts. Basic operations used with lists are concatenation [ conc(arguements) ], membership [member(arg.)], adding an item [ add(arg.) ], deleting an item [del(arg.)], and making a sublist [sublist(arg.) ]. 6. The append part will append the lists together. I have found few references to this but I believe that is what this does. ---------------------------------------- This is the code for ktour.pro ---------------------------------------- /* "top level" goal, short form */ tour(Size) :- tour(Size,1,1),!. <-------- Note 1 /* & long form */ tour(Size,Xstart,Ystart) :- <-------- Note 2 crtgmode(Screen), /* save screen attributes */ board(Size), /* draw board */ claim(1,Xstart,Ystart), /* put knight on board */ proceed(2,Size), /* ******** tour ******** */ crtset(Screen), /* restore screen */ reset,!. /* clean up database */ proceed(Movenum,Size) :- /* one step toward a solution */ Tmoves is Size * Size, Movenum =< Tmoves, claimed(Xnow,Ynow),!, moves(Xnow,Ynow,Size,L), exelist(Movenum,L), Nnum is Movenum + 1, proceed(Nnum,Size). proceed(_,_) :- /* recursion bottoms out here */ curset(23,1,0), put(7),print('Tour complete. Find another? (Y/N)'), get0(Key), curset(23,1,0), put(7),print(' '), not (Key = 121; Key = 89). /* y or Y */ moves(X,Y,Size,L) :- /* L = sorted list of legal moves */ kmove(Delx,Dely), Xnew is X + Delx, Xnew > 0, Xnew =< Size, Ynew is Y + Dely, Ynew > 0, Ynew =< Size, not(claimed(Xnew,Ynew)), nmoves(Xnew,Ynew,Size,Num), asserta(move(Xnew,Ynew,Num)), fail. /* force to next line */ moves(_,_,_,L) :- movelist(L),!. movelist(L) :- /* accumulate & sort "move" facts */ not(move(_,_,_)),!,L = []. movelist(L) :- retract(move(X,Y,Num)), movelist(L1), goesin(X,Y,Num,L1,L). /* insertion sort */ goesin(X,Y,Num,[],[X,Y,Num]). <------ Note 5 goesin(X,Y,Num,[X1,Y1,Num1|T],[X,Y,Num,X1,Y1,Num1|T]) :- Num < Num1. goesin(X,Y,Num,[X1,Y1,Num1|T1],[X1,Y1,Num1|T]) :- goesin(X,Y,Num,T1,T). exelist(Movenum,[X,Y,_|T]) :- /* "execute" move list */ empty(X,Y), claim(Movenum,X,Y). exelist(Movenum,[_,_,_|T]) :- /* drop 1st move off on backtrack */ exelist(Movenum,T). nmoves(X,Y,Size,Number) :- /* number of moves from (X,Y) */ kmove(Delx,Dely), Xnew is X + Delx, Xnew > 0, Xnew =< Size, Ynew is Y + Dely, Ynew > 0, Ynew =< Size, not(claimed(Xnew,Ynew)), asserta(count), fail. /* force to next line */ nmoves(_,_,_,Number) :- sum(0,Number),!. sum(Sofar,Total) :- /* accumulate "count" facts */ retract(count), Acc is Sofar + 1, sum(Acc,Total). sum(Total,Total). /* recursion bottoms out here */ empty(X,Y) :- claimed(X,Y),!,fail. /* empty fails if square claimed */ empty(X,Y). /* succeeds otherwise */ empty(X,Y) :- unclaim(X,Y), /* "empties" square on backtrack */ !,fail. /* before failing */ claim(Number,X,Y) :- /* claim a square on board */ asserta(claimed(X,Y)), Scr_col is 2 + 3 * X, <------- Note 4 Scr_row is 1 + 2 * Y, curset(Scr_row,Scr_col,0), print(Number). unclaim(X,Y) :- /* unclaim a square on board */ retract(claimed(X,Y)), Scr_col is 2 + 3 * X, Scr_row is 1 + 2 * Y, curset(Scr_row,Scr_col,0), print(' '). /* 1 */ kmove( 1, -2). /* 8 possible knight's moves */ /* 2 */ kmove( 2, -1). /* 3 */ kmove( 2, 1). /* 4 */ kmove( 1, 2). /* 5 */ kmove( -1, 2). /* 6 */ kmove( -2, 1). /* 7 */ kmove( -2, -1). /* 8 */ kmove( -1, -2). horizlines(X1,X2,Y) :- /* draws horiz grid lines */ drawline(X1,Y,X2,Y,1), Ynew is Y - 16, Ynew >= 20, horizlines(X1,X2,Ynew). horizlines(_,_,_). /* recursion bottoms out here */ vertlines(Y1,Y2,X) :- /* draws vert grid lines */ drawline(X,Y1,X,Y2,1), Xnew is X - 24, Xnew >= 36, vertlines(Y1,Y2,Xnew). vertlines(_,_,_). /* recursion bottoms out here */ board(Size) :- /* oversees grid (board) drawing */ integer(Size), Size > 0, Size < 10, cls, crtset(5), X1 is 36, X2 is 36 + 24 * Size, Y1 is 20, Y2 is 20 + 16 * Size, horizlines(X1,X2,Y2), vertlines(Y1,Y2,X2). reset :- retract(claimed(_,_)),fail. /* predicate to clean out */ reset :- retract(move(_,_,_)),fail. /* database. Also useful if */ reset. /* program is interrupted. */ -------------------------------------------------------------------------- See the documentation of ktour.doc included with the Ada Prolog interperter if you need an explanation of the knights tour. When tracing this program it may get very confusing because of the use of recursion throughout and the way the author has placed the rules scattered around. You'll start going up, down, sideways, it can get really crazy. 1. The ! mark used at the end of this rule is called a cut, it is used to prevent backtracking. ex : f(X,0) :- X<3,!. Is X less than zero, yes than go on, no then stop. It will prevent backtracking at the point that it appears in the program. Backtracking is used when there is no clause that matches the goal of the query. When the goal fails is starts at the top of the program and tries to find an alternative way to derive it. The is the start of the program, it is also where the user will tell the program the size of the board to use. The size is then established and the program moves on to the next rule. 2. The next rules arguements have already been established. Size is whatever the user specified and Xstart, Ystart are 1 and 1. The first cell on the board. Reason to prevent the backtracking is clear here. If it was backtracking the starting points could be established as 1,1 every time it doesn't meet it's match. crtgmode(Screen) should just set the mode for the graphics, references on this are vague. The next thing the rule looks at when evaluating it's conditions is the rule board(Size). The rule board(Size) is at the end of the program. See note 3 for information about this rule. After the board is drawn it precedes to claim a cell on the board with the rule claim(Number, X, Y). See note 4 about this rule. After the cell is claimed on the board we then go on to the moves rule which will determine a legal move. The is in the second line where it says Xnew is X + Delx is an arithemtic operator. Basically it can be thought of as an assignment. The result of X + Delx is stored in Xnew. We then check to see if Xnew is > 0, remember that rules are conditional for all parts. Notice that the last line is the built in procedure fail, this is usually used in conjunction with a conditional but in this case it wasn't. True can also be used in this manner. 3. What this rule does is prepare to draw the board on the screen. It first checks to see if the board size is less that 10 but greater than 0 (line 1) and then clears the screen and set the mode (line 2 - crtset isn't referenced readily available but we can assume it's purpose). It then sets the varius cordinates for X and Y (lines 3-6) and then calls rule horizlines with arguements of X1, X2, and Y2. Horizlines and vertlines use recursion to draw the board on the screen. When it fails it's arguements are nil and the program continues. 4. This claims a cell on the board and outputs it to the screen. The asserta command asserts a clause into the database at a specific position. It then determines the screen cols and rows and does the output. 5. This rule is using two lists, one is empty (nil) the other has three arguements. ****************************************************************** Last edited 25 April 00:17.