.Open 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.  I handed
out the details earlier
.See http://www/dick/cs320/prolog/Potions.htm
plus a copy of the source code.
You can download the source code here:
.See http://www/dick/cs320/prolog/potion1.plg
and then test it out.  Note if you are running `gprolog`  or
a later version of SWI Prolog then
you need
.See http://www/dick/cs320/prolog/potion1.pro
instead.  They've changed the way that `select` works:-(

Terminate Prolog  by tapping CTRL/D

. 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 
.See http://www/dick/cs320/prolog/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 `pl` to compile the program:
.As_is 	...$ pl
.As_is 	?- consult('crptarth.plg').
.As_is 	....
.As_is 	?- listing.
.As_is 	?- go.

For simpler examples of this kind of puzzle solving see
.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:
.As_is 		http://www/dick/cs320/prolog/sample1.plg
.See http://www/dick/cs320/prolog/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:
.As_is 	pl -o sample1 sample1.plg
.As_is 	sample1

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:
.See http://www/dick/cs320/prolog/sample2.plg
.See http://www/dick/cs320/prolog/sample3.plg

. Another Approach to Logic Puzzles
The previous experiment introduced you to Logic Puzzle
.See 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:
.See http://www/dick/cs320/prolog/sample4.plg
.See http://www/dick/cs320/prolog/zebra2.plg

.Open 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.
.Box
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?
.Close.Box

Write a file 'cones.plg' that 
defines all my favorite `scoop(Flavor)`.
.As_is 	scoop(chocolate).
.As_is 	scoop(vanilla).
.As_is 	scoop(strawberry).
Compile, run and test it with:
.As_is          scoop(Top).
(and don't forget to tap ';' to ask for each cone in turn.)

Then try two scoops of ice-cream.
.As_is          scoop(Top),scoop(Bottom).
(and don't forget to tap ';' to ask for each cone in turn.)
Now try the following simple Prolog loop....
.As_is          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 `scoop`s... to generate
all combinations:
.As_is          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.
.As_is 		cone(Top, Middle, Botttom):-scoop(Top), scoop(Middle). scoop(Bottom).
Compile and run.  Test it like this:
.As_is 		cone(Top,Middle,Bottom),
.As_is 		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:
.As_is 		:-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:
.As_is 		cone(A,B,C), assert(   a_cone(A,B,C)  ).
.As_is 		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:
.As_is 		bagof(X, scoop(X), Scoops).
.As_is 		bagof(X+Y, (scoop(X), scoop(Y)), Scoops).
You can count the number of cones easily by
using the `length(List, Length)` predicate:
.As_is 		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:
.As_is 		count(N):-bagof(A+B+C, cone(A,B,C), Cones), length(Cones, N).

.Close Combinatorics
.Open Programs that Learn
Prolog programs can grow as they run!  The predicate
.As_is 		assert(Fact)
puts the query into the data base. The predicate
.As_is 		assertz(Fact)
puts the item at the end of the data base.
.As_is 		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:
.As_is 		:-dynamic(functor/arity).
where `functor` is the name of the fact and `arity` is the number of arguments:
.As_is 		:-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:
.As_is 		clause(Head, Body).
searches for a rule of form:
.As_is 		Head:-Body.

. A Trivial Example
Here is an simple example.  Suppose we already have a predicate
that finds the fourth power of a number:
.As_is 	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:
.As_is 	fourth(X,X4):-square(X,X2), square(X2,X4),
.As_is 		assert_if_new(fourth(X,X4)).
The resulting program is in
.See http://www/dick/cs320/prolog/4th.plg
download this file and start up Prolog with this program.
Repeatedly try queries like:
.As_is 	fourth(2, F).
and and do a listing after each one... see how it accumulates data.... 

.Open 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:
.As_is 	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:
.As_is 		cones(0).
To count a cone we:
.Box
	Extract the old value out of the data base (cones(Old))
	Add one to the Old number we found
	Re-assert the new value of the number of cones.
.Close.Box
Like this
.As_is 	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:
.As_is 	cone(A,B, C), count, fail.
.As_is	cones(Number).

. Prolog List Processing
See Sebesta pages 502..507 first.
Ask Prolog for a listing of
.As_is 	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
.See http://www/dick/cs320/prolog/functions.plg.
along with a sample definition of a function:
.As_is 	function(square(X),X*X).
You can then see how '=', 'is', and 'es' differ:
.As_is 	Y = square(3).
.As_is 	Y is square(3).
.As_is 	Y es square(3).
You can add a new function to the definitions by asserting it:
.As_is 	assert(function( cube(X), X*X*X)).
or like this:
.As_is 	assert((function( abs(X), X) :- X>=0))).
.As_is 	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 
.See http://www/dick/cs320/prolog/rational.plg
I programmed an
assignment like 'is', called 'es', which treats
.As_is 		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
.See http://www/dick/cs320/prolog/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 
.See http://www/dick/cs320/prolog/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.
.As_is	set(x,1)
.As_is	print_ram.
.As_is	set(x,3)
.As_is	print_ram.
.As_is 	set(y,2)
.As_is	print_ram.
.As_is 	let(z,x+y).
.As_is	print_ram.


. The `univ` or `=..` predicate.
What happens to these queries:
.As_is 	(a+b)=..X.
.As_is 	tree(left,right)=..X.
.As_is 	Y=..[power, x, 2].
.As_is 	a*b+c =.. [F, X, Y].
.As_is 	a*(b+c) =.. [F, X, Y].
.As_is 	help(univ)
Describe what 'univ'/=.. is supposed to do.

. Faster Factorials by Caching Values
Look at 
.See http://www/dick/cs320/prolog/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:
.See http://www/dick/cs320/prolog/src/
This is precisely what I downloaded, uncompressed, unarchived,
compiled, and installed so that you could do these labs.

Note.
.Set
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.
.Close.Set

.Open 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 
.See http://www/dick/cs320/prolog/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
.See http://www/dick/cs320/prolog/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
.See http://www/dick/cs320/prolog/for.plg
.See http://www/dick/cs320/prolog/for.example.plg
.See http://www/dick/cs320/prolog/for.complex.plg
. Magic squares revisited
See 
.See http://www/dick/cs320/prolog/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
.See http://www/dick/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?
.See http://www/dick/cs320/prolog/barber.plg

. Parallel Processing
.See http://www/dick/cs320/prolog/cobegin.plg

. Gries Coffee Can Problem
Actually it is Dick Scholten's coffee bean can...
.See http://www/dick/cs320/prolog/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.
.See http://www/dick/cs320/prolog/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.
.See http://www/dick/cs320/prolog/pp.plg

. Quick Sort made Simple
The following experiments show
how simple sorting can be.
Two different examples...
.See http://www/dick/cs320/prolog/qsort.plg
.See http://www/dick/cs320/prolog/qsort2.plg
In both of these you call the sort like this:
.As_is 		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
.As_is 		help(sort).
.As_is 		help(setof).
or trying out
.See http://www/dick/cs320/prolog/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?".
.See http://www/dick/cs320/prolog/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:
.See http://www/dick/cs320/prolog/sum_squares.plg

. Genealogies
Here is an excellent example
.See http://kti.ms.mff.cuni.cz/~bartak/prolog/genealogy.html
given to me by Jonathan Wheeler.  It grows a simple Prolog
program for handling family trees and such.  Try it out!

.Close More sample Programs
.Close If you have Time
. 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:
.See http://www/dick/samples/prolog.html

Also see a selection of messages from the SWI-Prolog
mailing list
.See http://www/dick/cs320/prolog/mbox

The SWI manual (with some GIFs missing) is in
.See http://www.csci.csusb.edu/dick/cs320/prolog/SWI-prolog/
and the Gnu Prolog manual is at
.See http://www.csci.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...
.Set
 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.
.As_is 	End of line does not count.

 Prolog is highly case sensitive.  Variables all have a capital letter first.
.As_is 	X is a variable - with an unknown (as yet?) value.
.As_is 	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
.As_is 		pl
 You compile a program inside Prolog by
.As_is 		consult('name_of_file').
.Close.Set
. 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`
.As_is 		EDIT=name_of_your_favorite_editor
.As_is 		VISUAL=$EDIT
.As_is 		EDITOR=$EDIT
.As_is 		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
arity::= `the number of arguments in a compound term.`.
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
.As_is 	element(Name, _, Number1), element(Name, _, Number2), Number1=\=Number2.
.Close CS320 Prolog Examples
. Check the Preparation for next class
.See ../20.html