Mindshift: Part 10

Recursion Using Only Anonymous Functions

Maybe I should start with a warning: Before reading this blog, please ensure that you understand the principles of functional refactoring described in the previous Mindshift: Part 9 blog. If you don't understand these principles already, what follows might well appear cryptic or even nonsensical.

Remember back in Mindshift: Part 4 we stated that we would confine ourselves to writing code that:

  1. Uses only anonymous functions - well OK, we cheated here and named the functions, but the principle of inline function definition demonstrated that such function names are actually unnecessary.
  2. These (mostly) anonymous functions should take only one parameter

Well, this is all pretty straightforward up till the point we need to write a recursive function.

The classic example of recursion is the good old factorial function - which is exactly why I'm not going to use it. Instead, I'll use another common recursive function that calculates the n'th Fibonacci number.

However, we have a problem. Our rules state that all our functions should be anonymous; therefore, how can an anonymous function call itself recursively? What name should it use to identify itself?

In the above example, the definition of the fib function contains a reference to itself, and this breaks the rules.

So, we need to start refactoring things.

Refactoring The fib Function

Attempt 1

We could try the following approach. Since fib contains a reference to itself, why don't we wrap it in another function that takes the definition of fib as a parameter.

Hmmm, think about that for a moment... That won't work, will it.

All we've done here is move the problem to the point where we call make_fib. We haven't done anything to change the fact that function fib still contains a self-reference.

Attempt 2

Let's think about the way the Fibonacci series is calculated. We know it works in a stepwise manner: it starts with the number pair (0,1), then it performs a "shift and add" operation and outputs the next number pair.

So (0,1) becomes (1,1). If we then use (1,1) as the starting point for calculating the next pair, we get (1,2); then (1,2) can be used to generate (2,3), and (2,3) can be used to generate (3,5) etc.

So in general, we can say that given a number pair (a,b), we shift and add these numbers to generate the output (b,a+b), and we do this as many times as needed.

So to start with, we will alter the definition of make_fib so that, given the starting number pair of (0,1), it moves us only one step further down the series.

We need to change several things here:

  1. We need an additional error function to trap the times when we push our little one-step engine too far.
  2. Rename function make_fib to be fib_next
  3. Rename function fib to be fib_step

Here, we pass the fib_next function the error function as its parameter. This function then appears as the parameter fib_step and will be called when n is greater than or equal to one.

Hence, the "KABOOM!" result when we call fib0(1,0,1).

Ok, that's a start - but it doesn't get us very far does it?

But let's look at how function fib_next works. Its a higher order function that takes a single function as a parameter and gives back a partial function in three parameters. When this partial function (here called fib0) is supplied with the relevant parameters, it is then able to calculate the first number in the Fibonacci series.

So if we start nesting fib_next calls inside each other, we should get back functions that calculate the number of the Fibonacci series corresponding to the number of nested fib_next calls...

Well that works, but all those nested calls are just silly...

OK, let's remove the nested calls by passing fib0 back into fib_next, to generate fib1, then use fib1 to generate fib2 etc...

Well we're getting closer to the goal. All we need to do is decide what the highest number we be that we will ever need from the Fibonacci series, and call fib_next that many times...

Uh, no! That's not much of a solution is it?

Yeah, you're right...

Attempt 3

Ok, so let's refactor function fib_next using the function wrapping technique we saw in the previous blog. Remember how this works? This is where we wrap a function inside another function and then immediately call the new wrapper function. It is optional whether you pass the new wrapper function a parameter, but in this case, we're going to pass an inline definition of fib_next.

In the code below, we have wrapped fib_next in an anonymous function that takes a single parameter. Then, we immediately call this wrapper function passing in the definition of fib_next as an inline function.

In the previous code samples, we gave these generated partial functions names like fib0 or fib1 etc, but now, we'll just call it fib_x. This is to indicate we are detaching this partial function from any specific number in the Fibonacci series.

The new, anonymous wrapper function is a higher-order function that takes a single parameter called fib_next. fib_next needs to be a function because we then make two nested calls to it.

The two levels of nested call make this exactly the same as the line of code we saw in attempt 2 above where we defined:

fib1 = fib_next(fib_next(error)).

Next, we need to immediately invoke this new, anonymous function. But we can't just invoke the function without passing it a value to work with, so we surround the inline definition of fib_next in parentheses, making it the parameter value to the wrapper function.

(fib_step => (n,a,b) => n < 1 ? a : fib_step(n-1,b,a+b))

Hmmmm, we've added another layer of indirection here, but it looks like a backward step because we can only calculate the first and second numbers in the series. We still don't seem to be much closer to a general solution...

Attempt 4

We know that the wrapper function we've just created is a higher-order function that takes a function as its parameter; however, the only function we've ever passed it so far has been the error function. But the error function doesn't serve any useful purpose in terms of calculating numbers in the Fibonacci series: it simply writes a silly string to the console when called. So let's try doing without it.

Huh, that's odd! This works for the first number in the Fibonacci series (index zero), but returns a function when asked for any number further down the series.

But take a look at the returned function - haven't we seen that before? Yes, of course! Its the original Fibonacci function!

So for any index number higher than 0, we get back a copy of the Fibonacci function. Well in the same way that we created nested calls to fib_next in attempt 2, we need to pass this Fibonacci function to another function in order to get it to calculate the next number in the series.

Well, the perfect function to use here is fib_step, because this already does exactly what we want.

So we have now arrived at the point where we can start to see why all this refactoring was necessary. Since we have turned our recursive function into an inline definition that is then passed around as a parameter, we can implement recursion without ever needing to assign that function a global name.

And just for the sake of clarity, it is somewhat redundant to use the name fib_step inside the function definition, because this hides the fact that this value is nothing more than the definition of fib_next. So although it is not a technical requirement, we can rename fib_step to fib_next just to avoid having two different names for the same value.

So we'll now do two things:

  1. Pass fib_step a copy of itself as its parameter. Notice that since fib_step expects a function as a parameter and not a list of numbers, we must pass fib_step as the first parameter to itself. Then, since fib_step returns a partial function, the existing parameters (n-1,b,a+b) become the parameters to the partial function that actually calculates the required number in the Fibonacci series.
  2. Rename all occurances of fib_step to be fib_next, because the same functionality used in both places.

Ok, so where does that leave us?

In the immortal words of First Mate Gibbs from the Pirates of the Caribbean:

"Slap me thrice and hand me to my Mamma!"

We've implemented recursion using only anonymous functions!

Let's break down what we've done so far:

  1. We have a partial function that receives a parameter called fib_next.
    (fib_next => fib_next(fib_next))
  2. This partial functions calls whatever function it receives as a parameter and immediately passes that function to itself as a parameter. In other words:
    1. Some function is received in parameter fib_next
    2. We call this function
    3. When calling this function, we pass it a copy of itself fib_next(fib_next). This ensures that no matter what function fib_next actually does, it always receives a copy of itself and can therefore take one more step down the recursive rabbit hole.
  3. The value of parameter fib_next is the function that actually knows how to calculate the Fibonacci series. However, this calculation is wrapped in a higher-order function that expects a definition of the function that must be called when another recursive step is required.
    All of this information is supplied as the following inline definition:
    (fib_next => (n,a,b) => n < 1 ? a : fib_next(fib_next)(n-1,b,a+b));
  4. The call to fib_next(fib_next) returns a partial function that expects three numbers as parameters. This is the function that actually performs the required Fibonacci series calculation.
  5. The function generated in the previous step now disappears down a recursive rabbit hole until it reaches the point at which the termination condition is satisfied (which in this case is when n < 1 becomes true).
    At this point, recursion stops and the required values are returned.

So, we have succeeded in implementing recursion using nothing but anonymous functions!

This is great if we want only to calculate the Fibonacci series; but unfortunately, its still not the generic Y-Combinator we're after.

Some refactoring is still needed before this recursive example is the actual Y-Combinator. This will be the subject of my next blog.

Chris W

All source code from the Mindshift blog series can be found on GitHub