Re: [boost] [thread, async] Mini design review requested for a generic extensible Boost monadic continuations framework

Subject: Re: [boost] [thread, async] Mini design review requested for a generic extensible Boost monadic continuations framework
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 2014-03-05 07:54:57

Le 03/03/14 15:16, Niall Douglas a écrit :
> Dear Boost,
>
> I've been working on a Boost generalisation framework for N3857
> "Improvements to std::future<T> and Related APIs" (Jan 2014). It's
> also an extension of Vicente's N3865 "More Improvements to
> std::future<T>" (Jan 2014), though slightly incompatible with it. I
> would appreciate the Boost community's feedback on what is
> essentially pure exploratory prototype code before I commit any major
> design flaws in a proper implementation.
>
> The proposed design is specifically intended to allow proposed
> Boost.AFIO's async_io_op future-like object to seamlessly
> interoperate with any other future-like object e.g. std::future<T> or
> boost::future<T>. The design is intended to be extensible to any
> other third party future-like object, even including ones whose
> implementation is completely external (e.g. Qt).
>
> I would like to thank some people whose off-list discussions helped
> inform this design: to Bjorn Reese who has done so much to help me
> knock the kinks out of AFIO; to Vicente J. Botet Escriba for engaging
> with me pitching this proposal to him (he disagrees with it by the
> way); to Artur Laksberg and Niklas Gustafsson for continuing to reply
> to my criticisms and thoughts of the papers which precede N3857.
Niall, thanks for this more explanatory description of what you have in 
mind.
I think that our positions are closer than I believed after our private 
exchanges.
>
> What N3857 proposes for reference:
>
> * future<T> and shared_future<T> gain a .then(R(prec_future_type<T>))
> method. Callable will be called with the signalling future after the
> future signals. Return type is a future<R>.
>
> * A new when_all(...) can be used to compose a future which signals
> when all input futures are signalled. Inputs can be futures of
> heterogeneous types, in which case a future<tuple<...>> is returned.
>
> * A new when_any(...) composes a future which signals when any of its
> input futures signals. Inputs can be futures of heterogeneous types,
> in which case a future<tuple<...>> is returned. To avoid the linear
> scan on return, for a homogeneous types a when_any_swapped(...) swaps
> the last item in the return value with the ready item. Note there is
> no way in N3857 to avoid a when_any() linear scan when input types
> are heterogenous (something I feel is a deficiency, all you need to
> return is an index!).
I guess that this point could be discuss in std-proposals ML.
> <snip>
>
> Where I find issue with a naïve implementation of N3857 (and
> Vicente's N3865 mentions some of these same issues):
>
> * N3857 only understands std::future<> and std::shared_future<>. That
> means the following code will not compile:
>
> std::future<int> &a;
> boost::future<int> &b;
> boost::afio::async_io_op &c;
> std::future<std::tuple<int, int, std::shared_ptr<async_io_handle>>>
> f=when_all(a, b, c);
>
> This is unhelpful for interoperation. It doesn't just affect Boost:
> imagine mashing up Qt async objects and C++17 objects for example, or
> even WinRT Task<T> objects and C++17 objects. Most C++ (and C)
> libraries of any complexity supply their own async notification
> objects, and this problem of writing never ending boilerplate to get
> some async object from library X to work with library Y is very
> tedious considering the compiler can do it for you.
I have some doubts on who we can decide that the result of such an 
operation would be

std::future<std::tuple<int, int, std::shared_ptr<async_io_handle>>>

>
> * As I mentioned earlier, when_any() is suboptimal when called with
> heterogenous types. I don't particularly like the when_any_swapped()
> hack either - a better solution would solve when_any() of all kinds
> optimally.
Make a proposal on std-proposals then.
>
> * The .then(R(prec_future_type<T>)) is not tremendously useful in
> practice because it's too limited. Witness the very common use
> pattern of this form:
>
> auto ret=openedfile
> 	.then(write({ "He", "ll", "o ", "Wo", "rl", "d\n" }, 0))
> 	.then(sync());
> 	.then(write({ "He", "ll", "o ", "Wo", "rl", "d\n" }, 12))
> 	.then(sync());
>
> This sequence of code is clearly a *transaction* i.e. the programmer
> intends the set of continuations as a contained group of operations,
> and indeed some async i/o providers may guarantee atomic rollback
> (hint: forthcoming TripleGit does exactly this). A big additional
> problem is the lack of error handling logic: if say the second
> write() fails, you may wish to undo the first write, or do something
> custom. The problem with N3857 is that only the state of the first
> sync() is passed into the second write, and it may be the case that
> in generic code sync() needs to always sync irrespective of its
> preceding operation and therefore might pass through a garbage state.
> N3857 provides no easy method for a later .then() to inspect
> preceding .then()'s and do something about them (e.g. rewinding until
> it finds a valid open file handle rather than error states), other
> than by declaring special wrapper lambdas to pass through state. I
> personally think that is ugly.
Here is when I disagree the most on your proposal. I think that 
transactions are orthogonal to the future class and the user could 
return whatever she wants from its continuations.
Maybe you need to implement some kind of Monad State.

>
>
> * Vicente mirrors my point above in N3865 by pointing out that having
> .then(R(prec_future_type<T>)) push the error handling into the
> callable makes your callables unnecessarily boilerplate. N3865
> proposes adding .next(R(prec_future_type<T>)) for when a preceding
> operation succeeds and .recover(R(exception_ptr)) for when a
> preceding operation fails, with .fallback_to(value) as a way of
> default setting the return from an errored future.
>
> I think Vicente's argument here is a good one: but it's not generic
> enough in my opinion. I think continuations should be able to
> _filter_ outputs from preceding continuations in a really generic and
> customisable way. What I'd really like is this:
>
> continuations::thenable_get_placeholder<-1> last;
> auto ret=openedfile
> 	.then(write({ "He", "ll", "o ", "Wo", "rl", "d\n" }, 0))
> 	.then(if_error(last, [](future<...> f){ do something with last; }))
> 	.then(sync());
> 	.then(write({ "He", "ll", "o ", "Wo", "rl", "d\n" }, 12))
> 	.then(if_error(last, [](thenable<...> t){ do something more with
> everything; }))
> 	.then(sync());
Could you clarify what prevents you from doing this with the current 
proposals?
> Which treats the continuation as a functional transformation. In
> other words, Vicente's .recover(R(exception_ptr)) becomes tag
> dispatched instead of explicitly specified, so it's very easy for the
> programmer to transform state according to state.
I have been discussing something similar lastly on c++-parallel ML. I 
was suggesting something as if_valued/if_unexpected.
I have implemented it first on Boost.Expected.
>
>
> What I am proposing instead: a generic extensible Boost monadic
> continuations framework which via metaprogramming lets the compiler
> assemble the right code from N3857 like syntax. A quick summary of
> the proposed generic extensible Boost monadic continuations framework
> follows:
>
> * Future-like behaviours such as .valid(), .then(), .get(), .wait()
> and .share() have functional mixin classes of the form (simplified
> for brevity, but you get the picture):
>
> namespace boost { namespace continuations {
>
>     // Indicates the derived type provides a future compatible valid()
>     template<class I> struct validable : public I
>     {
>        bool valid() const;
>     };
>
>     // Indicates the derived type provides a future compatible then()
>     template<class I, class... Types> struct thenable : public I
>     {
>        template<class F> thenable<decltype(F(...))>, Types..., I>
> then(F &&f);
>     };
>
>     // Indicates the derived type provides a future compatible get()
>     template<class T, class I> struct gettable: public I
>     {
>        T get();
>     };
>
>     // Indicates the derived type provides a future compatible wait()
>     template<class I> struct waitable: public I
>     {
>        void wait() const;
>        template<class Rep, class Period> std::future_status
> wait_for(const std::chrono::duration<Rep,Period> &timeout_duration)
> const;
>        template<class Clock, class Duration> std::future_status
> wait_until(const std::chrono::time_point<Clock,Duration>
> &timeout_time) const;
>     };
>
> } }
>
> To mark up a type as being future-like, one might use:
>
> namespace boost { namespace continuations {
>
>     template<class T> using monad = thenable<waitable<gettable<T,
> validable<std::future<T>>>>>;
>     // Do all the partial specialisations of the internal machinery
>     // for this type to hook it into the metaprogramming
>
> } }
> // Voila, boost::continuations::monad<T> is now an interoperable
> // form of std::future<T>
I have also proposed something like that could be used as

monad_error(f).when_valued(g).when_unexpected(h);

or as

monad_error(f) & g | h;

I have a prototype implementation on one of the examples in Boost.Expected.
>
> * .then() can now take callables of the following forms:
>
> 1. R() and R(prec_future_type<T>) for compatibility with N3857.

IMO N3857 doesn't allows callables as R(). Neither Boost.Thread. But Boost.Expected allow it for expected<void> when using .next().

>
> 2. R(..., continuations::thenable_get_placeholder<idx>, ...) inserts
> an item from the continuation chain into the call.
> thenable_get_placeholder can be fed a negative number to wrap from
> the bottom, so thenable_get_placeholder<-1> is the most recently
> preceding operation. Therefore R(prec_future_type<T>) from above is
> actually implemented as
> R(continuations::thenable_get_placeholder<-1>). This can be used to
> insert error processing filters as illustrated earlier which can view
> a preceding chunk of chain at once, and act.
I don't understand this completely, but I suspect that what you are 
proposing is some variation of Monad state and an adaptor that extracts 
part of the state.
>
> 3. R(thenable<...> &&) which gives a continuation access to the
> entire continuation chain, just for those people who really need it.
> You saw this in the example above.
Again, this is more a kind of monad state that accumulates the results 
of each continuation.
>
> 4. Any specially treated prototype depending on what the
> metaprogramming has extended for some future_type. For example, if
> one does async_io_op.then(void(const boost::system::error_code&
> error, size_t bytes_transferred)) - which is the ASIO callback spec -
> then AFIO would emulate the ASIO callback calling convention for the
> completion of some i/o. This only happens if and only if the item
> being .then() is an async_io_op i.e. such custom extensions are type
> specific.
You lost me here.
>
> * future_type<T>.then(R()) now returns a thenable<future_type<R>,
> future_type<T>> which auto decays to a future_type<R> on demand for
> compatibility with N3857. Similarly a
> future_type<T>.then(R()).then(S()) would return a
> thenable<future_type<S>, future_type<T>, future_type<R>> and so on.
> You can convert a thenable<T, ...> into a std::tuple<..., T> using an
> overload of the make_tuple() function.
Monad state again.
>
> * when_all() and when_any() gain overloads for thenable<...>. These
> simply convert the tuple taken out of a thenable chain into a future
> with the results - AFIO will implement this generically using its
> closure engine, but a more intelligent solution might decompose all
> inputs into HANDLEs and do an asynchronous WaitForMultipleObjects()
> for example.
As I said above, why the result will be a future?
>
> Note this is a BREAKING CHANGE from N3857: If you do a when_all()
> under N3857 on a .then() chain, you will get a future to the last
> then() return, whereas under this proposal you will get a future to
> all the returns from all the then()s. This breaking change may still
> actually compile and work as expected - however when_any() actually
> now has completely different behaviour: when_any() under N3857 will
> be the same effect as when_all() on a .then() chain under N3857,
> whereas under this proposal when_any() will signal when any of the
> then() chain signals (I would assume the first item). I personally
> doubt this breaking change would affect any real world code, but it's
> worth noting.
>
>
> Note the following:
>
> 1. The proposed continuations framework, despite being monadic, is
> separate from the mooted Boost.Functional/Monads framework. This
> continuations framework could be implemented using such a
> Boost.Functional/Monads framework, but I suspect there wouldn't be
> much gain except interoperability with other monadic patterns.
> Continuation monads are a very limited specialisation of general
> monads, especially under the tight constraints of the N3857
> requirements, so reuse of any Boost.Functional/Monads I suspect would
> be minimal.
I think that the Boost.Functional/Monads framework I had in mind could 
be used for your use case. All you need to do is to define a specialized 
Monad, that in your case is close to a Monad State.
> 2. The proposed framework is 100% compatible with N3857 apart from
> the when_all()/when_any() breakages which I would assume shouldn't
> turn up in real world code, and it should be viewed as a
> Boost-specific extension which may get standardised later if it
> proves popular.
>

I have no problem in proposing a different interface as IIUC your 
proposal, the user would need to wrap the std::future, boost::expected, 
... or whatever AFIO monad or use specific 
monads::when_all/monads::when_any function.

I hope that my comments would help you to clarify my discrepancies about 
your design. Resuming,
I think that you must define your own monad state that could be seen as 
any other monad using the functional/monads framework.

> Here is the very rough prototype code:
> https://github.com/BoostGSoC/boost.afio/blob/monadic_continuations/lib
> s/afio/test/tests/monadic_continuations_test.cpp.
> It compiles using VS2013 only. It probably doesn't work, but it's
> simply there
> to demonstrate the viability of the concept and to help those
> confused by my
> unclear explanation above.
>
> Thoughts regarding the design much appreciated! My thanks in advance.
>
> Niall
>
>
I will inspect your code in order to see if I've understood your needs 
as soon as I have enough time.

Best,
Vicente