Path: utzoo!attcan!uunet!decwrl!sdd.hp.com!usc!snorkelwacker!bloom-beacon!eru!hagbard!sunic!sics.se!sics.se!matsc
From: matsc@sics.se (Mats Carlsson)
Newsgroups: comp.lang.prolog
Subject: Re: Arrays in Prolog
Message-ID: <1990Sep25.124816.12993@sics.se>
Date: 25 Sep 90 12:48:16 GMT
References: <1238@ecrc.de> <1990Sep19.075314.14372@irisa.fr>
Sender: news@sics.se
Organization: Swedish Institute of Computer Science, Kista
Lines: 68
In-Reply-To: ridoux@irisa.irisa.fr's message of 19 Sep 90 07:53:14 GMT

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):
   > 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.

This is in fact exactly the same scheme as I described in my ICLP'87
paper.  What may have confused people is that the paper introduces so
called "suspension structures", but they are really the same thing as
attributed variables.

An optimization of step (2) above, implemented in SICStus, is that
when the term to be modified was created more recently than the
youngest choicepoint, the term itself (the "attribute") can be
destructively modified, instead of binding the variable to a new
attributed variable.

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

That's my point too.  There is one snag, however.  If the optimization
of step (2) cannot be applied, it can happen that a very long chain of
variable bindings is created, turning accesses to the constrained
variables into O(N) operations.  This potential problem does not occur
in a value-trailing scheme.  Variable shunting can sometimes mitigate
the problem too.
--
Mats Carlsson
SICS, PO Box 1263, S-164 28  KISTA, Sweden    Internet: matsc@sics.se
Tel: +46 8 7521543      Ttx: 812 61 54 SICS S      Fax: +46 8 7517230