PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (08/10/86)
PROLOG Digest Monday, 11 Aug 1986 Volume 4 : Issue 35
Today's Topics:
Implementation - Bagof & ->,
Complaint - Comments & Consideration,
Puzzle - Farmer Solution
----------------------------------------------------------------------
Date: Fri, 8 Aug 86 16:22:12 pdt
From: Allen VanGelder <AVG@diablo>
Subject: Bagof Comments
Dave Plummer came up with a lulu in Vol. 3, Issue 34:
What should bagof do here?
p(1,_). p(2,_). p(3,3). p(4,4).
?- bagof(X, p(X,Y), S).
He reports that that the first solution was Y=3,S=[1,2,3],
but the second was Y=4,S=[4]. He expected the second to be
Y=4,S=[1,2,4]. In fact, if he reversed p(3,3) and p(4,4)
he surely would have gotten Y=4,S=[1,2,4] as the first
solution.
In designing NAIL! (*), we decided that neither of these
solutions was likely to make any sense in practice. We
established the following rule for evaluating our 'findall':
a variable in the goals (middle argument) of the 'findall'
was existentially quantified if it did not appear elsewhere.
Thus NAIL! delivers one solution, S=[1,2,3,4], to the above
question.
If the user really is interested in "grouping by" values of Y,
to use terminology from DBMS, then the the Y values need to
come from some source outside the 'findall'. E.g., add the
rule
g(Y,S) :- findall(X, p(X,Y), S).
Then NAIL! would answer the question ?- g(3,S) with S=[1,2,3]
and would answer g(4,S) with S=[1,2,4]. So far, this is
something like what Dave Plummer expects from 'bagof'.
In addition ?- g(23,S) is answered S=[1,2]. NAIL! would
decline to answer ?- g(U,S), essentially because there are
infinitely many answers.
The "universe" has to be specified. Thus, it is valid to ask:
?- member(U, [3,4,23,14,hike]), g(U,S).
which has five solutions that readers will have no trouble
figuring out.
* For information on NAIL!, see "Design Overview of the NAIL!
System" in Proceedings ICLP, July 86, London, or STAN-CS-86-1108
from Stanford Univ. Computer Science Dept.
------------------------------
Date: 9 Aug 1986 09:24-EST
From: Saumya Debray <Debray@Arizona.csnet>
Subject: Manipulating Programs With ->
It's well known that cuts can cause problems for tools that manipulate
Prolog programs. For example, inline expansion can't be done in a
straightforward way. In a paper at the Boston SLP last year, O'Keefe
recommended the use of the use of the if-then-else construct ( -> ) to
alleviate such problems. However, the way the construct "P -> Q ; R"
is parsed by Prolog -- as
';'( '->'(P,Q), R ) -- can also lead to problems
in the manipulation of Prolog programs.
In general, given two clauses
p(X) :- Body1.
p(X) :- Body2.
with identical heads, one would expect to be
able to replace them with the single clause
p(X) :- Body1 ; Body2.
This transformation is useful because it lets us avoid multiple
unifications of the same head arguments, and allows us to factor
common literals in the clauses. (We also use it in our compiler as a
starting point for other transformations that in some cases let us
generate code to create fewer choice points at runtime.)
Notice that this transformation works even if Body1 and Body2 contain
cuts. Well, it doesn't work if Body1 is of the form G1 -> G2. The
reason, of course, is that while one intuitively expects the principal
functor of P -> Q ; R to be '->', it really is ';'.
The problem is "merely" an idiosyncrasy of Prolog syntax, but an
annoying one. Perhaps the people involved with some of the earlier
implementations of Prolog could tell us the reasons for designing the
syntax of -> in this way?
-- Saumya Debray
------------------------------
Date: 8 Aug 86 12:43 PDT
From: Ghenis.pasa@Xerox.COM
Subject: Problem postings without comments
Regarding the recent posting of a buggy solution to the Farmers
problem with a request for help:
It DID lead to the posting of correct solutions, which is of value
to the distributon list, BUT, I doubt that too many people would
bother spending a lot of time trying to decypher the code in the
original posting when the author didn't care enough to insert some
comments init. >:-(
Personally, I refuse to spend more than 20 seconds trying to figure
out what an uncommented piece of code is doing, unless I have to.
Maybe my intelligence is too mediocre to simply recognize the
obvious meaning of "(F1,X1,G1,A1)" without being told. :-)
It is a matter of common sense and proper network etiquette that
any code postings to a list should include comments (if they are
meant to be analyzed) or be omitted altogether. This is doubly
true of postings of buggy code which list members are being asked
to read.
-- Pablo Ghenis
------------------------------
Date: Sun 10 Aug 86 13:53:24-PDT
From: Chuck Restivo <Restivo@Score.Stanford.EDU>
Subject: Uncommented Code
It is more often the case than not that code is checked before its
published. There exists some limitations on my time that make
detailed verification not always possible, unfortunately.
Best,
-- Chuck
------------------------------
Date: Fri, 8 Aug 86 00:15:04 edt
From: Yasuda%upenn-graded@cis.upenn.edu
Subject: Farmer Problem Solution
Yes, it works!!!!
============================= infile =======================
consult('farm.pro').
go(state(here,here,here,here),
state(there,there,there,there),
Path).
;
;
halt.
============================================================
======================== prolog call =======================
prolog <infile >outfile
============================================================
======================== outfile ===========================
C-Prolog version 1.5
| ?- farm.pro consulted 1340 bytes 0.333333 sec.
yes | ?- | |
Path =
[state(here,here,here,here),state(there,here,there,here),
state(here,here,there,here),state(there,there,there,here),
state(here,there,here,here),state(there,there,here,there),
state(here,there,here,there),state(there,there,there,there)]
Path =
[state(here,here,here,here),state(there,here,there,here),
state(here,here,there,here),state(there,here,there,there),
state(here,here,here,there),state(there,there,here,there),
state(here,there,here,there),state(there,there,there,there)]
no | ?- [ Prolog execution halted ]
============================================================
This program gives two solutions!
A nice thing about this solutions is that it can be used to
implement other problems. For example: Misssionaries and
Cannibals. [Indeed. -ed]
Regards,
-- Osvaldo
------------------------------
End of PROLOG Digest
********************