*f*:

*T*

_{1}→

*T*

_{2}→ ··· →

*T*→

_{n}*R*

lift

*(*_{M}*f*) :*MT*_{1}→*MT*_{2}→ ··· →*MT*→_{n}*MR*
with the following behavior:

lift

*(*_{M}*f*)(*m*_{1}, ... ,*m*_{n}) :=*m*_{1}>>= λ*t*_{1}.(*m*_{2}>>= λ*t*_{2}.( ··· (*m*>>= λ_{n}*t*.return_{n}*(*_{M}*f*(*t*_{1}, ... ,*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

*) and injecting a monadic object into a non-monadic to monadic function*_{M}*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

*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.*_{M}
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
, 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>._{M}

At first blush it could seem like this can be directly implemented by translating the definition lift

*to C++ via lambda functions and std::bind, but in fact it cannot, because std::bind is not curry-compatible,*_{M}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.

## No comments :

## Post a Comment