CIS587: Prolog

Last Modified:

These minimal notes on Prolog show only some of its flavor.

Here are facts

	plays(ann,fido).
	friend(john,sam).

where ann, fido, john, and sam are individuals, and plays and friend are functors. And here is a rule

	likes(X,Y) :- plays(X,Y),friend(X,Y).

It says that if X plays with Y and X is a friend of Y then X likes Y. Variables start with capital letters (If we are not interested in the value of a variable, we can just use _ (underscore)).
In a rule the left-hand side and the right-hand side are called respectively the head and the tail of the rule.

On yoda, you call prolog as /usr/local/prolog/bin/prolog. The prompt in prolog is

	| ?-

You exit prolog with the statement

	halt.

You can add rules and facts to the current session in a number of ways:

You can enter clauses from the terminal as follows:
```
	| ?- consult(user).
	| like(b,a).
	| like(d,c).
	^D
```
which adds the two clauses to the working space.
Or you can read in a file:
```
	| ?- consult('filename').
```
which is added at the end of the working space.
Or you can assert a clause
```
	| ?- assert(< clause >).
```

Here are some confusing "equalities" in prolog:

				variable	arithmetic
	predicate  relation	substitution	computation
	-----------------------------------------------------------
	==	   identical	no		no
	=	   unifiable    yes		no
	=:=	   same value	no		yes
	is	   is the 	yes		yes
		   value of

and some examples of their use:

	?- X == Y.
	no

	?- X + 1 == 2 + Y.
	no

	?- X + 1 = 2 + Y.
	X = 2
	Y = 1			

	?- X + 1 = 1 + 2.
	no

The ubiquitous Factorial Function

Example: Factorial1

	factorial(0,1).
	factorial(N,F) :- N>0, N1 is N-1, factorial(N1,F1),F is N*F1.
then
	?- factorial(5,F).
	F = 120

	?- factorial(X,120).
	instantiation error

Example: Factorial2: dropping N>0 from factorial1

	factorial(0,1).
	factorial(N,F) :- N1 is N-1, factorial(N1,F1),F is N*F1.
then
	?- factorial(5,F).
	F = 120;                   Here ";" asks for next value of F
	keeps on going until stack overflow

Example: Factorial3: Changing order of terms

(1)	factorial(0,1).
(2)	factorial(N,F) :- factorial(N1,F1), N is N1+1, F is N*F1.
then
	?- factorial(5,F).
	F = 120

	?- factorial(X,120).
	X = 5;
	integer overflow

Here is why factorial(X,120) returns 5. For brevity, instead of "factorial"
we will write "f".

		f(X,120)
	      /   |
	     /    | [0/N5,1/F5,1/N4,1/F4,2/N3,2/F3,3/N2,6/F2,4/N1,24/F1,5/N1]
	    /     +-----------------------+
	   /      |          |            |
   f(0,1)	f(N1,F1)   X is N1+1	6 is X*F1
	      /   |
	     /    | [0/N5,1/F5,1/N4,1/F4,2/N3,2/F3,3/N2,6/F2,4/N1,24/F1]
	    /     +-----------------------+
	   /      |          |            |
   f(0,1)	f(N2,F2)   N1 is N2+1   F1 is N1*F2
              /   |
	     /    | [0/N5,1/F5,1/N4,1/F4,2/N3,2/F3,3/N2,6/F2]
	    /     +-----------------------+
	   /      |          |            |
   f(0,1)	f(N3,F3)   N2 is N3+1   F2 is N2*F3
              /   |
	     /    | [0/N5,1/F5,1/N4,1/F4,2/N3,2/F3]
	    /     +-----------------------+
	   /      |          |            |
   f(0,1)	f(N4,F4)   N3 is N4+1   F3 is N3*F4
	      /   |
	     /    | [0/N5,1/F5,1/N4,1/F4]
	    /     +-----------------------+ 
	   /      |          |            |
   f(0,1)	f(N5,F5)   N4 is N5+1   F4 is N4*F5
		  |
		  |
		  | [0/N5,1/F5]
		  |
		f(0,1)

In this diagram we see the substitutions computed. Much is not said in the diagram, for example why we abandon the unifications with the various f(0,1)s. [Let's say it for the second f(0,1) from the top: because it forces the substitution [0/N1,1/F1,1/X] and this cause 6 is X*F1 to fail.]

Lists

Lists are very much as in lisp. In place of Lisp's cons, in Prolog we use the "." or dot:

	Dot Notation		List Notation	Lisp Notation
	-----------------------------------------------------
	.(X,Y)			[X | Y]		(X . Y)
	.(X, .(Y,Z))		[X,Y|Z]		(X (Y . Z))
	.(X, .(Y, .(Z, [])))	[X,Y,Z]		(X Y Z)

Example: len

	len([],0).
	len([_|T], N) :- len(T,M), N is M+1.		

	?- len([a,b,c],X).
	X = 3

	?- len([a,b,c], 3).
	yes

	?- len([a,b,c], 5).
	no

Example: member

member(X,Y) is inteded to mean X is one of the top level elements of the list Y.

	member(X,[X|_]).
	member(X,[_|T]) :- member(X,T).

	?- member(X, [1,2,3,4,5]).
	X=1;
	X=2;
	X=3;
	X=4;
	X=5;
	no

Example: select

select(X,A,R) is intended to mean that X is a top level element of the list A and that R is what is left of A after taking X out of it.

	select(H,[H|T],T).
	select(X,[H|T],[H|T1]) :- select(X,T,T1).

	?- select(X,[a,b,c],R).
	X=a
	R=[b,c];
	X=b
	R=[a,c];
	X=c
	R=[a,b];
	no

The Cryptography Problem

Here is a problem:

	S E N D +
	M O R E
      ---------
      M O N E Y

to be solved by mapping the letters into distinct digits and then doing regular arithmetic. We add variables to represent the various carries:

	C3 C2 C1
	S  E  N  D +
	M  O  R  E
      ------------
      M O  N  E  Y

We observe that carries can only be 0 or 1 and thus that M has to be 1. Then here is a solution:

    solve([S,E,N,D], [M,O,R,E], [M,O,N,E,Y]) :-
	M=1, L=[2,3,4,5,6,7,8,9],
	select(S,L,L1), S>0, (C3=0; C3=1),        ";" means OR
	O is S+M+C3-10*M, select(O, L1, L2),
	select(E,L2,L3), (C2=0;C2=1),
	N is E+O+C2-10*C3, select(N,L3,L4), (C1=0;C1=1),
	R is E+10*C2-(N+C1), select(R,L4,L5),
	select(D,L5,L6),
	Y is D+E-10*C1, select(Y,L6,_).

    ?- solve([S,E,N,D], [M,O,R,E], [M,O,N,E,Y]).
	S=9
	E=5
	N=6
	D=7
	M=1
	O=0
	R=8
	Y=2;
	no

ingargiola@cis.temple.edu