[m-rev.] for review: Add future datatype for concurrent and parallel programming

[Paul Bone]

On Tue, Oct 07, 2014 at 02:36:45PM +1100, Peter Wang wrote:
> > +
> > +:- module thread.future.
> > +:- interface.
> > +
> > +    % future/1 represents a value that is evaluated in a separate thread
> > +    % (using spawn/3).
> > +    %
> > +:- type future(T).
> > +
> 
> I think the description should be more generic and not mention threads.
> Perhaps
> 
>     future/1 represents a value that may yet to be computed.
> 

It's not a lazy value.  It is intended for use with threads, unlike lazy.m.

I propose:

    % future/1 represents a value that may not have been computed yet.  
    % Future values are usually computed by separate threads (using
    % spawn/3).
    %
    :- type future(T).

Note that if you're not using multiple (spawn/3) threads, then there's no
point using futures because wait will block until a value is provided, it
will not force evaluation.

> > +%-----------------------------------------------------------------------------%
> > +
> > +    % Create a new empty future.
> > +    %
> > +:- pred init(future(T)::uo, io::di, io::uo) is det.
> > +
> > +    % Provide a value for the future and signal any waiting threads.  Any
> > +    % further calls to wait will return immediatly.
> > +    %
> > +:- pred signal(future(T)::in, T::in, io::di, io::uo) is det.
> 
> immediately
> 
> What happens if it is signalled multiple times?  Probably throw an
> exception.

Undefined behaviour, don't do it!

I've added a comment to this effect and some code to detect this and throw
an exception if detected.  However, a race can occur preventing the
detection from working and therefore I cannot say that an exception will be
thrown.  So "undefined behaviour" will be the documented behaviour, but
hopefully if anybody tries to do this they'll find out via the exception.

> > +%-----------------------------------------------------------------------------%
> > +
> > +    % Create a future which has the value that the closure, when evaluated,
> > +    % will produce.
> > +    %
> > +:- func future((func) = T) = future(T).
> 
> The implicit spawn should at least be mentioned.
> 
> What happens if the function throws an exception?  I guess the user is
> responsible for catching exceptions and returning them.

Since I've separated futures into two different types (below), it's now easy
to trap exceptions for this type of future and re-throw them when wait is
called.  So, if you create a future with a closure that throws an exception,
that exception will be re-thrown out of the call to wait.

> It might be worth differentiating the two types of futures by a type
> parameter.

Okay, I had considered that and wondered what other people thought.  I'll go
ahead and do that.

> > +
> > +    % Wait is pure because it always returns the same value for the same
> > +    % future (if it terminates).
> > +    %
> > +:- pred wait(future(T)::in, T::out) is det.
> > +:- pragma promise_pure(wait/2).
> > +
> > +wait(Future, Value) :-
> > +    Future = future(MReady, Wait, MValue),
> > +    impure get_mutvar(MReady, Ready),
> > +    (
> > +        Ready = ready
> > +        % No wait necessary
> > +    ;
> > +        Ready = not_ready,
> > +        % We need to wait, this will probably block.
> > +        impure wait(Wait),
> > +        % Signal the semaphore to release the next waiting thread.
> > +        impure signal(Wait)
> > +    ),
> > +    impure get_mutvar(MValue, Value).
> 
> Is it not possible that you see Read = ready but the old (uninitialised)
> value of MValue?  I expect futures will usually be read exactly once so
> the optimisation seems unnecessary.

You're right.  It's easily fixable bo moving the write to Ready after the
signal(Wait) as the signal is a memory fence.  This will ensure that the
write to MValue will always be visible before or at the same time as the
write to Ready.


> So, we would have lazy(T), mvar(T), future(T) with three different
> interfaces, and mutvars acting as unsynchronised mvars with another
> interface.

Yes, each has different semantics even though they seem similar.


-- 
Paul Bone