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

Subject: [boost] [thread, async] Mini design review requested for a generic extensible Boost monadic continuations framework
From: Niall Douglas (s_sourceforge_at_[hidden])
Date: 2014-03-03 09:16:41

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.

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!).

* A new executor base class, with subclass thread_pool are added. 
Executors allow adding a std::function<void()> for asynchronous 
execution. These are detailed by N3785 "Executors and schedulers, 
revision 3" (Oct 2013). I haven't mentioned in detail here, but N3857 
specifies overloads for .then(executor, ...) to send some 
continuation to some executor. You will note the below framework 
makes it possible to use tag dispatch instead which looks much 
cleaner and is easier to write, nevertheless this explicit form is 
intended to be preserved. I won't mention executor support again for 
brevity.

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.

* 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.

* 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.

* 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());

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.

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>

* .then() can now take callables of the following forms:

1. R() and R(prec_future_type<T>) for compatibility with N3857.

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.

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.

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.

* 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.

* 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.

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.

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.

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

-- 
Currently unemployed and looking for work in Ireland.
Work Portfolio: http://careers.stackoverflow.com/nialldouglas/