Document number: N1438=03-0020
Programming Language C++, Library Subgroup
 
Peter Dimov <pdimov@mmltd.net>
Douglas Gregor <gregod@cs.rpi.edu>
Jaakko Järvi <jajarvi@cs.indiana.edu>
Gary Powell <powellg@amazon.com>
 
February 28, 2003

A Proposal to Add an Enhanced Binder to the Library Technical Report

I. Motivation

The standard C++ library supports and encourages a powerful programming style that relies on a combination of generic algorithms and small utility components known as function objects, used to adapt algorithm behavior. A collection of standard algorithms that cover a wide range of practical problems is provided by the standard header <algorithm> . The standard header <functional> provides some commonly used function objects, and algorithms are able to work with ordinary C++ functions as well. Nevertheless, the problem at hand often calls for a slightly different function object. For example, the order of the two parameters may need to be reversed, one of the parameters may need to have a specific value, or the desired functionality may be already present but provided by a member function.

One obvious solution is to write a new function or a function object by hand. This is often tedious, and the result is typically difficult to reuse, being tightly specialized to handle one particular situation. The standard library recognizes the need of function object creation tools, and attempts to provide a solution in the form of the function object adaptors bind1st, bind2nd, ptr_fun, mem_fun, and mem_fun_ref.

The standard adaptors bind1st and bind2nd have a number of limitations. They do not support function objects with reference arguments well, they only support adaptable function objects forcing users to adapt pointers to functions and pointers to member functions manually using ptr_fun, mem_fun, or mem_fun_ref as appropriate, and they only produce unary function objects given a binary function object. Some of these problems are described in [Simonis00]. [Järvi00], [Rodgers00] and [Williams01] offer solutions.

Function object composition libraries ([Josuttis00], [SGI97a], [SGI97b]) provide another useful tool for function object creation.

Lambda libraries ([Boost02], [Guzman02]) use operator overloading and expression template techniques to go even further. They provide a powerful framework that is not constrained to pre-existing function objects. As a result, these libraries can duplicate most of the functionality of the existing facilities provided in <functional>, while offering a familiar syntax built on C++ expressions. However, due to language limitations, most notably lack of a suitable typeof operator [Stroustrup00], such a library is not implementable in its "perfect" form, although the existing implementations use increasingly sophisticated heuristics to approximate typeof. Furthermore, it should be noted that the field is still a subject of active research [Järvi03].

This document proposes an enhanced binder facility that:

A. Examples

The following example demonstrates the basic functionality of bind:

double m; double s; double x;
double gauss(double x, double mean, double std);

bind(gauss, _1, m, s);             // #1
bind(gauss, x, _1, _2);            // #2
bind(gauss, bind(std::rand), m, s) // #3

Line #1 applies the gauss function partially, binding the parameters mean and std to m and s, respectively, resulting in a unary function. When called with an actual argument, say x, the special placeholder argument _1 is replaced by x and the gauss function is invoked with x, m, and s. Hence, bind(gauss, _1, m, s)(x) computes the same result as gauss(x, m, s). In line #2 we are using another placeholder variable _2, and the result is a binary function. The expression in line #3 shows how function compositions can be expressed as nested bind functions. Here, the result is a zero-argument function that calls gauss(std::rand(), m, s) on every invocation.

A simple demonstration of bind interacting with a standard algorithm is given by the following example:

class Employee
{
public:

  int number() const;
};

std::vector<Employee> v;

// sort by employee ID number

std::sort(v.begin(), v.end(), 
  bind(std::less<int>(),
    bind(&Employee::number, _1),
    bind(&Employee::number, _2)
  )
);

Note that the syntax of the bind calls doesn't change if number is made a public data member of Employee.

Finally, an example of bind and function [Gregor02] being used together:

class button
{
public:

    function< void() > onClick;
};

class player
{
public:

    void play(bool m);
};

button playButton, stopButton;
player thePlayer;

void connect()
{
    playButton.onClick = bind(&player::play, &thePlayer, true);
    stopButton.onClick = bind(&player::play, &thePlayer, false);
}

II. Impact On the Standard

This proposal is almost a pure library extension. It proposes changes to an existing header, <functional>, but it does not require changes to any standard classes or functions and it does not require changes to any of the standard requirement tables.

The proposal does not require any changes in the core language, although it would benefit greatly from a solution to the forwarding problem [Dimov02] or from a typeof extension [Stroustrup02]. Two independent and widely used implementations exist [Boost01] [Boost02].

In order to transparently handle pointers to members as function objects, the proposal depends on the pointer to member adaptor mem_fn [Dimov03].

To allow users to indicate that a function object should store references instead of values, this proposal depends on the auxilliary class template reference_wrapper [Gregor03a].

III. Design Decisions

A. Open and Closed Implementations

This proposal defines the class templates is_placeholder and is_bind_expression, used by bind to recognize placeholders and nested subexpressions, respectively.

Open implementations honor user specializations of is_placeholder and is_bind_expression, allowing user extensibility. Closed implementations do not.

Existing implementations are closed. Boost.Bind's primary goal has been portability to a wide range of compilers. The bind implementation in Boost.Lambda is tightly integrated with the rest of the library. However, as standard implementations of bind start becoming available, we firmly believe that a public extension interface would benefit libraries that aim to go beyond the functionality provided by bind [Boost02] [Guzman02]. Such libraries can even recognize each other's function objects and placeholders through the standard interface presented in this proposal.

Therefore, this proposal requires an open implementation.

B. Unspecified Return Types and Placeholder Types

This proposal does not specify the return types of the various bind overloads and the types of the placeholder variables. The exact types are almost never needed, are too unwieldy to manipulate, and vary greatly between existing implementations. For example, the innocent expression

bind(&X::f, &x, _1)

typically has a return type of

boost::_bi::bind_t<void, boost::_mfi::mf1<void, X, int>, boost::_bi::list2<boost::_bi::value<X *>, boost::arg<1> > >

in Boost.Bind (the actual type may vary across compilers), and

boost::lambda::lambda_functor<boost::lambda::lambda_functor_base<boost::lambda::action<3, boost::lambda::function_action<3, boost::lambda::detail::unspecified> >, boost::tuples::tuple<void (X::*const)(int), X * const, boost::lambda::lambda_functor< boost::lambda::placeholder<1> > const, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type> > >

in Boost.Lambda.

C. Placeholders Defined in a Nested Namespace

The placeholder variables _1, _2, ... are defined in a nested namespace, std::ph, in order to allow a single

using namespace std::ph;

directive to make them visible without qualification without bringing the whole namespace std into scope.

This proposal diverges from existing implementations in this regard. Boost.Bind defines its placeholders in a global unnamed namespace. Boost.Lambda defines both the bind function templates and the placeholders in the same namespace, boost::lambda.

D. Optional DefaultConstructible and Assignable Requirements

Some libraries create iterators that store function objects [Siek00]. As most iterators need to be DefaultConstructible and Assignable, this proposal requires implementations to document whether function objects produced by bind conform to these requirements.

Boost.Bind has DefaultConstructible and Assignable placeholders, and produces DefaultConstructible and/or Assignable function objects when all arguments to bind are DefaultConstructible and/or Assignable.

Boost.Lambda overloads the assignment operator to create a lambda expression, and its function objects and placeholders aren't Assignable.

E. result_type Requirement

It is generally accepted as good practice for a function object type F to define a nested typedef F::result_type that denotes the return type of F::operator(). Return type inference is difficult in the current language, and many libraries rely on result_type instead. Additionally, modern programming techniques allow the existence of result_type to be determined at compile time. The presence of result_type can even be used to enable an overload only for function objects.

Therefore, this proposal requires implementations to define result_type when it can be determined.

As a side note, as the current language allows fairly acceptable forwarding [Dimov02], the argument type typedefs described in 20.3/5 are rarely, if ever, required.

F. Arity Errors

In our experience, one of the most common user errors is invoking bind with a number of arguments that does not correspond to the arity of the function object being bound. In particular, it is easy to forget that pointers to members have an additional implicit argument that identifies the object.

It is important to detect these mistakes as early as possible, at the point where bind is called, hence the "f(w1, ..., wm) must be a valid expression" requirement in the proposed text.

Boost.Bind implements this early check by using separate overloads for function pointers and member pointers.

G. Dependency on mem_fn

This proposal specifies the behavior of bind with a pointer to member as a first argument in terms of mem_fn [Dimov03] to avoid unnecessary duplication. Within the scope of this proposal, implementations are not required to provide, or actually call, mem_fn.

H. bind Uses Pass by Value

The bind specification uses pass by value signatures to take advantage of the automatic function- and array-to-pointer decay, but the number of copies that is made for each argument is not specified. This is consistent with the resolution of Library Issue 181.

The additional CopyConstructible requirement is imposed to disallow arguments of types such as std::auto_ptr that implement destructive copy.

I. Qualifier Propagation

As the arguments passed to bind are stored in the returned function object, and are part of its state, they should inherit its cv-qualifiers, if any.

J. result_of

This proposal specifies a class template, result_of, that can be specialized by users to provide a hint to the implementation about the return type of a particular function call expression. For example, the return type of the function object square:

struct square
{
  template<class T> T operator(T t) const { return t * t; }
};

depends on its argument, and cannot be expressed via a simple result_type typedef.

By providing an appropriate result_of specialization:

template<class T> struct result_of<square(T)>
{
  typedef T type;
};

users can guide the return type deduction process, and help implementations accept code such as bind(square(), _1).

In this proposal, result_of is only specified from the narrow point of view of the bind implementation. The behavior of result_of when no user specializations are present is described in a separate proposal [Gregor03b].

Users should be able to use result_of with the types of the function objects returned by bind.

K. Implementation-Defined Behavior When Return Type Not Easily Deducible

This proposal does not specify the behavior of bind calls when a return type is not explicitly specified, and the first argument is not a pointer to function with C++ linkage or a function object with result_type defined.

The intent of the proposal is for such calls to work whenever the appropriate function call expression is valid. Implementations should support, if possible, pointers to arbitrary functions, including pointers to functions with C linkage (forming a large part of the standard library) and pointers to (member) functions with non-standard, but widely used, calling conventions (__stdcall or __fastcall on Windows, pascal on MacOS). If the argument is a function object, implementations should use result_of to compute the return type, taking advantage of user specializations. Non-standard built-in types that act as function objects, such as closures, should be supported. Implementations that support a typeof extension [Stroustrup02] should "just work" for any function object.

The proposal does not mandate this behavior, though, as most of it depends on non-standard extensions. Even deducing the return type of a function with C linkage is impossible in the current language. Although many compilers treat pointers to functions with C and C++ linkage as interchangeable, this behavior is non-standard.

L. Limits of Existing Implementations

Boost.Bind defines nine placeholders, from _1 to _9, and supports up to nine arguments (N = 9).

Boost.Lambda defines three placeholders, _1, _2, and _3, and also supports up to nine arguments (N = 9). A future release will increase the number of placeholders substantially.

IV. Proposed Text

A. Additions to header <functional> synopsis (20.3)

    template<class T> struct is_bind_expression;
    template<class T> struct is_placeholder;
    template<class E> struct result_of;

    template<class F> unspecified bind(F f);
    template<class R, class F> unspecified bind(F f);

    template<class F, class A1> unspecified bind(F f, A1 a1);
    template<class R, class T, class A1> unspecified bind(R T::* pm, A1 a1);
    template<class R, class F, class A1> unspecified bind(F f, A1 a1);

    // for all positive integers n in [2, N)

    template<class F, class A1, ..., class An> unspecified bind(F f, A1 a1, ..., An an);
    template<class R, class T, class A1, ..., class An> unspecified bind(R T::* pmf, A1 a1, ..., An an);
    template<class R, class F, class A1, ..., class An> unspecified bind(F f, A1 a1, ..., An an);
    
    namespace ph {
      extern unspecified _1;
      extern unspecified _2;
      extern unspecified _3;
      // implementation defined number of additional placeholders 1)
    }

1) This implies that the implementation must support at minimum three placeholders.

B. Class template is_bind_expression

  namespace std {
    template<class T> struct is_bind_expression {
      static const bool value = unspecified;
    };
  }

is_bind_expression can be used to detect function objects generated by bind. bind uses is_bind_expression to detect subexpressions. The template can be specialized by users to indicate that a type should be treated as a subexpression in a bind call.

      static const bool value;

true if T is a type returned from bind, false otherwise.

C. Class template is_placeholder

  namespace std {
    template<class T> struct is_placeholder {
      static const int value = unspecified;
    };
  }

is_placeholder can be used to detect the standard placeholders _1, _2, and so on. bind uses is_placeholder to detect placeholders. The template can be specialized by users to indicate a placeholder type.

      static const bool value;

N if T is the type of std::ph::_N, 0 otherwise.

D. Class template result_of

  namespace std {
    template<class E> struct result_of {
      typedef unspecified type;
    };
  }

The expression result_of<F(A1, ..., An)>::type, where n is a nonnegative integer and F is a function object type with arity n, is intended to yield the type of the expression f(a1, ..., an), where f and ai are lvalues of type F and Ai, respectively.

The default behavior of result_of is implementation defined. Implementations are strongly encouraged to supply a functional result_of that recognizes functions, function pointers, and function objects that have a nested typedef result_type as F, and define result_of<F(...)>::type accordingly.

result_of can be specialized by users to provide a hint to the implementation.

The implementation of bind is allowed but not required 1) to use result_of.


1) Conforming implementations are allowed to bypass result_of in order to be able to take advantage of a typeof extension, if present.

E. bind

The function λ(x) is defined as x.get() when x is of type reference_wrapper<F> for some F, x otherwise.

The function µ(x, v1, ..., vm), where m is a nonnegative integer, x is of type X, and k is is_placeholder<X>::value, is defined as:

A function object f of type F is called simple, if f is a pointer to a function with C++ linkage, F::result_type is defined, or F is a reference_wrapper<G> and G::result_type is defined.

The maximum number of supported arguments (N in the synopsis) is implementation defined. Implementations are allowed to define additional, more specialized, bind overloads, or to fold the pointer to member overload into the general function template, as long as the behavior of the bind calls is unchanged.

    template<class F> unspecified bind(F f);

Requires: F must be CopyConstructible. λ(f)() must be a valid expression. If f is not a simple function object, the behavior is implementation defined.

Returns: A function object g of an unspecified CopyConstructible type G such that the expression g(v1, ..., vm), where m is a nonnegative integer, is equivalent to λ(f)(). If the function application is made via a cv-qualified reference to, or copy of, g, the same cv-qualifiers are applied to f before the evaluation. When f is a pointer to a function with C++ linkage, G::result_type is defined as the return type of the f. When F::result_type is defined, G::result_type is defined as the same type.

Throws: nothing unless the copy constructor of f throws an exception.

Notes: Implementations are allowed to impose an upper limit on m (typically equal to the number of supported placeholders). It is implementation defined whether G is Assignable or DefaultConstructible.

    template<class R, class F> unspecified bind(F f);

Requires: F must be CopyConstructible. λ(f)() must be a valid expression convertible to R.

Returns: A function object g of an unspecified CopyConstructible type G such that the expression g(v1, ..., vm), where m is a nonnegative integer, is equivalent to λ(f)(), implicitly converted to R. If the function application is made via a cv-qualified reference to, or copy of, g, the same cv-qualifiers are applied to f before the evaluation. G::result_type is defined as R.

Throws: nothing unless the copy constructor of f throws an exception.

Notes: Implementations are allowed to impose an upper limit on m. It is implementation defined whether G is Assignable or DefaultConstructible.

    template<class F, class A1> unspecified bind(F f, A1 a1);

Requires: F and A1 must be CopyConstructible. λ(f)(w1) must be a valid expression for some value w1. If f is not a simple function object, the behavior is implementation defined.

Returns: A function object g of an unspecified CopyConstructible type G such that the expression g(v1, ..., vm), where m is a nonnegative integer, is equivalent to λ(f)(µ(a1, v1, ..., vm)). If the function application is made via a cv-qualified reference to, or copy of, g, the same cv-qualifiers are applied to f and a1 before the evaluation. When f is a pointer to a function with C++ linkage, G::result_type is defined as the return type of the f. When F::result_type is defined, G::result_type is defined as the same type.

Throws: nothing unless the copy constructors of f or a1 throw an exception.

Notes: Implementations are allowed to impose an upper limit on m. It is implementation defined whether G is Assignable or DefaultConstructible.

    template<class R, class T, class A1> unspecified bind(R T::* pm, A1 a1);

Requires: pm must be a pointer to data member or pointer to a member function taking no arguments.

Returns: bind(mem_fn(pm), a1).

    template<class R, class F, class A1> unspecified bind(F f, A1 a1);

Requires: F and A1 must be CopyConstructible. λ(f)(w1), for some value w1, must be a valid expression convertible to R.

Returns: A function object g of an unspecified CopyConstructible type G such that the expression g(v1, ..., vm), where m is a nonnegative integer, is equivalent to λ(f)(µ(a1, v1, ..., vm)), implicitly converted to R. If the function application is made via a cv-qualified reference to, or copy of, g, the same cv-qualifiers are applied to f and a1 before the evaluation. G::result_type is defined as R.

Throws: nothing unless the copy constructors of f or a1 throw an exception.

Notes: Implementations are allowed to impose an upper limit on m. It is implementation defined whether G is Assignable or DefaultConstructible.

    template<class F, class A1, ..., class An> unspecified bind(F f, A1 a1, ..., An an);

Requires: F and Ai must be CopyConstructible. λ(f)(w1, ..., wn) must be a valid expression for some values wi. If f is not a simple function object, the behavior is implementation defined.

Returns: A function object g of an unspecified CopyConstructible type G such that the expression g(v1, ..., vm), where m is a nonnegative integer, is equivalent to λ(f)(µ(a1, v1, ..., vm), ..., µ(an, v1, ..., vm)). If the function application is made via a cv-qualified reference to, or copy of, g, the same cv-qualifiers are applied to f and ai before the evaluation. When f is a pointer to a function with C++ linkage, G::result_type is defined as the return type of the f. When F::result_type is defined, G::result_type is defined as the same type.

Throws: nothing unless the copy constructors of f or ai throw an exception.

Notes: Implementations are allowed to impose an upper limit on m. It is implementation defined whether G is Assignable or DefaultConstructible.

    template<class R, class T, class A1, ..., class An> unspecified bind(R T::* pmf, A1 a1, ..., An an);

Requires: pmf must be a pointer to a member function taking n-1 arguments.

Returns: bind(mem_fn(pmf), a1, ..., an).

    template<class R, class F, class A1, ..., class An> unspecified bind(F f, A1 a1, ..., An an);

Requires: F and Ai must be CopyConstructible. λ(f)(w1, ..., wn), for some values wi, must be a valid expression convertible to R.

Returns: A function object g of an unspecified CopyConstructible type G such that the expression g(v1, ..., vm), where m is a nonnegative integer, is equivalent to λ(f)(µ(a1, v1, ..., vm), ..., µ(an, v1, ..., vm)), implicitly converted to R. If the function application is made via a cv-qualified reference to, or copy of, g, the same cv-qualifiers are applied to f and ai before the evaluation. G::result_type is defined as R.

Throws: nothing unless the copy constructors of f or ai throw an exception.

Notes: Implementations are allowed to impose an upper limit on m. It is implementation defined whether G is Assignable or DefaultConstructible.

F. Placeholders

  namespace std {
    namespace ph {
      extern unspecified _1;
      extern unspecified _2;
      extern unspecified _3;
      // implementation defined number of additional placeholders
    }
  }

All placeholder types are DefaultConstructible and CopyConstructible, and their default constructors and copy constructors do not throw. It is implementation defined whether placeholder types are Assignable. Assignable placeholders' copy assignment operators do not throw exceptions.

V. References

[Boost01] Boost.Bind library, September 2001. Available online at http://www.boost.org/libs/bind/

[Boost02] Boost.Lambda library, April 2002. Available online at http://www.boost.org/libs/lambda/

[Dimov02] Peter Dimov, Howard E. Hinnant, Dave Abrahams, The Forwarding Problem: Arguments, C++ committee document N1385=02-0043, September 2002. Available online at http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1385.htm

[Dimov03] Peter Dimov, A Proposal to Add an Enhanced Member Pointer Adaptor to the Library Technical Report, C++ committee document N1432=03-0014, February 2003. Available online at http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1432.htm

[Gregor02] Douglas Gregor, A Proposal to add a Polymorphic Function Object Wrapper to the Standard Library, C++ committee document N1402=02-0060, October 2002. Available online at http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1402.htm

[Gregor03a] Douglas Gregor, A Proposal to Add a Reference Wrapper to the Standard Library, C++ committee document N1436=03-0018, February 2003. Available online at http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1436.htm

[Gregor03b] Douglas Gregor, A Uniform Method for Computing Function Object Return Types, C++ committee document N1437=03-0019, February 2003. Available online at http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1437.htm

[Guzman02] Joel de Guzman, Phoenix library documentation, October 2002. Available online at http://spirit.sourceforge.net/index.php?doc=docs/phoenix_v1_0/index.html

[Järvi99] Jaakko Järvi, The Binder Library, Spetember 1999. Available online at http://staff.cs.utu.fi/BL/

[Järvi00] Jaakko Järvi, C++ Function Object Binders Made Easy, Proceedings of the Generative and Component-Based Software Engineering 99, Lecture Notes in Computer Science vol. 1977, August 2000. Available online at http://osl.iu.edu/~jajarvi/publications/papers/function_object_binders_made_easy.ps

[Järvi03] Jaakko Järvi, Gary Powell, Andrew Lumsdaine, The Lambda Library: Unnamed Functions in C++, Software: Practice and Experience, vol. 33(3), pp. 259-291, March 2003.

[Josuttis00] Nicolai Josuttis, Compose Function Object Adapters, July 2000. Available online at http://www.boost.org/libs/compose/compose.html

[Kempf02] William E. Kempf, The Boost.Threads Library, C/C++ Users Journal, May 2002. Available online at http://www.cuj.com/articles/2002/0205/0205a/0205a.htm?topic=articles

[Rodgers00] Mark Rodgers, Improved Function Object Adaptors, July 2000. Available online at http://www.boost.org/libs/functional/

[SGI97a] SGI STL documentation, unary_compose, 1997. Available online at http://www.sgi.com/tech/stl/unary_compose.html

[SGI97b] SGI STL documentation, binary_compose, 1997. Available online at http://www.sgi.com/tech/stl/binary_compose.html

[Siek00] Jeremy Siek, Transform Iterator Adaptor, 2000. Available online at http://www.boost.org/libs/utility/transform_iterator.htm

[Simonis00] Volker Simonis, Adapters and Binders - Overcoming Problems in the Design and Implementation of the C++-STL, February 2000. Available online at http://www.progdoc.de/papers/adapter_binder/adapter_binder/adapter_binder.html

[Stroustrup02] Bjarne Stroustrup, auto/typeof, C++ reflector message c++std-ext-5364, October 2002.

[Williams01] Anthony Williams, Flexible Functors and Binders, July 2001. Available online at http://web.onetel.net.uk/~anthony_w/cplusplus/functional.pdf