PROLOG-REQUEST@SUSHI.STANFORD.EDU (Chuck Restivo, The Moderator) (12/11/87)
PROLOG Digest Friday, 11 Dec 1987 Volume 5 : Issue 96
Today's Topics:
Query - Interfaces,
Theory - Impediments
----------------------------------------------------------------------
Date: 30 Nov 87 21:54:49 GMT
From: nosc!humu!uhmanoa!uhccux!todd@sdcsvax.ucsd.edu
Subject: Arity/Prolog and Microsoft C 5.0?
Has anyone successfully linked a Microsoft C (version 5.0) function
to Arity/Prolog 4.0? It seems like a lot has changed since Arity
wrote the "Building Arity/Prolog Applications" handbook. For example,
the handbook talks about an Arity supplied file called "arityc.h".
However, all I can find is "apctype.h" on my disks. It also seems that
some of the MSC compile options Arity says I must use to compile the C
code no longer exists in MSC version 5.0. Also, the Arity handbook
shows a C function called 'getint_c' being used to translate (I guess?)
parameters passed from Prolog to the C function. However, I can't
figure out where this function is supposed to come from.
-----------------------
Date: Tue 8 Dec 87 20:19:31-EST
From: Paul G. Weiss <PGW@XX.LCS.MIT.EDU>
Subject: Arity/Prolog and Msft C5.0
C5.0 works fine with A/P V4.0. The file apctype.h is the correct file,
arityc.h is a manual bug. Feel free to use /AL to compile (this also
works for C4.0). A/P V5.0 will support all the C models.
As for getint_c, it is provided in the ARITY.LIB. You are right in
that it is needed to translate parameters from Prolog to C. A/P V5
will do away with the need for this as it will allow you to declare
your C function and the types of its arguments from within your Prolog
source file.
------------------------------
Date: 8 Dec 87 20:19:13 GMT
From: iscuva!randyg@uunet.uu.net (Randy Gordon)
Subject: Re: Arity/Prolog and Microsoft C 5.0?
I just put up an example of linking arity prolog and C (version 4)
with the plink linker on the Arity Bulletin Board. Plink allows you
both multiple overlays and multiple overlay areas. With version 4
Arity, you have to add a few "class" statements to your plink command
file. (Not necessary using the microsoft linker).
In a couple of weeks version 5 of Arity Prolog will be out and the C
interface will be much cleaner(getint, etc dissapears... and you can
call prolog from C!)
------------------------------
Date: Wed, 9 Dec 87 17:45:36 PST
From: quintus!ok@Sun.COM (Richard A. O'Keefe)
Subject: A Theoretical Question
I'll start by briefly ignoring Sanjai Narain's question: the
super-exponentiality of Presburger Arithmetic has no more (and no less)
relevance to Prolog than to Lisp or ADA. We have known that resolution
is super-exponential since the mid-seventies. (I first saw this in one
of the Proc.Conf. Automata & Switching Theory volumes; sorry, don't
recall which.) A Prolog program to solve PA problems will be affected
by the result, as will a Prolog program to handle general resolution.
But so will a Lisp or ADA program for the same tasks.
Now for my theoretical question.
There is a significant difference between languages like ML and
Prolog and pure Lisp on one hand and languages like C and ADA and
the other FORTRAN look-alikes on the other hand. Assignment to
scalar variables is of no importance; what matters is that the
FORTRAN family has assignment to array elements, and the (pure) Lisp
family hasn't. (Yes, I *know* there are versions of Prolog which
have some sort of array facility. I am NOT asking about that.)
Basically, in order to maintain an array of N elements, a pure
language with bounded tuples of width T (pure Lisp: T=2, ALS Prolog:
T=14, some versions of C Prolog: T=100, others: T=200, Quintus Prolog:
T=255, DEC-10 Prolog: T>2000, ...) has to maintain a tree of
ceil(log(T,N))
levels. If you are accessing the elements of such a collection in
order, it takes unit time per element, and the same if you are building
a new collection in sequence. If you are accessing or constructing
a collection in other orders, it will usually cost a factor of
ceil(log(T,N)) per element. (Prolog can construct new collections
more cheaply than other declarative languages, thanks to the logical
variable. Turbo Prolog pays a high price here.)
For some applications, this doesn't matter. For example, the
Fast Fourier Transform on N numbers costs O(N.log(2,N)) time in a
member of the Fortran family. It turns out to be easy to write it
to take O(N.log(2,N)) time in a member of the (pure) Lisp family too.
Similarly, queue operations can be done in O(1) time both families.
But what about generating random permutations? Suppose we are
given a "sufficiently long" list of "pseudo-random" numbers, and a
data structure representing a collection, and want a new data
structure representing a permutation of the input.
QUESTION: Is there a data structure and algorithm such that
a permutation of N elements can be constructed in
O(N) time in a member of the (pure) Lisp family;
specifically in Prolog?
If N is bounded above by T, it is trivially easy.
A T-way divide-and-conquer yields an O(N.log(T,N)) algorithm,
for which "sufficiently long" means O(N.log(T,N)) random numbers.
The obvious attach-N-random-numbers-and-do-a-keysort is O(N.log(2,N)).
Can it be done in time O(N) for N >> T?
There is a sharper form of the question. Suppose we are given a
list whose elements form a permutation of {1...N}. That is, instead
of a "sufficiently long" list of random numbers, we have exactly N
integers.
QUESTION: Is there a data structure and algorithm such that
a permutation given as a list of N elements can be
applied in O(N) time, in ... Prolog?
This can certainly be done in O(N.log(T,N)) time by a T-way
divide-and-conquer.
QUESTION: If these things can't be done in linear time,
what bound can be proven?
I assume that tuples of size 0<=k<=T can be constructed in time O(k),
that the 1<=j<=k element of a tuple can be read in O(1) time, and
that an element which has not previously been set can be set in O(1)
time. I further assume that arithmetic operations cost O(1) time.
Now, for most practical purposes, O(N.log(200,N)) is nearly as
good as O(N): for any problem small enough to fit in a modern
computer, log(200,N) < 4. But coding a 200-way divide-and-conquer
is rather unpleasant. The Quintus routine random_permutation/2
actually takes O(N.log(2,N)) time because it was *so* much easier
to write. Perhaps someone can discover an O(N) method which is
simple as well as efficient?
------------------------------
End of PROLOG Digest
********************