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 = ref(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>
double minimize(F f, const vector<double>& initial);

// with function object wrappers
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 Boost.Bind and Boost.Lambda in the Boost libraries. The same should occur with the Bind and/or Lambda proposals.]

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

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

2. explicit reference_wrapper(T& t));
   • Postconditions: &this->get() == &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);
   • Returns: reference_wrapper<T const>(t)
   • Throws: will not throw.

Addition to 20.3: Function objects

Additions to Header <functional> synopsis:

    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>&);

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>(mem_fun(f(t1, t2, ..., tN)));
     }
   

   Dependency on other proposals: mem_fun can be substituted for a more powerful pointer to member function wrapper, such as the Boost mem_fn library.
3. A function object type F is Stateless if one of the following holds:
   • F is a function pointer type.
   • F is wrapped in reference_wrapper as reference_wrapper<cv F>.
   • Feature depending on other proposals: F is an empty class with a trivial copy constructor and destructor. These type traits will be available in the standard library if the type traits proposal is accepted.
   Stateless function objects do not require dynamic storage allocation when stored in a polymorphic function object wrapper, and therefore copy and construction of function object wrappers storing stateless function objects do not throw exceptions.
4. MAX_ARGS is an implementation-defined limit on the maximum number of arguments a function type may have when used with the function class template. The MAX_ARGS constant need not be defined by the implementation, but must have a value of no less than 10 on any conforming implementation.
5. The function class template is always a function object and, depending on the number of function argument parameters supplied to the function class template, may meet the requirements of an AdaptableUnaryFunction or AdaptableBinaryFunction. The first template argument supplied to the function class template must be a function type.

   namespace std {
     template<typename Function, // Function type R (T1, T2, ..., TN), 0 <= N <= MAX_ARGS
              typename Allocator = std::allocator<void> >
     class function 
       : public unary_function<R, T1> // iff N == 1
       : public binary_function<R, T1, T2> // iff N == 2
     {
       typedef implementation-defined safe_bool; // exposition only. See 20.3.9.3
   
     public:
       typedef R         result_type;
       typedef Allocator allocator_type;
   
       // 20.3.9.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.9.2 function modifiers
       void swap(function&);
       void clear();
     
       // 20.3.9.3 function capacity
       bool empty() const;
       operator safe_bool() const;
   
       // 20.3.9.4 function invocation
       R operator()(T1, T2, ..., TN) const;
     };
   
     // 20.3.9.5 specialized algorithms
     template<typename Function1, typename Allocator1, typename Function2, typename Allocator2>
     void swap(function<Function1, Allocator1>&, function<Function2, Allocator2>&);
   
     // 20.3.9.6 poisoned 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 stateless. Otherwise, may throw when copying the target of f.
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 stateless function object. Otherwise, may throw when copying f into the polymorphic wrapper.
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.
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.
   • 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 safe_bool() 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
   • Throws: will not throw.
   • Notes: The safe_bool type 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 for safe_bool to be a member function pointer whose class type is private to the function instantiation.

1. R operator()(T1 t1, T2 t2, ..., TN tN) const;
   • Preconditions: !this->empty()
   • 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.

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

V. Relationship with Other Proposals

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.

VI. Acknowledgements

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