Check out New things on the Course Web Page

[ index.html ]

Previous

[ 17.html ]

Preparation

Pages 211..222

Topics

Lab Experiences

[ lab17.html ]

Set Operations

The definition of member on page 211 is part of our SWI Prolog. Try this

 		prolog

 		listing(member).

The definitions on page 212 of subset, diff, intersection, union, card may or may not be part of our Prolog. Use listing to find out before you write your own definitions (in a file).

Language Constructs

The code at the bottom of page 213 is best put in a file and then loaded into Prolog.

I have defined the arithmetic of fractions in [ rational.plg ] but this is a more complex example involving finding Greatest Common Divisors and infix expressions.

The code on page 215: temp is interesting, but might be faster if they used cut! But this is not in our text book. See Cut below.

I prefer my own versions of factorials and for loops: [ factorial.plg ] [ factorl2.plg ] [ for.plg ] [ for.example.plg ]

page 217 has gcd and fibbonaci...

Conclusion

Cut

This is an advanced Prolog topic and can be skipped. Click Questions if you don't intend to pursue Prolog any further.

The Prolog cut adds an 'else' to Prolog. The member predicate defined in the book and used in our SWI Prolog will find every member of a list in turn:

 		member(X, [1,2,3,1]).

will find "1" twice! This is because a series of definitions like

 		p:-q1.

 		p:-q2.

 		etc

is like this code

 		if(q1) p;

 		if(q2) p;

 		etc

and so after q1 has succeeded prolog goes onto test q2.

To get something like

 		if(q1) p;

 		else

 		if(q2) p;

 		else

 		etc

we use a cut. This symbolized by an exclamation mark "!"

 		p:-q1, !.

 		p:-q2, !.

 		etc

Notice the strange syntax ",!". It is called a cut because it cuts off branches from the search tree.

Here is an example

 		temp(T, freezing):- T=<32, !.

 		temp(T, cold    ):- T=<45, !.

 		temp(T, cool    ):- T=<60, !.

 		temp(T, mild    ):- T=<80, !.

 		Etc.

This moves Prolog closer to procedural programming and so makes some programs faster. You need to think about the logic you want before you use it. "Is this a case where it is either-or with no and?".

Another point: there is more to cuts than I've explained here including the difference between blue cuts and red cuts. The whole topic is beyond this introduction to Prolog.

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

Questions

Explain the Fibbonaci Program

The Fibbonaci program has three parts:

Call	Condition	Response
fib	-	Asks you to input an upper bound for the Fibbonaci numbers to be printed. And calls fib(0,1, UpperBound).
fib(X,Y,U)	Y>U	Print X because Y is too big.
fib(X,Y,U)	-	Prints X, and calls fib(Y, Y1) where Y1 is X+Y.

So X and Y are two numbers in Fibonacci's series that are added to give the next one in the series.

Explain fact on page 215

First there is a dash where there should be a minus sign. Second the method chosen to work out the factorial seems a bit weird. Given a call like fact(4, F) it calls fact(4-1, F) which matches the rule for fact(A - B, F) which calculates 4-1 = 3 and calls fact(3,F). This, in turn, calls fact(3-1)...... I prefer my own solutions above.

What is Pattern Matching in Prolog?

Prolog uses unification to match variables to values. An expression that contains variables like X+Y*Z describes a pattern where there are three blank spaces to fill in named X, Y, and Z. The expression 1+2*3 has the same structure (pattern) but no variables. If we input this query

 		X+Y*Z=1+2*3.

then Prolog will respond that X=1, Y=2, and Z=3! The pattern matching is very powerful because you can match variables to expressions like this

 		X+Y=1+2*3.

and get X=1 and Y=2*3! You can also match variable to variables:

 		X+1+Y=Y+Z+2.

This sets X=Y=2 and Z=1!

The pattern matching is invoked by the "=" operator. Further, it also called into action when Prolog searches a set of definitions to pick one to call as a procedure. Here [ pat.plg ] is the example I improvised in class today.

Notice that the process also works with lists:

 		[1,X,Y,Z]=[X,Y,Z,W].

 		[X|Y] = [1,2,3,4].

Also notice that the pattern matching does not understand algebra or arithmetic. Prolog responds "No" to both of these

 		a+b = b+a.

 		1+1 = 2.

What is [_|Y] in the member function definition on page 211

The "_" is a wild card. It can stand for any item of data. It matches anything.

 		member(X, [_|Y]):-member(X,Y).

means that Prolog will match the second argument to a list. Try

 		[_|Y] = [1,2,3,4].

and Y is [2,3,4] for example. The effect is to make member search in the rest of the list after trying the first item.

The 'nl' command outputs the new line, is there a command for carriage return and other ASCII characters?

I don't know of a command that outputs a carriage return. But Prolog converts strings like "aba" into lists of ASCII codes:

 		"abc"=[97,98,99]

and the put_code(_) command outputs the character for the code. Try

 		apropos(character).

to find out all the character handling procedures in SWI Prolog.

Why do we have immediate and non-immediate commands, and how do they differ?

Immediate commands access the data base and are intended to be queries. Non-immediate commands are meant to define a database. An example is a definition:

 		ppp:-q1,q2,q3, ... .

what has no meaning as a query but is almost always put into the data base instead. However you can add it to the data base by something like

 		assert((ppp:-q1,q2,q3,....)).

Some Prologs require the extra parentheses shown above.

The benefit is that the database can be compiled into good fast code because it is not changed very much when the program is running.

Since Prolog has a Data Base can we share and maintain consistency between users?

No. Prolog relies operating systems to do this. There is no reason why we shouldn't use Prolog as a front end to access a relational data base. It make an interesting project to drive an SQL server from Prolog. SWI doesn't do this.

What is the difference between Tail and nonTail Recursion?

In tail recursion the recursive call is always made just before the procedure exits: the last step. For example:

 		tail_recursion(X):- blah(X), whatever(X,Y), Y<X, tail_recursion(Y).

When a recursive call is not last we don;t have tail recursion.

If you think about it, tail recursive calls can be implemented very efficiently because they can reuse the current stack frame or activation record rather than pushing a new one, filling it with data, doing some computation, and popping it. So tail recursion is often a fast option.

In Prolog is there and control structure other than if-then-else?

Just sequence and recursion. Even the else part of an if is frowned upon!

What is the difference between popping a stack and dequeuing queue?

Nothing. Al that matters is if the insert and deletion operators are on the same end of the sequence (a stack) or opposite ends (a queue).

Give examples of counting loops!

[ factorial.plg ] [ factorl2.plg ] [ for.plg ] [ for.example.plg ]

Give examples of a conditional loop!

It is wiser to use recursion.

Condition controlled loops tend to look like this:

 		ppp(...):-.... Condition, Body, fail.

What are the lower case letters in member(X, [p,7,d,2,set,7.8])?

They are meaningless constants. The numbers a meaningful constants. However, with care, we can program meanings into constants.

Explain the trace, member(...) on page 211!

I have not been able to duplicate the trace that is in the book. I am therefore also confused by it.

What is the number in traces?

It shows the height of the runtime stack as Prolog is executed. I'm not sure why we start with 6 activation records on the stack in many cases however.

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

Next

Presentations [ projects.html ] and [ 19.html ]

Laboratory

[ lab18.html ]

. . . . . . . . . ( end of section CSci620 Programing Languages -- 18 -- Goodbye, Prolog!) <<Contents | Index>>

Glossary