Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!know!zaphod.mps.ohio-state.edu!rpi!bu.edu!snorkelwacker!ira.uka.de!fauern!tumuc!guug!ecrc!joachim
From: joachim@ecrc.de (Joachim Schimpf)
Newsgroups: comp.lang.prolog
Subject: Re: Arrays in Prolog
Keywords: value trailing
Message-ID: <1403@ecrc.de>
Date: 27 Sep 90 16:20:09 GMT
References: <1238@ecrc.de> <1990Sep19.075314.14372@irisa.fr>
Sender: news@ecrc.de
Reply-To: joachim@ecrc.de (Joachim Schimpf)
Organization: European Computer-Industry Research Centre, Munich
Lines: 68

In article <1990Sep19.075314.14372@irisa.fr> ridoux@irisa.irisa.fr (Olivier Ridoux) writes:
>From article <1238@ecrc.de>, by joachim@ecrc.de (Joachim Schimpf):
>>  
>>  ...
>> Using destructive and value-trailed updates, all operations can be
>> performed in O(1) time. Without, the only choice seems to be using
>> open-ended lists, which means all operations are O(length).
>
>There is another solution which involves no value-trailing.  The idea is to 
>have "attributed variables".
>
>...
>(2) It can be seen as a reversibly modifiable term.  In this case the 
>attribute is the current value of the term.  To modify the term is to bind 
>the attributed variable to a new value.  If the term is meant to remain
>modifiable, the new value must be represented by a new attributed variable.
>
>...
>So all operations can be performed on O(1) time with no value-trailing.

I would like to point out that there is no such thing as
"(virtual) modification in O(1) without destructive assignment".
Basically, your modifiable data structure is still a list, where
the current value is stored at the end, together with a free place
for adding further modifications. 
A change history will therefore look like this (using infix dots): 
 
X = value1 . T1
X = value1 . value2 . T2			Trail: T1
X = value1 . value2 . value3 . T3		Trail: T2, T1
X = value1 . value2 . value3 . value4 . T4	Trail: T3, T2, T1
 
For modification and update, the list has to be traversed to the end.
This can be speeded up by
 
- hiding it in the dereferencing loop (done by MALI and SICSTUS)
- "shunting" the chain from time to time (done by MALI)
 
When you claim O(1) updates, do you have in mind that the update chains
cannot grow indefinitely because the garbage collector will shorten them ?
Then, still, this scheme is likely to be much slower than destructive
assignment (value-trailed if necessary), which could be pictured as follows
(as above, the trail entries need only be there if a choicepoint has been
created since the previous modification):

X = value1
X = value2	Trail: X=value1
X = value3	Trail: X=value2, X=value1
X = value4	Trail: X=value3, X=value2, X=value1

The current value is always immediately accessible, the change history
is where you need it, i.e. on the trail. The trail could be collapsed
by the garbage collector, but this is not essential for access speed.

What Mats Carlsson has mentionned is in fact a compromise, i.e. taking
advantage from destructive assignment if no trailing is needed, and
building up the chain otherwise.

>Attributed variables are available in the MALI memory (S. Le Huitouze 
>PLILP'90).  A similar object, called "meta-structure" is described by 
>U. Neumerkel (META'90).

I agree with Mats Carlsson that his suspension structures are essentially
the same.
--
Joachim Schimpf
ECRC, Arabellastrasse 17, D-8000 Munich 81, West-Germany
joachim@ecrc.de  (from USA: joachim%ecrc.de@pyramid.com)