PROLOG-REQUEST@SUSHI.STANFORD.EDU.UUCP (10/25/87)
PROLOG Digest Wednesday, 28 Oct 1987 Volume 5 : Issue 79
Today's Topics:
Query - Algorithmic Debugging,
Implementation - Style,
LP Library - Textbook Review
----------------------------------------------------------------------
Date: Tue, 20 Oct 87 21:09:36+0900
From: Dongwook Shin <dwshin%csd.kaist.ac.kr@RELAY.CS.NET>
Subject: Algorithmic debugging
BIM_Prolog is advertised to provide rich programming environments.
Especially, BIM_Prolog brochure says that it also include the
algorithmic debugging facility originally devised by Shapiro, without
precise description. Is there anyone out there who knows that this
algorithmic debugging is also applicable to impure Logic Programmings
( with "cut", "assert", and "retract")? Any information would be
appreciated. Thanks!
-- D.W. Shin
------------------------------
Date: 19 Oct 87 09:23:00 EST
From: <cugini@icst-ecf.arpa>
Reply-to: <cugini@icst-ecf.arpa>
Subject: programming style
We seem to have some people on the list who have strong ideas about
Prolog style. Here's something that comes up over and over again
in my code and if there's an accepted neat way to handle it, I'd
be happy to know.
The general problem is how to write reasonably efficient code which
smoothly accepts different variables as input or output.
For instance, suppose we have lots of ground facts like this:
parent_child( big_Lothar, little_Lothar).
with the obvious interpretation, and we want to construct an
ancestor_descendant predicate. The naive and clean version
might be:
ancestor_descendant(Anc, Des) :- parent_child(Anc, Des).
ancestor_descendant(Anc, Des) :-
parent_child(Anc, Middle),
ancestor_descendant(Middle, Des).
This is all just ducky if Anc is ground on invocation. However, if
we invoke this with Des as the "input" and especially if we want to
get multiple solutions, then of course the code gets inefficient
because it randomly (random wrt the intent) chooses someone as a
possible ancestor and then blindly tries to construct a path to Des.
If we have a couple of hundred ground facts, the inefficiency could
be prohibitive. After all, a possible Anc fails only after all
his/her descendants have been tried and found wanting (ie not = Des).
Of course we could do some variation of this:
ancestor_descendant(Anc, Des) :- parent_child(Anc, Des).
ancestor_descendant(Anc, Des) :-
nonvar(Anc) ->
(parent_child(Anc, Middle),
ancestor_descendant(Middle, Des)
);
(parent_child(Middle, Des),
ancestor_descendant(Anc, Middle)
).
but now we've used a non-logical test and have semi-duplicated code, etc.
Comments ?
-- John Cugini
------------------------------
Date: Tue, 20 Oct 87 23:09:43 PDT
From: quintus!ok@Sun.COM (Richard A. O'Keefe)
Subject: Another textbook
This one is
@Book(malpas-primer
, Key = Malpas
, Author = "Malpas, John"
, Title = "PROLOG: A Relational Language and its Applications"
, Publisher = Prentice-Hall
, Year = 1987
)
Once again, this is NOT a general review of the book.
There are several things about this book that I think are good,
such as the glossary. Let's briefly comment on that.
He calls compound terms "structures". The word "structure"
is indeed used in logic, but it certainly does not mean a
compound term. The word "structure" is indeed used in
old-fashioned programming, but it doesn't mean a compound term
there either. Instead it means a record, and records have
mutable Fields which are accessed by symbolic name. Compound
terms have immutable Arguments which are accessed by position.
Why use a word which manages to mislead both programmers and
logicians when there is a precise term ready to hand which has
no false connotations?
Yet again, he says that "| is known as the list constructor".
I hope it isn't known as that, because "|" is NOT the list
constructor in most of the Prolog systems Malpas says his book
is relevant to, particularly not in C Prolog, which is the basic
system he worked from. The list constructor is '.', and in
DEC-10 Prolog, C Prolog, and Quintus Prolog, you can say
| ?- op(600, xfy, .).
to make expressions such as
X = a.b.[]
legal. And even if you don't,
| ?- functor([a,b], ListConstructor, 2).
binds ListConstructor = '.'
in those Prologs.
Is this nit-picking? Well, no. Read Ayn Rand's "An Introduction to
Objectivist Epistemology". It is impossible to think clearly about a
topic if your vocabulary about that topic is muddled. Anyone who
believes that "|" is the list constructor is in for a nasty shock when
| ?- functor(List, '|', 2).
fails to construct a list.
Is this NIH syndrome? Well, no. I have several times suggested to
the BSI Prolog group that they should canonise the terminology in John
Lloyd's book, filling in anything else from Robinson's "Logic Form and
Function" or failing that Common Lisp. (The BSI Prolog group are
inventing a new language, so compatibility appears not to be of interest
to them.) If you notice me using poor terminology, please let me know,
and I'll mend my ways. I know that I tend to be rather slipshod about
predicate -vs- procedure, and it's not good enough!
Another good feature of the book is its catalogue of Prolog
implementations. It is one of the few books about real Prolog to tell
you about Turbo Prolog.
There are other good things I could say about this book. So let's
get on with the criticism.
My touchstone for evaluating the quality of a Prolog textbook is to
see what it says about all-solutions predicates. (Don't forget that
part of the point of these two textbook reports is to justify my claim
that Lagache's difficulties with findall&Co are no worse than some
textbooks.)
setof/3 and bagof/3 are not in the index of this book. findall/3,
however, is. Page 338 provide what is described as "source code for a
version of findall". Here is the code.
findall(Element, Query, _) :-
Query,
gettmplist(List),
append(List, [Element], Newlist),
assert(tmplist(Newlist)),
fail.
findall(_, _, List) :-
retract(tmplist(List)),
!.
gettmplist([]) :-
\+ tmplist(_),
!.
gettmplist(List) :-
retract(tmplist(List)),
!.
unique_value_list(Element, Query, _) :-
Query,
gettmplist(List),
( member(Element, List),
assert(tmplist(List))
; \+ member(Element, List),
assert(tmplist([Element|List]))
),
fail.
unique_value_list(_, _, List) :-
retract(tmplist(List)),
!.
Ouch!
It is interesting that this is the only version of findall/3 I have
ever come across which fails when there are no solutions. Suppose that
the dynamic predicate tmplist/1 is initially empty. Then we trace
?- findall(*, fail, List)
Clause 1 calls fail, which fails.
Clause 2 calls retract(tmplist(List)), which fails.
findall/3 fails.
The correction for this, of course, would be to change the last clause
of findall/3 to
findall(_, _, List) :-
gettmplist(List).
and make the corresponding change to unique_value_list/3. Of course,
this version of findall/3 is not steadfast. If you call
?- findall(*, true, [X,Y]).
the second clause of findall/3 will fail, because
retract(tmplist([X,Y]))
will <<correctly>> fail to recognise the clause
tmplist([*])
findall/3 having failed, tmplist([*]) will be left in the data base.
So if we then call findall/3 again in utter disbelief, we'll get the
incorrect answer X = *, Y = *. Try it! The correction for this would
be to make gettmplist/1 steadfast.
gettmplist(List) :-
retract(tmplist(L)),
!,
List = L.
gettmplist([]).
Having fixed two bugs, we are then left with the problem that this
version of findall/3 will not work if calls to findall/3 can be nested.
As indeed they can and should be. This is not the only textbook with
an all-solutions predicate which cannot be nested. I do not understand
this. Why would anyone fail to worry about nested calls to control
structures? Well, we can hack around this bug by temporarily moving
the outer value out of the way.
findall(Template, Generator, List) :-
retract(tmplist(OuterList)),
!,
findall_1(Template, Generator, L),
assert(tmplist(OuterList)),
List = L.
findall(Template, Generator, List) :-
findall_1(Template, Generator, List).
findall_1(Template, Generator, List) :-
/* what findall/3 used to be */
That only leaves us with efficiency problems (I think. I haven't
really been able to stomach testing it.)
One source of inefficiency is the way the list is built up using
append/3. If the final list has N elements, we'll have done
about (1/2)N^2 calls to append. This is in fact pretty much what
naive reverse does. If instead, the list were built up by adding
elements at the front and then reversing the final list, list
manipulation would take O(N) time.
The preferred way of building a list in Prolog is
to calculate L = [L1,...,Ln] do
calculate_list([], LoopVars) :-
ended(LoopVars).
calculate_list([Element|Elements], LoopVars) :-
calculate_next_element(LoopVars, Element),
advance_loop_variables(LoopVars, NextVars),
calculate_list(Elements, NextVars).
Where you can't do this,
calculate_list(List, InitVars) :-
calculate_list([], Rev, InitVars),
reverse(Rev, List).
calculate_list(L, L, LoopVars) :-
ended(LoopVars).
calculate_list(L0, L, LoopVars) :-
calculate_next_element(LoopVars, Element),
advance_loop_variables(LoopVars, NextVars),
calculate_list([Element|L0], L, NextVars).
In some implementations of Prolog, this may be enough to take the
cost down to O(|Size of answer List|) time. But not in any of the
Prolog implementations mentioned by Malpas. What is the reason for
that? If you have a List of size |List| in the data base, and an
Element of size |Element| you want to add to it,
| ?- retract(tmplist(List)),
!,
assert(tmplist([Element|List])).
will cost O(|List|+|Element|) space and time in a structure-sharing
system, and O(2*|List|+|Element|) space and time in a structure-
copying system. retract/1 in effect makes a copy of the clause it
deletes. In a structure-sharing system, this is pretty cheap, at
the price of delaying the reclamation until there are no further
references to any part of the deleting clause. In a structure-copying
system, it takes O(|List|) time and space to build the copy. Some
systems might do better if substantial parts of the clause are ground.
Then assert takes O(|List|+|Element|) time and space to build a copy
of the new term. This has to be done so that any variables in the term
will be properly handled. Again, if substantial parts of the new
clause are ground some systems may do better.
With all these copies going on, the cost of this version of findall/3
is O(length of final result*size of final result). Whew!
If you are going to maintain a stack or an output-restricted deque
in the data base, do it by using
asserta/1 to add items at the head of the deque
assertz/1 to add items at the foot of the deque
retract_first/1 to remove items from the head of the deque.
DON'T try to view the thing as a single "variable" held in a single
clause, because updating that "variable" will be appallingly costly in
nearly every Prolog system.
I don't know where Malpas got this code, or why he chose to
recommend it to his readers rather than the version in Clocksin &
Mellish. It is pretty bad.
Have any Prolog Digest readers any experience with this book,
either learning Prolog from it yourself, or trying to teach a class
with it? What do you think are the particularly good features of
the book? Do you think it matters that the code given in an
appendix for an operation already available in some form in most of
the Prolog systems he cares about is poor? Are there any examples
in the book which you think are particularly helpful?
Final repetition: this is not a general review of the book, and
there are good things in it too.
------------------------------
End of PROLOG Digest
********************