Path: utzoo!attcan!uunet!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Arrays in Prolog
Message-ID: <3629@goanna.cs.rmit.oz.au>
Date: 28 Aug 90 05:14:22 GMT
References: <90239.175243SCHMIED@DB0TUI11.BITNET> <9653@bunny.GTE.COM>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 77

In article <9653@bunny.GTE.COM>, tomf@GTE.COM (Tom Fawcett) writes:

> I too have needed to use arrays in Prolog, and have been generally
> dissatisfied with what I've found.  I'm using Quintus Prolog, which has two
> separate library files that implement arrays in different ways.  Neither have
> constant-time access and update, and the one that claims to be better requires
> that you retract, modify, and re-assert the array for every modification.

I don't understand the reference.  The Quintus library contains, apart
from library(vectors), two packages: library(arrays) and library(logarr).
Here's how an old copy of library(arrays) starts:

%   Package: arrays
%   Author : Richard A. O'Keefe
%   Updated: 10/13/89
%   Defines: updatable arrays in Prolog.

%   Adapted from shared code written by the same author; all changes
%   Copyright (C) 1987, Quintus Computer Systems, Inc.  All rights reserved.

/*  The operations in this file are fully described in an Edinburgh
    Department of Artificial Intelligence Working Paper (WP-150) by
    me, entitled "Updatable Arrays in Prolog", dated 1983.

    The basic idea is that these operations give you arrays whose
    elements can be fetched AND CHANGED in constant expected time
    and space.  This is an example of logic hacking, rather than
    logic programming.  For a logical solution (with O(lgN) cost)
    see library(logarr) by David Warren and Fernando Pereira.

Here's how library(logarr) starts:

%   Package: logarr
%   Authors: Mostly David H.D. Warren, some changes by Fernando C. N.  Pereira
%   Updated: 11/10/87
%   Purpose: Extendable arrays with logarithmic access time.

NIETHER of these packages does any asserting or retracting, nor does
either of the packages require or recommend that *you* do any asserting
or retracting.  And library(arrays) specifically DOES claim to provide
constant-time access and update.  (That's actually *average* time; the
worst case for any operation is O(N), but the average is O(1).)
 
> When asking about this deficiency, the reaction I've gotten is that you
> shouldn't need to use arrays - there is no logical interpretation of
> destructive modifications to a data structure.  I suppose this is generally
> true; for most applications there is a more natural and elegant way to
> accomplish what you want without resorting to arrays.  Nevertheless, for some
> applications Prolog's indexing mechanism simply isn't fast enough, and you
> need the speed of arrays.

Please, be specific.  What precisely is it that you are trying to do?
Prolog's indexing is simply irrelevant to applications where you would
have used arrays;  arrays are dynamic data structures which you would
pass around, they have no more to do with the data base than lists have.
Pretty well anything you might have done with Lisp-style arrays can be
*expressed* the same way using library(arrays) or library(logarr); the
remaining question is speed.  Trees (such as 3+4 trees) are surprisingly
fast, and make multi-version structures easy to implement.

> The solution I've settled on is to use a library file provided by Quintus
> called vectors.pl, which allows you to create and access single dimension
> arrays of arbitrary length.  I haven't looked closely at the code, but it uses
> Unix's malloc and free routines to do storage management inside Prolog's heap.
> The package was designed to be used to pass data between C and Prolog, and not
> be a general array management package, but it seems to do the job.  It should
> be fairly easy to write one yourself.

Thanks for the kind words.  I wrote library(vectors) so that I could pass
arrays to Fortran, not C.  It isn't as fast as it could be; but of course
the answer to that is that *if* enough customers identified that as being
of importance to them, a prudent company might build the facility in, but
if no-one appears to be using the scheme that is provided, a prudent
company would leave well enough alone.

-- 
The taxonomy of Pleistocene equids is in a state of confusion.