{{ This is a re-published article: it first appeared on my personal blog in 2010. }}
If you have watched any of the videos on SICP recorded in MIT during the 1980s, you may already have a good idea of the intuitive way in which Lisp allows one to express the notion of program flow in a functional way. Recently, while viewing the lectures myself, I decided to implement some of the ideas as explained by Professor Sussman in the aforementioned video series. However, my language of choice is C#. As it turns out, C# does provide some very good facilities for expressing functional programs, and those of us from the C world should find it easier to relate to it without having to understand the unfamiliar parenthesized syntax that many perceive as one of the many quirks of Lisp, et al.
To start with, I wrote a simple program that does summation of a series using simple recursion like so:
Thus, given a lower-bound value (argument a) and an upper-bound argument (b), we end with the following summation (hmm, wish I knew Latex):
I really don’t want to go into the details of how recursive functions work here, but if you are interested, you can go through my article on recursion. To put it simply enough, every single recursive call keeps accumulating or “stacking up” the result such that you eventually end up with the summed up value.
Similarly, we next have a function for calculating the sum of squares like so:
where the function Square (x) is defined as below:
Similarly we have a Cube function and a function that expresses 2x + 1 as below:
Thus we could now have functions for getting the sum of cubes or the sum of the expression (2x + 1) like so:
and so forth.
However, if you observe closely you will see that the basic function – regardless of whether it is summation of squares, cubes, or just about anything else – remains the same; the only notable difference is the way the lower-bound argument is “transformed.” For example, in the case of SummationSquare, the argument a is squared, while in SummationCube, it is cubed. In the case of simple summation of a, it remains the same, or in other words, the argument is identified by itself, so we can say that an identity transform is applied to it.
We thus find that we can further abstract the transformation itself into a parameter to our function. To be able to do that in C#, however, we need to declare a delegate like so:
delegate int Transform (int i);
(For those of you from the C world, a delegate is not much different from a function pointer.) And we next change the function to accommodate this delegate:
And I can now pass a transform function itself as the transform argument:
In case we would like to transform a back to itself, we could always use an identity function.
And then invoke the function like so:
int val = SummationWithTransform (1, 5, Identity);
Using the identity function would be useful when we would want to do a summation operation as expressed below.
You will have realized by now that SummationWithTransform has now become a higher-order function, that is a function that takes another function as its argument.
Let’s get a little more ambitious next. We see that in all cases the value of a is being stepped up by a single increment. How about letting the caller define how the increment ought to be done? To be able to do that, we would first need to declare a delegate that embodies the functionality for incrementing, or better yet, getting the next value for a, whatever that may happen to be.
And we now change the function SummationWithTransform to take one more parameter.
In this case SummationWithTransform is the same except that it takes any delegate object of type Next. The Next delegate object merely embodies how the next value for the lower-bound argument may be obtained. And notice that in the function at the point where we are doing the recursive call, instead of passing (a + 1) we now invoke the Next object. To see this in action, look at the following piece of code.
where the last argument is a function of Next type, in this case it is as below.
It could even have been something like this:
As an aside, one thing to note is that we could even use lambda functions here. Look at the function invocation line below.
Or even:
Next, let’s get a little dynamic, what with the never-ending holy wars about whether static- or dynamic-typing is better. C# 4.0 now supports the keyword dynamic. So let’s make our summation function (and the Next function too) more generic.
We invoke this like so:
where IncrBy4 is as defined below:
One thing to bear in mind, however, is that though C# may appear to be dynamic, it is in reality a statically-typed language. That’s the reason that we still have to declare the delegates prior to their being used within the program. Secondly, the entire program is purely functional, since none of the functions holds any state information.