STL-Style Functor Delegates

• Download source files - 9 Kb

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:

// Pseudo-code
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:

// 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#¹ and delegates only depend on the type signatures on a method, objects anonymous to eachother², 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 binding³ 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(); // Which basically means uf(someValue)

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; // hush the compiler
    }
  	
    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);
	
        // Multiply(2, x) = Double(x)
        Functors.UnaryFunctor dbl = 
         Functors.BindBinaryFunctor(new
          Functors.BinaryFunctor(Multiply), 0,2);

        // Double(Square(x)) = DoubleAndSquare(x)
        Functors.UnaryFunctor dblAndSquare =
            Functors.Compose(dbl, new
                  Functors.UnaryFunctor(Square));

        // Print(DoubleAndSquare(x)) = 
        // DoubleAndSquareAndPrint(x)
        Functors.UnaryFunctor dblAndSquareAndPrint
           = Functors.Compose(new Functors.
               UnaryFunctor(Print), dblAndSquare);

        // DoubleAndSquareAndPrint for each element
        // which are even
        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

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

² Anonymous in such way that they have don't know each others interfaces.

³ 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