PROLOG-REQUEST@SUSHI.STANFORD.EDU (Chuck Restivo, The Moderator) (10/25/87)
PROLOG Digest Tuesday, 27 Oct 1987 Volume 5 : Issue 78
Today's Topics:
Query - Negation as Failure,
Implementation - Prolog Machines,
LP Library - Rodger's Review
----------------------------------------------------------------------
Date: 22 Oct 87 08:43:54 GMT
From: reeves@locus.ucla.edu
Subject: forall/2 and negation as failure
I'm having a problem reading forall/2 and wondered if anyone could help.
In Sterling and Shapiro p. 270-271, the claim is that
forall(Goal,Condition) is true for all solutions of Goal, Condition is
true. Under this reading not(Goal, not(Condition)) works fine as far as I
can tell.
They claim that
forall(father(X,C),male(C))
is checking _for_ fathers that have all male children. My reading is that
it is checking _that_ all fathers have all male children. Their
implementation returns two solutions for the query: the fathers that have
only male children. In the database, however, there are fathers who do
not have only male children, so (I would think) the query should fail.
Is there a reading for forall/2 for the following implementation (from S&S)?
forall(G,C) :- setof(C,G,Cases), check(Cases).
check([Case|Cases]) :- Case, check(Cases).
check([]).
Alternatively, is there a case where:
forall(G,C) :- not(G, not C).
behaves counterintuitively, due to the use of not as negation-as-failure?
-- John Reeves
------------------------------
Date: 23 Oct 87 07:13:08 GMT
From: mcvax!unido!ecrcvax!jclaude@uunet.uu.net (Jean Claude Syre)
Subject: Prolog Machines
PROLOG MACHINES:
Here we go: below is a (non-exhaustive) list of machines/prototypes/
developments/basic research under way in different places around the
world, extracted from my presentation at a Panel on Parallel Inference
Machines at IJCAI87, Milano.
At ECRC, the Computer Architecture Group (17 people) is working
quite a lot on Sequential machines, but is also implementing a
Parallel Logic Programming System called PEPSys, on a commercial
multiprocessor. For more info contact us at ECRC Arabellastr. 17
D-8000 Munich 81 , BRD. We also would be pleased to get more info
on your activities (papers, reports, performance studies, ...) if
they deal with these topics, THANKS.
WORD is Word Length, KLIPS means the peak performance on Concat or
Naive reverse. The Klips is the most fuzzy unit to measure
performance of Prolog Systems (between 1 and 2000 assembly
instruction of a CISC computer, imagine..., but my opinion is that
REAL performance can be estimated at half of the peak performance for
Hardware implementations of Prolog, wheras it could be around 1/6th
to 1/10th of the peak performance for Software implementations).
NAME WORD KLIPS BY REMARKS
PSI I 40 25 Icot Inter., stand alone
PEK 34 40 U. KOBE
PSI I 40 110 Icot Compiled WAM
PLM 32 400 U. Berkeley WAM
CHI 36 250 NEC C&C ECL, WAM
CHI II ? 500? NEC ? (info wanted!)
IPP 32 1000 Hitachi ECL, WAM
PSI II 40 250 Icot stand alone wks,WAM
X1 32 300 Xenologic PLM, SUN co-proc.
ICM3 32 530 ECRC WAM, co-proc.
ICM4 32 680? ECRC RISC, fast memory
KCM 64 650 ECRC WAM, attached proc
DLM 38 600? BAe exp. board
AI32 40 200? Hitachi co-proc. chip
Pegasus 40 240 Mitsubishi RISC chip
SM45000 40 ??? Inference AI co-proc
MDS ?? 200?? Matra chip set
TOSHIBA ? ? 650 Attached Processor
OTHERS? CERTAINLY. I APOLOGIZE
Current work at ECRC:
KCM: Knowledge Crunching Machine (with Siemens, BULL, ICL): 64-bit,
tagged architecture. Private memory, two large Data and Code caches
Full Prolog/Lisp system, with extras.
------------------------------
Date: Sun, 18 Oct 87 22:05:27 PDT
From: quintus!ok@Sun.COM (Richard A. O'Keefe)
Subject: Rogers' textbook.
Having suggested in my previous message to this Digest that it
would be a good idea to discuss textbooks, here's some provocation.
I'm going to comment on a textbook:
@Book(RogersPrimer
, Key = Rogers
, Author = "Rogers, Jean B."
, Title = "A Prolog Primer"
, Publisher = Addison-Wesley
, Year = 1986
)
It is essential to point out before I start that Rogers explicitly
says "The audience for whom this book was written includes mature
learners who are neither experienced in computer programming nor
particularly sophisticated in mathematics." Rogers does claim that
"This book is also an effective introduction to Prolog for people
already quite familiar with computer programming", but obviously the
requirements of the first audience are the main control. I am quite
unable to judge the suitability of this or any other textbook for that
audience. The book "has been used for instruction in courses with
computer science and other graduate students, computer science under-
graduates, and undergraduates from non-computer-science majors. Their
feedback was a guiding factor in revisions for the book". It is worth
noting that Clocksin & Mellish can make precisely the same statement.
I should explain that I have not chosen to comment on Rogers' book
as an example of a notably bad book. Several people here liked it well
enough to buy copies. I am not commenting on the book as a whole in
any way at all. There are just two specific points I want to raise.
You should not attempt to guess my opinion of other aspects of the
book. For the most part, I have none.
The two points I want to discuss are setof/bagof and data base
design.
SETOF/BAGOF
Rogers explicitly states that "one version of Prolog is used
consistently in the examples and the explanations. That version is
Standard DECsystem-10/20 Prolog". We are entitled, therefore, to
conclude that when the book describes setof and bagof,
(a) Rogers has read the DEC-10 Prolog manual
(b) Rogers' book is intended to be true about DEC-10 Prolog
WHAT THE DEC-10 PROLOG MANUAL SAYS
setof(X, P, S)
Read this as "S is the set of all instances of X such that P is
provable, where that set is non-empty". The term P specifies a
goal or goals as in call(P). S is a set of terms represented
as a list of those terms, without duplicates, in the standard
order for terms. If there are no instances of X such that P is
satisfied, then the predicate fails.
The variables in appearing in the term X should not appear
anywhere else in the clause except within the term P.
Obviously, the set to be enumerated should be finite, and
should be enumerable by Prolog in finite time. It is possible
for the provable instances to contain variables, but in this
case the list S will only provide an imperfect representation
of what is in reality an infinite set.
If there are uninstantiated variables in P which do not also
appear in X, then a call to this evaluable predicate may
backtrack, generating alternative values for S corresponding to
different instantiations of the free variables of P. (It is to
cater for such usage that the set S is constrained to be
non-empty.) For example, the call:
| ?- setof(X, X likes Y, S).
might produce two alternative solutions via backtracking:
Y = beer, S = [dick,harry,tom] ;
Y = cider, S = [bill, jan, tom]
-- This was written in English, where "cider" denotes an
-- alcoholic beverage made from fermented apple juice. RAO'K.
The call:
| ?- setof((Y,S), setof(X, X likes Y, S), SS).
would then produce:
SS = [(beer,[dick,harry,tom]),(cider,[bill,jan,tom])]
Variables occurring in P will not be treated as free if they
are explicitly bound within P by an existential quantifier. An
existential quantification is written:
Y^Q
meaning that "there exists a Y such that Q is true", where Y is
some Prolog variable. For example:
| ?- setof(X, Y^(X likes Y), S).
would produce the single result:
S = [bill,dick,harry,jan,tom]
in contrast to the earlier example.
bagof(X,P,Bag)
This is exactly the same as setof except that the list (or
alternative lists) returned will not be ordered, and may
contain duplicates. The effect of this relaxation is to save
considerable time and space in execution.
X^P
The interpreter recognises this as meaning "there exists an X
such that P is true". and treats it as equivalent to call(P).
The use of this explicit existential quantifier outside the
setof and bagof constructs is superfluous, and therefore is not
recognised by the compiler.
-- But it still WORKS in compiled code. RAO'K.
WHAT ROGERS SAYS
PP 134-135 (Using Built-in Predicates)
Two predicates that gather instances of occurrences of objects
are bagof and setof. To use these predicates, we specify a
goal and a variable in the goal. The predicates search through
the data base to find all appearances of the goal that can be
proved true. For each true goal, the constant value that was
instantiated to the specified variable is gathered into the
bag. The bag (a list) is instantiated to the variable given in
the third argument of the predicate. If there are no
occurrences, the goal fails. This data base and query using
the bagof predicate show how to collect a list of constants
designated by the variable.
parent(jan, bet).
parent(jan, cat).
parent(joe, ann).
parent(joe, cat).
?- bagof(Child, parent(jan,Child), B).
B = [bet,cat]
yes
If there is more than one possible list of instances because of
another variable in the specified goal, the goal can backtrack
and find other responses. For example, given
parent(jan, bet).
parent(jan, cat).
parent(joe, ann).
parent(joe, cat).
?- bagof(Child, parent(Who,Child), B).
Who = jan, B = [bet,cat] ;
Who = joe, B = [ann,cat] ;
no
The instantiation of different bags can be gathered into a
single response by using what is called an existential
quantifier on the non-gathered variables from the goal. The
variable name followed by a caret (^) appears just before the
predicate. A predicate with several variables requires a
sequence (e.g., A^B^C^D^).
Using the data base above
?- bagof(Child, Who^(parent(Who,Child)), B).
B = [bet,cat,ann,cat],
Who = _45,
Child = _24 ;
no
This existential quantifier (read X^ as "there is an X such
that") is used only in bagof and setof.
The setof predicate works as though bagof is called to gather
the values into a list before the list is sorted. As in the
result of sort, any duplicates will have been removed.
Using the data base above
?- setof(Child, P^(parent(P,Child)), S).
S = [ann,bet,cat],
P = _45,
Child = _24 ;
no
P 203 (Appendix: Built-in Predicates)
bagof(V,P,B)
This predicate gathers all the instances of the variable V
that appear in goals, P, that are provable. It puts the
instances into a list that is instantiated to the bag B.
If there are no instances, the goal fails.
setof(X,P,S)
This predicate works as though bagof had been followed by
sort. That is, the elements in the list, S, are sorted and
duplicates have been removed. Existential quantifiers can
be used with bagof and setof. For example,
bagof(X, A^B^C^one(A,B,C,X), B).
COMMENTS.
It's been a while since I read the setof/bagof section in the
DEC-10 Prolog manual critically. I am pleasantly surprised at how
precisely it manages to say just what is true. It even manages to
convey the impression that setof/3 is the fundamental predicate and
bagof/3 is secondary, which is epistemologically true even if it may
not be true of an *implementation* of the operations. Rogers, alas,
manages to convey the opposite impression.
PROBLEM ONE:
The really vital predicate for an implementor to provide and
for a programmer to understand is setof/3. setof/3 was added
to the DEC-10 Prolog language to make certain types of data-
base query expressible in Prolog. bagof/3 is just a hack you
can use when you know that the exact representation of the set
doesn't matter too much. Rogers manages to suggest that the
way to understand setof/3 is to understand one way it might be
implemented.
A much worse problem is the foggy language. Instantiation is a
process in which variables in a term TA are bound to other terms,
forming a new term TC. TC is said to be an instance of TA, and TA is
said to be instantiated to TC. <<Terms>> are <<instantiated>>,
<<variables>> are <<bound>>. Since a variable is a special case of a
term, it is accurate to speak of instantiating a variable to a term.
But you cannot instantiate a constant to something, it hasn't got any
variables to bind. If the variable X is bound to 47, it is true that X
is instantiated to 47, but it is not true that 47 is instantiated to X.
Rogers could perhaps employ the Humpty-Dumpty offence, but the nearest
thing to a definition of "instantiation" in the book is on p55, and as
that clearly talks about a <<variable>> being instantiated or
uninstantiated, the standard direction must be assumed.
The same distinction applies in conventional languages, where an
assignment statement X := 47 is read as "47 is assigned to X" or "X is
assigned the value 47". But X is not assigned to 47! It's as
different as you paying tax to the IRS or them paying tax to you.
It is *especially* important to keep one's language straight when
teaching beginners, because they don't know enough to correct their
teacher, and a teacher with confused language is likely to have
confused students.
I found Rogers' language in these two passages very confusing. For
example, what is "an instance of an occurrence of an object"? Neither
"object" nor "occurrence" is in the index. Neither is "appearance of a
goal" defined that I can see. The book does not say what it means for
a "list of constants" or anything else to be "designated by a
variable"; "designated" is not in the index.
PROBLEM TWO:
The language in these passages looks like technical language
but is not being used with the precision proper to technical
language. A key technical word is being used backwards! The
effect is very confusing.
You may dismiss this as "nit-picking". Well, there are two answers
to that. With all the earnestness I possess, I tell you that I found
Rogers' explanation of setof/3 and bagof/3 so confusing that if I had
been trying to learn Prolog from this book I would have given up trying
to understand setof/3 and bagof/3, and would have started to have
serious doubts about Prolog generally. Without any earnestness at all,
I would point out that "nit" is one of the oldest words in the English
language. It comes from the Indo-European stem "knid-" (so is at least
5,000 years old) and means the egg of a louse. Picking nits out of the
hair is an essential part of health care, if there are any nits. Could
any of you seriously suggest that heads should have lousy hair on them,
or lousy ideas in them?
Let's suppose that one works one's way past the fog. In a book for
beginners, it is difficult to tell the whole truth. One's readers may
not possess the vocabulary needed to express the whole truth. But
everything one says should be true. It is quite proper to simplify,
but it is important to say that one has done so.
PROBLEM THREE
The following statements are reasonable inferences from
what Rogers says, but are not true.
In bagof(V, G, L) or setof(V, G, L)
(a) V must be a variable.
(b) V must occur in G.
(c) L must be a variable.
(d) G must bind V to constants.
(e) G will be solved by checking the data base,
not by general interpretation.
Re point (e), I would remind you that Rogers explicitly says that
"The predicates SEARCH THROUGH THE DATA BASE TO FIND ALL APPEARANCES".
It is probably a coincidence that points (a), (b), (c), and (d) were
also exhibited by Lagache in his library documentation. Since Rogers
must have had access to the DEC-10 Prolog manual, at least the
falsehood of (a) should have been apparent to her.
Am I nit-picking again? Not at all. It is USEFUL that (a) is
false. The DEC-10 Prolog manual even includes an example. When
converting between one representation of a graph and another, I have
very often found it useful to do
setof(Node-Neighbours,
setof(Neighbour, adjacent(Node,Neighbour), Neighbours),
Graph)
As for point (b), I have found it useful too, but at a minimum it is
useful to know that the Prolog system does not regard it as an error
for there to be no variable common to V and G, so that if that should
that be the cause of a bug in your program, you will know that Prolog
can't be expected to tell you about it.
[ Begin digression.
Having a call to setof/3 or bagof/3 where the first argument
is ground or contains a variable not in the second argument
is sufficiently odd that it is worth checking. You might like
to add this to your library:
checked_setof(Template, Generator, Set) :-
check_sb(Template, Generator, Set, set_of),
setof(Template, Generator, Set).
checked_bagof(Template, Generator, Bag) :-
check_sb(Template, Generator, Bag, bag_of),
bagof(Template, Generator, Bag).
check_sb(T, G, _, _) :-
\+ numbervars(T, 0, 0), % T not ground
\+ ( numbervars(G, 0, N),
( N = 0 % G not ground
; numbervars(T, N, X),
X > N % T not covered
)
),
!.
check_sb(T, G, L, P) :-
/* I don't care about efficiency here */
Query =.. [P,T,G,L],
format(user_error,
'~N! Bad template or generator~n! Goal: ~q~n',
[Query]),
format(user_error,
'Enter true, fail, or abort. ', []),
read(user_input, Command),
call(Command).
This code has been tested in Quintus Prolog.
If you think this kind of mistake is one you are likely to make,
it would be worth your while using an interface like this. The
cost of checking is comparable to the cost of finding one more
solution.
End digression.
]
Concerning point (d), the same example in the DEC-10 Prolog manual
that refutes point (a) refutes point (d). It is useful to be able to
collect proof trees, or picture descriptions, or fragments of code, or
whatever. If p(X) is a query which instantiates X to constants, then
X^(p(X), name(X,Chars)) is a query which unifies Chars with a list of
character codes, and it is reasonable to write
setof(Chars, X^(p(X), name(X,Chars)), SetOfNames)
[ Begin digression.
In fact it is more efficient not to do that. The trouble is
that executing an all-solutions predicate like findall/3, or
bagof/3, or setof/3, involves copying all the instances you
want, so the smaller the instances the cheaper. It is also
cheaper to compare smaller terms. So a more efficient way of
writing the query above is
setof(X, p(X), SetOfConstants),
maplist(name, SetOfConstants, SetOfNames)
The original version of the query is a perfectly sensible thing
to write, and the time to worry about efficiency like this is
AFTER that part of the program is working. Even when parts of
the result can be recomputed, as here, it may be more efficient
to copy the results rather than recompute them. It all depends
on the problem. Feel free to make the first argument of an all-
solutions predicate precisely as complex as suits the problem,
but try not to make it any bigger.
There is a general point here about when you should move a
computation inside setof/3 and when it should be outside.
Let's leave that for another time; it belongs in a general
discussion of sequence mapping. But if the computation is
likely to fail, or to produce smaller results, putting it
inside may be a good idea. Watch out for free variables!
End of digression.
]
There is a lot more I could say. But that's probably enough. It
may seem unfair to you that I have said so much about so very little of
Rogers' book. After all, this is a primer. Well, I repeat that I am
not giving a general review of Rogers' book. (This is fun, but it is
time-consuming.) Other parts of it may be excellent. All I am saying
is that
The sections of Rogers' book which describe setof/3 and bagof/3
are confusing to read and may lead reasonable readers to believe
things about those predicates which are not true.
It may, for all I know, be an excellent book in other respects. I
repeat that I do not regard myself as competent to judge what is a good
book for complete beginners and what is not.
If any of you is considering writing a Prolog textbook, I would
urge you to give setof/3, bagof/3, and findall/3 a chapter to
themselves, with lots of examples, chosen so that the all-solutions
predicates are naturally wanted to solve the problems, not contrived
"X likes Y" or "parent(X,Y)" examples invented to illustrate the
solutions.
That's finished with setof/3 and bagof/3. But there is another
point in Rogers' book which is worth discussing. I'm not referring to
page 174, which is likely to leave the reader believing that
"module"="predicate". If I were going to refer to that, I'd have to
refer to exercise 10.3.2, and I can't see any *point* in rewriting that
clause at all, let alone into three modules. (Whatever they are.
"Module" is not in the index. Looking at the answer, it appears that
"module"="clause". Not in Quintus Prolog, Prolog-X, or NIP it isn't.]
The second point concerns data base design, which is not something
that Rogers claims to cover, so this should not be read as a criticism
of things Rogers does claim to cover. The example actually comes from
the chapter on arithmetic.
Rogers says
Suppose we have a Prolog data base that contains information
about the presidents of the United States in the form:
president(<name>, <birthyear>,
<year began office>, <year left office>).
From this base, we can derive several kinds of information.
How long was a president in office:
length_of_office(Name, Years) :-
president(Name, _, In, Out),
Years is Out-In.
How old was a president when he took office:
age(Name, Years) :-
president(Name, Birth, In, _),
Years is In-Birth.
And so on. What is wrong with this?
There is a problem endemic among all sorts of textbooks. I first
had it brought to my attention in Statistics textbooks. The problem is
this:
- authors write examples to illustrate methods.
So they work from a known method to an invented example.
- students are trying to acquire two kinds of knowledge:
- how the methods work
The examples are usually adequate for this
- WHEN TO USE a particular method
And it is not uncommon for the methods to be
inappropriate to the invented problems.
That is, very often there is a better way to handle a given example
than the method the example has been chosen to illustrate, so a student
who is trying to work out when to use the method is left confused.
I wouldn't be surprised to find the same problem showing up in
carpentry textbooks.
The specific problem here is that Rogers is illustrating
arithmetic, and the examples she has made up do in fact illustrate the
aspects of arithmetic she is trying to explain. BUT any interested
student is going to look at section 9.4 as an example of how to put
together a data base about American presidents AS WELL. Indeed, as we
have seen with quicksort, it is not uncommon for students to miss the
real point of an example entirely and focus exclusively on the example
as a way of solving the invented problem.
What's wrong with this design of the data base? Briefly, the
information should be held in two predicates, not one:
birth_year(Name, Year)
presidency(Name, BeginningYear, EndingYear)
Indeed, there is a strong argument for splitting the second of these
predicates into two predicates itself: for how are we to say anything
about the *present* president?
I am not a citizen of the United States. I have heard that a
president can serve for only two consecutive terms, but I do not know
whether a president can serve two separated terms, or more than two
separated terms. I know that originally when a president died in
office the vice-president assumed his duties but not his title, but that
now he assumes the title as well, but I don't know whether that affects
the permitted number or consecutivity of terms. I can see no a priori
reason why a president might not resign part way through one term and
then return to office 10 years later. There is certainly nothing to
prevent Prime Ministers in many countries from holding office in
separated terms.
So in principle, it looks as though there could be two clauses
for some presidents. Let's imagine a hypothetical case:
president(ryan, 1660, 1700, 1704).
president(ryan, 1660, 1708, 1712).
Now let's pretend that we discover that we got the year of birth wrong
(not an implausible assumption), and want to change it. Now we have to
change TWO places.
****************
* A general rule of thumb for data base design is that each piece
* of information should be represented in ONE place. The uniqueness
* of this place should not depend on the contents of the data base
* but should be built into the structure.
****************
Now let's consider it from another angle. Suppose we have
president(macfarland, 1680, 1712, 1716)
and someone tells us no, it was 1716-1720. We have to remember to copy
the BirthYear from the old president/4 fact to the new one.
****************
* Another general rule of thumb is that pieces of information which
* are likely to be updated independently should be in different places
****************
Suppose we decided to represent information about vice-presidents
as well. Following Rogers' example, we would have facts
vice_president(Name, BirthYear, In, Out).
An obvious question is, for any two people X Y in the data base, was X
born before Y or not? With this structure, we have to write four
cases: X is a president/vice_president, Y is a president/vice_president.
But with the structure which keeps the birth year separate, we can write
born_before(X, Y) :-
birth_year(X, Xyear),
birth_year(Y, Yyear),
Xyear < Yyear.
****************
* Another rule of thumb is that a conceptual relation should be
* represented by a single relation, not by different relations for
* different types
****************
That's a bit vague, and there are justifiable exceptions, but
having to look in different places for the birth dates of presidents
and vice-presidents would be silly. Rogers' does not have an example
doing this. All I claim is that a naive reader without the benefit of
Rogers' actual presence could be misled by the example in section 9.4
into doing this.
Almost any good data-base textbook will do a much better job of
explaining these potential problems than I'm likely to. Look in the
index under "update anomalies" and "normal forms". Read Kent's book
"Data and Reality". When you know what a "join dependency" is, you'll
know why you will usually want to design them out.
--------------------------------
CONCLUSION
I've discussed at length two problems with Rogers' book. Would
someone who thinks it is a good textbook say what they like about it
and why they think it is better than some other textbook? I repeat
that I am not saying that Rogers' book is specially bad. Prolog
textbooks which explain setof/3 and bagof/3 lucidly and accurately are
vanishingly rare, and the problem of examples seems to apply to most
textbooks. Do you think these aspects matter? Would anyone teaching a
Prolog course like to say what text(s) s/he is using, why, and what
supplementary material is needed?
Are there any good elementary books on data base design? Anyone
got a favourite they'd like to recommend?
------------------------------
End of PROLOG Digest
********************