Home > Archive > Prolog > April 2005 > Thinking Recursion
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Thinking Recursion
|
|
| python1 2005-03-22, 3:59 pm |
| As a little background, I program in (good-ol' ANSI) C; script in dos,
sh, and Python; and write a lot of SQL. I'm mainly a hobbiest.
Trivial problems involving recursion are taking ages to solve/express in
prolog. I assume that after some point it 'clicks', but the progression
is slow. Bratko suggests thinking declaratively, as opposed to
procedurally (which I catch myself drifting to), but either way seems
non-intuitive.
This is probably the third time I've tried to learn Prolog over the last
half-decade, and once again progress has slowed to a stop once something
like this comes up (from "Programming in Prolog"):
append([],L,L).
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).
....which is understandable if contemplated long enough, but I don't
think I would have come up with this on my own.
How I read it is:
1. It is a fact that the boundary condition of appending occurs when the
first input list is empty; the second and third must be equal.
2. It is a rule that appending, when the first and third input is a
non-empty list, is satisfied if a call to append with the tail of the
first input, the whole of the second input, and the tail of the third
input is successful.
....phew. Is this how I should be thinking?
How long did it take for /you/ to start thinking recursion?
| |
| Joachim Schimpf 2005-03-22, 3:59 pm |
| python1 wrote:
> This is probably the third time I've tried to learn Prolog over the last
> half-decade, and once again progress has slowed to a stop once something
> like this comes up (from "Programming in Prolog"):
>
> append([],L,L).
> append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).
>
> ...which is understandable if contemplated long enough, but I don't
> think I would have come up with this on my own.
I find that for visually oriented people like myself, choosing better
variable names and layout can make things much more obvious:
append( [], Ys, Ys ).
append([X|Xs], Ys, [X|XsYs]) :- append(Xs, Ys, XsYs).
--
Joachim Schimpf / phone: +44 20 7594 8187
IC-Parc / mailto:J.Schimpf@imperial.ac.uk
Imperial College London / http://www.icparc.ic.ac.uk/eclipse
| |
| Bill Spight 2005-03-22, 3:59 pm |
| Dear python1,
> append([],L,L).
> append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).
>
> ...which is understandable if contemplated long enough, but I don't
> think I would have come up with this on my own.
>
Me, either. :-)
> How I read it is:
>
> 1. It is a fact that the boundary condition of appending occurs when the
> first input list is empty; the second and third must be equal.
>
> 2. It is a rule that appending, when the first and third input is a
> non-empty list, is satisfied if a call to append with the tail of the
> first input, the whole of the second input, and the tail of the third
> input is successful.
>
> ...phew. Is this how I should be thinking?
>
Here is how I read it.
Any list appended to the empty list is itself.
The result of appending List2 to List1 has the same head as List1. Its
tail is the result of appending List2 to the tail of List1.
I also note that the procedure will terminate, since at each iteration
the first list gets shorter, finally becoming the empty list.
Best wishes,
Bill
| |
| Bart Demoen 2005-03-22, 8:58 pm |
| python1 wrote:
> append([],L,L).
> append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).
[...]
> ...phew. Is this how I should be thinking?
[...]
> How long did it take for /you/ to start thinking recursion?
Assuming this is not a rethoric question ...
I encountered recursion first in Pascal (some time after having been
warned not to use recursion in Fortran and Cobol). It was for functions
like fibonacci and then quickly to balanced trees. Calling a function
recursively was explained as "just imagine that a renamed copy of the
same function is called". We were thaught to program with invariants, so
I never saw a problem: invariants make you worry less about the deeper
calls. What was true for Pascal appplies to Prolog.
Maybe one should try to think in terms of "induction" instead of as
"recursion":
append/3 is a relation which is true between the 3 objects
[], any object and the same object
and
if append is true between L1, L2 and L3, than it is also true
between [X|L1], L2 and [X|L3]
If you are interested only in least Herbrand models, you get exactly
what you want with looking at the append rules as an inductive
definition.
Cheers
Bart Demoen
| |
| Bart Demoen 2005-03-22, 8:58 pm |
| Bill Spight wrote:
> Dear python1,
>
>
>
>
> Me, either. :-)
Folklore says that it took the inventors of Prolog about 3 w s
to get their head around append/3. Prolog tutorials now force it on
students in half a page ... it certainly needs a lot of explanation,
amongst others about the multiple modes it can be used in, its
backtracking behaviour, termination, order of solutions ...
> Here is how I read it.
>
> Any list appended to the empty list is itself.
> The result of appending List2 to List1 has the same head as List1. Its
> tail is the result of appending List2 to the tail of List1.
>
> I also note that the procedure will terminate, since at each iteration
> the first list gets shorter, finally becoming the empty list.
You read it as a function of two arguments - nothing really wrong with
that, but limited. And your termination argument seems to depend on the
mode (+,?,?) [maybe even (+,?,-)] - again suggesting a particular
(functional) use of append/3.
Cheers
Bart Demoen
| |
| George SP. 2005-03-23, 3:58 pm |
|
"Bart Demoen" <bmd@cs.kuleuven.ac.be> wrote in message
news:1111521690.956513@seven.kulnet.kuleuven.ac.be...
> python1 wrote:
>
> [...]
> [...]
>
> Assuming this is not a rethoric question ...
> I encountered recursion first in Pascal (some time after having been
> warned not to use recursion in Fortran and Cobol). It was for functions
> like fibonacci and then quickly to balanced trees. Calling a function
> recursively was explained as "just imagine that a renamed copy of the
> same function is called". We were thaught to program with invariants, so
> I never saw a problem: invariants make you worry less about the deeper
> calls. What was true for Pascal appplies to Prolog.
>
>
> Maybe one should try to think in terms of "induction" instead of as
> "recursion":
>
> append/3 is a relation which is true between the 3 objects
>
> [], any object and the same object
> and
> if append is true between L1, L2 and L3, than it is also true
> between [X|L1], L2 and [X|L3]
> If you are interested only in least Herbrand models, you get exactly
> what you want with looking at the append rules as an inductive
> definition.
>
> Cheers
>
> Bart Demoen
Hi,
Could append really be a relation between any 3 objects?
Can you really write in prolog such "relation"?
If lists are "objects" in order to "append" them we need to know their
structure and how to access them.
Change the "object" and you would have to change the prolog code for append
therefore changing the "append relation". For some objects "append" may not
even make sense. It looks like "append" is more of a method for an object
than a relationship between objects.
It looks to me that append/3 as written above is more of a function
applicable to lists than a "relation" between objects. Therefore I tend to
go with the explanation of append/3 provided by Bill Spight despite some
limitations it may have.
Cheers
| |
| Matthew Huntbach 2005-03-23, 3:58 pm |
| On Tue, 22 Mar 2005, Bart Demoen wrote:
> Bill Spight wrote:
[color=darkred]
> You read it as a function of two arguments - nothing really wrong with
> that, but limited. And your termination argument seems to depend on the
> mode (+,?,?) [maybe even (+,?,-)] - again suggesting a particular
> (functional) use of append/3.
Yes, I think that's the sensible way to see it. Prolog predicates
work multi-moded when they're in effect database access, and in a few
examples like "append". But on the whole, you can't take an
arbitrary Prolog predicate and expect it to work multi-moded. Prolog
isn't magic, it doesn't help to encourage the idea that it's magic,
it's better to think of it operationally, and thinking of it
operationally means thinking of it in terms of moded operations.
My personal recommendation would be to actually use the same clauses
but with different names if you happen to want the effect with a
different moding. Our poor novice (or not so novice, since he tried
Prolog several times but couldn't get beyond append) finds it
difficult to grasp the simplest use of recursion. Isn't it just
leading him to more confusion, and encouraging the idea that
Prolog is only for very clever experts, if you expect him immediately
to grasp append in the multi-moded way of thinking?
Matthew Huntbach
| |
| Brian Hulley 2005-03-23, 3:58 pm |
|
python1 wrote:
>
> append([],L,L).
> append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).
>
> ...which is understandable if contemplated long enough, but I don't
> think I would have come up with this on my own.
>
> How I read it is:
>
> 1. It is a fact that the boundary condition of appending occurs when
the
> first input list is empty; the second and third must be equal.
>
> 2. It is a rule that appending, when the first and third input is a
> non-empty list, is satisfied if a call to append with the tail of the
> first input, the whole of the second input, and the tail of the third
> input is successful.
>
> ...phew. Is this how I should be thinking?
>
> How long did it take for /you/ to start thinking recursion?
I remember walking around in a daze for at least a w after being
introduced to the concept of recursion in my first year course in
Pascal. Initially I thought recursion meant "to solve a problem use the
solution you haven't yet written" which is clearly non-intuitive.
The key for me was realising that the essential thing that makes
recursion work is that the input gets smaller and smaller on each
recursive call, so for append/3 above the first list will eventually
become the empty list to the recursion will terminate.
It seems to me that you'd be better off trying out some recursive
programs in C first, so that you fully understand the idea of recursion
in C (which you are familiar with) before moving on to Prolog ie gain
clarity in one concept at a time. To understand it better you could
imagine what's happening to the CPU stack when you call a function
recursively (this is how I eventually managed to understand it -
there's no magic after all :-)).
As for understanding Prolog, I would suggest that to really understand
what's going on you have to have some idea how it is actually
implemented in terms of structs and pointers etc. This is how I
eventually understood unification.
While this may seem like a long way round, I can now say that
everything has definitely "clicked" (like a Zen koan) and I can now
also understand recursion and unification in a direct intuitive way
without thinking in lower level terms.
I think the idea that anyone can properly grasp what's going on just by
thinking in a purely declarative way is nonsense - this will just lead
to lots of gaps in understanding later, and is one reason why people
are so afraid of using the cut, or end up with non-terminating
programs.
Regards, Brian.
| |
|
| It's not strictly true that append/3 is a function applicable to lists.
I think a more accurate answer lies halfway between the definitions
above. It defines a relation on lists (rather than 'objects' which is a
bit wooly). It is a relation rather than a function because it defines
3 functions - one for each of the modes with two ground and one
variable parameter. As such it is a definition of how the lists are
related to each other, rather than a particular function. Although all
3 functions can be read in the code.
I still tend to think of most Prolog code as functions (comes from a
Haskell background), and do lots of functional things. Here's a nice
trick that you might like if you program the same way, it's new to me
but might be an oldie round here:
cutStr(Str,F,B,(Fs,Ms,Bs)) :-
length(Fs,F),
length(Bs,B),
append(Fs,T,Str),
append(Ms,Bs,T).
So I can use it as a drop:
drop(X,In,Out) :- cutStr(In,X,0,(_,Out,_)).
As a take:
take(X,In,Out) :- cutStr(In,X,0,(Out,_,_)).
As a take from the back:
btake(X,In,Out) :- cutStr(In,0,X,(_,_,Out)).
And as a drop from the back:
bdrop(X,In,Out) :- cutStr(In,0,X,(_,Out,_)).
There are probably a few more modes that I haven't found, as it is a
list slicer. Of course as length and append are both decalarative you
can also use it to merge lists.
Enjoy,
Amoss
| |
| Bart Demoen 2005-03-23, 3:58 pm |
| I don't want to answer separately to all the posts related to the reading
of append/3, so here is a global reply ...
I should not have used the word objects (it is too overloaded, or
worse, for many people, it has only one specific meaning), rather terms,
or Prolog terms.
Saying that append/3 (or any other predicate in Prolog) defines a relation
has nothing to do with append/3 being useful in more than one mode: here is
more explicitly what I claim:
every predicate defined in Prolog defines a relation
This relation is simply the subset of PTxPTx...xPT (n-times if the
predicate has n arguments) which result from a proof found by Prolog.
(PT = Prolog Terms)
You might expect (or want) that this subset has certain properties:
- being closed under applying variable substitutions to it
or
- calling the predicate with a arguments less instantiated than
an element from the relation, results in an answer in
the relation; or maybe even all the answers that unify
but that's very often not true. Prolog is not good enough for that and it
also allows non-logical stuff which uses or messes with instantiation.
It is most often helpful to understand the meaning of a predicate in terms
of the relation it defines. Even if the predicate is implemented in a way
that allows only one mode. A typical example is sort/2: the relation it
defines is clear, but you cannot use it for generating unordered lists in
the first argument.
For append/3 we have an almost ideal situation, so why not take advantage of
that and try to understand append/3 as the relation it defines. It can be
done operationally, or by seeing append/3 as an inductive definition of this
relation. I offered the latter as an alternative to someone who after several
attempts couldn't understand it when thinking of "recursion" - which is
language unrelated, with no particular problem in Prolog as compared to
other languages, but which in logic can be circumvented by talking about
relations and inductive definitions (one can do that in C as well of course,
but it would take a bit more convincing a C-programmer :-).
Even if you want to understand append/3 operationally, you still have the
choice between doing that in mode (in,in,out) or in mode (out,out,in) and
then talk about append/3 as a list splitter: and that view captures the
backtracking behaviour of append/3 which one misses out on with
the other mode.
I have not said that understanding append/3 as a relation (inductively
defined or not) is a magic bullet to understanding recursion, neither to
understanding Prolog; neither have I made any claim (in this thread) that
Prolog is a silver bullet for anything. I really hope we can keep the other
thread out of this one.
append/3 (in Prolog) does NOT (only) define 3 functions: it defines MANY
more functions; only if you restrict yourself to the two extreme
instantiations (ground and free) you are limited to 3.
From the software engineering point of view, it is a good idea to have a
separate (identical) version of append which you name split, if you call it
in the splitting mode, but that's not a langauge issue I think.
Finally: append/3 (in Prolog) does NOT (only) define a relation between lists,
as one of the elements in the relation is
([],foo,foo)
Cheers
Bart Demoen
| |
| bill hogan 2005-03-23, 3:58 pm |
| George SP. wrote:
> "Bart Demoen" <bmd@cs.kuleuven.ac.be> wrote in message
> news:1111521690.956513@seven.kulnet.kuleuven.ac.be...
[color=darkred]
>
> Hi,
> Could append really be a relation between any 3 objects?
append /holds/ only for a certain well-defined subset of the set
of all 3-tuples of Prolog terms but, yes, any of the constituents of
such a 3-tuple can be any Prolog term whatsoever.
?- append([], 2, 2 ).
Yes
?- append([a,b,c], 2, Q).
Q = [a, b, c |2]
'Prolog' as defined by the ISO at this time does not include
type definitions or typed or sorted predicate declarations.
[Type definitions catch errors of form (e.g.,
'append([a,b,c],2,Q)' where 'append([a,b,c],[2],Q)' was
intended), while sorts catch errors of agreement (e.g.
'speed(123,bmw)' where 'speed(bmw,123)' was intended). Types can
be made to do double-duty as sorts but IMHO it is better to be able
to define sorts i.t.o. types because this allows different sorts
to be represented by the same types yet never be  .]
--
billh
| |
| Brian Hulley 2005-03-23, 8:58 pm |
|
Matthew Huntbach wrote:
> Yet I've been forced to concede, through teaching this stuff to
> people over the years, that most people fall into your camp rather
> than mine. From this, Prolog's main selling point when it was
> first developed - that it is natural and intuitive and thus far
> easier to program in than languages which are closer to the
computer's
> architecture - falls down.
I think two issues are being here: 1) the difficulty of
learning new concepts, and 2) whether or not a language is intuitive
and natural once those new concepts have been properly assimilated.
I myself found some aspects of Prolog very difficult to grasp at first,
but now, having gone through the eye of the needle with that learning
curve, I find that Prolog is extremely natural and intuitive, since it
gives me all the ingredients of computation in an ultra-concise and
aesthetically pleasing form.
In particular, the concept of unification undergoes a metamorphosis
into an extremely powerful way of programming, since it frees you from
the need to think about input/output and essentially lifts the
algorithm to a realm beyond time. (I'm just trying to hint at the kind
of thought processes possible through Prolog, and am not very good at
expressing them in words.)
After all, the best view comes from the highest mountain, though not
everyone may have the stamina to climb it :-)
Regards, Brian.
| |
| Bill Spight 2005-03-24, 3:57 am |
| Dear Matthew,
> Yet I've been forced to concede, through teaching this stuff to
> people over the years, that most people fall into your camp rather
> than mine. From this, Prolog's main selling point when it was
> first developed - that it is natural and intuitive and thus far
> easier to program in than languages which are closer to the computer's
> architecture - falls down.
I think that context matters. Declarative thinking is not foreign to
ordinary people. What is foreign is declarative thinking about doing
things or issuing commands.
Still, it is not all that uncommon. For instance, several years ago I
was invited to Thanksgiving dinner at the home of a friend's parents.
Several of us were in the kitchen talking when my friend's mother
appeared in the doorway and announced, "We have a living room." We all
dutifully filed into the living room. The mother knew how to give a
command in a declarative way. ;-)
Best regards,
Bill
| |
| python1 2005-03-24, 3:57 am |
| Bart Demoen wrote:
> python1 wrote:
>
>
> [...]
>
>
> [...]
>
>
>
> Assuming this is not a rethoric question ...
> I encountered recursion first in Pascal (some time after having been
> warned not to use recursion in Fortran and Cobol). It was for functions
> like fibonacci and then quickly to balanced trees. Calling a function
> recursively was explained as "just imagine that a renamed copy of the
> same function is called". We were thaught to program with invariants, so
> I never saw a problem: invariants make you worry less about the deeper
> calls. What was true for Pascal appplies to Prolog.
>
>
> Maybe one should try to think in terms of "induction" instead of as
> "recursion":
>
> append/3 is a relation which is true between the 3 objects
>
> [], any object and the same object
> and
> if append is true between L1, L2 and L3, than it is also true
> between [X|L1], L2 and [X|L3]
> If you are interested only in least Herbrand models, you get exactly
> what you want with looking at the append rules as an inductive
> definition.
>
> Cheers
>
> Bart Demoen
I think this is exactly what I'm after. A sample of how someone fluent
in Prolog is thinking when writing code. Thanks.
Matthew Huntbach:
In python, I find myself having a dialog something like this...
"So now we're going to loop through this file as a list of strings"
<keyboard clacking away>
"...and then we're going to split each string by delimiter-X..."
<see previous emote>
"...and then we're going to call function-X against column-X..."
<emote>
"...blah, blah, ad infinitum."
....which runs like an interesting, fast-paced conversation with
myself/computer. Python always came rambling out of me, possibly due to
previous exposure with C.
With Prolog, and append specifically, my line of thought is something
like this...
1. Ok, the recursive call to append has to stop, and we're going to do
it by checking the first input to the relation to determine when it has
been stripped to an empty list, at which point the second input equals
the third. All the stripp'n is going to happen when the function is
called recursively.
2. Alright, so now we're going to call append with a non-empty list as
the first input. The head of the first non-empty list has to equal the
head of the third non empty list, (which I assume will put the items in
list one in order, one at a time, ahead of the items in list two in list
three, eventually). The second input list will just kinda sit there
doing nothing until condition one is kicked off, at which point it will
occupy the tail portion of the third list (you know, the list where the
first input list was put, one item at a time).
I think the reason why it seems difficult is because I don't know how to
"speak" prolog when I'm writing the code. Certainly not concisely enough
to put what I want to do into an understandable sentence in my mind. It
might be comparable to someone who speaks with a low vocabulary, thinks
in that same low vocabulary, and therefore is limited in reasoning to
the few ideas that can be expressed with their particular fund of words.
I hope that makes sense and helps some.
Incidentally, I have never done any recursion in C, but have used it on
occasion in Python. C is more of a utility language for me, I don't have
much fun in it, but do get results patching together code others have
written. Recursion in python was/is easy so long as you 'return' the
recursive call, and are sure the boundary condition is correct.
All:
I've hung back because nothing kills a thread faster than the initiator
responding to the first good reply with thanks. It's past due though.
Thank you all for the replies.
I was not following the Minsky thread, but have read it now. It seems
there is a nature vs nurture argument regarding the ability to learn the
language. Some think it is inherent, and programming declaratively will
come either instantly or very slowly, and (I presume) the reason why it
comes easily, is because the swift learner has either been born
spock-like or started thinking logically when so young as for it to be
ingrained in their thought process, thus being part of their nature. In
other words, "Non-logical learners taking up a logical programming
language, like people who take up musical instruments later in life,
will never be a virtuoso." The nurture camp believes the language can be
picked up by anyone if it is worked at long enough. Or, "You'll get as
much out of it as you put in it." (as my piano teacher used to say). Is
this a fair assessment?
Judging from the amount of opinions that have been expressed on
append/3, is it safe to assume that others have had trouble with it, and
so it would be best for now to focus on understanding it's uses rather
than the clever way it was put together?
| |
|
|
Bart Demoen wrote:
> Folklore says that it took the inventors of Prolog about 3 ws
> to get their head around append/3.
Now lets talk about difference lists for a while! :-)
Two points:
1. Prolog programs like append/3 remind me of the cryptic epigrams
from some ancient gnostic gospel. The more time you spend thinking
about them, the more and more facets you see and the more enlightened
you get. Its amazing how much knowledge is packed into such tiny
little two-line programs.
2. Backtracking is really hard to understand--but easy to do.
Everybody knows how to use their "back" button in their web browser.
-Randy
| |
|
| > Judging from the amount of opinions that have been expressed on
> append/3, is it safe to assume that others have had trouble with it,
and
> so it would be best for now to focus on understanding it's uses
rather
> than the clever way it was put together?
Well, understanding its uses is one way of understanding how it was put
together. Dude, understanding append/3 is a journey, not a
destination. I've been programming in prolog for 10 years and I still
find new insights when I think about it some time.
| |
| Orso Balù 2005-03-27, 3:57 pm |
| "python1" <python1@spamless.net> ha scritto nel messaggio
news:d1pjjr01u01@enews3.newsguy.com...
> As a little background, I program in (good-ol' ANSI) C; script in dos, sh,
> and Python; and write a lot of SQL. I'm mainly a hobbiest.
>
> Trivial problems involving recursion are taking ages to solve/express in
> prolog. I assume that after some point it 'clicks', but the progression is
> slow. Bratko suggests thinking declaratively, as opposed to procedurally
> (which I catch myself drifting to), but either way seems non-intuitive.
>
> This is probably the third time I've tried to learn Prolog over the last
> half-decade, and once again progress has slowed to a stop once something
> like this comes up (from "Programming in Prolog"):
>
> append([],L,L).
> append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).
>
> ...which is understandable if contemplated long enough, but I don't think
> I would have come up with this on my own.
>
> How I read it is:
>
> 1. It is a fact that the boundary condition of appending occurs when the
> first input list is empty; the second and third must be equal.
>
> 2. It is a rule that appending, when the first and third input is a
> non-empty list, is satisfied if a call to append with the tail of the
> first input, the whole of the second input, and the tail of the third
> input is successful.
>
> ...phew. Is this how I should be thinking?
>
> How long did it take for /you/ to start thinking recursion?
I'm a hobbyst too, but have been programming professinally in SQL for years,
so let me try and draw a parallel between Prolog and SQL.
SQL is basically a declarative language: you tell what you want, but it's
the optimizer that figures out the how.
The first time a tryed a multitable jojn in SQL it drove me nuts try to
figure out the way the database engine was to travel from one table to the
next via foreign/primary key, and the resuting SQL statement was prticularly
ugly.
Then I learned not to care, and just tell the optimizer which field linked
to which fileld; I didn't try anymore to figure out te way the optimizer was
carrying on his job.
Now back to Prolog: a Prolog program is made of predicates, something
similar to sentences.
So you don't really need to think in recursively terms - as you would do in
a functional oriented language such as Lisp or Q - you just need to tell the
interpreter what "sentences" are true in such a way that they cover all
possible legal instances of something - you also tell the interpreter in
which order to test them, by writing first ones first.
With the append/3 predicate, you basically say:
1. the result od appending a list to a null list is the list itself
2. otherwise, if the first list is not empty, the first element of the
result will be the first item of the first list, and the rest will be like
appending the tail of the first list to the second list.
Is like reducing a problem in real life (more or less... :-) ):
1. a room is in order if everything is in its place
2. if something is out of place, pick one item, put it in place, then make
order in the room
JM2(hobbyst)C
Carlo
| |
| student 2005-03-28, 8:56 am |
| Orso Balù wrote:
> "python1" <python1@spamless.net> ha scritto nel messaggio
> news:d1pjjr01u01@enews3.newsguy.com...
>
>
Remember the first time you moved a kitchen chair and climbed onto it
so you could reach the cookie jar?
>
....
> ... a Prolog program is made of predicates, something
> similar to sentences.
>
> So you don't really need to think in recursively terms - as you would do in
> a functional oriented language such as Lisp or Q - you just need to tell the
> interpreter what "sentences" are true in such a way that they cover all
> possible legal instances of something - you also tell the interpreter in
> which order to test them, by writing first ones first.
>
> With the append/3 predicate, you basically say:
> 1. the result od appending a list to a null list is the list itself
> 2. otherwise, if the first list is not empty, the first element of the
> result will be the first item of the first list, and the rest will be like
> appending the tail of the first list to the second list.
>
> It's like reducing a problem in real life (more or less... :-) ):
>
> 1. a room is in order if everything is in its place
>
> 2. if something is out of place, pick one item, put it in place, then make
> order in the room
>
Exactly.
But the question remains, how are things like 'append/3' derived?
Where do they come from?
Or is Prolog just another IFYSWIM[*] language?
When we discourse in a language, we operate on representations
of the things we have in mind. Prolog programs are things, and
if we want to talk about Prolog programs we need to agree on how
Prolog programs are to be represented.
LPTP is a (magnificent!) Prolog program designed to assist in
the interactive development and testing of theorems about Prolog
programs, and LPTP represents Prolog clauses as variable-free
("ground") terms.
For example, in LPTP,
append([],L,L).
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3)
becomes
:- assert_clauses(n(append, 3),[
clause([n(append, 3), [n([], 0)], $l, $l],
[&],
[l]/0),
clause([n(append, 3), [n('.', 2), $x, $l1], $l2, [n('.', 2), $x, $l3]],
[n(append, 3), $l1, $l2, $l3],
[x, l1, l2, l3]/0) ]).
Note that the names of the original universally quantified
variables are listed explicitly.
LPTP is built around three basic predicates -- 'succeeds',
'fails', and 'terminates' -- which it uses to describe the
/behavior/ of ("pure") Prolog programs.
A Prolog variable 'X' is referred to as '?x'.
Once LPTP has converted 'append/3' into ground form,
I can ask it ("def" means "define")
?- def(succeeds append(?t1,?t2,?t3)).
-- which means
"What does 'succeeds append(?t1,?t2,?t3)' mean?"
-- and LPTP replies
?t1 = [] & ?t3 = ?t2 \/
(ex [x,l1,l3]: ?t1 = [?x|?l1] & ?t3 = [?x|?l3] &
succeeds append(?l1,?t2,?l3))
("\/" is logical "or" and "ex" is the existential quantifier).
Now, I don't know about you, but somehow this seems closer to
the way I think about Prolog than Prolog does. It certainly
comes close to your "you just need to tell the interpreter what
'sentences' are true in such a way that they cover all possible
legal instances of something", but It isn't Prolog. However, it
tells me exactly how to "conjure up" the thing it is talking
about, namely,
append(T1,T2,T3) :- T1 = [], T2 = T3.
append(T1,T2,T3) :- T1 = [X|L1], T3=[X|L3], append(L1,T2,L3).
which /is/ Prolog!
(If this form of 'append/3' is a bit hard on the eyes, by
interpreting the "=" signs on the right as shorthand for the
phrase "is of the same form as", and appealing to the definition
of unification, we get the more familiar
append([],T,T).
append([X|L1],T2,[X|L3]) :- append(L1,T2,L3).
)
So I suggest that it is not a bad idea to get in the habit
of mentally inserting "succeeds" in front of each Prolog goal
when reading a Prolog program -- i.e., to look at
append([],T,T).
append([X|L1],T2,[X|L3]) :- append(L1,T2,L3).
but to "see"
succeeds append([],T,T).
succeeds append([X|L1],T2,[X|L3]) :- succeeds append(L1,T2,L3).
What does this have to do with /deriving/ 'append/3'?
So far, nothing, but /what if/ LPTP had a command that allowed
users to input things like
:- define_succeeds(sublist,2,
all [l1,l2]:
?l1 = [] & ?l2 = [] \/
(ex [x,t1]: ?l1 = [?x|?t1] & succeeds sublist(?t1,?l2)) \/
(ex [x,t1,t2]: ?l1 = [?x|?t1] & ?l2 = [?x|?t2] & succeeds
sublist(?t1,?t2))
).
directly, and a command along the lines of
?- translate_succeeds(sublist(?l1,?l2)).
that would output the corresponding Prolog clauses
sublist(L1,L2) :- L1 = [], L2 = [].
sublist(L1,L2) :- L1 = [X|T1], sublist(T1,L2).
sublist(L1,L2) :- L1 = [X|T1], L2 = [X|T2], sublist(T1,T2).
or, even better,
sublist([], []).
sublist(]X|T1], L2) :- sublist(T1, L2),
sublist([X|T1], [X|T2]) :- sublist(T1, T2).
I think that would provide Prolog newcomers with something of a
useful middle ground, a sort of base camp for experimenting with
alternative definitions in a language that is closer to familiar
language than Prolog is, secure in the knowledge that once the
intended definition has been expressed in that language, it will
translate directly into Prolog.
Just a thought.
Reference: http://www.inf.ethz.ch/personal/staerk/lptp.html
[*] IFYSWIM stands for "if you see what I mean".
--
bill hogan
sequitur "AT" sonic "DOT" net
| |
| Torkel Franzen 2005-03-28, 8:56 am |
| student <nospam@a.b.c.dINVALID> writes:
> But the question remains, how are things like 'append/3' derived?
append/3 is a direct translation into Prolog of the (only
reasonable) recursive definition of list concatenation:
[]+L=L
[X|L1]+L=[X|L1+L]
which is how I present it to beginners.
| |
| Bart Demoen 2005-03-28, 8:58 pm |
| randy wrote:
> Dude, understanding append/3 is a journey, not a
> destination. I've been programming in prolog for 10 years and I still
> find new insights when I think about it some time.
>
Please share them with us.
Thanks in advance,
Bart Demoen
| |
| student 2005-03-29, 3:59 am |
| Torkel Franzen wrote:
> student <nospam@a.b.c.dINVALID> writes:
>
>
>
>
> append/3 is a direct translation into Prolog of the (only
> reasonable) recursive definition of list concatenation:
>
> []+L=L
> [X|L1]+L=[X|L1+L]
>
> which is how I present it to beginners
That is nice but the statement
> append/3 is a direct translation into Prolog of the (only
> reasonable) recursive definition of list concatenation:
>
> []+L=L
> [X|L1]+L=[X|L1+L]
by itself is classic IFYSWIM.
What does "direct translation" mean?
Do you have a Prolog program that does this?
Can every (cut-free, etc) Prolog predicate definition be expressed as
equations?
What do the equations for 'member/2' look like?
Or 'sublist/2'?
Do you have a theorem prover that understands these equations?
--
| |
| Torkel Franzen 2005-03-29, 3:59 am |
| student <nospam@a.b.c.dINVALID> writes:
> Can every (cut-free, etc) Prolog predicate definition be expressed as
> equations?
Indeed not, which as we know is one of the glories of Prolog! But
you asked about append/3. As for member and sublist, the same
principle applies: if you can program these predicates as
(boolean valued) functions, you can also produce the corresponding
Prolog predicates. Learning to think in terms of recursion isn't
tied to any particular programming language, or to the differences
between functional programming and logic programming. The trickier
part of Prolog appears when you choose not to program
deterministically, and then you need to think about just what
happens on backtracking. Sometimes, of course, you also need to
be aware of the distinction between unification and pattern matching.
append/3 is a showcase predicate because the direct translation of
the "inevitable" recursive definition yields an extremely
well-behaved predicate.
As for automating program transformations, or the production of
clauses from specifications, that's a separate subject.
| |
| student 2005-03-29, 8:58 am |
| Torkel Franzen wrote:
> student <nospam@a.b.c.dINVALID> writes:
>
>
>
>
> Indeed not, which as we know is one of the glories of Prolog!
Thank you.
> But you asked about append/3. ....
Actually, what I asked was "how are things like 'append/3' derived?"
and I think it is clear from the ensuing context that this was a
rhetorical flourish,
a bit of fanfare to get things rolling.
My question was (and is) implicit in my suggestion that it would be
nice if LPTP
allowed users to directly input predicate definitions in internal form,
instead of only being able
to see the internal forms of predicate definitions that arise when a
Prolog predicate
is translated into internal form by LPTP.
--
| |
| Torkel Franzen 2005-03-29, 8:58 am |
| student <nospam@a.b.c.dINVALID> writes:
> My question was (and is) implicit in my suggestion that it would be
> nice if LPTP
> allowed users to directly input predicate definitions in internal form,
> instead of only being able
> to see the internal forms of predicate definitions that arise when a
> Prolog predicate
> is translated into internal form by LPTP.
I'm sure LPTP is great stuff, but it's unlikely to help student
who are having trouble with with "thinking recursion".
| |
| Bart Demoen 2005-03-29, 8:58 am |
| Torkel Franzen wrote:
> append/3 is a direct translation into Prolog of the (only
> reasonable) recursive definition of list concatenation:
>
> []+L=L
> [X|L1]+L=[X|L1+L]
>
> which is how I present it to beginners.
Do beginners grok this better than a Prolog definition
of append/3 ? And if so, why/how/... in your opinion ?
Do these beginners know already about things like recurrence
relations (or recurrence equations, or difference equations)
at the moment you show this to them ? Do they know about
induction (maybe specific instances like transitive closure)
or fixed point computations ...
I am just trying to find out whether the people who had no
(or little) problem with recursive functions or predicates on
first sight have something in common.
Cheers
Bart Demoen
| |
| Bart Demoen 2005-03-29, 8:58 am |
| Torkel Franzen wrote:
> I'm sure LPTP is great stuff, but it's unlikely to help student
> who are having trouble with with "thinking recursion".
I feel the same. I can't see how the more complicated syntax can help
understanding recursion.
Cheers
Bart Demoen
| |
| Torkel Franzen 2005-03-29, 8:58 am |
| Bart Demoen <bmd@cs.kuleuven.ac.be> writes:
> Do beginners grok this better than a Prolog definition
> of append/3 ? And if so, why/how/... in your opinion ?
Some cheating is involved, since my students often have some
acquaintance with functional programming (Haskell). But it is my
impression that they have an easier time grasping recursive function
definitions than recursive predicates. This I think is connected with
the fact that thinking in terms of functions and computations and
equality is a lot more familar to students than thinking in terms of
predicates and "if-then".
> Do these beginners know already about things like recurrence
> relations (or recurrence equations, or difference equations)
> at the moment you show this to them ? Do they know about
> induction (maybe specific instances like transitive closure)
> or fixed point computations ...
I would guess that very few of my students know anything about
such stuff.
| |
| student 2005-03-29, 8:58 pm |
| Bart Demoen wrote:
> Torkel Franzen wrote:
>
>
>
> I feel the same. I can't see how the more complicated syntax can help
> understanding recursion.
>
> Cheers
>
> Bart Demoen
I neither said nor implied that I thought that "the [sic] more
complicated syntax would help understanding recursion" and I
neither said nor implied that LPTP was likely to "help student
[sic] who are having trouble with 'thinking recursion'".
That is not what the article to which you both seem in a big
hurry to attach impertinent rejoinders is about.
Apparently, neither of you read it, and I won't rehash it here
except, for the sake of young readers who may become by
such authoritative bombast, to say
1. The main point of the article to which I was replying was
precisely that "thinking recursion" is something we all do all
the time.
2. I agreed with that view in my first sentence and drew the
implication that the actual basis of the OP's complaint was not
named in his Subject line, but rather was expressed as follows:
>This is probably the third time I've tried to learn Prolog over
>the last half-decade, and once again progress has slowed to a
>stop once something like this comes up (from "Programming in
>Prolog"):
>append([],L,L).
>append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).
> ...which is understandable if contemplated long enough, but I
> don't think I would have come up with this on my own.
After pondering the matter over a period of days, a period
during which I happened also to be exploring LPTP, it occurred
to me that two issues were involved: (a) what is the best way to
/read/ Prolog predicates, and (b) how can Prolog predicates be
/derived/, as opposed to seemingly being snatched from thin air?
3. A Prolog *newcomer* can be anyone who has never worked with
Prolog before, a category which embraces everything from grammar
school students to PhDs, doctors, lawyers, engineers, actuaries,
documentation writers, and so on and so on.
| |
| student 2005-03-30, 9:00 am |
| > Torkel Franzen wrote:
>
>
p.s.
I notice that your equations appear to fit in with LPTP quite
nicely, at least if they are given a functional interpretation
(the following is from the file 'suffix.pr' in the LPTP library):
:- definition_fun(**,2,
all [l1,l2,l3]: succeeds list(?l1) =>
(?l1 ** ?l2 = ?l3 <=> succeeds append(?l1,?l2,?l3)),
existence by lemma(append:existence),
uniqueness by lemma(append:uniqueness)
).
:- corollary(app:nil,
all l: [] ** ?l = ?l,
[] ** ?l = ?l by uniqueness(**,2)
).
:- corollary(app:cons,
all [x,l1,l2]: succeeds list(?l1) =>
[?x|?l1] ** ?l2 = [?x|?l1 ** ?l2],
assume(succeeds list(?l1),
[succeeds append(?l1,?l2,?l1 ** ?l2) by existence(**,2),
succeeds append([?x|?l1],?l2,[?x|?l1 ** ?l2]), % by def. append/3.
succeeds list([?x|?l1]), % by def. list/1.
% succeeds append([?x|?l1],?l2,[?x|?l1] ** ?l2) by existence(**,2)
[?x|?l1] ** ?l2 = [?x|?l1 ** ?l2] by uniqueness(**,2)],
[?x|?l1] ** ?l2 = [?x|?l1 ** ?l2]) % q.e.d.
).
% = comments added by me
The TeX output is easier to read.
Proofs, not IFYSWIM.
| |
| Bart Demoen 2005-03-30, 8:58 pm |
|
student wrote:
> Bart Demoen wrote:
>
>
>
>
> I neither said nor implied that I thought that "the [sic] more
> complicated syntax would help understanding recursion" and I
> neither said nor implied that LPTP was likely to "help student
> [sic] who are having trouble with 'thinking recursion'".
Where did you get the idea that I (or Torkel) was implying that you
said something particular ? This thread is about "Thinking recursion"
and my (particular) comment was related to the the introduction of LPTP
into this thread.
> That is not what the article to which you both seem in a big
> hurry to attach impertinent rejoinders is about.
When I am in a [sic] big hurry, my response time is way shorter.
> Apparently, neither of you read it,
I did read it. Torkel can speak for himself if he wants to.
I didn't find anything in LPTP as you presented it of any help to
people trying to "think recursion" (remember: it's the thread subject).
I went to the LPTP home page - didn't help.
> for the sake of young readers who may become by
> such authoritative bombast
Oh dear, now you might be underestimating, maybe insulting, the young
readers. What is your own age ?
Don't get upset so quickly: newsgroups are there for expressing
opinions; that's what I did, and that's what Torkel did. If you think
I (or Torkel) am mistaken, please give arguments. Do you think that LPTP
helps in thinking recursion ?
Cheers
Bart Demoen
| |
| Bart Demoen 2005-03-30, 8:58 pm |
| Torkel Franzen wrote:
> Bart Demoen <bmd@cs.kuleuven.ac.be> writes:
>
>
>
>
>
> Some cheating is involved, since my students often have some
> acquaintance with functional programming (Haskell).
Ah, a fairly common pattern: one can only grasp recursion the first time
one hears about it, if one has heard about it before ...
Cheers
Bart Demoen
| |
| Jan Burse 2005-03-30, 8:58 pm |
| Try (for runtime Types):
------------------------
list([]).
list([_|Y]) :- list(Y).
append([],X,X) :- list(X).
append([X|Y],Z,[X|T]) :- append(Y,Z,T).
?- append([],2,X).
No
?- append([],[2],X).
X=[2]
Yes
Try (for compiletime Types):
----------------------------
:- op(700,xfx,'@').
X@T :- var(X), !, X=var(T).
var(S)@T :- !, S=T.
true@t.
append(X,Y,Z)@t :- X@list, Y@list, Z@list.
[]@list.
[_|Y]@list :- Y@list.
kb(append([],X,X),true).
kb(append([X|Y],Z,[X|T]),append(Y,Z,T)).
ok_kb :- \+ (kb(A,B), \+ (A@t, B@t)).
ok_goal(X) :- X@t.
?- ok_kb.
Yes
?- ok_goal(append([],2,X)).
No
?- ok_goal(append([],2,X)).
No
?- ok_goal(append([],[2],X)).
X = var(list)
Yes
bill hogan wrote:
> append /holds/ only for a certain well-defined subset of the set
> of all 3-tuples of Prolog terms but, yes, any of the constituents of
> such a 3-tuple can be any Prolog term whatsoever.
>
> ?- append([], 2, 2 ).
> Yes
>
> ?- append([a,b,c], 2, Q).
>
> Q = [a, b, c |2]
>
> 'Prolog' as defined by the ISO at this time does not include
> type definitions or typed or sorted predicate declarations.
> [Type definitions catch errors of form (e.g.,
> 'append([a,b,c],2,Q)' where 'append([a,b,c],[2],Q)' was
> intended), while sorts catch errors of agreement (e.g.
> 'speed(123,bmw)' where 'speed(bmw,123)' was intended). Types can
| |
| Bill Spight 2005-03-30, 8:58 pm |
| Dear Bart, et al.,
Bart Demoen wrote:
>
> Torkel Franzen wrote:
>
> Ah, a fairly common pattern: one can only grasp recursion the first time
> one hears about it, if one has heard about it before ...
>
> Cheers
>
> Bart Demoen
I once taught Computers and Problem Solving at an alternative high
school in the U. S. About half the class were above average. ;-)
My first homework assignment was a variant of the game, 20 Questions.
They were to have someone look up a word in the dictionary, and then
they had 20 yes-or-no questions to guess the word. One of my students
(out of eight) discovered binary search. (Only approximate, OC, since
she used page numbers. But she got the principle.) Furthermore, the
whole class got it in short order.
Now, binary search is recursive. So are a lot of problem-solving
strategies. IMX, most people (teenagers and up) who are interested in
such things have little trouble understanding such recursive strategies.
But context matters. If they are trying to get computers to do things,
they might find writing recursive programs difficult. The mind set is
different.
Best,
Bill
| |
| Markus Triska 2005-03-31, 8:57 am |
| Bart Demoen wrote:
> Don't get upset so quickly: newsgroups are there for expressing
> opinions; that's what I did, and that's what Torkel did.
Personally, I'm glad that you changed your opinion about this matter. I
remember the different Bart of the previous year who - moderately upset
- wrote in response to another reader: "But replies as from tmp123 ...
please no more !".
Cheers!
All the best,
Markus.
| |
| Bart Demoen 2005-03-31, 3:59 pm |
| NNTP-Posting-Host: seven.kulnet.kuleuven.ac.be
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: ikaria.belnet.be 1112293335 29822 134.58.127.12 (31 Mar 2005 18:22:15 GMT)
X-Complaints-To: abuse@belnet.be
NNTP-Posting-Date: Thu, 31 Mar 2005 18:22:15 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7) Gecko/20040616
X-Accept-Language: en-us, en
In-Reply-To: <424be5ac$0$8024$3b214f66@tunews.univie.ac.at>
Cache-Post-Path: seven.kulnet.kuleuven.ac.be!unknown@10-91-97-252.kotnet.org
X-Cache: nntpcache 2.4.0b5 (see http://www.nntpcache.org/)
Xref: number1.nntp.dca.giganews.com comp.lang.prolog:27594
Markus Triska wrote:
> Bart Demoen wrote:
>
>
>
> Personally, I'm glad that you changed your opinion about this matter. I
> remember the different Bart of the previous year who - moderately upset
> - wrote in response to another reader: "But replies as from tmp123 ...
> please no more !".
I am sorry to disappoint you: I have not changed my opinion about this
matter. I fully stick to what I wrote at both occasions and there is in
my opinion no contradiction.
Cheers
Bart Demoen
| |
| tmp123 2005-04-01, 3:59 pm |
| Bart Demoen wrote:
> Markus Triska wrote:
matter. I[color=darkred]
upset[color=darkred]
....[color=darkred]
>
> I am sorry to disappoint you: I have not changed my opinion about
this
> matter. I fully stick to what I wrote at both occasions and there is
in
> my opinion no contradiction.
>
> Cheers
>
> Bart Demoen
As I said on 2005/01/07, I will no write more non-technical comments
until next year.
However, in the old post, I still waiting the answer to my proposal of
algorithm. I hope one day I will read it, and improve my programming
knowledgment from the answer.
Well, now I'm here, so, even when I'm not prolog/python teacher nor
expert:
After sometime thinking the post from "python1" where he describes the
steps thinking a functional program vs a prolog program, I'm wondering
that if the decomposition of the steps goes a few in deep, it starts to
appear a lot of similarities between both processes. (by example: loop
doing... could be decomposed in loop until what? doing what?. The
answer to the fist gives the end loop condition or the end rule, ...).
In fact, a lot of the algorithms that are presented in this group are
more near to LISP than to prolog. (oops, this assertion will produce
strong answers ;-) ). Example: assert/retract and cut are sometimes
taken as the worst things of the (virtual) world.
| |
| Bart Demoen 2005-04-01, 8:57 pm |
| tmp123 wrote:
> However, in the old post, I still waiting the answer to my proposal of
> algorithm. I hope one day I will read it, and improve my programming
> knowledgment from the answer.
The program (you call it proposal of an algorithm) did not solve the
OP's request, as you changed the accepted input - this in itself was
essential in allowing you to write the program you wrote. You might
think that enlarging the accepted input makes your program superior
to programs that did stick to the OP's restrictions, but I think you
would be mistaken.
Your program lacks what you would probably name Prolog quality; you have
given the following advice many times: use more cuts. However, your
program has too few cuts. For two reasons: the way it uses cuts
(actually very few of them) is not uniform and your style would benefit
from using cuts consistently (I would suggest consistently not using it,
but then your program wouldn't work at all). Secondly, without the extra
cuts that you ommitted, your program has a very weird behaviour on
backtracking.
I will come back to the cut issue later in this post.
> In fact, a lot of the algorithms that are presented in this group are
> more near to LISP than to prolog. (oops, this assertion will produce
> strong answers ;-) ). Example: assert/retract and cut are sometimes
> taken as the worst things of the (virtual) world.
They are. If you think that assert/retract and cut make out the
essentials of Prolog, and that those builtins are the best things about
Prolog, I beg you to reconsider. Cut is sometimes named "the goto of
LP" and for good reasons. There are red and green cuts - if you didn't
know that, there is one more reason to reconsider your opinion about
cut. Have you seen recently the program posted here for doing the
Dijkstra algorithm, sprinkled with assert/retract ? I am sure that
intelligent people like yourself can understand it fully and make
changes to it confidently, but would you recommend this style of Prolog
programming ? Would that increase the confidence in Prolog elsewhere ?
Would sligthly less intelligent people than yourself be able to
understand fully the program ? Do yo know about programming with
invariants ? It's not very popular these days apparently, but it has its
value when it comes to proving programs correct. Prolog has a very weird
semantics for assert/retract (it's named the "logical database update
semantics" or something like that - but it has nothing to do with
logic). [not that there is a better logical semantics] Constructing
invariants for Prolog programs that use assert/retract in a liberal way
can be a nightmare.
As long as the programs in this group are closer to Lisp than what you
think Prolog is, we are fine - at least if it's pure Lisp, not the one
with the setq or replaca.
Once more: please reconsider your idea about Prolog (and perhaps LP in
general).
Cheers
Bart Demoen
| |
| tmp123 2005-04-06, 12:44 pm |
| Hi Bart,
Thanks for your answer. More thanks for an answer that is constructive.
Please, if you still with a few free time, could you (or any other
reader) also comment this one?
> Bart Demoen wrote:
>
> They are. If you think that assert/retract and cut make out the
> essentials of Prolog, and that those builtins are the best things
about
> Prolog, I beg you to reconsider. Cut is sometimes named "the goto of
> LP" and for good reasons. There are red and green cuts - if you
didn't
> know that, there is one more reason to reconsider your opinion about
> cut.
Well, about cuts, I'm not "pro" nor "contra". After years hearing the
bad aspects of "goto" statements, I've seen years of the advantages of
"try/catch/raise" :-).
> Prolog has a very weird semantics for assert/retract.
The biggest point: Assert/retract are the base to implement learning,
and learning is AI.
Other usages of "assert": well, if someone needs to store information,
store it in parameters, rules, or others (by example, SWI has several
very interesting methods) is only a subject of performance in
execution/memory/... . If the programmer writes an easy to mantain
source, then, no problem.
> Do yo know about programming with
> invariants ? It's not very popular these days apparently, but it has
its
> value when it comes to proving programs correct.
Excellent! If you came to Barcelona, I pay you a beer ;-). It is the
first time from 2003 (at least, according to a fast google search) this
concept appears in this group. More about it and its relation with
prolog?
>
> As long as the programs in this group are closer to Lisp than what
you
> think Prolog is, we are fine - at least if it's pure Lisp, not the
one
> with the setq or replaca.
>
> Once more: please reconsider your idea about Prolog (and perhaps LP
in
> general).
It is important analize the difficulties for a programmer about think
an imperative, a functional or a prolog program.
However, for my current interest it is more important why is so
difficult for a computer to understand ANYTHING? (sorry for the
uppers).
LP is the nearest to solve the problem I'm interested:
Example 1:
A file is a list of bytes, an ascii text file is a list of lines, a
line is a list of characters, a character is one byte, ... .
Why it is not posible to fix that in some rules like:
| file(X) <- ascii_file(X).
| list_of(X,ascii_line) <- ascii_file(X).
| list_of(X,chars) <- ascii_line(X).
| ...
and from it (comment: this is more near to a generic librarian that any
other ?), the own computer should be able to execute/generate
program/... directly things like:
| ?- let(ascii_file(foo)) in sum(foo,N).
| N=1234
| yes
OK, it is posible to translate "sum" to prolog, or python, or perl, but
with cost and with loss of generality. In the translation, errors can
be inserted (worst). Prolog is near my objective, but I do not know how
to reach it. Suggestions?.
Example 2:
the "echo" program is OK iff for all message(M) received from
communication channel(C) exist a message(N) sent by C and
data(M)=data(N), with quality measure minimize the sum of times between
M and N.
Natural language is not the subject. If, after write this in any
syntax, the computer is able to do it (execute it or generate the
source of a program that does it), the target is reached.
Here, it seems (?) that prolog is insufficient because:
a) lack of planning.
b) lack of logic calculus, HOL vs FOL, ...?
>
> Cheers
>
> Bart Demoen
| |
| Bart Demoen 2005-04-06, 12:44 pm |
| tmp123 wrote:
> The biggest point: Assert/retract are the base to implement learning,
ILP doesn't need to use assert/retract - still it learns.
> It is important analize the difficulties for a programmer about think
> an imperative, a functional or a prolog program.
> However, for my current interest it is more important why is so
> difficult for a computer to understand ANYTHING? (sorry for the
> uppers).
Maybe you should have a look at Answer Set Programming - it might appeal
to you.
Cheers
Bart Demoen
| |
| Matthew Huntbach 2005-04-06, 12:44 pm |
| On Sat, 2 Apr 2005, tmp123 wrote:
[color=darkred]
> The biggest point: Assert/retract are the base to implement learning,
> and learning is AI.
Only if you're going to mix up object level and meta level code,
which is often not a good idea.
> Other usages of "assert": well, if someone needs to store information,
> store it in parameters, rules, or others (by example, SWI has several
> very interesting methods) is only a subject of performance in
> execution/memory/... . If the programmer writes an easy to mantain
> source, then, no problem.
There may be a few occasions where use of assert/retract is appropriate,
or at least acceptable. However in many cases, the recent code someone
gave for the Dijkstra shortest path algorithm is a good example, they
are used despite the fact that a way of expressing the algorithm
which is just as efficient but does not use assert/retract can be
found in Prolog, and the chances are the algorithm expressed in this
way will look a lot clearer than the version which uses assert/retract.
So in general I find it a good rule, unless the person who has written
the code really knows what they are doing and is known to be a real
expert with Prolog, to assume that if you see a piece of Prolog code
which makes use of assert/retract, it's been written by someone who
just doesn't think in Prolog and so is using it to obtain a mutable
data structure of the sort you'd find in imperative languages.
Matthew Huntbach
|
|
|
|
|