Please use the alphabetical Index, Contents List, and your browsers search feature to find what you need.

This page generated at Mon May 18 19:43:30 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.


Contents


    CS320 second Prolog Lab - Definitions

    Remember

    Hints

    A Simple Predicate

    In Prolog, a program is a set of definitions of predicates. Here is start of a file that defines the relationship between the number of a month and the name of the month (in lowercase letters). As in all good programs the first line is a short comment.
     	% --------- month(Number, LongName). ---------
     	month(1, january).
     	month(2, february).
     	month(3, march).
     	...
    Carefully prepare a file called months.plg that has the above lines plus nine (9) more (months 4,5,6,7,8,9,10,11,12). Check to make sure that there is a period at the end of each definition.

    Start up prolog

     	pl
    and ask prolog to compile your file:
     	consult(months).
    (don't forget that period!)

    List the information about month:

     	listing(month).
    You can now use this data in many ways.

    First, it can test to see if something is a particular month:

     	month(1,january).
     	month(2,january).

    Second, it can test whether a number or atom is ANY month. Because _ matches any argument value at all:

     	month(1, _).
     	month(12,_).
     	month(13,_).
     	month(_,january).
     	month(_,janember).

    Third, month can be used to generate the name given the number, as long as you give it a variable like X to put it in:

     	month(1, X).
     	month(2, X).
     	month(13,X).
    OR Vice versa you can generate the number from the name:
     	month(N, february).
     	month(N, march).
    OR, even be used to generate a whole series of months:
     	month(Number, Name).
     			(tap ';' after each pair)
    OR, a series of names, with no numbers:
     	month(_, Name).

    How about the summer months:

     	month(N,X), N>3, N<6.
    Or a pair of months:
     	(X=january; X=march), month(N,X).

    Notice the leverage:

     	One set of data, many ways to use it.

    Something to think about: How would you record a set of facts about three or more items of data, for example a month has a number, a long name, a short name, and a number of days.

    Right! Make a file that starts:

     	% month(Number, Long, Short, Days)
     	month(1, 'January', jan, 31).
    However, the month of February has a problem..... we will come back to that real soon.

    Functions R not Us

    Try these and you will realize that Prolog does not have functions:
     	X=square(5).
     	X is square(5).
     	square(5) :- 25.

    Prolog can not declare a function like this C/C++ function:

     	int square(int x){return x*x}
    Instead we must use something like the Prolog version of:
     	void square(int x, int&y){ y= x*x; }
    instead. So Functions become predicates in Prolog.

    Make a file called powers.plg that has the following line

    	square(X,Y) :-  Y is X*X.
    Compile it and run it [ Hints ] and then you can try these ok:
     	square(5,25).
    or
     	square(5,Y).
    or
      square(5,Y), square(Y,Z), square(Z,W).
    but the following go wrong:
      square(X, 25).
      Y=square(5).
      Y is square(5).

    Return to your powers.plg file, can you define something called cube that helps you evaluate cubes?

    You might like to try some other powers, and arithmetic functions.

    Definitions with Many Answers

    Prolog lets you store definitions of predicates that work very like 'void functions' or procedures that set values into variable, but with two twists: they will supply many different answers, and they can also be used a conditions and tests. For example a predicate that is true of 1,2 and 3 only:
     	a(X) :-  X=1; X=2; X=3.
    This will first generate X=1, and if that is rejected then it backtracks. This means it abandons X=1 and looks for another alternative. Then it tries X=2, and if this fails, it backtracks and tries X=3.

    Create a file called 'choices.plg' that has the above line in it. This give a(X) the chance to choose three different values for X, X=1 or else X=2 or else X=3.

    Compile it.... and then try things like the following:

     	listing(a).
     	a(1).
     	a(2).
     	a(3).
     	a(4).
     	a(zebra).

    Then we can use it to generate all the values that fit....

     	a(X).
    (tap ';' to get all the possible X's in turn).
     	a(Y).
     	a(X),a(Y),a(Z), 5 is X + Y + Z.

    Alternative branches make if-then-else

    The file [ abs.plg ] defines two predicates that can be used to calculate the absolute value of a known number:
     		remove_sign(Known_number, Absolute_value).
     		absolution(Known_number, Absolute_value).
    The absolute value of X is either X or -X and is always >= 0.

    Down load, compile, and try these out. Look at the file. Do both versions work? Which is like structured programming and which is like declarative programming?

    Alternative Definitions can make Many Choices

    What happens if you define the same thing several times? C/C++ don't like it. Prolog accepts all them as different possible solutions! Edit your choices.plg file and add three lines:
     		b(X) :- X=1.
     		b(X) :- X=2.
     		b(X) :- X=3.
    Save, compile, load and run.... and list both a and b:
     		listing(a), listing(b).
    Now check that
     		b
    behaves just like
    		a

    Summing the Number from 1 to N.

    Normally you want Prolog to find a single solution - especially when your predicate is implementing a function. However, different values might be calculated different ways. Here is the simplest example of a common form of such a Predicate. Input this into a file called "summer.plg":
     	% s1(N,SN) - given a positive non zero integer number N, SN=1+2+...+N
     	s1(N,SN) :-  N < 1, print('Error in s1'), nl, fail.
     	s1(N,SN) :-  N = 1, SN is 1.
     	s1(N,SN) :-  N > 1, N1 is N-1, s1(N1, SN1), SN is SN1 + N.
    Check for typos. Check that there are three definitions for Prolog to try - it will try each in turn. Then notice that each definition has a body that starts with a condition, and that precisely one of these conditions can be true for any given N. So only one will be selected. Can you predict what it will do?

    Compile, list, and test the above code.

    Summing 1 to N again

    The precious exercise worked but is more like Ada/C/C++/LISP/Pascal than Prolog. Here is a more stylish program... Compare it with the previous. Put it in a file and test it.
      % s1(N,SN) - given a positive non zero integer number N, SN=1+2+...+N
      s1(1,1).
      s1(N,SN ) :-  N > 1, N1 is N-1, s1(N1, SN1), SN is SN1 + N.
      s1(N, _ ) :-  N < 1, print('Error in s1'), nl, fail.

    Later we will make a final improvement.

    Putting several definitions together

    This is a simple example of how you might develop a Logic Program one simple assumption at a time. In this case, we will develop a predicate that lets us add up all the squares from 1 until a particular number N.

    Firstly recall we can not define functions in Prolog, we must define predicates... so let us invent a predicate with two arguments: the number and the sum of squares from 1 to that number. Here is a comment to add to your file powers.plg

     	% s2(Number, Sum_Squares)
    That is a start, now we think of something we know for sure... when N is 1 then the sum of all squares from N to 1 is 1:
     	s2(1,1).
    we think of another simple assumption we might make, that when N is negative or zero then there is no answer:
     	s2(N, _) :-  N=<0, print('Silly Sum Squares'), fail.

    How about s2(2, S)??? You could write:

     	s2(2, 5).
    but that is not going to be too helpful... so why not
     	s2(2, S2) :-  S2 is 1+2*2.
    Its a pity we can't use square(N, S)!

    But we can! So junk the above s2(2,S2) and put:

     	s2(2, S2) :-  square(2, Sq2), S2 is 1 + Sq2.
    Here is the next special case:
     	s2(3, S3) :-  square(3, Sq3), s2(2, S3), S3 is S2+Sq3.
    Notice that in s2(2,S2)
     	1
    is the sum of squares from 1 to 1 and so would be produced by
     	s2(1,S1).

    So... You may be able to work out the general case, but first lets just write out some more special cases to get the pattern right:

     	s2(2, S2) :-  square(2, Sq2), s2(1, S2), S2 is S1+Sq2.
     	s2(3, S3) :-  square(3, Sq3), s2(2, S2), S3 is S2+Sq3.
     	s2(4, S4) :-  square(4, Sq4), s2(3, S3), S4 is S3+Sq4.
     	s2(5, S5) :-  square(5, Sq5), s2(4, S4), S5 is S4+Sq5.

    You might want to stop, compile, and test the above, or if you see that it is ok, look at the generalized form in the code below:

    	square(X,Y) :-  Y is X*X.
     	% s2(Number, Sum_Squares)
     	s2(1,1).
     	s2(N, _) :-  N=<0, print('Error in Sum Squares'), nl, fail.
     	s2(N,SN) :-  N>1, square(N, SqN), N1 is N-1, s2(N1, SN1), SN is SN1+SqN.
    Compile, run, list, and test!

    Factorials

    Prolog permits (and perhaps over-uses) recursion. But how else could you explain to a logical idiot what a factorial was? I have two solutions on file - factorial.plg and factorl2.plg. The second one is sophisticated and for those who want to become Prolog gurus.

    Look at [ factorial.plg ] down load it, compile, and list it. Figure out how to use it from the listing.

    Sebesta Chapter 14

    Now is an excellent time to try all the examples in Sebesta What difference does the case of an atom matter (X vs x for example).

    In Particular the one on page 550 is a good place to start...

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

    You can now look at what Dr. Murphy told the SDI people: [ joke.plg ]

    Of course their is a better algorithm, and it can be written in Prolog. A more complex problem is solved quickly below [ A Cryptarithm Puzzle ]

    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.

    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 existance of a clause - rather than trying to discover if the query is true:

     		clause(Head, Body).
    seaches 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....

    Another example: LEarning all pathes in a Maze

    Suppose we start with a few simple facts about paths in a maze. Solving the maze is a matter of stringing a series of moves together, and we have a data base of moves. Then:
    1. A path can be made of a single move.
    2. A path can start with a single move and end with any path.

    End.
    [ maze.plg ] Look at this first then save it(download it) and load it into Prolog. It defines a query
     		go(Path).
    input this and repeatedly tap the semicolon key and watch the paths being discovered. The list the program (listing.) and see that the paths have been added to the data base. Now try the 'go' command again... and it generates more paths, that are added to the data base. In this maze the process now stops adding paths. In other mazes it can go on forever.

    Exit from Prolog. Use your favorite editor to modify the maze and test out the program. There may be bugs.

    . . . . . . . . . ( end of section Programs that Learn) <<Contents | Index>>

    Programs that Modify the data base

    A common programming technique in Prolog is to read in a data base and modify it before returning it to the data base. The predicate
     		retract( Query )
    looks up a matching piece of data in the usual way, but then deletes it from the data base. The predicate
     		assert( Fact )
    puts the query into the data base. Here are some examples of how this is done.

    A Student Records database

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

    Note: If we don't use a list of grades in the record we have to have a separate set of facts linking students, courses and grades. For more on data base design see CSci480.

    Admisions 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. Hence a possible 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.

    . . . . . . . . . ( end of section Programs that Modify the data base) <<Contents | Index>>

    . . . . . . . . . ( end of section CS320 second Prolog Lab - Definitions) <<Contents | Index>>

    If you have Time

    How to Write Bad Science Fiction

    Find, download and test out the 1950-style sci-fi pulp-fiction processor that is in [ story.plg ]

    How does it do it? Try

     	listing(go).
    Using 'help', 'listing', and some guessing can you see how I encoded the structure of these stories?

    A Cryptarithm Puzzle

    The following is intended to dazzle you with the shear 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 try using Q:

     	...$ Q crptarth.plg
     	....
     	?- listing.
     	?- go.

    Prolog backtracking

    Create a file 'abc.plg' with the following definitions in it:
            abc(a). abc(b). abc(c).
            x(X) :- (X=a; X=b; X=c).
            y(X) :- abc(X).
    Study pages 551..552 to see how traces and backtracking work. Turn on the tracing on 'abc' by 'trace(abc)'. What do each of the following queries produce (and why?)
            trace(abc),abc(a).
            trace(abc),abc(c).
            trace(abc),abc(b).
            trace(abc),abc(x).
            trace(abc),abc(X).
    How many different solutions to abc(X) are there? Now compare with:
            x(X).
            y(Y).
            x(X),   y(Y).

    Prolog backtracking with cuts

    Take your 'abc.plg' file and add the following definition:
    	xyz(a) :- !.
    	xyz(b) :- !.
    	xyz(c) :- !.
    What do the following queries produce (and why?)
            xyz(a).
            xyz(b).
            xyz(c).
            xyz(x).
            xyz(X).
    How many different solutions to xyz(X) are there? How many different solutions to abc(X) are there? How does the ! change the meaning of abc?

    Summing 1 to N With a cut!

    The effect of the ! is stop Prolog entering another alternative. It can simplify some programs and speed up others. The previous [ Summing 1 to N again ] worked. Here a version that use the cut operator ! to simplify the code further. Put it in a file and test it.
      % s1(N,SN) - given a positive non zero integer number N, SN=1+2+...+N
      s1(1,1) :- !.
      s1(N,SN ) :-  N > 1, !, N1 is N-1, s1(N1, SN1), SN is SN1 + N.
      s1(N, _ ) :-  !, print('Error in s1'), nl, fail.

    Happiness and tom

    A simple example has been encoded into Prolog in [ happy.plg ] To run this get your own copy and then input the unix command
     	$ Q happy.plg

    Alternately get your own copy and run prolog by

     	pl
    The prolog command ?- consult(happy). loads the file.

    This is a simple model of what makes simple people happy. A query like ?- happy(X). will list all the happy people.

    Now list the facts:

     	listing.
    Here are some more queries to try out:
     	happy(dick).
     	happy(Dick).
     	has(X,beer).
     	has(tom, X).
     	has(X,Y).

    Prolog List Processing

    See Sebesta pages 502..507 first. Ask Prolog for a listing of
     	append
    Study it. Test it out. Trace it. Describe in English how 'append' works.

    A Logic puzzle

    Sample1.plg in my cs320/prolog directory [ sample1.plg ] sets up and solves a sample logic puzzle (Smith-Jones-Robinson puzzles) found in a magazine.

    Look at the file and then try it out:

     	pl -o sample1 sample1.plg
     	sample1

    There are some variations on this program: [ Logic Puzzles ]

    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 or =.. predicate.

    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.

    Logic Puzzles

    [ sample1.plg ] [ sample2.plg ] [ sample3.plg ]

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

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


Labels and Definitions in Alphabetical Order