STL-Style Functors
As a C++ programmer, I've come to rely on the STL when it comes to implementing my
solutions. Since I am a C++ programmer learning C#, I will use C++ terminology
to explain concepts. If you are not a C++ programmer and have no idea what I'm
referring to (although I promise to keep things as easy as possible), please
use the message board to ask for an explanation.
One of the tools that an STL-programmer must learn to master is the functor
concept. A functor is any valid expression that can be syntactically written
as a function call. Those expressions can be functions, function pointers and
operator()
overloading. Functors may exist in other forms, but I
can't think of any other at this moment. For those who can name another form,
don't hesitate to enlighten me on the message board below. Also,
The concept of functors is very powerful. It allows one, with the use of generic
template programming, to use function pointers and operator()
overloads
interchangeably. Template containers use functors for equality testing,
ordering, predicates, etc. where the user of the container dictates how the
stored values are to be interpreted.
For instance, suppose you want to perform some task on each element in a
container. You could write code like this:
for(i = 0; i < container.size(); ++i) {
perform_task(container.get(i));
}
This code is very simple to write. Unfortunately it's also very error prone.
It's easy to write <
when you meant >=
and vice
versa. What if you have hundreds of these simple loops in your code and just
one of them are faulty? It may or may not be hard to find the error, but it's
something you do not want to do as a programmer. Solving new problems is more
fun than fixing old errors.
So, how are functors going to help here? Well, for starters, you can cleverly
abstract away the loop by writing a function which does the looping for you.
The intent of abstracting the loop is to have it written once. By having it
written only once, you can verify its correctness once.
The loop function should be devised in such way that it accepts a container and
a functor as input. The functor, function pointer or object overloading ()
,
must be capable of handling the elements in the container. Let me demonstrate
with some pseudo-code:
for_each(container, functor) {
for(i = 0; i < container.size(); ++i)
functor(container.get(i));
}
There's the loop - encapsulated in a function. Verify its correctness. Once
verified, we can use it like this:
for_each(container, perform_task);
Simple isn't it? And very readable too! We've just compressed the code by a
factor of three except for the constant overhead of 5 lines (but what's 5 lines
in a sea of hundreds of loops?)
C# Delegates
Delegates in C# gives the programmer a way to masquerade a method on a specific
object as a free function. The only requirement is that the function and the
method have the same type signature, meaning that return values and parameters
must be of the same type.
When the delegate is created it is given a reference to an object and the
targeted method. Each delegate call will then cause a call on the objects
method used during construction of the delegate.
Since delegates are first class citizens of C#1 and delegates only
depend on the type signatures on a method, objects anonymous to eachother2,
the value of delegates are significant - less interdependencies on interfaces!
Why do we need Functors when there are Delegates?
In my opinion, functors are needed when delegates can't do the job. Jobs that delegates can't handle include:
- Binding of parameters
- Composition of delegates
Parameter Binding
Parameter binding3 is like delegating the function. Suppose you have
a function f(x, y). If you bind a constant c to f's first
parameter, you can interpret f(c, y) as g(y). This can't be
done using delegates: it's all or nothing. Functors can be cleverly designed
so that parameter binding is possible, as demonstrated by the people behind the
STL. I will show a simple technique on how to implement this in C#.
Composition
Composition is a method to chain functions. Consider the functions f(x)
and g(x). By chaining these functions like this f(g(x)) we
can interpret that chain as a new function h(x).
C# Implementation of Functors
I'll be using objects for solving the main problems of delegates - parameter
binding and composition. But since I want functors to act like free functions,
I'll be using a couple of delegate types for that purpose!
The Delegates
The following delegate types are defined:
public class Functors {
public delegate object Functor();
public delegate object UnaryFunctor(object objArg1);
public delegate object BinaryFunctor(object objArg1, object objArg2);
public delegate object TernaryFunctor(object objArg1, object objArg2, object objArg3);
...
}
As you can figure out by looking at the delegate declaration above, I'll only
support a few functor cases; functors with no parameters to functors with three
parameters. It's very easy to add more levels, but with my experience, one
seldom finds the need for more.
Also worth noting is the type signatures on the delegates. As I mentioned
earlier, these delegates will be the interface to the functors. This means that
the functors will have the same limitation as the delegates: object
.
C# is a "fluffy" language (pardon my French) and is a semi-strong typed
language. It uses the type object
as a base type for everything.
This means that all values can be treated as an object
. This is a
good thing since it promotes generalization. Although a lot of casting may be
required as a result of using object
as the base type. In C++, which
is a strongly typed language which supports template type parameters, you do
not need to take care of the types - C++ does it for you. C++ programmers may
laugh at this type system, but if there is no other tool in the toolbox, one
has to make the best of it - or get another toolbox.
The bound unary function
The bound unary function is a unary function, whose only parameter has been
bound. In essence it's a functor which takes no argument. This is where the
classes and objects come into play:
private class BoundUnaryFunctor {
UnaryFunctor m_func;
object m_objArg;
public BoundUnaryFunctor(UnaryFunctor func,
object objArg) {
m_func = func;
m_objArg = objArg;
}
public object Call() {
return m_func(m_objArg);
}
}
As you can see, a bound unary functor is constructed by using a unary functor
delegate and a constant value. The unary functor delegate can be called by
calling the Call
method of the BoundUnaryFunctor
objects.
The helper functions
As a pure coincidence, the Call
method happens to match parameter
less functor delegate. This means that a delegate of type Functor
can
be created by using a reference to new BoundUnaryFunctor(aUnaryFunctor, aValue).Call
.
UnaryFunctor uf = ...;
Functor f = new Functor(new BoundBinaryFunctor(
uf, someValue).Call);
f();
To simplify the syntax for binding a parameter, there's a helper function:
public static Functor BindUnaryFunctor(
UnaryFunctor uf, object objArg) {
return new Functor(new BoundUnaryFunctor(
uf, objArg).Call);
}
The bound binary and ternary functors
The bound binary functors are implemented similarly to the bound unary
functions. Binary functors can be bound into unary functors. In the binary
functor case there are two possible parameters to bind. This code does not
require you to bind the first parameter only; you specify which parameter to
bind. Either way the result is a unary functor. The code that makes this work
looks like this:
private class BoundBinaryFunctor {
BinaryFunctor m_func;
int m_nParam;
object m_objArg;
public BoundBinaryFunctor(BinaryFunctor
func, int nParam, object objArg) {
if(nParam < 0 || nParam > 1)
throw new IndexOutOfRangeException(
"BoundBinaryFunctor: nParam must be
>= 0 and <= 1");
m_func = func;
m_nParam = nParam;
m_objArg = objArg;
}
public object Call(object objArg) {
if(m_nParam == 0)
return m_func(m_objArg, objArg);
else
return m_func(objArg, m_objArg);
}
}
The constructor accepts a binary functor, a parameter specifying which
parameter to bind and the value to bind. Note that the parameter specifier is
0-based, meaning the first parameter is represented by 0
and the
second by 1
. Just as BoundUnaryFunctor.Call
matches a
Functor
,
BoundBinaryFunctor
matches a
UnaryFunctor
.
As you can see, the parameter specifier is used in the Call
-method.
Depending on which parameter is bound, the argument of Call
is
passed as the binary functors first or second parameter.
The bound ternary functor works just like the bound binary functor, with the
exception that it turns a ternary functor into binary functor.
The rest of the code looks like this:
private class BoundTernaryFunctor {
TernaryFunctor m_func;
int m_nParam;
object m_objArg;
public BoundTernaryFunctor(TernaryFunctor
func, int nParam, object objArg) {
if(nParam < 0 || nParam > 2)
throw new IndexOutOfRangeException(
"BoundTernaryFunctor: nParam must be
>= 0 and <= 2");
m_func = func;
m_nParam = nParam;
m_objArg = objArg;
}
public object Call(object objArg1,
object objArg2) {
if(m_nParam == 0)
return m_func(m_objArg,
objArg1, objArg2);
else if(m_nParam == 1)
return m_func(objArg1,
m_objArg, objArg2);
else
return m_func(objArg1,
objArg2, m_objArg);
}
}
public static UnaryFunctor BindBinaryFunctor
(BinaryFunctor bf, int nParam,
object objArg) {
return new UnaryFunctor(new
BoundBinaryFunctor(bf, nParam,
objArg).Call);
}
public static BinaryFunctor BindTernaryFunctor(TernaryFunctor tf, int nParam, object objArg) {
return new BinaryFunctor(new BoundTernaryFunctor(tf, nParam, objArg).Call);
}
The Composed Functors
The composed functors support only composition of unary functors. The basic
idea is to let an object chain the functor calls, much like the bound functors
pass the bound parameters. The implementation should by now be quite obvious,
so here it is:
private class ComposedUnaryFunctor {
UnaryFunctor m_f, m_g;
public ComposedUnaryFunctor(UnaryFunctor f, UnaryFunctor g) {
m_f = f;
m_g = g;
}
public object Call(object objArg1) {
return m_f(m_g(objArg1));
}
}
public static UnaryFunctor Compose(UnaryFunctor f, UnaryFunctor g) {
return new UnaryFunctor(new ComposedUnaryFunctor(f, g).Call);
}
Some Functor Aware Algorithms
A functor is only as good as where it can be used. I've written a couple of
algorithms which resemble those found in the STL <algorithm> header.
I could "copy" all of the algorithms from the STL since they utilize the iterator
concept. The closest thing you get in .NET are the enumerators. Simply
put, enumerators are less equipped iterators. Because of this, some of the
algorithms which rely on the stronger features found in iterators, could not be
easily ported. I think it is possible write a similar iterator implementation
in .NET, but it would not be feasible since no predefined container could
utilize them. The algorithms I wrote are by no means as complete as those found
in STL, but nevertheless, they may be useful.
Not only do the algorithms utilize the general functors, they also utilize some
specialized functors/delegates. These are:
- Predicate
- A delegate of type
bool (object)
- BinaryPredicate
- A delegate of type
bool (object, object)
- Compare
- A delegate of type
int (object, object)
Predicates are typically used to determine a truth for some value. An example
of such a predicate is bool IsNull(object obj)
. A binary predicate
are typicall used to determine a truth for a relation between two values. An
example of this is bool IsGreater(object obj, object objBelievedToBeGreater)
.
ForEach
This algorithm takes an enumerator and a functor. It then applies the functor
on each element enumerable by the enumerator. This is the C# implementation of
the pseudo-code example I showed above.
ForEachWhich
This algorithm works just like the algorithm ForEach
with one
exception - it uses a predicate to determine whether it peform the functor on
each element.
Accumulate
This algorithm seeks to accumulate some value over all elements enumerable by
the enumerator. It takes an enumerator, a start value and a binary functor as
input. With it, it'll perform startValue = binaryFunctor(startValue, element)
for each element. The accumulated value is then returned. If startValue
is zero and binaryFunctor
is a function which adds numbers and
return the sum, then accumulate can be used to sum all elements.
FindIf
The algorithm takes an enumerator and a predicate. The function will enumerate
all elements until it finds an element that satisfies the predicate or it'll
reach the end. In both cases, the enumerator is returned.
Some examples
Sum all elements
public class Example {
object Add(object objLeft, object objRight) {
return (int)objLeft + (int)objRight;
}
void example() {
ArrayList a = new ArrayList();
a.Add(1);
a.Add(2);
a.Add(3);
a.Add(4);
a.Add(5);
int nSum = (int)Algorithms.Accumulate(
a.GetEnumerator(), 0,
new Functors.BinaryFunctor(Add));
}
}
Print all numbers squared and doubled
public class Example {
object Square(object obj) {
return (int)obj * (int)obj;
}
object Multiply(object objLeft, object
objRight) {
return (int)objLeft * (int)objRight;
}
object Print(object obj) {
Console.Out.Write(obj);
return null;
}
bool IsEven(object obj) {
return (int)obj % 2 == 0;
}
void example() {
ArrayList a = new ArrayList();
a.Add(1);
a.Add(2);
a.Add(3);
a.Add(4);
a.Add(5);
Functors.UnaryFunctor dbl =
Functors.BindBinaryFunctor(new
Functors.BinaryFunctor(Multiply), 0,2);
Functors.UnaryFunctor dblAndSquare =
Functors.Compose(dbl, new
Functors.UnaryFunctor(Square));
Functors.UnaryFunctor dblAndSquareAndPrint
= Functors.Compose(new Functors.
UnaryFunctor(Print), dblAndSquare);
Algorithms.ForEachWhich(a.GetEnumerator(),
dblAndSquareAndPrint, new
Functions.Predicate(IsEven));
}
}
Last Words
Notes about the examples
The examples above are solutions to trivial problems indeed. But keep in mind
that these functors are small but effective building blocks. By piecing them
together one can make pretty elegant solutions to complex tasks.
Enumerators
Without going too deep into the realms of iterators, I must say .NET
enumerators are inferior to STL iterators. I'm sure there is a perfectly valid
explanation why enumerators are much weaker than iterator. I suspect it has to
do with the type system used in the .NET runtime. All I can say is that if the
enumerators would have been just as powerful as iterators, far more complex
algorithms could be written using the functor concepts.
Casting and Objects
Since the type system is not as complete in C#/.NET as in C++, one has to
depend on the object
type. object
is perfectly
generic to represent all values in C#/.NET so the functors can be applied to
any type of parameters. You, the programmer however, must enforce type
integrity using casts. The compiler cannot help you once you downcast to object
.
.NET Platform
The .NET platform allows other languages to use the functor concepts. Visual
Basic is to many people somewhat of a toy language. But with .NET Visual Basic
is no longer confined in the sand box. Who could've dreamed of
functions/functors as first class language citizens when VB6 was the new kid on
the block?
Why?
Hi, my name is Jörgen Sigvardsson, and I'm a C++ programmer.
Not until recently have I played with C# or .NET. Compared to raw C++, it's a
whole new environment. I'm still learning and have some more steps to take
before I can call myself a C# programmer. The first steps I usually take when
learning a new language and environment, is to see if I can redo what I've done
before in another environment. I tend to re-invent the wheel in terms of
abstract datatypes and algorithms. That way I'm already familiarised with the
problem, which means I can focus entirely on the language and environment.
Sometimes I save code during these stages, for later use. This functor code is
one such example, and I thought someone else might have use for it.
Footnotes
1 First class citizens of a language means that it can be
treated as any other value. It can be passed in method calls, delegate calls,
stored in containers. Just what you'd expect of a "simple" int.
2 Anonymous in such way that they have don't know each others
interfaces.
3 Parameter binding is loosely related to the concept or currying.
Contrary to common belief, function currying is not a way to spice up your
functions. It's a concept named after it's "inventor"
Haskell Brooks Curry.
Revision History
25 Sep 2002 - Initial Revision