A Proposal to add a Polymorphic Function Object Wrapper to the Standard Library

I. Motivation

Function pointers in C and C++ are used in both user and library code to customize the behavior of components by substituting a user-supplied function for part of a computation. This proposal introduces a class template that generalizes the notion of a function pointer to subsume function pointers, member function pointers, and arbitrary function objects while maintaining similar syntax and semantics to function pointers.

Several function object wrappers (often referred to as "callbacks") have appeared with similar interfaces [1, 2, 10, 11], suggesting that this class template is appropriate for standardization. This proposal is based on the design and implementation of the Boost.Function library [8].

Ia. Callbacks

Experience with Boost.Function has shown that polymorphic function object wrappers are often used for callbacks. Callbacks can be constructed in many ways, but in C++ they are often constructed in the "OO-style" using virtual functions and abstract callback classes. For instance, an abstract callback class that receives updates when a computer mouse is moved may be constructed as follows:

class mouse_move_listener {
public:
  virtual void on_mouse_move(int x, int y) = 0;
};

Callbacks in this "OO-style" are stored by holding a pointer to an object derived from mouse_move_listener, and invoked by calling the on_mouse_move virtual function:

mouse_move_listener* move_listener;

void fire_mouse_move(int x, int y)
{
  if (move_listener)
    move_listener->on_mouse_move(x, y);
}

Suppose we wish to create a listener for this event that prints the mouse position to an output stream. We must create a new subclass of mouse_move_listener and implement the on_mouse_move virtual function:

class mouse_loc_printer : public mouse_move_listener
{
public:
  virtual void on_mouse_move(int x, int y)
  {
    out << '(' << x << ", " << y << "\n";
  }

private:
  std::ostream& out;
};

The proposed class template function greatly reduces the amount of boilerplate code required to create a callback but also allows much greater leeway in the creation of a receiver. Using the proposed function class template, the on_mouse_move event would be created and stored as such:

function<void (int x, int y)> on_mouse_move;

void fire_mouse_move(int x, int y)
{
  if (on_mouse_move)
    on_mouse_move(x, y);
}

The on_mouse_move object will store any function object that can be called with the given function signature, that is, two arguments of type int will be passed to the function object and no return value is expected. Note that, unlike with the OO-style case using virtual functions, the function object can rely on implicit conversions to its actual argument types, so the following function object can be called by on_mouse_move:

struct print_position
{
  void operator()(long x, long y) const
  {
    std::cout << '(' << x << ", " << y << ")\n";
  }
};

Most importantly, the use of function objects as callback targets in lieu of the more restrictive virtual function approach allows users to compose function objects using other libraries (see Section V) that can be directly used as callback types. The callback target that prints the mouse position can be concisely created and assigned in a single C++ statement (using Boost.Lambda syntax to create the body of the callback target via a lambda abstraction; _1 and _2 are placeholders for the first and second callback arguments, respectively):

on_mouse_move = var(cout) << '(' << _1 << ", " << _2 << ")\n";

Ib. Higher-order Functions

Higher-order functions are not often used in C++, in part because they are unwieldy. To return a function, one must return a function pointer (which therefore cannot have state) or a full callback such as the OO-style callback presented above (which requires a large amount of boilerplate code). The proposed class template simplifies the creation and use of higher-order functions, e.g.,

function<int (int x, int y)> arithmetic_operation(char k)
{
  switch (k) {
    case '+': return plus<int>();
    case '-': return minus<int>();
    case '*': return multiplies<int>();
    case '/': return divides<int>();
    case '%': return modulus<int>();
    default: assert(0);
  }
}

Polymorphic function object wrappers may also be used in lieu of arbitrary function objects whose type is a template parameter, allowing a trivial switch from function templates to functions (with a corresponding size/speed tradeoff). For instance, the following function signatures represent the template and function object wrapper versions of a function that minimizes another function.

// with function objects
template<typename F>
vector<double> minimize(F f, const vector<double>& initial);

// with function object wrappers
vector<double> minimize(const function<double (const vector<double>& values)>& f, const vector<double>& initial);

The former signature declares a function template that would be instantiated for every function to be minimized (potentially generating a large amount of well-optimized code); the latter would require only one (non-template) version of the minimize function with several small instantiations for use with the function class template (less code, but less efficient calls to the function object). From the user's point of view, the two options can be made indistinguishable, enabling code to be compiled for either small size (with short compile times) or faster execution speed (with longer compile times).

II. Impact on the Standard

This proposal defines a pure library extension, requiring no changes to the core C++ language. A new class template function is proposed to be added into the standard header <functional> along with supporting function overloads. A new class template reference_wrapper is proposed to be added to the standard header <utility> with two supporting functions.

III. Design

The proposed function object wrapper is designed to mimic function pointers in both syntax and semantics, but generalize the notion to allow the target of a function object wrapper to be any function object, function pointer, or member function pointer that can be called given the return and argument types supplied to the function object wrapper.

[Example -

    int add(int x, int y) { return x+y; }
    bool adjacent(int x, int y) { return x == y-1 || x == y+1; }

    struct compare_and_record {
      std::vector<std::pair<int, int> > values;

      bool operator()(int x, int y)
      {
        values.push_back(std::make_pair(x, y));
        return x == y;
      }
    };
    
    function<int (int, int)> f;
    
    f = &add; 
    cout << f(2, 3) << endl; // 5
    
    f = minus<int>();
    cout << f(2, 3) << endl; // -1
    
    assert(f); // okay, f refers to a minus<int> object
    
    function<bool (int, int)> g;
    assert(!g); // okay, g doesn't refer to any object
    
    g = &adjacent;
    assert(g(2, 3)); // okay, adjacent(2, 3) returns true
    
    g = equal_to<long>(); // argument conversions ok
    assert(g(3, 3)); //okay, equal_to<long>()(3, 3) returns true

    compare_and_record car;
    g = ref(car);

    assert(g(3, 3)); // okay, and adds (3, 3) to car.values

    g = f; // okay, int return value of f is convertible to bool

The proposed function object wrapper supports only a subset of the operations supported by function pointers with slightly different syntax and semantics. The major differences are detailed below, but can be summarized as follows:

• Relaxation of target requirements to allow conversions in arguments and result type.
• Lack of comparison operators.
• Lack of extraneous null-checking syntax.

IIIa. Relaxation of target requirements

A function pointer of a given type R (*)(T1, T2, ..., TN) may only target functions with an identical type signature. The corresponding function wrapper function<R (T1, T2, ..., TN)> may target any function object f such that for values t1, t2, ..., tN, of types T1, T2, ..., TN, respectively, the expression static_cast<R>(f(t1, t2, ..., tN)) is well-formed. When this is true, we say that the function object f (and its type F) is Callable with return type R and argument types T1, T2, ..., TN.

Rationale: this loose definition of Callable allows arbitrary function objects to be used with function object wrappers in a manner similar to their use when the function object's type is a template parameter. A stricter definition, e.g., one that required the argument and return types of the target function object match exactly with the declared argument and return types of the function object wrapper, would make the use of function object wrappers less seamless.

[Example - the given definition of Callable allows the two variations on the sort algorithm to operate almost identically from the user's point of view; the former sort signature favors inlining for efficiency (at the code of increased code size), whereas the latter sort signature favors smaller code size by producing only a single version of sort for each iterator type, with a potential cost in execution efficiency.

    // Very efficient, but potentially creates a large amount of code
    template<typename RAIterator, typename Compare>
    void sort(RAIterator first, RAIterator last, Compare comp);
    
    // Less efficient (because of indirection), but less generated code
    template<typename RAIterator>
    void sort(RAIterator first, RAIterator last, 
	      const function<bool (typename iterator_traits<RAIterator>::value_type const&,
			           typename iterator_traits<RAIterator>::value_type const&)>& comp);

IIIb. Lack of comparison operators

The comparison operators ==, !=, <, >, <=, and >= are not supported by the function object wrapper.

Rationale: (in)equality and ordering relations cannot be sensibly defined for function objects.

IIIc. Lack of extraneous null-checking syntax

This follows from the lack of comparison operators. For a function object wrapper f, there is no syntax f != 0, f == 0, etc. The allowed syntactic constructs for checking for an empty (null) function object wrapper are f or !f in a boolean context, (bool)f or f.empty().

IV. Proposed Text

Addition to 20.2: Utility components

Additions to Header <utility> synopsis:

    template<typename T> class reference_wrapper;

    template<typename T> reference_wrapper<T> ref(T& t);
    template<typename T> reference_wrapper<T const> cref(const T& t);

Proposed new section: 20.2.3 Reference wrappers

1. The library provides a reference wrapper and reference wrapper construction functions that allow the user to express intent in storing a reference instead of a copy.
2. [Author's note: the reference_wrapper class template and the ref and cref function templates are shared with the Tuples library proposal. The text is repeated in both proposals.]

1. The reference_wrapper class template stores a reference to an object in a CopyConstructible wrapper.

   namespace std {
     template<typename T>
     class reference_wrapper {
     public:
       typedef T type;
      
       explicit reference_wrapper(T &);
   
       operator T& () const;
       T& get() const;
   
     private:
       T& data; // exposition only
     };
   }
   

2. explicit reference_wrapper(T& t));
   • Postconditions: this->get() is equivalent to t.
   • Throws: will not throw.
3. operator T& () const;
   • Returns: this->get()
   • Throws: will not throw.
4. T& get() const;
   • Returns: the stored reference.
   • Throws: will not throw.

20.2.3.2 ref and cref

1. template<typename T> reference_wrapper<T> ref(T& t);
   • Returns: reference_wrapper<T>(t)
   • Throws: will not throw.
2. template<typename T> reference_wrapper<T const> cref(const T& t);
   • Requires: T cannot be a function type.

     [This requirement may be unnecessary depending on the resolution of core language issue 295]

   • Returns: reference_wrapper<T const>(t)
   • Throws: will not throw.

Addition to 20.3: Function objects

Additions to Header <functional> synopsis:

    class bad_function_call;

    template<typename Function, typename Allocator = std::allocator<void> >
    class function;

    template<typename Function, typename Allocator>
    void swap(function<Function, Allocator>&, function<Function, Allocator>&);

    template<typename Function1, typename Allocator1, typename Function2, typename Allocator2>
    void operator==(const function<Function1, Allocator1>&, const function<Function2, Allocator2>&);
    template<typename Function1, typename Allocator1, typename Function2, typename Allocator2>
    void operator!=(const function<Function1, Allocator1>&, const function<Function2, Allocator2>&);

Proposed new section: 20.3.9 Class bad_function_call

1. The bad_function_call exception class is thrown primarily when a polymorphic adaptor is invoked but is empty (see 20.3.10).

   namespace std {
     class bad_function_call : public std::runtime_error
     {
     public:
       // 20.3.9.1 constructor
       bad_function_call();
     };
   }
   

1. bad_function_call();
   • Effects: constructs a bad_function_call object.

1. The library provides polymorphic wrappers that generalize the notion of a function pointer. Wrappers can store, copy, and call arbitrary function objects given a function signature (denoted by a set of argument types and a return type), allowing functions to be first-class objects.
2. A function object f of type F is Callable given a set of argument types T1, T2, ..., TN and a return type R, if the appropriate following function definition is well-formed:

     // If F is not a pointer to member function
     R callable(F& f, T1 t1, T2 t2, ..., TN tN)
     {
       return static_cast<R>(f(t1, t2, ..., tN));
     }
   
     // If F is a pointer to member function
     R callable(F f, T1 t1, T2 t2, ..., TN tN)
     {
       return static_cast<R>(((*t1).*f)(t2, t3, ..., tN));
     }
   

3. The function class template is a function object type whose call signature is defined by its first template argument (a function type).

   namespace std {
     template<typename Function, // Function type R (T1, T2, ..., TN), 0 <= N <= implementation-defined maximum (see Annex B)
              typename Allocator = std::allocator<void> >
     class function 
       : public unary_function<R, T1> // iff N == 1
       : public binary_function<R, T1, T2> // iff N == 2
     {
     public:
       typedef R         result_type;
       typedef Allocator allocator_type;
   
       // 20.3.10.1 construct/copy/destroy
       explicit function(const Allocator& = Allocator());
       function(const function&);
       template<typename F> function(F, const Allocator& = Allocator());
       template<typename F> function(reference_wrapper<F>, const Allocator& = Allocator());
       function& operator=(const function&);
       template<typename F> function& operator=(F);
       template<typename F> function& operator=(reference_wrapper<F>);
       ~function();
   
       // 20.3.10.2 function modifiers
       void swap(function&);
       void clear();
     
       // 20.3.10.3 function capacity
       bool empty() const;
       operator implementation-defined() const;
   
       // 20.3.10.4 function invocation
       R operator()(T1, T2, ..., TN) const;
     };
   
     // 20.3.10.5 specialized algorithms
     template<typename Function1, typename Allocator1, typename Function2, typename Allocator2>
     void swap(function<Function1, Allocator1>&, function<Function2, Allocator2>&);
   
     // 20.3.10.6 undefined operators
     template<typename Function1, typename Allocator1, typename Function2, typename Allocator2>
     void operator==(const function<Function1, Allocator1>&, const function<Function2, Allocator2>&);
     template<typename Function1, typename Allocator1, typename Function2, typename Allocator2>
     void operator!=(const function<Function1, Allocator1>&, const function<Function2, Allocator2>&);
   }
   

1. explicit function(const Allocator& = Allocator());
   • Postconditions: this->empty().
   • Throws: will not throw.
2. function(const function& f);
   • Postconditions: this->empty()if f.empty(); otherwise, *this targets a copy of f.
   • Throws: will not throw if the target of f is a function pointer or a function object passed via reference_wrapper. Otherwise, may throw bad_alloc or any exception thrown by the copy constructor of the stored function object.
3. template<typename F> function(F f, const Allocator& = Allocator());
   • Requires: f is a callable function object for argument types T1, T2, ..., TN and return type R.
   • Postconditions: this->empty() if any of the following hold:
     • f is a NULL function pointer.
     • f is a NULL member function pointer.
     • f is an instance of the function class template and f.empty()
     Otherwise, *this targets a copy of f if f is not a pointer to member function, and targets a copy of mem_fun(f) if f is a pointer to member function.
   • Throws: will not throw when f is a function pointer. Otherwise, may throw bad_alloc or any exception thrown by F's copy constructor.
4. template<typename F> function(reference_wrapper<F> f, const Allocator& = Allocator());
   • Requires: f.get() is a callable function object for argument types T1, T2, ..., TN and return type R.
   • Postconditions: !this->empty() and *this targets f.get().
   • Throws: will not throw.
   • Rationale: a potential alternative would be to replace the reference_wrapper argument with an argument taking a function object pointer. This route was not taken because reference_wrapper is a general solution stating the user's intention to pass a reference to an object instead of a copy.
5. function& operator=(const function& f);
   • Effects: function(f).swap(*this);
   • Returns: *this
6. template<typename F> function& operator=(F f);
   • Effects: function(f).swap(*this);
   • Returns: *this
7. template<typename F> function& operator=(reference_wrapper<F> f);
   • Effects: function(f).swap(*this);
   • Returns: *this
   • Throws: will not throw.
8. ~function();
   • Effects: if !this->empty(), destroys the target of this.

1. void swap(function& other);
   • Effects: interchanges the targets of *this and other and the allocators of *this and other.
   • Throws: will not throw.
2. void clear();
   • Effects: If !this->empty(), deallocates current target.
   • Postconditions: this->empty().

1. bool empty() const
   • Returns: true if the function object has a target, false otherwise.
   • Throws: will not throw.
2. operator implementation-defined() const
   • Returns: if !this->empty(), returns a value that will evaluate true in a boolean context; otherwise, returns a value that will evaluate false in a boolean context. The value type returned shall not be convertible to int.
   • Throws: will not throw.
   • Notes: This conversion can be used in contexts where a bool is expected (e.g., an if condition); however, implicit conversions (e.g., to int) that can occur with bool are not allowed, eliminating some sources of user error. The suggested implementation technique is to use a member function pointer whose class type is private to the function instantiation.

1. R operator()(T1 t1, T2 t2, ..., TN tN) const;
   • Effects: f(t1, t2, ..., tN), where f is the target of *this.
   • Returns: nothing, if R is void; otherwise, the return value of the call to f.
   • Throws: bad_function_call if this->empty(); otherwise, any exception thrown by the wrapped function object.

1. template<typename Function, typename Allocator>
void swap(function<Function, Allocator>& f1, function<Function, Allocator>& f2);
   • Effects: f1.swap(f2);

1. template<typename Function1, typename Allocator1, typename Function2, typename Allocator2>
void operator==(const function<Function1, Allocator1>&, const function<Function2, Allocator2>&);
   • Notes: this function must be left undefined.
   • Rationale: the boolean-like conversion opens a loophole whereby two function instances can be compared via ==. This undefined void operator == closes the loophole and ensures a compile-time or link-time error.
2. template<typename Function1, typename Allocator1, typename Function2, typename Allocator2>
void operator!=(const function<Function1, Allocator1>&, const function<Function2, Allocator2>&);
   • Notes: this function must be left undefined.
   • Rationale: the boolean-like conversion opens a loophole whereby two function instances can be compared via !=. This undefined void operator != closes the loophole and ensures a compile-time or link-time error.

Add to Annex B

Add to list of implementation quantities:

  -- maximum number of function call arguments supported by class template function [10].

V. Relationship with Other Proposals or Future Developments

This section describes the interaction of this proposal with other C++ extension proposals that are already available or are likely to be available in the near future, based primarily on experience with the Boost libraries. Every attempt has been made to accurately represent the proposals, but these comments have not been verified by the authors of the proposals discussed.

Binder libraries, such as Boost.Lambda [3], Boost.Bind [4], Phoenix (part of the Spirit parser framework) [5], FC++ [6], and FACT! [7] enable composition of function objects to create new function objects. These libraries are orthogonal but complementary to this proposal, i.e., this proposal can be accepted or rejected regardless of the status of a binder library proposal. However, experience with the Boost libraries has shown that most uses of Boost.Function benefit greatly from a binder library.

The proposed type traits library [9] enables further optimization and tighter exception guarantees in implementations of the proposed function class template.

The addition of variable-length template argument lists would have little effect on this proposal. Variable-length template argument lists would allow a syntax such as function<void, int, float> instead of function< void (int, float)>. However, such a formulation:

• Doesn't have the intuitive grouping of argument types.
• Doesn't mimic function/function pointer syntax as closely, and loses the ability to directly specify function parameter names.
• Confuses the last template parameter with the Allocator template parameter.
• Was originally the syntax of the Boost.Function library (by emulating variable-length template argument lists), and was later changed to the proposed syntax.

VI. Revision History

This proposal is a revised version of document number N1375=02-0033. The changes made from that document are:

• Discussion of the merits of current syntax vs. an alternative syntax based on variable-length template argument lists.
• Rationale for use of reference_wrapper instead of function object pointers in the proposed 20.3.10.1.
• Callable definition reworded so that it does not rely on mem_fun.
• Adaptable unary/binary function reference removed.
• Stronger exception guarantees in 20.3.10.1.
• swap() swaps the allocator.
• boolean-like conversion is now an implementation-defined conversion, and the name safe_bool has been removed.
• The term "poisoned" has been replaced with "undefined".
• Added the bad_function_call exception class.
• Removed MAX_ARGS, replacing it with an implementation quantity.
• Removed "stateless" function object terminology and implied "stateless" type trait.

VII. Acknowledgements

VIII. References

[1] Huber, Andreas. Elegant Function Call Wrappers. C/C++ Users Journal. May, 2001. pp. 8-16.

[2] Alexandrescu, Andrei. Modern C++ Design: Generic Programming and Design Patterns Applied Addison-Wesley, 2001.

[3] The Boost.Lambda Library. http://www.boost.org/libs/lambda/doc/index.html

[4] The Boost.Bind Library. http://www.boost.org/libs/bind/bind.html

[5] Phoenix, a part of the Spirit parser framework. http://spirit.sourceforge.net

[6] FC++. http://www.cc.gatech.edu/~yannis/fc++/

[7] FACT!. http://www.kfa-juelich.de/zam/FACT/start/index.html

[8] The Boost.Function Library. http://www.boost.org/libs/function/index.html

[9] Maddock, John. A Proposal to add Type Traits to the Standard Library. http://ourworld.compuserve.com/homepages/John_Maddock/proposals/n1345.htm

[10] Haendel, Lars.How to implement callbacks in C and C++. http://www.function-pointer.org/, 2002.

[11] Hickey, Rich. Callbacks in C++ Using Template Functors. http://www.tutok.sk/fastgl/callback.html, 1994.