Sign in to follow this  

Prolog (and school) - I'm about ready to snap

This topic is 3666 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I am taking a course this semester that is about programming languages. I have two weeks left in the course, and one assignment left before the final exam. The last part of the course has been on Prolog, and I am really struggling with it. The instructor can't teach worth crap, and the resources (ie: textbook) we have and the notes (which are pretty much regurgitated from the textbook) are also crap. So, does anyone have any good resources for learning prolog? I understand the basic concepts behind it, but for the life of me can't figure out the questions on the assignment. <venting> At this point I've pretty much had it with the course and the instructor. The midterm for the course (which was partially on Scheme) was the first time I have never passed a midterm in my academic history. The instructor just stands at the front of the class and drones on, basically reading from the powerpoint presentation notes that come from the book (written by the book's publisher). Its boring as heck, and doesn't offer much in the way of explanations. The only sets of examples we get are ones from the book, which usually do a piss-poor job of explaining things. I've seriously had enough of this. The assignment that is on Prolog is due on Tuesday, which doesn't give me much time to finish pulling out my hair. The other retarded thing is we are supposed to use something called "BP" - a prolog interpreter on the linux machines at school. One of the students who started working on the assignment this past week discovered that it wasn't installed on the systems like the professor had said it was. The version that they did end up installing for everyone to use was a very old version (ie: 1996), which was broken and wouldn't work half the time. So now on top of all the other crap I have to deal with, I would like to find a decent prolog interpreter that I can run on my windows machine at home. </venting> Any assistance or encouraging words would be very welcome at this point.

Share this post


Link to post
Share on other sites
There is GNU Prolog which has an interpreter and has been sufficient for my needs in my experimentation with Prolog so far.

However, I can't help with any more than that since I haven't actually done anything other than experiment with it.

Share this post


Link to post
Share on other sites
This reminds me of my experiences with Prolog while I took a course in software engineering...

The two flavours of Prolog we mainly worked with were SWI and Sicstus Prolog (do you know it?) and I only passed the final test because my professor gave us a very easy one...

Links to tutorials:
Learn Prolog now!

Adventure in Prolog

Those were the two I mainly used to get an idea about prolog....


Share this post


Link to post
Share on other sites
I've used Prolog before and quite enjoyed it. I wrote Othello, Checkers, and Gomoku using it where you play against the computer's minimax AI.

I'd be happy to lend a hand, if you'll post some info on what you're being asked to implement.

Share this post


Link to post
Share on other sites
iMalc, I would greatly welcome your help. I don't want to you give me the answers, just a nudge in the right direction. (I think also posting the questions will help give me a better understand of what is being asked, which will help me find the answer).

Well, the first question had to do with drawing a search tree for a statement. I more or less understand what is being asked. Basically, the search tree is a sort of diagram following the flow of the prolog interpreter, which shows how it is attempting to find an answer.

The statements that we are supposed to draw the search tree are as follows:

%facts/rules
append( [], Y, Y).
append( [H|X], Y, [H|Z]) :- append( X, Y, Z).

prefix(X, Y) :- append( X, Y, Z).
suffix(Y, Z) :- append( X, Y, Z).

%statement to draw out the search tree for:
suffix( [B], L), prefix( L, [a, b, c]).

We more or less have to do the search tree to show that the statement is indeed true.

Let me see if my understanding is correct.

The first fact basically states that appending an empty list to something is the same as that something.

The second rule states that appending a list and an object, is the same as taking that first list's tail, and the object, and append them together. Those then become the tail of the new list, with the head of the first list being the head of the new list. Because of the first rule, eventually it will hit a situation where the list is empty, and the object being appended to the list is the object itself.

The prefix rule states that something is prefixed if it is the same as taking the two things and appending them, the first being the first object, and the second being the thing that is appended to the first object.

The suffix rule is where my understanding gets shakey. Is it more or less saying that when one thing is the suffix of another, it is the equivalent of an object (for lack of a better word) that has had a known thing appended to it, and gives a known result?

I think just trying to describe it is giving me a better understanding of it.

Share this post


Link to post
Share on other sites
Quote:
Original post by Moe
iMalc, I would greatly welcome your help. I don't want to you give me the answers, just a nudge in the right direction. (I think also posting the questions will help give me a better understand of what is being asked, which will help me find the answer).

Well, the first question had to do with drawing a search tree for a statement. I more or less understand what is being asked. Basically, the search tree is a sort of diagram following the flow of the prolog interpreter, which shows how it is attempting to find an answer.
Okay. Back when I did a lot of Prolog stuff I was using some Prolog interpreter on a Mac and it allowed single step debugging, which basically showed you what it was matching, and what was already matched etc as it went. It was very handy, and even allowed my to learn how to optimise Prolog code. If the interpreter you have has got a debugging feature then it might help you similarly.
Quote:

The statements that we are supposed to draw the search tree are as follows:

%facts/rules
append( [], Y, Y).
append( [H|X], Y, [H|Z]) :- append( X, Y, Z).

prefix(X, Y) :- append( X, Y, Z).
suffix(Y, Z) :- append( X, Y, Z).

%statement to draw out the search tree for:
suffix( [B], L), prefix( L, [a, b, c]).

Cool, Okay. I've come across that append one many times. I've never seen those suffix and prefix ones though. From memory, you would probably get a warning about Z in prefix, and about X in suffix as these are unused. Normally unused things are named with an underscore.
I'm actually certain that the prefix example is wrong! I would write them both like this:
prefix(X, Z) :- append(X, _, Z).
suffix(Y, Z) :- append(_, Y, Z).

Quote:
We more or less have to do the search tree to show that the statement is indeed true.

Let me see if my understanding is correct.

The first fact basically states that appending an empty list to something is the same as that something.
Yep, that's exactly right.
Quote:

The second rule states that appending a list and an object, is the same as taking that first list's tail, and the object, and append them together. Those then become the tail of the new list, with the head of the first list being the head of the new list. Because of the first rule, eventually it will hit a situation where the list is empty, and the object being appended to the list is the object itself.
Sounds almost right. The situation it will eventually come across is that the first list is empty, in which case it immediately succeeds matching the first rule, and the last parameter is set the same as the second. Any parameter may itself be a whole list, as can be the case for Y there. The [H|T] notation basically enforces that it has to be a list to match at all, and that it has to contain at least 1 item (H), and the tail (T) can be empty.
Quote:

The prefix rule states that something is prefixed if it is the same as taking the two things and appending them, the first being the first object, and the second being the thing that is appended to the first object.
That's kinda what the incorrect code looks like. For the correct code, X is a prefix of Z if appending X to something is the same as Z.
Quote:

The suffix rule is where my understanding gets shakey. Is it more or less saying that when one thing is the suffix of another, it is the equivalent of an object (for lack of a better word) that has had a known thing appended to it, and gives a known result?
The suffix one says that Y is a suffix of Z if something with Y appended is the same as Z.
Quote:

I think just trying to describe it is giving me a better understanding of it.
It sure does eh!

Share this post


Link to post
Share on other sites
Here's another example you might find easy enough to explain what it does to furthur your understanding. Give it a try...
count([], 0).
count([_|T], N) :- count(T, M), N is M+1.

Share this post


Link to post
Share on other sites
Go to your library and get the book ``PROLOG Programming for Artificial Intelligence", by Ivan Bratko. Also, download SWI-Prolog and learn how to use its graphical debugger.

iMalc is correct, your prefix relation is incorrect. The best way to read a Prolog relation is to remember that :- is secretly logical implication oriented backward.

For example...


append( [H|X], Y, [H|Z]) :- append( X, Y, Z).


... reads, if you append X onto Y to obtain Z, then we may conclude consing H onto X and then appending this to Y gives us H consd onto Z. It may also help you to translate your relations into a functional form (this won't always work, relations are strictly more general than functions).

For example:


fun append [] y = y
| append (h::t) y = h::append(t, y)


In the translation, it's important to keep straight in your mind what is acting as input, and what is acting as output (there's even a convention in Prolog for notating this information).

HTH.

Share this post


Link to post
Share on other sites
Thanks for the amazing replies so far guys. I greatly appreciate this!

Quote:
Original post by iMalc
Here's another example you might find easy enough to explain what it does to furthur your understanding. Give it a try...
count([], 0).
count([_|T], N) :- count(T, M), N is M+1.

Lets see: The first rule states that an empty list has a count of 0. The second rule states that the count of a list is the same as taking the count of the tail, and incrementing the count each time it is called recursively.

Share this post


Link to post
Share on other sites
Heh.

Quote:
Original post by Moe
Quote:
Original post by iMalc
count([], 0).
count([_|T], N) :- count(T, M), N is M+1.

Lets see: The first rule states that an empty list has a count of 0. The second rule states that the count of a list is the same as taking the count of the tail, and incrementing the count each time it is called recursively.



count([], 0) does indeed express that the empty list has a count of zero. The second rule could be interpreted this way, but it wouldn't be the correct mindset or vocabulary to express it: it expresses that [_|T] is of size N if T is of size N-1. These are static properties, not results of function applications.

Share this post


Link to post
Share on other sites
Of course most prolog rules can be used in many ways. For example we can also use count like this:
?- count(X, 4).

and get something like this:
X = [_1, _2, _3, _4]

where _1 to _4 are not yet bound to anything in particular.
Much like how those prefix and suffix examples can use different parameters of append as inputs or outputs.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Heh.

*snip*

count([], 0) does indeed express that the empty list has a count of zero. The second rule could be interpreted this way, but it wouldn't be the correct mindset or vocabulary to express it: it expresses that [_|T] is of size N if T is of size N-1. These are static properties, not results of function applications.

See, that's the part that I am finding hard - changing my mindset. I've been working with object oriented languages and the like for so long that it is hard for me to think any different way.

ToohrVyk: I'm impressed. There's no way I'd be able to write a soduku solver in three days in Prolog.

I'll post another question or two when I get home from school.

Share this post


Link to post
Share on other sites
Alrighty, here is something more to munch on. Again, I don't want the answer, I just want a gentle nudge in the right direction.

We are given a diagram of all the computer science courses offered at the university. (Here, for the curious). The first part is to create a rule called "called" that takes two arguments displays the name of a course when given the course number. For example, a course number of "CS3740" displays "Programming Languages". I have already completed this step, so no worries. here. I just did something like the following:

called( CS3740, 'Programming languages aka evil course').

This seems to work just fine.

The next step is to create a rule called "offered" that takes three arguments (a course number and "Fall" or "Spring", and displays if the course is offered every year or every other year. I have completed this step as well. I did the following:

offered( CS2560, 'Fall', 'Every Year').
offered( CS2560, 'Spring', 'Every Year').

Again, this seems to work.

The next step was to set up a rule for each prerequisite called "directreq". It has two arguments, and takes in a course number and gives the prerequisite. Again, this is simple enough:

directreq(CS3740, CS2620).


It's the next one that I think is going to take a bit more work than expected. We are to create a rule that takes two arguments (a course number) and calculates a complete list of prerequisites of that course. My guess is that it is basically going to be a call to the "directreq" rule with the given course number as the first parameter and a variable as a second parameter. That variable is then used as the course number to the second call of "directreq". Let me post a snippet:

prereq( A, _ ) :-
directreq( A, C),
directreq( C, _).

Am I on the right track, or is there something much more to it?

EDIT: I apparently can't spell "prerequisites".

Share this post


Link to post
Share on other sites
What I'd program, in English:
A is a prerequisite of B if either:
A is a direct-prerequisite of B, or
A is a prerequsite of Something and that Something is a direct-prerequisite of B.

You're not too far off in what you've got so far. Just a note though, whenever you use an underscore, the things it matches are simply ignored and do not have to be equal to other underscores used. In your case you want both places where you have used underscores to be matched to the same thing, so you have to use a named parameter for them both.

Then you might want to look into using the build-in "setof" relation. Once you get that working, you're just about done.

Share this post


Link to post
Share on other sites
Alrighty, I've tried the following, but it results in a stack overflow. I guess the key is using the setof operator, right?


prereq( A, B ) :-
directreq( A, B ),
prereq( A, C ),
directreq( C, B).

Share this post


Link to post
Share on other sites
Quote:
Original post by Moe

prereq( A, B ) :-
directreq( A, B ),
prereq( A, C ),
directreq( C, B).


Separating these three things with commas is a logical AND. You don't want that. You want to express two different possibilities. Something like this:


prereq( A, B ) :-
directreq( A, B ).

prereq( A, B ) :-
prereq( A, C ),
directreq( C, B).

Share this post


Link to post
Share on other sites
I don't think

called(CS3740, 'Programming languages aka evil course').
does what you believe it does.

Prolog handles capitalized identifiers differently from non-capitalized ones. CS3740 stands for a variable, i.e. you're saying every course is called 'Programming languages aka evil course': (?- being nothing more than the prompt).

?- code(blah, Y).
Y = 'Programming languages aka evil course'

?- called(bluh,Y).
Y = 'Programming languages aka evil course'

You need to either use a string ('CS3740') or use another identifier which isn't capitalized (cs3740).

Be careful when testing things in Prolog. I once met a guy who claimed his Prolog code did exactly what it needed to but in reality his code only checked values but was not able to actually compute them.

?- length([1,2,3], 3).
Yes.

Him: see it works!
Me: no it doesn't.

?- length([1,2,3], X).
--error--
He then went to ask for a second opinion...

Share this post


Link to post
Share on other sites

This topic is 3666 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this