Transcript PPT

CS 403 - Programming
Languages
Class 21
November 9, 2000
1
Today’s Agenda
Finish Chapter 15
Assignment:

Read chapter 15 for today
Announcement:

Programming assignment.
CS 403, Class 19
Slide # 2
Objectives

Introduction to using Prolog
CS 403, Class 19
Slide # 3
Length of Lists I
The Problem: Define a relation llength(L,N) to
mean that the length of the list L is N.
The Program:
llength([],0).
llength([X|Z],N):- llength(Z,M), N is M + 1.
CS 403, Class 19
Slide # 4
Watch it work:
?- [length].
?- llength([a,b,c,d],M).
M=4
CS 403, Class 19
Slide # 5
Length of Lists II
The Program:
llength([],0).
llength([X|Z],N) :- N is M + 1,
llength(Z,M).
CS 403, Class 19
Slide # 6
Watch it work:
?- [length2].
?- llength([a,b,c,d],M).
evaluation_error: [goal(_1629 is
_1805+1),argument_index(2)]
CS 403, Class 19
Slide # 7
Control in Prolog I
How Prolog tries to solve a query like:
<query1>, <query2>, .... , <queryN>
This is the control side of the equation:
Algorithm=Logic+Control
Step 1: Find Things that solve <query1>, if
none then fail else goto Step 2
Step 2: Do the things found from the previous
step allow more things to be found that solve
<query2>? If not then go back to step1 else
goto step 3.......
CS 403, Class 19
Slide # 8
Control in Prolog I
Prolog tries to solve the clauses from left to
right If there is a database file around it will
use it in a similarly sequential fashion.
1. Goal Order: Solve goals from left to right.
2. Rule Order: Select the first applicable rule,
where first refers to their order of appearance
in the program/file/database
CS 403, Class 19
Slide # 9
Control in Prolog II
The actual search algorithm is:
1. start with a query as the current goal.
2. WHILE the current goal is non-empty
DO choose the leftmost subgoal ;
IF a rule applies to the subgoal
THEN select the first applicable rule;
form a new current goal;
ELSE backtrack;
SUCCEED
CS 403, Class 19
Slide # 10
Control in Prolog II
Note 1: Thus the order of the queries is of
paramount importance .
Note 2: The general paradigm in Prolog is
Guess then Verify: Queries with the fewest
solutions should come first, followed by those
that filter or verify these few solutions
CS 403, Class 19
Slide # 11
Binary Search Trees I
An example of user defined data structures.
The Problem: Recall that a binary search tree
(with integer labels) is either :
1. the empty tree empty,or
2. a node labeled with an integer N, that has a
left subtree and a right subtree, each of which
is a binary search tree such that the nodes in
the left subtree are labeled by integers strictly
smaller than N, while those in the right subtree
are strictly greater than N.
CS 403, Class 19
Slide # 12
Data Types in Prolog
The primitive data types in prolog can be combined via
structures,to form complex datatypes:
<structure>::= <functor>(<arg1>,<arg2>,...)
Example In the case of binary search trees we have:
<bstree> ::= empty
| node(<number>, <bstree>, <bstree>)
node(15,node(2,node(0,empty,empty),
node(10,node(9,node(3,empty,empty),
empty),
node(12,empty,empty))),
node(16,empty,node(19,empty,empty)))
Draw this tree
CS 403, Class 19
Slide # 13
Binary Search Trees II
The Problem: Define a unary predicate isbstree
which is true only of those trees that are
binary search trees .
The Program
isbstree(empty).
isbstree(node(N,L,R)):- number(N),isbstree(L),isbstree(R),
smaller(N,R),bigger(N,L).
smaller(N,empty).
smaller(N, node(M,L,R)) :- N < M, smaller(N,L), smaller(N,R).
bigger(N, empty).
bigger(N, node(M,L,R)) :- N > M, bigger(N,L), bigger(N,R).
CS 403, Class 19
Slide # 14
Watch it work:
 ?- [btree].
 ?-
isbstree(node(9,node(3,empty,empty),empty))
.
 true ?
 yes
CS 403, Class 19
Slide # 15
Binary Search Trees III
The Problem: Define a relation which tells
whether a particular number is in a binary
search tree .
mymember(N,T) should be true if the number
N is in the tree T.
Now you try it
The Program
mymember(K,node(K,_,_)).
mymember(K,node(N,S,_)) :- K < N,mymember(K,S).
mymember(K,node(N,_,T)) :- K > N,mymember(K,T).
CS 403, Class 19
Slide # 16
Watch it work:
?- [btree].
?- [mymember].
?- mymember(3,
node(10,node(9,node(3,empty,empty),empty),
node(12,empty,empty))).
true ?
yes
CS 403, Class 19
Slide # 17
Unification
Unification is a more general form of pattern
matching. In that pattern variables can
appear in both the pattern and the target.
The following summarizes how unification
works:
1. a variable and any term unify
2. two atomic terms unify only if they are
identical
3. two complex terms unify if they have the
same functor and their arguments unify .
CS 403, Class 19
Slide # 18
Prolog Search Trees Summary




1. Goal Order affects solutions
2. Rule Order affects Solutions
3. Gaps in Goals can creep in
4. More advanced Prolog programming
manipulates the searching
CS 403, Class 19
Slide # 19
Sublists (Goal Order)
 Two definitions of S being a sublist of Z use:
myappend([], Y, Y).
myappend([H|X], Y, [H|Z]) :- myappend(X,Y,Z).
&
myprefix(X,Z) :- myappend(X,Y,Z).
mysuffix(Y,Z) :- myappend(X,Y,Z).
Version 1
sublist1(S,Z) :- myprefix(X,Z), mysuffix(S,X).
Version 2
sublist2(S,Z) :- mysuffix(S,X), myprefix(X,Z).
Version 3
sublist3(S,Z) :- mysuffix(Y,Z), myprefix(S,Y).
CS 403, Class 19
Slide # 20
Watch them work:
| ?- [sublist].
consulting....sublist.pl
yes
| ?- sublist1([e], [a,b,c]).
no
| ?- sublist2([e], [a,b,c]).
Fatal Error: global stack overflow …
CS 403, Class 19
Slide # 21
Version 1
So what’s happening? If we ask the question:
sublist1([e], [a,b,c]).
this becomes
prefix(X,[a,b,c]), suffix([e],X).
and using the guess-query idea we see that the
first goal will generate four guesses:
[]
[a]
[a,b]
[a,b,c]
none of which pass the verify goal, so we fail.
CS 403, Class 19
Slide # 22
Version 2
On the other hand, if we ask the question:
sublist2([e], [a,b,c])
this becomes
suffix([e],X),prefix(X,[a,b,c]).
using the guess-query idea note:
Goal will generate an infinite number of guesses.
[e] [_,e] [_,_,e] [_,_,_,e] [_,_,_,_,e] [_,_,_,_,_,e]
....
None of which pass the verify goal, so we never terminate
CS 403, Class 19
Slide # 23