Discussion:
[next gen futures] Lightweight monad ready for inspection
(too old to reply)
Niall Douglas
2015-06-19 17:03:59 UTC
Permalink
Some may remember the thread starting from
http://boost.2283326.n4.nabble.com/next-gen-future-promise-What-to-cal
l-the-monadic-return-type-td4676039.html and that I would firstly
prepare an optimally lightweight monad<T> for review here before
going on to base a next-gen lightweight future-promise on that
monad<T>.

I didn't expect it would take nearly four weeks to get there, but
writing STL quality C++ with full conformance test suite is amazingly
labourious. Anyway you can now view the design and tell me what you
think. A quick overview of the design:

This monad can hold a fixed variant list of empty, a type R, a
lightweight error_type or a heavier exception_type at a space cost of
max(20, sizeof(R)+4). Features:

* Very lightweight on build times and run times up to the point of
zero execution cost and just a four byte space overhead. Requires min
clang 3.2, GCC 4.7 or VS2015. A quick sample of runtime overhead, min
to max opcodes generated by GCC 5.1:

1 opcodes <= Value transport <= 113 opcodes

8 opcodes <= Error transport <= 119 opcodes

22 opcodes <= Exception transport <= 214 opcodes

4 opcodes <= then() <= 154 opcodes

5 opcodes <= bind() <= 44 opcodes

* Just enough monad, nothing more, nothing fancy. Replicates the
future API with a fair chunk of the Expected<T> API, so if you know
how to use a future you already know how to use this.

* Enables convenient all-noexcept mathematically verifiable close
semantic design, so why bother with Rust anymore? :)

* Can replace most uses of optional<T>.

* Deep integration with lightweight future-promise (i.e. async
monadic programming) also in this library.

* Comprehensive unit testing and validation suite.

* Mirrors noexcept of type R.

* Type R can have no default constructor, move nor copy.

* Works inside a STL container, and type R can be a STL container.

* No comparison operations nor hashing is provided, deliberately to
keep things simple.

Documentation page:

https://ci.nedprod.com/view/Boost%20Thread-Expected-Permit/job/Boost.S
pinlock%20Test%20Linux%20GCC%204.8/doxygen/classboost_1_1spinlock_1_1l
ightweight__futures_1_1monad.html

Source code:

https://github.com/ned14/boost.spinlock/blob/master/include/boost/spin
lock/monad.hpp

Online wandbox compiler:

http://melpon.org/wandbox/permlink/cnZM5KRNpjErXrPH


Any opinions or thoughts gratefully received, particularly if I have
the exception safety semantics right (i.e. a throw during move or
copy leaves the monad empty). Do you also like the polymorphic bind()
and map() which does different things depending on the parameter type
your callable takes? Do you like that by simply changing the
callable's type to a rvalue reference you can move state, or is this
being too clever?

This monad will become the basis of lightweight future-promise which
is essentially a "split monad" with the setter interface and getter
interface potentially in different system threads. The then(), bind()
and map() work as here but only are triggered at the point of the
value being changed. This effectively makes the lightweight future a
"lazy continued monad".

That lightweight future-promise will then enter AFIO to replace its
async_io_op type hopefully in time for the peer review this time next
month.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Robert Ramey
2015-06-19 17:50:52 UTC
Permalink
On 6/19/15 10:03 AM, Niall Douglas wrote:
> https://ci.nedprod.com/view/Boost%20Thread-Expected-Permit/job/Boost.S
> pinlock%20Test%20Linux%20GCC%204.8/doxygen/classboost_1_1spinlock_1_1l
> ightweight__futures_1_1monad.html

I didn't follow any previous discussion but out of curiosity I took a
look at the documentation. I didn't see any information describing what
this thing is, or what problem it solves. So to actually evaluate this,
I'd have to ... I'm not sure. I think you'd like get more and better
feedback if you included this information.

Robert Ramey


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Niall Douglas
2015-06-19 19:52:08 UTC
Permalink
On 19 Jun 2015 at 10:50, Robert Ramey wrote:

> On 6/19/15 10:03 AM, Niall Douglas wrote:
> > https://ci.nedprod.com/view/Boost%20Thread-Expected-Permit/job/Boost.S
> > pinlock%20Test%20Linux%20GCC%204.8/doxygen/classboost_1_1spinlock_1_1l
> > ightweight__futures_1_1monad.html
>
> I didn't follow any previous discussion but out of curiosity I took a
> look at the documentation. I didn't see any information describing what
> this thing is, or what problem it solves. So to actually evaluate this,
> I'd have to ... I'm not sure. I think you'd like get more and better
> feedback if you included this information.

I do apologise. I thought the need for a C++ monad obvious. Some
quick notes on this:

Definitely read this before all the others:
http://bartoszmilewski.com/2011/07/11/monads-in-c/

Constraint programming with monads:
http://bartoszmilewski.com/2015/05/11/using-monads-in-c-to-solve-const
raints-1-the-list-monad/

Tutorial in C++ monads:
http://thebytekitchen.com/2014/10/22/harder-to-c-monads-for-mortals-1/

Combining tuples with monads (this is exactly what Hana is meant to
help with):
http://cpptruths.blogspot.ie/2014/08/fun-with-lambdas-c14-style-part-3
.html

My own personal and particular need for a monad in AFIO:

https://svn.boost.org/trac/boost/wiki/BestPracticeHandbook#a8.DESIGN:S
tronglyconsiderusingconstexprsemanticwrappertransporttypestoreturnstat
esfromfunctions


Many, many people have had a try at a C++ monad, including at least
half a dozen people on this list and the one which came closest to
standardisation was probably Vicente's Expected<T, E>. All those
implementations have not caught on as the default monad for C++ for
varying reasons.

I have badly needed one for AFIO since its beginning as it solves a
large number of design problems for me (the Handbook example is but
one of many), but I made do without mainly because of MSVC. VS2015 is
finally just about capable enough at C++ 11 to make a decent
optimally lightweight C++ monad feasible, so here is my attempt.

The main differences in mine over the other monads around are:

1. Monadic impurity. Mine is deliberately impure monad to make C++
programming much easier. A "C++-ised" monad. It also replaces
optional<T> for me whose design I have never much liked mainly
because optional<T> should always have been a monad like this one.

2. Fixed function. Mine hardcodes the unexpected options. This makes
it easier to program against because you can switch on implicit
conversions all the time, plus you can do polymorphic continuations
like I have which I personally think is very cool. It also allows the
compiler to generate far more optimal code some of the time because
I've intentionally twiddled the compiler to not bail out during
optimisation, so you don't get as much of the bloat traditional
monads force the compiler to generate.

3. Standalone: Mine doesn't come with an associated library. It is
completely standalone and single purpose. You can just drop it into
projects and get to work.

4. Deep integration with future-promise. I'll demonstrate how handy
this is when I bring lightweight future-promise for review to this
list sometime in the next few weeks.

Finally, you may still wonder as to the point? If you do some
programming in Rust which will probably become C++'s biggest
competitor five years from now, all Rust's error handling is done via
its Optional type Option<T> and its Monad type Result<T, E> as there
is no exception throwing mechanism in Rust whatsoever. Once you get
used to programming and designing your code that way, you start to
wish you could do the same as easily in C++.

Rust's Option<T> and Result<T, E> are very lightweight on both build
times and runtime overhead unlike most C++ monad implementations.
With this proposed lightweight monad<T>, I very substantially close
that gap between C++ and Rust, and I personally think my monad<T> is
much nicer again to program against than Rust's which is a bit
clunky. This may prove very useful in the years to come when C++ will
be forced to get out of its ivory tower to stay relevant as a systems
programming language as Rust starts to eat away at the C++ ecosystem.

Does this help Robert?

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Robert Ramey
2015-06-20 00:18:21 UTC
Permalink
On 6/19/15 12:52 PM, Niall Douglas wrote:
> On 19 Jun 2015 at 10:50, Robert Ramey wrote:
> Does this help Robert?
>

It's a good start. Actually, you could might want to include most of
the text in this email in the document as an introduction. At a
minimum, it would save you trouble of answering the same question again.
And it wouldn't cost you anything since you just did most of the work.

Robert Ramey


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Avi Kivity
2015-06-20 09:44:27 UTC
Permalink
On 06/19/2015 08:03 PM, Niall Douglas wrote:
> Some may remember the thread starting from
> http://boost.2283326.n4.nabble.com/next-gen-future-promise-What-to-cal
> l-the-monadic-return-type-td4676039.html and that I would firstly
> prepare an optimally lightweight monad<T> for review here before
> going on to base a next-gen lightweight future-promise on that
> monad<T>.

BOOST_SPINLOCK_FUTURE_MSVC_HELP future_type get_future()
{
// If no value stored yet, I need locks on from now on
if(!_need_locks && _storage.type==value_storage_type::storage_type::empty)
{
_need_locks=true;
new (&_lock) spinlock<bool>();
}


Isn't that the common case? Usually if you already have a value, you
return it with make_ready_future(). Otherwise, at the time of
get_future(), the promise still doesn't have a value.



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Niall Douglas
2015-06-20 12:21:50 UTC
Permalink
On 20 Jun 2015 at 12:44, Avi Kivity wrote:

> On 06/19/2015 08:03 PM, Niall Douglas wrote:
> > Some may remember the thread starting from
> > http://boost.2283326.n4.nabble.com/next-gen-future-promise-What-to-cal
> > l-the-monadic-return-type-td4676039.html and that I would firstly
> > prepare an optimally lightweight monad<T> for review here before
> > going on to base a next-gen lightweight future-promise on that
> > monad<T>.
>
> BOOST_SPINLOCK_FUTURE_MSVC_HELP future_type get_future()
> {
> // If no value stored yet, I need locks on from now on
> if(!_need_locks && _storage.type==value_storage_type::storage_type::empty)
> {
> _need_locks=true;
> new (&_lock) spinlock<bool>();
> }
>
>
> Isn't that the common case? Usually if you already have a value, you
> return it with make_ready_future(). Otherwise, at the time of
> get_future(), the promise still doesn't have a value.

This came up in the discussion a month ago with some feeling that
this was a pointless optimisation. I disagree for the same reasons I
outlined back then, just because you should use make_ready_future()
doesn't mean in generic programming you always can. A very good
example of that is in the WG21 coroutines proposal where if the
operations are correctly ordered and if you never enter a suspend
point, the compiler can set the promise before getting the future and
therefore its optimiser can completely elide the promise-future
construct entirely. I've already raised that idea with Gor as a
non-compiler-magic way of completely eliding future-promise overheads
in the non-suspending coroutine outcome.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Bjorn Reese
2015-06-20 11:48:29 UTC
Permalink
On 06/19/2015 07:03 PM, Niall Douglas wrote:

> https://github.com/ned14/boost.spinlock/blob/master/include/boost/spinlock/monad.hpp

This starts with the words "The world's most simple C++ monad" followed
by 1200 lines of code... makes one scared of monads.

Here are some random throughts I had while reading the code.

Minor comment, consider letting monad_error inherit from system_error
instead of logic_error.

When throwing monad_error, you cast to int (presumably to satisfy some
compiler.) Can't you simply use make_error_code() instead? That will
also ensure that you set the correct category.

Why does one of the value_storage constructors call abort() rather than
throwing an exception?

Why does monad::get_error() throw on no_state, rather than simply
returning an error_code that says so?

Is there any difference between monad::get() and monad::value()? If
they are synonyms, then you may consider removing monad::get() to keep
the class interface smaller, and instead overload std/boost::get().


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Niall Douglas
2015-06-20 13:08:13 UTC
Permalink
On 20 Jun 2015 at 13:48, Bjorn Reese wrote:

> On 06/19/2015 07:03 PM, Niall Douglas wrote:
>
> > https://github.com/ned14/boost.spinlock/blob/master/include/boost/spinlock/monad.hpp
>
> This starts with the words "The world's most simple C++ monad" followed
> by 1200 lines of code... makes one scared of monads.

Firstly, thanks for the review. As I know you know, STL quality C++
is amazingly verbose. And I haven't implemented monad<void> yet,
which will require doubling the existing lines of code to stamp out
an almost identical monad<void> specialisation. I am currently
strongly considering an automatically generated source solution to
that.

(One could use enable_if everywhere to get a void and non-void single
implementation, but I want minimal build time costs).

> Here are some random throughts I had while reading the code.
>
> Minor comment, consider letting monad_error inherit from system_error
> instead of logic_error.

http://en.cppreference.com/w/cpp/thread/future_error

I agree with you, but that's the C++ standard.

Of course, monad need not duplicate future here, but I think if I
claim "future semantics" then it ought to.

> When throwing monad_error, you cast to int (presumably to satisfy some
> compiler.) Can't you simply use make_error_code() instead? That will
> also ensure that you set the correct category.

VS2015 RC was the problem. The current cast to int workaround is the
first thing I'll try fixing when VS2015 RTM comes out.

The category is correct though. The throw_error() function is a
template parameter, and that is a struct detail::throw_monad_error
which in turn throws monad_error(monad_errc). monad_error takes a
std::error_code, and the C++ 11 STL uses the
std::is_error_code_enum<> trait to auto convert the monad_errc enum
into the correct error code and monad_category category.

I lifted that pattern of how to throw a future_error straight from
Boost and two STLs I examined. It's identical to std::future<T> and
boost::future<T>.

> Why does one of the value_storage constructors call abort() rather than
> throwing an exception?

value_storage lives in the detail namespace, and its ability to carry
a future<T>* in its variant space is an internal implementation
detail nor exposed to public users. The only users of that facility
are lightweight future-promise. They (should) never ever copy
construct a value_storage, so if a copy construction ever occurs when
the contents are a future<T>*, that's memory corruption and/or bad
programming by me. It was purely defensive programming on my part.

> Why does monad::get_error() throw on no_state, rather than simply
> returning an error_code that says so?

A very good question. I purely did it that way round for these two
reasons:

1. Any attempt to get any state from an empty monad always throws
no_state consistenty no matter what you call.

2. future-promise always throws a no_state if either has no state, so
boost::future<T>::get_exception_ptr() will throw a no_state instead
of returning an exception_ptr of no_state. monad<T> matches that
behaviour.

Actually, I just lied. The monad get_or(), get_error_or(),
get_exception_or() functions never throw no_state, they return the OR
value. I am unsure if that is a wise design choice.

There is also another potential design problem in that get_error()
returns a null error_code if the monad is not errored even if it is
excepted. I did it that way to match get_exception() as
boost::future<T>::get_exception_ptr() returns a null exception_ptr if
there is no exception. However there is a discrepency, because if the
monad is errored not excepted and you call get_exception(), you'll
get an exception_ptr to the system_error for the error_code, and it's
not the same the other way round.

There is a logic to this though. monad<T> is effectively a tribool
state of empty/value/excepted where an errored state always converts
when needed into an exception state, but never the other way round.
The errored state is therefore a non-type-erased excepted state,
while the excepted state is a type-erased state. I am just unsure if
that is a wise design.

> Is there any difference between monad::get() and monad::value()? If
> they are synonyms, then you may consider removing monad::get() to keep
> the class interface smaller, and instead overload std/boost::get().

They are identical.

I hate multiple names for the same function. However, Expected<T,
E>'s value fetcher function is called value(), and I was hoping for
an easy swap for code using Expected<T, E>.

That said, if there is any opposition here I will gladly remove
value() and leave it with just get().

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Gavin Lambert
2015-06-29 08:08:17 UTC
Permalink
On 21/06/2015 01:08, Niall Douglas wrote:
> Actually, I just lied. The monad get_or(), get_error_or(),
> get_exception_or() functions never throw no_state, they return the OR
> value. I am unsure if that is a wise design choice.

I think it is.

> There is also another potential design problem in that get_error()
> returns a null error_code if the monad is not errored even if it is
> excepted. I did it that way to match get_exception() as
> boost::future<T>::get_exception_ptr() returns a null exception_ptr if
> there is no exception. However there is a discrepency, because if the
> monad is errored not excepted and you call get_exception(), you'll
> get an exception_ptr to the system_error for the error_code, and it's
> not the same the other way round.

Perhaps there should be an error code that represents "has an
exception"? (Either from a custom category or finding an appropriate
system error to hijack for this purpose.)

I don't like the idea of someone writing code that only tests the
error_code (because they weren't expecting exceptions), but which claims
there is no error because there really was an exception instead.
Exceptions are errors are exceptions, and neither is an ordinary result
value.



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Niall Douglas
2015-06-29 10:35:37 UTC
Permalink
On 29 Jun 2015 at 20:08, Gavin Lambert wrote:

> > There is also another potential design problem in that get_error()
> > returns a null error_code if the monad is not errored even if it is
> > excepted. I did it that way to match get_exception() as
> > boost::future<T>::get_exception_ptr() returns a null exception_ptr if
> > there is no exception. However there is a discrepency, because if the
> > monad is errored not excepted and you call get_exception(), you'll
> > get an exception_ptr to the system_error for the error_code, and it's
> > not the same the other way round.
>
> Perhaps there should be an error code that represents "has an
> exception"? (Either from a custom category or finding an appropriate
> system error to hijack for this purpose.)

I already have a monad_category and a monad_errc which can do this.

> I don't like the idea of someone writing code that only tests the
> error_code (because they weren't expecting exceptions), but which claims
> there is no error because there really was an exception instead.
> Exceptions are errors are exceptions, and neither is an ordinary result
> value.

It's definitely a very valid concern. I'll sleep on it and make a
decision.

Thanks for commenting on this problem, it's a particular worry of
mine.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Vicente J. Botet Escriba
2015-06-29 15:54:19 UTC
Permalink
Le 29/06/15 12:35, Niall Douglas a écrit :

Niall, I don't see why do you need to define a concrete monad class that
is used to define other monadic types. The implementation of each
specific monadic type has its own trade-offs.

We can provide monadic operations for optional/expected/future/....

Why do you need to have a concrete monad class?
What is the added value?

Best,
Vicente

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Niall Douglas
2015-06-29 17:03:49 UTC
Permalink
On 29 Jun 2015 at 17:54, Vicente J. Botet Escriba wrote:

> Niall, I don't see why do you need to define a concrete monad class that
> is used to define other monadic types. The implementation of each
> specific monadic type has its own trade-offs.
>
> We can provide monadic operations for optional/expected/future/....
>
> Why do you need to have a concrete monad class?
> What is the added value?

Let me flip the question to you.

Why does it matter how the monadic types are implemented? All the
user needs to care about is that monad<T>, result<T>, option<T>,
future<T>, future_result<T> and future_option<T> behave according to
strict and sensible rules which make sense to program against.

You could of course implement them separately. I chose not to, but
that's an internal implementation detail. Each correctly SFINAE's out
those functionalities they don't provide and/or provides a
static_assert when you try doing something you can't.

If you're really asking why are they all so similar, I'd also flip
the question: "why is experimental::optional<T> not the same pattern
as future<T>?" Both transport a T, so why aren't they the same?

There are many advantages and very few costs if they were. I
especially like that I can use the same mental model for both, both
have identical APIs where that makes sense, and both work the same
way in my head. Both are also each absolutely minimum impact on build
and runtime costs, I have a suite of unit tests verifying that per
commit.

BTW there is absolutely nothing ruling out a later monad<T,E>. I
deliberately left that open for the future, all the existing design
an API assumes an implict monad<T, E=variant<error_code,
exception_ptr>>. Any code written against the current design would
work with a recompile with a later monad<T, E>.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Vicente J. Botet Escriba
2015-07-01 17:22:57 UTC
Permalink
Le 29/06/15 19:03, Niall Douglas a écrit :
> On 29 Jun 2015 at 17:54, Vicente J. Botet Escriba wrote:
>
>> Niall, I don't see why do you need to define a concrete monad class that
>> is used to define other monadic types. The implementation of each
>> specific monadic type has its own trade-offs.
>>
>> We can provide monadic operations for optional/expected/future/....
>>
>> Why do you need to have a concrete monad class?
>> What is the added value?
> Let me flip the question to you.
>
> Why does it matter how the monadic types are implemented? All the
> user needs to care about is that monad<T>, result<T>, option<T>,
> future<T>, future_result<T> and future_option<T> behave according to
> strict and sensible rules which make sense to program against.
If it is an implementation detail it is no worth continuing the
discussion at the design level.
Could we then avoid to mention the monad class on these threads as it is
an implementation detail.
So what are the public classes you would present for review?

Vicente


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Niall Douglas
2015-07-02 00:54:37 UTC
Permalink
On 1 Jul 2015 at 19:22, Vicente J. Botet Escriba wrote:

> >> Niall, I don't see why do you need to define a concrete monad class that
> >> is used to define other monadic types. The implementation of each
> >> specific monadic type has its own trade-offs.
>
> Could we then avoid to mention the monad class on these threads as it is
> an implementation detail.

basic_monad is the base class of everything. You probably wouldn't
use it directly, so it's an implementation detail.

monad<T> is a user facing specialisation for convenient use.

> So what are the public classes you would present for review?

Documentation for lightweight future promise:

https://ci.nedprod.com/view/Boost%20Thread-Expected-Permit/job/Boost.S
pinlock%20Test%20Linux%20GCC%204.8/doxygen/group__future__promise.html

Documentation for monads, which are base classes of the futures:

https://ci.nedprod.com/view/Boost%20Thread-Expected-Permit/job/Boost.S
pinlock%20Test%20Linux%20GCC%204.8/doxygen/group__monad.html

Note the futures are not finished yet. I don't expect them to be
considered finished until around 11th July. I have yet to do:

- [ ] Implement N4399 continuations extended with monadic bind etc.
- [ ] wait() should sleep the thread as necessary.
- [ ] Implement wait_for()/wait_until().
- [ ] when_any/when_all composure.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Vicente J. Botet Escriba
2015-06-21 07:07:11 UTC
Permalink
Le 19/06/15 19:03, Niall Douglas a écrit :
> Some may remember the thread starting from
> http://boost.2283326.n4.nabble.com/next-gen-future-promise-What-to-cal
> l-the-monadic-return-type-td4676039.html and that I would firstly
> prepare an optimally lightweight monad<T> for review here before
> going on to base a next-gen lightweight future-promise on that
> monad<T>.

Nial, I don't understand why you call this class monad. I see it much
more as a generalized optional_expected that allows the user to say
which exception is thorw when there is an error type and not an
exception type.

IMO, the last parameter throw_error is really not needed.

You can always wrap an error code with a class that states how to throw
an exception. That means that we need an additional Error concept that
defines the throw_error function, e.g.

We could have a class that wraps an error with an exception

template <class Error, class Exception>
struct ThrowError {
Error value;
};

template <class Error, class Exception>
void throw_error(ThrowError<Error, Exception> const& e) {
throw Exception(e.value);
}

Now the generalized optional/expected class will use the throw error
whenever it needs to throw an exception and has an error type stored.

BTW, why have you chosen a Callable for throw_error instead of directly
the Exception?


BTH, expected could already store an error or an exception_ptr. All you
need is to have a class

template <class Error, class Exception>
struct ErrorOrException;


Resuming you monad class is in some way an alias of

expected<optional<R>, ErrorOrException<ThrowError<Error,
ThrowException>, Exception>>

possibly optimized with a specific specialization.

BTW, why your class accepts only on Exception type and not a variadic
set of Exceptions types?


I have some trouble with the is_ready function. You say "True if monad
is not empty.".
Do you mean that oi will not be ready

optional<int> oi;

You need to add the preconditions of each function. No precondition mean
the function is not partial.

I don't see comparison operators, neither hash customization, was this
intentional?


I suspect that the exception thown by value() when an instance is empty
is not future_error<no_state>,and that there is a type on the
documentation. Or was this intentional?

In the function value()&& you say
"If contains a value_type, returns a rvalue reference to it, else throws
an exception of future_error(no_state), system_error or the
exception_type."

Why system_error? Do you mean that when the exception_type given as
parameter is exception_ptr, the exception throw is exception_ptr and not
the stored exception? In the Expected proposal and in std::future, the
exception throw will be the stored exception.

The function has_exception is not coherent with the others state
observer functions empty/has/value/has_error.

What is the exact signature (or valid signatures) of the functions
passed to map/bind/then?
BTW, are these functions proposed?

Last can the map function be applied to an empty instance? What would be
the result?



Best,
Vicente




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Vicente J. Botet Escriba
2015-06-21 08:00:21 UTC
Permalink
Le 21/06/15 09:07, Vicente J. Botet Escriba a écrit :
> Le 19/06/15 19:03, Niall Douglas a écrit :
>> Some may remember the thread starting from
>> http://boost.2283326.n4.nabble.com/next-gen-future-promise-What-to-cal
>> l-the-monadic-return-type-td4676039.html and that I would firstly
>> prepare an optimally lightweight monad<T> for review here before
>> going on to base a next-gen lightweight future-promise on that
>> monad<T>.
>
> Nial, I don't understand why you call this class monad. I see it much
> more as a generalized optional_expected that allows the user to say
> which exception is thorw when there is an error type and not an
> exception type.
>
> IMO, the last parameter throw_error is really not needed.
>
> You can always wrap an error code with a class that states how to
> throw an exception. That means that we need an additional Error
> concept that defines the throw_error function, e.g.
>
> We could have a class that wraps an error with an exception
>
> template <class Error, class Exception>
> struct ThrowError {
> Error value;
> };
>
> template <class Error, class Exception>
> void throw_error(ThrowError<Error, Exception> const& e) {
> throw Exception(e.value);
> }
>
> Now the generalized optional/expected class will use the throw error
> whenever it needs to throw an exception and has an error type stored.
>
> BTW, why have you chosen a Callable for throw_error instead of
> directly the Exception?
>
>
> BTH, expected could already store an error or an exception_ptr. All
> you need is to have a class
>
> template <class Error, class Exception>
> struct ErrorOrException;
>
>
> Resuming you monad class is in some way an alias of
>
> expected<optional<R>, ErrorOrException<ThrowError<Error,
> ThrowException>, Exception>>
>
> possibly optimized with a specific specialization.
>
> BTW, why your class accepts only on Exception type and not a variadic
> set of Exceptions types?
>
>
> I have some trouble with the is_ready function. You say "True if monad
> is not empty.".
> Do you mean that oi will not be ready
>
> optional<int> oi;
>
> You need to add the preconditions of each function. No precondition
> mean the function is not partial.
>
> I don't see comparison operators, neither hash customization, was this
> intentional?
>
>
> I suspect that the exception thown by value() when an instance is
> empty is not future_error<no_state>,and that there is a type on the
> documentation. Or was this intentional?
>
> In the function value()&& you say
> "If contains a value_type, returns a rvalue reference to it, else
> throws an exception of future_error(no_state), system_error or the
> exception_type."
>
> Why system_error? Do you mean that when the exception_type given as
> parameter is exception_ptr, the exception throw is exception_ptr and
> not the stored exception? In the Expected proposal and in std::future,
> the exception throw will be the stored exception.
>
> The function has_exception is not coherent with the others state
> observer functions empty/has/value/has_error.
>
> What is the exact signature (or valid signatures) of the functions
> passed to map/bind/then?
> BTW, are these functions proposed?
>
> Last can the map function be applied to an empty instance? What would
> be the result?
>
I would like to suggest a different approach.

Given a class optionals<T1, ..., Tn>, which is a variant accepting to
be empty

we can see optionals<T, E1, ..., En> as an Error Monad, when all the Ei
are instances of the Error concept.

A class is a model of the Error concept if it defines the
rethrow_exception function.

When the optionals is empty the exception thrown is bad_optionals_access.

exception_ptr is a type erased Error that rethrows the stored exception.

std::error_code and std::error_condition can be seen as instances of the
type class Error if we define the rethrow_exception on them throwing an
system_error exception.

optionals<T1, ..., Tn> can not define all the function that your class
monad defines as they are too specific.

Instead of defining member functions we can define non-member functions.

has_value/has_error/value/set_value/set_error/get_error/emplace/map/bind/then


optionals<T1, ..., Tn> should be default constructible from Ti and
convertible to Ti using maybe a specific cast function.

optionals<T, E1, ..., En> must be implicitly convertible from the result
of throw_error(e).

We could also define a specific class as you propose with specific
semantic for the first argument that would defines member functions. I'm
not against this approach, nevertheless the main issue I have is how to
name this class :(

result<T, E1, En> doesn't conveys the fact that it can be empty.
monad<T, E1, En> is not good as Monad is a type class not a
concrete type.
optional_result<T, E1, En> is too long
optional_value_or_errors<T, E1, En> is too long

HTH,
Vicente

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Vicente J. Botet Escriba
2015-06-21 08:42:59 UTC
Permalink
Le 21/06/15 09:07, Vicente J. Botet Escriba a écrit :
> Le 19/06/15 19:03, Niall Douglas a écrit :
>> Some may remember the thread starting from
>> http://boost.2283326.n4.nabble.com/next-gen-future-promise-What-to-cal
>> l-the-monadic-return-type-td4676039.html and that I would firstly
>> prepare an optimally lightweight monad<T> for review here before
>> going on to base a next-gen lightweight future-promise on that
>> monad<T>.
>
>
>
>
A few additional questions:

* The future::then function has the semantic of calling the continuation
when the future becomes ready. In addition the future::then moved the
future to the continuation.

I believe that your monad<T>::then has not this semantic. So, what is
the added value of this function? IIUC, the difference between

m.then(f);

and

f(m);

is that monad::then wraps the result of f if needed as bind do, but the
continuation function takes a monad reference

I believe that it would be better to have a different name. What a bout
next, wrap_call, call_with, ...?


* As you have bind, why you don't have catch_error? I understand that
::then could be used instead, but I would add it just for symmetry and
because the user don't needs to check when she is handling errors.

* What about having a match function using overload on the stored type? [1]

* Monads are defined by having a bind and unit functions. I'm missing a
unit function. std::future has std::make_future_ready, expected has
make_expected, std::optional has std::make_optional.

I've been working on a generic make factory library [2] that could be
associated to the unit Monad function

Vicente

[1] https://github.com/viboes/tags/tree/master/doc/proposals/match
[2] https://github.com/viboes/std-make/tree/master/doc/proposal/factories



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Niall Douglas
2015-06-22 00:43:17 UTC
Permalink
On 21 Jun 2015 at 9:07, Vicente J. Botet Escriba wrote:

> Le 19/06/15 19:03, Niall Douglas a écrit :
> > Some may remember the thread starting from
> > http://boost.2283326.n4.nabble.com/next-gen-future-promise-What-to-cal
> > l-the-monadic-return-type-td4676039.html and that I would firstly
> > prepare an optimally lightweight monad<T> for review here before
> > going on to base a next-gen lightweight future-promise on that
> > monad<T>.

Firstly Vicente your three emails contained a ton of gold quality
observations. From those I have generated this task list:

Boost review feedback work items:
- [x] Documentation incorrectly says exceptions thrown are
future_error when they are in fact monad_error.
- [ ] Add template aliases for different configurations of monad<T>
(one of maybe, result, holder, value, retval, potential, likely). Add
two additional aliases, one for a monad without exception_ptr, and
another for a monad with neither error_code nor exception_ptr
(option<T>?).
- [ ] Make how error_type is converted into exception_type
configurable.
- [ ] Make the tribool nature of monad<T> much more formally
obvious.
- [ ] In addition to value_or(), error_or() etc add value_and(),
error_and() etc.
- [ ] As .then() is defined in a future as executing the callable
when the value is set, and monad<T>.then() executes immediately and
does not execute when the value is next changed, does this make
monad<T>.then() deceptively named? (I think yes). Perhaps and() is a
better name for then()? What about simply operator() i.e. make the
monad callable? What about operator[]?
- [ ] Add match() function which visits a callable on the contents.
- [ ] Look into member operator overloads for bind() and map() e.g.
monad<int> &m; auto r = m >> [](int a){return a;}; Can't use operator
>>=() from Haskell as has same precedence to operator=().

Thank you *hugely* for your feedback Vicente. It was extremely
valuable to me.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Niall Douglas
2015-06-26 01:11:05 UTC
Permalink
On 22 Jun 2015 at 1:43, Niall Douglas wrote:

> Firstly Vicente your three emails contained a ton of gold quality
> observations. From those I have generated this task list:
> [snip]
> Thank you *hugely* for your feedback Vicente. It was extremely
> valuable to me.

For those interested, the final version of lightweight monad hit
github earlier today. Highlights:

monad is now space optimal, consuming as little as two bytes
depending on configuration. monad<void> is now working, plus these
new specialisations were added:

* result<T>: empty/T/error_code (no exception_ptr).
* option<T>: empty/T (no error code nor exceptions).

I chose those names to match the same thing in Rust. They are all
really instantiations of basic_monad<> with a different policy class.
As will be lightweight future<T> next week.

I formalised the logic behind monad into a tribool based ternary
logic, with added C++ 11 tribool implementation based on a constexpr
enum class. This provides a full ternary logic via the usual AND OR
operators etc such that:

if(true_(monad)) // has value
...
else if(false_(monad)) // is empty
...
else // if(other(monad)) // is errored or excepted
...

One can now do make_monad([](Args...){}) and the monad can be called
with (Args...). That also applies to result and option. This opens
some very interesting possibilities for lazy functional programming.

Finally, I added some operator overloads. The bind operator is now
shortcut with operator >>, and operator | and & can be used for
expression binds instead of functional binds like this:

std::error_code ec;
monad<int> a(5);
monad<int> b(a & 6); // a has a value, so become 6
monad<int> c(b | 4); // b has a value, so remain at 6
monad<int> d(a & ec); // a has a value, so become errored
monad<int> e(d & 2); // d does not have a value, so remain
errored
monad<int> f(d | 2); // d does not have a value, so become 2

I believe, sans bugs, lightweight monad is now finished. I have some
minor todo items, but this is my final intended feature set. Build
impact remains featherweight, space impact is close to optimally low,
and I have even shaved off a few more opcodes from what the compiler
generates for all the operations.

This weekend I'll get started on lightweight future-promise which
derives from monad and indeed is also a basic_monad but with
different implementation policy class. These future-promise ought to
be 98% compatible with the WG21 Concurrency TS spec and will be able
to participate in hetereogeneous when_any/when_all i.e. you can mash
them in with std::future.

It'll likely take me a week to come up with some benchmarks comparing
std::future and my future in a 4-SHA256 engine so you can see the
benefits of the new design. After that I'll replace AFIO's
std::future with these lightweight futures in its public API, and we
should be ready to rock for the 17th July when AFIO's review begins.

Note that only the public user facing API will be refactored to use
these lightweight futures such that you all will review my best
attempt at a final and stable API. I'll leave the existing internal
engine well alone as it's mature and stable until after the community
review, as it will have to be completely redesigned and rewritten to
have optimal performance with these new futures. I don't expect that
to be at all noticeable from external code however, it'll just go
much faster, that's all.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Andrzej Krzemienski
2015-06-26 08:42:59 UTC
Permalink
2015-06-26 3:11 GMT+02:00 Niall Douglas <***@nedprod.com>:

> On 22 Jun 2015 at 1:43, Niall Douglas wrote:
>
> > Firstly Vicente your three emails contained a ton of gold quality
> > observations. From those I have generated this task list:
> > [snip]
> > Thank you *hugely* for your feedback Vicente. It was extremely
> > valuable to me.
>
> For those interested, the final version of lightweight monad hit
> github earlier today. Highlights:
>
> monad is now space optimal, consuming as little as two bytes
> depending on configuration. monad<void> is now working, plus these
> new specialisations were added:
>
> * result<T>: empty/T/error_code (no exception_ptr).
>

To what run-time condition does an empty state correspond here? I used to
thing that you either have a result (T) or a reason why you do not have one
(error_code), but what does it mean that you have neither?

Regards,
&rzej

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Niall Douglas
2015-06-26 11:00:45 UTC
Permalink
On 26 Jun 2015 at 10:42, Andrzej Krzemienski wrote:

> > monad is now space optimal, consuming as little as two bytes
> > depending on configuration. monad<void> is now working, plus these
> > new specialisations were added:
> >
> > * result<T>: empty/T/error_code (no exception_ptr).
>
> To what run-time condition does an empty state correspond here? I used to
> thing that you either have a result (T) or a reason why you do not have one
> (error_code), but what does it mean that you have neither?

Semantically speaking, after feedback from this list, and having
attended Charley's C++ Now Presentation on ternary logic programming
"Your CPU is Binary", I realised that it's worthwhile to formally
specify future/monad/result as ternary logic primitives with ternary
logic operators. option<T> remains boolean. This gives the following
logic table:

Empty => False (future/monad/result/option)
Errored/Excepted => Indeterminate (future/monad/result)
Value => True (future/monad/result/option)

In other words, you never draw a distinction between errored and
excepted. They are semantically equivalent. Therefore not being
possible to be excepted in the case of result<T> means nothing, it's
simply a quality of implementation detail.


From a non-semantic perspective, avoiding exception_ptr has *BIG*
benefits to runtime overhead because exception_ptr forces a memory
barrier, which is why MSVC spews ~2000 opcodes every time you use it.
Some of the time in promise-future you really don't require the
ability to transport arbitrary exceptions because an error_code is
enough, or maybe even no error transport is needed at all. Why
therefore pay for an exception transport when you don't need it? In
AFIO any time we go near OS APIs we currently convert the system
error code into an exception and throw it - this is total overkill.
Using result<T>, any time AFIO calls OS APIs it can exactly and
precisely wrap the outcome into a result<T> and not expend overhead
on unnecessary exception_ptr costs. Only if downstream code consumes
the result without checking for an error will a lazy conversion to an
exception throw occur.

This is why I hope these lightweight promise-futures will be
lightweight enough to promise-future a SHA256 round inside a budget
of 40 cycles because you can disable all error transport entirely,
and effectively just promise an async_optional<char[32]> as SHA256
cannot generate errors. Compare that to std::promise/future which
costs >= 530 CPU cycles per round, a little more than the SHA256
round itself.

I'm still unsure how to handle naming though. promise<T>/future<T>
obviously mean what they mean under the Concurrency TS, so they must
support exception_ptr. A promise-future only capable of transporting
a T and nothing else would need a descriptive name.

I'm currently thinking promise_option<T> and future_option<T>, but I
(a) find those too verbose and (b) I don't think the name means what
they do precisely. Any suggestions for a better name for a kind of
future which can only transport a T and nothing else is welcome.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Vicente J. Botet Escriba
2015-06-29 06:37:30 UTC
Permalink
Le 26/06/15 13:00, Niall Douglas a écrit :
> On 26 Jun 2015 at 10:42, Andrzej Krzemienski wrote:
>
>>> monad is now space optimal, consuming as little as two bytes
>>> depending on configuration. monad<void> is now working, plus these
>>> new specialisations were added:
>>>
>>> * result<T>: empty/T/error_code (no exception_ptr).
>> To what run-time condition does an empty state correspond here? I used to
>> thing that you either have a result (T) or a reason why you do not have one
>> (error_code), but what does it mean that you have neither?
> Semantically speaking, after feedback from this list, and having
> attended Charley's C++ Now Presentation on ternary logic programming
> "Your CPU is Binary", I realised that it's worthwhile to formally
> specify future/monad/result as ternary logic primitives with ternary
> logic operators. option<T> remains boolean. This gives the following
> logic table:
>
> Empty => False (future/monad/result/option)
> Errored/Excepted => Indeterminate (future/monad/result)
> Value => True (future/monad/result/option)
The meaning of empty in optional/option and future is not the same. For
the fist is a valid state, for the second is an invalid state.
In addition asynchronous types have an additional state not-ready, e.g.
future can be invalid, not-ready, exceptional or valued.

Vicente


_______________________________________________
Unsubscribe & other changes: http://
Andrzej Krzemienski
2015-06-29 08:05:07 UTC
Permalink
2015-06-29 8:37 GMT+02:00 Vicente J. Botet Escriba <***@wanadoo.fr
>:

> Le 26/06/15 13:00, Niall Douglas a écrit :
>
>> On 26 Jun 2015 at 10:42, Andrzej Krzemienski wrote:
>>
>> monad is now space optimal, consuming as little as two bytes
>>>> depending on configuration. monad<void> is now working, plus these
>>>> new specialisations were added:
>>>>
>>>> * result<T>: empty/T/error_code (no exception_ptr).
>>>>
>>> To what run-time condition does an empty state correspond here? I used to
>>> thing that you either have a result (T) or a reason why you do not have
>>> one
>>> (error_code), but what does it mean that you have neither?
>>>
>> Semantically speaking, after feedback from this list, and having
>> attended Charley's C++ Now Presentation on ternary logic programming
>> "Your CPU is Binary", I realised that it's worthwhile to formally
>> specify future/monad/result as ternary logic primitives with ternary
>> logic operators. option<T> remains boolean. This gives the following
>> logic table:
>>
>> Empty => False (future/monad/result/option)
>> Errored/Excepted => Indeterminate (future/monad/result)
>> Value => True (future/monad/result/option)
>>
> The meaning of empty in optional/option and future is not the same. For
> the fist is a valid state, for the second is an invalid state.
>

If "empty" means something different in the case of three-type "result",
perhaps it deserves a different name?


> In addition asynchronous types have an additional state not-ready, e.g.
> future can be invalid, not-ready, exceptional or valued.


So it looks like you have two sets of error codes:
1. The one represented by E in result<T, E>
2. A set of error conditions inherent to asynchronous state processing:
"invalid", "not ready" (maybe also "already retrieved").

Regards,
&rzej

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/bo
Niall Douglas
2015-06-29 10:31:58 UTC
Permalink
On 29 Jun 2015 at 10:05, Andrzej Krzemienski wrote:

> >> Empty => False (future/monad/result/option)
> >> Errored/Excepted => Indeterminate (future/monad/result)
> >> Value => True (future/monad/result/option)
> >>
> > The meaning of empty in optional/option and future is not the same. For
> > the fist is a valid state, for the second is an invalid state.
> >
>
> If "empty" means something different in the case of three-type "result",
> perhaps it deserves a different name?

In my synchronous monad, empty is always an invalid state, just as
with future.

States T/errored/excepted are always valid states.

> > In addition asynchronous types have an additional state not-ready, e.g.
> > future can be invalid, not-ready, exceptional or valued.
>
> So it looks like you have two sets of error codes:
> 1. The one represented by E in result<T, E>
> 2. A set of error conditions inherent to asynchronous state processing:
> "invalid", "not ready" (maybe also "already retrieved").

You have nailed another design tradeoff I made on the head. Right now
if lightweight future experiences an error condition, it makes the
future valid in order to set the state to that error condition which
is of type future_errc.

monad behaves identically, as it maps future as closely as possible,
except it uses type monad_errc (which is a subset of future_errc).
This, as you correctly observe means that one cannot disambiguate
between a user who tries to transport a monad_errc with monad<T> and
a monad<T> which set itself to an errored state due to some problem.

As the docs say, "don't use monad<T> to transport a monad_errc nor a
future_errc. Misoperation is likely".

Note also that lightweight monad<T> and future<T> both explicitly
static_assert prevent you from using a T which is an error_type or an
exception_type. In other words, monad<std::error_code> or
monad<std::exception_ptr> will fail to compile. In the docs I suggest
that if you really need to transport those, wrap them in a wrapper
type.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Andrzej Krzemienski
2015-06-29 11:29:36 UTC
Permalink
2015-06-29 12:31 GMT+02:00 Niall Douglas <***@nedprod.com>:

> On 29 Jun 2015 at 10:05, Andrzej Krzemienski wrote:
>
> > >> Empty => False (future/monad/result/option)
> > >> Errored/Excepted => Indeterminate (future/monad/result)
> > >> Value => True (future/monad/result/option)
> > >>
> > > The meaning of empty in optional/option and future is not the same. For
> > > the fist is a valid state, for the second is an invalid state.
> > >
> >
> > If "empty" means something different in the case of three-type "result",
> > perhaps it deserves a different name?
>
> In my synchronous monad, empty is always an invalid state, just as
> with future.
>

In that case, perhaps name "empty" is not the best choice? It has positive
connotations like "empty optional" or "empty vector" which are as valid
states as only a state can be. I believe "invalid state" would reflect your
intention more clearly.

Regards,
&rzej

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Niall Douglas
2015-06-29 11:58:46 UTC
Permalink
On 29 Jun 2015 at 13:29, Andrzej Krzemienski wrote:

> > > If "empty" means something different in the case of three-type "result",
> > > perhaps it deserves a different name?
> >
> > In my synchronous monad, empty is always an invalid state, just as
> > with future.
> >
>
> In that case, perhaps name "empty" is not the best choice? It has positive
> connotations like "empty optional" or "empty vector" which are as valid
> states as only a state can be. I believe "invalid state" would reflect your
> intention more clearly.

It's a tricky one this. On the one hand, empty means that
get()/get_error()/get_exception() will throw no_state, so in that
sense it is invalid.

On the other hand, the monadic operators bind/map/next etc see empty
as a valid state i.e. you can write the bind expression:

monad<T> >> [](monad<T>::empty_type) { /* executed if empty */ );

... and that's just fine too. Similarly, the AND OR operators treat
empty as equal to errored/excepted, so:

monad<int> & 5 | 2

... means that if the monad has a value, emit a monad with 5, else
emit a monad with 2.

Finally, the specialisation option<T> (which is simply a monad
missing the ability to be errored or excepted) has only the two state
options of empty or T. Otherwise it's a monad in every other way, and
can interact with monads like result or monad (i.e. option<T> will
implicitly convert to monad<T>, and monad<T> can be explicitly
converted to option<T>). For option<T>, an empty state might be
invalid, but it is also valid in the sense of state being not a T. If
that makes sense.

In other words, my "dirty monad" doesn't just act like a future, it
also acts like an optional. Identical semantics. Your big win of
choosing option<T> over monad<T> is far lighter weight overheads on
runtime because exception_ptr is *expensive* when you are working in
hundreds of cycles.

I can see already that all this ambiguity and lack of clear design
goals will smack of a poor design not fully baked and thought
through. I can assure boost-dev that I have been pondering this
design for over a year and half a dozen designs were considered and
thrown away before I settled on this design. So far, I am pleased
with it as it ticks all the "red boxes" i.e. the absolute hard red
line requirements I needed (specifically a minimal runtime and build
time overhead). The rest of the design has been allowed to float to
wherever it falls naturally, and you can see what we've now got - a
real "mongrel" of a design where it is up to the programmer to not
shoot themselves in the foot.

This is not to say I don't have qualms and concerns and worries with
this design. All I am claiming is that it solves my pressing problems
in what I think is a neat way, and I am therefore pleased with it so
far. I may later discover I have made a serious design boo boo.

Thanks everyone for your feedback. Designing this stuff is hard, and
your comments have been very useful and helpful.

Niall


--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Niall Douglas
2015-06-29 10:12:13 UTC
Permalink
On 29 Jun 2015 at 8:37, Vicente J. Botet Escriba wrote:

> > Empty => False (future/monad/result/option)
> > Errored/Excepted => Indeterminate (future/monad/result)
> > Value => True (future/monad/result/option)
>
> The meaning of empty in optional/option and future is not the same. For
> the fist is a valid state, for the second is an invalid state.
> In addition asynchronous types have an additional state not-ready, e.g.
> future can be invalid, not-ready, exceptional or valued.

Indeed very true. One of my worries in my design is that you cannot
send an empty state via future<T>, only a T/error/exception. I
console myself that future<void> effectively means sending an empty
state, however in monad<void> empty state is not void state.

That's one of my design tradeoffs. I don't much like it, but it does
make the code much simpler. I am essentially trusting that the
programmer does not do anything too silly.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Vinícius dos Santos Oliveira
2015-06-28 20:14:46 UTC
Permalink
2015-06-25 22:11 GMT-03:00 Niall Douglas <***@nedprod.com>:

> plus these
> new specialisations were added:
>
> * result<T>: empty/T/error_code (no exception_ptr).
> * option<T>: empty/T (no error code nor exceptions).
>

I like these specialisations. Makes the code clearer.

What do you think about renaming monad to async_monad?


--
Vinícius dos Santos Oliveira
https://about.me/vinipsmaker

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailm
Niall Douglas
2015-06-28 20:52:09 UTC
Permalink
On 28 Jun 2015 at 17:14, Vinícius dos Santos Oliveira wrote:

> > plus these
> > new specialisations were added:
> >
> > * result<T>: empty/T/error_code (no exception_ptr).
> > * option<T>: empty/T (no error code nor exceptions).
> >
>
> I like these specialisations. Makes the code clearer.
>
> What do you think about renaming monad to async_monad?

monad<T>, result<T> and option<T> are all *synchronous* value
transports. Just like Rust's Result and Option.

future<T>, future_result<T> and future_option<T> will all be the
asynchronous versions with associated promise types.

I suppose you could have instead async_monad<T>, async_result<T> and
async_option<T>. But async_result<T> would collide with ASIO's
async_result, and that might be confusing.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Vinícius dos Santos Oliveira
2015-06-28 20:52:18 UTC
Permalink
2015-06-28 17:52 GMT-03:00 Niall Douglas <***@nedprod.com>:

> monad<T>, result<T> and option<T> are all *synchronous* value
> transports. Just like Rust's Result and Option.
>

So, why can result<t> be empty?

Sorry about the silly question, but you could use the answer to improve the
documentation for dumb users like me.


--
Vinícius dos Santos Oliveira
https://about.me/vinipsmaker

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/list
Vinícius dos Santos Oliveira
2015-06-28 22:02:35 UTC
Permalink
2015-06-28 17:52 GMT-03:00 Vinícius dos Santos Oliveira <
***@gmail.com>:

> 2015-06-28 17:52 GMT-03:00 Niall Douglas <***@nedprod.com>:
>
>> monad<T>, result<T> and option<T> are all *synchronous* value
>> transports. Just like Rust's Result and Option.
>>
>
> So, why can result<t> be empty?
>

I mean: result<T, E> is like "give me T or it's an error". There is no
empty state. Empty would already be an error state. I'd only understand
empty if it's an async operation that didn't finish already.


--
Vinícius dos Santos Oliveira
https://about.me/vinipsmaker

_______________________________________________
Unsubscribe & other changes: http://lists.boost.
Michael Marcin
2015-06-29 02:05:24 UTC
Permalink
On 6/28/2015 5:02 PM, Vinícius dos Santos Oliveira wrote:
> 2015-06-28 17:52 GMT-03:00 Vinícius dos Santos Oliveira <
> ***@gmail.com>:
>
>> 2015-06-28 17:52 GMT-03:00 Niall Douglas <***@nedprod.com>:
>>
>>> monad<T>, result<T> and option<T> are all *synchronous* value
>>> transports. Just like Rust's Result and Option.
>>>
>>
>> So, why can result<t> be empty?
>>
>
> I mean: result<T, E> is like "give me T or it's an error". There is no
> empty state. Empty would already be an error state. I'd only understand
> empty if it's an async operation that didn't finish already.
>
>

What's the state of a default constructed result<T, E>?

Is it an error state?
Is it empty?
Or is it not default constructible?



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.c
Niall Douglas
2015-06-29 10:07:23 UTC
Permalink
On 28 Jun 2015 at 21:05, Michael Marcin wrote:

> > I mean: result<T, E> is like "give me T or it's an error". There is no
> > empty state. Empty would already be an error state. I'd only understand
> > empty if it's an async operation that didn't finish already.
>
> What's the state of a default constructed result<T, E>?
>
> Is it an error state?
> Is it empty?
> Or is it not default constructible?

In my dirty monad, result<T> (there is no result<T, E>) is always
default constructed to empty. If you want it constructed to something
else, simply pass that into its constructor. There is also a
make_monad(T/error_code/exception_ptr).

In Rust's Result<T, E>, there is no default construction. You must
choose either a T or a E at the point of construction, failure to do
so is a compile time error.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Niall Douglas
2015-06-29 10:04:34 UTC
Permalink
On 28 Jun 2015 at 17:52, Vinícius dos Santos Oliveira wrote:

> > monad<T>, result<T> and option<T> are all *synchronous* value
> > transports. Just like Rust's Result and Option.
>
> So, why can result<t> be empty?

The idea was that the synchronous transport editions map semantically
onto the asynchronous transport editions. So:

Empty <= Unsignalled/Default constructed.
Value <= Value.
Errored/Excepted <= Errored/Excepted.

If you consider a default constructed future, you will see you have
to have a default constructed monad be empty. What else could it be?

There is also the truth that allowing an empty state makes everything
vastly more efficient to implement. For example, I can hard assume
that monad<T> will always have a default constructor, and that makes
implementing monad<monad<T>> considerably easier. If an exception
throws during a move or copy constructor, I can throw the exception
out with the monad left empty. In a situation with (de)serialisation,
the ability to guarantee default construction no matter what T is is
also very valuable. All this turns into a minimum number of assembler
instructions output by the compiler, and is why I chose this design.

> I mean: result<T, E> is like "give me T or it's an error". There is no
> empty state. Empty would already be an error state. I'd only understand
> empty if it's an async operation that didn't finish already.

In case others on boost-dev don't realise, Vinicius here is referring
to Rust, not C++. Myself and Vinicius currently work for the same
client writing code in Rust, at least until he replaces me in a few
week's time! :)

Rust's Result<T, E>, and any traditional monad, has no empty state. I
would call those "pure monads". My monad is not a pure monad, it is a
"dirty" monad with an impure design which I hope/believe is better
suited to the typical C++ programmer. For example, monadic parsing is
not well suited to my impure design, it does work if you throw an
exception to carry the failure to parse state so it "works", but
nobody should be doing that in any real world code.

I may be wrong in those design tradeoffs and assumptions - just
because I've been working on the right design for over a year (I have
a presentation I did on these design deliberations February 2014 with
many of the same unsolved problems) doesn't mean I am 100% confident
in it being the correct balance between all the exigencies.

However, the AFIO review is in two weeks, and boost-dev wanted a
final AFIO design, so here it is coming best as I can make it.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Vicente J. Botet Escriba
2015-06-29 06:25:14 UTC
Permalink
Le 28/06/15 22:14, Vinícius dos Santos Oliveira a écrit :
> 2015-06-25 22:11 GMT-03:00 Niall Douglas <***@nedprod.com>:
>
>> plus these
>> new specialisations were added:
>>
>> * result<T>: empty/T/error_code (no exception_ptr).
>> * option<T>: empty/T (no error code nor exceptions).
>>
> I like these specialisations. Makes the code clearer.
>
> What do you think about renaming monad to async_monad?
>
>
Please, don't use monad nor async_monad for any class. Monad is a
concept not a type and we need to reserve his use for a library
proposing to work on Monad concepts.

Vicente

_______________________________________________
Unsubscribe & other changes: http://li
Niall Douglas
2015-06-30 14:44:44 UTC
Permalink
On 26 Jun 2015 at 2:11, Niall Douglas wrote:

> This weekend I'll get started on lightweight future-promise which
> derives from monad and indeed is also a basic_monad but with
> different implementation policy class. These future-promise ought to
> be 98% compatible with the WG21 Concurrency TS spec and will be able
> to participate in hetereogeneous when_any/when_all i.e. you can mash
> them in with std::future.
>
> It'll likely take me a week to come up with some benchmarks comparing
> std::future and my future in a 4-SHA256 engine so you can see the
> benefits of the new design. After that I'll replace AFIO's
> std::future with these lightweight futures in its public API, and we
> should be ready to rock for the 17th July when AFIO's review begins.

I have the first set of benchmarks for lightweight non-allocating
futures ready. They aren't final, but they are representative of what
to expect as compared to the STL future-promise. Note these futures
are configured with a *superset* of the facilities of STL
future-promise, so you have all your monadic programming goodness in
there as a lightweight future inherits from basic_monad plus you can
return error_code as well as exception_ptr:

clang 3.7 libstdc++ 4.9: about 3x faster single threaded (~260 CPU
cycles versus ~780) and 3.2x faster multithreaded.

GCC 5.1 libstdc++ 5.1: about 3x faster single threaded (~260 CPU
cycles versus ~780) and 3.7x faster multithreaded.

VS2015: about 6.8x faster single threaded (~243 CPU cycles versus
~1668).


For shared_future things aren't as good due to the shared_ptr.
However:

clang 3.7 libstdc++ 4.9: about 2x faster single threaded (~380 CPU
cycles versus ~780).

GCC 5.1 libstdc++ 5.1: about 2x faster single threaded (~380 CPU
cycles versus ~780).

VS2015: about 2 faster single threaded (~750 CPU cycles versus
~1433).


These are worst case improvements. My next step is future_option<T>,
and that should be dramatically faster than future<T>. I definitely
know it will be at least around the 100 CPU cycle mark, the question
is how much lower I can push it. I'll know in a few days.

Gory detail can be found at
https://github.com/ned14/boost.spinlock/blob/master/Readme.md.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Michael Marcin
2015-07-01 03:37:29 UTC
Permalink
Forgive me if this is dumb I haven't looked at the implementation of a
future/promise solution before and I was curious.

It seems the basic strategy is to have a member variant called
value_storage in both the promise and the future.

Let me see if I can enumerate the flows:

- If you set_value on a promise twice you get an already_set error.

- If you set_value on a promise that noone has gotten the future of you
set the storage of the promise to the value

- If you set_value on a promise that someone has gotten the future of
you set the storage of the future to the value and detach the promise
from the future

- If no one ever gets the future and the value is set then the value
gets destroyed in the promise's storage when the promise is destroyed

- If someone gets the future before the value is set then a future is
constructed and the promise's storage stores a pointer to the future

- If someone gets the future then gets it again while the first future
still exists it throws future_already_retrieved

- If someone gets the future then destroys the future then gets the
future again it is now safe to call get_future again on the promise so
long as the value was never set (This seems rather complicated, is it
necessary?)

- If someone sets the promise value then gets the future this is the
fast path no lock is ever taken, the promise is left detached with empty
storage and the value has been moved to the future's storage

Is this about right?

I'm not sure that _need_locks being changed inside of get_future is
always going to be visible other threads. The documentation says it will
be thread safe after you have called get_future but I don't see anything
that necessarily creates a happens-before relationship between other
threads reading _needs_locks. I am not an expert though.


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Niall Douglas
2015-07-01 10:29:40 UTC
Permalink
On 30 Jun 2015 at 22:37, Michael Marcin wrote:

> Forgive me if this is dumb I haven't looked at the implementation of a
> future/promise solution before and I was curious.
>
> It seems the basic strategy is to have a member variant called
> value_storage in both the promise and the future.
>
> Let me see if I can enumerate the flows:
>
> - If you set_value on a promise twice you get an already_set error.
>
> - If you set_value on a promise that noone has gotten the future of you
> set the storage of the promise to the value
>
> - If you set_value on a promise that someone has gotten the future of
> you set the storage of the future to the value and detach the promise
> from the future
>
> - If no one ever gets the future and the value is set then the value
> gets destroyed in the promise's storage when the promise is destroyed
>
> - If someone gets the future before the value is set then a future is
> constructed and the promise's storage stores a pointer to the future
>
> - If someone gets the future then gets it again while the first future
> still exists it throws future_already_retrieved

Sounds about right so far.

> - If someone gets the future then destroys the future then gets the
> future again it is now safe to call get_future again on the promise so
> long as the value was never set (This seems rather complicated, is it
> necessary?)

That's a bug! So thank you. What should happen is that the future
destructor should set the promise to detached if no value was set.
I'll fix that shortly.

> - If someone sets the promise value then gets the future this is the
> fast path no lock is ever taken, the promise is left detached with empty
> storage and the value has been moved to the future's storage

Until late last night, this was the case. I found I could shave off
15% CPU cycles by removing this optimisation as it makes the output
code less branchy and I'm overloading the branch predictor, so it
makes a big difference. It's still in there for the unit testing to
prevent me writing code which causes failure to constant expression
reduce, but #ifdef'd out by default.

> Is this about right?
>
> I'm not sure that _need_locks being changed inside of get_future is
> always going to be visible other threads. The documentation says it will
> be thread safe after you have called get_future but I don't see anything
> that necessarily creates a happens-before relationship between other
> threads reading _needs_locks. I am not an expert though.

It's a good question, and thank you for taking the time to review the
code and the design.

What you are missing is that we assume that whoever is calling
get_future() must issue some form of memory synchronisation to
transmit the newly constructed future to another thread. That
synchronises the changed _needs_locks to other threads. I suppose it
is possible that someone could send the future to one thread, and
have a different thread do a state read and in theory the state
reading thread doesn't see any new state.

However, that is part of the design in general anyway, and it will be
documented that any examination of promise-future state between
synchronisation points (I have still to document which APIs are
those) may be stale. I've taken care to make sure that unlocked state
reads cannot be racy. Modulo bugs of course.

I have yet to write this up into the docs, but a very strong advice
will be given to not concurrently consume lightweight future promise
from more than one thread. Multiple threads able to set the promise
are fine, but there should be only one thread able to inspect and get
from the future at any one time. Lightweight future-promise should
still be safe to get() from multiple threads concurrently as wait()
synchronises, but any inspection of state from multiple threads
concurrently will be racy.

Any design where multiple threads can consume a future concurrently
is likely a very bad design. Use a shared_future instead where
concurrent get() is intended.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Gavin Lambert
2015-07-01 23:39:58 UTC
Permalink
On 1/07/2015 22:29, Niall Douglas wrote:
> What you are missing is that we assume that whoever is calling
> get_future() must issue some form of memory synchronisation to
> transmit the newly constructed future to another thread. That
> synchronises the changed _needs_locks to other threads. I suppose it
> is possible that someone could send the future to one thread, and
> have a different thread do a state read and in theory the state
> reading thread doesn't see any new state.

The most common case is to transport the promise to another thread
(sometimes via packaged_task) and to return the future on the calling
thread.

I suppose designs that pass the future to another thread instead are
possible but they seem a lot weirder and more convoluted.



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Niall Douglas
2015-07-02 00:46:06 UTC
Permalink
On 2 Jul 2015 at 11:39, Gavin Lambert wrote:

> On 1/07/2015 22:29, Niall Douglas wrote:
> > What you are missing is that we assume that whoever is calling
> > get_future() must issue some form of memory synchronisation to
> > transmit the newly constructed future to another thread. That
> > synchronises the changed _needs_locks to other threads. I suppose it
> > is possible that someone could send the future to one thread, and
> > have a different thread do a state read and in theory the state
> > reading thread doesn't see any new state.
>
> The most common case is to transport the promise to another thread
> (sometimes via packaged_task) and to return the future on the calling
> thread.
>
> I suppose designs that pass the future to another thread instead are
> possible but they seem a lot weirder and more convoluted.

Now locks are always on, and as both promise's and future's move
constructors are acquire release points, transporting either works.

I've documented the exact deviations from the STL in the docs,
copying and pasting from those:

Known deviations from the ISO C++ standard specification:

* No memory allocation is done, so if your code overrides the STL
allocator for promise-future it will be ignored.

* T must implement either or both the copy or move constructor, else
it will static_assert.

* T cannot be error_type nor exception_type, else it will
static_assert.
set_value_at_thread_exit() and set_exception_at_thread_exit() are not
implemented, nor probably ever will be.

* promise's and future's move constructor and move assignment are
guaranteed noexcept in the standard. This promise's and future's move
constructor and assignment is noexcept only if type T's move
constructor is noexcept.

* Only the APIs marked "SYNC POINT" in both promise and future
synchronise memory. Calling APIs not marked "SYNC POINT" can return
stale information, so don't write code which has a problem with that
(specifically, do NOT have multiple threads examining a future for
state concurrently unless they are exclusively using SYNC POINT APIs
to synchronise memory between them).

When might this be a problem in real world code? For example, valid()
which is not a SYNC POINT API may return true when it is in fact
false. If your code uses a synchronisation mechanism which is not a
SYNC POINT API - most usually, this is "synchronised by time/sleep" -
and then executes code which depends on valid() being correct as it
would always be with STL future promise as valid() there synchronises
memory, your code will be racy. The simplest solution is to call any
SYNC POINT API before examining valid(), or issue a memory fence
(std::atomic_thread_fence), or best of all refactor your code to not
use synchronised by time/sleep in the first place. The thread
sanitiser tsan reports any use of time to synchronise as a failure
which is the correct thing to do - just don't do it in your code.

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Gottlob Frege
2015-07-02 18:26:08 UTC
Permalink
On Wed, Jul 1, 2015 at 6:29 AM, Niall Douglas <***@nedprod.com> wrote:
> On 30 Jun 2015 at 22:37, Michael Marcin wrote:
>
>>
>> I'm not sure that _need_locks being changed inside of get_future is
>> always going to be visible other threads. The documentation says it will
>> be thread safe after you have called get_future but I don't see anything
>> that necessarily creates a happens-before relationship between other
>> threads reading _needs_locks. I am not an expert though.
>
> It's a good question, and thank you for taking the time to review the
> code and the design.
>
> What you are missing is that we assume that whoever is calling
> get_future() must issue some form of memory synchronisation to
> transmit the newly constructed future to another thread. That
> synchronises the changed _needs_locks to other threads. I suppose it
> is possible that someone could send the future to one thread, and
> have a different thread do a state read and in theory the state
> reading thread doesn't see any new state.
>

_needs_locks concerned me as well, but I haven't had enough time to
look at it closely (and I have some faith in Niall :-)

Any time there is a flag about locks, but it isn't synchronized, it
look suspicious. My first thought was the same as what Niall is
saying - there will be synchronization elsewhere. But I still think
it needs to be thought through to be sure.

The common case is

future<int> fi = someFunction(a, b, c);

so someFunction() typically builds a promise (or something with a
promise) and gets a future from it, _then_ sends the promise off to
another thread to fulfill the promise (with synchronization happening
when sending it off).

So at that point, the value of _needs_locks, whatever it is, is valid
for both the future thread and the promise thread.

But without looking at all the code, I'm not sure who/what/when
_needs_locks ever changes. Assuming both the promise and the future
side READ it, and one of them can WRITE it, then the writer needs a
release on setting, and the other side needs an acquire on every read.
If only one side can set, the setter side never needs anything beyond
the release, and only needs release after the other side has gone off
onto its own thread.

But I haven't looked at the code enough to know the details of which
cases apply.


As for multiple threads reading the future: No. IIUC, std::future
isn't thread-safe on its own. It can only be used by one thread
(without extra external synchronization). It only guarantees no data
races relative to the other thread holding the promise, not to other
threads trying to read the same future.

Tony

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Niall Douglas
2015-07-03 02:26:47 UTC
Permalink
On 2 Jul 2015 at 14:26, Gottlob Frege wrote:

> But without looking at all the code, I'm not sure who/what/when
> _needs_locks ever changes. Assuming both the promise and the future
> side READ it, and one of them can WRITE it, then the writer needs a
> release on setting, and the other side needs an acquire on every read.
> If only one side can set, the setter side never needs anything beyond
> the release, and only needs release after the other side has gone off
> onto its own thread.

That facility is disabled by default now. It always locks in the APIs
documented "SYNC POINT".

> As for multiple threads reading the future: No. IIUC, std::future
> isn't thread-safe on its own. It can only be used by one thread
> (without extra external synchronization). It only guarantees no data
> races relative to the other thread holding the promise, not to other
> threads trying to read the same future.

This surprises me.

As you saying that if two threads try to get() from a future
concurrently, that both may succeed due to racing?

I had thought that exactly one succeeds and exactly one will receive
a no_state exception throw?

Niall

--
ned Productions Limited Consulting
http://www.nedproductions.biz/
http://ie.linkedin.com/in/nialldouglas/
Gottlob Frege
2015-07-03 21:28:49 UTC
Permalink
On Thu, Jul 2, 2015 at 10:26 PM, Niall Douglas
<***@nedprod.com> wrote:
> On 2 Jul 2015 at 14:26, Gottlob Frege wrote:
>
>> But without looking at all the code, I'm not sure who/what/when
>> _needs_locks ever changes. Assuming both the promise and the future
>> side READ it, and one of them can WRITE it, then the writer needs a
>> release on setting, and the other side needs an acquire on every read.
>> If only one side can set, the setter side never needs anything beyond
>> the release, and only needs release after the other side has gone off
>> onto its own thread.
>
> That facility is disabled by default now. It always locks in the APIs
> documented "SYNC POINT".
>
>> As for multiple threads reading the future: No. IIUC, std::future
>> isn't thread-safe on its own. It can only be used by one thread
>> (without extra external synchronization). It only guarantees no data
>> races relative to the other thread holding the promise, not to other
>> threads trying to read the same future.
>
> This surprises me.
>

Anything else would surprise me. I guess I better go read the
standard though, to be sure...


30.6.6 Class template future

2 [ Note: Member functions of future do not synchronize with
themselves or with member functions of
shared_future. —end note ]


It is a non-normative note, but I suspect that is because the default
throughout the standard is that everything is unsynchronized. So they
don't need to say anything normative to say that future get() is
unsynchronized, but just to be sure, they included a note.

> As you saying that if two threads try to get() from a future
> concurrently, that both may succeed due to racing?
>

Or your cat could get pregnant. ie Undefined Behaviour.

> I had thought that exactly one succeeds and exactly one will receive
> a no_state exception throw?
>

UB.

I could still be wrong. There might be other parts that say
otherwise, but I couldn't find them. We could ask the committee I
suppose.

Tony

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/l
Loading...