Boost C++ Libraries

The Standard Template Library (STL) [STL94], now part of the C++ Standard Library [C++98], is a generic container and algorithm library. Typically STL algorithms operate on container elements via function objects. These function objects are passed as arguments to the algorithms.

Any C++ construct that can be called with the function call syntax is a function object. The STL contains predefined function objects for some common cases (such as plus, less and not1). As an example, one possible implementation for the standard plus template is:

template <class T> 
struct plus : public binary_function<T, T, T> {
  T operator()(const T& i, const T& j) const {
    return i + j; 
  }
};

The base class binary_function<T, T, T> contains typedefs for the argument and return types of the function object, which are needed to make the function object adaptable.

In addition to the basic function object classes, such as the one above, the STL contains binder templates for creating a unary function object from an adaptable binary function object by fixing one of the arguments to a constant value. For example, instead of having to explicitly write a function object class like:

class plus_1 {
  int _i;
public:
  plus_1(const int& i) : _i(i) {}
  int operator()(const int& j) { return _i + j; }
};

the equivalent functionality can be achieved with the plus template and one of the binder templates (bind1st). E.g., the following two expressions create function objects with identical functionalities; when invoked, both return the result of adding 1 to the argument of the function object:

plus_1(1)
bind1st(plus<int>(), 1)

The subexpression plus<int>() in the latter line is a binary function object which computes the sum of two integers, and bind1st invokes this function object partially binding the first argument to 1. As an example of using the above function object, the following code adds 1 to each element of some container a and outputs the results into the standard output stream cout.

transform(a.begin(), a.end(), ostream_iterator<int>(cout),
          bind1st(plus<int>(), 1));

To make the binder templates more generally applicable, the STL contains adaptors for making pointers or references to functions, and pointers to member functions, adaptable. Finally, some STL implementations contain function composition operations as extensions to the standard [SGI02].

All these tools aim at one goal: to make it possible to specify unnamed functions in a call of an STL algorithm, in other words, to pass code fragments as an argument to a function. However, this goal is attained only partially. The simple example above shows that the definition of unnamed functions with the standard tools is cumbersome. Complex expressions involving functors, adaptors, binders and function composition operations tend to be difficult to comprehend. In addition to this, there are significant restrictions in applying the standard tools. E.g. the standard binders allow only one argument of a binary function to be bound; there are no binders for 3-ary, 4-ary etc. functions.

The Boost Lambda Library provides solutions for the problems described above:

Lambda expression are common in functional programming languages. Their syntax varies between languages (and between different forms of lambda calculus), but the basic form of a lambda expressions is:

lambda x1 ... xn.e

A lambda expression defines an unnamed function and consists of:

A simple example of a lambda expression is

lambda x y.x+y

Applying the lambda function means substituting the formal parameters with the actual arguments:

(lambda x y.x+y) 2 3 = 2 + 3 = 5 

In the C++ version of lambda expressions the lambda x1 ... xn part is missing and the formal parameters have predefined names. In the current version of the library, there are three such predefined formal parameters, called placeholders: _1, _2 and _3. They refer to the first, second and third argument of the function defined by the lambda expression. For example, the C++ version of the definition

lambda x y.x+y

is

_1 + _2

Hence, there is no syntactic keyword for C++ lambda expressions. The use of a placeholder as an operand implies that the operator invocation is a lambda expression. However, this is true only for operator invocations. Lambda expressions containing function calls, control structures, casts etc. require special syntactic constructs. Most importantly, function calls need to be wrapped inside a bind function. As an example, consider the lambda expression:

lambda x y.foo(x,y)

Rather than foo(_1, _2), the C++ counterpart for this expression is:

bind(foo, _1, _2)

We refer to this type of C++ lambda expressions as bind expressions.

A lambda expression defines a C++ function object, hence function application syntax is like calling any other function object, for instance: (_1 + _2)(i, j).