This page generated at Mon May 18 19:43:40 PDT 1998.

This page is part of the CS320: Programming Languages Course on the Computer Science Department's WWW Server at CalState, San Bernardino, California, USA. It was generated by Doc Dick Botting.

• CS320 Third Prolog Laboratory -- Writing Prolog "Programs"
• : Prolog Part of your Portfolio
• : Hints.
• : A Real C Program
• : Check my Database
• : Dates again
• : Record a fact for future use.
• : From the Book: A family database
• : Simple Loops and Combinations
• : Listing and Counting Combinations
• : Counting from First Principles
• : Extensions to the Cones Problem
• : How about pizza?
• : Lists and Sets in Prolog
• : An Interesting number
• : Divisbillity etc
• : A Classical Algorithm
• : Solve a Puzzle
• : Do something for another class
• : More sample Programs
• : : Picking lotto type numbers
• : : For loops in Prolog
• : : Magic squares revisitted
• : : A Prototype Advising Program
• : : The Barber Paradox
• : : Parallel Processing
• : : Gries Coffee Can Problem
• : : Cantor's Enumeration of Pairs
• : : Pretty Print a Structure
• : : Quick Sort made Simple
• : : Sorting in Practice
• : : A Tool for Programming?
• : : Statistics?
• : For more on Prolog
• Index of defined terms etc.

CS320 Third Prolog Laboratory -- Writing Prolog "Programs"

Do as many of these experiments as you have time for. If you want play around with the other samples listed below. You can earn points by (1) posting comments, questions, and answers on the class BBS, and (2) preparing a Prolog Portfolio that shows some interesting Prolog examples.

Prolog Part of your Portfolio

The Prolog part of your portfolio is worth 25 points maximum. In this part of the Portfolio a pointer to a piece of your own Prolog is worth a max of 5 points(max), and pointers to other people's work will be worth 4 points each - as long as your comments make it clear whose work it is. Your comments about the work you point to are worth (4) four more points as long as they are clearly your own expression of your thinking about the code. The comments can be text or graphic form...(same points either form)

Hints.

---

1. Keep your lab manual beside you and open to the Prolog pages.

2. We have online documentation for Prolog in my samples of formal documentation directory [ prolog.html ]

3. If your .profile sets up EDITOR, EDIT and VISUAL variables in your UNIX environment you can access your favorite editor without leaving Prolog, Mail, etc.

4. If you need to review Earlier work see [ lab1.html ] and [ lab2.html ] There is a good review of Prolog data structures at [ facts.html ]

---

A Real C Program

The time has come for you to see an industrial size C program.... the Prolog Source Code. Explore this a little... before you start the lab: [ http://www.csci.csusb.edu/cs320/prolog/src/ ] This is precisely what I downloaded, uncompressed, unarchived, compiled, and installed so that you could do these labs.

Note.

Don't try to understand a large program like this. It would take you several weeks full time work to understand it all. More importantly, working with it does not mean understanding how the compiler stores the syntax tree! Even maintaining a program this big means that you only work on a small part at a time. In a well designed program, you can understand it one small part at a time.

Check my Database

I have just typed in a database describing the chemical and physical properties of the elements...(most of them). Each element has a record structure that lists
1. Its name - an atom
2. It's chemical symbol - an atomic string with a capital letter and and optional lower case letter
3. It's Atomic number
4. Whether it is 'radioactive' or 'not radioactive'
5. What type of element is it: metal, nonmetal, alkali, rare_earth,...
6. What its normal state is (at 0C, and normal pressure...)
7. Its Melting point(MP) in Centigrade
8. Its Boiling point(BP) in Centigrade

End.
I also define some abbreviations for getting an elements Name, or to get its element's name and symbol, or to relate name, symbol, and number:

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

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:

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

  ---

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

  ---

• An element with the same name as a another with a different number.
• Hint (its like the previous but use =\= to compare numbers.

  ---

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

  ---

• An element with the same number as a another with a different name.
• An element with the same number as a another with a different symbol.
• An element with the same symbol as a another with a different name.
• An element with the same symbol as a another with a different number.
• A radioactive element with atomic number less than 80.
• Any element whose boiling point is greater than its meting point.
• Any solid that melts or boils at a temperature less than 0C
• Any gas that whose boiling point is less than 0C
• Any liquid whose melting point is above 0C
• Any other errors...

Dates again

At the start of lab2 [ lab2.html ] I showed you how to create a file that expressed facts about months. I stopped with:

---

To record data about months. For each month we need its number, its long name, its short name, and number of days in it. Make a file that starts:

 	% month(Number, Long, Short, Days)

 	month(1, 'January', jan, 31).

 	...

 	month(12, 'December', dec, 31).

However, the month of February has a problem.....

---

The problem with February is that its length depends on the year. That means Prolog needs to know what year it is, so that we can calculate the number of days in February. So let us suppose that the user has already defined the year as a fact:

 	year(1998).

(by using assert(year(1998)).).

Then

 	Year(N)

will set N to the year for us and we can use it to find out whether February has 28 or 29 days.

 	% month(Number, Long, Short, Days)

 	month(1, 'January', jan, 31).

 	month(2, 'February', feb, 28):-

 		year(N),

 		( N mod 4 =:=0, N mod 100 =\=0

 		; N mod 400 =:= 0

 		).

 	month(2, 'February', feb, 29).

 	...

 	month(12, 'December', dec, 31).

We can mix and match simple facts and more complex clause in a set of definitions.

Prepare a file "months.plg" based on these hints and test it out. I think I got the formula for leap year right... but check it!

(added later.... And also check for other stupid errors....:-)

Record a fact for future use.

This continues the date problem.

Asking our user to type:

	assert(year(1998)).

is not friendly.... so we might add to the "months.plg" the following definition (which is less than perfect!):

 	set_year:-write('Input the year ending with a period: '), read(Year), assert(year(Year)).

Compile and run this and test it.... (use 'listing.' to see the data base).

Here is the catch: if you set_year twice, prolog learns that there are two years (try it!).

So we need to be able to cancel out all pre-existing year(N) records before we save the new one. The "abolish/2" predicate does this:

 set_year:-write('Input the year ending with a period: '), read(Year),

 	abolish(year,1), assert(year(Year)).

Replace the previous set_year command by the above and test it out.

Finally.... you can also define set_year(N) as a non-interactive version. Here the user supplies the year directly:

 		set_year(1998).

for example. Complete the following:

		set_year(N):-

You could then rewrite the interactive one:

  set_year:-write('Input the year ending with a period: '), read(Year),

 		set_year(N).

Prolog will let you have both forms in one program and they are called set_year/0 and set_year/1 in any documentation.

Add the two versions of set_year (set_year/0 and set_year/1) to your months.plg file and test the result.

If you like you can take this much further... setting today's date, calculating tomorrow's date,...

From the Book: A family database

Sebesta Page 567. Problems sets 3 and 4. Perhaps look at [ A Prototype Advising Program ] below, for a sample data base.

Simple Loops and Combinations

Here is a very simple problem. 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 have a different cone each time. How many different cones are there? Follow the following development...

Write a file 'cones.plg' that has a Prolog predicate that defines all possible scoop(Flavor). 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.) Also 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, only scoop provides a 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) and test it:

 		cone(Top,Middle,Bottom),

 		write(Top+Middle+Bottom),nl,fail.

Try the following which generates a database of all the possible cones, ready for further computation:

 		cone(A,B,C), assert(   a_cone(A,B,C)  ).

 		listing(a_cone).

Listing and Counting Combinations

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

and, using the length(List, Length) predicate:

 		bagof(A+B+C, cone(A,B,C), Cones), length(Cones, Number_cones).

Thank you Tracy for correcting the above!

Counting from First Principles

Suppose we wanted to count how many cones there are, but don't want to store each possible cone before we count. We want something like this:

 	cone(A,B,C), count, fail.

were we need the right definition for count. The fail forces Prolog to backtrack and find another cone. 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:i 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: Initial we have no cones:

 		cones(0).

To count a cone we:

---

1. Extract the old value out of the data base (cones(Old))
2. Add one to the Old number we found
3. Re-assert the new value of the number of cones.

---

Like this

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

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?

How about pizza?

Show how a similar approach can enumerate Pizza's at a hypothetical Pizza Place.

Lists and Sets in Prolog

Sebesta Page 567. 5, 6, 7 are interesting but are built into our Prolog already (I think). But before you list the code.... can you work out your own solution ... then compare your answer with the ones in SWI-Prolog. Make notes for portfolio/BBS.

An Interesting number

First define a predicate digit(D) that means that D is a decimal digit. Hint:

---

digit(D) if D=0 or D=1 or D=2 or D=3 or ... D=9.

---

Then express the following simple example as a single Prolog query and then see what the answers are.

  	D1, D2, D2 are decimal digits,

  and

  	X is the digit decimal number with digits D1,D2,D3,

  and

  	X is also equal to D1^3 + D2^3 +D3^3.

Note.

  	The three digit number X is 100*D1+10*D2+D3.

Finally find all 4 digit numbers whose digits, when cubed add up to them selves.

Divisbillity etc

Forsaking all other languages, can you work out the Prolog way to express the following conditions/predicates.

For all natural numbers (integers>0) X and Y:

  div(X,Y) is true if Y divided by X leaves no remainder.

Hint. apropos(division).

For all natural numbers (integers>0) X and Y:

  nodivisors(X,Y) is true if and only if

     either

        X is less than 2

     or

.As-is X is greater than equal to 2

        and

  	X does not divide Y,

        and

  	for X1 is X-1, nodivisors(X1,Y).

For any natural number N,

  prime(N) is true if and only if N has no divisors between 2 and N-1.

How about defining 'composite(N)' in terms of 'prime(N)'.

A Classical Algorithm

Although Prolog is not designed to express algorithms or to run them efficiently, it can do so. A first rough version of the Binary search algorithm is defined in //www/cs320/prolog/binary.plg Firstly test it:

 		go.

Then time bsearch (see help(time)), and then see if you can improve it.

Solve a Puzzle

Find a simple puzzle that Prolog can help you solve.

---

There is a general Smith-Jones-Robinson problem solver and a couple of helpful utilities in //www/cs320/prolog/sample2.plg In these puzzles you try to complete a data base on a set of entities. Each entity in the puzzle has the same set of attributes, but the attribute values are not repeated. For example you may need to find the last-names of people and you therefore know that each last-name appears once in the solution.

The challenge of the puzzle becomes extracting the properties of the attributes from the clues you've been given. If you miss a "given" then this algorithm may generate a solution that is not a solution of the problem.

---

Hint. Prolog is best when you need to try out a large but finite number of possibilities against a set of given. It has a definite problem if it has to search an infinite number of options.

Do something for another class

Take any problem from another class at CSUSB that strikes you s unusually easy in Prolog. Prove your point by doing it.

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.

For loops in Prolog

//www/cs320/prolog/for.plg //www/cs320/prolog/for.example.plg //www/cs320/prolog/for.complex.plg

Magic squares revisitted

See //www/cs320/prolog/magic2.plg for an example of selecting unused values from a set of possibilities.... and so generating permutations.

A Prototype Advising Program

The following is out of date and not useful advising system //www/cs320/prolog/compsci.plg Improve it.

The Barber Paradox

In a certain village every boy shaves and are either shaved by themselves or the barber. And nobody is shaved by two people. Who shaves the barber? //www/cs320/prolog/barber.plg

Parallel Processing

//www/cs320/prolog/cobegin.plg

Gries Coffee Can Problem

Actually it is Dick Scholten's coffee bean can... //www/cs320/prolog/coffeecan.plg

Cantor's Enumeration of Pairs

//www/cs320/prolog/cantor.plg

Pretty Print a Structure

//www/cs320/prolog/pp.plg

Quick Sort made Simple

The following experiments show how simple sorting can be: Two different examples... //www/cs320/prolog/qsort.plg //www/cs320/prolog/qsort2.plg In both of these you call the sort like this:

 		qsort(Given_list, Variable_for_sorted_list).

Exercise - modify either of the above so that instead of sorting numbers into increasing order they can sort a list of any terms into any order. The call would become:

 		qsort(Given, Goal, Order).

where Order would be the name of a predicate with two arguments, that is true precisely when the two arguments are in the right order, so

 		qsort(Given, Goal, <).

should work.

More advanced exercise....

 		qsort(Given, Goal, lambda([Var1,Var2], Expression)).

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?

//www/cs320/prolog/tool.plg

Statistics?

//www/cs320/prolog/sum_squares.plg

. . . . . . . . . ( end of section More sample Programs) <<Contents | Index>>

For more on Prolog

Schnupp and Bernard have an excellent introduction and it is in the CSUSB library.

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 ]

. . . . . . . . . ( end of section CS320 Third Prolog Laboratory -- Writing Prolog "Programs") <<Contents | Index>>

• 2, 'February', feb, 28 (Label)
• N (Label)
• which is less than perfect! (Label)