Monadic lifting in C++

Monadic lifting is the process of transforming a (curryed) n-ary function

f : T₁ → T₂ → ··· → T_n → R

into a function lift_M(f) with domain and range in the type system associated to a monad M:

lift_M(f) : MT₁ → MT₂ → ··· → MT_n → MR

with the following behavior:

lift_M(f)(m₁, ... , m_n) :=
m₁ >>= λt₁.(m₂ >>= λt₂.( ··· (m_n >>= λt_n.return_M(f(t₁, ... , t_n)))···).

(We are using lambda notation here.) This looks more complex than it really is: lifting is basically translating a function into the realm of a monad by using the only mechanisms monads allow us to process their values, namely creating a monadic object from a non-monadic value (return_M) and injecting a monadic object into a non-monadic to monadic function f : T → MR via binding (denoted by >>=). The resulting scheme complies with a key design aspect of monads: we are not supposed to unwrap and rewrap them at will, but this is something only the monadic code can do within the implementation of >>=. 

So, let us implement monadic lifting in C++. The following is a minimal monadic framewok plus an implementation of the famous Maybe monad. For brevity of exposition, C++14 automatic return type deduction is used.

struct mvoid{};

template<template<typename> class M,class T>
M<T> mreturn(T&& t)
{
  return std::forward<T>(t);
}

// maybe built on top of boost::optional
// maybe<T>(t) is Just t, boost::none acts as Nothing

template<typename T>
struct maybe:boost::optional<T>
{
  using super=boost::optional<T>;
  using super::super;
};

template<typename T,typename F>
auto operator>>=(const maybe<T>& m,F&& f)
{
  return m?f(m.get()):boost::none;
}

template<typename T,typename F>
auto operator>>=(maybe<T>& m,F&& f)
{
  return m?f(m.get()):boost::none;
}

Within this framework, a monad is a class template M mapping underlying types T to their associated monadic types M<T>, plus corresponding overloads of operator>>= (non-const monadic objects, which are alien to functional programming, are accepted here). return_M is provided by the framework (i.e. it need not be written by the monad implementer) on the assumption that M<T> can be constructed from T. The other C++-specific addition is mvoid: while in functional programming all functions return something, C++ functions can return void, which is not a proper type with associated values: we will accommodate this difficulty by lifting void-returning functions into monadic functions returning M<mvoid>s.

The task at hand is then implementing

template<template<typename> class M,typename F>
mlifted<M,F> mlift(F&& f);

with the following properties:

•  If F is callable with arguments T1, ... , Tn, then mlifted<M,F> is callable with arguments M1, ... , Mn, where each Mi is either Ti or M<Ti>, and the return type is M<std::result_of(F(T1,...,Tn))> (or M<mvoid> if F does not return a value).
• Constness is propagated from Ti to Mi. All arguments are accepted by lvalue reference: rvalue references and move semantics do not play well with monadic code where the underlying functions can be invoked internally more than once (for instance, with collection monads).
• The behavior of mlifted<M,F> follows the formal definition of lift_M, with the additional provisions that 1) non-monadic values are passed directly to the invocation of F and 2) if F returns void then it is executed internally as a side effect previously to returning M<mvoid>.

At first blush it could seem like this can be directly implemented by translating the definition lift_M to C++ via lambda functions and std::bind, but in fact it cannot, because std::bind is not curry-compatible,

int foo(int x,int y);
...
auto f=std::bind(foo,5);
f(6); // error: no match for call to std::bind<...>

that is, if the underlying function is n-ary, specifying m binding arguments does not produce a (m-n)-ary callable entity, which greatly complicate things for our task. So, we have to implement mlifted on our own. This is the general outlook of our solution:

template<template<typename> class M,typename F>
struct mlifted
{
  mlifted(const F& f):f(f){}
  mlifted(F&& f):f(std::move(f)){}
  
  template<typename ...Args>
  auto operator()(Args&&... args)
  {
    mlifted_call_context<M,F,Args...> context(f,args...);
    return context();
  }
  
private:
  F f;
};

template<template<typename> class M,typename F,typename ...Args>
struct mlifted_call_context
{
  static const std::size_t num_args=sizeof...(Args);
  
  mlifted_call_context(F& f,Args&... args):
    f(f),args(std::make_tuple(&args...)){}
  
  auto operator()()
  {
    mlifted_call_stage<M,mlifted_call_context,num_args>
     stage(*this);
    return stage();
  }
  
  F& f;
  std::tuple<
    typename std::remove_reference<Args>::type*...>
    args;
  std::tuple<
    mwrapped_t<M,typename std::remove_reference<Args>::type>*...>
    postargs;
};

mlifted::operator(M1,...,Mn) creates a call context with two sets of arguments:

• A tuple of pointers to M1, ..., Mn.
• A tuple of pointers to the postprocesed args T1, ..., Tn, where each Ti is either Mi in the case of non-monadic values or else the value generated by Mi during its binding (determining this underlying type is accomplished with mwrapped_t, whose simple implementation is not described).

Execution resolves then to a recursive call to

mlifted_call_stage<...,n> → ... → mlifted_call_stage<...,0>,

each taking care of the (n-i)-th argument until the final invocation of F once all Tis are resolved:

template<
  template<typename> class M,typename Context,std::size_t N
>
struct mlifted_call_stage
{
  static const std::size_t I=Context::num_args-N;
  
  mlifted_call_stage(Context& c):c(c){}
  
  auto operator()(){return operator()(*std::get<I>(c.args));}
  
  template<typename T> auto operator()(T&& t)
  {
     std::get<I>(c.postargs)=&t;
     mlifted_call_stage<M,Context,N-1> next(c);
     return next();
  }
  template<typename T> auto operator()(const M<T>& m)
  {
    return m>>=*this;
  }
  template<typename T> auto operator()(M<T>& m)
  {
    return m>>=*this;
  }

  Context& c;
};

template<template<typename> class M,typename Context>
struct mlifted_call_stage<M,Context,0>
{  
  mlifted_call_stage(Context& c):c(c){}
  
  auto operator()(){return apply_pointer_tuple(c.f,c.postargs);}
};

The actual code is a little more complicated so as to deal with the mvoid issue, and some portions, like the implementation of apply_pointer_tuple, have been omitted here, but the general idea is rather simple and there is not too much execution overhead involved (ideally, a compiler could strip most of the scaffolding away): in particular, no dynamic memory allocation is used. The entire implementation is available online; a C++11 compiler with C++14 automatic return type detection (usually via the -std=c++1y compiler option) is needed to run it.

So equipped, we can play a bit with mlift (more examples are given in the program):

int foo(int x,int y){return x*y;}
...
auto mfoo=mlift<maybe>(&foo);

mfoo(maybe<int>(2),maybe<int>(3));  // maybe<int>(6)
mfoo(2,maybe<int>(3));              // maybe<int>(6)
mfoo(
  maybe<int>(4),
  mfoo(2,maybe<int>(3)));           // maybe<int>(24)
mfoo(maybe<int>(boost::none),3);    // maybe<int>(boost::none)
mfoo(
  maybe<int>(4),
  mfoo(maybe<int>(boost::none),3)); // maybe<int>(boost::none)

This snippet is admittedly trivial, but the framework is entirely generic and works with monads and functions of arbitrary complexity. In a later entry we will explore the possibilites of monadic lifting within slot-based progamming.