Teaching Prolog - many just don't get it!
Dan Benanav
of students. I find that most students just dont get it. We are
using the Bratko book. I don't believe the book is the problem.
For the first 3-4 weeks I discussed only prolog. For the next
3-4 weeks I discussed prolog and natural language processing.
After that time I gave an exam which included the following question:
Write a predicate insertlast that inserts and element E onto the
end of a list L. For example:
?- insertlast(c, [a,b], X).
> X = [a,b,c].
That was supposed to be the easy question. Many, in fact a majority
did not get the question right. Previous to the exam, I had spent
several classes going over similar questions.
Has anyone else experienced this problem ot similar problems with other
languages?
Dan
Doug Nicholson
>Write a predicate insertlast that inserts and element E onto the
>end of a list L. For example:
>?- insertlast(c, [a,b], X).
>> X = [a,b,c].
>
>That was supposed to be the easy question. Many, in fact a majority
>did not get the question right. Previous to the exam, I had spent
>several classes going over similar questions.
>
>Has anyone else experienced this problem ot similar problems with other
>languages?
The Intro to Programming course for CS majors at the U of Minnesota
uses Abelson and Sussman's "Structure and Interpretation of Computer
Programs" which has a mini logic programming language written in
Scheme in, I believe, chapter 4. The instructor had a question
like this on the final. I got it right but I sure as hell don't
know why! Neither the book or the instructor explained the situation
very well.
I imagine the when I get around to studying Prolog in more depth I'll
figure it out. I didn't have any trouble grasping the more basic
'deductive reasoning' type stuff. I blame it on being unable to
break through my long familiarity with procedural languages to
declarative ones.
Michael Covington
back in 1987 because so many students had so much trouble with ordinary
Prolog textbooks (although Bratko's is one of the best and I wouldn't
have expected a problem with it).
Too often, students start out determined to believe that Prolog works
just like Pascal, and when it doesn't, they conclude it doesn't work in
any definite way at all (i.e., they think that as soon as you start
thinking about it as logic, you can stop thinking about the process actually
going on in the computer).
I don't really know what to advise, other than maybe to take a look at
our book, and at my article, "Efficient Prolog: A Practical Tutorial,"
which appeared in Artificial Intelligence Review a year or two ago.
(PROLOG PROGRAMMING IN DEPTH is currently out of print, but some copies
are available from the U. of Georgia. A new edition will come out, from
a different publisher, in about a year.)
--
:- Michael A. Covington internet mcov...@ai.uga.edu : *****
:- Artificial Intelligence Programs phone 706 542-0358 : *********
:- The University of Georgia fax 706 542-0349 : * * *
:- Athens, Georgia 30602-7415 U.S.A. amateur radio N4TMI : ** *** **
Michael Covington
>In article <Mar.26.13.57....@pilot.njin.net> ben...@pilot.njin.net (Dan Benanav) writes:
>
>>Write a predicate insertlast that inserts and element E onto the
>>end of a list L. For example:
>>?- insertlast(c, [a,b], X).
>>> X = [a,b,c].
>Scheme in, I believe, chapter 4. The instructor had a question
>like this on the final. I got it right but I sure as hell don't
>know why! Neither the book or the instructor explained the situation
>very well.
Here's how I would explain it.
Lists have a logic (i.e., a structure) all their own. Every list consists
of an element plus another list (unless it's empty).
So if you want to define
insertlast(E,List,NewList)
(given E and List) you have to decide whether List is empty or nonempty,
and do different things in the two cases.
If List is empty, it's obvious what to do: just make a list out of E,
and that's your answer. Thus:
insertlast(E,[],[E]).
But List may not be empty. If that's the case, you want to skip over and
preserve its first element, and then recursively do to the rest of it the
exact same thing you were going to do to the whole list:
insertlast(E,[First|Rest],[First|NewRest]) :- insertlast(E,Rest,NewRest).
Crucially: The First element stays the same, the Rest gets changed to NewRest
by a recursive invocation of insertlast.
WHY THIS IS HARD: It's natural to think of putting First and NewRest
together as the _last_ operation, after you've computed NewRest.
But it's not written last in Prolog. In fact it doesn't _happen_ last,
either; upon seeing [First|NewRest] in the argument list, the Prolog
system goes ahead and makes a list whose first element is First and whose
rest is a pointer to something that is going to be computed.
That is, a crucial step in the computation is done by the pattern
matcher, not by any explicit operation. And that takes some getting
used to.
Markus Fromherz
> In article <1993Mar26.1...@walter.cray.com> tin...@ferris.cray.com (Doug Nicholson) writes:
> >In article <Mar.26.13.57....@pilot.njin.net> ben...@pilot.njin.net (Dan Benanav) writes:
> >
> >>Write a predicate insertlast that inserts and element E onto the
> >>end of a list L. For example:
> >>?- insertlast(c, [a,b], X).
> >>> X = [a,b,c].
>
> Here's how I would explain it.
... lines deleleted
> insertlast(E,[First|Rest],[First|NewRest]) :- insertlast(E,Rest,NewRest).
>
> WHY THIS IS HARD: It's natural to think of putting First and NewRest
> together as the _last_ operation, after you've computed NewRest.
> But it's not written last in Prolog. In fact it doesn't _happen_ last,
> either; ...
>
> That is, a crucial step in the computation is done by the pattern
> matcher, not by any explicit operation. And that takes some getting
> used to.
Because you want to explain both ways of looking at Prolog - the declarative
way and the procedural way - I found it useful to contrast the above clause
with the following,
insertlast(E, List, NewList) :-
List = [First|Rest],
insertlast(E, Rest, NewRest),
NewList = [First|NewRest].
and then to show that both versions are equivalent declaratively (but different
procedurally). The second version allows one to defer some explanations of
logical variables.
-- Markus Fromherz
Xerox PARC, Systems and Practices Lab | Tel.: +1 (415) 812-4273
3333 Coyote Hill Road | Fax.: +1 (415) 812-4334
Palo Alto, CA 94304 | E-Mail: from...@parc.xerox.com
Gopal Gupta
Now that teaching of Prolog/Logic Programming is being discussed
on the net, let me take this opportunity to point everyone's
attention to an interesting project being done at NMSU.
At NMSU, we are developing a set of CS courses based on the
Logic Programming paradigm for teaching introductory programming
to freshman Computer Science majors. Two such classes have already
been taught over the last three semesters. (The courses are taught
in conjunction with closely coordinated Math courses)
Also, a birds-of-a-feather session was held in the last ICLP to discuss
the issues involved. Some very interesting discussion took place
during the session (A report appears in the recent ALP Newsletter).
A Technical Report containing a copy of the article and copies of
transparencies of the various speakers can be obtained (if you are
interested) by sending email to ju...@nmsu.edu.
Gopal Gupta
---------------------------------------------------------------------
Department of Computer Science email: gu...@nmsu.edu
Box 30001, Dept. 3CS gu...@compsci.bristol.ac.uk
New Mexico State University Ph: +1 (505) 646 6236
Las Cruces, NM 88003-0001 Fax: +1 (505) 646 6218
USA
---------------------------------------------------------------------
Dennis C Merritt
>In article <Mar.26.13.57....@pilot.njin.net> ben...@pilot.njin.net (Dan Benanav) writes:
>>Write a predicate insertlast that inserts and element E onto the
>>end of a list L. For example:
>>?- insertlast(c, [a,b], X).
>>> X = [a,b,c].
>>
>>That was supposed to be the easy question. Many, in fact a majority
>>did not get the question right. Previous to the exam, I had spent
>>several classes going over similar questions.
>>
>>Has anyone else experienced this problem ot similar problems with other
>>languages?
>I imagine the when I get around to studying Prolog in more depth I'll
>figure it out. I didn't have any trouble grasping the more basic
>'deductive reasoning' type stuff. I blame it on being unable to
>break through my long familiarity with procedural languages to
>declarative ones.
I suspect the problem is not so much not understanding the declarative
nature of Prolog, but rather not understanding the procedural aspects of
recursive list utilities.
Because of the way lists are represented, list utilities most do something
with the head of the list and then recurse with the tail. If you are
trying to implement something like insertlast, or more commonly, append/3
that approach is somewhat counterintuitive. The problem gets the student
focusing on the end of the list, but the solution comes from the head.
--
Amziod--Software, Hardwoods & Books
40 Samuel Prescott Dr., Stow, MA 01775 USA
Tel 508/897-7332, FAX 508/897-2784, amz...@world.std.com
Dennis C Merritt
do with its user interface.
According to Dave Liddle the most important aspect of a user interface is
the degree to which it leads the user to a good conceptual model of how
the thing works. A user interface that does this will encourage
experimentation, which will work as expected, which will lead to deeper
understanding which will lead to more experimentation and so on drawing
the user in.
By contrast, a interface that leads to a faulty conceptual model will
cause frustration.
Most conventional programming languages are very good in this respect, the
syntax of the language (its user interface) leads one to a good
understanding of how a computer works. This is probably why they are so
addictive.
Prolog, on the other hand, has a syntax that makes one think it is logic.
Everything about the language is designed to make it appear declarative
and logical. But thats not how it works, it works by backtracking and
unification. Nothing about the design of the language gives the new user
any clue as to how Prolog actually works.
This makes it a frustrating language to work with until, through some
means or another the student learns how it works. Once that is
understood, then it becomes a lot of fun.
The same is true of many AI tools, they all deliberately hide how they
work, making them appear easy on the surface, but in fact making them
really accessible only to those stubborn enough to figure out how they
really work.
Dennis Merritt
Dan Benanav
>I suspect the problem is not so much not understanding the declarative
>nature of Prolog, but rather not understanding the procedural aspects of
>recursive list utilities.
Yes, I would tend to agree. Students have trouble with recursion,
and the problem is that prolog forces one to write recursive programs.
I suspect that many students would be unable to write recursive versions
of the insertlast program in C, pascal or some other procedural language.
Dan
Mireille Ducasse
>>
>> I suspect the problem is not so much not understanding the declarative
>> nature of Prolog, but rather not understanding the procedural aspects of
>> recursive list utilities.
This is were TRACERS help. They provide a model of the procedural
semantics of Prolog suited for people used to think in this term.
If I were to teach Prolog, besides the declarative explanations, I
would demonstrate its procedural semantics by explaning traces of
typical programs. (This is actually how *I* got to understand Prolog
and *believe* you could program with it :-)).
If you want to do this you'd better check how accurate the model
provided by your tracer is. Some models are more confusing than
helpful. You have to make sure that what is traced really happens!
Some people will object that a step by step trace is too low-level.
Actually on small programs (and typical programs should be small) this
is not really a problem, and "procedural" people are usually happy to
see all the details to fully understand what is happening.
However, if you would like to show your students a higher level of the
procedural semantics of Prolog, I would recommend to use OPIUM. With
OPIUM you can program what has to be traced and how it is to be traced.
Although it has not been developed with teaching purposes in mind the
abstract views described in the paper referenced below should be a
good start.
Opium is distributed to academic sites together with Eclipse, ECRC's
Prolog system for a nominal fee of a few hundreds DM.
@InProceedings(ducasse91,
Author="M. Ducass\'{e}",
Title="Abstract views of {Prolog} executions in {Opium}",
BookTitle="Proceedings of the International Logic Programming
Symposium",
Year="1991",
Editor="V. Saraswat and K. Ueda",
Address="San Diego",
Publisher="MIT Press",
Month="October",
Pages="18-32")
Abstract:
Opium is a system for analysing and debugging Prolog programs. Its
kernel comprises an execution tracer and a programming language with a
full set of primitives for trace and source analysis.
In this paper we show the power of Opium for supporting abstract views
of Prolog executions. Abstract views give high-level points of view
about the execution. They filter out irrelevant details; they
restructure the remaining information; and they compact it so that the
amount of information given at each step has a reasonable size. The
examples of abstract views given in the following are a goal execution
profile, some data abstractions, an instantiation profile, a failure
analysis and a kind of explanation for an expert system written in
Prolog.
-------------------------------------------------------------------
Mireille Ducasse' email: mire...@ecrc.de
ECRC phone: +49 89 926 99 142
Arabellastr. 17, fax: +49 89 926 99 170
D-8000 Munich 81 Tx : 5216910
Tomas Arvidsson
Programming (where everything is done in Prolog):
In <Mar.28.21.12....@pilot.njin.net> ben...@pilot.njin.net
(Dan Benanav) writes:
>amz...@world.std.com (Dennis C Merritt) writes:
>>I suspect the problem is not so much not understanding the declarative
>>nature of Prolog, but rather not understanding the procedural aspects of
>>recursive list utilities.
>Yes, I would tend to agree. Students have trouble with recursion,
>and the problem is that prolog forces one to write recursive programs.
Nah, recursion is not the problem. The problem is getting that
recursive algoritm written in Prolog syntax and understanding all the
things taken care of by the language itself. Ofcourse, that is
something that applies to me and not necessarily anybody else.
For example; I have no problem writing or understanding insertLast if I it
is done recursively in LISP but in Prolog...
> Dan
--
Tomas Arvidson ///
d91...@csd.uu.se, ///
tom...@nada.kth.se, tom...@sprawl.adsp.sub.org \\\///
Expressed opinions are mine unless stated otherwise \XX/
--
Tomas Arvidson ///
d91...@csd.uu.se, ///
tom...@nada.kth.se, tom...@sprawl.adsp.sub.org \\\///
Expressed opinions are mine unless stated otherwise \XX/
Matthew Huntbach
>Too often, students start out determined to believe that Prolog works
>just like Pascal, and when it doesn't, they conclude it doesn't work in
>any definite way at all (i.e., they think that as soon as you start
>thinking about it as logic, you can stop thinking about the process actually
>going on in the computer).
>
that Prolog is a rather myterious thing, completely different
from any other programming language.
My solution is rather than introduce it through the "logic" or
"database" approach, to introduce it gradually, starting off with
simple recursive list-processing examples (I am assuming they
have already seen recursion in imperative or functional
languages). At this stage, I tell them that '=' is assignment,
but that unlike imperative languages, variables cannot be
re-assigned. All output is done through "=", not through
goal/clause-head unification.
From this one can gradually introduce various Prolog features -
tell them that "=" is actually more powerful than assignment,
it means something like "make equal", introduce backtracking
through the idea of non-determinism, etc.
If anyone is interested in comparing this approach to others, I
have a set of notes using it whcih I could post (sorry they're
not machine readable).
Matthew Huntbach
Dept. of Computer Science
Queen Mary and Westfield College
London E1 4NS
UK
Dan Benanav
>Nah, recursion is not the problem. The problem is getting that
>recursive algoritm written in Prolog syntax and understanding all the
>things taken care of by the language itself. Ofcourse, that is
>something that applies to me and not necessarily anybody else.
>For example; I have no problem writing or understanding insertLast if I it
>is done recursively in LISP but in Prolog...
In lisp the solution looks like:
(defun insertlast(E,X)
(cond
((null X) (list E))
(t (cons (car X) (insertlast E (cdr X))))))
In prolog the solution looks like:
insertlast(E,[],[E]).
insertlast(E,[Z|Y],[Z|R]) :- insertlast(E,Y,R).
What makes prolog harder then lisp?
D.S.Riches
%tom...@dront.nada.kth.se (Tomas Arvidsson) writes:
%
%
%>Nah, recursion is not the problem. The problem is getting that
%>recursive algoritm written in Prolog syntax and understanding all the
%>things taken care of by the language itself. Ofcourse, that is
%>something that applies to me and not necessarily anybody else.
%
%>For example; I have no problem writing or understanding insertLast if I it
%>is done recursively in LISP but in Prolog...
%
%In lisp the solution looks like:
%(defun insertlast(E,X)
% (cond
% ((null X) (list E))
% (t (cons (car X) (insertlast E (cdr X))))))
%
%In prolog the solution looks like:
%insertlast(E,[],[E]).
%insertlast(E,[Z|Y],[Z|R]) :- insertlast(E,Y,R).
%
%What makes prolog harder then lisp?
Well speaking as one who hasn't programmed in either, I can see
straight away that the LISP one is recursive but I can't on the Prolog
one.
Dave Riches
Email: David.S...@bnr.co.uk
Smail: BNR Europe Ltd, London Road,
Harlow, Essex. CM17 9NA. England
Phone: +44 (0)279-402496
Fax: +44 (0)279-402047
Tom Fawcett
>For example; I have no problem writing or understanding insertLast if I it
>is done recursively in LISP but in Prolog...
In lisp the solution looks like:
(defun insertlast(E,X)
(cond
((null X) (list E))
(t (cons (car X) (insertlast E (cdr X))))))
In prolog the solution looks like:
insertlast(E,[],[E]).
insertlast(E,[Z|Y],[Z|R]) :- insertlast(E,Y,R).
What makes prolog harder then lisp?
Two answers:
1) LISP is procedural. In general, if you're used to a procedural language, a
declarative one is hard to understand. Rutgers students still begin with
Pascal, yes?
2) In this example, the list construction in LISP is out in the open: car,
cdr, cons. In the Prolog example, half the work is being done by unification
in the head.
-Tom
Peter Jackson,CH237A,,
> tom...@dront.nada.kth.se (Tomas Arvidsson) writes:
>
>>For example; I have no problem writing or understanding insertLast if I it
>>is done recursively in LISP but in Prolog...
>
> In lisp the solution looks like:
> (defun insertlast(E,X)
> (cond
> ((null X) (list E))
> (t (cons (car X) (insertlast E (cdr X))))))
>
> In prolog the solution looks like:
> insertlast(E,[],[E]).
> insertlast(E,[Z|Y],[Z|R]) :- insertlast(E,Y,R).
>
> What makes prolog harder then lisp?
Surely the problem is the following. Arguments to LISP functions
are input variables, whereas arguments to PROLOG procedures can be
input variables or output variables.
Assume that 'insertlast' is called so that the third argument is
bound to the result.
Then [Z|Y] performs a CAR and [Z|R] performs a CONS. So two constructs
with the same declarative meaning get a different procedural interpretation
depending upon the context of the procedure call.
Needless to say. students are confused.
--
Peter Jackson
Department of Electrical & Computer Engineering
Clarkson University, Potsdam, NY 13699, USA
Michael Covington
>
>Then [Z|Y] performs a CAR and [Z|R] performs a CONS. So two constructs
>with the same declarative meaning get a different procedural interpretation
>depending upon the context of the procedure call.
>
>Needless to say. students are confused.
Only if they insist on thinking in Lisp. CAR + CDR and CONS are the _same_
pattern. Just as
a = b + c
is the same equation whether you are solving for a, b, or c.
Tomas Arvidsson
>tom...@dront.nada.kth.se (Tomas Arvidsson) writes:
>>For example; I have no problem writing or understanding insertLast if I it
>>is done recursively in LISP but in Prolog...
>
>[LISP version of insertlast removed]
>In prolog the solution looks like:
>insertlast(E,[],[E]).
>insertlast(E,[Z|Y],[Z|R]) :- insertlast(E,Y,R).
>What makes prolog harder then lisp?
The way variables are used and all "hidden" steps, i.e. no explicit
car, cdr or null functions. In the end I guess it's all about
understanding the unification procedure, which I apparently haven't
grasped yet...
Frank Deutschmann
>From article <Mar.30.08.07....@pilot.njin.net>, by ben...@pilot.njin.net (Dan Benanav):
>> tom...@dront.nada.kth.se (Tomas Arvidsson) writes:
>>
>>>For example; I have no problem writing or understanding insertLast if I it
>>>is done recursively in LISP but in Prolog...
>>
>> In lisp the solution looks like:
>> (defun insertlast(E,X)
>> (cond
>> ((null X) (list E))
>> (t (cons (car X) (insertlast E (cdr X))))))
>>
>> In prolog the solution looks like:
>> insertlast(E,[],[E]).
>> insertlast(E,[Z|Y],[Z|R]) :- insertlast(E,Y,R).
>>
>> What makes prolog harder then lisp?
>Surely the problem is the following. Arguments to LISP functions
>are input variables, whereas arguments to PROLOG procedures can be
>input variables or output variables.
>Assume that 'insertlast' is called so that the third argument is
>bound to the result.
>Then [Z|Y] performs a CAR and [Z|R] performs a CONS. So two constructs
>with the same declarative meaning get a different procedural interpretation
>depending upon the context of the procedure call.
I'd go even further and say that, in PROLOG, what look like input
arguments are really serving the purposes of input variables, output
variables, as well as _conditional expressions_. For me (I started
learning PROLOG four years ago...), the big jump was recognizing the
difference between function invocation in proceedural languages, and
unification in PROLOG; these are two very different ways of thinking
about the world...
Beyond this, I think one of the most confusing aspects of PROLOG
(without constraints) is the difference between math expressions, and
other predicates; even today, I still find myself trying to use
ordinary PROLOG's as equation solvers, but that (of course!) doesn't
work, as programming in PROLOG is not exactly the same as programming
in logic (though perhaps someday logic programming and functional
programming will be married in some clean way)....
-frank
--
EMail: f...@panix.com | Money creates taste. -Jenny Holzer
Phone: 1 - 212 / 765 - 2050 | N O T !! -Madonna
Dennis C Merritt
faw...@iron.cs.umass.edu (Tom Fawcett) writes:
>ben...@pilot.njin.net (Dan Benanav) writes:
> >For example; I have no problem writing or understanding insertLast if I it
> >is done recursively in LISP but in Prolog...
>Two answers:
>1) LISP is procedural. In general, if you're used to a procedural language, a
>declarative one is hard to understand. Rutgers students still begin with
>Pascal, yes?
>2) In this example, the list construction in LISP is out in the open: car,
>cdr, cons. In the Prolog example, half the work is being done by unification
>in the head.
>-Tom
The point is well taken, and goes back to the hidden magic of Prolog, in
this case unification.
Anoteher difficulty is the syntactic sugar of the list notation in Prolog.
It further hides whats going on. The dot notation, while denser,
actually is more revealing as to what Prolog is doing in a recursive list
predicate. If you think of a list as .(a,.(b,.(c ...))) then the point of
the recursions becomes a little clearer.
Dennis
Lee Naish
>amz...@world.std.com (Dennis C Merritt) writes:
>
>>I suspect the problem is not so much not understanding the declarative
>>nature of Prolog, but rather not understanding the procedural aspects of
>>recursive list utilities.
>
>Yes, I would tend to agree.
But such simple predicates can be written without knowledge of the
procedural aspects of Prolog, and they generally work. If you can
get student to write logically correct definitions (whether or not they
work in Prolog) its a good thing. If you use a text such as Bratko you
need to provide additional help. The section in Bratko on "The
relationship between Prolog and logic" is less than a page long. Bratko
deliberately avoids logic to be "more practical". I'm not convinced
this is a good idea.
lee
Shinji Kono
tom...@dront.nada.kth.se (Tomas Arvidsson) writes
In my experiences, troubles are comming from combination of
Prolog features:
Unification
Recursion
Backtracking
Each features are easy to unerstand for many students. But a combination
of Unification and Recursion is difficult. I saw some studuent gave up
to understand the combination and used asseerts with repeat-failer-loop.
So it is not better to teach backtracing and assert in the eary stage
of teaching course.
Here is my suggestion. Think a Prolog clause in this way:
procedure_name(Input,Output) :-
check_on(Input),
!,
generate(Output).
For example,
ap([H|X],Y,[H|Z]) :- ap(X,Y,Z).
can be understand like this:
ap(Input1,Input2,Output) :-
Input1 = [H|T],
!,
ap(T,Input2,Output1),
Output = [H|Output1].
This reveals the procedural nature of Prolog, which is a heart of
Prolog invention.
In article <Mar.30.08.07....@pilot.njin.net>,
ben...@pilot.njin.net (Dan Benanav) writes:
> insertlast(E,[],[E]).
> insertlast(E,[Z|Y],[Z|R]) :- insertlast(E,Y,R).
How about this?
insertlast(E,List,Output) :-
List = [],
!,
Output = [E].
insertlast(E,List,Output) :-
List = [H|Tail],
!,
insertlast(E,Tail,Output1),
Output = [H|,Output1].
Of course, logical meaning are easily recovered. In case of Lisp, this
a little difficult.
---
Shinji Kono @ ko...@csl.sony.co.jp
河野真治 Sony Computer Science Laboratory, Inc,Japan
Peter Jackson,CH237A,,
> In article <1993Mar30....@news.clarkson.edu> jac...@sandman.ece.clarkson.edu (Peter Jackson,CH237A,,) writes:
>>
>>Then [Z|Y] performs a CAR and [Z|R] performs a CONS. So two constructs
>>with the same declarative meaning get a different procedural interpretation
>>depending upon the context of the procedure call.
>>
>>Needless to say. students are confused.
>
> Only if they insist on thinking in Lisp. CAR + CDR and CONS are the _same_
> pattern. Just as
>
> a = b + c
>
> is the same equation whether you are solving for a, b, or c.
> --
i agree absolutely, although actually solving the equation for a, b or c
is different in each case from a procedural point of view.
the point is that students (whatever previous languages they have learned)
will have no prior experience of different context-dependent procedural interpretations
of programming constructs that look the same. this difficulty is *added* to all
the usual difficulties of understanding recursion (although, to be fair, you don't have
to puzzle over composition of recursive calls, as you do in functional langauges).
of course, once you understand it, you can see it's rather elegant.
(for 'thinking in Lisp' you should perhaps substitute 'thinking in any other extant
programming language which does list processing.')
David Poole
>>amz...@world.std.com (Dennis C Merritt) writes:
>>>I suspect the problem is not so much not understanding the declarative
>>>nature of Prolog, but rather not understanding the procedural aspects of
>>>recursive list utilities.
>procedural aspects of Prolog, and they generally work. If you can
>get student to write logically correct definitions (whether or not they
>work in Prolog) its a good thing.
I completely agree with Lee. I have taught Prolog for about 10 years now,
and I am convinced that the best way to learn it is to learn logic as a
specification language first.
The best way to understand the program:
insertlast(E,[],[E]).
insertlast(E,[Z|Y],[Z|R]) :- insertlast(E,Y,R).
is bottom up. Treat it is a proof in mathematical induction.
Show that mathematical induction = recursion.
Students find it a bit confusing at first, but quickly like this idea
of mathematics made less abstract (and even runnable). Only after they
have written lots of programs (specifications), and can write these
comfortably do we give a way to execute these (and then give both
bottom-up and top-down interpreters).
Instead of telling students that Prolog is really neat, and then give
give them lots of procedural baggage, and then they get to think that
Prolog is really stupid. Try telling them that it is really stupid,
and let them realise that it is really neat.
Only at the very end should you tell them that there are all these
tricks that you can use to make current implementations / current
incarnations of logic programming more efficient (and "more practical").
I know a number of AI people who dislike Prolog because it is such a
weak logic, with such a dumb search strategy. I tell them that Prolog
is interesting precisely because it is such a weak logic and has such
a dumb search straetegy. But it is nice to separate these, and
consider the specificiation langauge (the logic), and then to give
Prolog's search strategy as one of the many possible (and many
available). You should also remember that not all logic programming
langauages have the same search strategy (e.g., deductive database
langauges, and constraint logic programming languages). They typically
have the same logic, though. What we teach them about logic
programming should be trasferable to these other implemenmtations.
There are lots of other people who study specification languages, and
who consider them essential for programming (in the large). We often
have software engineering people coming through to give talks and they
give specificiation langauges which are syntactic variants (usually
weaker, and more ad hoc) of pure Prolog. They claim these are useful
for speficiations of large software systems. It is in some sense a
black mark on the logic programming community that we are known for
hacking in this obscure langaue called Prolog, instead of being the
experts in specificiation langauges, who have deep theories, and
excellent implementations of good specification languages. The problem
probably lies in how we teach logic programming.....
David Poole
Michael Covington
implementation of pure logic, nor a pure procedural language, but rather
a reasonable compromise between the two.
Its theorem prover has obvious limitations, resulting from the desire from
efficiency; but if you use it right, you can write programs that are at
once logical specifications and executable procedures.
Bart Demoen
I teach my students first how to write logic programs starting from a (verbal)
description of the problem. They learn about the meaning of a logic program
and later about (refutation) strategies as a means to discover something about
the meaning. And then Prolog comes in. Even at the end of the course, I write
down the flemmish description of a problem and its logic specification before
the Prolog program appears on the blackboard. Even for 'simple' things like
insertlast/3. And I make sure they are shown the difference between the two
statements
I am writing a predicate that inserts something at the end of a given list
and
I am writing a predicate that specifies the relation between 2 lists
and an object such that ...
Another point is that Prolog text books introduce lists too quickly, as if
they are the most important thing about Prolog. If I need 'lists' in my course,
I specify them by the abstract operations on them: firstel/2 listtail/2
lastel/2 (yes of course, if that is natural in the specification). It is
one of the problems of Prolog that it doesn't really invite you to program
that way, but invites you to make the abstract operations explicit from the
beginning.
Bart Demoen
Matthew Huntbach
>In my experiences, troubles are comming from combination of
>Prolog features:
> Unification
> Recursion
> Backtracking
>Each features are easy to unerstand for many students. But a combination
>of Unification and Recursion is difficult. I saw some studuent gave up
>to understand the combination and used asseerts with repeat-failer-loop.
>So it is not better to teach backtracing and assert in the eary stage
>of teaching course.
>
earlier: first as a simple functional language, in which output is
given by explicit assignment using '=' to a variable, so that
they get used to recursion, following this the gradual
introduction of bactracking and full unification; assert and
retract only given in a section on advanced techniques at the
end.
Yes, I know this is not the "politically correct" way of
teaching Prolog, but I am sorry, I just find that most people,
at least those who've already done some programming in other
languages, find it much easier this way, and I've seen too many
people put off Prolog and made hopelessly confused by the
over-hyped notion that it's "just programming in pure logic".
Matthew Huntbach
Shinji Kono
bim...@cs.kuleuven.ac.be (Bart Demoen) writes
There are many relations between lists in insertlast/3. So students
have to learn a practical method of finding useful relations. This is
not easy, especially in list manipulation.
>Another point is that Prolog text books introduce lists too quickly, as if
>they are the most important thing about Prolog.
So I think this is correct. When we teach logic programming, it is better
to avoid lists. List processing requires careful thoughts on clause selection
and program termination which are out of logical semantics.
To find out useful relations, decompositon of the prolbem can be a
guidance. These are classification of input / output variable,
classification of recursive predicate / simple system call and case
analysis of calling sequence. Then we can construct a horn clause like this:
procdure(Input,Output) :-
check(Input), !, generate(Output).
The check part is usually trivial for list processing.
The cut is essential here to seprate Input and Output. This can avoid
uncesessary backtrack which annoys early stage students. After that,
the students can learn remove cuts in necessary cluases to achive
correct don't know non-determinisms.
Olivier Ridoux
>>
>>Needless to say. students are confused.
>
> Only if they insist on thinking in Lisp. CAR + CDR and CONS are the _same_
> pattern. Just as
>
> a = b + c
>
> is the same equation whether you are solving for a, b, or c.
I do not think students insist on thinking in Lisp, but they are not
ready for thinking in terms of equation solving.
Moreover, the equation solving point of view is misleading as for
Prolog (without constraints), because the only terms Prolog can solve
for are first-order terms, and the only domains students think of
solving for are numerical domains. Thinking this way, they would
surely try to solve a=b+c with unification.
Olivier
Arindam Das
> %>is done recursively in LISP but in Prolog...
> %
> %In lisp the solution looks like:
> %(defun insertlast(E,X)
> % (cond
> % ((null X) (list E))
> % (t (cons (car X) (insertlast E (cdr X))))))
> %
> %In prolog the solution looks like:
> %insertlast(E,[],[E]).
> %insertlast(E,[Z|Y],[Z|R]) :- insertlast(E,Y,R).
> %
> %What makes prolog harder then lisp?
>
>
> Well speaking as one who hasn't programmed in either, I can see
> straight away that the LISP one is recursive but I can't on the Prolog
> one.
> Dave Riches
well Dave,
if you are meaning that recursive semantic in above prolog code is
a bit hard to grasp we can give a try. The subgoal interLast in the
2nd rule finally matches with the first rule when the Y becomes empty
since we were stripping the head of the second argument List in the
2nd rule one by one. The moment Y unifies with [], backtracking
starts.
-arindam
--
Arindam Das email: ari...@CS.Uwindsor.Ca
Dept. of Comp. Sci. ph# (519)253-4232Ext 3003/3007
U. of Windsor, Ont, Canada
Lee Naish
>In article <1993Apr1.0...@cs.kuleuven.ac.be> ,
> bim...@cs.kuleuven.ac.be (Bart Demoen) writes
>> I am writing a predicate that inserts something at the end
>> I am writing a predicate that specifies the relation between 2 lists
>
>There are many relations between lists in insertlast/3. So students
>have to learn a practical method of finding useful relations.
As Bart says, there is ONE relation between the lists we are interested
in specifying (code given earlier).
> List processing requires careful thoughts on clause selection
>and program termination which are out of logical semantics.
It is a common misconception (shared by many authors of prolog texts)
that clause selection has something to do with termination. If your
program is not polluted with cuts and other nasties, the size of the
search space is independent of the order in which clauses are selected.
Termination does depend on the order in which atoms are selected, but in
many simple examples, such as insertlast/3 and append/3, there is no
choice in what atom to select so there is no problem.
> procdure(Input,Output) :-
> check(Input), !, generate(Output).
>The check part is usually trivial for list processing.
>
>The cut is essential here to seprate Input and Output.
1) It is not "essential" or even desirable to separate input and output
2) It is not even necessary to have the concept of input and output
3) Even if you do think of input and output, and want to separate them
for some reason, it is not necessary or desirable to use cut.
4) It would be better to use assert('Beam me up'(Scotty)) than cut.
5) It would be even better to use 'true'.
6) It would be better still to use a comment!
>This can avoid
>uncesessary backtrack which annoys early stage students.
It also makes it impossible to use the declarative semantics which is
useful to people at all stages. Backtracking is only a problem if you
are thinking very procedurally. If you want students to only write
deterministic code initially then tell them the input checks should be
mutually exclusive.
>After that,
>the students can learn remove cuts in necessary cluases to achive
>correct don't know non-determinisms.
Have you taught may people Prolog? If so, that may partially explain
why there are so many people who put useless, if not incorrect, confusing,
confused and inefficient cuts in their code.
lee
Warren A. Postma
>implementation of pure logic, nor a pure procedural language, but rather
>a reasonable compromise between the two.
>
>Its theorem prover has obvious limitations, resulting from the desire from
>efficiency; but if you use it right, you can write programs that are at
>once logical specifications and executable procedures.
>
I am currently in the throes of dismembering my brain, trying to learn
prolog. It certainly makes you bend over backwards to get where you need to be,
but once you see something actually function properly, like a sort, when all
you've told the prolog compiler is that:
- if the first list is identical to the sorted list, we're done
- if the first two items of the list are out of order, swap them,
and check the rest of the list.
This is still very new to me. I am trying to understand the set operations
given to us in class. Can anyone suggest an FTP site containing a tutorial
on thinking-in-prolog. It's rather mind-bending.
Warren Postma
CompSci III
University of Western Ontario
.
pos...@gaul.csd.uwo.ca
.
Shinji Kono
l...@munta.cs.mu.OZ.AU (Lee Naish) writes
>in specifying (code given earlier).
The question is how to find out the relation. An easy way is decomposition
of the problem with dataflow and data structure. This analysis is necessary
even if we use automatic generation of program from abstract specification.
Prolog is a programming language which is a logic + control, so we have to
think about dataflow.
>Termination does depend on the order in which atoms are selected, but in
>many simple examples, such as insertlast/3 and append/3, there is no
>choice in what atom to select so there is no problem.
Then why append(X,[a,b,c],X) does not terminate? Or why brother(A,B) :-
brother(B,A) is bad in Prolog? Students have to know how to avoid these
kind of things.
procdure(Input,Output) :-
check(Input), !, generate(Output).
This form gives students a natural way of problem analysis. This cut
is logically safe because we can remove cut and add necessary exclusive
condition to the program without changing its semantics. But it is
usually redundant and time consuming (for human and machine). To write
exclusive conditions, cuts are convenient and reduce errors for
beginners.
>3) Even if you do think of input and output, and want to separate them
>for some reason, it is not necessary or desirable to use cut.
The cut is introduces only to separate backtracking, as you said. But in
this way, it gives useful declarative semantics for all ground input
with the cut. It is also useful on incomplete data structure such as
D-lists or var(X) technique, where there are no clear logical
semantics.
I think it is better to teach cut as a short cut of writing exclusive
conditions rather than correct usage of negation in Prolog. And it is
better to teach cut in early stage of learning Prolog, since backtracking
is the major obstacle.
Fergus James HENDERSON
> procdure(Input,Output) :-
> check(Input), !, generate(Output).
>
>This form gives students a natural way of problem analysis. This cut
>is logically safe because we can remove cut and add necessary exclusive
>condition to the program without changing its semantics. But it is
>usually redundant and time consuming (for human and machine). To write
>exclusive conditions, cuts are convenient and reduce errors for
>beginners.
This cut is not logically safe at all - it *does* change the semantics.
The predicate can no longer be used backwards.
Cuts are difficult for students to understand.
Hell, cuts are difficult for *everyone* to understand.
If writing exclusive conditions is tedious, then use if-then-else.
It is much much better, and much easier to understand, if you write
foo :-
( bar ->
baz
;
barf
).
(pronounced "if bar, then baz, else barf") than if you write
foo :- bar, !, baz.
foo :- barf.
It corresponds much more closely with what students have already learned
in other languages.
Furthermore, it may well even be more efficient.
Admittedly, '->' is non-logical. However it is much much clearer than cut.
If your version of Prolog has a logical form of if-then-else (ie.
one that delays if the condition is not ground) then you can use that
instead, to get purely logical, declarative programs.
>>3) Even if you do think of input and output, and want to separate them
>>for some reason, it is not necessary or desirable to use cut.
>
>The cut is introduces only to separate backtracking, as you said. But in
>this way, it gives useful declarative semantics for all ground input
>with the cut.
I don't understand this. The presence of any cut except a green cut
essentially destroys the declarative semantics of a predicate.
It certainly doesn't *add* any useful declarative semantics.
>It is also useful on incomplete data structure such as
>D-lists or var(X) technique, where there are no clear logical
>semantics.
I don't see why cut is useful with difference lists.
You shouldn't be teaching your beginning students about var/1, IMHO.
But even when you use var/1 you can and should use '->' instead of cut.
>I think it is better to teach cut as a short cut of writing exclusive
>conditions rather than correct usage of negation in Prolog.
I can't agree. Correct usage of negation in Prolog should be easy.
Correct usage of cut *is* difficult. Even many textbook authors get
it wrong!
>And it is
>better to teach cut in early stage of learning Prolog, since backtracking
>is the major obstacle.
Why not teach your students about choice points, when they are created,
and how to avoid them, rather than teaching them how to remove choice
points that they didn't need to create in the first place?
P.S.
Here's a "proof" that arrow is significantly simpler than cut:
meta-interpreting prolog with '->' is significantly simpler than
meta-interpreting prolog with '!'.
% A simple meta-interpreter for pure Prolog with '->'
solve(true).
solve((A,B)) :- solve(A), solve(B).
solve((A;B)) :- solve(A) ; solve(B).
solve((A->B;C)) :- solve(A) -> solve(B) ; solve(C). % Look, it's trivial.
solve(A) :- clause(A,B), solve(B).
(I have an example which meta-interprets cut, but it's too long to post ;-)
--
Fergus Henderson f...@munta.cs.mu.OZ.AU
This .signature virus is a self-referential statement that is true - but
you will only be able to consistently believe it if you copy it to your own
.signature file!
Paul Singleton
> [reasonable stuff on 'cut' deleted]
> It is much much better, and much easier to understand, if you write
> foo :-
> ( bar ->
> baz
> ;
> barf
> ).
> (pronounced "if bar, then baz, else barf") than if you write
> foo :- bar, !, baz.
> foo :- barf.
I write foo :-
IF bar
THEN baz
ELSE barf
FI
(and then employ the C preprocessor).
This, too, is pronounced "if bar, then baz, else barf" :-) ("fi" optional).
The resemblance to ALGOL 68 is not accidental, and helps to remind me that
if-then-else is not logical implication (as misleadingly suggested by the
traditional '->' notation). I found it easier to change the concrete
syntax than to change the semantics :-)
Better still, I try to follow RAOK's advice and avoid ELSE, since one
nearly always really means "ELSE IF another_condition" (about the only
redundant cases are extralogical ones such as
IF var(X)
THEN ...
ELIF nonvar(X)
THEN ...
> (I have an example which meta-interprets cut, but it's too long to post ;-)
Then there's something wrong with it, or with your posting program :-)
Paul
----
__ __ Paul Singleton (Mr) JANET: pa...@uk.ac.keele.cs
|__) (__ Computer Science Dept. other: pa...@cs.keele.ac.uk
| . __). Keele University, Newcastle, tel: +44 (0)782 621111 x7355
Staffs ST5 5BG, ENGLAND fax: +44 (0)782 713082
Jens Kilian
So any if-then-else will match the second clause first.
^^^^^^
Oops, I meant to write third.
Sorry,
Jens.
--
Internet: je...@hpbeo82.bbn.hp.com HPDESK : JENS_KILIAN%XU@HP1200
MausNet: Jens Kilian @ BB KILIAN_JENS/HP1200_XU@hpbbi4
-------------------------------------------------------------------------------
As the air to a bird, or the sea to a fish, so is contempt to the contemptible.
Jens Kilian
> solve((A,B)) :- solve(A), solve(B).
> solve((A;B)) :- solve(A) ; solve(B).
> solve((A->B;C)) :- solve(A) -> solve(B) ; solve(C). % Look, it's trivial.
> solve(A) :- clause(A,B), solve(B).
Sorry, won't work (given the usual operator priorities of ';'/2 and '->'/2).
A -> B ; C is really ';'('->'(A, B), C)
So any if-then-else will match the second clause first.
Besides, this program won't handle A -> B alone.
Greetings,
Shinji Kono
f...@munta.cs.mu.OZ.AU (Fergus James HENDERSON) writes
>The predicate can no longer be used backwards.
I think this form is common in practical applications:
procdure(Input,Output) :-
check(Input), !, generate(Output).
So I think it shuold be justified rather than be drived out. The facts are:
1. Cut is necessary to write practical application.
2. Writing reversible predicates is more difficult than directed predicates.
As a directed predicates ( or functional predicates), this cut is safe.
>If writing exclusive conditions is tedious, then use if-then-else.
> foo :-( bar ->baz;barf).
>Admittedly, '->' is non-logical. However it is much much clearer than cut.
This is essentially the same as I intended. If there are no need of
cut with if-then-else, you are right. But it introduces another syntax
and another inference rule and it is not easy to understand.
>Here's a "proof" that arrow is significantly simpler than cut:
>meta-interpreting prolog with '->' is significantly simpler than
>meta-interpreting prolog with '!'.
>(I have an example which meta-interprets cut, but it's too long to post ;-)
Yes, it is easy to write meta interpreter for the form. Assume
clause(A,Check,B) stands for A :- Check,!,B.
solve(true).
solve((A,B)) :- solve(A), solve(B).
solve((A;B)) :- solve(A) ; solve(B).
solve(A) :- clause(A,Check,B), solve(Check),!,solve(B). % Look, it's trivial.
----
Fergus James HENDERSON
>In article <930980...@mulga.cs.mu.OZ.AU> ,
> f...@munta.cs.mu.OZ.AU (Fergus James HENDERSON) writes
>>This cut is not logically safe at all - it *does* change the semantics.
>>The predicate can no longer be used backwards.
>
>I think this form is common in practical applications:
> procdure(Input,Output) :-
> check(Input), !, generate(Output).
>So I think it shuold be justified rather than be drived out. The facts are:
> 1. Cut is necessary to write practical application.
This is definitely not the case. It is quite easy to demonstrate that
arrow can be used to replace cut. Furthermore, if your code is otherwise
logical, you can replace arrow with a logical if-then-else if your
Prolog supports such a thing (NU-Prolog does), resulting in purely
logical code.
> 2. Writing reversible predicates is more difficult than directed predicates.
Yes. But if you learn to program with cuts strewn throughout your code,
then learning to write reversible predicates will probably be well-nigh
impossible, IMHO.
>As a directed predicates ( or functional predicates), this cut is safe.
>
>>If writing exclusive conditions is tedious, then use if-then-else.
>> foo :-( bar ->baz;barf).
>>Admittedly, '->' is non-logical. However it is much much clearer than cut.
>
>This is essentially the same as I intended. If there are no need of
>cut with if-then-else, you are right. But it introduces another syntax
>and another inference rule and it is not easy to understand.
The only new thing about the syntax is that it is a new predefined
operator. You could say the same thing about cut only worse: it
introduces another syntax, but instead of introducing another inference
rule it actually makes a difficult-to-understand non-local modification
to the existing inference rule. As I keep saying, arrow is (IHMO)
considerably *easier* to understand than cut.
Another advantage of using arrow instead of cut is that it makes it
impossible to introduce errors by accidentally binding output too early
in the head. Eg.
max(X,Y,X) :- X >= Y, !.
max(_,Y,Y).
This example of how (NOT) to write max/3 comes from Bratko, "Prolog
Programming for Artificial Intelligence", which contains numerous other
examples of the same sort of bug. Note that in describing the process
of producing the above code, Bratko writes the following psuedo-code
as explanation:
If X >= Y then Max = X,
otherwise Max = Y.
Using arrow not only corresponds directly with the explanation (ie.
it's easier to understand), it also *ensures* that you delay output
unification, avoiding the bug.
max(X,Y,Z) :-
(X >= Y ->
Z = X
;
Z = Y
).
>>Here's a "proof" that arrow is significantly simpler than cut:
>>meta-interpreting prolog with '->' is significantly simpler than
>>meta-interpreting prolog with '!'.
>>(I have an example which meta-interprets cut, but it's too long to post ;-)
>Yes, it is easy to write meta interpreter for the form. Assume
>clause(A,Check,B) stands for A :- Check,!,B.
But this does not give you a general meta-interpreter that can handle
cuts, it only gives you a meta-interpreter than can handle your form.
Your code doesn't handle cut within disjunctions or multiple cuts within
a single clause. (Also to be fair, you should write your meta-interpreter
in a form in which it can directly interpret itself - this means adding
adding code for clause/3 in terms of clause/2.)
The problem is that you are using a chainsaw (cut) when really what you
want is something more delicate. It's just like the use of goto vs.
structured programming constructs, or the use of completely general
and arbitrary pointers vs. the use of typed pointers.
Cut is *too* general. Just as with the use of goto, using a more
restrictive construct would result in programs that are more readable
and more maintainable and would make optimization easier.
P.S. my "trivial" meta-interpreter had a bug. I posted something like
solve(A->B;C) :- solve(A) -> solve(B) ; solve(C).
This should have been
solve(A->B) :- solve(A) -> solve(B).
% add "; fail" if your Prolog is non-standard (ie. NU-Prolog).
since the ';' part of A->B;C was already handled by the code for disjunctions.
Lars-Henrik Eriksson
So I think it shuold be justified rather than be drived out. The facts are:
1. Cut is necessary to write practical application.
This is not a fact at all! I have a practical application of about
3800 lines of Prolog. This program contains about half a dozen
"necessary" cuts. Most of them have to do with i/o and one or two are
part of a very dirty bug fix that I didn't take the time to do right.
I also have a rather large number of "green" cuts, but these are not
necessary.
--
Lars-Henrik Eriksson Internet: l...@sics.se
Swedish Institute of Computer Science Phone (intn'l): +46 8 752 15 09
Box 1263 Telefon (nat'l): 08 - 752 15 09
S-164 28 KISTA, SWEDEN Fax: +46 8 751 72 30
Shinji Kono
>impossible to introduce errors by accidentally binding output too early
>in the head. Eg.
> max(X,Y,X) :- X >= Y, !.
> max(_,Y,Y).
If this is a buggy code, then
append([],X,X).
append([H|X],Y,[H|Z]) :- append(X,Y,Z).
is also buggy one. As I mentioned before this code loops forever on
?- append(X,[a,b,c],X).
Please remember the original question is how to teach students Prolog
programming. The code of append is logically correct but it is buggy
for some Prolog call. Why?
We are different in a stand point of logic / control separation.
To represent logic of a program, neither cut nor if-then-else is necessary.
Two codes are buggy from a view point of control. The mode of predicates
are wrong. For max(+,+,-), append(+,+,-),
max(X,Y,Z) :- X >= Y, !, Z = X.
max(X,Y,Z) :- X < Y, !, Z = Y.
append([],X,Y) :- !, Y = X.
append([H|X],Y,Z) :- !, Z = [H|Z1],append(X,Y,Z1).
are a little more correct. We can optimize these tedious controls if we
use append in one directional way and we can recover the same program.
We are different in the question:
Input / Output should be separated syntactically in Prolog?
For logical relation of program, this question is meaningless. When we
write a procedural program it is important.
>Yes. But if you learn to program with cuts strewn throughout your code,
>then learning to write reversible predicates will probably be well-nigh
>impossible, IMHO.
Usually for different modes different controls are required. We can
check these different modes using this form:
procdure(Input,Output) :- var(Input), !, generate(Output).
procdure(Output,Input) :- var(Input), !, generate(Output).
>>Yes, it is easy to write meta interpreter for the form. Assume
>>clause(A,Check,B) stands for A :- Check,!,B.
>But this does not give you a general meta-interpreter that can handle
>cuts, it only gives you a meta-interpreter than can handle your form.
General cut is harmful indeed, I agree. The meta interpreter proves
that if-then-else and my restricted cut are essentially the same from your
proof method, that's all. I think cut should be introduced as an operator
rather than a system predicate.
>Cut is *too* general. Just as with the use of goto, using a more
>restrictive construct would result in programs that are more readable
>and more maintainable and would make optimization easier.
This type of cut is easy to understand because it is very clear which
choice point is cut. Yes, choice point of current clause. If-then-else
structure affects choice point in a hidden way. It is impossible to
teach if-then-else without mentionning choice point, then why not teach
cut instead?
The necessary information for maintenance and optimization is data flow,
that is,
mode of predicate (Input / Output) and
clear declaration of choice point.
Students have to learn about these after logical relation of program.
This also becomes usefull guide for list manipuration, such as
insertlast/3. This is my answer to the original question. Do you really
answer the question?
Jonas Almgren
> check(Input), !, generate(Output).
I think this form is common in committed choice languages, not
particularly in Prolog. In most "practical" cases, I think the input
parsing and output generation is mixed in the body of the clause,
>So I think it shuold be justified rather than be drived out. The facts are:
> 1. Cut is necessary to write practical applicationn.
Why do you think so? At Quintus they are working on a very practical
application called WorkPro. It's so practical it is sold for money,
which cannot be said for most existing Prolog applications. WorkPro
interfaces X and RDBMSes, and consists of about 60.000 lines of Prolog
code. I can assure you that not a single occurrence of cut in WorkPro
is put there by "default". All predicates that should be deterministic
are written in such a way that they are. Of course, the people at
Quintus know how to write Prolog code, and how to utilize 1st argument
indexing, and I think this is the point. You should not teach people
how to cheat with Prolog (i.e. make them believe they understand
Prolog when they don't), but rather train them in how to write
"proper" (i.e. readable and efficient) Prolog programs, as it was
intended by David H. D. Warren and his followers.
> 2. Writing reversible predicates is more difficult than directed predicates.
I agree. Most predicates in WorkPro are not reversible. But this is not
an argument for more cuts.
Regards,
Jonas Almgren
Note: The advantages of Prolog are very different from those of committed
choice languages, and to utilize the benefits of Prolog, Prolog programs
must be written in a very different style.
--------------------------------------------------------------------
Disclaimer: My opinions are personal and not necessarily approved by
my employer, ProActive Software, Inc.
Saumya K. Debray
>WorkPro interfaces X and RDBMSes, and consists of about 60.000 lines of
>Prolog code. I can assure you that not a single occurrence of cut in
>WorkPro is put there by "default". All predicates that should be
>deterministic are written in such a way that they are. Of course, the
>people at Quintus know how to write Prolog code, and how to utilize 1st
>argument indexing, and I think this is the point.
I don't know about you (or about the people who wrote WorkPro), but not
infrequently I find myself writing code that has the general structure
p(M, N, ...) :- M =< N, ...
p(M, N, ...) :- M > N, ...
The last time I looked, most Prolog systems out there wouldn't recognize
that these clauses are mutually exclusive, and would create a choice
point, so I'd *have* *to* put in cuts to get decent performance. It's
embarrassing as hell when you've just told your idealistic young students
all about the Goodness of pure declarative programming and the Evils
of cuts, and they go off and work very hard to write their pure Prolog
programs only to find they can't run their code without blowing the stack
unless they put in some cuts. So you hem and haw and rationalize about
how "green cuts are OK", and it sounds like a giant cop-out, which of
course it is.
I agree that abusing cuts is a Bad Thing. I agree that first argument
indexing is a Good Thing, and that we should try to take advantage of
it where possible rather than use cuts. But it's not a panacea, and
there's no point pretending that it is.
--
Saumya Debray
CIS Dept, University of Oregon, Eugene, OR
deb...@cs.uoregon.edu
Tom Fawcett
You should not teach people how to cheat with Prolog (i.e. make them
believe they understand Prolog when they don't), but rather train them in
how to write "proper" (i.e. readable and efficient) Prolog programs, as it
was intended by David H. D. Warren and his followers.
Never have I seen a remark that made Prolog seem so much like a
religious cult.
-Tom
Ted Dunning
In article <FAWCETT.93...@iron.cs.umass.edu>
faw...@iron.cs.umass.edu (Tom Fawcett) writes:
jo...@proactive.com (Jonas Almgren) writes:
been listening very long?
-Tom
-ted
Michael Covington
>In article <FAWCETT.93...@iron.cs.umass.edu>
>faw...@iron.cs.umass.edu (Tom Fawcett) writes:
> jo...@proactive.com (Jonas Almgren) writes:
> efficient) Prolog programs, as it was intended by David H. D.
> Warren and his followers.
> Never have I seen a remark that made Prolog seem so much like a
> religious cult.
>been listening very long?
The thing is, of course, excessive purism impedes the practical use of
Prolog. I used to take flak for referring to Prolog predicate defi-
nitions as "procedures," which is exactly what they are.
--
:- Michael A. Covington, Associate Research Scientist : *****
:- Artificial Intelligence Programs mcov...@ai.uga.edu : *********
:- The University of Georgia phone 706 542-0358 : * * *
Jonas Almgren
>Never have I seen a remark that made Prolog seem so much like a
>religious cult.
I've never thought of myself as promoting a religious cult..., but
there are definitely different beliefs within the Prolog community.
Personally, I prefer to look at Prolog as a programming language.
Nothing more. Nothing less. Those who believe a Prolog program is a
runable specification, and those who believe a Prolog program is
closely related to logic, do not belong to the same cult as me.
Now, when we soon will have a Prolog standard, it should be clear that
Prolog is a language with so many fundamental features relying on
execution model rather than declarative model, that if our schools
want to produce competent *Prolog* programmers, they must teach Prolog
from a program-flow point of view, rather than as an "extension" to
logic. The confusion of and discrepancy between Prolog, the language,
and Prolog, the theory, has in my opinion caused: (1) The confusion
many students feel when faced with writing a Prolog program (2) The
bad programming practices with which many (most?) Prolog programs are
written. The former has resulted in students leaving universities
thinking that Prolog is really weird, the latter has resulted in the
common perception that Prolog is extremely inefficient. (1) and (2)
taken together explains why the true benefits of Prolog so often are
forgotten. David H.D. Warren made Prolog practical by devising an
efficient implementation strategy - it's a shame when universities
make Prolog *impractical* by not teaching how to utilize the benefits of
this implementation strategy.
deb...@majestix.cs.uoregon.edu (Saumya K. Debray) writes:
>I agree that abusing cuts is a Bad Thing. I agree that first argument
>indexing is a Good Thing, and that we should try to take advantage of
>it where possible rather than use cuts. But it's not a panacea, and
>there's no point pretending that it is.
Exactly! That's why you have to look at Prolog as just another programming
language (though, in my opinion, a very nice programming language indeed),
and forget the godlike aura of logic in which the true spirit of Prolog
often is hidden from the naive observer. I'm sure this opinion is shocking
for many theorists, because in their opinion the only advantage of Prolog is
it's logic foundation. Fortunately they are wrong! Prolog is a splendid
language all by itself, and by throwing some of the theoretical ballast
overboard (or into classes where it is more appropriate), we might be
able to get the teaching of Prolog *programmers* up to speed, and maybe
we can see some of the misconceptions that hinder the widespread usage of
Prolog in the industry, erased in the future.
Regards,
Jonas
PS. To return to cuts for a brief moment: I just want to make clear
that I'm not opposed to cuts in general. But I don't think that putting
cuts in a program by "default" (to be safe), and promoting it as a
programming technique, is acceptable. Nor would I think a programming
technique for C advising the declaration of the variable 'i' at the
beginning of each function, "because you might use it later on", would
be acceptable.
----------------------------------------------------------------------
Michael Covington
>Personally, I prefer to look at Prolog as a programming language.
>Nothing more. Nothing less. Those who believe a Prolog program is a
>runable specification, and those who believe a Prolog program is
>closely related to logic, do not belong to the same cult as me.
That's close to my view. I would view Prolog as a programming language
that is *inspired* by first-order logic (as opposed to others that are
inspired by mathematical notations, or English sentences, or whatever).
Thus, Prolog is a language where some programs tend to be relatively
close to logical specifications. (Just as some Fortran programs are
relatively close to sets of mathematical equations.)
>[...[ if our schools
>want to produce competent *Prolog* programmers, they must teach Prolog
>from a program-flow point of view, rather than as an "extension" to
>logic.
That was the idea behind _Prolog Programming in Depth_ (which I
co-authored with Donald Nute and Andre Vellino). We found out that
the _first_ thing you must teach about Prolog is the flow of control.
Naturally, the flow of control is motivated by Prolog's close
relationship to logic; but Prolog is not so close to logic that you
can ignore the flow of control.
>David H.D. Warren made Prolog practical by devising an
>efficient implementation strategy - it's a shame when universities
>make Prolog *impractical* by not teaching how to utilize the benefits of
>this implementation strategy.
Amen. Another thing I have to say very early in a Prolog course is that
Prolog is not logic; it is a _reasonable compromise_ between pure logic
and practical execution.
Kjell Post
>I don't know about you (or about the people who wrote WorkPro), but not
>infrequently I find myself writing code that has the general structure
>
> p(M, N, ...) :- M =< N, ...
> p(M, N, ...) :- M > N, ...
>
>The last time I looked, most Prolog systems out there wouldn't recognize
>that these clauses are mutually exclusive, and would create a choice
>point, so I'd *have* *to* put in cuts to get decent performance.
I've noticed this myself, for instance implementing merge sort.
Are there _any_ Prolog systems that will discover the mutual exclusion?
Aquarius perhaps? It seems simple enough: both M and N have to be ground,
'=<' and '>' both appear as the first subgoal and together they are
mutually exclusive to each other.
--Kjell
Shinji Kono
>that these clauses are mutually exclusive
Detection of exclusivness is not easy, even for human. If there is a
cut in the predicates, it is easy to find it. It helps readability.
This type of cut is not embarrassing.
1) If a predicate is deterministic relative to its inputs, it is better to
put cuts explicitly.
2) Writing exculive conditions is more difficult than puting cuts.
3) Most of predicates in practical program are deterministic and directed.
So I think there are good reasons to put cut explicitly. If you can
still extract logical semantics, logic programming still works. It is
not complete though.
In article <1993Apr12....@proactive.com>,
jo...@proactive.com (Jonas Almgren) writes:
> Personally, I prefer to look at Prolog as a programming language.
> Nothing more. Nothing less. Those who believe a Prolog program is a
> runable specification, and those who believe a Prolog program is
> closely related to logic, do not belong to the same cult as me.
I agree with it. In "Programming in Prolog" they recomend usage of
not/1 rather than cuts. But it is also recomended to avoid \+/1,
because it requires careful thoughts. I can't belive these comments
help students. It is better to teach them correct usage of cuts instead.
When the students studied enough about how Prolog works, they can write
pure logical, reversible and practical Prolog programs.
liang han
>Now, when we soon will have a Prolog standard, it should be clear that
>Prolog is a language with so many fundamental features relying on
>execution model rather than declarative model, that if our schools
>want to produce competent *Prolog* programmers, they must teach Prolog
>from a program-flow point of view, rather than as an "extension" to
>logic. The confusion of and discrepancy between Prolog, the language,
>and Prolog, the theory, has in my opinion caused: (1) The confusion
>many students feel when faced with writing a Prolog program (2) The
>bad programming practices with which many (most?) Prolog programs are
>written. The former has resulted in students leaving universities
>thinking that Prolog is really weird, the latter has resulted in the
>common perception that Prolog is extremely inefficient. (1) and (2)
>taken together explains why the true benefits of Prolog so often are
>forgotten. David H.D. Warren made Prolog practical by devising an
>efficient implementation strategy - it's a shame when universities
>make Prolog *impractical* by not teaching how to utilize the benefits of
>this implementation strategy.
I have not read this newgroup for a while; so my comment may be off
the topic. If the declarative approach does not work well, maybe it
is due to the chosen query processing strategy and implementation.
To me, I do not see why a logic evaluator cannot be both declarative
and efficient, as efficient as any programming language.
>Exactly! That's why you have to look at Prolog as just another programming
>language (though, in my opinion, a very nice programming language indeed),
>and forget the godlike aura of logic in which the true spirit of Prolog
>often is hidden from the naive observer. I'm sure this opinion is shocking
>for many theorists, because in their opinion the only advantage of Prolog is
>it's logic foundation. Fortunately they are wrong! Prolog is a splendid
>language all by itself, and by throwing some of the theoretical ballast
>overboard (or into classes where it is more appropriate), we might be
>able to get the teaching of Prolog *programmers* up to speed, and maybe
>we can see some of the misconceptions that hinder the widespread usage of
>Prolog in the industry, erased in the future.
This is an interesting point. Prolog formalism by itself offers some
advantages even without declarative programming. I agree with this.
>PS. To return to cuts for a brief moment: I just want to make clear
>that I'm not opposed to cuts in general. But I don't think that putting
>cuts in a program by "default" (to be safe), and promoting it as a
>programming technique, is acceptable. Nor would I think a programming
>technique for C advising the declaration of the variable 'i' at the
>beginning of each function, "because you might use it later on", would
>be acceptable.
Since cuts may cause so many problems, why not eliminate them altogether
and optimize query evaluation by other means?
JL Han
Paul Singleton
>...
> infrequently I find myself writing code that has the general structure
>
> p(M, N, ...) :- M =< N, ...
> p(M, N, ...) :- M > N, ...
>
> The last time I looked, most Prolog systems out there wouldn't recognize
> that these clauses are mutually exclusive, and would create a choice
I regard Prolog as an assembly language for relational/logic/deductive
programming and meta-programming, and we should be looking for well-
-defined abstractions which can be compiled into raw portable/universal
Prolog. Surely static determinacy checkers can spot the exclusivity of
the clauses above, and either insert a green cut or employ if-then-else
(but not both :-)? I like designing algorithms for Prolog's execution
model but tire of the detailed generation of concrete code e.g. to make
best use of first argument indexing. I find myself performing the same
old source transformations and expansions over and over again. I can
envisage a structure editor which allows me to re-order arguments of
some procedure throughout a program with a couple of key or mouse strokes
(NB mouse stroking relieves stress :-) but I haven't written it yet. But
better still I want a preprocessor to do these performance-oriented
restructurings automatically.
----
__ __ Paul Singleton (Mr) JANET: pa...@uk.ac.keele.cs
|__) (__ Computer Science Dept. other: pa...@cs.keele.ac.uk
| . __). Keele University, Newcastle, tel: +44 (0)782 583477 << NEW for
Staffs ST5 5BG, ENGLAND fax: +44 (0)782 713082 1993
Saumya K. Debray
clauses of the form
p(M, N, ...) :- M =< N, ...
p(M, N, ...) :- M > N, ...
cs...@seq1.keele.ac.uk (Paul Singleton) writes:
> Surely static determinacy checkers can spot the exclusivity of
> the clauses above, and either insert a green cut or employ if-then-else?
kj...@cse.ucsc.edu (Kjell Post) writes:
> It seems simple enough: both M and N have to be ground,
> '=<' and '>' both appear as the first subgoal and together they are
> mutually exclusive to each other.
Actually, the general problem turns out to be undecidable, even if we
restrict ourselves to the case where each clause has just one relational
test. This follows from the fact that given any polynomial P(x), we can
construct a pair of clauses
p(X, Z) :- integer(X), Eval_P(X) =:= Z.
p(X, Z) :- integer(X), Z =\= 0.
where Eval_P(X) denotes an expression to evaluate the polynomial P
at X, e.g., if P(x) = x^3 + 2x^2 then Eval_P(X) = X*X*X + 2*X*X.
Now these two clauses are mutually exclusive if and only if, in
the first clause, we have
Z =:= 0 ( =:= Eval_P(X) )
i.e., there is some integer value of x for which the polynomial P(x)
evaluates to 0. But the problem of determining whether an arbitrary
polynomial has integer roots is undecidable (Matijasevic, 1970). It
follows that deciding whether two arbitrary clauses are mutually
exclusive is also undecidable.
Incidentally, notice that this argument is easily adapted to show that it's
undecidable to determine whether a cut is "green" even if we restrict
ourselves to cuts after "flat guards", i.e., cuts after a sequence of
primitive tests.
Saumya K. Debray
>Actually, the general problem turns out to be undecidable, even if we
>restrict ourselves to the case where each clause has just one relational
>test. This follows from the fact that given any polynomial P(x), we can
>construct a pair of clauses
>
> p(X, Z) :- integer(X), Eval_P(X) =:= Z.
> p(X, Z) :- integer(X), Z =\= 0.
>
>where Eval_P(X) denotes an expression to evaluate the polynomial P
>at X, e.g., if P(x) = x^3 + 2x^2 then Eval_P(X) = X*X*X + 2*X*X.
>Now these two clauses are mutually exclusive if and only if, in
>the first clause, we have
>
> Z =:= 0 ( =:= Eval_P(X) )
>
>i.e., there is some integer value of x for which the polynomial P(x)
>evaluates to 0. But the problem of determining whether an arbitrary
>polynomial has integer roots is undecidable (Matijasevic, 1970). It
>follows that deciding whether two arbitrary clauses are mutually
>exclusive is also undecidable.
There's an obvious bug in this argument, stemming from confusion
over the quantification. What I really should have said is that
given a polynomial P(x), we can construct the clauses
p(X,Z) :- integer(X), Eval_P(X) =:= Z.
p(X,Z) :- integer(X), Z =:= 0.
These clauses are _not_ mutually exclusive if and only if there is
some value of x for which P(x) is 0. Undecidability now follows
from Matijasevic's result.
(That'll teach me to post before drinking my coffee in the morning :-)
Thom Fruehwirth
In <1qe58n$q...@gabriel.keele.ac.uk>, cs...@seq1.keele.ac.uk (Paul Singleton)
writes:
"I regard Prolog as an assembly language for relational/logic/deductive
programming and meta-programming"
I regard Prolog as the Basic of logic programming.
thom
Paul Singleton
> In <1qe58n$q...@gabriel.keele.ac.uk>, cs...@seq1.keele.ac.uk (Paul Singleton) :
> "I regard Prolog as an assembly language for relational/logic/deductive
> programming and meta-programming"
> I regard Prolog as the Basic of logic programming.
Do you mean "BASIC"?
I believe that Unix 'C' compilers produce assembly source, and that the first
C++ compilers produced 'C' and so on. It is in this sense that I regard Prolog
as an assembly language. Grammar rules and functional notations compile into
Prolog, for example. Does anyone use BASIC as a target language for some
higher-level language?
NB does anyone please have a PD Prolog-to-BASIC compiler for my VIC 20?
Paul S.
Paul Singleton
> In an earlier article I wrote:
>>Actually, the general problem turns out to be undecidable, even if we
....
Please could you spell out the importance of your undecidability result?
Does this mean that I am unable to place a cut correctly in a Prolog program?
Paul S.
Saumya K. Debray
it's undecidable whether two arbitrary clauses are mutually exclusive]:
>Please could you spell out the importance of your undecidability result?
>Does this mean that I am unable to place a cut correctly in a Prolog program?
Oh, you can place cuts all you want. It simply means that you may not
always be able to argue convincingly that they've been placed "correctly."
Lee Naish
>I don't know about you (or about the people who wrote WorkPro), but not
>infrequently I find myself writing code that has the general structure
>
> p(M, N, ...) :- M =< N, ...
> p(M, N, ...) :- M > N, ...
>
>The last time I looked, most Prolog systems out there wouldn't recognize
>that these clauses are mutually exclusive, and would create a choice
>point, so I'd *have* *to* put in cuts to get decent performance.
If you use if-then-else then you won't leave any choice points around
and in some Prolog systems at least it will be significantly more
efficient than using cut.
>It's
>embarrassing as hell when you've just told your idealistic young students
>all about the Goodness of pure declarative programming and the Evils
>of cuts, and they go off and work very hard to write their pure Prolog
>programs only to find they can't run their code without blowing the stack
>unless they put in some cuts.
Pure declarative if-then-else constructs have been around since well
before the WAM. Why don't you use them? Why don't most other people
use them? If you code initially with such constructs then its very easy
to later convert them to -> to get maximum efficiency if/where its really
needed. This doesn't obscure the logic very much (especially if
bits of the logical version are left as comments).
If you start off with multiple clauses (as above) then it looks prettier
to begin with but its significantly more work to convert it into a
decent Prolog program. People tend to add cuts without moving output
unification after the cuts and delete the test in the second clause.
This makes the intended declarative semantics much more obscure and the
code non-steadfast and not particularly efficient.
lee
Remco Moolenaar
>From article <C5F5M...@ecrc.de>, by th...@ecrc.de (Thom Fruehwirth):
>
>> In <1qe58n$q...@gabriel.keele.ac.uk>, cs...@seq1.keele.ac.uk (Paul Singleton) :
>
>> "I regard Prolog as an assembly language for relational/logic/deductive
>> programming and meta-programming"
>
>> I regard Prolog as the Basic of logic programming.
>
>Do you mean "BASIC"?
>
>I believe that Unix 'C' compilers produce assembly source, and that the first
>C++ compilers produced 'C' and so on. It is in this sense that I regard Prolog
>as an assembly language. Grammar rules and functional notations compile into
>Prolog, for example. Does anyone use BASIC as a target language for some
>higher-level language?
>
Well, looking at this, the Warren Abstract Machine is the assembly language for
relational/logic/deductive programming.
Remco.
--
------------------------------------------------------------------------
Remco Moolenaar
K.U. Leuven, Celestijnenlaan 200A, 3001 Heverlee, Belgium
E-mail: re...@cs.kuleuven.ac.be
Boris Borcic
re...@cs.kuleuven.ac.be (Remco Moolenaar) wrote:
[...]
> >> I regard Prolog as the Basic of logic programming.
> >
> >Do you mean "BASIC"?
> >
> >I believe that Unix 'C' compilers produce assembly source, and that the first
> >C++ compilers produced 'C' and so on. It is in this sense that I regard Prolog
> >as an assembly language. Grammar rules and functional notations compile into
> >Prolog, for example. Does anyone use BASIC as a target language for some
> >higher-level language?
> >
> >Paul S.
>
> Well, looking at this, the Warren Abstract Machine is the assembly language for
> relational/logic/deductive programming.
>
> Remco.
If WAM is ASM, then Prolog is C. Consider Yacc, lex, f2c, m3 etc...
Boris
Paul Singleton
>> "I regard Prolog as an assembly language for relational/logic/deductive
>> programming and meta-programming"
> Well, looking at this, the Warren Abstract Machine is the assembly language for
> relational/logic/deductive programming.
Nah, that's microcode (well maybe millicode :-)
OK, maybe I should have said "I regard Prolog as the 'C' of relational/logic/-
-deductive programming" since I regard 'C' as a universal assembly code: it is
the lowest level programmatic interface common to nearly all commercially
significant hardware, but no-one with an education actually *wants* to program
in 'C'. Anyway, BASIC seems to have dropped out of this discussion.
PS
Shinji Kono
If you prefer if-then-else by means of logical correctness it's ok.
If some one prefer cut by means of syntactical simplicity it's also
ok.
In article <931051...@mulga.cs.mu.OZ.AU> ,
l...@munta.cs.mu.OZ.AU (Lee Naish) writes
>Pure declarative if-then-else constructs have been around since well
>before the WAM. Why don't you use them?
In my case, this is because if-then-else looks redundant. It looks like
clauses within a clause. Nested if-then-else looks ugly in Prlog. It is
also counter intutive since a->b means a and b.
>If you code initially with such constructs then its very easy
>to later convert them to -> to get maximum efficiency if/where its really
>needed.
If it is very easy why not leave them to compilers? It is not easy to
find where to use if-then-else for cut-free clauses. But putting a cut
for each clause is very easy. Finaly it is easy to understand
if-then-else after leaning cut. The reverse is difficult.
>People tend to add cuts without moving output unification after the cuts
This is a bad usage of cut. I agree with you. But this can happen in
if-then-else case also.
>and delete the test in the second clause.
If you think about effciency it is better to drop the test. If there
is a cut, it is easy to add necessary negation.
>This makes the intended declarative semantics much more obscure and the
>code non-steadfast and not particularly efficient.
Yes, bad cut is bad. Putting cuts for determnistic and directed
predicates is good way to presents programmer's intention.
Michael Covington
>I think choice of cut and if-then-else is a matter of preference.
>If you prefer if-then-else by means of logical correctness it's ok.
>If some one prefer cut by means of syntactical simplicity it's also
>ok.
Thanks for your support. I'm revising a Prolog textbook, and we apparently
are not going to rely on if-then-else because Arity Prolog still doesn't
have it (in the usual form) and we want our code to be portable.
Instead we are going to use cuts in a very disciplined way.
Fergus Henderson
>I think choice of cut and if-then-else is a matter of preference.
>If you prefer if-then-else by means of logical correctness it's ok.
>If some one prefer cut by means of syntactical simplicity it's also
>ok.
>
>In article <931051...@mulga.cs.mu.OZ.AU> ,
> l...@munta.cs.mu.OZ.AU (Lee Naish) writes
>>Pure declarative if-then-else constructs have been around since well
>>before the WAM. Why don't you use them?
>
>In my case, this is because if-then-else looks redundant. It looks like
>clauses within a clause. Nested if-then-else looks ugly in Prlog.
Well, beauty is in the eye of the beholder, but to me nested if-then-else
looks no uglier in Prolog than nested if statements in C, or nested
if expressions in Haskell. (Certainly much more beautiful than all those
ugly red cuts I keep seeing in other people's code.)
Why should we avoid nesting in Prolog? I use nesting in virtually
every other language I know, I don't see why Prolog should be so different.
>It is also counter intutive since a->b means a and b.
In every logic course I have done, "a->b" is read as "a implies b"
or "if a then b", never "a and b". Where did you get the idea that
"a->b" means "a and b"?
>>If you code initially with such constructs then its very easy
>>to later convert them to -> to get maximum efficiency if/where its really
>>needed.
>
>If it is very easy why not leave them to compilers?
Because most compilers are very dumb when it comes to data-flow analysis,
and don't perform this optimization automatically. You are right, it
should be the job of the compiler, but until compilers get smarter
programmers interested in efficiency will have to perform this optimization
themselves.
>It is not easy to find where to use if-then-else for cut-free
>clauses. But putting a cut for each clause is very easy.
I would disagree. The following are equivalent, so if you can work out
how to write either one, it should be easy to work out how to write
the other.
% example using cut
p :- a,
!,
b.
p :- c,
!,
d.
p :- e.
% example using if-then-else
p :- ( a ->
b
; c ->
d
;
e
).
But using arrow better expresses the logic of the problem: the second
example has a simple declarative reading, whereas the first doesn't.
>Finaly it is easy to understand
>if-then-else after leaning cut. The reverse is difficult.
I would say that it is easy to understand if-then-else and difficult
to understand cut, whichever order you learn them in.
It makes it easier to understand if-then-else if you have used another
language with an if-then-else construct, as have most students.
It makes it easier to understand cut if you have used a committed
choice language, but virtually no students will have learned such
a language before learning Prolog.
>>People tend to add cuts without moving output unification after the cuts
>
>This is a bad usage of cut. I agree with you. But this can happen in
>if-then-else case also.
No, as I pointed out with the "max" example, this *can't* happen when you
use if-then-else. The reason is that using if-then-else ensures that
you have a single clause, which means that output unifications *can't*
be placed in the head. (Unless of course they are the same for all cases
of the if-then-else, in which case there is no problem.)
>>and delete the test in the second clause.
>
>If you think about effciency it is better to drop the test. If there
>is a cut, it is easy to add necessary negation.
I don't quite understand what you mean here.
If you think about efficiency, then for at least some Prologs it is better
to use arrow. Using cut results in a choice point being created and then
removed by the cut. Some Prologs may be able to avoid creating the choice
point in the first place if you use arrow, resulting in more efficient code.
>>This makes the intended declarative semantics much more obscure and the
>>code non-steadfast and not particularly efficient.
>
>Yes, bad cut is bad. Putting cuts for determnistic and directed
>predicates is good way to presents programmer's intention.
Well, I maintain that using arrow is a better way.
I guess we'll just have to agree to disagree.
Paul Singleton
>>If it is very easy why not leave them to compilers?
> Because most compilers are very dumb when it comes to data-flow analysis,
> and don't perform this optimization automatically. You are right, it
> should be the job of the compiler, but until compilers get smarter
> programmers interested in efficiency will have to perform this optimization
> themselves.
I thought Turbo Prolog was based on some pretty smart data flow analysis ...
I, too, want compilers to get smarter, but this may mean that we end up
writing in a language other than Prolog (which is fine by me).
Paul S.
Lars-Henrik Eriksson
ko...@csl.sony.co.jp (Shinji Kono) writes:
>It is also counter intutive since a->b means a and b.
In every logic course I have done, "a->b" is read as "a implies b"
or "if a then b", never "a and b". Where did you get the idea that
"a->b" means "a and b"?
He got the idea from Prolog, because in *Prolog* a->b means "a and b".
THAT is what is counter-intuitive!
Witness:
SICStus 2.1 #8: Thu Apr 15 10:00:31 MET DST 1993
| ?- false->false.
no
| ?- false->true.
no
| ?- true->false.
no
| ?- true->true.
yes
--
Lars-Henrik Eriksson Internet: l...@sics.se
Swedish Institute of Computer Science Phone (intn'l): +46 8 752 15 09
Box 1263 Telefon (nat'l): 08 - 752 15 09
S-164 28 KISTA, SWEDEN Fax: +46 8 751 72 30
Fergus James HENDERSON
>From article <931090...@mulga.cs.mu.OZ.AU>, by f...@cs.mu.OZ.AU (Fergus Henderson):
>
>I thought Turbo Prolog was based on some pretty smart data flow analysis ...
It was, but unfortunately that came at a high cost. Turbo Prolog had a
straitjacket type system less flexible than that of Pascal, didn't allow
overloaded operators, and didn't support meta-programming.
Worst of all <grin> it didn't have an if-then-else construct ;-)
and since it didn't allow higher-order predicates and call/1, you
couldn't write your own. You were *forced* to scatter cuts throughout your
code.
>I, too, want compilers to get smarter, but this may mean that we end up
>writing in a language other than Prolog (which is fine by me).
Successful languages evolve as time goes by. Look at COBOL, Fortran, and C.
Compare the original Fortran and Fortran 90. Are they the same language?
--
Fergus Henderson f...@munta.cs.mu.OZ.AU
This .signature virus is a self-referential statement that is true - but
you will only be able to consistently believe it if you copy it to your own
.signature file!
PONTELLI
>In article <931090...@mulga.cs.mu.OZ.AU> f...@cs.mu.OZ.AU (Fergus Henderson) writes:
>
>He got the idea from Prolog, because in *Prolog* a->b means "a and b".
>THAT is what is counter-intuitive!
>
I guess there should be also a '!' in the middle since
a(1).
a(2).
b(2).
| ?- a(X)->b(X).
no.
so a->b looks more like a,!,b, or am I wrong ?
Enrico
Lunjin Lu
|> I, too, want compilers to get smarter, but this may mean that we end up
|> writing in a language other than Prolog (which is fine by me).
|>
|> Paul S.
The language is still PROgramming in LOGic. In fact it is a
better implementaion that gives more support for
declarative programming.
Michael Covington
>
> ko...@csl.sony.co.jp (Shinji Kono) writes:
> >It is also counter intutive since a->b means a and b.
>
> In every logic course I have done, "a->b" is read as "a implies b"
> or "if a then b", never "a and b". Where did you get the idea that
> "a->b" means "a and b"?
>
>He got the idea from Prolog, because in *Prolog* a->b means "a and b".
>THAT is what is counter-intuitive!
>Witness:
>SICStus 2.1 #8: Thu Apr 15 10:00:31 MET DST 1993
>| ?- false->false.
>no
>| ?- false->true.
>no
>| ?- true->false.
>no
>| ?- true->true.
>yes
Thanks for clarifying what had been bothering me all along about the
if-then arrow.
Peter Van Roy
> >
> > p(M, N, ...) :- M =< N, ...
> > p(M, N, ...) :- M > N, ...
> >
> Aquarius perhaps? It seems simple enough: both M and N have to be ground,
> '=<' and '>' both appear as the first subgoal and together they are
> mutually exclusive to each other.
>
> --Kjell
Yes, Aquarius will discover the mutual exclusion. It will even compile
the following predicate:
max(A, B, C) :- A=<B, C=B.
max(A, B, C) :- A>=B, C=A.
so that it only creates a choice point when A and B are equal. But it only
does part of what could be done: It only avoids choice point creations for
certain classes of tests (unifications, arithmetic comparisons, and type
checks). It will *not* avoid the choice point creation when the test is a
user-defined goal.
There is still a lot to be done in Prolog compilation!
Peter
Lunjin Lu
You are right. If you change the order of two clauses for a/1.
then
| ?- a(X)->b(X).
X=2 ;
no
Shinji Kono
enpo...@dante.nmsu.edu (PONTELLI) writes:
>so a->b looks more like a,!,b, or am I wrong ?
You are right... Ah.. but it's a definition of a->b. Look. In
Sicstus Prolog's manual:
`+P -> +Q ; +R' Analogous to if P then Q else R i.e. defined as if by
(P -> Q; R) :- P, !, Q.
(P -> Q; R) :- R.
So the problem is this. Should we use '->' instead of restricted cut?
My answer is restricted cut because of ugly syntax of '->'.
In article <931090...@mulga.cs.mu.OZ.AU> ,
f...@cs.mu.OZ.AU (Fergus Henderson) writes
>No, as I pointed out with the "max" example, this *can't* happen when you
>use if-then-else.
Good point. I agree that if-then-else is better in single clause max/3.
>I would say that it is easy to understand if-then-else and difficult
>to understand cut, whichever order you learn them in.
Can you tell me how to teach if-then-else without mentioning choice point?
From Sicstus manual again:
Note also that the `;' is not read as a disjunction operator in this case;
instead, it is part of the if-then-else construction.
The precedence of `->' is less than that of `;' (*Note Operators::),
so the expression is read as ;(->(P,Q),R)
It has too many ``note''. From syntactical point of view, ``->'' has
some problems.
>I guess we'll just have to agree to disagree.
I think you have to invent a better syntax for if-then-else which answers
yes for false->false. Then I'll use it. But please don't force NU-Prolog
for me. I tried it already. I like NU-Prolog's idea but I prefer Sicstus
Prolog's implementation.
Tim Arnold
>In article <931090...@mulga.cs.mu.OZ.AU> f...@cs.mu.OZ.AU (Fergus Henderson) writes:
> ko...@csl.sony.co.jp (Shinji Kono) writes:
> >It is also counter intutive since a->b means a and b.
> In every logic course I have done, "a->b" is read as "a implies b"
> or "if a then b", never "a and b". Where did you get the idea that
> "a->b" means "a and b"?
>He got the idea from Prolog, because in *Prolog* a->b means "a and b".
>THAT is what is counter-intuitive!
>Witness:
>SICStus 2.1 #8: Thu Apr 15 10:00:31 MET DST 1993
>| ?- false->false.
>no
>| ?- false->true.
>no
>| ?- true->false.
>no
>| ?- true->true.
>yes
Yes but witness:
NU-Prolog 1.5.33
1?- fail -> fail.
true.
2?- fail -> true.
true.
3?- true -> fail.
fail.
4?- true -> true.
true.
NU-Prolog gets it right! The SICStus implementation of Prolog is
counter-intuitive (in this respect - I'm sure it is a good system in
other respects or nobody would use it) but not generic Prolog.
"a -> b" is not and should not be the same as "a and b".
What does the standard say about SICStus creativity?
--
Tim Arnold | CITRI, RMIT | Uni. of Melbourne Law School
t...@kbs.citri.edu.au | 723 Swanston St | ----------------------------
Phone: +61 3 282 2487 | Carlton 3053 | simul iustus
Fax: +61 3 282 2490 | Victoria, Australia | et peccator
Lars-Henrik Eriksson
[Demonstrations of Prolog behaviour omitted]
NU-Prolog gets it right! The SICStus implementation of Prolog is
counter-intuitive (in this respect - I'm sure it is a good system in
other respects or nobody would use it) but not generic Prolog.
"a -> b" is not and should not be the same as "a and b".
What does the standard say about SICStus creativity?
You should rather ask what the standard says about NU-Prolog
creativity. "Generic" Prolog behaves like Sicstus. NU-Prolog does many
things in a much better way than generic Prolog - this is one of them.
Unfortunately, that means that NU-Prolog is the odd system - not
Sicstus.
I can repeat the example with Quintus Prolog:
Quintus Prolog Release 3.1.1 (Sun-4, SunOS 4.1)
Copyright (C) 1990, Quintus Corporation. All rights reserved.
2100 Geng Road, Palo Alto, California U.S.A. (415) 813-3800
| ?- false->false.
no
| ?- false->true.
no
| ?- true->false.
no
| ?- true->true.
yes
Thomas Sj|land
>NU-Prolog gets it right! The SICStus implementation of Prolog is
>counter-intuitive (in this respect - I'm sure it is a good system in
>other respects or nobody would use it) but not generic Prolog.
My impression is that the behaviour and syntax of (A->B;C)
was carefully chosen by Mats Carlsson in order to be as
much "standard Prolog" as possible, rather than to try to be "logical".
When it comes to syntax it would probably have been a good idea to ban
the ';' operator from the if-then-else construction in the standard since
it is overloaded. I am not sure whether that is the case in the document.
>"a -> b" is not and should not be the same as "a and b".
>What does the standard say about SICStus creativity?
This is obscure. 'and' is not an operator, you probably
mean "a,b". What is meant by the question?
SICStus Prolog has also the metapredicate if/3 used
for more "logical needs" like theorem provers.
--
(Alf) Thomas Sjoeland
SICS, PO Box 1263, S-164 28 KISTA, SWEDEN
Tel: +46 8 752 15 42 Fax: +46 8 751 72 30 Tel home: +46 8 80 44 08
Internet: a...@sics.se
......
Fergus James HENDERSON
>l...@sics.se (Lars-Henrik Eriksson) writes:
>>f...@cs.mu.OZ.AU (Fergus Henderson) writes:
>>
>> Where did you get the idea that "a->b" means "a and b"?
>>
>>He got the idea from Prolog, because in *Prolog* a->b means "a and b".
>>THAT is what is counter-intuitive!
>
>Thanks for clarifying what had been bothering me all along about the
>if-then arrow.
So are you suggesting that the only thing wrong with arrow is the
counter-intuitive behaviour when the 'else' case is omitted?
Simple solution: always make the else case explicit.
Fergus James HENDERSON
>So the problem is this. Should we use '->' instead of restricted cut?
>My answer is restricted cut because of ugly syntax of '->'.
>
>In article <931090...@mulga.cs.mu.OZ.AU> ,
> f...@cs.mu.OZ.AU (Fergus Henderson) writes
>>No, as I pointed out with the "max" example, this *can't* happen when you
>>use if-then-else.
>
>Good point. I agree that if-then-else is better in single clause max/3.
>
>>I would say that it is easy to understand if-then-else and difficult
>>to understand cut, whichever order you learn them in.
>
>Can you tell me how to teach if-then-else without mentioning choice point?
Sure. Just say that
(A -> B ; C)
is exactly the same as
( once(A), B ; \+ A, C )
except more efficient (because it only needs to evaluate A once).
once(A) returns the first solution to A only. (You should generally only
use (A->B;C) where A is deterministic, ie. has at most one solution,
in which case once(A) is equivalent to A).
\+ A succeeds if A fails. [A little bit more explanation regarding
negation-as-failure required here.]
Or alternately, just say that (A -> B ; C) evaluates A, and
if it succeeds, is equivalent to B, otherwse (if A fails) it's
equivalent to C. Note that only the first solution to A is considered.
>>I guess we'll just have to agree to disagree.
>
>I think you have to invent a better syntax for if-then-else which answers
>yes for false->false. Then I'll use it. But please don't force NU-Prolog
>for me. I tried it already. I like NU-Prolog's idea but I prefer Sicstus
>Prolog's implementation.
Well, at least we agree on the ideas ;-)
Jacques Garrigue
Well, as I understand, this is not "a->b" which is defined is in
SICStus, or other prologs (except NU), but "a->b;c" as something that
is intuitively "if a then b else c". In these conditions, "a->b" is
understood as "a->b;false".
If you want the logical implication, you can just use "a->b;true", it
works OK:
| ?- fail -> fail; true.
yes
| ?- true -> fail; true.
no
Now, maybe it would be better (more intuitive) to interpret "a->b" as
"a->b;true", and use explicitely a cut if you want the other way.
Jacques
--
---------------------------------------------------------------------------
Jacques Garrigue University of Tokyo garr...@is.s.u-tokyo.ac.jp
Inf. Sc. Ecole Normale Superieure,Paris garr...@dmi.ens.fr
Shinji Kono
garr...@is.s.u-tokyo.ac.jp (Jacques Garrigue) writes
>"a->b;true", and use explicitely a cut if you want the other way.
Corrrect.
insertlast(E,L,O) :- L = [], !, O = [E].
insertlast(E,L,O) :- L = [H|T],!, O = [H|,O1],insertlast(E,T,O1).
insertlast(E,L,O) :- L = [] -> O = [E].
insertlast(E,L,O) :- L = [H|T] -> O = [H|,O1],insertlast(E,T,O1).
/* Is this correct in NU-Prolog? */
insertlast(E,L,O) :-
L = [] -> O = [E];
L = [H|T] -> O = [H|,O1],insertlast(E,T,O1).
Above all three are equivalent. In some sense we all agree with this
kind of programming in Prolog, that is, how to do functional programming
in Prolog.
Jonas Almgren
and is quite uninteresting, but... returning to my old argument that
Prolog is a programming language (defined by the ISO standard) rather
than logic, I would like to point out that no language I know of
implements if-then-else as logical implication. If-then-else is
another construct, and the syntactical use of a right arrow in Prolog
might be confusing, but still doesn't in any way imply that
if-then-else has to be implemented as logical implication. In fact, in
doing so the loss to the Prolog language would be greater than the
gain, because to most people, an if-then-else construct sometimes
succeeding when the if-part is false, would be REALLY confusing. Of
course, "most people" don't even read this news group, so maybe trying
to satisfy them is a stupid objective. Why try to make Prolog
practical anyway? Let's just admit it, in the future, Prolog will
still be nothing but a toy for the purists, and all practical programming
will be made in C++... Quintus will be writing GUI builders for
Windows, and BIM will be writing device drivers...
/Jonas
Note: NU-Prolog doesn't implement if-then-else, but implication. The
two constructs just happen to have the same syntax in Prolog and
NU-Prolog. You might argue that the NU-Prolog implementation is
more logically clean, but this doesn't necessarily mean that it
is better, or more useful.
Fergus James HENDERSON
>insertlast(E,L,O) :- L = [], !, O = [E].
>insertlast(E,L,O) :- L = [H|T],!, O = [H|,O1],insertlast(E,T,O1).
>
>insertlast(E,L,O) :- L = [] -> O = [E].
>insertlast(E,L,O) :- L = [H|T] -> O = [H|,O1],insertlast(E,T,O1).
> /* Is this correct in NU-Prolog? */
No. If you're using NU-Prolog, you would need to add " ; fail":
insertlast(E,L,O) :- L = [] -> O = [E] ; fail.
insertlast(E,L,O) :- L = [H|T] -> O = [H|,O1],insertlast(E,T,O1) ; fail.
>insertlast(E,L,O) :-
> L = [] -> O = [E];
> L = [H|T] -> O = [H|,O1],insertlast(E,T,O1).
>
>Above all three are equivalent. In some sense we all agree with this
>kind of programming in Prolog, that is, how to do functional programming
>in Prolog.
I must say that the second method seems the odd one out to me, since
it's the only one that leaves unnecessary choice points around.
But in NU-Prolog you could just do
?- insertlast(E,L,O) when L. % ensures proper indexing
insertlast(E,[],[E]).
insertlast(E,[H|T0],[H|T]) :- insertlast(E,H,T).
and with other compilers you could do
insertlast(E,L,O) :- insertlast2(L,E,O).
% swap order of arguments to get first-argument indexing
insertlast2([],E,[E]).
insertlast2([H|T0],E,[H|T]) :- insertlast2(T0,E,T).
You don't need to use either cut or arrow.
Micha Meier
>In article <1993Apr11.1...@cs.uoregon.edu> deb...@majestix.cs.uoregon.edu (Saumya K. Debray) writes:
>>I don't know about you (or about the people who wrote WorkPro), but not
>>infrequently I find myself writing code that has the general structure
>>
>> p(M, N, ...) :- M > N, ...
>>
>>that these clauses are mutually exclusive, and would create a choice
>>point, so I'd *have* *to* put in cuts to get decent performance.
>
>Are there _any_ Prolog systems that will discover the mutual exclusion?
>Aquarius perhaps? It seems simple enough: both M and N have to be ground,
>'=<' and '>' both appear as the first subgoal and together they are
>mutually exclusive to each other.
It should be noted that Prolog systems which can suspend goals must assume
that M or N or both can be also free. In this case a choice point
must be created and kept until it is known which one of the two tests succeeds.
--Micha
---
Micha Meier ------------------------------------------------
ECRC, Arabellastr. 17 The opinions expressed above are private
D-8000 Munich 81 and may not reflect those of my employer.
mi...@ecrc.de, Tel. +49-89-92699-108, Fax +49-89-92699-170
Lee Naish
>Prolog is a programming language (defined by the ISO standard) rather
>than logic, I would like to point out that no language I know of
>implements if-then-else as logical implication.
How many other languages do you know that have logic variables and
implement argument passing and '=' using a unification procedure?
>Note: NU-Prolog doesn't implement if-then-else, but implication. The
>two constructs just happen to have the same syntax in Prolog and
>NU-Prolog.
if-then-*else* is the same in NU-Prolog as in ISO standard Prolog.
It certainly is implemented in NU-Prolog:
p(X) :- (X > 0 -> q ; r).
is compiled into
.pred 'p',1
.clause
0: apushx 0
pushi $$0
jpred 4,&2 % conditional branch instruction
exec 0,&'q'/0
2: exec 0,&'r'/0
3: last
The other (declarative) form of if-then-else is compiled into similar
code which first checks that X is ground.
Logical implication is not an implementation technique or a procedural
notion, it is a declarative notion. If-then-else is a well known
procedural notion. One of the attractions of logic programming languages
is that they have *both* a declarative semantics and a procedural semantics.
You don't have to choose between something logical and something
procedural - you have both.
In Prolog (including NU-Prolog) you can read (a -> b ; c) as
Procedurally:
if a (is true/succeeds) then (execute) b else (execute) c
Declaratively (assuming a will be ground when called):
if a (is true) then b (is true) otherwise c (is true)
Note that from a declarative classical logic viewpoint the implementation
is incomplete since (p -> p ; true) is true but may not terminate.
The problems occur with (a -> b).
In NU-Prolog it can be read as
Procedurally:
if a (is true/succeeds) then (execute) b
Declaratively (assuming a will be ground when called):
if a (is true) then b (is true)
(or equivalently, a implies b)
Declaratively, (a -> b ; c) is equivalent to (a -> b), (not a -> c).
This is just like logic (the conjunction operator in Prolog is ',').
Procedurally, (a -> b ; c) is equivalent to (a -> b), (not a -> c),
except in the latter a is executed twice (the result will be the same if
a has no side effects). This is just like Algol, Pascal, C, C++ etc.
(and I know Jonas *does* know of C++ since he mentioned it in his
posting). The sequencing operator in Prolog is ','.
In Standard Prolog, people who have some familiarity with logic and/or
popular imperative languages seem to have a tendency to read (a -> b) as
if a then b. This is a mistake. (a -> b ; c) is not the same as
(a -> b), (not a -> c).
> You might argue that the NU-Prolog implementation is
>more logically clean, but this doesn't necessarily mean that it
>is better, or more useful.
The NU-Prolog version of (a -> b) is no more or less logical than the
standard version - its just different. As for how useful it is, ever
since I discovered the incompatibility (some years ago now) I have never
used (a -> b). I always use (a -> b ; c) for portability reasons.
There have been very many occasions where I have used true for c. I
have *never* used fail. ie, I (and others) find the NU-Prolog semantics
is much more useful.
The design of the conditional construct in Prolog was not based on logic
(logic doesn't have an if-then-else construct) or on Algol. It was
based on COND in LISP. Quite a rational (though not logical :-)
choice. If the NU-Prolog form had been implemented instead and the
construct had been compiled in Dec10 Prolog then I think that typical
Prolog code today would be more logical.
lee
Lee Naish
>insertlast(E,L,O) :- L = [], !, O = [E].
>insertlast(E,L,O) :- L = [H|T],!, O = [H|,O1],insertlast(E,T,O1).
>
>insertlast(E,L,O) :- L = [] -> O = [E].
>insertlast(E,L,O) :- L = [H|T] -> O = [H|,O1],insertlast(E,T,O1).
> /* Is this correct in NU-Prolog? */
>insertlast(E,L,O) :-
> L = [] -> O = [E];
> L = [H|T] -> O = [H|,O1],insertlast(E,T,O1).
>
>Above all three are equivalent.
In what sense? All three have syntax errors, so at least the NU-Prolog
compiler produces equivalent output - an error message :-). The syntax
is different. Who knows what the declarative semantics is. The second
version behaves differently when called with a variable in the second
argument (and there is nothing in the code to indicate there is anything
wrong with this). Even if L is a nonvariable the second version can
have noticibly different behavior due to the choice point being left
around (see Fergus' posting).
>In some sense we all agree with this
>kind of programming in Prolog, that is, how to do functional programming
>in Prolog.
In some sense some of us disagree (if I understand your posting
correctly).
I think a nicer way of doing functional programming in Prolog is as
follows:
% appends single element onto list
insertlast(E, []) = [E].
insertlast(E, H.T) = H.insertlast(E, T).
I won't describe (yet again) how this is flattened into Horn clauses etc.
However, I will mention that when I typed this in the first time I typed
L instead of [] in the first equation. The result was an error message
(at transformation/compilation time) that the two equations were not
mutually exclusive. If I had made the same error in a pure Horn clause
version I could have found the error later using the declarative
debugger in NUDE (invoked from the automatic testing facility).
If I used cut everywhere then I could not have used compile time error
detection or the nice testing and debugging facilites of NUDE since
these are based on declarative semantics of programs.
One final point on efficiency. The equational version and the optimized
Prolog version took 0.10s on a 10000 element list. The naive Prolog
version took 0.15s (plus left choice points behind). Kono's versions
took 0.17s, 0.29s (+ left choice points) and 0.23s.
lee
Tim Arnold
>>NU-Prolog gets it right! The SICStus implementation of Prolog is
>>counter-intuitive (in this respect - I'm sure it is a good system in
>>other respects or nobody would use it) but not generic Prolog.
>My impression is that the behaviour and syntax of (A->B;C)
>was carefully chosen by Mats Carlsson in order to be as
>much "standard Prolog" as possible, rather than to try to be "logical".
Okay. I just assumed that standard Prolog was a bit more logical than that. It was
taught to me as normal at Melbourne and it makes sense. The only argument in favour of
the other semantics is it is easier to implement and people have gotten used to it.
>When it comes to syntax it would probably have been a good idea to ban
>the ';' operator from the if-then-else construction in the standard since
>it is overloaded. I am not sure whether that is the case in the document.
Well it isn't an if-then-else construct at all really with either the "a, !, b"
semantics or without " ; "! But it still might be necessary to provide for backward
compatibility :-(
>>"a -> b" is not and should not be the same as "a and b".
>>What does the standard say about SICStus creativity?
>This is obscure. 'and' is not an operator, you probably
>mean "a,b". What is meant by the question?
I just used the language in the original post. I thought it would be obvious.
Ah well ;-(
>SICStus Prolog has also the metapredicate if/3 used
>for more "logical needs" like theorem provers.
So does NU-Prolog of course ;-)
I have since been corrected that SICSTUS follows the more normal procedural semantics
for "a -> b" and NU-Prolog is unusual. Apologies to those annoyed by my response.
But surely the "->" symbol is supposed to look like the logical implication arrow and
should receive an interpretation consistent with PROgramming in LOGic??
My question should be restated (a little less agressively) as:
What does the standard say about NU-Prolog sensibility?
Micha Meier
>In article <1993Apr22.0...@nntp.csl.sony.co.jp> ko...@csl.sony.co.jp writes:
>>insertlast(E,L,O) :- L = [], !, O = [E].
>>insertlast(E,L,O) :- L = [H|T],!, O = [H|,O1],insertlast(E,T,O1).
>>
>>insertlast(E,L,O) :- L = [] -> O = [E].
>>insertlast(E,L,O) :- L = [H|T] -> O = [H|,O1],insertlast(E,T,O1).
>> /* Is this correct in NU-Prolog? */
>>insertlast(E,L,O) :-
>> L = [] -> O = [E];
>> L = [H|T] -> O = [H|,O1],insertlast(E,T,O1).
>>
>Prolog version took 0.10s on a 10000 element list. The naive Prolog
>version took 0.15s (plus left choice points behind). Kono's versions
>took 0.17s, 0.29s (+ left choice points) and 0.23s.
>
> lee
The efficiency and choice points left behind depend on the particular Prolog
compiler. In ECLiPSe, the first version is equivalent to the optimized Prolog
version and none of the versions leaves a choice point behind no matter
if there is a cut or not.
Jonas Almgren
>In article <1993Apr22.1...@proactive.com> jo...@proactive.com (Jonas Almgren) writes:
>>Prolog is a programming language (defined by the ISO standard) rather
>>than logic, I would like to point out that no language I know of
>>implements if-then-else as logical implication.
>
>How many other languages do you know that have logic variables and
>implement argument passing and '=' using a unification procedure?
Not many! And this is what makes Prolog a "splendid programming
language"! Though we have to remember that it is how these concepts
simplifies programming tasks that really matter. They may be inherited
from logic, but when using them in most real life situations, that's
not what you care about.
All good Prolog programmers I know (and Lee is among them) are very
much aware of choice-points, indexing, data structures, heap and stack
space (usage and pruning), garbage (collection) and backtracking.
Frankly, I don't think you can be a good Prolog programmer if you
don't grasp these concepts. So let's not fool ourselves, and our
students, that Prolog is logic. It isn't.
>if-then-*else* is the same in NU-Prolog as in ISO standard Prolog.
>The NU-Prolog version of (a -> b) is no more or less logical than the
>standard version - its just different. As for how useful it is, ever
>since I discovered the incompatibility (some years ago now) I have never
>used (a -> b). I always use (a -> b ; c) for portability reasons.
>There have been very many occasions where I have used true for c. I
>have *never* used fail. ie, I (and others) find the NU-Prolog semantics
>is much more useful.
Thanks Lee for clarifying this. My argument was not meant to be for or
against (a->b) being (a->b;true) or (a->b;false), though we have to
accept the standard's choice of the latter. What I can not agree with
is an interpretation in which (a->b) succeeds if both a and b are false
(because it would mean that b has to be executed regardless of a.)
I'm sorry this wasn't clear.
/Jonas
By the way, I don't know why Lee thought I know C++, I most definitely don't.
But I can open any newspaper and see 20 or more companies looking for C++
programmers, and none looking for Prolog programmers... It's called reality.
--------------------------------------------------------------------------------
My opinions are personal, and my employer has probably no clue what I'm speaking
about.
--------------------------------------------------------------------------------
Fergus James HENDERSON
>[someone else wrote:]
>>> p(M, N, ...) :- M =< N, ...
>>> p(M, N, ...) :- M > N, ...
>>Aquarius perhaps? It seems simple enough: both M and N have to be ground,
>>'=<' and '>' both appear as the first subgoal and together they are
>>mutually exclusive to each other.
>
>It should be noted that Prolog systems which can suspend goals must assume
>that M or N or both can be also free. In this case a choice point
>must be created and kept until it is known which one of the two tests succeeds.
Yes, asssuming that '=<' and '>' are suspending comparisons.
But in NU-Prolog at least, and in Goedel (not that Goedel is Prolog),
you can specify that p itself should suspend until M and N are ground.
I imagine that something similar is possible in other coroutining Prologs.
Once you have specified this, then the compiler could go ahead and
discover the mutual exclusion. (Regretably, however, NU-Prolog isn't
smart enough to do so.)
Lee Naish
>... choice-points, indexing, ...
>Frankly, I don't think you can be a good Prolog programmer if you
>don't grasp these concepts.
Unfortunately I have to agree, and I think that its an important
criticism of Prolog. Its the price we pay for a high level programming
language with complicated procedural semantics (particularly
backtracking).
>So let's not fool ourselves, and our
>students, that Prolog is logic. It isn't.
You can say its logic to a first approximation and just beacause its not
the only thing you need to know to become a good Prolog programmer is no
reason to treat logic without the reverence it deserves. Do you see the
declarative semantics, brother? Yes, I SEE the declarative semantics!
Hallelujah:-)
> What I can not agree with
>is an interpretation in which (a->b) succeeds if both a and b are false
>(because it would mean that b has to be executed regardless of a.)
The NU-Prolog interpretation of (a->b) succeeds if both a and b are false,
without executing b.
lee
Bart Demoen
>... choice-points, indexing, ...
>Frankly, I don't think you can be a good Prolog programmer if you
>don't grasp these concepts.
to which Lee in <931182...@mulga.cs.mu.OZ.AU> replies
> Unfortunately I have to agree, and I think that its an important
> criticism of Prolog.
I prefer to see it a criticism of Prolog compilers.
I know that a compiler cannot detect in general that a choicepoint is not
necessary and that sometimes cuts are necessary, but very often, my eye sees
obvious determinism and the compiler doesn't.
Moreover, there are equivalent constructs like
a(X,Y) :- X >= Y , g .
a(X,Y) :- X < Y , h .
and
a(X,Y) :- X >= Y , ! , g .
a(X,Y) :- h .
and
a(X,Y) :- X >=Y -> g ; h .
and
a(X,Y) :- X >=Y , ! , g ; h .
or
a([X,Y|R]) :- blabla , g([Y|R]) .
and
a([X|Z]) :- Z = [Y|R] , blabla , g(Z) .
or
a([]) :- ...
a([X|R]) :- ...
and
a(L) :- L = [] , ...
a(L) :- L = [X|R] , ...
or
try putting the argument that makes your predicate deterministic
in the second argument position ...
or
see your performance degrade if you dare use abstract data types
and your system has no partial evaluation
or
instead of ./2, try using a meaningful functor name with arity 2
which most compilers do not treat the same way and then we are told (by
compiler writers) that there is a 'good' way and a 'bad' way to write things.
That's absurd.
Prolog implementors have a solution for each of the above things, actually a
solution that works for most 'user' problems, the ultimate solution, by which
the user is not helped at all and in fact many users feel bad about it:
do it yourself - it is easy in Prolog
If it is so easy, why haven't they done it themselves and put it in the system ?
Prolog suffers most from being badly implemented - well, that sounds to hard,
from not being implemented as good is possible.
Bart Demoen
Peter Van Roy
> Let's just admit it, in the future, Prolog will
> still be nothing but a toy for the purists, and all practical programming
> will be made in C++.
> /Jonas
Regarding the hordes of C++ programmers, it is their loss, not ours. In our
lab I am seeing Prolog-like ideas trickle into practical C and C++ programs.
For example, one tool is using a limited subset of infinite tree unification.
Another example is Extended DCGs (corresponding to the use of monads in
functional languages). C++'s I/O stream routines implement a hacked up subset
of this. In Prolog, besides being clean, it is useful for all data types, not
just streams. I am currently using a preprocessor that goes far beyond even
the Extended DCG's used in Aquarius Prolog. It's quite comfortable to program
in, believe me, and eminently practical.
Having a sound theoretical basis does not make a language a toy for purists.
On the contrary, it´s a big advantage. Without it we would be no more than C
with a few clever libraries and a large manual explaining how to use them.
That's how most good C programming is done these days, by the way¸ using C
mostly as glue.
Practicality is in the eye of the beholder. For most any general-purpose
programming task, Prolog-like languages are quite practical.
Peter
----------------------------------------------------------------
Peter Van Roy DEC Paris Research Laboratory
Email: van...@prl.dec.com Phone: (33)-1-47.14.28.65
Micha Meier
>In article <1993Apr27.1...@proactive.com> jo...@proactive.com (Jonas Almgren) writes:
>>... choice-points, indexing, ...
>>Frankly, I don't think you can be a good Prolog programmer if you
>>don't grasp these concepts.
>
>to which Lee in <931182...@mulga.cs.mu.OZ.AU> replies
>
>> Unfortunately I have to agree, and I think that its an important
>> criticism of Prolog.
>
>I prefer to see it a criticism of Prolog compilers.
>Prolog suffers most from being badly implemented - well, that sounds to hard,
>from not being implemented as good is possible.
I fully agree. If a program is not efficient in Prolog it does not mean
that one should try to match it to the compiler, but ther other way round.
There are limits to what a Prolog compiler can do, but it should certainly
do everything that is obvious. People who are now trying to teach others
how to program in a way that suits current compilers should better try
to put their knowledge of such programming into programs that can
transform automatically obvious user programs into ones that are efficient
on current compilers. The reason for this is obvious - when we
have better Prolog compilers, we can just drop the preprocessor (or make
a better one) and keep the readable program.
By this I do not mean that every efficient Prolog program is unreadable,
but programs relying on a particular feature of a Prolog compiler usually are.
Jonas Almgren
>In article <1993Apr22.1...@proactive.com>, jo...@proactive.com (Jonas Almgren) writes:
>> Let's just admit it, in the future, Prolog will
>> still be nothing but a toy for the purists, and all practical programming
>> will be made in C++.
>
>> /Jonas
>
>Regarding the hordes of C++ programmers, it is their loss, not ours.
Of course it is. I'm really surprised the irony of my message was
missed, I guess a ':-)' should have been added. I'm not a C++
programmer, but from what I know of C++, it still lacks most of the
features that make Prolog a superior programming language. My point
was that if we keep on bickering about the details of the Prolog
language, people outside the Prolog community will not see what the
real advantages are. The Prolog ISO standard might not be perfect, but
the language described therein surely is better than C or C++. Can we
agree on that?
>Having a sound theoretical basis does not make a language a toy for purists.
>On the contrary, it's a big advantage.
The problem is that if you claim *THE* advantage of Prolog is its logic
foundation, you're in trouble. The logic foundation of Prolog is of very
little help when you write an extensive Prolog program. You care much,
much more for the other advantages Prolog gives you (explicit data
structures, unification, built-in data base and hashing/indexing). Yes,
some of these have a foundation in logic, but it's their practical usage,
and how you think of them when programming, that makes Prolog a great
language. Not whether they are inherited from logic or not.
>Without it we would be no more than C
>with a few clever libraries and a large manual explaining how to use them.
Well, if these libraries gave us the same ease of programming Prolog does
(which I doubt they ever could), I don't see why they would be any worse
than Prolog. A programming language has to be judged by it's virtue as
programming language, not by it's heritage. As we all know, only a
rather uninteresting (from a programming language point of view) subset
of Prolog is really logic anyway.
>Practicality is in the eye of the beholder. For most any general-purpose
>programming task, Prolog-like languages are quite practical.
Indeed.
In another article, mi...@ecrc.de (Micha Meier) writes:
>There are limits to what a Prolog compiler can do, but it should certainly
>do everything that is obvious. People who are now trying to teach others
>how to program in a way that suits current compilers should better try
>to put their knowledge of such programming into programs that can
>transform automatically obvious user programs into ones that are efficient
>on current compilers. The reason for this is obvious - when we
If you can't make an optimizer perfect, you must leave it transparent
enough so that the programmer can (with a reasonable effort) avoid
the deficiencies. For instance, if a Prolog compiler quazi automated
the selection of which arguments to index on, and it wasn't straight
forward to tell the actual selection from the structure of the program,
the programmer would be better off with just 1st argument indexing.
One problem with pre-processors compiling a clean Prolog program into
a more efficient (compiler adapted) program, has to do with debugging.
You would like to annotate the transforms, so that a source level debugger
still could handle the optimized code. Peter Schachte at Quintus has
some really good ideas on how to extend term_expansion/[2,3] to handle
such annotations, and when Quintus releases them, we could look
forward to e.g. object layers, and pre-processors performing partial
evaluation (by some called partial deduction, which of course isn't
really appropriate, since the tough problems with partial evaluation
of *Prolog* has to do with the non-logical features), and still be
able to debug our programs!
/Jonas
James Mcguire
> In our lab I am seeing Prolog-like ideas trickle into practical C and C++ programs.
I agree. Four years ago, all I did was Prolog programming. I still program some in
Prolog but, I do much more C++.
The thing I liked about Prolog was the power of backtracking: being able to get
the next answer, and let Prolog worry about maintaining context. In C++, I use
this notion of backtracking all the time. In C++, you call these "iterators". These
effectively implement an active object or stream (in the Abelson and Sussman sense -
Structure and Interpretation of Computer Programs). My "real world" code is
strewn with backtracking points, where I force the stream to get the next answer.
The C++ implementation of the active object maintains the context state to backtrack
and get the next answer. It may be hard to believe, but I feel my C++ code
has a prolog feel to it.
Jim
Lee Naish
>In article 42...@cs.kuleuven.ac.be, bim...@cs.kuleuven.ac.be (Bart Demoen) writes:
>>In article <1993Apr27.1...@proactive.com> jo...@proactive.com (Jonas Almgren) writes:
>>>... choice-points, indexing, ...
>>>Frankly, I don't think you can be a good Prolog programmer if you
>>>don't grasp these concepts.
>>
>>to which Lee in <931182...@mulga.cs.mu.OZ.AU> replies
>>
>>> Unfortunately I have to agree, and I think that its an important
>>> criticism of Prolog.
>>
>>I prefer to see it a criticism of Prolog compilers.
>..
>>Prolog suffers most from being badly implemented - well, that sounds to hard,
>>from not being implemented as good is possible.
>
>I fully agree. If a program is not efficient in Prolog it does not mean
>that one should try to match it to the compiler, but ther other way round.
>There are limits to what a Prolog compiler can do, but it should certainly
>do everything that is obvious.
Jonas writes:
>If you can't make an optimizer perfect, you must leave it transparent
>enough so that the programmer can (with a reasonable effort) avoid
>the deficiencies.
I agree with Jonas. If one of your procedures leaves choice points
around it can kill the efficiency of your whole program. Its all very
well handling more and more special cases in the compiler, but there
will always be cases where the program is deterministic from a logical
point of view, but the implementation is not clever enough. As a
result, the space complexity may be O(N) instead of O(1). No-one has
found a method of implementing Prolog style non-determinism without this
property to my knowledge.
The same criticism applies to some of the "Andorra" based languages such
as Andorra-I. A single case of missed determinism can dramatically affect
efficiency, but in Andorra-I there is a deliberate decision not to tell
the programmer about such details of the implementation.
There are several possible solutions to the problem:
1) Don't support nondeterminism.
2) Have sufficient conditions for determinism detection which are simple
enough for an average programmer to comprehend (eg, first argument indexing
+ cut). These should preferably be standardized so efficient portable
programs can be written. Of course your compiler may do additional
analysis, but its not so useful unless the programmer knows about it.
3) Provide good performance analysis tools (eg gauge) which can track
down choice points, plus some rules for eliminating choice points (eg,
add cut). Here a clever compiler is more useful.
4) Support determinism declarations. This is done in Parallel NU-Prolog,
which is Andorra-like. If the system is unable to recognize the
declared determinism an error message is produced. You still need rule
for making determinism more obvious to the system (eg, adding cut).
lee
Bart Demoen
> ... simple enough for an average programmer to comprehend (eg, first argument
> indexing + cut). These should preferably be standardized so efficient portable
> programs can be written ...
please Lee, don't joke about standardization: some people will take this seriously !
Prolog has enough trouble already
Bart Demoen
Paul Singleton
> Having a sound theoretical basis does not make a language a toy for purists.
> On the contrary, it4s a big advantage. Without it we would be no more than C
> with a few clever libraries and a large manual explaining how to use them.
> That's how most good C programming is done these days, by the way8 using C
> mostly as glue.
Most of my Prolog programming is done using a few (actually, many) clever
libraries, using Prolog as glue (Prolog makes a far better glue than C,
IMHO). Don't sniff at software reuse.
Paul S.
Paul Singleton
>>Without it we would be no more than C
>>with a few clever libraries and a large manual explaining how to use them.
> Well, if these libraries gave us the same ease of programming Prolog does
> (which I doubt they ever could), I don't see why they would be any worse
> than Prolog. A programming language has to be judged by it's virtue as
> programming language, not by it's heritage. As we all know, only a
> rather uninteresting (from a programming language point of view) subset
> of Prolog is really logic anyway.
I have made *far* more use of Prolog library code in my Prolog programs than
I ever did (or do) of 'C' (i.e. 'C'-interfaced) libraries in my 'C' programs.
Sure, I use 'stdio' and 'strings', but rarely do I feel that I am building
a 'C' program largely out of big chunks of functionality plus a modicum of
glue.
There is still (?) some interest in "Software Reuse" in the world outside,
and I feel we should be able to quantify, or at least qualify, the superior
reuseability of Prolog procedures.
For starters, there is:
* unification of arguments to relational procedures subsumes fixed
input/output args in lowlier languages;
* stateless (assert/retract-less) code has no initialisation and cleanup
requirements;
* the conciseness and soundness of dynamic memory allocation (and
recovery) in Prolog makes it easier to write programs in the way
one really *ought* to write 'C' programs but can't be bothered (I
couldn't face malloc-ing for every little new bit of data);
* typelessness and pass-by-reference makes it easier to write and
reuse type-generic procedures.
Maybe we can't persuade the world to use Prolog :-) but we might illustrate
why their languages of choice encourage barely-reuseable programming practice
and style.
----
__ __ Paul Singleton (Mr) JANET: pa...@uk.ac.keele.cs
|__) (__ Computer Science Dept. other: pa...@cs.keele.ac.uk
| . __). Keele University, Newcastle, tel: +44 (0)782 583477 << NEW for
Staffs ST5 5BG, ENGLAND fax: +44 (0)782 713082 1993