The library consists of include files only, hence there is no installation procedure. The boost include directory must be on the include path. There are a number of include files that give different functionality:

All definitions are placed in the namespace boost::lambda and its subnamespaces.

In most code examples, we omit the namespace prefixes for names in the std and boost::lambda namespaces. Implicit using declarations

using namespace std;
using namespace boost::lambda;

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> : public binary_function<T, T, T>
struct plus {
  T operator()(const T& i, const T& j) const {
    return i + j; 
  }
};

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; }
};

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

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

lambda x y.x+y

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

In the C++ version of lambda expressions the lambda x₁ ... x_n 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

_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)

bind(foo, _1, _2)

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).

In this section we give basic examples of using BLL lambda expressions in STL algorithm invocations. We start with some simple expressions and work up. First, we initialize the elements of a container, say, a list, to the value 1:

list<int> v(10);
for_each(v.begin(), v.end(), _1 = 1);

Next, we create a container of pointers and make them point to the elements in the first container v:

vector<int*> vp(10); 
transform(v.begin(), v.end(), vp.begin(), &_1);

The next code fragment changes the values in v. For each element, the function foo is called. The original value of the element is passed as an argument to foo. The result of foo is assigned back to the element:

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

The next step is to sort the elements of vp:

sort(vp.begin(), vp.end(), *_1 > *_2);

Finally, the following for_each call outputs the sorted content of vp separated by line breaks:

for_each(vp.begin(), vp.end(), cout << *_1 << '\n');

for_each(vp.begin(), vp.end(), cout << '\n' << *_1);

for_each(vp.begin(), vp.end(), cout << constant('\n') << *_1);

During the invocation of a lambda functor, the actual arguments are substituted for the placeholders. The placeholders do not dictate the type of these actual arguments. The basic rule is that a lambda function can be called with arguments of any types, as long as the lambda expression with substitutions performed is a valid C++ expression. As an example, the expression _1 + _2 creates a binary lambda functor. It can be called with two objects of any types A and B for which operator+(A,B) is defined (and for which BLL knows the return type of the operator, see below).

C++ lacks a mechanism to query a type of an expression. However, this precise mechanism is crucial for the implementation of C++ lambda expressions. Consequently, BLL includes a somewhat complex type deduction system which uses a set of traits classes for deducing the resulting type of lambda functions. It handles expressions where the operands are of built-in types and many of the expressions with operands of standard library types. Many of the user defined types are covered as well, particularly if the user defined operators obey normal conventions in defining the return types.

There are, however, cases when the return type cannot be deduced. For example, suppose you have defined:

C operator+(A, B);

A a; B b; (_1 + _2)(a, b);

There are two alternative solutions to this. The first is to extend the BLL type deduction system to cover your own types (see Section 6). The second is to use a special lambda expression (ret) which defines the return type in place (see Section 5.4):

A a; B b; ret<C>(_1 + _2)(a, b);

For bind expressions, the return type can be defined as a template argument of the bind function as well:

bind<int>(foo, _1, _2);

A general restriction for the actual arguments is that they cannot be non-const rvalues. For example:

int i = 1; int j = 2; 
(_1 + _2)(i, j); // ok
(_1 + _2)(1, 2); // error (!)

By default, temporary const copies of the bound arguments are stored in the lambda functor. This means that the value of a bound argument is fixed at the time of the creation of the lambda function and remains constant during the lifetime of the lambda function object. For example:

int i = 1;
(_1 = 2, _1 + i)(i);

As said, this is the default behavior for which there are exceptions. The exact rules are as follows:

The BLL defines three placeholder types: placeholder1_type, placeholder2_type and placeholder3_type. BLL has a predefined placeholder variable for each placeholder type: _1, _2 and _3. However, the user is not forced to use these placeholders. It is easy to define placeholders with alternative names. This is done by defining new variables of placeholder types. For example:

boost::lambda::placeholder1_type X;
boost::lambda::placeholder2_type Y;
boost::lambda::placeholder3_type Z;

The use of placeholders in the lambda expression determines whether the resulting function is nullary, unary, binary or 3-ary. The highest placeholder index is decisive. For example:

_1 + 5              // unary
_1 * _1 + _1        // unary
_1 + _2             // binary
bind(f, _1, _2, _3) // 3-ary
_3 + 10             // 3-ary

int i, j, k; 
_1(i, j, k)        // returns i, discards j and k
(_2 + _2)(i, j, k) // returns j+j, discards i and k

In addition to these three placeholder types, there is also a fourth placeholder type placeholderE_type. The use of this placeholder is defined in Section 5.7 describing exception handling in lambda expressions.

When an actual argument is supplied for a placeholder, the parameter passing mode is always by reference. This means that any side-effects to the placeholder are reflected to the actual argument. For example:

int i = 1; 
(_1 += 2)(i);         // i is now 3
(++_1, cout << _1)(i) // i is now 4, outputs 4

The basic rule is that any C++ operator invocation with at least one argument being a lambda expression is itself a lambda expression. Almost all overloadable operators are supported. For example, the following is a valid lambda expression:

cout << _1, _2[_3] = _1 && false

However, there are some restrictions that originate from the C++ operator overloading rules, and some special cases.

int i; 
_1 = i;      // ok
i = _1;      // not ok. i is not a lambda expression

var(i) = _1; // ok

bool flag = true; int i = 0;
(_1 || ++_2)(flag, i);

for_each(a.begin(), a.end(), (++_1, cout << _1));

Bind expressions can have two forms:

bind(target-function, bind-argument-list)
bind(target-member-function, object-argument, bind-argument-list)

The return type of the lambda functor created by the bind expression can be given as an explicitly specified template parameter, as in the following example:

bind<RET>(target-function, bind-argument-list)

The following sections describe the different types of bind expressions.

X foo(A, B, C); A a; B b; C c;
bind(foo, _1, _2, c)(a, b);
bind(&foo, _1, _2, c)(a, b);
bind(_1, a, b, c)(foo);

void foo(int);
void foo(float);
int i; 
  ...
bind(&foo, _1)(i);                            // error 
  ...
void (*pf1)(int) = &foo;
bind(pf1, _1)(i);                             // ok
bind(static_cast<void(*)(int)>(&foo), _1)(i); // ok

bind(target-member-function, object-argument, bind-argument-list)

bool A::foo(int) const; 
A a;
vector<int> ints; 
  ...
find_if(ints.begin(), ints.end(), bind(&A::foo, a, _1)); 
find_if(ints.begin(), ints.end(), bind(&A::foo, &a, _1));

bool A::foo(int); 
list<A> refs; 
list<A*> pointers; 
  ...
find_if(refs.begin(), refs.end(), bind(&A::foo, _1, 1)); 
find_if(pointers.begin(), pointers.end(), bind(&A::foo, _1, 1));

class A {
  int i; mutable int j;
public:

  A(int ii, int jj) : i(ii), j(jj) {};
  void set_i(int x) { i = x; }; 
  void set_j(int x) const { j = x; }; 
};

A a(0,0); int k = 1;
bind(&A::set_i, &a, _1)(k); // a.i == 1
bind(&A::set_j, &a, _1)(k); // a.j == 1

A a(0,0); int k = 1;
bind(&A::set_i, a, _1)(k); // error; a const copy of a is stored. 
                           // Cannot call a non-const function set_i
bind(&A::set_j, a, _1)(k); // a.j == 0, as a copy of a is modified

bind(&A::set_i, ref(a), _1)(k); // a.j == 1
bind(&A::set_j, cref(a), _1)(k); // a.j == 1

A a(0,0);
bind(&A::set_i, _1, 1)(a); // a.i == 1
bind(&A::set_j, _1, 1)(a); // a.j == 1

struct A { int data; };
A a;
bind(&A::data, _1)(a) = 1;     // a.data == 1

const A ca = a;
bind(&A::data, _1)(ca) = 1;     // error

struct A {
  template <class Args> struct sig { typedef B type; }
  B operator()(X, Y, Z); 
};

struct A {

  // the return type equals the third argument type:
  template<class T1, T2, T3>
  T3 operator()(const T1& t1, const T2& t2, const T3& t3);

  template <class Args> 
  class sig {
    // get the third argument type (4th element)
    typedef typename 
      boost::tuples::element<3, Args>::type T3;
  public:
    typedef typename 
      boost::remove_cv<T3>::type type;
  }
};

int i = 1;
bind(plus<int>(), _1, 1)(i);              // error, no sig template
bind(std_functor(plus<int>()), _1, 1)(i); // ok

The return type deduction system may not be able to deduce the return types of some user defined operators or bind expressions with class objects. A special lambda expression type is provided for stating the return type explicitly and overriding the deduction system. To state that the return type of the lambda functor defined by the lambda expression e is T, you can write:

ret<T>(e);

A a; B b;
C operator+(A, B);
int operator*(A, B); 
  ...
ret<D>(_1 + _2)(a, b);     // error (C cannot be converted to D)
ret<C>(_1 + _2)(a, b);     // ok
ret<float>(_1 * _2)(a, b); // ok (int can be converted to float)
  ...
struct X {
  Y operator(int)();   
};
  ...
X x; int i;
bind(x, _1)(i);            // error, return type cannot be deduced
ret<Y>(bind(x, _1))(i);    // ok

bind<Z>(x, _1)(i);

Note that within nested lambda expressions, the ret must be used at each subexpression where the deduction would otherwise fail. For example:

A a; B b;
C operator+(A, B); D operator-(C);
  ...
ret<D>( - (_1 + _2))(a, b); // error 
ret<D>( - ret<C>(_1 + _2))(a, b); // ok

If you find yourself using ret repeatedly with the same types, it is worth while extending the return type deduction (see Section 6).

struct F { int operator()(int i) const; }; 
F f;
  ...
bind(f, _1);           // fails, cannot deduce the return type
ret<int>(bind(f, _1)); // ok
  ...
bind(f, 1);            // fails, cannot deduce the return type
ret<int>(bind(f, 1));  // fails as well!

bind<int>(f, 1);       // ok

The unary functions constant, constant_ref and var turn their argument into a lambda functor, that implements an identity mapping. The former two are for constants, the latter for variables. The use of these delayed constants and variables is sometimes necessary due to the lack of explicit syntax for lambda expressions. For example:

for_each(a.begin(), a.end(), cout << _1 << ' ');
for_each(a.begin(), a.end(), cout << ' ' << _1);

for_each(a.begin(), a.end(), cout << constant(' ') << _1);

Sometimes we need to delay the evaluation of a variable. Suppose we wanted to output the elements of a container in a numbered list:

int index = 0; 
for_each(a.begin(), a.end(), cout << ++index << ':' << _1 << '\n');
for_each(a.begin(), a.end(), cout << ++var(index) << ':' << _1 << '\n');

In sum, var(x) creates a nullary lambda functor, which stores a reference to the variable x. When the lambda functor is invoked, a reference to x is returned.

var_type<T>::type delayed_i(var(i));
constant_type<T>::type delayed_c(constant(c));

int i = 0; int j;
for_each(a.begin(), a.end(), (var(j) = _1, _1 = var(i), var(i) = var(j))); 

int i = 0; int j;
var_type<int>::type vi(var(i)), vj(var(j));
for_each(a.begin(), a.end(), (vj = _1, _1 = vi, vi = vj));

constant_type<char>::type space(constant(' '));
for_each(a.begin(),a.end(), cout << space << _1);

int i; 
i = _1;       // error
var(i) = _1;  // ok

BLL defines several functions to create lambda functors that represent control structures. They all take lambda functors as parameters and return void. To start with an example, the following code outputs all even elements of some container a:

for_each(a.begin(), a.end(), 
         if_then(_1 % 2 == 0, cout << _1));  

The BLL supports the following function templates for control structures:

if_then(condition, then_part)
if_then_else(condition, then_part, else_part)
if_then_else_return(condition, then_part, else_part)
while_loop(condition, body)
while_loop(condition) // no body case
do_while_loop(condition, body)
do_while_loop(condition) // no body case 
for_loop(init, condition, increment, body)
for_loop(init, condition, increment) // no body case
switch_statement(...)

condition ? then_part : else_part

Delayed variables tend to be commonplace in control structure lambda expressions. For instance, here we use the var function to turn the arguments of for_loop into lambda expressions. The effect of the code is to add 1 to each element of a two-dimensional array:

int a[5][10]; int i;
for_each(a, a+5, 
  for_loop(var(i)=0, var(i)<10, ++var(i), 
           _1[var(i)] += 1));  

The BLL supports an alternative syntax for control expressions, suggested by Joel de Guzmann. By overloading the operator[] we can get a closer resemblance with the built-in control structures:

if_(condition)[then_part]
if_(condition)[then_part].else_[else_part]
while_(condition)[body]
do_[body].while_(condition)
for_(init, condition, increment)[body]

for_each(a.begin(), a.end(), 
         if_(_1 % 2 == 0)[ cout << _1 ])  

The lambda expressions for switch control structures are more complex since the number of cases may vary. The general form of a switch lambda expression is:

switch_statement(condition, 
  case_statement<label>(lambda expression),
  case_statement<label>(lambda expression),
  ...
  default_statement(lambda expression)
)

case 1: 
  evaluate lambda functor a; 
  break;

As a concrete example, the following code iterates over some container v and ouptuts “zero” for each 0, “one” for each 1, and “other: n” for any other value n. Note that another lambda expression is sequenced after the switch_statement to output a line break after each element:

std::for_each(v.begin(), v.end(),
  ( 
    switch_statement(
      _1,
      case_statement<0>(std::cout << constant("zero")),
      case_statement<1>(std::cout << constant("one")),
      default_statement(cout << constant("other: ") << _1)
    ), 
    cout << constant("\n") 
  )
);

The BLL provides lambda functors that throw and catch exceptions. Lambda functors for throwing exceptions are created with the unary function throw_exception. The argument to this function is the exception to be thrown, or a lambda functor which creates the exception to be thrown. A lambda functor for rethrowing exceptions is created with the nullary rethrow function.

Lambda expressions for handling exceptions are somewhat more complex. The general form of a lambda expression for try catch blocks is as follows:

try_catch(
  lambda expression,
  catch_exception<type>(lambda expression),
  catch_exception<type>(lambda expression),
  ...
  catch_all(lambda expression)
)

catch(T& e) { ... }

The Example 1 demonstrates the use of the BLL exception handling tools. The first handler catches exceptions of type foo_exception. Note the use of _1 placeholder in the body of the handler.

The second handler shows how to throw exceptions, and demonstrates the use of the exception placeholder _e. It is a special placeholder, which refers to the caught exception object within the handler body. Here we are handling an exception of type std::exception, which carries a string explaining the cause of the exception. This explanation can be queried with the zero-argument member function what. The expression bind(&std::exception::what, _e) creates the lambda function for making that call. Note that _e cannot be used outside of an exception handler lambda expression. The last line of the second handler constructs a new exception object and throws that with throw exception. Constructing and destructing objects within lambda expressions is explained in Section 5.8

Finally, the third handler (catch_all) demonstrates rethrowing exceptions.

for_each(
  a.begin(), a.end(),
  try_catch(
    bind(foo, _1),                 // foo may throw
    catch_exception<foo_exception>(
      cout << constant("Caught foo_exception: ") 
           << "foo was called with argument = " << _1
    ),
    catch_exception<std::exception>(
      cout << constant("Caught std::exception: ") 
           << bind(&std::exception::what, _e),
      throw_exception(bind(constructor<bar_exception>(), _1)))
    ),      
    catch_all(
      (cout << constant("Unknown"), rethrow())
    )
  )
);

Operators new and delete can be overloaded, but their return types are fixed. Particularly, the return types cannot be lambda functors, which prevents them to be overloaded for lambda expressions. It is not possible to take the address of a constructor, hence constructors cannot be used as target functions in bind expressions. The same is true for destructors. As a way around these constraints, BLL defines wrapper classes for new and delete calls, as well as for constructors and destructors. Instances of these classes are function objects, that can be used as target functions of bind expressions. For example:

int* a[10];
for_each(a, a+10, _1 = bind(new_ptr<int>())); 
for_each(a, a+10, bind(delete_ptr(), _1));

As an example of constructor calls in lambda expressions, the following code reads integers from two containers x and y, constructs pairs out of them and inserts them into a third container:

vector<pair<int, int> > v;
transform(x.begin(), x.end(), y.begin(), back_inserter(v),
          bind(constructor<pair<int, int> >(), _1, _2));

The BLL defines common STL algorithms as function object classes, instances of which can be used as target functions in bind expressions. For example, the following code iterates over the elements of a two-dimensional array, and computes their sum.

int a[100][200];
int sum = 0;

std::for_each(a, a + 100, 
	      bind(ll::for_each(), _1, _1 + 200, protect(sum += _1)));

Note that there is no easy way to express an overloaded member function call in a lambda expression. This limits the usefulness of nested STL algorithms, as for instance the begin function has more than one overloaded definitions in container templates. In general, something analogous to the pseudo-code below cannot be written:

std::for_each(a.begin(), a.end(), 
	      bind(ll::for_each(), _1.begin(), _1.end(), protect(sum += _1)));

std::for_each(a.begin(), a.end(), 
	      bind(ll::for_each(), 
                   bind(call_begin(), _1), bind(call_end(), _1),
                        protect(sum += _1)));

In theory, all overhead of using STL algorithms and lambda functors compared to hand written loops can be optimized away, just as the overhead from standard STL function objects and binders can. Depending on the compiler, this can also be true in practice. We ran two tests with the GCC 3.0.4 compiler on 1.5 GHz Intel Pentium 4. The optimization flag -03 was used.

In the first test we compared lambda functors against explicitly written function objects. We used both of these styles to define unary functions which multiply the argument repeatedly by itself. We started with the identity function, going up to x⁵. The expressions were called inside a std::transform loop, reading the argument from one std::vector<int> and placing the result into another. The length of the vectors was 100 elements. The running times are listed in Table 3. We can observe that there is no significant difference between the two approaches.

In the second test we again used std::transform to perform an operation to each element in a 100-element long vector. This time the element type of the vectors was double and we started with very simple arithmetic expressions and moved to more complex ones. The running times are listed in Table 4. Here, we also included classic STL style unnamed functions into tests. We do not show these expressions, as they get rather complex. For example, the last expression in Table 4 written with classic STL tools contains 7 calls to compose2, 8 calls to bind1st and altogether 14 constructor invocations for creating multiplies, minus and plus objects. In this test the BLL expressions are a little slower (roughly 10% on average, less than 14% in all cases) than the corresponding hand-written function objects. The performance hit is a bit greater with classic STL expressions, up to 27% for the simplest expressios.

The tests suggest that the BLL does not introduce a loss of performance compared to STL function objects. With a reasonable optimizing compiler, one should expect the performance characteristics be comparable to using classic STL. Moreover, with simple expressions the performance can be expected to be close to that of explicitly written function objects. Note however, that evaluating a lambda functor consist of a sequence of calls to small functions that are declared inline. If the compiler fails to actually expand these functions inline, the performance can suffer. The running time can more than double if this happens. Although the above tests do not include such an expression, we have experienced this for some seemingly simple expressions.

Some additional performance testing with an earlier version of the library is described [Jär00].

The BLL uses templates rather heavily, performing numerous recursive instantiations of the same templates. This has (at least) three implications:

The BLL works with the following compilers, that is, the compilers are capable of compiling the test cases that are included with the BLL:

Sometimes it is convenient to store lambda functors in variables. However, the types of even the simplest lambda functors are long and unwieldy, and it is in general unfeasible to declare variables with lambda functor types. The Boost Function library [function] defines wrappers for arbitrary function objects, for example lambda functors; and these wrappers have types that are easy to type out. For example:

boost::function<int(int, int)> f = _1 + _2;
boost::function<int&(int&)> g = (_1 += 10);
int i = 1, j = 2;
f(i, j); // returns 3
g(i);    // sets i to = 11;

int* sum = new int();
*sum = 0;
boost::function<int&(int)> counter = *sum += _1;
counter(5); // ok, *sum = 5;
delete sum; 
counter(3); // error, *sum does not exist anymore

The Boost Bind [bind] library has partially overlapping functionality with the BLL. Basically, the Boost Bind library (BB in the sequel) implements the bind expression part of BLL. There are, however, some semantical differerences.

The BLL and BB evolved separately, and have different implementations. This means that the bind expressions from the BB cannot be used within bind expressions, or within other type of lambda expressions, of the BLL. The same holds for using BLL bind expressions in the BB. The libraries can coexist, however, as the names of the BB library are in boost namespace, whereas the BLL names are in boost::lambda namespace.

The BLL requires a compiler that is reasonably conformant to the C++ standard, whereas the BB library is more portable, and works with a larger set of compilers.

The following two sections describe what are the semantic differences between the bind expressions in BB and BLL.

template<class F>
int foo(const F& f) {
  int x;
  ..
  bind(f, _1)(x);
  ...
}

int bar(int, int);
nested(bind(bar, 1, _1));

bind(bind(bar, 1, _1), _1)(x)

bar(1, x)(x)

bar(1, x)

bind(unlambda(f), _1)(x);

The BB library supports up to nine placeholders, while the BLL defines only three placeholders. The rationale for not providing more, is that the highest arity of the function objects accepted by any STL algorithm is two. The placeholder count is easy to increase in the BB library. In BLL it is possible, but more laborous. The BLL currently passes the actual arguments to the lambda functors internally just as they are and does not wrap them inside a tuple object. The reason for this is that some widely used compilers are not capable of optimizing the intermediate tuple objects away. The creation of the intermediate tuples would cause a significant performance hit, particularly for the simplest (and thus the most common) lambda functors. We are working on a hybrid approach, which will allow more placeholders but not compromise the performance of simple lambda functors.