Function object

This article is about the computer programming concept. For functors in the mathematical field of category theory, see Functor.

A function object, also called a functor, functional, or functionoid, is a computer programming construct allowing an object to be invoked or called like it was an ordinary function, usually with the same syntax.

Description

A typical use of a function object is in writing callback functions. A callback in procedural languages, such as C, may be accomplished by using function pointers. However it can be difficult or awkward to pass a state into or out of the callback function. This restriction also inhibits more dynamic behavior of the function. A function object solves those problems since the function is really a façade for a full object, thus it carries its own state.

Most modern object-oriented languages e.g. C++, Java, PHP, Python, Ruby and Lisp support the definition of function objects and may even make significant use of them.

Origins

Smalltalk was one of the first languages to support function objects through the use of block constructs that are an integral part of the language syntax. For example, they can be supplied as arguments to collection objects to provide filtering and sorting. It is a perfect realization of the strategy pattern that promotes the use of pluggable behaviour.

In C and C++

Consider the example of a sorting routine which uses a callback function to define an ordering relation between a pair of items. A C program using function pointers may appear as:

/* Callback function */
int compare_function(int A, int B) {
  return A < B;
}
...
/* Declaration of C sorting function */
void sort_ints(int* begin_items, int num_items, int (*cmpfunc)(int, int) );
...
int main(void) {
    int items[] = {4, 3, 1, 2};
    sort_ints(items, sizeof(items)/sizeof(int), compare_function);
    return 0;
}

In C++ a function object may be used instead of an ordinary function by defining a class which overloads the function call operator by defining an operator() member function. In C++ this is called a class type functor, and may appear as follows:

class compare_class {
  public:
  bool operator()(int A, int B) {
    return (A < B);
  }
};
...
// Declaration of C++ sorting function.
template <class ComparisonFunctor> 
void sort_ints(int* begin_items, int num_items, ComparisonFunctor c);
...
int main() {
    int items[] = {4, 3, 1, 2};
    compare_class functor;
    sort_ints(items, sizeof(items)/sizeof(int), functor);
}

Notice that the syntax for providing the callback to the sort_ints() function is identical, but an object is passed instead of a function pointer. When invoked, the callback function is executed just as any other member function, and therefore has full access to the other members (data or functions) of the object.

It is possible to use function objects in situations other than as callback functions (although the shortened term functor is normally not used). Continuing the example,

  functor_class Y;
  int result = Y( a, b );

In addition to class type functors, other kinds of function objects are also possible in C++. They can take advantage of C++'s member-pointer or template facilities. The expressiveness of templates allows some functional programming techniques to be used, such as defining function objects in terms of other function objects (like function composition). Much of the C++ Standard Template Library (STL) makes heavy use of template-based function objects.

Performance

An advantage of function objects in C++ is performance because unlike a function pointer, a function object can be inlined^{[citation needed]}. For example, consider a simple function which increments its argument implemented as a function object:

struct IncrementFunctor {
  void operator()(int &i) { ++i; }
};

and as a free function:

void increment_function(int &i) { ++i; }

Recall the standard library function std::for_each():

template<typename InputIterator, typename Function>
Function for_each(InputIterator first, InputIterator last, Function f) {
  for ( ; first != last; ++first)
    f(*first);
  return f;
}

Suppose we apply std::for_each() like so:

int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(A[0]);
for_each(A, A + N, IncrementFunctor());
for_each(A, A + N, increment_function);

Both calls to for_each() will work as expected. The first call will be to this version:

IncrementFunctor for_each<int*,IncrementFunctor>(int*, int*, IncrementFunctor)

the second will be to this version:

void(*)(int&) for_each<int*,void(*)(int&)>(int*, int*, void(*)(int&))

Within for_each<int*,IncrementFunctor>(), the compiler will be able to inline the function object because the function is known at compile time whereas within for_each<int*,void(*)(int&)>() the function cannot be known at compile time because the pointer has not been assigned and so cannot be inlined.

Maintaining state

Another advantage of function objects is their ability to maintain a state which affects operator() between calls. Inconveniently copies of a function object must share a state to work correctly. STL algorithms are allowed to instantiate copies. For example, the following code defines a generator counting from 10 upwards and is invoked 11 times.

#include <iostream>
#include <iterator>
#include <algorithm>

class countfrom {
private:
  int &count;
public:
  countfrom(int &n) : count(n) {}
  int operator()() { return count++; }
};

int main() {
  int state(10);
  std::generate_n(std::ostream_iterator<int>(std::cout, "\n"), 11, countfrom(state));
  return 0;
}

In C#

By using delegates

In D

D provides several ways of declaring function objects: Lisp/Python-style using closures or C#-style using delegates, respectively:

bool find(T)(T[] haystack, bool delegate(T) needle_test) {
  foreach ( straw; haystack ) {
    if ( needle_test(straw) )
      return true;
  }
  return false;
}

void main() {
    int[] haystack = [345,15,457,9,56,123,456];
    int   needle = 123;
    bool needleTest(int n) {
      return n == needle;
    }
    assert(
      find(haystack, &needleTest)
    );
}

The difference between a delegate and a closure in D is automatically and conservatively determined by the compiler. D also supports function literals, that allow a lambda-style definition:

void main() {
    int[] haystack = [345,15,457,9,56,123,456];
    int   needle = 123;
    assert(
       find(haystack, (int n) { return n == needle; })
    );
}

In order to allow the compiler to inline the code (see above), function objects can also be specified C++-style using operator overloading:

bool find(T,F)(T[] haystack, F needle_test) {
  foreach ( straw; haystack ) {
    if ( needle_test(straw) )
      return true;
  }
  return false;
}

void main() {
    int[] haystack = [345,15,457,9,56,123,456];
    int   needle = 123;
    class NeedleTest {
      int needle;
      this(int n) { needle = n; }
      bool opCall(int n) {
        return n == needle;
      }
    }
    assert(
      find(haystack, new NeedleTest(needle))
    );
}

In Java

Since Java does not have first-class functions, function objects are usually expressed by an interface with a single method (most commonly the Callable interface), typically with the implementation being an anonymous inner class.

For an example from Java's standard library, java.util.Collections.sort() takes a List and a functor whose role is to compare objects in the List. But because Java does not have first-class functions, the function is part of the Comparator interface. This could be used as follows.

List<String> list = Arrays.asList("10", "1", "20", "11", "21", "12");
		
Collections.sort(list, new Comparator<String>() {
    public int compare(String o1, String o2) {
        return Integer.valueOf(o1).compareTo(Integer.valueOf(o2));
    }
});

In Python

In Python, functions are first-class objects, just like strings, numbers, lists etc. This feature eliminates the need to write a function object in many cases. Any object with a __call__() method can be called using function-call syntax.

An example is this Accumulator class (based on Paul Graham's study on programming language syntax and clarity here):

class Accumulator(object):
    def __init__(self, n):
        self.n = n
    def __call__(self, x):
        self.n += x
        return self.n

An example of this in use (using the interactive interpreter):

>>> a = Accumulator(4)
>>> a(5)
9
>>> a(2)
11
>>> b = Accumulator(42)
>>> b(7)
49

A function object using a closure in Python 3:

def accumulator(n):
    def inc(x):
        nonlocal n
        n += x
        return n
    return inc

In Lisp

In Common Lisp, Scheme and other languages in that family, functions are objects, just like strings, vectors, lists, numbers and so forth. A closure-constructing operator creates a function-object from a piece of the program itself: the piece of code given as an argument to the operator is part of the function, and so is the lexical environment: the bindings of the lexically visible variables are "captured" and stored in the function object, which is more commonly called a closure. The captured bindings play the role of "member variables", and the code part of the closure plays the role of the "anonymous member function", just like operator () in C++.

The closure constructor has the syntax (lambda (parameters ...) code ...). The (parameters ...) part allows an interface to be declared, so that the function takes the declared parameters. The code ... part consists of expressions that are evaluated when the functor is called.

Many uses of functors in languages like C++ are simply emulations of the missing closure constructor. Since the programmer cannot directly construct a closure, he or she must define a class which has all of the necessary state variables, and also a member function. Then, construct an instance of that class instead, ensuring that all the member variables are initialized through its constructor. The values are derived precisely from those local variables that ought to be captured directly by a closure.

A function-object using the class system, no use of closures:

(defclass counter ()
  ((value :initarg :value :accessor value-of)))

(defmethod functor-call ((c counter))
  (incf (value-of c)))

(defun make-counter (initial-value)
  (make-instance 'counter :value initial-value))

;;; use the counter:

(defvar *c* (make-counter 10))

(functor-call *c*) --> 11
(functor-call *c*) --> 12

Since there is no standard way to make funcallable objects in Lisp, we fake it by defining a generic function called FUNCTOR-CALL. This can be specialized for any class whatsoever. The standard FUNCALL function is not generic; it only takes function objects.

It is this FUNCTOR-CALL generic function which gives us function objects, which are a computer programming construct allowing an object to be invoked or called as if it were an ordinary function, usually with the same syntax. We have almost the same syntax: FUNCTOR-CALL instead of FUNCALL. Some Lisps provide "funcallable" objects as a simple extension. Making objects callable using the same syntax as functions is a fairly trivial business. Making a function call operator work with different kinds of "function things", whether they be class objects or closures is no more complicated than making a + operator that works with different kinds of numbers, such as integers, reals or complex numbers.

Now, a counter implemented using a closure. This is much more brief and direct. The INITIAL-VALUE argument of the MAKE-COUNTER factory function is captured and used directly. It does not have to be copied into some auxiliary class object through a constructor. It is the counter. An auxiliary object is created, but that happens "behind the scenes".

(defun make-counter (initial-value)
  (lambda () (incf initial-value)))

;;; use the counter

(defvar *c* (make-counter 10))

(funcall *c*) --> 11
(funcall *c*) --> 12

More than one closure can be created in the same lexical environment. A vector of closures, each implementing a specific kind of operation, can quite faithfully emulate an object that has a set of virtual operations. That type of single dispatch object-oriented programming can be done entirely with closures.

Thus there exists a kind of tunnel being dug from both sides of the proverbial mountain. Programmers in OOP languages discover function objects by restricting objects to have one "main" function to "do" that object's functional purpose, and even eliminate its name so that it looks like the object is being called! While programmers who use closures are not surprised that an object is called like a function, they discover that multiple closures sharing the same environment can provide a complete set of abstract operations like a virtual table for single dispatch type OOP.

In Ruby

Ruby has a number of objects that can be considered function objects, in particular Method and Proc objects. Ruby also has two kinds of objects that can be thought of as semi-function objects: UnboundMethod and block. UnboundMethods must first be bound to an object (thus becoming a Method) before they can be used as a function object. Blocks can be called like function objects, but in order to be used in any other capacity as an object (eg. passed as an argument) they must first be converted to a Proc. More recently, symbols (accessed via the literal unary indicator :) can also be converted to Procs. Using Ruby's unary & operator—equivalent to calling to_proc on an object, and assuming that method exists—the Ruby Extensions Project created a simple hack.

class Symbol
   def to_proc
      proc { |obj, *args| obj.send(self, *args) }
   end
end

Now, method foo can be a function object, i.e. a Proc, via &:foo and used via takes_a_functor(&:foo). Symbol.to_proc was officially added to Ruby on June 11, 2006 during RubyKaiga2006. [1]

Because of the variety of forms, the term Functor is not generally used in Ruby to mean a Function object. Rather it has come to represent a type of dispatch delegation introduced by the Ruby Facets project. The most basic definition of which is:

class Functor
  def initialize(&func)
    @func = func
  end
  def method_missing(op, *args, &blk)
    @func.call(op, *args, &blk)
  end
end

This usage is more akin to that used by functional programming languages, like ML, and the original mathematical terminology.

In Eiffel

Operations and objects are seen always as separate concepts in the Eiffel software development method and programming language. However, the agent mechanism facilitates the modeling of operations as runtime objects. Agents satisfy the range of application attributed to function objects, such as being passed as arguments in procedural calls or specified as callback routines. The design of the agent mechanism in Eiffel attempts to reflect the object-oriented nature of the method and language. An agent is an object which generally is a direct instance of one of the two library classes which model the two types of routines in Eiffel: PROCEDURE and FUNCTION. These two classes descend from the more abstract ROUTINE.

Within software text, the language keyword agent allows agents to be constructed in a compact form. In the following example, the goal is to add the action of stepping the gauge forward to the list of actions to be executed in the event that a button is clicked.

            my_button.select_actions.extend (agent my_gauge.step_forward)

The routine extend referenced in the example above is a feature of a class in a graphical user interface (GUI) library to provide event-driven programming capabilities.

In other library classes, agents are seen to be used for different purposes. In a library supporting data structures, for example, a class modeling linear structures effects universal quantification with a function for_all of type BOOLEAN which accepts an agent, an instance of FUNCTION, as an argument. So, in the following example, my_action is executed only if all members of my_list contain the character '!':

    my_list: LINKED_LIST [STRING]
        ...
            if my_list.for_all (agent {STRING}.has ('!')) then
                my_action
            end
        ...

When agents are created, the arguments to the routines they model and even the target object to which they are applied can be either closed or left open. Closed arguments and targets are given values at agent creation time. The assignment of values for open arguments and targets is deferred until some point after the agent is created. The routine for_all expects as an argument an agent representing a function with one open argument or target which conforms to actual generic parameter for the structure (STRING in this example.)

When the target of an agent is left open, the class name of the expected target, enclosed in braces, is substituted for an object reference as shown in the text agent {STRING}.has ('!') in the example above. When an argument is left open, the question mark character ('?') is coded as a placeholder for the open argument.

The ability to close or leave open targets and arguments is intended to improve the flexibility of the agent mechanism. Consider a class that contains the following procedure to print a string on standard output after a new line:

    print_on_new_line (s: STRING)
            -- Print `s' preceded by a new line
        do
            print ("%N" + s)
        end

The following snippet, assumed to be in the same class, uses print_on_new_line to demonstrate the mixing of open arguments and open targets in agents used as arguments to the same routine.

    my_list: LINKED_LIST [STRING]
        ...
            my_list.do_all (agent print_on_new_line (?))
            my_list.do_all (agent {STRING}.to_lower)
            my_list.do_all (agent print_on_new_line (?))
        ...

This example uses the procedure do_all for linear structures, which executes the routine modeled by an agent for each item in the structure.

The sequence of three instructions prints the strings in my_list, converts the strings to lowercase, and then prints them again.

Procedure do_all iterates across the structure executing the routine substituting the current item for either the open argument (in the case of the agents based on print_on_new_line), or the open target (in the case of the agent based on to_lower).

Open and closed arguments and targets also allow the use of routines which call for more arguments than are required by closing all but the necessary number of arguments:

            my_list.do_all (agent my_multi_arg_procedure (closed_arg_1, ?, closed_arg_2, closed_arg_3)

The Eiffel agent mechanism is detailed in the Eiffel ISO/ECMA standard document.

Other meanings

In a more theoretical context a function object may be considered to be any instance of the class of functions, especially in languages such as Common Lisp in which functions are first-class objects.

In some functional programming languages, such as ML and Haskell, the term functor has a different meaning; it represents a mapping from modules to modules, or from types to types and is a technique for reusing code. Functors used in this manner are analogous to the original mathematical meaning of functor in category theory, or to the use of generic programming in C++, Java or Ada.

In Prolog and related languages, functor is a synonym for function symbol.

See also

• Callback
• Function pointer
• function closure
• Command pattern
• Currying

References

Further reading

• David Vandevoorde & Nicolai M Josuttis (2006). C++ Templates: The Complete Guide, ISBN 0-201-73484-2 : Specifically, chapter 22 is entirely devoted to function objects.

External links

• Description from the Portland Pattern Repository
• C++ Advanced Design Issues - Asynchronous C++ by Kevlin Henney
• The Function Pointer Tutorials by Lars Haendel (2000/2001)
• Article "Generalized Function Pointers" by Herb Sutter
• Generic Algorithms for Java