Contents

• CS320 Prolog Examples 2
• : Harry Potter and the Poison Potions
• : A Cryptarithm Puzzle
• : Logic Puzzles
• : Another Approach to Logic Puzzles
• : Combinatorics
• : Programs that Learn
• : Check the Preparation for next class

CS320 Prolog Examples 2

Your task in this laboratory is to gather together more 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. You may change the examples on this page if you really want to.

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.

Harry Potter and the Poison Potions

Here is another logic puzzle that models the situation as a list of elements and tries out various permutations to find those that match the problem.

In the first Harry Potter book, Harry and Hermione have to solve a puzzle involving 7 potions. Here is a page with the details [ Potions.htm ] and here [ potion1.plg ] a copy of the source code.

When compiled an run you can print out a solution of the puzzle, a list of the types of potion by using 'go.'. Terminate Prolog by tapping CTRL/D.

Note. You can experiment with solving the problem without the drawing by removing the comment and the following line.

A Cryptarithm Puzzle

The following is intended to dazzle you with the sheer cleverness of Prolog. I don't expect you to duplicate this technique in this class. But I can't resist sharing it with you.

Prolog can be used to solve puzzles where you are given a sum and all the numbers have been coded as letters. The file [ crptarth.plg ] shows a clever way to this by using the fact that Prolog variables are rather like algebraic variables. They stand for blanks that need to filled in. All you have to do is generate all the possibilities and reject the ones that do not fit the rules.

Download it and use swipl to compile the program:

 	...$ swipl

 	?- consult('crptarth.plg').

 	....

 	?- listing.

 	?- go.

For simpler examples of this kind of puzzle solving see [ Another Approach to Logic Puzzles ]

Logic Puzzles

In these puzzles you try to complete the known data about a set of entities. Each entity in the puzzle has the same set of attributes, and the attribute values are not repeated. For example you may need to find the last-names of people and you know that each last-name appears once in the solution. These puzzles are also known as Smith-Jones-Robinson puzzles.

Prolog is best when you need to try out a moderately large number of possibilities against a set of given facts and rules. It has a definite problem if it has to search an infinite number of options. Trying all combinations can take much to long as well. In this case however the Prolog solution is fast enough:

 		http://www/dick/cs320/prolog/sample1.plg

[ sample1.plg ] sets up and solves a sample logic puzzle found in a magazine.

Look at the file, down load it, and then try it out:

 	swipl sample1.plg

When you use Prolog to help you solve these puzzles 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.

There are some variations on this program: [ sample2.plg ] [ sample3.plg ]

Another Approach to Logic Puzzles

The previous experiment introduced you to Logic Puzzle [ Logic Puzzles ] Another approach is to set up a data structure representing the complete solution with blanks and variables where the values are unknown. Normally this a list of entities. Each entity has the same arguments. I use the 'member(Entity, List)' to scan the entities in the "world" (List) and match up meanings for us. Here are two examples: [ sample4.plg ] [ zebra2.plg ]

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

And fix the errors in the definition of a cone. I know of two.

Put Combinations in a Database

It is possible to save the database of ice-cream cones. The program file must tell the Prolog system that there is a dynamic predicate with 3 arguments:

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

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

. . . . . . . . . ( end of section Combinatorics) <<Contents | End>>

Programs that Learn

Prolog programs can grow as they run! The predicate

 		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.

A Trivial Example

Here is an simple example. Suppose we already have a predicate that finds the fourth power of a number:

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

If you have Time

Counting Ice-cream Cones 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.

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:

---

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

Prolog List Processing

See Sebesta pages 720 to 725 first.

Ask Prolog for a listing of

 	append

Study it. Test it out. Trace it. Describe in English how 'append' works.

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

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.

The univ predicate.

This is also known as "=..". It universalizes prolog expressions.

What happens to these queries:

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

Faster Factorials by Caching Values

Look at [ factorl2.plg ] Down load it, compile, and list it. Figure out how to test it from the listing.

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://cse.csusb.edu/dick/cs320/prolog/src/ ]

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.

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

[ for.plg ] [ for.example.plg ] [ for.complex.plg ]

Magic squares revisited

See [ magic2.plg ] for an attempt to select unused values from a set of possibilities.... and so generating permutations.

Currently this has developed a bug that I can't spot...

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 every boy shaves and are either shaved by themselves or the barber. And nobody is shaved by two people. Who shaves the barber? [ barber.plg ]

Parallel Processing

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

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

. . . . . . . . . ( end of section If you have Time) <<Contents | End>>

For more on Prolog

Schnupp and Bernard have written an excellent introduction. There book 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 ]

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.

Hints

Study these hints if unexpected things happen...
• Prolog is a combination of compiler and interpreter. The compiler reads in the "program" made up of data and rules. It produces a running program which reads and interprets your input according to the compiled data.

• In Prolog you must finish each statement with a period.

   	End of line does not count.

• Prolog is highly case sensitive. Variables all have a capital letter first.

   	X is a variable - with an unknown (as yet?) value.

   	x is the atom x

• You get out of Prolog by inputting CTRL/D or 'halt.' on a new line.

• You run Prolog with the command

   		swipl

• You compile a program inside Prolog by

   		consult('name_of_file').

Default Editor

If you have a favorite editor and want to have invoked from other UNIX programs (like mail and Prolog) then add these lines to your .profile

 		EDIT=name_of_your_favorite_editor

 		VISUAL=$EDIT

 		EDITOR=$EDIT

 		export EDIT VISUAL EDITOR

The next time you login most UNIX programs will know what editor you like to use.

UML to Prolog

Speaking of data bases.... You can often do a very quick translation from a UML class diagram into a prototype Prolog data base. Each box becomes a predicate. The chemistry example had a predicate called element which would come from the UML class Element with 8 public attributes: name:atom, symbol:string, etc. . The operations would typically be written as rules. Operations that change the state of the object will need to retract the old attribute values and assert the new ones in place of the old ones. Relationships between classes can be code as: a predicate relating the two classes, a list stored as an parameter of a predicate in a class, or a single parameter identifying a unique corresponding object in the other calls. Inheritance is harder but you can write Prolog rules that attempt to find information in one predicate, and if it fails goes else where. You can also write rules that will search a series of predicates to find which one needs changing.

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 CS320 Prolog Examples) <<Contents | End>>

Check the Preparation for next class

[ ../20.html ]

( End of document ) <<Contents | Top