Plus some notes on what you have learned.
End of the lab.
. . . . . . . . . ( end of section Introduction) <<Contents | Index>>
A version of the Binary search algorithm is defined in
[ binary.plg ]
You can test to see if it calculated the square root of 49
go.You can edit f in the program 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. How about fourth roots?
A Simple Data Base
I rapidly prototyped the data base of chemical elements
that you met in the last laboratory.
The data and program are in
[ chem.plg ]
save/download a copy of this file.
Problems: 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:
Can you fix the data base?
Using the 'member' predicate we can abbreviate
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:
But the following fails.... why?
You can also search for two digits:
member(X,[1,2,3,4,5,6,7,8,9,0]),member(Y,[1,2,3,4,5,6,7,8,9,0]), X^2+Y^2 =:= 10 *X+1.What two digit numbers does this find?
Explore other simple arithmetic puzzles based on the digits.
Summing the Number from 1 to N.
Here is a an example of adding up all the numbers from 1 to N.
Put it in a file and test it.
% s(N,SN) - given a positive non zero integer number N, SN=1+2+...+N
s(N,SN ) :- N > 1, N1 is N-1, s(N1, SN1), SN is SN1 + N.
s(N, _ ) :- N < 1, print('Error in s1'), nl, fail.
Can you write a predicate that adds up a different series: sum of squares, for example?
Generate Magic Squares
The following demonstrates the real problem with Prolog...
it can take a long time to generate a solution. The following
[ magic.plg ]
can be used to print out all 3 by 3 magic squares
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?
Write a file 'cones.plg' that defines all my favorite scoop(Flavor).
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:
Bags of Snow Cones
This continues the Ice-cream Cone scenario, but shows you a
powerful alternative to using the Prolog database for saving
a set of items for future use.
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).
Extensions to the Cones Problem
Modify your cones.plg file to count cones that have the same flavor
on the top and bottom scoops.
Modify the program to count the cones must have three different flavors.
How about 4 scoops?
. . . . . . . . . ( end of section Combinatorics) <<Contents | Index>>
A Student Records database
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).
Admissions and Records
Here is a very simple application that manipulates the student
records in students.plg:
[ ar.plg ]
It defines the following commands:
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. This is just a prototype to check out the algorithms and data structures, not a finished program.
Look at the program to record new grades in student records:
[ grading.plg ]
Save this program. You will also need your students.plg and
ar.plg file. Start up the grading.plg program and use
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. Can you improve it?
. . . . . . . . . ( end of section A Prototype Student Data Base) <<Contents | Index>>
Adding Functions to Prolog
Functions can be added to Prolog - some later generation Prologs have
them built in. I have worked out a set of rules and a new infix
operator 'es' which evaluates expressions that use user defined functions.
The necessary rules are in
[ functions.plg] .
along with a sample definition of a function:
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))).
Experiment with adding new functions.
Adding Rational Numbers to Prolog
Because Prolog stores expressions until it is forced to
evaluate them by an is or a relational operator we can easily
program Prolog with a new way to evaluate them - as long as we
give it a new name. In the
[ rational.plg ]
I programmed an
assignment like 'is', called 'es', which treats
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.
Adding RAM to Prolog
Another feature of Prolog is the absence of global variables - data stored
in locations in random access memory. The file
[ ram.plg ]
Shows how to simulate such a memory using the Prolog data base.
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.
Can you add more featrues of an imperative language?
More sample Programs
Picking lotto type numbers
My first algorithm
[ lotto.plg ]
for picking a sample of lottery picks has a bad feature....
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.
A Prototype Advising Program
The following is out of date and not useful advising system
[ compsci.plg ]
The Barber Paradox
In a certain village everybody shaves and each person is
either shaved by themselves or the barber. And
nobody is shaved by two people. Who shaves the barber?
[ barber.plg ]
Can you model another paradox in Prolog?
This solved a GRE Comp Sci problem:
[ cobegin.plg ]
Gries Coffee Can Problem
Actually it is Dick Scholten's coffee bean can...
[ coffeecan.plg ]
Cantor's Enumeration of Pairs
The following example runs through every pair of positive integers if
you run it long enough. It could be used to find whole number
solutions to equations. However it will go on forever if there
is no solution.
[ cantor.plg ]
Pretty Print a Structure
The following is used to print out a structure (a parse tree for
example) in a more readable way.
[ pp.plg ]
Quick Sort made Simple
The following experiments show
how simple sorting can be.
Two different examples...
[ qsort.plg ]
[ qsort2.plg ]
In both of these you call the sort like this:
Can you program a merge or selection sort?
Sorting in Practice
Practical Prolog programmers use the built-in sort/2
or setof/3 predicates when they want data in a
particular order. You can find out more about sort and
setof by asking prolog
help(setof).or trying out [ setof.plg ]
A Tool for Programming
This is based on a research paper in the IEEE Transactions of Software
Engineering. It shows how a lot of information about a complicated
C program can be placed in a Prolog data base and then searched to answer
questions like: "What could change the following variable?".
[ tool.plg ]
This shows how you to use the Prolog data base to do
summations that appear in statistical work. The predicate
expects a list of numbers stored as data(...). data(....). ... and
sums the squares of these numbers:
[ sum_squares.plg ]
Here is an excellent example
[ genealogy.html ]
given to me by Jonathan Wheeler. It grows a simple Prolog
program for handling family trees and such. Try it out!
. . . . . . . . . ( end of section More sample Programs) <<Contents | Index>>
element(Name, _, Number1), element(Name, _, Number2), Number1=\=Number2.
. . . . . . . . . ( end of section CS620 Prolog Examples) <<Contents | Index>>