C++ Blog

Functional Programming & Boost.Lambda Programming

Posted in boost, templates by Umesh Sirsiwal on December 26, 2009

I will like to take a break from Boost.Spirit related topic to talk about Functional Programming. Understanding of Functional Programming is essential for understanding how Spirit related actions are implemented. Typical object oriented programming paradigm combines mutable data and set of algorithms which operates on data. In contrast FP avoids mutable data or state and emphasizes on application of functions. From Wikipedia:

In practice, the difference between a mathematical function and the notion of a “function” used in imperative programming is that imperative functions can have side effects, changing the value of already calculated computations. Because of this they lack referential transparency, i.e. the same language expression can result in different values at different times depending on the state of the executing program. Conversely, in functional code, the output value of a function depends only on the arguments that are input to the function, so calling a function f twice with the same value for an argument x will produce the same result f(x) both times. Eliminating side-effects can make it much easier to understand and predict the behavior of a program, which is one of the key motivations for the development of functional programming.

STL provides set of algorithms which can be viewed as FP. For example std::copy will always copy source to destination.

The next concept in FP is called currying, technique in which a function is applied to its arguments one at a time, with each application returning a new function that accepts the next argument. The STL function bind1st, bind2nd and binary_compose can be used for currying

All funcitonal programming languages are based on Lambda Calculus introduced in 1930s which is based on anonymous functions and currying. You can read more on it here.

Boost.Lambda and Boost.Phoenix introduce formal system of funcitonal programming and lambda expressions to C++. I typically use Boost.Lambda. I only use Phoenix when using Spirit since they are more closely integrated. They share a lot of similar concept. This post will discuss Boost.Lambda. The next post will use these concepts to introduce Phonix as applied to Boost.Spirit.

Let us start with a simple lambda expression _1 = 1 is definition of an anonymous function which takes one argument and sets it to 1. So to initialize a variable to 1 you could write:

(_1 + 1)(i);

or if you wanted to initialize all variables in a container to 1, you would write something like:

std::vector v;

std::for_each(v.begin(), v.end(), _1=1);

or to print everyobject in a container:

std::for_each(v.begin(), v.end(), std::cout << _1);

What if you wanted to define a function with calls a function with one argument and assigns results to the same argument:

That function will be _1 = bind(foo, _1);

Bind is generalized version of std::bind1st and bind2nd. With the above expression in place one can write:

(_1 = bind(foo, _1))(i);

Which will be equivalent to:

i = foo(i);

So with for_each one can write:

std::for_each(v.begin(), v.end(); _1 = bind(foo, _1));

_1 in the above examples are called placeholders which are equlvalent of lambda in the lambda expression. The above can be generalized with larger number of placeholders. For example one can write: (_1 + _2) to create a function which adds its two arguments. Boost Lambda defines up to 3 place holders. Higher order functions can be constructed using currying.

A function definition which used _2 takes 2 arguments and one which uses _3 takes 3 arguments.

For example _3 = 1, takes 3 argument and

(_3 = 1)(k) will have compile time errors.

(_3 = 1)(i,j,k) is good and is equivalent to k = 1.

Above, we are using simple expressions to create anonymous functions which do not have side effects and depend only on their arguments. As alluded earlier BLL also provides bind expression as generalization of bind1st and bind2nd. With BLL bind expression it is possible to bind any method with up to 9 arguments for delayed executions. It can target C++ class members, or simple functions as target. The syntax used is similar to bind1st and bind2nd.

Advertisements
Tagged with: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: