Understanding Prolog (a little better) 
Author Message
 Understanding Prolog (a little better)

Hi,

   In the Fall of 2001, I was a Graduate Teaching Assistant for a
class at my University.  At one point the students had to program in
Prolog, which almost none of them had ever programmed in (Prolog was
not a prerequisite for this class).  Most students only knew Lisp and
either C++ or Java.

   When the instructor taught the students Prolog for the first time,
I noticed that many students failed to completely grasp the concepts
that were contained in Prolog.  They could understand really simple
lines of Prolog, but when it came to learning how to write the code
for "append", many students were lost (mainly because the code looked
nothing like its C/C++/Java/Lisp counterparts).

   A problem instructors have with teaching new students is that it's
not always obvious to the instructor what concepts are difficult to
the students (that's one reason that having a Graduate Teaching
Assistant around is a good idea).

   Since I was a Teacher's Assistant, I was learning Prolog for the
second time and therefore able to discern exactly what it was that was
giving the students a difficult time learning Prolog:  unlike Lisp,
C++, and Java, Prolog had a totally different programming paradigm
that the students had never been exposed to.  This "paradigm shift" is
difficult for the professor to detect, since he or she has programmed
in Prolog for so long that it no longer is obvious what is difficult
for the new learner.

   Therefore, I wrote this write-up for my class to help the students
"get the hang of" this new paradigm.  I avoided technical wording
because my primary goal was to have my students understand how Prolog
"saw" the world, and how it did this differently than C++, Java, and
Lisp.

   I'm posting the write-up here on the hope that somebody somewhere
might find it useful.  Keep in mind that my goal in composing the
write-up was to use simple, understandable wording (instead of aiming
for technical completeness).  Anybody who has basic knowldege of
Prolog and knowledge of either Lisp, C, C++, or Java should be able to
understand my write-up.  (It is assumed that the reader of this
document already knows about the "|" operator.  The "!" operator,
however, is never talked about here.)

   I am by no means a Prolog guru or expert.  Therefore there might be
a lot of places where an expert in Prolog might wish that the wording
was different, or that a concept I presented was not technically
correct.  This was the best I could do on my limited knowledge of
Prolog, but nevertheless, many students found my document useful.  My
write-up received a lot of positive feedback from the students, even
though it was about 11 pages long.  (Several of the students who
bothered to read it all the way through told me that they were glad
they did, even though they thought they knew Prolog well enough before
reading my write-up.)

   Feel free to distribute my write-up, especially for educational
purposes.  I would ask, however, that my write-up not be changed
unless it is to correct an error.

   Finally, here is my write-up:

---------------------------------------------------------
---------------------------------------------------------

   UNDERSTANDING PROLOG (A LITTLE BETTER)

      by Jean-Luc Romano

-----------------------------------------------

   INTRODUCTION

   You've tackled Java, taken on Lisp, and now you're learning Prolog.
 You've certainly proven that you can learn new programming languages,
but Prolog doesn't strike you as being like any other programming
language that you've seen before.

   If you find yourself struggling to understand even a very basic set
of rules in Prolog, then perhaps this file will help you understand
some fundamentals of Prolog.

-----------------------------------------------

   UNDERSTANDING THE PROLOG PARADIGM:
   LOOKING AT THE WORLD THE WAY PROLOG SEES IT

   One of the areas that causes the most confusion in Prolog is that
many users new to Prolog want to treat the Prolog functors like
functions in C/C++, Java, or Lisp.  Since Prolog functors look a lot
like the functions in these other languages, it's easy to understand
how this mistake might be made.  Therefore, let's first look at this
first difference.

   Let's define a function designed to find the square of a number.
It might look like this:

   float square(float a) { return a*a; };  /* for C/C++ and Java */
   (defun square (a) (* a a))   ; for Lisp

   Let's examine what's going on:  basically, in each of the
languages, we are passing in the value we want squared.  The value is
squared, then returned.  Simple, isn't it?

   This is where Prolog is different.  In Prolog, there are no return
values.  Values are simply passed into a functor as a statement, and
then Prolog declares whether the statement can be proven true.

   Therefore, BOTH the value to be squared AND the result should be
passed in; THEN we get to know if those values form a valid
combination.

   To understand, review the following lines of code, noticing that
they now return boolean values (instead of the square of the number):

   boolean square(float a, float b) { return (b == a*a;) } /*
C/C++/Java */
   (defun square (a b) (= b (* a a)))   ; Lisp
   square(A,B) :- B is A * A.   % Prolog

   You probably understand what the first two lines of code are doing,
so let's review the Prolog line (the third line).

   When you query Prolog with a statement like square(3,9) you are
asking Prolog if it can prove the statement as being true.  Looking
back at the code we typed in, we see that Prolog will state any
statement that can bind to square(A,B) as being true if it can prove
that the statement "B is A * A" is true.  Therefore, when you type
"square(3,9)." Prolog tries to prove that "9 is 3 * 3."  Since this is
a rather trivial mathematical operation for Prolog to prove, it will
have no problem proving that statement as true.  Because it determines
that 9 is in fact equal to 3 * 3, it then displays "yes", meaning that
it was able to prove square(3,9) as being true.

   A few things to note:

- If Prolog ever displays "no" it does not
  necessarily mean that the statement is false,
  but rather that it was unable to be proven true.  
  You will find, however, that sometimes Prolog
  will end up in an infinite loop (rather than
  displaying "yes" or "no") when it is unable to
  prove a true statement as true.

- If you've ever wondered why the keyword "is"
  is used when comparing one mathematical value
  to another, it is because the equal sign ("=")
  is already reserved for the bind operation (for
  example, List1 = [a,b,c] means that the variable
  named "List1" binds to [a,b,c]).

- Remember, Prolog never returns a value, it
  simply states whether or not it can prove the
  statement (with its parameters) as being true.  
  Whereas in other languages you would write a
  function to return a desired value, in Prolog
  you would write code that, given all the
  parameters, would say that all the parameters
  and values fit together to make a true statement.  
  This is one of Prolog's main differences from
  many other programming languages.

-----------------------------------------------

   AN EXTRA FEATURE OF PROLOG

   There's a handy feature of Prolog that hasn't been mentioned yet in
this file which you probably know about if you've studied even a
little bit of Prolog.  Not only will Prolog try to prove a statement
(with all its parameters) as being true, but if you replace a
parameter value with a variable, it will try to find a value for the
variable that makes the statement true!  To clarify, we all know that
Prolog will say the following is true:

   square(6,36).

   We typed this already knowing that the square of 6 is 36.  But what
if we don't know that?  What if we enter a huge number whose square we
don't know?  If this is the case, we can put a variable name
(remember: variable names always start with a capital letter in
Prolog!) in place of where the squared value should be, like this:

   square(17,SquaredValue).

Prolog then says:

   SquaredValue = 289

This means that Prolog was able to able to prove
"square(17,SquaredValue)" as true, provided that SquaredValue binds to
289.

   So, can you do it the other way around?  In other words, can you
put a variable name in for the first parameter, and have it show you
the square root, like this?:

   square(SquareRoot,9).

Well... sometimes, depending on how well you wrote your program.  This
particular example gives me an error message, most likely because
Prolog wasn't made to "undo" a multiplication operation.
Theoretically it COULD go through the set of all real numbers, but
since it would have an infinite number of values to test, it's
possible that Prolog would never show you any value at all.

   However, most code you will write in Prolog will deal with lists
instead of mathematical operations (after all, if we wanted to use
many mathematical operations, we would probably write our program in
C/C++ or Lisp, wouldn't we?...).  And when dealing with lists it's
much easier to write code that works "the other way around," or that
fills in the missing piece (the parameter that is replaced with a
variable).  But even here you need to be careful that you don't send
Prolog into a near-infinite loop.

-----------------------------------------------

   TRY THIS AT HOME

   Say you want to find the square of some number, for example, 15.
Now type the following into Prolog:

   square(15).

You will probably see something similar to the following message:

   ++Error: Undefined predicate:  square / 1
   Aborting...

So what does this mean?  Did we misspell the word "square"?  Did we
type the code for "square" incorrectly?  Did we find a number that the
functor does not work correctly with?  Or did we just find a bug in
Prolog?

   Actually, none of the above are correct.  Do you know what's wrong?
 We made the error of confusing Prolog usage with C/C++, Java, and
Lisp ...

read more »



Mon, 20 Jun 2005 01:39:51 GMT  
 Understanding Prolog (a little better)

hi jean-luc,

IMHO you've done a good job taking a student who is used to C-like
languages to Prolog. i have a few comments which i hope are useful to
you.

Quote:
> - If you've ever wondered why the keyword "is"
>   is used when comparing one mathematical value
>   to another, it is because the equal sign ("=")
>   is already reserved for the bind operation (for
>   example, List1 = [a,b,c] means that the variable
>   named "List1" binds to [a,b,c]).

this is not correct. = is not the "binding operator", (whatever that
would be), it is a comparison operator. 'List1 = [a,b,c]' is taken by
Prolog to be a statement that needs to be proven, and it can be proven
if List1 is bound to [a,b,c]. so the binding is more or less a
side-effect of the comparison.

"is" is being used here because a mathematical evaluation needs to be
performed. in itself, 3*3 is just a statement, and if you say 'A =
3*3.' in Prolog, A will be bound to '3*3'. in order to force Prolog to
evaluate the expression, you must use "is".

Quote:
>    So, can you do it the other way around?  In other words, can you
> put a variable name in for the first parameter, and have it show you
> the square root, like this?:

>    square(SquareRoot,9).

> Well... sometimes, depending on how well you wrote your program.  This
> particular example gives me an error message, most likely because
> Prolog wasn't made to "undo" a multiplication operation.

no, it has nothing to do with the multiplication, it has to do with
the special status of "is": a statement with "is" simply cannot be
re-evaluated and therefore cannot be backtracked over. this makes
sense, because an arithmatic calculation will only have one answer.

Quote:

>    member(Item,LongList) :- member(Item,ShortList),
>                        LongList = [Disregard|ShortList].

>    This line just above will get called ONLY IF the item is not the
> first element of the list (if it were, the first line would tell
> Prolog that the expression is true).

*if* the statements appear in the correct order, of course. perhaps
you should mention that explicitly.

Quote:
>    Now put all the lines of code together:

>    % member example usage:  member(a,[a,b,c,d,e]).
>    % another member example usage:  member(c,[a,b,c,d,e]).
>    member(Item,[Item|Rest]).
>    member(Item,[Disregard|ShortList]) :- member(Item,ShortList).

> ...and, voila'!  We now have code that determines if an item is in a
> list.  We can run the examples to test our code if we want.

some (most?) Prolog systems will complain about the singleton variable
Disregard, so why not introduce '_' here?

Quote:
>    Now let's shorten the line above by substituting List1 and List3 to
> what they bind to:

>    append([First|Rest1],List2,[First|Rest3] :-

you're missing a ')' here.

Quote:
>    YET ANOTHER RECURSION EXAMPLE

>    Let's do one last recursion example.  Hopefully this example will
> help you to think around certain problems.  Let's write code to
> reverse a list.

>    The first thing we should do is acknowledge that we are not writing
> a function that taken a list as a parameter and returns the reversed

s/taken/takes/

Quote:
>    Now you might be thinking to yourself, "Wouldn't it be nice if
> Prolog had an operator that split out the last element?  It sure would
> save a lot of trouble."  Now, think about it.  As far as I know,
> Prolog does not have an operator that splits out the last element of a
> list,

you can leave out "As far as I know", because it really doesn't. the
reason for this is in the way lists are defined. L is a list either if
L = [] or if L = [A|B] where B is also a list. in other words,
internally, a list is not a sequence of elements, but something that
is composed of exactly two elements: the head and the tail. this means
that there is no "natural" way to refer to the last element of a list.

(in Lisp, a list is either NIL or a cons whose cdr is a list. Prolog
lists are defined in the same way, with "|" = ".").

Quote:
> 1.  Before writing code, acknowledge the fact
>     that programming languages like C/C++, Java,
>     and Lisp all return values.  In Prolog, however,
>     you will not return anything; if there is a
>     value you want to discover you will pass a
>     variable in its place in the parameter list.

i think it would be good if you put some more emphasis on the actual
difference between Prolog and C, Lisp, Java etc. Prolog is a
declarative language, while C, Lisp and Java are imperative
languages. because of this, one must approach a Prolog program in a
different way. you do this implicitly (when you say things like "when
is it true that..."), but i think it would be good if you made this
explicit. otherwise, students may get the impression that Prolog is
simply an imperative language with a funny syntax.

there is a certain dilemma, here. Prolog programs will often have
parts with a strong imperative character, and even declarative
definitions such as those of member, append and reverse that you
discussed can be approached from an imperative point of view. i think
it is important that students are made aware of this. it shouldn't be
very difficult to add this to your paper, because you already make the
distinction implicitly.

Quote:
> 5.  If reading Lisp code is too overwhelming for

i assume you mean Prolog code?

HTH

--
Joost Kremers           http://baserv.uci.kun.nl/~jkremers
"taxi" is the vocative of "cab"



Mon, 20 Jun 2005 03:37:08 GMT  
 Understanding Prolog (a little better)

Quote:
> > - If you've ever wondered why the keyword "is"
> >   is used when comparing one mathematical value
> >   to another, it is because the equal sign ("=")
> >   is already reserved for the bind operation (for
> >   example, List1 = [a,b,c] means that the variable
> >   named "List1" binds to [a,b,c]).

> this is not correct. = is not the "binding operator", (whatever that
> would be), it is a comparison operator. 'List1 = [a,b,c]' is taken by
> Prolog to be a statement that needs to be proven, and it can be proven
> if List1 is bound to [a,b,c]. so the binding is more or less a
> side-effect of the comparison.

I recall that when I took a subject on Prolog at uni our lecturer described
= as the unification operator, but this was somewhat intimidating for the
class. To call it a comparison operator would confuse the issue with the
operators > and < that behave very differently from unification.

Binding operator seems to me to be a fairly "safe" description. Though,
hopefully the word unification would be mentioned, if only to allow students
to be able to read and understand more advanced discussion of prolog.

Quote:
> >    So, can you do it the other way around?  In other words, can you
> > put a variable name in for the first parameter, and have it show you
> > the square root, like this?:

> >    square(SquareRoot,9).

> > Well... sometimes, depending on how well you wrote your program.  This
> > particular example gives me an error message, most likely because
> > Prolog wasn't made to "undo" a multiplication operation.

> no, it has nothing to do with the multiplication, it has to do with
> the special status of "is": a statement with "is" simply cannot be
> re-evaluated and therefore cannot be backtracked over. this makes
> sense, because an arithmatic calculation will only have one answer.

I think it would be too early to be giving a precise explanation such as
that. I think the explanation offered is a suitable answer to why "is"
requires a fully ground expression, and is a vague answer that avoids the
student having to understand unnecessary detail.

-Benjamin Johnston



Mon, 20 Jun 2005 19:49:21 GMT  
 Understanding Prolog (a little better)

Quote:

>    Well, that's about it.  If you were able to read through this whole
> text file you hopefully have a deeper understanding (and maybe even a
> greater appreciation) for Prolog.

I did read through the whole text and here are just 4 remarks from my much longer list:

1) you use very often the word "functor" where you should use
"predicate" (as an example, you write "the append functor")
or "function symbol"

2) your advice
        > When using recursion, remember to ALWAYS avoid
        > left-recursion
is bad; take for instance the following definition of permute/2:

            permute([],[]).
            permute([X|R],P) :-
                   permute(R,PR),
                   insert_in_all_positions(X,PR,P).

it is left recursive and there is nothing wrong with it - it is a direct translation of the english

            to permute a list, permute its tail and insert the head everywhere

it is even faster (on every implementation I checked) than the right-recursive (similar) version
and for good (implementation) reasons
also in tabled LP, it pays off to use left recursion instead of right recursion
you don't have to throw away your advice - just rephrase it so that it becomes sound

Note also that in this advice you use "expression" instead of "goal" ...

3) you write:

Quote:
> 5.  If reading Lisp code is too overwhelming for
>   you, try expanding it by individually binding
>   the parameters after the ":-" operator.
>   Remember, though, that it's always best to
>   shorten the code when you're writing it to
>   save steps and computation time.

Only the most naive and unsophisticated Prolog systems execute more steps for

    append(List1,List2,List3) :- List1 = [First|Rest1],
                                List3 = [First|Rest3].

than for append([First|Rest1],List2,[First|Rest3]).

So the reason you give is wrong most often. Even worse, it sometimes pays off to make the unification
explicit, and not only for clarity.

#    % reverse example usage:  reverse([1,2,3,4,5],[5,4,3,2,1]).
#    reverse([],[]).
#    reverse([First|Subset1],List2) :- append(Subset2,[First],List2),
#                                    reverse(Subset1,Subset2).
#
#    Now you can test it with expressions like:
#
#    reverse([a,b,c,d],ReversedList).
#    reverse(OriginalSentence,[backwards,is,sentence,this]).
#
#    Of course, for this code to work it requires that append be defined
# as well.  Hopefully you should see that with useful little operations
# like append you can create more complex operations that we normally
# could not accomplish with what we originally had to work with.

your definition of reverse has the disadvantage that when reverse is called in the usual way, e.g.
as ?- reverse([1,2,3],L).
it returns one solution and then loops - well, that is in case you have the more or less "standard" definition
of append; but if you have an append with the two clauses interchanged, the goal ?- reverse([1,2,3],L).
loops without returning an answer.

5) I liked the explicit statement of you tip 2 - although it should apply to every programming language.

===========

On the whole, your text breathes that you haven't grasped Prolog very well; the text is technically incorrect or
misleading at several places; I would not recommend it to a student, unless the student has mastered
Prolog better than you.

Cheers

Bart Demoen



Tue, 21 Jun 2005 23:46:23 GMT  
 Understanding Prolog (a little better)

Quote:

> i think it would be good if you put some more emphasis on the actual
> difference between Prolog and C, Lisp, Java etc.

right

Quote:
> students may get the impression that Prolog is
> simply an imperative language with a funny syntax.

which would be very close to the truth, no ?

the main difference between Prolog and the other languages that were mentioned is its parameter passing
mechanism, the logical variable, backtracking and (in its pure form) the absence of assignment and side-effects

the fact that there is a declarative reading to a few Prolog programs (or predicates) does not provide
a basic difference with C: lots of well written C programs (or C functions) have a declarative reading as well

Cheers

Bart Demoen



Tue, 21 Jun 2005 23:55:09 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. Understanding Lisp Hash-Tables (a little better)

2. 1 little, 2 little, 3 little endians...

3. Better understand of Logout, Commit and Rollback

4. I would,like to understand Clipper better.

5. Looking for a better understanding of Classes

6. Looking for a good page to understand continuations

7. A good free/trial prolog IDE for compiling and loading wordnet prolog database

8. Prolog purposes - newbie understanding...

9. great masses of programmers would do better with a little more teamwork

10. Good least-squares fitting library for linux

11. little prolog projects

12. So many Prologs, so little time....

 

 
Powered by phpBB® Forum Software