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

[Julien Fischer]

Hi Paul,

On Thu, 9 Oct 2014, Paul Bone wrote:

> Add future datatype for concurrent and parallel programming

s/datatype/data type/

>
> library/library.m:
> library/thread.future.m:
> library/thread.m:
>    Add new future standard library module.
>
> NEWS:
>    Announce the new addition.
>
> library/thread.semaphore.m:
>    Add an impure interface to thread.semaphore.m.  Semaphores are used to
>    implement our other concurrency primatives and an impure interface can

s/primatives/primitives/

>    often be useful to implement things such as futures, which don't require
>    IO state threading.  The impure interface predicate names are prefixed
>    with "impure_" an existing impure function is now marked as depprecated.

s/an/and an/

s/depprecated/deprecated/

> library/thread.mvar.m:
>    Conform to changes in semaphore.m.
>
> benchmarks/progs/mandelbrot/mandelbrot.m:
>    Add future example to mandelbrot benchmark.

...

> diff --git a/NEWS b/NEWS
> index 751af65..b37a4f3 100644
> --- a/NEWS
> +++ b/NEWS
> @@ -24,8 +24,9 @@ Changes to the Mercury standard library:
>   highly efficient set implementation for fat sets.  This module is a
>   contribution from Yes Logic Pty. Ltd.
>
> -* We have added a module that implements barriers for concurrent
> -  programming.  This module is a contribution from Mission Critical IT.
> +* We have added two new modules for concurrent programming.  They implement
> +  barriers and futures respectively.  These modules are contributed by
> +  Mission Critical IT.

I suggest something of the form:

    We have added two new modules for concurrent programming: thread.barrier
    and thread.future.
    The barrier module provides ....
    The future module provides ....
    These modules were contributed by Mission Critical IT.

The rationale for this is that the NEWS entry should at least say *what* the
names of the new modules are.

...

> new file mode 100644
> index 0000000..fde780d
> --- /dev/null
> +++ b/library/thread.future.m
> @@ -0,0 +1,282 @@
> +%-----------------------------------------------------------------------------%
> +% vim: ft=mercury ts=4 sw=4 et
> +%-----------------------------------------------------------------------------%
> +% Copyright (C) 2014 The Mercury Team.
> +% This file may only be copied under the terms of the GNU Library General
> +% Public License - see the file COPYING.LIB in the Mercury distribution.
> +%-----------------------------------------------------------------------------%
> +%
> +% File: thread.future.m.
> +% Authors: pbone.
> +% Stability: low.
> +%
> +% This module defines a future data type for parallel and concurrent
> +% programming.

I suggest:

    This module defines the data type future/1 which is useful for parallel
    and concurrent programming.

> +% A future represents a value that might not exist yet.  There are two
> +% styles of futures.

s/styles/kinds/

Also, you don't say what the two kinds are here.  I suggest:

    There are two kinds of future: <description of type 1> and <description of type 2>.

>  A future can be set exactly once, but can be read a
> +% number of times.

s/a number/any number/


> This allows the implementor to use a more efficient
> +% algorithm than for mvars.

What does that mean? The implementor of futures (i.e. you) or the user?

> +% There are two ways to use futures.  The first is to create a future,
> +% and supply its value as separate steps.  This is the most flexible way

s/as separate steps/separately/

> +% but requires use of the IO state:

s/IO state/I\/O state/

> +%
> +%  First:
> +%    future(Fut, !IO),


s/Fut/Future/

> +%
> +%  Then in a separate thread:
> +%    signal(Fut, Value0, !IO),
> +%
> +%  Finally, in the original thread:
> +%    wait(Fut, Value, !IO),
> +%
> +% This is flexible because a thread can do more than provide a single future
> +% value.  It can provide many future values or use any other concurrency
> +% feature such as mvars or channels, or do any IO operation.

s/IO operation/I\/O operation/

> +%
> +% The alternative is to create the future and supply a function which when
> +% evaluated will produce the value.  This is pure (and similar to a lazy
> +% value) and therefore does not require the IO state.

s/IO state/I\/O state/

>   The spawning of the
> +% thread is done on behalf of the caller.
> +%
> +%  Just do:
> +%    Future = future(SomeFunction),
> +%    ... do something in the meantime ...
> +%    Value = wait(Future).
> +%
> +%-----------------------------------------------------------------------------%
> +%-----------------------------------------------------------------------------%
> +
> +:- module thread.future.
> +:- interface.
> +
> +%-----------------------------------------------------------------------------%
> +
> +    % future/1 represents a value that will be computed by another thread.
> +    %
> +:- type future(T).
> +
> +    % Create a future which has the value that the closure, when evaluated,

s/closure/argument/

> +    % will produce.  This function will create a thread to evaluate the
> +    % closure using spawn/3.
> +    %
> +    % If the closure throws an exception, that exception will be rethrown by
> +    % wait/1.
> +    %
> +:- func future((func) = T) = future(T).
> +
> +    % Return the value of the future, potentially blocking until the value
> +    % is available.

What do you mean by "potentially" blocking?  It *will* block until the value
is available, won't it?

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

s/are usually/are intended to be/

> +    %
> +    % Technically this is a promise however promise is a reserved word in
> +    % Mercury.  A promise's value can be provided by different calls to
> +    % signal on different branches of execution.

I'm not sure what this last paragraph is telling me.


> +    %
> +:- type future_io(T).
> +
> +    % Create a new empty future_io.
> +    %
> +:- pred init(future_io(T)::uo, io::di, io::uo) is det.
> +
> +    % Provide a value for the future_io and signal any waiting threads.  Any
> +    % further calls to wait will return immediately.
> +    %
> +    % Calling signal multiple times will result in undefined behaviour.
> +    %
> +:- pred signal(future_io(T)::in, T::in, io::di, io::uo) is det.
> +
> +    % Return the future_io's value, potentially blocking until it is
> +    % signaled.
> +    %
> +:- pred wait(future_io(T)::in, T::out, io::di, io::uo) is det.
>

...

> diff --git a/library/thread.semaphore.m b/library/thread.semaphore.m
> index 46c53e2..14f80e1 100644
> --- a/library/thread.semaphore.m
> +++ b/library/thread.semaphore.m
> @@ -2,6 +2,7 @@
> % vim: ft=mercury ts=4 sw=4 et
> %-----------------------------------------------------------------------------%
> % Copyright (C) 2000-2001,2003-2004, 2006-2007, 2009-2011 The University of Melbourne.
> +% Copyright (C) 2014 The Mercury Team.
> % This file may only be copied under the terms of the GNU Library General
> % Public License - see the file COPYING.LIB in the Mercury distribution.
> %-----------------------------------------------------------------------------%
> @@ -28,40 +29,93 @@
>
> :- type semaphore.
>
> +    % init(Count, Sem, !IO) creates a new semaphore `Sem' with its counter
> +    % initialized to Count.


Why is `Sem' quoted, but Count not?

> +    %
> +:- pred init(int::in, semaphore::uo, io::di, io::uo) is det.
> +
>     % init(Sem, !IO) creates a new semaphore `Sem' with its counter
>     % initialized to 0.
>     %
> -:- pred semaphore.init(semaphore::out, io::di, io::uo) is det.
> +:- pred init(semaphore::uo, io::di, io::uo) is det.
>
> -    % Returns a new semaphore `Sem' with its counter initialized to Count.
> +    % Sem = init(Count) returns a new semaphore `Sem' with its counter
> +    % initialized to Count.
>     %
> -:- impure func semaphore.init(int::in) = (semaphore::uo) is det.
> +    % This has been renamed to impure_init.
> +    %
> +:- impure func init(int::in) = (semaphore::uo) is det.
> +:- pragma obsolete(init/1).

impure_init needs to be (1) a function and (2) defined in the public interface,
since users require a way of initialising semaphore valued mutables.

The deprecation of the function semaphore.init/1 should be mentioned in
the NEWS file.

>     % wait(Sem, !IO) blocks until the counter associated with `Sem'
>     % becomes greater than 0, whereupon it wakes, decrements the
>     % counter and returns.
>     %
> -:- pred semaphore.wait(semaphore::in, io::di, io::uo) is det.
> +:- pred wait(semaphore::in, io::di, io::uo) is det.
>
>     % try_wait(Sem, Succ, !IO) is the same as wait/3, except that
>     % instead of blocking, it binds `Succ' to a boolean indicating
>     % whether the call succeeded in obtaining the semaphore or not.
>     %
> -:- pred semaphore.try_wait(semaphore::in, bool::out, io::di, io::uo) is det.
> +:- pred try_wait(semaphore::in, bool::out, io::di, io::uo) is det.
>
>     % signal(Sem, !IO) increments the counter associated with `Sem'
>     % and if the resulting counter has a value greater than 0, it wakes
>     % one or more coroutines that are waiting on this semaphore (if
>     % any).

We should probably settle on one of "thread" or "coroutine".  (Since the latter
only occurs in two places, it should most likely be the former.)

> -:- pred semaphore.signal(semaphore::in, io::di, io::uo) is det.
> +:- pred signal(semaphore::in, io::di, io::uo) is det.
>
> %-----------------------------------------------------------------------------%
> %-----------------------------------------------------------------------------%
> -
> :- implementation.
>
> +init(Count, Semaphore, !IO) :-
> +    promise_pure (
> +        impure impure_init(Count, Semaphore)
> +    ).
> +
> +init(Semaphore, !IO) :-
> +    init(0, Semaphore, !IO).
> +
> +init(Count) = Semaphore :-
> +    impure impure_init(Count, Semaphore).
> +
> +signal(Semaphore, !IO) :-
> +    promise_pure (
> +        impure impure_signal(Semaphore)
> +    ).

Guess what the Mercury compiler does to pure det goals with no outputs,
such as the body of signal/3 there? ;-)
When you're done guessing, it should be:

    signal(Semaphore, !IO) :-
        promise_pure (
            impure impure_signal(Semaphore),
            !:IO = !.IO
        ).

> +wait(Semaphore, !IO) :-
> +    promise_pure (
> +        impure impure_wait(Semaphore)
> +    ).

Ditto.

> +
> +try_wait(Sem, Res, !IO) :-
> +    promise_pure (
> +        impure impure_try_wait(Sem, Res)
> +    ).
> +
> +%-----------------------------------------------------------------------------%
> %-----------------------------------------------------------------------------%
> +:- interface.
> +
> +% The semaphore operations above can be used without the IO state in impure
> +% code.

s/IO state/I\/O state/

Add a comment saying that these are exported for use by implementors.

> +
> +:- impure pred impure_init(int::in, semaphore::uo) is det.
> +
> +:- impure pred impure_init(semaphore::uo) is det.
> +
> +:- impure pred impure_wait(semaphore::in) is det.
> +
> +:- impure pred impure_try_wait(semaphore::in, bool::out) is det.
> +
> +:- impure pred impure_signal(semaphore::in) is det.
> +
> +%-----------------------------------------------------------------------------%
> +%-----------------------------------------------------------------------------%
> +:- implementation.
>
> :- pragma foreign_decl("C", "
>     #include <stdio.h>
> @@ -106,13 +160,17 @@ ML_finalize_semaphore(void *obj, void *cd);
>
> %-----------------------------------------------------------------------------%
>
> -init(Semaphore, !IO) :-
> -    promise_pure (
> -        impure Semaphore = init(0)
> -    ).
> +%impure_init(Count) = Semaphore :-
> +%    impure init(Count, Semaphore).


I don't like mystery commented out code: either delete the commented out
clauses or add a comment saying *why* they are commented out.

> +
> +impure_init(Semaphore) :-
> +    impure impure_init(0, Semaphore).
> +
> +%init = Semaphore :-
> +%    impure Semaphore = init(0).

Ditto.

Cheers,
Julien.