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


Document number: N1375=02-0033
Date: 25 August 2002
Project: Programming Language C++
Reply-to: Douglas Gregor <gregod@cs.rpi.edu>

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";
[Author's note: the construction of the function object on the right-hand side of the assignment above is not covered by this proposal]

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
- end example]

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:

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);
- end example]

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

20.2.3.1 Template class reference_wrapper

  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));
  3. operator T& () const;
  4. T& get() const;

20.2.3.2 ref and cref

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

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

Proposed new section: 20.3.9 Template class function

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

20.3.9.1 function construct/copy/destroy

  1. explicit function(const Allocator& = Allocator());
  2. function(const function& f);
  3. template<typename F> function(F f, const Allocator& = Allocator());
  4. template<typename F> function(reference_wrapper<F> f, const Allocator& = Allocator());
  5. function& operator=(const function& f);
  6. template<typename F> function& operator=(F f);
  7. template<typename F> function& operator=(reference_wrapper<F> f);
  8. ~function();

20.3.9.2 function modifiers

  1. void swap(function& other);
  2. void clear();

20.3.9.3 function capacity

  1. bool empty() const
  2. operator safe_bool() const

20.3.9.4 function invocation

  1. R operator()(T1 t1, T2 t2, ..., TN tN) const;

20.3.9.5 specialized algorithms

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

20.3.9.6 poisoned operators

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

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

William Kempf, Jesse Jones and Karl Nelson were all extremely helpful in isolating an interface and scope for the Boost.Function [8] library upon which this proposal is based. John Maddock managed the formal review, and many reviewers gave excellent comments on interface, implementation, and documentation. Peter Dimov proposed function pointer syntax for representing the argument and return types, which was later revised to use function declarator syntax.

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.