Chapter 2 – Uninformed Search
Prolog
Do we have to? Yes…
Logic Programming
Uses a set of logical assertions (rule base), as a program.
Execution is initiated by a query or goal, which the system attempts to prove true or false, based on the existing set of assertions.
2
Prolog
Prolog is a logic programming language.
Prolog consists of a series of rules and facts.
A program is run by presenting some query and seeing if this can be proved against these known rules and facts.
Free prolog compiler: SWI-Prolog (http://www.swi-prolog.org/)
3
Elements of Prolog: Terms
Everything in Prolog is built from terms.
Three kinds of terms:
Constants: integers, real numbers, atoms
Variables
Compound terms
4
Constants
Integer constants: 123
Real constants: 1.23
Atoms:
A lowercase letter followed by any number of additional letters, digits or underscores: fred
A sequence of non-alphanumeric characters:
*, ., =, @#$
Plus a few special atoms: []
5
Atoms Are Not Variables
An atom can look like an Scheme or Java variable:
i, size, length
But an atom is not a variable; it is not bound to anything, never equal to anything else
Think of atoms as being more like string constants: “i”, “size”, “length”
6
Variables
Any name beginning with an uppercase letter or an underscore, followed by any number of additional letters, digits or underscores: X, Child, Fred, _, _123
Most of the variables you write will start with an uppercase letter
Those starting with an underscore, including _, get special treatment
7
Compound Terms
An atom followed by a parenthesized, comma-separated list of one or more terms: x(y,z), +(1,2), .(1,[]), parent(adam,seth), x(Y,x(Y,Z))
A compound term can look like an Scheme function call: f(x,y)
Again, this is misleading
Think of them as structured data
8
The Prolog rule base
A Prolog language system maintains a collection of facts and rules of inference
A Prolog program is just a set of rules for this rule base
The simplest kind of thing in the rule base is a fact: a term followed by a period
9
Example rule base
A Prolog program of six facts
Defining a predicate parent/2 of arity 2
We would naturally interpret these as facts about families: Kim is the parent of Holly and so on
10
parent(kim,holly).
parent(margaret,kim).
parent(margaret,kent).
parent(esther,margaret).
parent(herbert,margaret).
parent(herbert,jean).
SWI-Prolog
Prompting for a query with ?-
Normally interactive: get query, print result, repeat
11
For help, use ?- help(Topic). or ?- apropos(Word).
?-
The consult Predicate
Predefined predicate to read a program from a file into the database
File relations (or relations.pl) contains our parent facts
12
?- consult(relations).
% relations compiled 0.00 sec, 0 bytes
Yes
?-
Simple Queries
A query asks the language system to prove something
The answer will be Yes or No
13
?- parent(margaret,kent).
Yes
?- parent(fred,pebbles).
No
?-
Final Period
Queries can take multiple lines
If you forget the final period, Prolog prompts for more input with |
14
?- parent(margaret,kent)
| .
Yes
?-
Queries With Variables
Any term can appear as a query, including a term with variables
The Prolog system shows the bindings necessary to prove the query
15
?- parent(P,jean).
P = herbert
Yes
?- parent(P,esther).
No
Flexibility
Normally, variables can appear in any or all positions in a query:
parent(Parent,jean)
parent(esther,Child)
parent(Parent,Child)
parent(Person,Person)
16
Conjunctive query
A conjunctive query has a list of query terms separated by commas
The Prolog system tries prove them all (using a single set of bindings)
17
?- parent(margaret,X), parent(X,holly).
//”?-” is if
X = kim
Yes
Disjunctive query
A disjunctive query has a list of query terms separated by semicolons.
The Prolog system tries prove any of them (using a single set of bindings)
18
?- adam=adam.
true.
?- adam=fred.
false.
?- (adam=adam);(adam=fred).//”;” is or
true
Multiple Solutions
There might be more than one way to prove the query
By typing ; rather than Enter, you ask the Prolog system to find more solutions
19
?- parent(margaret,Child)
Child = kim ;
Child = kent ;
No
How to write a rule
A rule says how to prove something: to prove the head, prove the conditions
To prove greatgrandparent(GGP,GGC), find some GP and P for which you can prove parent(GGP,GP), then parent(GP,P) and then finally parent(P,GGC)
20
greatgrandparent(GGP,GGC) :-
parent(GGP,GP), //”,”is and
parent(GP,P),
parent(P,GGC).
conditions
head
Example Prolog program with facts and rules
A program consists of a list of clauses
A clause is either a fact or a rule, and ends with a period
21
parent(kim,holly).
parent(margaret,kim).
parent(margaret,kent).
parent(esther,margaret).
parent(herbert,margaret).
parent(herbert,jean).
greatgrandparent(GGP,GGC) :-
parent(GGP,GP), parent(GP,P), parent(P,GGC).
Example
This shows the initial query and final result
Internally, there are intermediate goals:
The first goal is the initial query
The next is what remains to be proved after transforming the first goal using one of the clauses (in this case, the greatgrandparent rule)
And so on, until nothing remains to be proved
22
?- greatgrandparent(esther,GreatGrandchild).
GreatGrandchild = holly
Yes
How to write rules using other rules
Same relation, defined indirectly
Note that both clauses use a variable P
The scope of the definition of a variable is the clause that contains it
23
grandparent(GP,GC) :-
parent(GP,P), parent(P,GC).
greatgrandparent(GGP,GGC) :-
grandparent(GGP,P), parent(P,GGC).
Arithmetic Operators in Prolog
Predicates +, -, * and / are operators too, with the usual precedence and associativity
24
?- X = +(1,*(2,3)).
X = 1+2*3
Yes
?- X = 1+2*3.
X = 1+2*3
Yes
Unification in Prolog
Unification is the process of matching to make statement identical.
Variables that are set equal to patterns are said to be instantiated.
25
Unification in Prolog
A constant unifies only with itself.
A variable that is uninstantiated unifies with anything and become instantiated to that thing.
A structured term unifies with another term only if it has the same function/predicate name and same number of arguments, and the arguments can be unified recursively.
26
The = Predicate
The goal =(X,Y) succeeds if and only if X and Y can be unified:
Since = is an operator, it can be and usually is written like this:
27
?- =(parent(adam,seth),parent(adam,X)).
X = seth
Yes
?- parent(adam,seth)=parent(adam,X).
X = seth
Yes
Examples
28
?- me = me.
?- me = you.
?- me = X.
?- you = Y.
?- X = Y.
?- f(X) = g(X).
?- f(a,g(x)) = f(Y,X).
?- f(a,g(X)) = f(Y,g(b)).
Lists in Prolog
These are just abbreviations for the underlying term using the . predicate
Prolog usually displays lists in the list notation
29
List notation
Term denoted
[]
[]
[1]
.(1,[])
[1,2,3]
.(1,.(2,.(3,[])))
[1,parent(X,Y)]
.(1,.(parent(X,Y),[]))
Example
30
?- X = .(1,.(2,.(3,[]))).
X = [1, 2, 3]
Yes
?- .(X,Y) = [1,2,3].
X = 1
Y = [2, 3]
Yes
List notation with head and tail
Last in a list can be the symbol | followed by a final term for the tail of the list
Useful in patterns: [1,2|X] unifies with any list that starts with 1,2 and binds X to the tail
Same pattern as we saw with Scheme, but more flexible…
31
List notation
Term denoted
[1|X]
.(1,X)
[1,2|X]
.(1,.(2,X)))
[1,2|[3,4]]
same as [1,2,3,4]
?- [1,2|X] = [1,2,3,4,5].
X = [3, 4, 5]
Yes
Predefined List Predicates
32
Predicate
Description
member(X,Y)
Provable if the list Y contains the element X.
select(X,Y,Z)
Provable if the list Y contains the element X, and Z is the same as Y but with one instance of X removed.
nth0(X,Y,Z)
Provable if X is an integer, Y is a list, and Z is the Xth element of Y, counting from 0.
length(X,Y)
Provable if X is a list of length Y.
Examples of using select
33
?- select(2,[1,2,3],Z).
Z = [1, 3] ;
No
?- select(2,Y,[1,3]).
Y = [2, 1, 3] ;
Y = [1, 2, 3] ;
Y = [1, 3, 2] ;
No
The Anonymous Variable
The variable _ is an anonymous variable
Every occurrence is bound independently of every other occurrence
It matches any term without introducing bindings
34
Example
This tailof(X,Y) succeeds when X is a non-empty list and Y is the tail of that list
35
tailof(.(_,A),A).
The not Predicate
36
?- member(1,[1,2,3]).
Yes
?- not(member(4,[1,2,3])).
Yes
Real Values And Integers
37
?- X is 1/2.
X = 0.5
Yes
?- X is 1.0/2.0.
X = 0.5
Yes
?- X is 2/1.
X = 2
Yes
?- X is 2.0/1.0.
X = 2
Yes
There are two numeric types: integer and real.
Most of the evaluable predicates are overloaded for all combinations.
Prolog is dynamically typed; the types are used at runtime to resolve the overloading.
But note that the goal 2=2.0 would fail.
Comparisons
Numeric comparison operators:
<, >, =<, >=, =:=, =\=
To solve a numeric comparison goal, Prolog evaluates both sides and compares the results numerically
So both sides must be fully instantiated
38
Equalities In Prolog
We have used three different but related equality operators:
X is Y evaluates Y and unifies the result with X: 3 is 1+2 succeeds, but 1+2 is 3 fails
X = Y unifies X and Y, with no evaluation: both 3 = 1+2 and 1+2 = 3 fail
X =:= Y evaluates both and compares: both
3 =:= 1+2 and 1+2 =:= 3 succeed
Any evaluated term must be fully instantiated
39
Example: mylength
40
mylength([],0).
mylength([_|Tail], Len) :-
mylength(Tail, TailLen),
Len is TailLen + 1.
?- mylength([a,b,c],X).
X = 3
Yes
?- mylength(X,3).
X = [_G266, _G269, _G272]
Yes
Counterexample: mylength
41
mylength([],0).
mylength([_|Tail], Len) :-
mylength(Tail, TailLen),
Len = TailLen + 1.
?- mylength([1,2,3,4,5],X).
X = 0+1+1+1+1+1
Yes
Example: sum
42
sum([],0).
sum([Head|Tail],X) :-
sum(Tail,TailSum),
X is Head + TailSum.
?- sum([1,2,3],X).
X = 6
Yes
?- sum([1,2.5,3],X).
X = 6.5
Yes
The 8-Queens Problem
Chess background:
Played on an 8-by-8 grid
Queen can move any number of spaces vertically, horizontally or diagonally
Two queens are in check if they are in the same row, column or diagonal, so that one could move to the other’s square
The problem: place 8 queens on an empty chess board so that no queen is in check
43
Representation
We could represent a queen in column 2, row 5 with the term queen(2,5)
But it will be more readable if we use something more compact
Since there will be no other pieces—no pawn(X,Y) or king(X,Y)—we will just use a term of the form X/Y
(We won’t evaluate it as a quotient)
44
Example
A chessboard configuration is just a list of queens
This one can be represented with
[2/5,3/7,6/1]
45
46
/*
nocheck(X/Y,L) takes a queen X/Y and a list
of queens. We succeed if and only if the X/Y
queen holds none of the others in check.
*/
nocheck(_, []).
nocheck(X/Y, [X1/Y1 | Rest]) :-
X =\= X1,
Y =\= Y1,
abs(Y1-Y) =\= abs(X1-X),
nocheck(X/Y, Rest).
47
/*
legal(L) succeeds if L is a legal placement of
queens: all coordinates in range and no queen
in check.
*/
legal([]).
legal([X/Y | Rest]) :-
legal(Rest),
member(X,[1,2,3,4,5,6,7,8]),
member(Y,[1,2,3,4,5,6,7,8]),
nocheck(X/Y, Rest).
Adequate to solve the problem
This is already enough to solve the problem: the query legal(X) will find all legal configurations:
48
?- legal(X).
X = [] ;
X = [1/1] ;
X = [1/2] ;
X = [1/3]
8-Queens Solution
Of course that will take too long: it finds all 64 solutions with one queen, then starts on those with two, and so on
To make it concentrate right away on
eight queens, we can give a different query:
49
?- X = [_,_,_,_,_,_,_,_], legal(X).
X = [8/4, 7/2, 6/7, 5/3, 4/6, 3/8, 2/5, 1/1]
Yes
Example
Our 8-queens solution
[8/4, 7/2, 6/7, 5/3,
4/6, 3/8, 2/5, 1/1]
50
Room For Improvement
Slow
Finds trivial permutations after the first:
51
?- X = [_,_,_,_,_,_,_,_], legal(X).
X = [8/4, 7/2, 6/7, 5/3, 4/6, 3/8, 2/5, 1/1] ;
X = [7/2, 8/4, 6/7, 5/3, 4/6, 3/8, 2/5, 1/1] ;
X = [8/4, 6/7, 7/2, 5/3, 4/6, 3/8, 2/5, 1/1] ;
X = [6/7, 8/4, 7/2, 5/3, 4/6, 3/8, 2/5, 1/1]
An Improvement
Clearly every solution has 1 queen in each column
So every solution can be written in a fixed order, like this:
X=[1/_,2/_,3/_,4/_,5/_,6/_,7/_,8/_]
Starting with a goal term of that form will restrict the search (speeding it up) and avoid those trivial permutations
52
53
/*
eightqueens(X) succeeds if X is a legal
placement of eight queens, listed in order
of their X coordinates.
*/
eightqueens(X) :-
X = [1/_,2/_,3/_,4/_,5/_,6/_,7/_,8/_],
legal(X).
Improved 8-Queens Solution
Now much faster
Does not bother with permutations
54
?- eightqueens(X).
X = [1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1] ;
X = [1/5, 2/2, 3/4, 4/7, 5/3, 6/8, 7/6, 8/1]
Working with Logic Puzzles
55
Three Sections
Generally, you want to have three “sections”.
These aren’t part of the language (like Cobol’s sections), but they are the general pattern that you will find yourself doing.
56
Traditional Prolog
Input Setup
Processing Rules
Output Output
Choose one “category” to be the “anchor” – the one solid element that we will talk about.
All of the rest we need to define a rule for (tie, relative)
We make a variable for each anchor/category combination
Then we make a list of lists of the “answers” with the anchors and the variables.
57
tie(cupids).
tie(happy_faces).
tie(leprechauns).
tie(reindeer).
relative(daughter).
relative(father_in_law).
relative(sister).
relative(uncle).
solve :-
tie(CrowTie), tie(EvansTie), tie(HurleyTie), tie(SpeiglerTie),
all_different([CrowTie, EvansTie, HurleyTie, SpeiglerTie]),
relative(CrowRelative), relative(EvansRelative),
relative(HurleyRelative), relative(SpeiglerRelative),
all_different([CrowRelative, EvansRelative, HurleyRelative,
SpeiglerRelative]),
Triples = [ [crow, CrowTie, CrowRelative],
[evans, EvansTie, EvansRelative],
[hurley, HurleyTie, HurleyRelative],
[speigler, SpeiglerTie, SpeiglerRelative] ],
Rules focus on defining a list and saying that it either IS or IS NOT a member of the result list.
Use _ for variables not mentioned in the problem.
58
% 1. The leprechauns tie wasn’t a present from a daughter.
not(member([_, leprechauns, daughter], Triples)),
% 2. Crow’s tie features neither the reindeer nor the faces.
not(member([crow, reindeer, _], Triples)),
not(member([crow, happy_faces, _], Triples)),
% 3. Speigler’s tie wasn’t a present from his uncle.
not(member([speigler, _, uncle], Triples)),
% 4. The tie with the faces wasn’t a gift from a sister.
not(member([_, happy_faces, sister], Triples)),
% 5. Evans and Speigler own the tie with the leprechauns
% and the tie that was a present from a father-in-law
( (member([evans, leprechauns, _], Triples),
member([speigler, _, father_in_law], Triples)) ;
(member([speigler, leprechauns, _], Triples),
member([evans, _, father_in_law], Triples)) ),
% 6. Hurley received his flamboyant tie from his sister.
member([hurley, _, sister], Triples),
Output and Utility
tell(crow, CrowTie, CrowRelative),
tell(evans, EvansTie, EvansRelative),
tell(hurley, HurleyTie, HurleyRelative),
tell(speigler, SpeiglerTie, SpeiglerRelative).
% Succeeds if all elements of the argument list are bound and different.
% Fails if any elements are unbound or equal to some other element.
all_different([H | T]) :- member(H, T), !, fail.
all_different([_ | T]) :- all_different(T).
all_different([_]).
tell(X, Y, Z) :-
write(‘Mr. ‘), write(X), write(‘ got the ‘), write(Y),
write(‘ tie from his ‘), write(Z), write(‘.’), nl.
59
8
7
6
5
4
3
2
1
2
1
4
3
6
5
8
7
Q
Q
Q
8
7
6
5
4
3
2
1
2
1
4
3
6
5
8
7
Q
Q
Q
Q
Q
Q
Q
Q
/docProps/thumbnail.jpeg