Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!wuarchive!zaphod.mps.ohio-state.edu!mips!prls!pyramid!leadsv!laic!mcguire
From: mcguire@laic.UUCP (James Mcguire)
Newsgroups: comp.lang.prolog
Subject: Re: Arrays in Prolog
Summary: experience using logarithmic arrays
Message-ID: <870@laic.UUCP>
Date: 28 Aug 90 17:57:04 GMT
References: <90239.175243SCHMIED@DB0TUI11.BITNET>
Organization: Lockheed AI Center, Menlo Park
Lines: 56



Thought I'd put in my two cents. I have been generally pleased with the
library(logarr) facility in Quintus (mentioned by Richard O'Keefe).
I have used it many times to implement graph algorithms (strongly connected
components, depth-first spanning forests, etc) on large graphs
(> 1000 nodes with approx 5000 edges). If you're willing to modify the
code, you can make array lookup logarithmic to the base of your own choosing.
Furthermore the arrays are sparse (don't have to pre-allocate a pre-defined
number of array storage positions).

I have also used it to implement what is essentially a non-persistent
property list in Prolog (i.e. can be reclaimed on backtracking).
The first step is to compute a set of persistent integer indices for each
symbol. Given a list of symbols [s1,s2,..], compute an integer key for each 
symbol and assert the created index to the prolog database. When the symbol 
names are pretty stable (hang around a long-time) but attributes describing the
symbol change frequently during computation, I've always found it 
cost-effective to pre-compute persistent integer indices and to store
the attribute's of a given symbol in a non-persistent (stored in a variable) 
property-lists data-structure as such:

%integer_key(?Symbol,?Array_Index_Key)
:- dynamic integer_key/2.
integer_key(symbol1,12) 

%% Update the attribute +Slot of symbol +Symbol to have value +NewValue,
%% where +PropertyListsDB1 is the existing array database containing the 
%% property list of each symbol. ?PropertyListsDB2 is the new array database 
%% reflecting the change to +Symbol's property list.
add_to_property_list(Symbol,Slot,NewValue,PropertyListsDB1,PropertyListsDB2):-
  integer_key(Symbol,Key),          %retrieve Symbol's array index

  aref(Key,PropertyListsDB1,List),  %retrieve the List stored at the
                                    %Key'th index of the array PropertyListsDB1

  modify_property_list(List,Slot,NewValue,NewList), %update Symbol's property
                                                    %list

  aset(Key,PropertyListsDB1,NewList,PropertyListsDB2).%Create a new property
                                                      %lists array database 
                                                      %which
                                                      %contains the change
                                                      %to Symbol's property
						      %list.

    I would still like to see Prolog incorporate a richer set of built-in
non-persistent (not stored in database) variable-based data-types, such as 
hash-tables and arrays. This could be done in a very clean way where the
modification to an existing array/hash-table would be reflected in a newly
introduced variable. This is what is done in Quintus' library(logarr) facility.

----
Jim McGuire
mcguire@laic.lockheed.com
Lockheed AI Center, Menlo Park, Ca, USA.