Introduction

Check out New things on the Course Web Page

[ index.html ]

Goals

Your task in this laboratory is to look at some more examples of Prolog solutions. You shouls select one to experiment with and change the database/program in some way.

Deliverable

A Prolog example based on those below.

Plus some notes on what you have learned.

Deadline

End of the lab.

. . . . . . . . . ( end of section Introduction) <<Contents | Index>>

Binary Search

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 correctly:

 		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:

• An element with the same name as a another with a different symbol.
• Strong Hint

  ---

  1. element(Name, Symbol1), element(Name, Symbol2), Symbol1\==Symbol2.

  ---

• Elements with different names but the same symbol.

• An element with the same name as a another with a different number.
• Hint

  ---

  1. Its like the previous but use =\= to compare numbers. [ Bigger Hint ]

  ---

Can you fix the data base?

Prolog loops!

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:

 	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.

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(1,1).

  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?

Combinatorics

Ice-Cream Cones

Here is a very simple problem. It came up in an elementary school math class. It shows how the number of combinations of options gives a large number of cases to consider.

---

I like ice-cream cones with three scoops of ice-cream. I like chocolate, vanilla, and strawberry ice-cream. Any mixture of three is ok. But I want to have a different cone each time. How many different cones are there?

---

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.

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

Basics

Down load and examine the following file: [ students.plg ]

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:

 		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. This is just a prototype to check out the algorithms and data structures, not a finished program.

Grades.

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

 		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. 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/d

as 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.

	set(x,1)

	print_ram.

	set(x,3)

	print_ram.

 	set(y,2)

	print_ram.

 	let(z,x+y).

	print_ram.

Can you add more featrues of an imperative language?

More sample Programs

You can explore these as you wish, and you can probably improve most of them.

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 ] Improve it.

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?

Parallel Processing

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:

 		qsort(Given_list, Variable_result).

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(sort).

 		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 ]

Statistics

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 ]

Genealogies

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>>

Glossary

1. arity::= the number of arguments in a compound term..
2. functor::= the identifier of a structure in a term. It can appear immediately before a bracketed list of arguments, or be infixed between two arguments. It can also be prefixed and post-fixed.

   Bigger Hint

    	element(Name, _, Number1), element(Name, _, Number2), Number1=\=Number2.

. . . . . . . . . ( end of section CS620 Prolog Examples) <<Contents | Index>>

Glossary