🚀 go-pugleaf

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.