Higher Order Programming is one of those things that to many people sounds weird, magical, mysterious or just too hard for them to be able to do. It's not. If you have ever passed a function or method as a parameter to another function or method, then you have done higher order programming. If you have ever used a function pointer in C or a delegate in C# or some kind of callback mechanism, then you have done higher order programming.

Define it!

We are all used to writing code that takes parameters. We do it whenever we write subroutines, functions or methods. Normally these parameters are data. In higher order programming, one or more of these parameters is code rather than data. That is, you can pass code, functions and/or methods around, just as you can pass data around. That's all there is to it.

Show me an example

Let's look at C#, because the syntax will not be too unusual to programmers in many languages. Suppose we have a List of scores for a test.

var Scores = new List<int>() { 2, 7, 9, 5, 6, 10, 8 };

We want to get all scores that were considered passes. Suppose the test is out of ten, and to pass you need to get more than half marks. We can write a method to determine whether a score is a pass and that returns a boolean (true or false value).

public bool Pass(int Score)
{
    return Score > 5;
}

Then we can use the FindAll method to find all scores that were considered passes.

var Passed = Scores.FindAll(Pass);

Notice what we have done here. We did not call the Pass method ourself. Instead, we passed the Pass method to the FindAll method as a parameter. Internally, it looped over the values in the list and called the Pass method on each of them, and put those that it returned true for into a new list and returned it.

You are probably now thinking, why go to all the trouble when I could have just written a loop? And it's true - you could have written a loop that did the test in an if statement and build a new list.

var Passed = new List<int>();
foreach (var Score in Scores)
    if (Score > 5)
        Passed.Add(Score);

However, step back and think about what we just achieved from a software engineering perspective. It is a well known principle that separation of concerns helps to reduce code complexity. Here we have separated the concerns of:

• Testing each element of a list and building a new list of elements that passed the test
• The test itself

Therefore, higher order programming is a tool that enables us to reduce our code complexity by separating concerns, and also increase code re-use along the way.

Code without a name

You might be thinking, "huh, I just wrote more code than I would have; I had to define a whole extra method!" You can also argue, quite reasonably, that we have actually made the program harder to understand now too, because you have to go and find the Pass method to fully understand the code.

While sometimes we may have complex conditions that we wish to re-use in many places in our program - in which case writing a separate function or method is the right thing to do - in this case it would be nice if we could take advantage of higher order programming without having to resort to writing a separate method.

Enter anonymous methods, or lambda expressions. These allow you to define a method (or function, depending on your language) without a name and inside another method. Let's re-write the previous example using a lambda expression.

var Passed = Scores.FindAll(Score => Score > 5);

The "=>" is the syntax for defining an anonymous method in C# 3.0. Anything to the left of it is a parameter that the method takes. In this case, it takes a single parameter named "Score". To the right of it is the body of the method, with an implicit "return" (that is, it will return the boolean result of testing whether its parameter Score is greater than 5).

You could read the "=>" quite nicely in this case as "where". That is, "find all scores where the score is greater than five".

Yes, you can return code too

Suppose that I want to work out how many scores got different grades. For example, Grade A was given for scores between 8 and 10, Grade B for given for between 5 and 7, and so forth. We could write:

var GradeA = Scores.FindAll(Score => Score >= 8 && Score <= 10);
var GradeB = Scores.FindAll(Score => Score >= 5 && Score <= 7);

However, it would be nice if we could make something that read more clearly, such as:

var GradeA = Scores.FindAll(Range(8,10));
var GradeB = Scores.FindAll(Range(5,7));

How could this work? Well, FindAll expects a method that takes an int and returns a bool. This type of method - that is, a method with that signature - has a name: Predicate. Therefore, the Range method needs to have a return type of Predicate (actually, Predicate<int>, which means that the parameter it takes is of type int).

public Predicate<int> Range(int LowerLimit, int UpperLimit)
{
}

And what do we write inside the Range method? Well, we return an anonymous function that takes a single parameter and tests if it is squeezed between the two values we supplied as parameters to the Range method.

public Predicate<int> Range(int LowerLimit, int UpperLimit)
{
    return x => x >= LowerLimit && x <= UpperLimit;
}

And that's it.

What languages support this?

Here's the stinger: not all languages support these kinds of programming techniques. C# started out with the ability to do higher order programming, but without anonymous methods. In C# 2.0 they introduced anonymous methods, but with a fairly cumbersome syntax. In C# 3.0, they introduced the nice "lambda" syntax that I have shown here. Essentially, the language designers have realized more and more the value of higher order programming and worked to make it as easy as they make object oriented programming. The C# of today is a truly multi-paradigm language.

Many of the dynamic languages provide good support for this, including Perl, Python and Ruby. C enables it through function pointers, though there's no anonymous method or lambda style syntax. Java, however, has so far chosen to stick to its object oriented roots rather than embracing the multi-paradigm approach. We'll leave arguing about whether that's a good or a bad thing for another time. And primarily functional languages, such as ML and Haskell, make extremely heavy use of higher order programming techniques.

Taking it further

The examples I've shown here are trivial, but they are enough to give you a taste of what higher order programming is about. Try writing some code like this yourself, or reading up on higher order programming in a language of your choice. And when you're trying to work out a good way to get better code reuse and reduce code complexity, keep it in mind as one of the tools in your toolbox, alongside the other paradigms (such as object oriented programming, procedural programming and generic programming) that you are probably already more familiar with.

Post Comment Return To Blog

public Predicate<int> Range(int LowerLimit, int UpperLimit)
{
    return x => x >= LowerLimit && x <= UpperLimit;
}

public delegate bool Predicate<T>(T Item);