================================================================= Quick Introduction to Prolog (SWI-Prolog) ================================================================= Contents: ================================================================= I. Getting started II. Examples of problem solving in Prolog 1. Finding a path in a directed graph 2. Solving systems of equations with Peano numbers ================================================================= I. Getting started ================================================================= Install SWI-Prolog using the infomation at http://www.swi-prolog.org/ Run it and wait until you get the SWI-Prolog window with the prompt "?-". When Prolog is ready it prints a prompt (?-) and you can type queries (goals, questions). Try this one: ?- member(X,[1,2,3]). *** NOTE THAT ALL PROLOG QUERIES MUST END WITH A FULL STOP (.) !!! Now you get X=1 Press Enter to end the query or if you want alternative solutions type semicolon (;). Then you get: X = 1 ; X = 2 ; X = 3 ; No 4 ?- (The number 4 before the prompt indicates how many times the prompt has been printed.) These are all the solutions of this query, i.e. all values of the variable X that satisfy the query (all members of the list). *** NOTE THAT THE VARIABLES MUST BEGIN WITH A CAPITAL LETTER !!! If you whant to get all solutions in a list you can use this: 4 ?- findall(X,member(X,[1,2,3]),L). X = _G354 L = [1, 2, 3] Or you may try a conjunction of two goals to get the intersection of two sets (lists). For example: 9 ?- member(X,[1,2,3]),member(X,[a,b,3,c,2]). X = 2 ; X = 3 ; No 5 ?- Or again, using findall you get all solutions in a list: ERROR: Stream user_input:71: Syntax error: Unexpected end of clause 10 ?- findall(X,(member(X,[1,2,3]),member(X,[a,b,3,c,2])),L). X = _G504 L = [2, 3] *** YOU MAY TYPE THE QUERIES IN MULTIPLE LINES AND PUT A DOT (.) AT THE END OF THE LAST LINE. FOR EXAMPLE: 13 ?- member(X, | [1,2, | 3 | ] | ). X = 1 Prolog prints a bar (|) in the beginning of the line, indicating that this is a continuation. You may also get ERROR MESSAGES. For example: 14 ?- member (X,[1,2,3]). ERROR: Syntax error: Operator expected ERROR: member (X,[1,2,3] ERROR: ** here ** ERROR: ) . 14 ?- *** NO SPACE IS ALLOWED AFTER A PREDICATE OR GOAL NAME (e.g. member). 14 ?- member(X,[1,2,3]. ERROR: Syntax error: Unexpected end of clause ERROR: member(X,[1,2,3] ERROR: ** here ** ERROR: . 14 ?- *** ANY NUMBER OF BLANKS OR NEW LINES CAN BE USED AFTER A COMMA. *** MAKE SURE THAT ALL PARENTHESES AND SRUARE BRACKETS ARE PROPERLY PAIRED !!! 14 ?- MEMBER(X,[1,2,3]). ERROR: Syntax error: Operator expected ERROR: MEMBER(X,[1,2,3] ERROR: ** here ** ERROR: ) . 14 ?- *** TYPE ALL PREDICATES OR GOALS (as member) with lower case letters !!! ================================================================= II. Examples of problem solving in Prolog. Using files. ================================================================= 1. Finding a path in a directed graph ------------------------------------- Consider the following graph 1 --> 2 --> 3 --> 4 | | |--------> 5 | | \-------------> 6 In Prolog this is represented as a set of facts. i.e. arc(1,2). arc(2,3). arc(3,4). arc(3,5). arc(2,5). arc(5,6). arc(2,6). Now we want to define a procedure to find a path between two nodes X and Y in this graph. That is, we want to define a predicate path(X,Y,Path). We just follow our intuition: 1. If there is an arc between X and Y, then Path=arc(X,Y). That is, if arc(X,Y) then path(X,Y)). Or, in Prolog this is: path(X,Y,[arc(X,Y)]) :- arc(X,Y). 2. Otherwise, if there is an arc between X and some other node Z, and there is a path from Z to Y, then there is a path from X to Y too. That is, if arc(X,Z) and path(Z,Y) then path(X,Y). In Prolog this is: path(X,Y,[arc(X,Z)|P]) :- arc(X,Z),path(Z,Y,P). 3. The only thing that is not so intuitive is how we get the third argument of path. This is a technicality that allows us to create lists and is a built-in feature of Prolog. Now, we have to add these two rules (clauses) along with the set of facts describing the graph to the Prolog database. To do this we need to create a text file and then copy/paste the above two rules and 7 facts into it. Assume we use, for example, NOTEPAD and create a file named "path.pl" in the folder "c:/prolog". We can load this file into the Prolog database by using the following query: ?- ['c:/prolog/path.pl']. After a successfull load (compilation) we get the prompt again. Then, we may ask the following questions (type ; after the Prolog answer to see alternative solutions, or just to continue with the next question): Find the path (or all possible paths, if you use ;) from node 1 to node 6. ?- path(1,6,P). Find paths from node 1 to other nodes in the graph. ?- path(1,X,P). Find paths from some/all nodes to node 5. ?- path(X,5,P). Find paths with length 3 from node 1 to node 6. ?- path(1,6,[A,B,C]). Find paths with length 3 from node 1 to node 6. ?- path(1,6,P), length(P,3). Find paths in the graph that are longer than 2 arcs. ?- path(X,Y,P), length(P,L), L>2. Find paths with length 2 that go through node 3. ?- path(X,Y,[arc(X,3),arc(3,Y)]). Find paths in the graph that include arc(3,4). ?- path(X,Y,P),member(arc(3,4),P). 2. Solving systems of equations with Peano numbers -------------------------------------------------- The original Peano numbers are defined functionally as 0 and s(s(...s(0)...)). Here we use a similar definition based on lists. 0 is represented as an empty list []. An integer N>0 is represented as a list of N 1's For example: 5 is [1,1,1,1,1]. Prolog has a built-in predicate that can be used for adding such numbers. This is the same prdicate that appends lists. Let's now solve the following system of equations: X+Y=5 X-Y=3 First, we make the transformation X-Y=3 ==> Y+3=X (why?). Then we put the two equatons as Prolog predicates. Y+3=X ==> append(Y,[1,1,1],X) X+Y=5 ==> append(X,Y,[1,1,1,1,1]) Obviously, both equations must be true, i.e. we need a conjunction between the two append's. So, with the following query get the answers: ?- append(X,Y,[1,1,1,1,1]),append(Y,[1,1,1],X). X=[1,1,1,1] Y=[1] i.e. X=4, Y=1 Here is another, simpler example: 21 ?- append(X,Y,[1,1,1,1,1]). X = [] Y = [1, 1, 1, 1, 1] ; X = [1] Y = [1, 1, 1, 1] ; X = [1, 1] Y = [1, 1, 1] ; X = [1, 1, 1] Y = [1, 1] ; X = [1, 1, 1, 1] Y = [1] ; X = [1, 1, 1, 1, 1] Y = [] ; No 22 ?- What we get here is actually all possible solutions of the equation X+Y=5. That is: X=0, Y=5 X=1, Y=4 X=2, Y=3 X=3, Y=2 X=4, Y=1 X=5, Y=0 Happy Prolog-ing...