Merge of the "new ByNeed" branch

[Raphael Collet]

Hi Denys,

The following version defines the semantics of ByNeedFuture.  Let's call
it the "semantic" version of ByNeedFuture.

> >    fun {ByNeedFuture P}
> >       !!{ByNeed fun {$} try {P} catch E then {Value.failed E} end end}
> >    end
> 
> I looked at the actual code in share/lib/base/Base.oz, and I found:
> 
>    ByNeedFuture = proc {$ P X}
> 		     R={Boot_Value.newReadOnly}
> 		  in
> 		     thread
> 			{WaitNeeded R}
> 			try Y=!!{P} in
> 			   % necessary if R has no demanding suspension
> 			   {Boot_Value.makeNeeded Y}
> 			   {Boot_Value.bindReadOnly R Y}
> 			catch E then
> 			   {Boot_Value.bindReadOnly R {FailedValue E}}
> 			end
> 		     end
> 		     X=R
> 		  end
> 
> Isn't this unnecessarily complicated? Why the second read-only?  Could
> you comment this design; that would be very helpful.

The first idea was to create one thread instead of two.  In the semantic
version, '!!' and ByNeed create one thread each.  Second, if {P} returns
a free variable Z, R must be bound to a read-only view of Z.  Otherwise,
the semantics of ByNeedFuture would be broken.  This second read-only is
cheap if {P} returns a value, because !!X immediately returns X if it
determined or failed.

Maybe it is simpler to synchronize on Y before binding R.  The following
avoids the creation of a second read-only, without breaking semantics:

ByNeedFuture = proc {$ P X}
		  R={Boot_Value.newReadOnly}
	       in
		  thread
		     {WaitNeeded R}
		     try Y={P} in
			% necessary if R has no demanding suspension
			{Boot_Value.makeNeeded Y}
			{WaitQuiet Y} {Boot_Value.bindReadOnly R Y}
		     catch E then
			{Boot_Value.bindReadOnly R {FailedValue E}}
		     end
		  end
		  X=R
	       end

> >  - The former implementation of futures will be removed from Mozart.
> >    Maintaining both implementations introduces unnecessary complexity,
> >    and therefore degrades readability of the code.  This decision is
> >    supported by the fact that no performance degradation has been
> >    observed with the new implementation (see below).
> 
> Well... yes and no.  We certainly don't want to keep the old futures
> as they are.  However the performance argument is missing the actual
> point that I discussed before and which is about resources
> (e.g. memory).

The resource problem you mention is only a problem if a program refers
to several thousands of untriggered ByNeedFutures at a certain time.  To
me this is a *big* issue only if some realistic programs (I mean not toy
programs) have that property.  I don't know any such program.

But don't take me wrong.  I fundamentally agree with your point.  I
don't like wasting either ;-)

> The plan that I wish to pursue is as I described previously: to
> eventually replace ByNeedFuture with a resource-optimized
> representation (i.e. one that delays allocation of resources until
> needed).  The wonderful thing about the new foundation is that such an
> optimization becomes very straightforward and semantically clean: what
> is a ByNeedFuture? It is simply a ReadOnly variable with the
> additional twist that, when this variable becomes needed, a
> computation is started (as described by the current implementation in
> Oz).

Let me share similar ideas Kevin and I have.

 - R=!!X currently creates a thread with one statement that propagates
   both the need from R to X, and the value from X to R.  I thought we
   could implement it as a real propagator.  They look quite economical
   in memory.  I already gave it a try, but miserably failed.

 - {ByNeed P X} currently creates a thread with {WaitNeeded X} {P X}.
   Maybe we can create a cheap suspension on X that, whenever X becomes
   needed, creates the actual thread with {P X} on it.

 - {ByNeedFuture P X} could use the same technique as ByNeed above.
   Simply make X a read-only with a cheap suspension that creates a
   thread whenever X becomes needed.

Kevin and I don't think those have to be done for the upcoming release.
Maybe for 1.3.1...

> Of course, that's my itch, and I perfectly understand if you don't
> feel like scratching it :-) I can do that myself.
> 
> >  - Read-only variables (the ones you get with !!X) have been
> >    reimplemented, in a way very similar to former futures.
> 
> but more efficiently/economically using the bidirectional propagator
> trick.

Thanks to you!


Cheers,

raph
-
Please send submissions to hackers at mozart-oz.org
and administriva mail to hackers-request at mozart-oz.org.
The Mozart Oz web site is at http://www.mozart-oz.org/.