Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!mcsun!prlbcom!kulcs!gerda
From: gerda@kulcs.uucp (Gerda Janssens)
Newsgroups: comp.lang.prolog
Subject: Re: Re : incrementing values
Message-ID: <1837@kulcs.kulcs.uucp>
Date: 12 Feb 90 10:03:50 GMT
Reply-To: gerda@kulcs.UUCP ()
Organization: Katholieke Universiteit Leuven, Dept. Computer Science
Lines: 37


In <703@cluster.cs.su.oz> andrewt@cluster.cs.su.oz (Andrew Taylor) replies :
> >The efficiency of 'X1 is X0 + 1' can substantially be increased
> >if at compile time we known that it is actually destructive assignment
> >and that we can safely reuse the memory cel of X0 for X1.
> >This kind of information can be derived by doing global analysis of the 
> >PROLOG program. ...

> I don't think this is relevant.  Expressions like this can be compiled
> efficiently,  re-using memory-locations/registers without global
> analaysis for  compile-time garbage collection. This analysis
> becomes useful when compund terms are involved.


Actually, I was referring to the space efficiency of the 'X1 is X0 + 1' 
solution. In order to justify the impact of global analysis for compile-time 
garbage collection, we need the context in which the  'X1 is X0 + 1' expression
occurs.
 
1)
	 p(..) :- ...
	 p(X0) :- X1 is X0 + 1 , p(X1).
As X1 is a temporary variable, it is never stored in a memory cel (on the 
stack or on the heap).  Obviously, in this case does not benefit from the
above kind of global analysis.
(Observe that we can only safely reduce 'X1 is X0 + 1' to an increment if we 
know that X0 is an integer.  Therefore we need 'type'-information derivable
by global analysis)

2)
	p( f(X0), f(X1)) :- X1 is X0 + 1 .

Whether we can reuse the memory of the structure 'f(X0)' for 'f(X1)' is 
determined by the information provided by the global analysis for compile-time
garbage collection :  if the second argument of the call is free and the first
argument is known to be DEAD, the structure 'f(X0)' can be reused for 'f(X1)'.
Therefore, we need to overwrite 'X0' by 'X1'.