Path: utzoo!attcan!uunet!mcsun!inria!irisa!ridoux
From: ridoux@irisa.irisa.fr (Olivier Ridoux)
Newsgroups: comp.lang.prolog
Subject: Re: Arrays in Prolog
Message-ID: <1990Sep19.075314.14372@irisa.fr>
Date: 19 Sep 90 07:53:14 GMT
References: <1238@ecrc.de>
Sender: news@irisa.fr
Organization: IRISA, Rennes (FR)
Lines: 69
Originator: ridoux@calypso.irisa.fr

From article <1238@ecrc.de>, by joachim@ecrc.de (Joachim Schimpf):
> In article <1990Sep11.150245.26833@sics.se> matsc@sics.se (Mats Carlsson) writes:
>>In article <1032@ecrc.de> micha@ecrc.de (Micha Meier) writes:
>>   Value trailing is necessary to implement
>>   efficiently coroutining systems (yes, I know that it is possible
>>   without, but not fast enough). It was already present in MU-Prolog.
>>
>>This is an interesting claim.  Could you provide some arguments for
>>why it is that coroutining systems become so much slower without value
>>trailing?
>  
> The main advantage - compared to a scheme as presented in Mats
> Carlsson's ICLP 87 paper - is a more efficient handling of updates
> to the list of delayed goals associated to every suspending variable.
>  
> In a typical delay-tests-and-generate application it is quite common
> to have hundreds of goals delayed on only a few variables, so these
> lists can become rather long.
>  
> 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".  They behave like variables but have an attribute
that is a term which may in turn be constructed with attributed variables.  
The attribute is accessible when and only when the attributed variable is 
free.  When bound the attributed variable is transparent (just like a regular 
variable).  This means that it is dereferenced upon every encounter.  

An attributed variable can be seen in to ways.
(1) It can be seen as a decorated variable.  In this case the attribute is
meant to represent a constraint, a type, a domain etc.  Anything that can been
interpreted as a descriptor of what is the variable or how to use it will do.
(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.

Coroutining uses the two ways.  The suspending variable is decorated by the
decriptor of the delayed goals (first vision).  The descriptor of the delayed
goals must be a modifiable structure (second vision) in order to add 
efficiently new delayed goals.

So all operations can be performed on O(1) time with no value-trailing.

>>Value trailing seems to have a rather high price: the trail
> It is not necessary to use value trailing even for normal variables.

The regular trail is used for both types of variable.

> A point to mention, however, is that garbage collection becomes
> somewhat more difficult in the presence of value trailing.

Attributed variables add no difficulty for garbage collection.  The garbage
collection of attributes is a side effect of the "variable shunting" (also
known as "variable collapsing").  Variable shunting is the ability to recognize
that no choice-point exists in which a given variable is free.  In other term,
the variable is either bound or does not exist.  Such a variable can be
physically replaced by its binding value in all its occurrences.  Since an
attribute is accessible only when its variable is free, it is garbage collected
with the variable.

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).  Meta-structures are associated to an escape mechanism
that allows to hook a user defined unification procedure in the system.

Olivier Ridoux