Lightweight Continuation Passing in C++

8 minutes

2018 NOTE: This post describes software that is no longer maintained. It is kept here for posterity

MNMLSTC Core is starting to near its 1.2 release target, and this will most likely be the last version that targets C++11 and may be the last non-bugfix release for the 1.x series. There are many reasons for this, but the primary one is the difficulty that exists in implementing C++17 proposals without C++14 language features.

Before I move on to begin work on 2.0, I’m going to be adding several extensions to the proposals that Core already implements. Specifically, I’ll be adding extensions to the optional types. As of right now, the match member function provided for all core::variant<Ts...> is now available for all optional types that Core provides (optional<T>, expected<T>, and result<T>). However, this post is about a different feature that I’ll be adding and it may be one that doesn’t exist beyong the 1.x series. Please note that this post makes extensive use of C++14 library features that are implemented in MNMLSTC Core, as well as the extensions it provides (namely result<T>). In addition, the code contained within is not 100% correct, and should be approached as though it were psuedo code.

The recent expected<T, E> proposal encompasses both the use case of expected<T> and result<T>. The proposal discusses using a set of member functions to ‘bind’ or ‘map’ a function to the potential value in the expected<T> type:

expected<int, error_condition> f (int i, int j, int k) {
  return safe_divide(i, k).bind([=] (int q1) {
    return safe_divide(j, k).bind([=] (int q2) { return q1 + q2; });
  });
}

This is all well and good (as they are monadic operations and the proposal discusses a monadic type), but these aren’t the words that we use in C++, and they aren’t what I internally verbalize when reading. Instead, I think of the phrase “and then”. I noticed when reading the code aloud, that I would often say “This function returns X and then…”. I know I’m not alone in this train of thought, as std::future had a proposed then member function, and even boost::future provides a member function by the same name. While the expected proposal does give a then member function, it is simply an alias to bind, and the rest of the proposal uses bind instead of then in its terminology.

I was curious thoug. Could I have the actual expression and then used in my code for a continuation? In short, yes, and I’ve broke a generally agreed upon rule regarding operator overloading to do it.

Let’s assume someone wrote a posix wrapper for basic file io that looks like the following:

#include <core/optional.hpp>
#include <system_error>
#include <unistd.h>
#include <fcntl.h>

using core::make_result;
using core::result;

using ::std::error_condition;
using ::std::system_category;
using ::std::size_t;

namespace posix {
  using descriptor = int;

  result<descriptor> open (char const* path, int flags) noexcept {
    auto fd = ::open(path, flags);
    if (fd == -1) { return make_result<descriptor>(errno, system_category()); }
    return fd;
  }

  result<descriptor> write (descriptor fd, void const* buf, size_t n) noexcept {
    auto res = ::write(fd, buf, n);
    if (res == -1) { return make_result<descriptor>(errno, system_category()); }
    return fd;
  }

  result<void> close (descriptor fd) noexcept {
    auto res = ::close(fd);
    if (res == -1) { return make_result<void>(errno, system_category()); }
    return error_condition { };
  }

} /* namespace posix */

We now have two options. We can make our continuation passing look like this:

auto result = posix::open("file.bin", O_RDWR | O_CREAT)
                and then([] (descriptor fd) { return posix::write(fd, "data", 4); })
                and then([] (descriptor fd) { return posix::write(fd, "asdf", 4); })
                and then([] (descriptor fd) { return posix::close(fd); });

or take the expected<T, E> proposal like this:

auto result = posix::open("file.bin", O_RDWR | O_CREAT)
                .bind([] (descriptor fd) { return posix::write(fd, "data", 4); })
                .bind([] (descriptor fd) { return posix::write(fd, "asdf", 4); })
                .bind([] (descriptor fd) { return posix::close(fd); });

Yes, that is an overloaded operator and, and I will be showing how this is implemented, rather than the .bind member function way. The primary reason that I’m showing the and then([]{}) form is because it doesn’t require an implementation to ship it. We can instead rely on Argument Dependent Lookup to extend the functionality of a given optional type, and provide this functionality in a separate library. As an aside, I am aware that this example discusses the result<T> type found in Core, but this approach could work for an expected, optional, or any other potentially “monadic” type.

All that the then function has to do is generate a functor that does the heavy lifting. It’s quite simple:

template <class C>
auto then (C&& c) -> impl::then_functor<C> {
  return impl::then_functor<C> { std::forward<C>(c) };
}

The real heavy lifting comes from the implementation of the then_functor, which isn’t all that difficult to being with (sans some basic checking for constructibility).

namespace impl {

using core::enable_if_t;
using core::result_of_t;
using core::meta::any;
using core::result;
using core::invoke;

template <class C>
struct then_functor final {
  template <class T>
  auto operator () (result<T>& opt) -> enable_if_t<
    std::is_constructible<result<T>, result_of_t<C(decltype(*opt))>>::value,
    result<T>
  > {
    if (not opt) { return opt.condition(); }
    return invoke(this->call, *opt);
  }
  
  template <class T>
  result<T> const operator () (result<T> const& opt) -> enable_if_t<
    std::is_constructible<result<T>, result_of_t<C(decltype(opt))>>::value,
    result<T> const
  > {
    if (not opt) { return opt.condition(); }
    return invoke(this->call, *opt);
  }
  
  C call;
};
 
} /* namespace impl */

Of important note here, is that we do not attempt to unwrap the return value of invoke sice we do ont, for simplcity’s sake, have the ability to deal with a result<result<T>>, although I may modify the constructor of Core’s optional types to permit this sort of conversion manually (i.e., converting a result<T> to an expected<T>). If the function that is called by the fuctor returns a result<T>, then we simply pass that along as a return value but we also permit the function to simply return a T or a U.

And now, for the coup de grace, we finally implement the operator and overload:

using core::forward;
using core::result;
using core::invoke;

template <class T, class F>
result<T> operator and (result<T>& opt, then_functor<F>&& f) {
  return invoke(forward<then_functor<F>>(f), opt);
}

template <class T, class F>
result<T> operator and (result<T> const& opt, then_functor<F> const& f) {
  return invoke(f, opt);
}

} /* namespace impl */

And that is how the origial example is implemented. Combined, we get the following:

#include <iostream>

#include <core/type_traits.hpp>
#include <core/optional.hpp>
#include <unistd.h>
#include <fcntl.h>

using core::make_result;
using core::result;

using ::std::error_condition;
using ::std::system_category;
using ::std::size_t;

namespace posix {

using descriptor = int;

result<descriptor> open (char const* path, int flags) noexcept {
  auto fd = ::open(path, flags);
  if (fd == -1) { return make_result<descriptor>(errno, system_category()); }
  return fd;
}

result<descriptor> write (descriptor fd, void const* buf, size_t n) noexcept {
  auto res = ::write(fd, buf, n);
  if (res == -1) { return make_result<descriptor>(errno, system_category()); }
  return fd;
}

result<void> close (descriptor fd) noexcept {
  auto res = ::close(fd);
  if (res == -1) { return make_result<void>(errno, system_category()); }
  return error_condition { };
}

} /* namespace posix */


namespace impl {

using core::enable_if_t;
using core::result_of_t;
using core::forward;
using core::invoke;

template <class F>
struct then_functor final {

  template <class T>
  auto operator () (result<T>& opt) -> enable_if_t<
    std::is_constructible<result<T>, result_of_t<F(decltype(*opt))>>::value,
    result<T>
  > {
    if (not opt) { return opt.condition(); }
    return invoke(this->call, *opt);
  }

  template <class T>
  auto operator () (result<T> const& opt) const -> enable_if_t<
    std::is_constructible<result<T>, result_of_t<F(decltype(*opt))>>::value,
    result<T> const
  > {
    if (not opt) { return opt.condition(); }
    return invoke(this->call, *opt);
  }

  F call;
};

template <class T, class F>
result<T> operator and (result<T>& opt, then_functor<F>&& f) {
  return invoke(forward<then_functor<F>>(f), opt);
}

template <class T, class F>
result<T> operator and (result<T> const& opt, then_functor<F> const& f) {
  return invoke(forward<then_functor<F>>(f), opt);
}

} /* namespace impl */

template <class F>
impl::then_functor<F> then (F&& f) {
  return impl::then_functor<F> { core::forward<F>(f) };
}

int main () {
  using posix::descriptor;
  auto result =
   posix::open("file.bin", O_RDWR | O_CREAT)
     and then([] (descriptor fd) { return posix::write(fd, "data", 4); })
     and then([] (descriptor fd) { return posix::write(fd, "asdf", 4); })
     and then([] (descriptor fd) { return posix::close(fd); });
  if (not result) {
    std::clog << "An error has occurred: "
              << result.condition().message()
              << std::endl;
    return EXIT_FAILURE;
  }
}

It goes without saying that there are a lot of ways that this can be improved. For starters, we shouldn’t have to continue callong on each of the then_functor<F> instances if we fail early, however, I don’t know of any way to permit a different result<U> as a possible return type while also permitting this ’early cancellation’, while also flattening embedded result<result<result<result<...>>>>, which can get hair in the event of an error, though I have a few ideas with which to approach it. Additioally, if the proposal allowing exceptions to pass file or line number information goes through (which it should, because it’s a great idea), this would allow us to inform the user as to when the error occurred. As it stands now, with both the Core and then and the expected<T, E>, there is no way to inform the consumer of an API when a failure occurred during the various passing, unless they are familiar with the internals, and I find this to be a defect of API desig, but I am not here to make them. That’s a different post for a different time.

While I’ll be taking some time to clean up and polish the and then approach, I wanted to give a brief “sneak peek” of a possible approach to continuation passing with optional types in C++11/C++14.

C++

optional