PROLOG-REQUEST@SUSHI.STANFORD.EDU (Chuck Restivo, The Moderator) (08/02/87)
PROLOG Digest Tuesday, 4 Aug 1987 Volume 5 : Issue 54
Today's Topics:
Implementation - Naive Reverse,
Puzzle - Riddle Summary,
Terminology - Direction
----------------------------------------------------------------------
Date: 31 Jul 87 15:24:53 GMT
From: Richard Tobin <mcvax!ukc!its63b!aiva!richard@seismo.css.gov>
Subject: Naive Reverse
A logical inference is a succesful unification with the head if a
clause.
append([], L, L)
requires one logical inference.
append([X|L1], L2, [X|L3])
requires one logical inference plus those required for append(L1, L2, L3).
Writing a(N) for the logical inferences required for append with a
first argument of length N, we have
a(0) = 1
a(N) = 1 + a(N-1)
so ('trivially')
a(N) = N+1.
nairev([], [])
requires one logical inference.
nairev([X|Xs], Zs)
requires one logical inference plus those required for nairev(Xs,Ys),
plus those required for append(Ys, [X], Zs).
Writing n(N) for the logical inferences required for reversing a list of N
elements, we have
n(0) = 1
n(N) = 1 + n(N-1) + a(N-1)
= N+1 + n(N-1) since a(N-1) is N
= N+1 + N + n(N-2) expanding n(N-1)
= N+1 + (N-1)+1 + ... + (2-1)+1 + n(2-2)
= N+1 + N + ... + 2 + 1
= (N+1)(N+2)/2 as is well known (:-)
You could do the last bit by induction if you wanted to be rigorous.
In particular, n(30) = 496.
-- Richard Tobin
Edinburgh University
------------------------------
Date: 31 Jul 87 03:14:55 GMT
From: Lee Naish <uunet!munnari!mulga!lee@seismo.css.gov>
Subject: Prolog riddle summary - (nf)
Without tail recursion optimization there will be N stack frames in
use after the Nth number has been returned. ie O(N).
Its true that in simple implementations there will be N copies of X
around but unless the implementation is extremely brain damaged, all
the copies will be pointing directly to the original variable, not
arranged in a chain of length N. To get the next solution, only the
top stack frame is changed. ie. space is O(N) but time (dereferencing
and manipulating the stack) is O(1) to get the next solution and
therefore O(N) to get N solutions.
Off hand, I cant think of how compilation techniques can improve time
complexity, though there is a factor of a few hardware-years.
-- Lee Naish
------------------------------
Date: 31 Jul 87 07:23:04 GMT
From: Harald Sondergaard <uunet!munnari!harald@seismo.css.gov>
Subject: Terminology
Terminology is certainly an important issue and it is true that we
could need some clarification. The attempt by Chris Moss to start a
discussion is thus praiseworthy. In fact it is guaranteed to succeed
since the draft posted is sufficiently vague to create a heated
debate.
It seems that the attempt is premature. If a group is working on this
under the auspices of BSI, one would expect that it would like to put
off a presentation of its work to a wider audience until the draft was
found reasonably well-balanced, coherent and finished.
A rationale and a statement of purpose would seem to be minimal
requirements for debaters. Who are the addressees of this standard?
Prolog novices? Researchers in programming languages? I would like to
be more constructive, but without a rationale it is a bit difficult.
Following are some more or less specific comments to the draft:
General
Basically, much more precision is needed. As it stands, "Definitions" is
a grossly misleading heading. Also, well established term from logic
programming should be adopted. Lloyd's book by now serves more or less as
a standard, and it would be nice if there were to be no conflicts between
this book and the BSI draft [Lloyd 1984]. In particular, "atom" should be
given the meaning of "atomic formula". (Note that a second edition of
Lloyd's book is due to appear this year, and there are some changes in
terminology as compared to the first edition).
Substitutions
The idea of substitutions being mappings is fine, but note that this is
not in agreement with [Lloyd 1984]. In any case, the fact that substitutions
(apparently) are not assumed to be idempotent causes all kinds of problems.
For instance, is the continual "repeated application" of a substitution
supposed to terminate? Or does {x/f(x)} unify {x,f(x)} ("to unify")? On a
conceptual level, all substitutions generated by unification are idempotent
so why not use the fact to simplify definitions? (Admittedly the set of
idempotent substitutions is not closed under composition, but this never
causes problems for Prolog semantics). It is not stated what is meant by a
minimal substitution ("most general unifier"), and the reader may wonder
what a minimal mapping is. Indeed, if one allows for the lack of idem-
potence, there is no "unique minimal substitution" (under the ordering
we normally assume for substitutions). And in the general case, uniqueness
only holds modulo consistent renaming of variables.
The authors of course know this well, but they should keep in
mind that readers probably do not.
Issues of reference
It is suggested that matters of syntax and of semantics are more carefully
distinguished. It is unclear what it means for a literal (a syntactic
entity) to be "known to be true" ("fact"). Or what it means to "define a
predicate" which is in turn explained as an atom and a natural number
("procedure"). Indeed, the notion of "truth" is never clarified. A good
device for emphasizing the difference between phrases in the language
and what they denote is the term "expression". For instance it would be
more natural to say that nil is a list expression that can denote any
empty list, rather than define lists to be purely syntactic objects.
Miscellaneous
-------------
In the definition of a ground term, "uninstantiated" should be dropped.
It is not clear what "top level" means. Is a "variable substitution"
anything but a substitution ("query")? To "consult" does not sound
natural for reading and storing.
[Lloyd 1984]
Lloyd, John W., Foundations of Logic Programming, Springer-Verlag 1984
-- Harald Sondergaard
University of Copenhagen
------------------------------
End of PROLOG Digest
********************