Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!spool.mu.edu!munnari.oz.au!bruce!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Array implementation in (PDC) Prolog
Keywords: array, PDC Prolog
Message-ID: <6476@goanna.cs.rmit.oz.au>
Date: 24 Jun 91 09:11:53 GMT
Article-I.D.: goanna.6476
References: <858@watson.albany.edu>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 52

In article <858@watson.albany.edu>, stst@cs.albany.edu (Stefan Strack) writes:
> Prolog is great for recursive data-structures, such as lists, trees, etc..
> Sometimes, though, I find myself needing a simple one-dimensional array.
> What I mostly resort to is to implement an array as a collection of indexed
> facts, such as:
> 
>         array(0,Contents1).
>         array(1,Contents2).
>         ...
> 
> Array-updates are implemented as assert/retract operation. The nice thing 
> about this implementation is that accesses by index and by contents are 
> possible. The bad news is that access speed is inversely related to the 
> "size" of the array.

Let me tell you the *really* bad news.  In other Prologs the access time
is *not* related to the size of the array.  In every commercial Prolog I
have ever had my hands on (with the exception of one, running on PCs and
Macs), a dynamic predicate is accessed via a hash table.  If you cannot
assert, retract, and access such facts in essentially constant time,
complain to your vendor.  In the case of Turbo/PDC, demand that they give
you something as efficient as Prolog.

> So, what I am looking for is a better implementation of an array in Prolog.

There's a paper of mine from the Department of Artificial Intelligence at
the University of Edinburgh which shows how array element access and update
can be done in constant _amortized_ time using ordinary Prolog terms.  I'm
not sure if it's doable in Turbo/PDC Prolog, I never did quite grasp how to
use 'reference's in that language.  Don't bother asking me for a copy of
that paper, I haven't any.

> [Idea of using an external data base.]
> A B+ tree would be used to maintain the indices in ascending order.
> ... the keyword is "(largely) array-size independent access-time".

But a B+ tree provides you only LOGARITHMIC access and update time.
Why not use an internal tree?  It will still be logarithmic, but the
constant factor will be a heck of a lot lower.  You might try using
the N+K trees described in "The Craft of Prolog", tuning N and K for
your application.

> In case you are asking what kind of program I am writing: it's an
> implementation of A.K.Dewdney's "Core War" game, and I am looking for a good
> representation of the Core memory array.

I would not have thought Turbo/PDC Prolog was the language of choice
for that application.  If you want a logic programming language which
*would* make sense for that application, try Trilogy.

-- 
I agree with Jim Giles about many of the deficiencies of present UNIX.