## Friday, November 30, 2012

### Arrows and Kleisli in C++

Control.Arrow shows an odd-but-interesting part of Haskell. Arrows are functions; composable and callable. Arrows and Monads sometimes seem to be referred to as alternatives to each other. Perhaps now would be a good time to relate some category theory.

#### From A to B.

A category theorist might view functions as a transformation from one type to another. For example,

std::to_string : X -> std::string

would mean that to_string is a function that maps an X to a string.

In "Generic Function Objects", I talked about type constructors.

/* MakeT T : X -> T<X> */
template< template<class...> class T > struct MakeT {
template< class ...X, class R = T< typename std::decay<X>::type... > >
constexpr R operator () ( X&& ...x ) {
return R( std::forward<X>(x)... );
}
};

/* pair : X x Y -> std::pair<X,Y> */
constexpr auto pair = MakeT<std::pair>();

I use the notation X x Y to mean that MakeT<pair> takes two arguments. Though, in Haskell, it would actually look like this:

make_pair :: X -> Y -> (X,Y)

Haskell uses curried notation.

g : pair<X,A> -> pair<X,B>

Here, g is a function that transforms the second element of the pair to a B, but leaves the first as an X. Although this cannot be inferred from the definition, let's assume that the first value (X) is not transformed in any way. There is a function that represents this non-transformation.

/* id : X -> X */
constexpr struct Id {
template< class X >
constexpr X operator () ( X&& x ) {
return std::forward<X>(x);
}
} id{};

Arrows provide the tools to take a normal function, f : A -> B, and convert it to a function like g. This is sort of like composition

/* compose : (B -> C) x (A -> B) -> (A -> C) */
template< class F, class G >
struct Composition
{
F f; G g;

template< class _F, class _G >
constexpr Composition( _F&& f, _G&& g )
: f(std::forward<_F>(f)), g(std::forward<_G>(g)) { }

template< class X >
constexpr auto operator() ( X&& x)
-> decltype( f(g(std::declval<X>())) )
{
return f( g( std::forward<X>(x) ) );
}
};

constexpr auto compose = MakeT<Composition>();

If we look at A -> B as a type itself, say AB, and B -> C as a type, BC, then it is clear that composition is BC x AB -> AC. Functions themselves are values with types and composition creates a new value and type. We can think of them as being on a geometric plain with the points A, B, and C. Functions are connections from point-to-point. Similarly, we can think of AB, BC, and AC as points on a different plain with arrows connecting AB and BC to AC (though AB and BC cannot be connected).

#### Functions as Arrows.

Arrows have several operations. The first is arr, which transforms a function to an arrow; but since functions are arrows, it isn't useful, right off the bat. first and second take functions, A -> B, and lift them to pair-oriented functions. fan takes two functions, one A -> B, another A -> C, and returns a function to pair<B,C>. split takes two functions as well, A -> B and X -> Y, and returns a function pair<A,X> -> pair<B,Y>.

arr : (A -> B) -> (A -> B)
first : (A -> B) -> (pair<A,X> -> pair<B,X>)
second : (A -> B) -> (pair<X,A> -> pair<X,B>)
split : (A -> B) x (X -> Y) -> (pair<A,X> -> pair<B,Y>)
fan : (A -> B) x (A -> C) -> (A -> pair<B,C>)

First, we fill in the declarations.

template< class A, class F, class Arr = Arrow< Cat<A> > >
constexpr auto arr( F&& f ) ->  decltype( Arr::arr( std::declval<F>() ) )
{
return Arr::arr( std::forward<F>(f) );
}

template< class A > struct Arr {
template< class F >
constexpr auto operator () ( F&& f ) -> decltype( arr(std::declval<F>()) )
{
return arr( std::forward<F>(f) );
}
};

constexpr struct Split {
template< class F, class G, class A = Arrow<Cat<F>> >
constexpr auto operator () ( F&& f, G&& g )
-> decltype( A::split(std::declval<F>(), std::declval<G>()) )
{
return A::split( std::forward<F>(f), std::forward<G>(g) );
}
} split{};

constexpr struct Fan {
template< class F, class G, class A = Arrow<Cat<F>> >
constexpr auto operator () ( F&& f, G&& g )
-> decltype( A::fan(std::declval<F>(),std::declval<G>()) )
{
return A::fan( std::forward<F>(f), std::forward<G>(g) );
}
} fan{};

constexpr struct First {
template< class F, class A = Arrow<Cat<F>> >
constexpr auto operator () ( F&& f )
-> decltype( A::first(std::declval<F>()) )
{
return A::first( std::forward<F>(f) );
}
} first{};

constexpr struct Second {
template< class F, class A = Arrow<Cat<F>> >
constexpr auto operator () ( F&& f ) -> decltype( A::second(std::declval<F>()) ) {
return A::second( std::forward<F>(f) );
}
} second{};

arr will be trivial to implement, but the others are tricky. Luckily, we can define it mostly in terms of split--it looks like this:

/* pairCompose : (A -> B) x (X -> Y) -> (pair<A,X> -> pair<B,Y>) */
template< class F, class G > struct PairComposition {
F f; G g;

template< class _F, class _G >
constexpr PairComposition( _F&& f, _G&& g )
: f(std::forward<_F>(f)), g(std::forward<_G>(g))
{
}

template< class P/*air*/ >
constexpr auto operator() ( const P& p )
-> decltype( std::make_pair( f(std::get<0>(p)), g(std::get<1>(p)) ) )
{
return std::make_pair( f(std::get<0>(p)), g(std::get<1>(p)) );
}
};

constexpr auto pairCompose = MakeT<PairComposition>();

pairCompose returns a function expecting a pair and returns a pair, threading the first value through f and the second through g. We can compose PairCompositions.

namespace std {
std::string to_string( const std::string& s );
template< class X, class Y >
std::string to_string( const std::pair<X,Y>& p );

std::string to_string( const std::string& s ) {
return "\"" + s + "\"";
}

template< class X, class Y >
std::string to_string( const std::pair<X,Y>& p ) {
return "(" + to_string(p.first) + "," + to_string(p.second) + ")";
}
}

constexpr struct ToString {
template< class X >
std::string operator () ( const X& x ) const {
return std::to_string(x);
}
} string{};

int main() {
using std::cin;
using std::cout;
using std::endl;

auto plus2 = []( int x ){ return x+2; };

std::pair<int,int> p( 1, 1 );

cout << "((+2) . string, (+4))( 1, 1 ) = "
<< compose( pairCompose(string,plus2),
pairCompose(plus2, plus2) )(p) << endl;
}

This will output ("3",5). It's easiest to look at this as p.first and p.second being on two separate paths. I have written it such that the individual paths are verticle. The first path starts at 1, and goes to plus2(1), to show(plus2(1)). The second path starts at 2 and ends at plus2(plus2(2)). The odd part is that we're defining both paths at once.

Observe that first(f) = split(f,id). Proof?

first : (A -> B) -> (pair<A,X> -> pair<B,X>)
split : (A -> B) x (X -> Y) -> (pair<A,X> -> pair<B,Y>)
id : X -> X
f : A -> B
split(f,id) : pair<A,X> -> pair<B,X>

Since we know first(f) = split(f,id), we can intuit that second(f) = split(id,f) and also, split(f,g) = compose( first(f), second(g) ).

fan represents a fork in the road. One variable gets fed into two functions, the results of which get zipped into a pair. duplicate will do the splitting, but we'll rely on split to implement fan.

constexpr struct Duplicate {
template< class X, class P = std::pair<X,X> >
constexpr P operator() ( const X& x ) {
return P( x, x );
}
} duplicate{};

With this, we can say that fan(f,g)(x) = split(f,g)( duplicate(x) ). Since we know what everything looks like, we can define Arrow<F>.

template< class Func > struct Arrow<Func> {
template< class F >
static constexpr F arr( F&& f ) { return std::forward<F>(f); }

/* split(f,g)(x,y) = { f(x), g(y) } */
template< class F, class G >
static constexpr auto split( F f, G g )
-> PairComposition<F,G>
{
return pairCompose( std::move(f), std::move(g) );
}

/*
* first(f)(x,y)  = { f(x), y }
* second(f)(x,y) = { x, f(y) }
*/

template< class F >
static constexpr auto first( F f )
-> decltype( split(std::move(f),id) )
{
return split( std::move(f), id );
}

template< class F >
static constexpr auto second( F f )
-> decltype( split(id,std::move(f)) )
{
return split( id, std::move(f) );
}

/* fan(f,g)(x) = { f(x), g(x) } */
template< class F, class G >
static constexpr auto fan( F f, G g )
-> decltype( compose( split(std::move(f),std::move(g)), duplicate ) )
{
return compose( split(std::move(f),std::move(g)), duplicate );
}
};

Now, we can rewrite the above example:

int main() {
auto plus2 = []( int x ){ return x+2; };

cout << "(+2) *** (+2) >>> string *** (+2) \$ 1 = "
<< compose( split(string, plus2),
fan(  plus2,  plus2) )(1) << endl;
}

One way to think of Arrows is as paths. fan represents a fork in the road, split defines two separate, but parallel, paths at once, and first and second allow progress on one of the paths. For an arbitrary example, consider a branching path that hides some treasure. What sequence of moves are required to recover it?

/*
* Get 0 : (X,Y) -> X
* Get 1 : (X,Y) -> Y
*/
template< size_t N > struct Get {
template< class P >
constexpr auto operator () ( P&& p )
-> decltype( std::get<N>(std::declval<P>()) )
{
return std::get<N>( std::forward<P>(p) );
}
};

int main() {
constexpr auto fst = Get<0>();
constexpr auto snd = Get<1>();
constexpr auto oneHundred = []( int x ){ return 100; };

// Hide the hundred.
// hidden = pair( pair( 0, pair(100,0) ), 0 )
auto hidden = fan( fan(id,fan(oneHundred,id)), id )( 0 );
// Function to find it again.
auto find = compose( fst, compose(snd,fst) );

cout << "I found " << find(hidden) << "!" << endl;
}

#### Enter Kleisli.

This all works great for free functions, but some functions look like this:

f : X -> M<Y> -- Where M is some Monad

This f is a member of the Kleisli category. It accepts a normal value and returns a Monadic one. Examples of Kelisli functions (psuedocode):

Just : X -> unique_ptr<X>
Just = MakeT<unique_ptr>();

Seq : X -> std::vector<X>
Seq(x) = std::vector<X>{x}

mreturn<M> : X -> M<X>

unique_ptrs and vectors are monads, so any function that produces one from some x can be considered in the Kleisli category. Though, to the compiler, there's no logic to that, so we define a wrapper type around the function. This is a fairly common pattern, so I define a base class for it.

template< class F > struct Forwarder {
using function = typename std::decay<F>::type;
function f = F();

template< class ...G >
constexpr Forwarder( G&& ...g ) : f( std::forward<G>(g)... ) { }

template< class ...X >
constexpr auto operator() ( X&& ...x )
-> decltype( f(std::declval<X>()...) )
{
return f( std::forward<X>(x)... );
}

constexpr operator function () { return f; }
};

The Kleisli itself can be implemented two ways. The Haskell way would be something like this:

/* Kleisli M A B : A -> M<B> */
template< template<class...> class M, class A, class B,
class F = std::function<M<A>(B)> >
struct Kleisli : Forwarder<F> {
template< class ...G >
constexpr Kleisli( G&& ...g ) : Forwarder<F>(std::forward<G>(g)...) { }
};

This is faithful to how Haskell defines it.

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }

But just think about this for a moment. A Kleisli is an Arrow, right? What would Arrow<Kleisli>::first return?

first : (A -> B) -> (pair<A,X> -> pair<B,X>)
Kleisli f = A -> M<B>
first(Kleisli f) : (A -> M B) -> (pair<A,X> -> M pair<B,X>)

What's the type of X? It's truly impossible to know because it depends on what gets passed in, which is what the notation above means.

Is it impossible to define Kleisli in this way? I don't know. I attempted to specialize its composition function for when A or B were pair types, but there are four combinations of whether A or B or both is a pair. I tried assigning X the type of std::placeholders::_1, but none of my attempts to make it really work compiled. (It was horrible.)

But we don't have any of that trouble if we define Kleisli differently.

#### Kleisli<F>.

/* Kleisli M F : F -- where F : A -> M<B> */
template< template<class...> class M, class F = Id >
struct Kleisli : Forwarder<F> {
template< class ...G >
constexpr Kleisli( G&& ...g ) : Forwarder<F>(std::forward<G>(g)...) { }
};

An implicit requirement of arrows is that they can be composed, but Kleislies?

compseKleisli : Kleisli(B -> M<C>) x Kleisli(A -> M<B>) -> (...?)

We can reasonably assume that it should be Kleisli(A -> M<C>), but our naive definition of composition must be specialized. Literally.

/* Composition : Kleisli(B -> M<C>) x Kleisli(A -> M<B>) -> (A -> M<C>) */
template< template<class...> class M, class F, class G >
struct Composition<Kleisli<M,F>,Kleisli<M,G>>
{
Kleisli<M,F> f;
Kleisli<M,G> g;

template< class _F, class _G >
constexpr Composition( _F&& f, _G&& g )
: f(std::forward<_F>(f)), g(std::forward<_G>(g)) { }

template< class X >
constexpr auto operator() ( X&& x )
-> decltype( g(std::forward<X>(x)) >>= f )
{
return g(std::forward<X>(x)) >>= f;
}
};

/* kcompose : Kleisli(B -> M<C>) x Kleisli(A -> M<B>) -> Kleisli(A -> M<C>) */
constexpr struct KCompose {
template< template<class...> class M, class F, class G >
constexpr auto operator () ( Kleisli<M,F> f, Kleisli<M,G> g )
-> Kleisli< M, Composition<Kleisli<M,F>,Kleisli<M,G> >
{
return kleisli<M> (
compose( std::move(f), std::move(g) )
);
}
} kcompose{};

int main() {
auto stars = kleisli<std::basic_string> (
[] (char c) -> std::string {
return c == '*' ? "++" :
c == '+' ? "* *" : std::string{c};
}
);

auto starsSqr = kcompose( stars, stars );

auto starsCube = kcompose( starsSqr, stars );

cout << "stars of '*' : " << stars('*') << endl;
cout << "stars^2 of '*' : " << starsSqr('*') << endl;
cout << "stars^3 of '*' : " << starsCube('*') << endl;
}

This outputs

stars of '*' : "++"
stars^2 of '*' : "* ** *"
stars^3 of '*' : "++ ++++ ++"

Like before, it would be most convenient to define Arrow<Kleisli> in terms of split. split(f,g), given the pair {x,y}, will have to pass x into f and y into g, both of which will return Monadic values. Finally, a pair will have to be constructed from the values extracted from f(x) and g(y).

split: Kleisli (A -> M B) x Kleisli (X -> M Y) -> Kleisli (pair<A,X> -> M pair<B,Y>)

To extract the values from f(x) and g(y), we need to call mbind on each, which in Haskell might look like this:

f(x) >>= (\x' -> g(y) >>= (\y' -> return (x,y)))

Or, Control.Monad defines liftM.

liftM2 (,) f(x) g(y) -- where (,) is equivalent to make_pair

template< class M > struct Return {
template< class X >
constexpr auto operator () ( X&& x )
-> decltype( mreturn<M>(std::declval<X>()) )
{
return mreturn<M>( std::forward<X>(x) );
}
};

/*
* liftM : (A -> B) x M<A> -> M<B>
* liftM : (A x B -> C) x M<A> x M<B> -> M<C>
*/
constexpr struct LiftM {
template< class F, class M, class R = Return<typename std::decay<M>::type> >
constexpr auto operator () ( F&& f, M&& m )
-> decltype( std::declval<M>() >>= compose(R(),std::declval<F>()) )
{
return std::forward<M>(m) >>= compose( R(), std::forward<F>(f) );
}

template< class F, class A, class B >
constexpr auto operator () ( F&& f, A&& a, B&& b )
-> decltype( std::declval<A>() >>= compose (
rcloset( LiftM(), std::declval<B>() ),
closet(closet,std::declval<F>())
) )
{
return std::forward<A>(a) >>= compose (
rcloset( LiftM(), std::forward<B>(b) ),
closet(closet,std::forward<F>(f))
);
}
} liftM{};

It acts basically as a n-ary mbind, though one could also define an n-ary mbind! liftM works even if you don't.

Finally, we have all the pieces in place to implement KleisliSplit.

/* kleisliSplit : Kleisli(A -> M<B>) x Kleisli(X -> M<Y>) -> (piar<A,X> -> M<pair<B,Y>>) */
template< template<class...> class M, class F, class G >
struct KleisliSplit {
F f;
G g;

constexpr KleisliSplit( F f, G g ) : f(std::move(f)), g(std::move(g)) { }

template< class X, class Y >
constexpr auto operator () ( const std::pair<X,Y>& p )
-> decltype( liftM(pair,f(std::get<0>(p)),g(std::get<1>(p))) )
{
return liftM (
pair,
f( std::get<0>(p) ),
g( std::get<1>(p) )
);
}
};

The final note before moving on: arr. Kleisli's arr is like a Monad's mreturn.

arr : (A -> B) -> Kleisli(A -> M<B>)
arr(f)(x) = mreturn<M>( f(x) )

or:

arr = liftM

template< template<class...> class M, class F >
struct Arrow< Kleisli<M,F> > {

template< class G >
using K = Kleisli<M,G>;

template< class G >
static constexpr auto arr( G g ) -> Kleisli< M, Part<LiftM,G> > {
return kleisli<M>( closet(liftM,std::move(g)) );
}

template< class G >
static constexpr auto first( G g )
-> K<decltype( ::split(std::move(g),arr(id)) )>
{
// id is not a Kleisli.
// The call to arr refers to the arr above, not ::arr.
// arr(id) : Kleisli(X -> M<X>)
return ::split( std::move(g), arr(id) );
}

template< class G >
static constexpr auto second( G g)
-> K<decltype( ::split(arr(id),std::move(g)) )>
{
return ::split( arr(id), std::move(g) );
}

template< class G >
static constexpr auto split( Kleisli<M,F> f, Kleisli<M,G> g )
-> K< KleisliSplit<M,F,G> >
{
return KleisliSplit<M,F,G>( std::move(f.f), std::move(g.f) );
}

template< class _F, class _G >
static constexpr auto fan( _F&& f, _G&& g )
-> decltype( kcompose(split(std::declval<_F>(),std::declval<_G>()),arr(duplicate)) )
{
return kcompose( split(std::forward<_F>(f),std::forward<_G>(g)), arr(duplicate) );
}
};

int main() {
auto stars = kleisli<std::vector> (
[] (char c) {
return c == '*' ? std::vector<char>{'+','+'} :
c == '+' ? std::vector<char>{'*',' ','*'} : std::vector<char>{c};
}
);

auto hairs = kleisli<std::vector> (
[] (char c) -> std::vector<char> {
return c == '*' ? std::vector<char>{'\'','"','\''} :
c == '+' ? std::vector<char>{'"',' ','"'} :
c == '"' ? std::vector<char>{'\''} :
c == '\'' ? std::vector<char>{} :
std::vector<char>{c};
}
);

cout << "hairs of '*' : " << hairs('*') << endl;
cout << "hairs^2 of '*' : " << compose(hairs,hairs)('*') << endl;

cout << "split(stars,hairs) (*,*) = " << split(stars,hairs)(pair('*','*')) << endl;
cout << "fan(stars,hairs)    (*)  = " << fan(stars,hairs)('*') << endl;
cout << "fan(hairs,stars)    (*)  = " << fan(hairs,stars)('*') << endl;
cout << "split(hairs,stars) . fan(stars,hairs) = "
<< compose( split(hairs,stars), fan(stars,hairs) )('*') << endl;
}

Finally, this outputs

hairs of '*' : [',",']
hairs^2 of '*' : [']
split(stars,hairs) (*,*) = [(+,'),(+,"),(+,'),(+,'),(+,"),(+,')]
fan(stars,hairs)    (*)  = [(+,'),(+,"),(+,'),(+,'),(+,"),(+,')]
fan(hairs,stars)    (*)  = [(',+),(',+),(",+),(",+),(',+),(',+)]
split(hairs,stars) . fan(stars,hairs) = [(",'),( ,'),(",'),(","),( ,"),(","),(",'),( ,'),(",'),(",'),( ,'),(",'),(","),( ,"),(","),(",'),( ,'),(",')]

#### Extras -- Convenience and Pitfalls.

Perhaps the most important parts of Control.Arrow are here, but there are still a few things that can be added. For example, compose is backwards! compose(f,g) means "do g, then do f." Because of this we have to read it backwards. fomp is useful, if only because we read left-to-right, not the other way around.

/* fcomp : (A -> B) x (B -> C) -> (A -> C) */
constexpr struct FComp {
template< class G, class F, class C = Composition<F,G> >
constexpr C operator () ( G g, F f ) {
return C(std::move(f),std::move(g));
}
} fcomp{};

Another tool is precompose and postcompose. Perhaps one wants to compose something that is not a Kleisli with something that is.

/* prefcomp : (A -> B) x (Arrow X Y) -> Arrow A Y */
constexpr struct PreFComp {
template< class F, class A >
constexpr auto operator () ( F&& f, A&& a )
-> decltype( arr<A>(declval<F>()) > declval<A>() )
{
return arr<A>(forward<F>(f)) > forward<A>(a);
}
} prefcomp{};

/* postfcomp : Arrow A B x (X -> Y) -> Arrow A Y */
constexpr struct PostFComp {
template< class A, class F >
constexpr auto operator () ( A&& a, F&& f )
-> decltype( declval<A>() > arr<A>(declval<F>()) )
{
return forward<A>(a) > arr<A>(forward<F>(f));
}
} postfcomp{};

Beyond that, there's ArrowZero and ArrowPlus to work with Monoids, ArrowChoice based on Either, ArrowApply and ArrowLoop.

ArrowZero, defining zeroArrow, shows the downside to implementing Kleisli as K<M,F> instead of K<M,A,B>. It is defined like so:

zeroArrow = Kleisli (\_ -> mzero)

The type mzero needs to return is M<B>. Its argument, the _, will be of type A. So we have this problem where zeroArrow(k) (for some Kleisli, k) doesn't know what type to return and can't deduce it!

If we had implemented Kleisli with A and B, this would be no problem, but then it would have been impossible(?) to implement Arrow<Kleisli>::first. In Haskell, all functions carry around information about their domain and codomain, so there is no difference between passing around A and B or just F.

The easiest solution is to diverge from Haskell's definition and require zeroArrow to take an explicit result-type parameter.

#### Conclusions.

Arrows let us do interesting types of composition that one would not normally likely think of. They fall somewhere between Functors and Monads (this article has a graph). My Monadic parser could have also been written with Arrows.

I realize this has been a very long post. Hopefully all the code examples work, there are no inaccuracies, and it is understandable, but with an article this large, something has probably been fudged. Due to the large amount of material, it may be a good idea to split this article up and go more in depth. Please speak up if something seems off.

Source code: https://gist.github.com/4176121
Haskell reference: Control.Arrow

## Monday, November 26, 2012

### The Importance of Function Objects

Function objects allow for freedoms that free functions do not. They are more compatible with higher order functions, composition, and generic programming. They are easier to use; extensible and convenient.  They are often even more efficient.

#### Higher Order Functions.

Write a function that adds two arguments of any given type.

template< class X, class Y >
constexpr auto add( X&& x, Y&& y )
-> decltype( std::declval() + std::declval() )
{
return std::forward(x) + std::forward(y);
}

Easy, right? Now pass that in to std::accumulate.

int main() {
std::vector<int> v = { 0, 1, 2, 3, 4, 5 };
int sum = std::accumulate( v.begin(), v.end(), 0, add );
std::cout << "sum = " << sum << std::endl;
}

And compile!

fo.cpp:20:68: error: no matching function for call to 'accumulate(std::vector<int>::iterator, std::vector<int>::iterator, int, <unresolved overloaded function type>)'

Huh, GCC can't deduce the type of add. Really, the lexical name, add, refers to a whole set of possible template overloads. It could pick one from the set if we supplied some arguments, but not by the name alone. We can fix this by specifying the type arguments.

int sum = std::accumulate( v.begin(), v.end(), 0, add<int&,int&> );

Why do we specify int& instead of int? If we specify int, then because of the quirks in perfect forwarding, signature is

int add( int&&, int&& )

Since its inputs will be lvalues, this will fail to compile. Instead, it will look like this:

int add( int& &&, int& && )

and the arguments will be forwarded to the addition as int&'s.

At this point, falling back on std::plus<int>() would make the most sense, but what if we don't want to have to specify the type? The proposal n3421 expresses this concern, and would allow for the syntax, std::plus<>(), which would be a function object version of add. Finally, that line would compile, but n3421 isn't standard yet. Why not do this?

struct Add {
template< class X, class Y >
constexpr auto operator () ( X&& x, Y&& y )
-> decltype( std::declval<Y>() + std::declval<X>() )
{
return std::forward<X>(x) + std::forward<Y>(y);
}
};

constexpr auto add = Add();

...

int sum = std::accumulate( v.begin(), v.end(), 0, add );

Here, add would be essentially no different from an instance of std::plus<>, but because it is already instantiated, we can avoid much of the syntactic cruft.

#### Programming Compositionally.

Let's say we have a two-dimensional array

std::vector<int> v = { 1, 2, 3, 4, 5 };
std::vector<std::vector<int>> vv = { v, v, v };

and we want to find the sum of all its element. We might first write a small function to find the sum of a one-dimensional array.

template< class S >
int sum( const S& s ) {
return std::accumulate( s.begin(), s.end(), 0, add );
}

With this, we could write a simple for loop to iterate over each element, adding the sums of each vector, but that's the whole point of accumulate! We could use std::transform to build a list of sums and accumulate that, but what's the point? The easiest thing to do is use function composition.

Previously, I have talked about function composition. I defined a type, Composition<F,G>, which passed its first argument to G and the result of that along with any following arguments to F.

std::accumulate expects a function where the first value is the accumulator (the sum) and the second value comes from the sequence (in this case: another std::vector). We want the sum of the vector, and then to add the results together. One could fairly trivially write a function that does this explicitly, but that will have to be done for every similar use-case. Patterns of composition can be abstracted away.

template< class F, class G > struct AccumRight {
F f = F();
G g = G();

constexpr AccumRight() { }

constexpr AccumRight( F f, G g)
: f(f), g(g) { }

template< class X, class Y >
constexpr auto operator () ( X&& x, Y&& y )
-> decltype( f(std::declval<X>(), g(std::declval<Y>()) ) )
{
return f( std::forward<X>(x), g(std::forward<Y>(y)) );
}
};

template< class F, class G, class A = AccumRight<F,G> >
constexpr A rAccumulation( F f, G g ) {
return A( f, g );
}

Finally, we can write that function. How does it look if we use free functions?

sum = std::accumulate( vv.begin(), vv.end(), 0,
rAccumulation(add<int&,int>,sum<std::vector<int>>) );

Notice how, since the right-hand argument of add will be an rvalue (the result of sum), we can just tell it int. Now, how about function objects?

sum = std::accumulate( vv.begin(), vv.end(), 0,
rAccumulation(add,sum) );

Much nicer, no? Imagine more complex examples involving passing higher-order functions to higher-order functions. Without using such techniques, higher order functional programming in C++ would be daunting. Manually deducing types is difficult and error prone--sometime impossible due to implementation details, but the compiler can do it instead, if given the chance. Because of this, techniques in C++ that would otherwise be thought of as impossible become easy.

#### Finer Control.

std::get<N> is a nice function for working with pairs and tuples, but doesn't work on normal containers. Lets define a function object for that!

struct Selector {
int i;

Selector( int j=0 ) : i(j) { }

template< class S >
typename const S::value_type& operator () ( const S& s ) const {
return *std::next( s.begin(), i );
}
};

Selector first(0), third(2);

int main() {
std::vector<int> v = { 1, 2, 3, 4, 5 };
std::cout << "first = " << first(v) << std::endl;
std::cout << "third = " << third(v) << std::endl;
std::cout << "fourth = " << Selector(third(v))(v) << std::endl;
}

This will output

first =1
third = 3
fourth = 4

We typically think of functions as static, unchanging things, but Selector is dynamic. It could be used, for example, as a function returning the current player in a game by keeping its member, i, always up-to-date.

For another example, consider a function object, Printer, that prints its arguments to some file. We might write that like this:

namespace std {

template< class X >
string to_string( const std::vector<X>& v ) {
string str = "[ ";
for( const X& x : v ) str += to_string(x) + " ";
str += "]";
return str;
}

// Because the standard doesn't define this.
string to_string( const std::string& s ) {
return s;
}

template< class T >
string to_string( const T& s ) {
ostringstream ss;
ss << s;
return ss.str();
}

} // namespace std

struct Printer {
std::string destination;

Printer( std::string filename )
: destination( std::move(filename) )
{
}

void redirect( std::string filename ) {
destination = std::move( filename );
}

template< class X >
void operator () ( const X& x ) {
std::ofstream s( destination, std::ios_base::app );
s << std::to_string(x);
}
};

int main() {
std::vector<int> v = { 1, 2, 3, 4, 5 };
std::vector<std::vector<int>> vv = { v, v, v };

Printer prnt( "file1" );
prnt( v );
prnt.redirect( "file2" );
prnt( vv );
}

Here, the dynamics come from being able to change the destination of our output at runtime. It outputs:

file1: [ 1 2 3 4 5 ]
file2: [ [ 1 2 3 4 5 ] [ 1 2 3 4 5 ] [ 1 2 3 4 5 ] ]

#### Extensibility.

I have talked before about generalizing associativity, transitivity, and other such things in function objects. Inheritance adds a new dimension to functions. Derivatives can benefit from functionality offered in base classes and base classes can benefit from their derivations via the curiously recurring template pattern.

For a different example, let's have the Printer class time-stamp its output.

#include <ctime>
struct StampedPrinter : Printer {
StampedPrinter( std::string filename )
: Printer( std::move(filename) )
{
}

template< class X >
void operator () ( const X& x ) {
std::time_t t = std::time( nullptr );
std::tm tm = *std::localtime( &t );

std::string time = std::to_string(tm.tm_min) + ":" +
std::to_string(tm.tm_sec) + " -- ";

Printer::operator()( time + std::to_string(x) + "\n" );
}
};

By simply changing the type of prnt in the previous example to StampedPrinter, it will output:

file1:
6:46 -- [ 1 2 3 4 5 ]

file2:
6:46 -- [ [ 1 2 3 4 5 ] [ 1 2 3 4 5 ] [ 1 2 3 4 5 ] ]

And if run again,

file1:
6:46 -- [ 1 2 3 4 5 ]
13:13 -- [ 1 2 3 4 5 ]

file2:
6:46 -- [ [ 1 2 3 4 5 ] [ 1 2 3 4 5 ] [ 1 2 3 4 5 ] ]
13:13 -- [ [ 1 2 3 4 5 ] [ 1 2 3 4 5 ] [ 1 2 3 4 5 ] ]

#### In conclusion,

Function objects can do anything that free functions can do, but they cooperate better. They are more cohesive and orthogonal. I hope that these simple demonstrations have been thought provoking.

The code for this post: https://gist.github.com/4151880
See also: An interesting article that talks about a trampoline function that runs a recursive function object for tail-call optimization: http://fendrich.se/blog/2012/11/22/compile-time-loops-in-c-plus-plus-11-with-trampolines-and-exponential-recursion/

## Wednesday, November 21, 2012

### Some Observations on Human Behavior

Are not the ones who praise a drug-free space also the most tempted to bring drugs to it? Are the ones who cry in empathy for the poor not actually rich? Is it not the case that those who despise intolerance are the most intolerant?

Don't those who scream "Revolution!" fear change? Are the people who demonize sex not the ones who crave it deeply, and they that oppose pornography not the same as those who suffer from addiction?

Are the polluters not the biggest deniers of global warming? Are the people opposing gay rights not in the closet? Are those who commit voter fraud not condemning it? Are those who speak of freedom not dreaming of fascism? Don't those with the most to give also complain the most about "hand-outs"?

Are the knowledgeable not the quietest and the ignorant not the loudest or do those who speak know, and those who don't not? Do those who boast not actually suck?

Are not those who cast suspicion the least trustworthy? Are those who push blame not riddled with guilt? Does a thief not secure her own goods?

Does laughter imply absence of sorrow?

Is hypocrisy human nature?

## Monday, November 19, 2012

### Monadic Parsing in C++

When researching parsing in Haskell, I always find this pdf: eprints.nottingham.ac.uk/223/1/pearl.pdf

I will be referring back to this paper and encourage my readers to at least skim it as well. It may provide more understanding in how it works.

It describes a simple, yet hard to comprehend functional parser. I have attempted to translate this to C++, but first I wrote a more intuitive, less functional one. Just a simple calculator, somewhat close to what's described in the pdf, and it worked like this:

The first stage took the input string and created a list of token type-lexeme pairs. Given the input "1+2*2", it would spit back {(INT,"1"),(OP,"+"),...}. The next stage uses two mutually recursive functions to represent two parse states: that of sums and subtractions and that of numbers, multiplications and divisions. Since addition has the lowest precedence in this mini-language, it's safe to parenthesize the rest of the expression, meaning that if it parsed "1+", it will expect the next number to be a number, and it might want to add one to it, eagerly, but not if fallowed by a "2*2" since multiplication has higher precedence.

These functions convert the vector of tokens to an expression tree that evaluates the arguments."2*2" would parse to a tree with a multiplier at its root and two numbers as its leaves. So, after the first state (sums) had read "1+", it would eagerly construct an addition object with the left argument being 1, and the right argument being the result of the rest of the parse! So it reads "2*2" and builds a tree that becomes the right-side argument for our "1+" tree.

This solution is theoretically consistent with building a language using flex and bison. The source can be found here (gist). But it isn't functional. That's when I stumbled back onto this research paper and decided to give a real go at it.

#### Functional Parsing.

The parser described in this paper does not act in the same way as my parser does. Rather than lexing, tokenizing, and building an expression tree, it cuts straight to the point. A Parser<int> will be a function that accepts a string and produces ints. But, the job may not be done; there may be more to parse. For every int it parses, it will also store the suffix of the parse. So, if p is some parser of type Parse<int>, p("1abc") will return a vector holding one match: the value, 1, and the suffix, "abc".

What does this class look like?

/* A Parser is a function taking a string and returning a vector of matches. */
template< class X > struct Parser {
// The value is the target of the parse. (For example "1" may parse to int(1).
using value_type    = X;

// A match consists of a value and the rest of the input to process.
using parse_state   = std::pair<X,std::string>;

// A parse results in a list of matches.
using result_type   = std::vector< std::pair<X,std::string> >;

// A parser is a function that produces matches.
using function_type = std::function< result_type( const std::string& ) >;

function_type f;

Parser( function_type f ) : f(std::move(f)) { }

Parser( const Parser<X>& p ) : f(p.f) { }
Parser() { }

result_type operator () ( const std::string& s ) const {
return f( s );
}
};

template< class X, class F > Parser<X> parser( F f ) {
using G = typename Parser<X>::function_type;
return Parser<X>( G(std::move(f)) );
}

I have mentioned in previous articles that one should avoid std::function for efficiency reasons, but it vastly simplifies things here. As you can see, Parser merely wraps itself around std::function. I would encourage the reader to think of it as a type alias--not deserving of being called a new type, but more than a typedef.

This is consistent with how the paper defines this type:

newtype Parser a = Parser (String -> [(a,String)])

If nothing can be parsed, and empty list will be returned. If many things are parsed, a list of each match will be returned.

#### The Parser Monad.

As a reminder, the basic monadic operations are these:

a >> b = b -- Do a, then b.
a >>= f = b -- For each x from a, construct b with f(x).
mreturn x = a -- Construct a monad from a value.

How does this relate to parsing? A parser is basically just a function, so if p and q are both parsers, p >> q must return a new parser, a new function. The simple explanation (do p, then q) is correct. First, p parses and let's say it returns a match, (x,rest). rest is sent to q for parsing and the x is thrown away. It may sound odd to just throw away a value, but it will become more obvious soon.

If p had failed to parse a value, then q would not have been run.

The bind operation, p >>= f, extracts the parsed value, x, from p and creates a new parser from f(x). mreturn x creates a new parser that returns x as its value. It accepts any string, even an empty one. Ideally, x came from the output of another parser.

p >> q -- Run parser p, then q.
p >>= f -- Construct a parser with p's matches.
mreturn x -- Construct a parser that returns x.

We can define it like so:

template< class X > struct Monad< Parser<X> > {
using Pair = typename Parser<X>::parse_state;
using R    = typename Parser<X>::result_type;

/*
* mreturn x = parser(s){ vector( pair(x,s) ) }
* Return a parsed value. Forwards rest of input to the next parser.
*/
template< class M >
static M mreturn( X x ) {
return parser<typename M::value_type> (
[x]( const std::string& s ) {
return R{ Pair(std::move(x),s) };
}
);
}

/* a >> b = b */
template< class Y, class Z >
template< class Y, class Z >
static Parser<Y> mdo( Parser<Z> a, Parser<Y> b ) {
return a >>= [b]( const Z& z ) { return b; };
}

/* Continue parsing from p into f. */
template< class F, class Y = typename std::result_of<F(X)>::type >
static Y mbind( F f, Parser<X> p )
{
using Z = typename Y::value_type;
return parser<Z> (
[f,p]( const std::string& s ) {
// First, extract p's matches.
return p(s) >>= [&]( Pair p ) {
// Then construct the new parser from the p's output.
// Continue parsing with the remaining input with the new parser.
return f( std::move(p.first) )( std::move(p.second) );
};
}
);
}
};

Do not worry if this source is difficult to understand. It is more important to understand how it is used (which is perhaps common with monads). Note that mdo is defined such that for every successful parse of a, b is parsed. If a fails to parse anything, b fails, too.

These monadic operations are the core building blocks from which we can build more complex system, but the paper also discusses MonadZero and MonadPlus. They are both type classes, like Monad, but extend it to do a few interesting things. In C++, one can concatenate two string by using simple addition: s1 + s2 = s12. MonadPlus is generalization of this. MonadZero completes this generalization by supplying the additive identity. For example, we know that zero + x = x. Thus, "" + s = s.

In parsing terms, zero would refer to a parser that matches nothing and adding two parsers, p+q, will produce a third parser that accepts either p's or q's. For example, itentifier+number would create a function that parses either identifiers or numbers.

We can define MonadPlus and MonadZero in the same way we would define Monad.

template< class ... > struct MonadZero;
template< class ... > struct MonadPlus;

template< class M, class Mo = MonadZero< Cat<M> > >
auto mzero() -> decltype( Mo::template mzero<M>() )
{
return Mo::template mzero<M>();
}

template< class A, class B, class Mo = MonadPlus<Cat<A>> >
auto mplus( A&& a, B&& b ) -> decltype( Mo::mplus(std::declval<A>(),std::declval<B>()) )
{
return Mo::mplus( std::forward<A>(a), std::forward<B>(b) );
}

template< class X, class Y >
auto operator + ( X&& x, Y&& y ) -> decltype( mplus(std::declval<X>(),std::declval<Y>()) )
{
return mplus( std::forward<X>(x), std::forward<Y>(y) );
}

First, we define these for sequences.

template<> struct MonadZero< sequence_tag > {
/* An empty sequence. */
template< class S >
S mzero() { return S{}; }
};

/* mplus( xs, ys ) = "append xs with ys" */
template<> struct MonadPlus< sequence_tag > {
template< class A, class B >
static A mplus( A a, const B& b ) {
std::copy( b.begin(), b.end(), std::back_inserter(a) );
return a;
}
};

And then for Parsers.

/* mzero: a parser that matches nothing, no matter the input. */
template< class X > struct MonadZero< Parser<X> > {
template< class P >
static P mzero() {
return parser<X> (
[]( const std::string& s ){
return std::vector<std::pair<X,std::string>>();
}
);
}
};

/* mplus( pa, pb ) = "append the results of pa with the results of pb" */
template< class X > struct MonadPlus< Parser<X> > {
using P = Parser<X>;
static P mplus( P a, P b ) {
return parser<X> (
[=]( const std::string& s ) { return a(s) + b(s); }
);
}
};

Since we usually only want the first successful parse, the paper define an operator, +++, that does this.

template< class X >
Parser<X> mplus_first( const Parser<X>& a, const Parser<X>& b ) {
return parser<X> (
[=]( const std::string s ) {
using V = std::vector< std::pair< X, std::string > >;
V c = (a + b)( s );
return c.size() ?  V{ c[0] } : V{};
}
);
}

This completes the required building blocks. A parser of significant complexity could be made using only the above functions and types. The paper describes building a notably simple parser, so let's do that instead!

#### Basic Monadic Parsers.

The simplest parser is item, which accepts any char.

std::string tail( const std::string& s ) {
return std::string( std::next(s.begin()), s.end() );
}

/*
* Unconditionally match a char if the string is not empty.
* Ex: item("abc") = {('a',"bc")}
*/
auto item = parser<char> (
[]( const std::string& s ) {
using Pair = Parser<char>::parse_state;
using R = Parser<char>::result_type;
return s.size() ? R{ Pair( s[0], tail(s) ) } : R();
}
);

To demonstrate its usage, the paper defines a simple parser that takes a string of length three or more and returns the first and third values.

auto p = item >>= []( char c ) {
return item >> item >>= [c]( char d ) {
return mreturn<Parser>( std::make_pair(c,d) );
};
};

p first runs item to extract c, then runs item again but throws away the value. It runs item a third time to extract d and finally returns as its value (c,d). p("abcd") would return {(('a','c'),"d")}.

The next function creates a parser that is a little more helpful:

/* sat( pred ) = "item, if pred" */
template< class P >
Parser<char> sat( P p ) {
return item >>= [p]( char c ) {
return p(c) ? mreturn<Parser>(c) : mzero<Parser<char>>();
};
}

Given some function that operates on chars, this extracts an item, but then checks the condition without consuming any additional input. If p(c) returns true, then it returns a parser with the value c, otherwise zero, a failed parse. Using this, we can define a parser to accept only a specific char.

Parser<char> pchar( char c ) {
return sat( [=](char d){ return c == d; } );
}

And then, a parser that accepts only a specific string.

Parser<std::string> string( const std::string& s ) {
if( s.size() == 0 )
return mreturn<Parser>( s );

Parser<char> p = pchar( s[0] );
for( auto it=std::next(s.begin()); it != s.end(); it++ )
p = p >> pchar( *it );

return p >> mreturn<Parser>(s);
}

Note: There is no name conflict with std::string because the source does not contain "using namespace std;".

This function does something very odd. For every char in s, it chains together char parsers. For example, string("abc") would return a parser equivalent to pchar('a') >> pchar('b') >> pchar('c') >> mreturn<Parser>("abc"). If any of the char parsers fail down the line, mreturn<Parser>(s) will fail. Since we already know the values of the successful parses, their values are thrown away.

Though faithful to the paper, this may be less efficient than desirable. One could implement string in this way, too:

Parser<std::string> string( const std::string& str ) {
return parser<std::string> (
[str]( const std::string& s ) {
using R = typename Parser<std::string>::result_type;
if( std::equal(str.begin(),str.end(),s.begin()) ) {
return R {
{ str, s.substr( str.size() ) }
};
} else {
return R();
}
}
);
}

It can at times be simpler to write out these functions instead of composing them, however, that can be thought of as an optimization.

The next function creates a new parser from a parser, p, that accepts one or zero p's.

template< class X >
Parser<std::vector<X>> some( Parser<X> p ) {
using V = std::vector<X>;
using Pair = std::pair<V,std::string>;
using R = std::vector< Pair >;
using P = Parser<V>;
return mplus_first(
parser<V> (
[=]( const std::string& s ) {
auto matches = p(s);

return matches.size() == 0 ? R{}
: R{
Pair(
V{std::move(matches[0].first)},
std::move( matches[0].second )
)
};
}
),
mreturn<Parser>( V{} )
);
}

It was unfortunately difficult to translate, but does work. (The gist also contains a version called many, which accepts zero or many p's.) some converts a parser of type X to one that produces a vector or X's. It always succeeds, even if it does not successfully parse anything.

To create a parser that consumes whitespace is now trivial.

template< class X >
using ManyParser = Parser< std::vector<X> >;

ManyParser<char> space = some( sat([](char c){return std::isspace(c);}) );

We require one more function to parse alternating sequences. Like what? A sum, like "1+2+3" is a sort of alternating sequence of numbers and +'s. A product is an alternating sequence of numbers and *'s.

Here's the weird part: what does a parser that accepts a "+" return? What about a parser that accepts a "-"? The value of such a parser, as it turns out, is the binary function that it represents! In the case of the implementation below, this is a function pointer of type int(*)(int,int).

/*
* chain(p,op): Parse with p infinitely (until there is no match) folding with op.
*
* p and op are both parsers, but op returns a binary function, given some
* input, and p returns the inputs to that function. For example, if:
*      input: "4"
*      p returns: 4
* No operator is read, no operation is performed. But:
*      input: "4+4"
*      p returns: 4
* op is then parsed with the function, rest:
*      input: "+4"
*      op returns: do_add
*      input: "4"
*      p returns: 4
*      rest returns: 8
* rest applies the operation parsed by op. It alternates between parsing p and
* op until there are no more matches.
*/
constexpr struct Chainl1 {
template< class X, class F >
static Parser<X> rest( const Parser<X>& p, const Parser<F>& op, const X& a ) {
// Alternate between op and p until input is consumed or a parse fails.
auto r = op >>= [=]( const F& f ) {
return p >>= [&]( const X& b ) {
return rest( p, op, f(a,b) );
};
};

// Return the first successful parse, or a if none.
return mplus_first( r, mreturn<Parser>(a) );
}

template< class X, class F >
Parser<X> operator () ( Parser<X> p, Parser<F> op ) const {
return p >>= closet( rest<X,F>, std::move(p), std::move(op) );
}
} chainl1{};

#### Adding the final touches.

The paper describes a few generally useful functions for constructing parsers based off the above function. space (defined above) consumes whitespace. token consumes any trailing whitespace after parsing p.

constexpr struct Token {
template< class X >
Parser<X> operator () ( Parser<X> p ) const {
return p >>= []( X x ) {
return space >> mreturn<Parser>(std::move(x));
};
}
} token{};

symb converts a string to a token.

auto symb = compose( token, string ); // symb(s) = token( string(s) )

apply consumes any leading whitespace.

constexpr struct Apply {
template< class X >
Parser<X> operator () ( Parser<X> p ) const {
return space >> std::move(p);
}
} apply{};

The big idea is that we never want to manually write a function that returns a list of successful parses. It's hard! It's much easier to compose such  functions from smaller, more comprehensible ones and use those to build reasonable complex, but more simple to reason about, parsers.

#### The parser itself.

Now, using all of the tools provided, we can create a parser much more trivially than otherwise--though that is perhaps true of any time one has a new set of tools. First, we define a parser that accepts digits.

constexpr bool is_num( char c ) {
return c >= '0' and c <= '9';
}

/* Parse one digit. */
Parser<int> digit = token( sat(is_num) ) >>= []( char i ) {
return mreturn<Parser>(i-'0');
};

Now, digit("2") returns 2, but (digit >> digit)("22") returns 2 as well! Why? Because the first run of digit extracts the first 2, but throws that value away and the second run of digit extracts the second 2. To parse a two-digit number, we need something like this:

Parser<int> twoDigit = digit >>= []( int x ) {
return digit >>= [x]( int y ) {
return mreturn<Parser>( x*10 + y );
};
};

It extracts the first then the second digit and returns the original number, converted from a string to an int! To parse arbitrarily long numbers (diverging from the paper's version), we can define a chain operation!

int consDigit( int accum, int digit ) { return accum*10 + digit; }
Parser<int> num = chainl1( digit, mreturn<Parser>(consDigit) );

For every two digits parse, num calls consDigit to fold the values together. As mentioned earlier, chainl1 works by alternating between its two parsers. Since the second argument is a parser which consumes no input, num only accepts digits.

Next, we can define the parsers for binary operations.

// Binary operations of type int(*)(int,int).
int do_add(  int x, int y ) { return x + y; }
int do_sub(  int x, int y ) { return x - y; }
int do_mult( int x, int y ) { return x * y; }
int do_div(  int x, int y ) { return x / y; }

auto addop = mplus (
pchar('+') >> mreturn<Parser>(do_add),
pchar('-') >> mreturn<Parser>(do_sub)
);

auto mulop = mplus (
pchar('*') >> mreturn<Parser>(do_mult),
pchar('/') >> mreturn<Parser>(do_div)
);

addop parses either a "+" or "-" and returns either do_add or do_sub, respectively. Because the parsers must return functions of the same types, std::plus and std::minus could not be used.

With this, we can define a term as an alternating sequence of numbers and multiplications and divisions; and an expr(ession) as an alternating sequence of terms, +'s and -'s.

/*
* Parse terms: series of numbers, multiplications and divisions.
* Ex: "1*3*2" -> (3,"*2") -> 6
*/
Parser<int> term = chainl1( num, mulop );

/*
* Parse expressions: series of terms, additions and subtractions.
* Ex: "1+7*9-1" -> (1."+7*9-1") -> (63,"-1") -> 62
*/
Parser<int> expr = chainl1( term, addop );

And we're done! We have just built a calculator! It can evaluate any expression of additions, subtractions, multiplications, divisions, and it is whitespace agnostic. While implementing Parser itself took a considerable amount of work, using it does not.

int main() {
using std::cin;
using std::cout;
using std::endl;

cout << "Welcome to the calculator!\n"
<< "Press ctrl+d or ctrl+c to exit.\n"
<< "Type in an equation and press enter to solve it!\n" << endl;

std::string input;
while( cout << "Solve : " and std::getline(std::cin,input) ) {
auto ans = apply(expr)(input);
if( ans.size() and ans[0].second.size() == 0 )
cout << " = " << ans[0].first;
else
cout << "No answer.";
cout << endl;
}
}

I highly encourage anyone reading this to attempt to compile and modify the source code.

See the gist at github for the source in full: https://gist.github.com/4112114
And for the original parser I wrote: https://gist.github.com/4112114#file_trivial_parser.cpp

## Thursday, November 15, 2012

### A public letter to Microsoft about the CTP.

Dear Microsoft,

I see that you have decided to release C++11 in the form of a CTP. Congratulations on catching up! For a long time, it seemed like you just didn't give a shit, but thankfully that's not true.

I see you now offer variadic templates. Great! You know when GCC 4.3 came out offering back in 2008, and Clang 2.9 the April of last year, it was really amazing, so I'm glad to see you're offering this too now. It's really something that developers chained faithful to MSVC will finally be compiling code written with GCC years ago!

Initializer lists, too!? Wow! How nostalgic. Like when GCC 4.4 came out in '09. Oh, but you can't use it for std::vector? How silly. Well, I'm sure it's just one of those things you'll get around to in the same way you finally got around to C++11. There are probably some major complexities that I am not aware of for integrating this feature into the standard library.

You also now offer delegated constructors. It took GCC a long time to implement that! It only happened earlier this year. Clang didn't even have it until December 2011. Being only a year behind must feel like a major accomplishment. The whole team who implemented this should be promoted for their unusual efficiency.

My, my, default template argument for functions was a huge oversight for the standardizing committee. It's a good thing they corrected themselves, allowing GCC to include it in their 4.3 release series. It's good to see you have also corrected yourselves by including it in your CTP. Developers of MSVC will finally be able to write

template< class X, class Y = type-exp >
Y f( X x ) {return Y(...); }

instead of what we used to have to write:

template< class X >
type-exp(...) f( X x ) { return type-exp(...); }

Remember how it took GCC until 4.5 (April 2010) to get explicit conversion operators in, and Clang until 3.0 in December 2011? Well now MSVC developers too can take advantage of the fact that allowing smart pointers to explicitly convert to bools won't allow them to then convert to ints!

std::unique_ptr<int> p( new int(6); );
if( p ) { } // Explicit conversion!
p + p; // Not allowed!

Have I forgotten a feature to applaud you for? Oh yes, raw string literals! Good job. Not the first here, either, but hey, it's not like you're competing for market share, right? After all, you already got it. Developers are locked in, aren't they? They have do use MSVC to develop professionally for Windows, right? Isn't that the idea?

Now, it would be absolutely horrible if you released all these features that the rest of the C++ community has been using for years and none of your customers knew any of it. So how wonderful it is that you have channel 9 where you have been publishing videos like Scott Meyer's influential Universal References talk and Herb Sutter's (who works for you) talk on the future of our langauge and Lavavej's core C++ course. Your parade of C++ intellectuals surely adds much to the discussion. I wonder: did they use your CTP to research those talks, GCC, or Clang?

So thank you, Microsoft. Thanks for holding the C++ community back several years. Thanks for offering educational content on these features, now that you finally decided to implement them. Thanks for parading all the C++ intellectuals in our faces to get us excited about these features, now that you offer them. Thank you for showing that you really care about advancements in C++, in your products. Thank you for demonstrating that you care about the advancement of the C++ community at-large, when they're using MSVC. Thank you for dishing out pieces of C++11 like chocolate rations. And thank you for hiring Herb Sutter back in 2002, which obviously made you hurry much faster in releasing C++11 features.

Thank you for being you. Without you, we'd all be programming in C++11! That would be insanity.

### Generalized Function Objects Explained (For the C++11 unfluent.)

It occurred to me that some of those who found my "Generic Function Objects" article were not all that familiar with C++11 syntax, and in particular, template template parameters and variadic templates. Learning these concepts is one thing--just takes some googling, reading, and a little practice. Understanding examples like in my article may be more difficult, so I will explain how it works line-by-line. I will not be explaining these features, or how and why they work as that is too much for one blog post to accomplish, but I will be explaining how they work in context.

Note that if one understood the article up to the definition of ConstructT, then feel free to skip to that section.

Update: I have attempted to improve the original article with some of this one, so it may be a little redundant.

#### Binary

Binary defines member functions for partially applying the first and last arguments. I wrote about this back in September.

template< class F, class X >
struct Part {
F f;
X x;

template< class _F, class _X >
constexpr Part( _F&& f, _X&& x )
: f(forward<_F>(f)), x(forward<_X>(x))
{
}

template< class ... Xs >
constexpr auto operator () ( Xs&& ...xs )
-> decltype( f(x,declval<Xs>()...) )
{
return f( x, forward<Xs>(xs)... );
}
};

template< class F, class X > struct RPart {
F f;
X x;

template< class _F, class _X >
constexpr RPart( _F&& f, _X&& x )
: f( forward<_F>(f) ), x( forward<_X>(x) ) { }

template< class ...Y >
constexpr decltype( f(declval<Y>()..., x) )
operator() ( Y&& ...y ) {
return f( forward<Y>(y)..., x );
}
};

template< class F > struct Binary {
template< class X >
constexpr Part<F,X> operator () ( X x ) {
return Part<F,X>( F(), move(x) );
}

template< class X >
constexpr RPart<F,X> with( X x ) {
return RPart<F,X>( F(), move(x) );
}
};

So, given some type, F, inherited from Binary<F>, F is defined as taking one argument (partial application), and calling the member function with (reverse-partial application). F must be a type that defines a two-argument operator() overload.

We define a derivation like so:

constexpr struct Add : public Binary<Add> {
using Binary<Add>::operator();

template< class X, class Y >
constexpr auto operator () ( X&& x, Y&& y )
-> decltype( std::declval<X>() + std::declval<Y>() )
{
return std::forward<X>(x) + std::forward<Y>(y);
}
} add{};

Add, is not a function in the C sense, it's a function type. add is an instance of Add and is a function object. Add does not inherit Binary's operator() overload by default, so we explicitly tell it to by saying "using Binary<Add>::operator()". Binary's with requires no work to inherit.

auto inc = add(1); // Calls Binary<Add>::operator(); returns Part<Add,int>.
auto dec = add.with(-1); // Calls Binary<Add>::with; returns RPart<Add,int>.
int two = inc(1); // Calls Part<Add,int>::operator(); returns add(1,1).
int one = dec(two); // returns add(2,-1).
add(1,2) -- Calls Add::operator(); returns int(3).

#### Chainable.

template< class F > struct Chainable : Binary<F> {
using Binary<F>::operator();

template< class X, class Y >
using R = typename std::result_of< F(X,Y) >::type;

// Three arguments: unroll.
template< class X, class Y, class Z >
constexpr auto operator () ( X&& x, Y&& y, Z&& z )
-> R< R<X,Y>, Z >
{
return F()(
F()( std::forward<X>(x), std::forward<Y>(y) ),
std::forward<Z>(z)
);
}

template< class X, class Y, class ...Z >
using Unroll = typename std::result_of <
Chainable<F>( typename std::result_of<F(X,Y)>, Z... )
>::type;

// Any more? recurse.
template< class X, class Y, class Z, class H, class ...J >
constexpr auto operator () ( X&& x, Y&& y, Z&& z, H&& h, J&& ...j )
-> Unroll<X,Y,Z,H,J...>
{
// Notice how (*this) always gets applied at LEAST three arguments.
return (*this)(
F()( std::forward<X>(x), std::forward<Y>(y) ),
std::forward<Z>(z), std::forward<H>(h), std::forward<J>(j)...
);
}
};

Chainable works in much the same way as Binary does, except that it extends F to take any arbitrary number of arguments (except for zero, but that'd be pretty useless anyway). Redefining Add to be Chainable is not hard.

constexpr struct Add : public Chainable<Add> {
using Chainable<Add>::operator();

template< class X, class Y >
constexpr auto operator () ( X&& x, Y&& y )
-> decltype( std::declval<X>() + std::declval<Y>() )
{
return std::forward<X>(x) + std::forward<Y>(y);
}
} add{};

Only two lines have changed, however add's behaviour has changed dramatically.

int x = add(1,2,3); // Calls Chainable<Add>::operator(X,Y,Z); returns (1+2)+3.
int y = add(1,2,3,4,5,6); // Calls Chainable<Add>::operator(X,Y,Z,H,J...).
auto inc = add(1); // Still calls Binary<Add>::operator().

The three arg version of Chainable<Add> calls add( add(x,y), z ), while the variadic version calls itself( add(x,y), z, h, j... ). It reduces the number of arguments to process by one, being supplied at least four. It is therefore never the base case and always ends by calling its three-arg version.

#### ConstructT.

template< template<class...> class T > struct ConstructT {
template< class ...X, class R = T< typename std::decay<X>::type... > >
constexpr R operator () ( X&& ...x ) {
return R( forward<X>(x)... );
}
};

The first template argument may be confusing to those who have not seen them before. We could write template<class> class T, and that would expect a T that took one type parameter. It may actually take one, zero, or several. template<class...> class T is the generic way to say "we know T takes type parameters, but we don't know how many (and it doesn't yet matter)". It might be std::vector, which can take two; the value type and allocator. It might be std::set, which can take three. (Though, neither vector nor set would work for ConstructT.)

We deduce the return type using the default template parameter, R. std::decay transforms the type such that if we pass in an int&, we get an int back.

typename std::decay<const int&>::type = int
typename std::decay<int&&>::type = int
typename std::decay<int>::type = int

So, if T=std::pair and we pass in an int& and std::string&&, R = std::pair<int,std::string>.

ConstructT perfectly forwards the arguments to T's constructor, but decays the types to ensure that it holds the actual values.

Just the same as with add and Add, we must create an instance of ConstructT to call it.

constexpr auto make_pair = ConstructT<std::pair>();

This version of make_pair behaves just like std::make_pair. Its type is equivalent to this:

template< struct ConstructPair {
template< class ...X, class R = std::pair< typename std::decay<X>::type... > >
constexpr R operator () ( X&& ...x ) {
return R( forward<X>(x)... );
}
};

#### Conclusion.

C++11 is very big and no one feature is incredibly useful, but in conjunction they build up a powerful synergy. If these features had been a part of the language to begin with, there is no question that they would be considered required reading, just as much as std::vector and the <algorithm> library are today. They solve problems that have led to years frustration in developers. Perhaps one of the reasons many hate C++ is because of the lacking of many of these features. Becoming fluent in them makes C++ a much nicer language to speak and communicate with.

## Tuesday, November 13, 2012

### The Object-Function Paradox.

Previously, I discussed using inheritance to simplify the writing of generic functions. However, it occurred to me that I can't find anyone else advocating the same thing. No one has yet told me it's a bad practice, but I can't find any other examples of it on the web. (If anyone knows of one, please relieve me of my ignorance.) It's a very short amount of code. Obvious and intuitive. So what impedes people from thinking of it? For that matter, why do some have difficulties comprehending it?

C++ programmers seem to think of functions as something very distinct from objects and types, so obviously the OOP principles of code reuse don't apply. Indeed, the standard says in the first sentence under "The C++ Object Model" (1.8)

The constructs in a C++ program create, destroy, refer to, access, and manipulate objects. An object is a region of storage. [ Note: A function is not an object, regardless of whether or not it occupies storage in the way that objects do. — end note ]
This is technically correct. Functions cannot be objects, they're more like a lexical representation of a code section. The problem is that objects can look like functions, but if we think of this object as a function, then we contradict ourselves because functions cannot be objects.

The distinction is not so transparent. We can make objects that look, talk, and feel like functions, but they aren't.

So, when working out a problem, if a programmer notices a repetitious pattern, s/he might say "I'll create another function that executes the common code!" However, the repetition moves from the in-lined pattern to the calling convention. Because this programmer believes functions are not objects, the solution of using inheritance is impossible to cogitate. Because of this fallacy, this programmer may find the solution hard to comprehend.

We end up with this train of thought: Objects can be functions, but functions cannot be objects, and therefore objects are not functions.

What does a function do? It executes some arbitrary code, taking in arbitrary parameters and returning some value. Function-objects do just that! So objects can be functions! But functions aren't objects...

Paradoxes stunt innovation by preventing the problem from being worked out in a logical way. One cannot conceive of how to use OOP-features to implement functions if they believe the two are fundamentally different and incompatible.

Take Zeno's famous paradox. At one time, we all believe "all is one". We thought of things as wholes. Zeno seemed to think that odd and pointed out that one can go half way from A to B, and then half way to B from there, but he would never get to B. This is obviously true, but with the assumption that "all is one", we have to think about how, then, can we never reach B since we should eventually be one away? The invention of calculus gave way for mathematicians to properly reason about infinitesimally small ones, and a whole new field of science opened up. Our first physicist was born.

Russle's Paradox led to several attempts at improving set theory to remove the paradox, such as the invention of Type Theory, which is obviously very important to computer science.

In quantum mechanics, Schrodinger's Cat and Bell's Theorem led to a greater understanding of the field. Even today, many first learn of quantum mechanics through the tale of an alive and dead cat.

If I was more knowledgeable of the histories of math and physics, I might know more examples, but I hope my point has been persuasive: Paradoxical thinking holds us back, as individuals, as a community.

I submit to the reader this: Functions are objects. Objects are functions. A function is not a procedure to call, but the pointer to that procedure, and pointers are objects, or it can be an instantiation of a user-defined type (like ConstructChainable). We should think of C-functions as the fundamentally different and incompatible things. They are low-level. Function objects are first-class citizens.

The hope is that by removing this logical inconsistency in our minds, we can explore areas of possibility that we never imagined. We can invent solutions to problems that before would have caused a cognitive dissonance. We can progress in directions we hadn't realized before. We can really discover something really interesting, but only if we keep an open mind.

## Sunday, November 11, 2012

### Generic Function Objects, or Generalizing Associativity, Transitivity, and such abstractions over functions and types.

So, I posted "Rethinking std::binary_function", which was this epiphany that instead of writing all these variadic operator types, I could actually define a base class and inherit its operator overloads. That lead to another realization: https://gist.github.com/4049946. What I am about to elaborate on below feels like a discovery rather than an invention. It's also only a few days old. I normally try to present something much more polished, but this is exciting enough to myself that I want to share it sooner rather than later.

#### Starting from the top.

In "Rethinking std::binary_function", I thought that all binary functions might benefit from being chained, but actually, not all can be. We can write add(1,2,3) and think of it as (1+2)+3 = 6, but what about <, or less? less(1,2,3) would be equivalent to (true < 3), which is only incidentally correct. And so chaining might not be good for all binary functions, but we can at least say that partially applying the front and back might be useful.

template< class F, class X >
struct Part {
F f;
X x;

template< class _F, class _X >
constexpr Part( _F&& f, _X&& x )
: f(forward<_F>(f)), x(forward<_X>(x))
{
}

template< class ... Xs >
constexpr auto operator () ( Xs&& ...xs )
-> decltype( f(x,declval<Xs>()...) )
{
return f( x, forward<Xs>(xs)... );
}
};

template< class F, class X > struct RPart {
F f;
X x;

template< class _F, class _X >
constexpr RPart( _F&& f, _X&& x )
: f( forward<_F>(f) ), x( forward<_X>(x) ) { }

template< class ...Y >
constexpr decltype( f(declval<Y>()..., x) )
operator() ( Y&& ...y ) {
return f( forward<Y>(y)..., x );
}
};

template< class F > struct Binary {
template< class X >
constexpr Part<F,X> operator () ( X x ) {
return Part<F,X>( F(), move(x) );
}

template< class X >
constexpr RPart<F,X> with( X x ) {
return RPart<F,X>( F(), move(x) );
}
};

We might define a subtraction type like so:

constexpr struct Sub : public Binary<Sub> {
using Binary<Sub>::operator();

template< class X, class Y >
constexpr auto operator () ( X&& x, Y&& y )
-> decltype( std::declval<X>() - std::declval<Y>() )
{
return std::forward<X>(x) - std::forward<Y>(y);
}
} sub{};

sub is a function object of type Sub and inherits the partial- and reverse partial-application from Binary<Sub>.

constepxr auto twoMinus = sub(2); // Calls Binary<Sub>::operator(int); returns Part<Sub,int>.
constexptr int zero = twoMinus(2);

constexpr auto minusTwo = sub.with(2); // Calls Binary<Sub>::with(int); returns RPart<Sub,int>;
constexpr int two = minusTwo(4);

constexpr int one = sub(2,1); // Calls Sub::operator(int,int).

#### Associativity and Transitivity.

Addition is an associative operation, by which I mean

x + y + z = (x+y) + z

In particular, this demonstrates left (left-to-right) associativity. We can apply this same principle of associativity to functions!

template< class F > struct Chainable : Binary<F> {
using Binary<F>::operator();

template< class X, class Y >
using R = typename std::result_of< F(X,Y) >::type;

// Three arguments: unroll.
template< class X, class Y, class Z >
constexpr auto operator () ( X&& x, Y&& y, Z&& z )
-> R< R<X,Y>, Z >
{
return F()(
F()( std::forward<X>(x), std::forward<Y>(y) ),
std::forward<Z>(z)
);
}

template< class X, class Y, class ...Z >
using Unroll = typename std::result_of <
Chainable<F>( typename std::result_of<F(X,Y)>, Z... )
>::type;

// Any more? recurse.
template< class X, class Y, class Z, class H, class ...J >
constexpr auto operator () ( X&& x, Y&& y, Z&& z, H&& h, J&& ...j )
-> Unroll<X,Y,Z,H,J...>
{
// Notice how (*this) always gets applied at LEAST three arguments.
return (*this)(
F()( std::forward<X>(x), std::forward<Y>(y) ),
std::forward<Z>(z), std::forward<H>(h), std::forward<J>(j)...
);
}
};

One might define an addition type like this:

constexpr struct Add : public Chainable<Add> {
using Chainable<Add>::operator();

template< class X, class Y >
constexpr auto operator () ( X&& x, Y&& y )
-> decltype( std::declval<X>() + std::declval<Y>() )
{
return std::forward<X>(x) + std::forward<Y>(y);
}
} add{};

Add inherits Binary<Add>'s ::operator() and ::with, and Chainable<Add>'s overloads as well. The three argument overload in Chainable will return add(add(x,y),z). If given four or more arguments, it will call add on the first two, and call itself on the rest, being at least three. The base case for Chainable will always be the three-argument overload.

consexpr auto plusTwo = add(2); // Calls Binary<Add>::operator(int); returns Part<Add,int>.
constexpr int fifteen = add(1,2,3,4,5) // Calls Chainable<Add>::operator(int,int,int,int...).

Operations like less, as mentioned above, are not associative. They are, however, transitive, by which I mean:

x < y < z = (x<y) and (y<z)

In writing a class for transitivity, we can have it just apply each argument to the one right of it, but we need this and to glue the results together. My Transitive class will require both defining the operation (<) and the function that folds the results together (and).

template< class F, class Fold > struct Transitive : Binary<F> {
using Binary<F>::operator();

template< class X, class Y, class Z >
constexpr auto operator () ( X&& x, Y&& y, Z&& z )
-> typename std::result_of<F(X,Y)>::type
{
return Fold() (
F()( forward<X>(x), forward<Y>(y) ),
F()( forward<Y>(y), forward<Z>(z) )
);
}

template< class X, class Y, class Z, class A, class ...B >
constexpr auto operator () ( X&& x, Y&& y, Z&& z, A&& a, B&& ...b )
-> typename std::result_of<F(X,Y)>::type
{
return Fold() ( F()( forward<X>(x), forward<Y>(y) ),
F()( forward<Y>(y), forward<Z>(z),
forward<A>(a), forward<B>(b)... ) );
}
};

We can define less like so:

struct And : Chainable<And> {
using Chainable<And>::operator();

template< class X, class Y >
constexpr auto operator () ( X&& x, Y&& y )
-> decltype( declval<X>() && declval<Y>() )
{
return forward<X>(x) && forward<Y>(y);
}
};

constexpr struct Less : Transitive<Less,And> {
using Transitive<Less,And>::operator();

template< class X, class Y >
constexpr bool operator() ( X&& x, Y&& y ) {
return forward<X>(x) < forward<Y>(y);
}
} less{};

Now, writing less(1,2,3) would be equivalent to writing 1<2 and 2<3. less.with(3) would be a function returning whether x is "less than three".

Here's where things get really interesting. What if I want to use these properties of associativity and transitivity to construct types?

#### From the top, again.

The biggest problem is that types are not functions. Sure, we can write std::pair<X,Y>(x,y) and you might say "Look! A constructor! It's a function!", but we don't like needing to specify our types, so we prefer std::make_pair(x,y). Even though we have this type with a construction function, it's not as useful as a general function. This is a surprisingly common pattern. We make a type, but we want the result's type to be argument dependent, so we make a function that constructs the type. And we do this for every type.

There's make_pair, make_tuple, make_shared, make_unique (eventually), and many, many others. Instead of writing any of these, let's abstract the pattern away using our OOP principles!

template< template<class...> class T > struct ConstructT {
template< class ...X, class R = T< typename std::decay<X>::type... > >
constexpr R operator () ( X&& ...x ) {
return R( forward<X>(x)... );
}
};

std::decay is a handy type that removes any reference or const until we get the type itself.

typename std::decay<const int>::type = int
typename std::decay<int&&>::type = int
typename std::decay<int>::type = int;

When we call an instance of ConstructT, we may pass in references, r-values, or const values, but the return, R, will hold values.

Now, we can write

constexpr auto make_pair = ConstructT<std::pair>();
std::pair<int,int> p = make_pair(1,2);

constexpr auto make_tuple = ConstructT<std::tuple>();

Each of what used to be an entire function, a paragraph, is now a line. Now, for associativity!

template< template<class...> class T >
struct ConstructChainable : Chainable<ConstructT<T>> {
using Self = ConstructChainable<T>;
using Chainable<ConstructT<T>>::operator();

template< class X >
using D = typename std::decay<X>::type;
template< class X, class Y, class R = T< D<X>, D<Y> > >
constexpr R operator () ( X&& x, Y&& y ) {
return R( forward<X>(x), forward<Y>(y) );
}
};

ConstructChainable inherits from Chainable which inherits from Binary, so now we can rewrite the above:

constexpr auto make_pair = ConstructChainable<std::pair>();
constexpr auto pairWith = make_pair.with(y); // Calls Binary<ConstructT<std::pair>>::operator(int).
constexpr auto pairPair = make_pair(1,2,3); // Returns an std::pair< std::pair<int,int>, int >.

All this without having ever explicitly defining make_pair!

Remember the definition of Part from above?

constexpr auto closet   = ConstructChainable<Part>();

This one line is very powerful. Let me demonstrate by showing all the code it replaces!

// An extra, variadic definition of the class.
template< class F, class X1, class ...Xs >
struct Part< F, X1, Xs... >
: public Part< Part<F,X1>, Xs... >
{
template< class _F, class _X1, class ..._Xs >
constexpr Part( _F&& f, _X1&& x1, _Xs&& ...xs )
: Part< Part<F,X1>, Xs... > (
Part<F,X1>( forward<_F>(f), forward<_X1>(x1) ),
forward<_Xs>(xs)...
)
{
}
};

template< class F, class ...X >
constexpr Part<F,X...> closet( F f, X ...x ) {
return Part<F,X...>( move(f), move(x)... );
}

So what does ConstructChainable do? It makes mole hills out of mountains! What's more; it does so optimally. It perfect forwards the arguments all the way to the constructor, whereas I often would write moving functions in order to simplify type deduction.

So, one might have noticed that closet creates a Part, but it's also derived from Binary, so we can write things like

constexpr auto cc = closet(closet);

and all sorts of unexpected things!

#### Conclusion.

I guess one way to describe this phenomenon is perhaps as an update to the factory pattern. I'm tempted to call it a type constructor, but I'm not sure that's technically correct.

This post has been more off-the-cuff than I normally try to be, and I haven't prepared any test source to ease in the process of learning. Still, I hope you find this as fascinating as I do.

Gist: https://gist.github.com/4055136

I use this trick extensively in my library, Pure. (Functional.h)