Sunday, March 9, 2014

Monadic lifting is the process of transforming a (curryed) n-ary function
f : T1 T2 ··· Tn R
into a function liftM(f) with domain and range in the type system associated to a monad M:
liftM(f) : MT1 MT2 ··· MTn MR
with the following behavior:
liftM(f)(m1, ... , mn) :=
m1 >>= λt1.(m2 >>= λt2.( ··· (mn >>= λtn.returnM(f(t1, ... , tn)))···).
(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 (returnM) 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). returnM 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 liftM, 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 liftM 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.