Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!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: <1990Sep13.071715.4852@sics.se>
Date: 13 Sep 90 07:17:15 GMT
References: <90239.175243SCHMIED@DB0TUI11.BITNET>
	<1990Sep11.150245.26833@sics.se> <1990Sep12.170553.14414@cl.cam.ac.uk>
	<3996@bingvaxu.cc.binghamton.edu>
Sender: news@sics.se
Organization: Swedish Institute of Computer Science, Kista
Lines: 32
In-Reply-To: kym@bingvaxu.cc.binghamton.edu's message of 13 Sep 90 04:26:36 GMT

In article <3996@bingvaxu.cc.binghamton.edu> kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) writes:
   In article <1990Sep12.170553.14414@cl.cam.ac.uk> ksh@cl.cam.ac.uk (Kish Shen) writes:
   \\\
   >Perhaps I am showing my ignorance, but can you not have a "special trail" to 
   >store the those trailing that need value trailing? This is what I am doing for
   >my own work with implementing dependent and-parallelism in Prolog -- I have a
   >special trail which  grows in the opposite direction to the normal
   >trail, towards
   >the normal trail. This means that you only pay for the cost of value
   >trailing for
   >those variables that need to use it. Am I missing something? 

A comment to Kish's note: Presumably your scheme requires an extra
"special trail pointer" register and a corresponding slot in every
choicepoint.  This means extra work when creating choicepoints and at
backtracking.  At backtracking you would also need to check whether
there are special trail items to untrail.

   Although the trail _can_ grow to twice the size using naive value
   trailing the cases where values _are_ trailed (and I don't have any
   figures on this to hand on how _often_ this happens) can be ``special 
   cased''. I prefer the using a single bit in the trail entries (you come 
   across them during backtracking in sequence anyway, right)? Probably 
   not too portable `tho.

In Kym's scheme you would have to watch out for the magic bit in every
trail entry.  This means extra work even if there are no value trail
entries at all.
--
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