PROLOG-REQUEST@SUSHI.STANFORD.EDU (Chuck Restivo, The Moderator) (12/24/87)
PROLOG Digest Friday, 25 Dec 1987 Volume 5 : Issue 99
Today's Topics:
Query - Debugging,
Implementation - termCompare/3,
Theory - Complexity
----------------------------------------------------------------------
Date: 23 Dec 87 01:34:44 GMT
From: munnari!mulga!ysy@uunet.uu.net (Song Yan)
Subject: Declarative Debugging in Non-standard Logic Programming
I am doing some research in declarative debugging in logic
programming, and going to extend the result into the non-standard
logic (temporal logic, modal logic and fuzzy logic) programming. Does
anybody show interest or has anyone done some work in this area? Any
ideas, comments, meta-interpreters are most welcome and appreciated.
Any programs in non-standard logic are also appreciated. If you have
done some work in debugging in standard logic programming, I would be
very interested in conducting correspondence with you.
-- Song Y. Yan
------------------------------
Date: Mon, 14 Dec 87 14:11:38 +1100
From: Jeff Schultz <munnari!mulga.oz.au!jws@uunet.UU.NET>
Subject: NU-Prolog termCompare/3.
This bug was fixed in patch 1.1-1 which was distributed by e-mail in
early November. If you have a version earlier than 1.2 and have not
received the patch, please send me a valid e-mail address.
Only a few tapes with this bug were distributed.
------------------------------
Date: Wed, 23 Dec 87 03:13:09 PST
From: quintus!ok@Sun.COM (Richard A. O'Keefe)
Subject: Complexity
Well, I've just about convinced myself that it can't be done.
It is easy to show that a pure functional language cannot generate
random permutations in O(N) time. The argument is the same as the
proof that sorting by comparison takes O(NlogN) time: there are N!
different permutations, so running the program must supply O(NlogN)
bits, but a single computational step in a pure functional language
can only supply a fixed number of bits. (Let's take a computational
step as being matching one constructor function or applying one
primitive function.) Don't forget that fixnum arithmetic yields a
fixed number of bits, and bignum arithmetic just hides the logarithmic
factor in the arithmetic.
We can give a precise meaning to a computational step in a Prolog
program too. Basically, the cost of a predicate head is proportional
to its size, and the cost of a goal is proportional to its size EACH
time it is executed. Because goals in the body of a clause may be
executed different numbers of times, the cost of a clause is data-
dependent. We charge unit cost for arithmetic. It is possible to
implement functor/3 and arg/3 so that they have constant cost
independent of the size of the term (modulo caveats about the
ultimate unreality of unbounded linear structures in ANY programming
language) though functor/3 is not usually so implemented.
General unification (V1 = V2 where neither is the first occurrence of
a variable) is the joker: the cost of this is data dependent, but it
is not less than unit cost.
There are two ways that you can code some bits: you can code them in
a number, or you can code them in the location of your data. In the
case of permutation generation, N! is too big to code in a fixnum for
all but a few N. (13! is the highest that fits in 32 bits.) So we
have to code a permutation as a distribution of items in a data
structure.
What gives the "unbounded term" languages the illusion of being
able to support O(N) random permutation generation is that there
is a number NMAX such not only can they generate lg(NMAX)
"arithmetic" bits in a single step, they can generate lg(NMAX)
"locational" bits in a single step. Provided N =< NMAX, they
can generate a permutation over [1..N] in O(N) time and space.
(And Prologs with unbounded terms are in this class.)
However, pure Prolog has one more operation than pure functional
languages: it can not only fill in a hole in unit time, it can
fill any (predetermined) number of holes in with the same value
in unit time. Is this enough to make a difference?
So we have a more precise version of the original question:
by exploiting logical variables, is it possible to generate
more than lg(T) "locational" bits in a single step?
I suspect that the answer is no. I'll put it in the form of a
Science Fiction idea, which I'll call for obscure reasons
"The Sansato Hypothesis".
If you have instantaneous matter transmitters
which only work one way
and which destroy themselves after a single use
and have to be placed by rockets (you can't transmit them)
then you're not much better off than if you only have rockets.
More precisely, a civilisation with such means of transport can
only expand twice as fast as one with rockets alone.
It turns out that such matter transmitters ARE good for internal
communication: what you have to do is set up pipelines of rockets
sending matter transmitters to interesting places, so that at any
one predetermined place you only have to wait a day for the next
matter transmitter to arrive, even if it took 1,000 years to get
there.
So there we have it:
there is reason to believe that Prolog can be as efficient as
conventional languages for fixed simple patterns of communication.
we have some idea of what a proof that Prolog cannot generate
permutations with the quasi-asymptotic efficiency of Fortran
might look like.
there is reason to believe that a parallel Prolog MIGHT have
more opportunities for speedup than a parallel functional
language (you have a chance to set up those pipelines).
Is it possible to set up a "systolic" network of FCP processes
which will deliver a stream of permutations with the same delay
that a network of Linda processes would require (whatever that is)?
There's an important point in all of this, even if you aren't
interested in permutations as such. The point is that, just as
designing efficient parallel algorithms is not a matter of taking
sequential algorithms and parallelising them (not always), so
designing efficient algorithms for Prolog is not a matter of taking
Pascal algorithms and turning them into "logic" (not always).
I've actually found the little that I know about parallel algorithms
(the *very* little) helpful in trying to design efficient Prolog
algorithms, and I suspect that I would find that approach still more
helpful in NU Prolog.
There's another interesting point: it isn't being "single-assignment"
which is the problem. Unbounded-term Prologs can (with the aid of !)
get O(N) expected time for this problem, without changing any bindings.
The key is being able to generate lg(K) bits of locational information
by calling arg/3 on a term of arity K. It looks as though there is a
weaker operation than array update which will solve this problem:
can we find a logical specification for it, and how will if perform
with other problems?
PS: it seems I missed a point in the Warren&Maier text. They knew
their findall/3 didn't work, didn't want it to, and said so in the
text. It was the similarity of the name to findall/3 which confused
me.
------------------------------
End of PROLOG Digest
********************