Your task in this laboratory is to gather together some examples of Prolog solutions to problems that interest you, or that will remind you of the peculiarities of Prolog. You don't have to try every example and experiment below. You do need have between about 5 links to examples each with a comment (2 or three sentences) describing what you think is interesting about it.
Keep your Prolog notes open beside your keyboard so you can look for help when things do not work as you expect. Also see the Hints at the end of this lab.
To run the tests below use the command
swiplto execute SWI Prolog. Check out [ http://www.swi-prolog.org/ ] too see the various versions that are available. I have downloaded the Windows/MSDOS executable and run it on my laptop at home. It is the only programming language honored in this way!
Sherlock Holmes is using a computer("The Engine") to investigate the murder at the Metropolitan Club. Read the handout first....
Find and download(Shift/click, and "Save as" text) a copy of
http://cse.csusb.edu/dick/cs320/prolog/metro1.plg[ metro1.plg ] You can run Prolog with UNIX command
swiplTell the interpreter to compile the facts of the case into database.
consult('metro1.plg').
^Don't forget the period.You can now investigate the murder. What happens when you input these lines?
listing(murderer).
listing(room).
listing(attire).
listing(hair).Don't forget the periods, and the case of everything is lower case.
Then try inputting this query:
murderer(X).Don't forget the periods, and the case of X.
We will now ask Prolog to show us, step by step how it solved the crime:
trace, murderer(X).Keep tapping return as each step is taken. ("creep" is not intended to be insulting... it indicates that the system is taking a very small step forward or backward).
Don't forget the '.' at the end of each query.
help.
help(1-1).
help(2-1).
help(=).
help(is).
help(member).The notation name/arity which means: the predicate with functor name and arity arguments. The signs on the arguments in the description say whether they have to be in or out arguments - whether you supply a value or if the predicate will supply the value. Sometimes either can happen as is needed.
Getting lists of helpful topics on a given subject:
apropos(list).
apropos(help).
go.You could use
edit(f).to change the function from squaring to cubing:
f(X,Y):- Y is X*X*X.Then exit the editor and see if the binary search will find cube roots.
element(Name).
element(Name, Symbol).
element(Name, Symbol, Number).I also define some properties of the atomic numbers: Is the element metallic or non-metallic, and what group and period in the periodic table is assigned to the element. There also three utility commands that print information about an element: period(Atomic_number), group(Atomic_Number), and print_element(Name_of_an_element).
The data and program are in [ chem.plg ] save/download a copy of this file. Load it into Prolog and try a query:
print_element(boron).To see how this works list the prolog program:
listing(print_element).Now try the following simple searches/queries of our knowledge base:
element(boron, Symbol, Number).
element(Name, 'F', Number).
element(Name, Symbol, 14).
element(barium, 'Ba', 56).
element(hydrogen, 'H', 24).
element(hydrogen, 'H', Nbr, Rad, Class,Normally,Melt, Boil).
element(Name, _, _, radioactive, _,_,_, _).The last of these above has several answers... tap ';' to get each radioactive element in turn. Notice the wild-card variable _.
Problem: I just typed it in and haven't checked it for errors.
Write simple Prolog queries that will detect some of the possible errors that I might have made:
Also see [ UML to Prolog ]
How does it do it? Try
listing(go).Using 'help', 'listing', and some guessing can you see how I encoded the "structure" of these stories as a grammar?
X=1;X=2;X=3....and so we can solve simple word problems by writing searches: What digit has a square of 9?
member(X,[1,2,3,4,5,6,7,8,9,0]), X*X =:= 9.
What digit has a square of 3?
member(X,[1,2,3,4,5,6,7,8,9,0]), X^2 =:= 3.
How about looking for a solution of an equation:
member(X,[1,2,3,4,5,6,7,8,9,0]), X^2-11*X+28=:=0.
But the following fails.... why?
member(X,[1,2,3,4,5,6,7,8,9,0]), X^2-11*X+28=0.
% s1(N,SN) - given a positive non zero integer number N, SN=1+2+...+N
s1(N,SN) :- N < 1, print('Error in s1'), nl, fail.
s1(N,SN) :- N = 1, SN is 1.
s1(N,SN) :- N > 1, N1 is N-1, s1(N1, SN1), SN is SN1 + N.Check for typos. Check that there are three definitions for Prolog to try - it will try each in turn. Then notice that each definition has a body that starts with a condition, and that precisely one of these conditions can be true for any given N. So only one will be selected. Can you predict what it will do?
Compile, list, test , and trace the above code.
% s2(N,SN) - given a positive non zero integer number N, SN=1+2+...+N
s2(1,1).
s2(N,SN ) :- N > 1, N1 is N-1, s2(N1, SN1), SN is SN1 + N.
s2(N, _ ) :- N < 1, print('Error in s1'), nl, fail.
Download it, and consult it, and then
go(More).Be ready for a long delay....
Of course there is a better algorithm. If you study what the program does you'll notice that it spends a lot of time generating digits and rejecting them here:
row(X,Y,Z):-d(X),d(Y), X=\=Y, d(Z),X=\=Z, Y=\=Z, X+Y+Z=:=15.Here it keeps trying different Zs until it finds one (if any) that fits the last calculation. It would be faster to calculate a single Z instead of using trial-an-error:
row(X,Y,Z):-d(X),d(Y), X=\=Y, Z is 15-X-Y, X=\=Z, Y=\=Z.Similarly, once the first two rows have been found in a 3><3 magic square it is easy to calculate the bottom row. Here [ magic3.plg ] is the improved program. Is it faster? Does it produce the same squares?
This experiment shows an important fact: The simple and obvious, logical, program may need intelligent tweaking before it is fast enough.
Write a file 'cones.plg' that defines all my favorite scoop(Flavor).
scoop(chocolate).
scoop(vanilla).
scoop(strawberry).Compile, run and test it with:
scoop(Top).(and don't forget to tap ';' to ask for each cone in turn.)
Then try two scoops of ice-cream.
scoop(Top),scoop(Bottom).(and don't forget to tap ';' to ask for each cone in turn.) Now try the following simple Prolog loop....
scoop(Top),write(Top),nl,fail.Notice how we put fail at the end of the loop, because it forces Prolog to go back and find the next alternative, and in the above, the scoop provides a choice point with 3 alternatives. 'fail' take Prolog back to the last choice point to look for another alternative... and if there are none it backtracks to the next previous choice point.
We can use the same technique with two scoops... to generate all combinations:
scoop(Top),scoop(Bottom),write(Top+Bottom),nl,fail.Also notice that we can use + in the output.... because Prolog will write X+Y without evaluating it!
Edit your 'cones.plg' file so that it defines a predicate cone(Top, Middle, Bottom) that chooses a Top, Middle and Bottom Scoop.
cone(Top, Middle, Botttom):-scoop(Top), scoop(Middle). scoop(Bottom).Compile and run. Test it like this:
cone(Top,Middle,Bottom),
write(Top+Middle+Bottom),nl,fail.
:-dynamic(a_cone/3).Try the following which generates a database of all the possible cones, ready for further computation, as long as you tap the ";" key:
cone(A,B,C), assert( a_cone(A,B,C) ).
listing(a_cone).
Prolog has some high-level commands for handling list, sets, and "bags". (A bag can have elements that occur several times). The bagof(Term, Condition, Bag) predicate is built into our Prolog and assembles a list in Bag of all Terms that fit the Condition. Load your 'cones.plg' into Prolog and try the following:
bagof(X, scoop(X), Scoops).
bagof(X+Y, (scoop(X), scoop(Y)), Scoops).You can count the number of cones easily by using the length(List, Length) predicate:
bagof(A+B+C, cone(A,B,C), Cones), length(Cones, Number_cones).You can add a definition of count to your cones.plg program:
count(N):-bagof(A+B+C, cone(A,B,C), Cones), length(Cones, N).
Modify the program to count the cones must have three different flavors.
How about 4 scoops?
. . . . . . . . . ( end of section Combinatorics) <<Contents | End>>
assert(Fact)puts the query into the data base. The predicate
assertz(Fact)puts the item at the end of the data base.
asserta(Fact).adds the Fact at the beginning of the facts.
In modern Prologs the facts and clauses in the database are assumed to be static. To allow them to be dynamic the following command has to be executed in any program that uses the assert predicates:
:-dynamic(functor/arity).where functor is the name of the fact and arity is the number of arguments:
:-dynamic(fact/1).allows new 'facts' about single objects to be asserted or retracted.
It helps to know that a fact we assert is not already in the data base. There is a special Prolog statement that checks for a the existence of a clause - rather than trying to discover if the query is true:
clause(Head, Body).searches for a rule of form:
Head:-Body.
fourth(X, X4):- square(X,X2), square(X2,X4).(try this definition out, adding anything that is missing:-)
However we want to avoid doing the same calculation twice. Instead, whenever we recalculating the old values.... Instead, each time a fourth power for an integer is found we add any new facts to the data base:
fourth(X,X4):-square(X,X2), square(X2,X4),
assert_if_new(fourth(X,X4)).The resulting program is in [ 4th.plg ] download this file and start up Prolog with this program. Repeatedly try queries like:
fourth(2, F).and and do a listing after each one... see how it accumulates data....
retract( Query )looks up a matching piece of data in the usual way, but then deletes it from the data base. The predicate
assert( Fact )puts the query into the data base. Here are some examples of how this is done.
Again in modern Prolog systems we have to set up the dynamic predicates in advance:
dynamic(functor/arity).
Can you see how it records some information on 3 students?
Notice the clever use of Prolog operators to encode grades:
cs320=a: A grade of A in CS320
cs320+b: A grade of B+ in CS320
cs320-c: A grade of C- in CS320(This may not be a good idea... but it shows you that in Prolog you can make expressions mean anything you want).
Note: If we don't use a list of grades in the record we have to have a separate set of facts linking students, courses and grades. For more on data base design see CSci480.
load_students.
list_students.
save_students.
admit(Student_number, Student_name).
dismiss(Student_number, Student_name).Notice it also needs you to have download [ students.plg ] first.
Run the ar.plg program, load the students, list them, add a new student with number 9999 and name 'Joe Coyote', list the result, and save the students. Quit Prolog and look at the result.
Study how the program is written. Notice the unfriendly user interface. Notice how simple the resulting code is. Hence a possible prototype to check out the algorithms and data structures, not a finished program.
consult('ar.plg').
load_students.to get the data online.
Add student with number 9999 and name 'Joe Coyote'. Hint. [ Admissions and Records ] above.
Give him the grade of a in cs125.
grade(9999, cs125=a).List the student records. Give Joe a grade of B+ in cs201 (cs201+b), and list the result.
Give Joe a grade of A- in CS320, and check the result...
If this works, study the code and then try some other experiments.
. . . . . . . . . ( end of section A Prototype Student Data Base) <<Contents | End>>
. . . . . . . . . ( end of section Programs that Learn) <<Contents | End>>
cone(A,B,C), count, fail.The fail forces Prolog to backtrack and find another cone. We need the right definition for count. We want count to increase some hidden item of data each time is called, and we don't want it to undo anything when backtracking from the fail.
Prolog variables only have one value so we can not use them for counting (except recursively - one symbol but many variables!). We can't use a variable so we use the Prolog database: Initially we have no cones:
cones(0).To count a cone we:
count:-retract(cones(Old)), New is Old+1, assert(cones(New)).(Prolog uses the jargon word retract to mean `find the first matching rule and remove it from the data base`.)
Put together the definition of cone, scoop, cones, and count, in your cones.plg file and then test:
cone(A,B, C), count, fail.
cones(Number).
appendStudy it. Test it out. Trace it. Describe in English how 'append' works.
function(square(X),X*X).You can then see how '=', 'is', and 'es' differ:
Y = square(3).
Y is square(3).
Y es square(3).You can add a new function to the definitions by asserting it:
assert(function( cube(X), X*X*X)).or like this:
assert((function( abs(X), X) :- X>=0))).
assert((function( abs(X), Y) :- X<0, Y is -X))).
n/das a fraction with numerator n and denominator d. This shows how the ADT(class) of rational numbers is declared and can be used.
When you look at the code, notice that 'ram' is essentially a function that converts the names of variables into values. So the code must make sure that there is never more than one value for any variable.
The file also needs you to download [ functions.plg ] so that the 'let' command will work.
It uses two special Prolog functors 'assert' and 'retract' to store and retrieve values in a array called ram.
Here is a set of tests.
set(x,1)
print_ram.
set(x,3)
print_ram.
set(y,2)
print_ram.
let(z,x+y).
print_ram.
(a+b)=..X.
tree(left,right)=..X.
Y=..[power, x, 2].
a*b+c =.. [F, X, Y].
a*(b+c) =.. [F, X, Y].
help(univ)Describe what 'univ'/=.. is supposed to do.
Note.
. . . . . . . . . ( end of section Problems From the Book) <<Contents | End>>
Load the bad solution and investigate why and how it fails, using trace to help. What are the problems?
Later I produced [ lotto93.plg ] that seems to have the problem licked by using a smarter idea and a way to express a 'for loop' in Prolog.
qsort(Given_list, Variable_for_sorted_list).
help(sort).
help(setof).or trying out [ setof.plg ]
. . . . . . . . . ( end of section More sample Programs) <<Contents | End>>
. . . . . . . . . ( end of section If you have Time) <<Contents | End>>
If you want to learn the techniques used for expert systems, simulations, and half a dozen other purposes... see T Van Le's text book.
I have a page of pointers to Prolog information: [ prolog.html ]
Also see a selection of messages from the SWI-Prolog mailing list [ mbox ]
The SWI manual (with some GIFs missing) is in [ http://cse.csusb.edu/dick/cs320/prolog/SWI-prolog/ ] and the Gnu Prolog manual is at [ http://cse.csusb.edu/dick/cs320/prolog/gnu/ ] and describes how to use gprolog and all the predicates it defines.
End of line does not count.
X is a variable - with an unknown (as yet?) value.
x is the atom x
swipl
consult('name_of_file').
EDIT=name_of_your_favorite_editor
VISUAL=$EDIT
EDITOR=$EDIT
export EDIT VISUAL EDITORThe next time you login most UNIX programs will know what editor you like to use.
element(Name, _, Number1), element(Name, _, Number2), Number1=\=Number2.
. . . . . . . . . ( end of section CS320 Prolog Examples) <<Contents | End>>