Mindshift: Part 10 Republished on Feb 5th, 2018 Previous Blog Next Blog 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: 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. 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.
{ // Recursive definition of the Fibonacci series // When calling this function, you must supply the zero-based index // of the desired number in the sequence, followed by zero and one as // the series starting values var fib = (n,a,b) => n < 1 ? a : fib(n-1,b,a+b); // Derive the 8th number in the Fibonacci series return fib(8,0,1); }
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.
{ // Attempt 1: Try to extract the definition of fib by making it a // parameter var make_fib = fib => (n,a,b) => n < 1 ? a : fib(n-1,b,a+b); // So, all I need to do is call make_fib and pass it the definition // of fib as a parameter var fib = make_fib(/* definition of fib */) }
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: We need an additional error function to trap the times when we push our little one-step engine too far. Rename function make_fib to be fib_next Rename function fib to be fib_step
{ // Attempt 2: Calculate only the first number in the Fibonacci series // Notice that the error function completely ignores its parameters. // It does nothing more than return a constant value - which in this // case is the string 'KABOOM'. This means that this function should // only ever be called when an error condition has already occurred var error = (n,a,b) => "KABOOM!"; var fib_next = fib_step => (n,a,b) => n < 1 ? a : fib_step(n-1,b,a+b); // Create a function that gives us the first number in the Fibonacci // series var fib0 = fib_next(error); // -> (n,a,b) => n < 1 ? a : error(n-1,b,a+b) return { fib0 : fib0(0,0,1), fib1 : fib0(1,0,1) } }
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...
{ var error = (n,a,b) => "KABOOM!"; var fib_next = fib_step => (n,a,b) => n < 1 ? a : fib_step(n-1,b,a+b); // Create a function that gives us the first number in the Fibonacci series var fib0 = fib_next(error); var fib1 = fib_next(fib_next(error)); var fib2 = fib_next(fib_next(fib_next(error))); var fib3 = fib_next(fib_next(fib_next(fib_next(error)))); return { fib0 : fib0(0,0,1), fib0_1: fib0(1,0,1), fib1 : fib1(1,0,1), fib1_2: fib1(2,0,1), fib2 : fib2(2,0,1), fib2_3: fib2(3,0,1), fib3 : fib3(3,0,1), fib3_4: fib3(4,0,1) } }
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...
{ var error = (n,a,b) => "KABOOM!"; var fib_next = fib_step => (n,a,b) => n < 1 ? a : fib_step(n-1,b,a+b); // Create a function that gives us the first number in the Fibonacci series var fib0 = fib_next(error); var fib1 = fib_next(fib0); var fib2 = fib_next(fib1); var fib3 = fib_next(fib2); var fib4 = fib_next(fib3); var fib5 = fib_next(fib4); var fib6 = fib_next(fib5); var fib7 = fib_next(fib6); var fib8 = fib_next(fib7); var fib9 = fib_next(fib8); // Function fib9 can now calculate any number in the Fibonacci series // up to and including the 9th number. Trying to calculate the 10th // number will cause an error. return { fib9_7 : fib9(7,0,1), fib9_8 : fib9(8,0,1), fib9_9 : fib9(9,0,1), fib9_10: fib9(10,0,1) } }
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.
{ // Attempt 3.1: Perform function wrapping on function fib_next. Here // we pass the wrapper function the definition of fib_next and then // call it immediately var error = (n,a,b) => "KABOOM!"; var fib_x = (fib_next => fib_next(fib_next(error))) (fib_step => (n,a,b) => n < 1 ? a : fib_step(n-1,b,a+b)); }
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))
{ // Attempt 3.2: Perform function wrapping on function fib_next. Here // we pass the wrapper function the inline definition of fib_next and // then call it immediately var error = (n,a,b) => "KABOOM!"; var fib_x = (fib_next => fib_next(fib_next(error))) (fib_step => (n,a,b) => n < 1 ? a : fib_step(n-1,b,a+b)); return { fib_x0: fib_x(0,0,1), fib_x1: fib_x(1,0,1), fib_x2: fib_x(2,0,1) } }
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 returns the error message "KABOOM!". So let's try doing without it.
{ // Attempt 4.1: Remove the error function //var error = (n,a,b) => console.log("KABOOM!"); //var fib_x = (fib_next => fib_next(fib_next(error))) // (fib_step => (n,a,b) => n < 1 ? a : fib_step(n-1,b,a+b)); // This leaves us with a new definition of fib_x in which the error // function is missing var fib_x = (fib_next => fib_next(fib_next)) (fib_step => (n,a,b) => n < 1 ? a : fib_step(n-1,b,a+b)); return { fib_x0 : fib_x(0,0,1), fib_x1 : fib_x(1,0,1), fib_x2 : fib_x(2,0,1) } }
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: 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. Rename all occurences of fib_step to be fib_next, because the same functionality used in both places.
{ // Attempt 4.2: // Pass fib_step a copy of itself. Because fib_step returns a partial, // we can immediately pass this partial the numbers it requires to // perform the calculation we want var fib_x = (fib_next => fib_next(fib_next)) (fib_step => (n,a,b) => n < 1 ? a : fib_step(fib_step)(n-1,b,a+b)); }
{ // Now rename all instances of fib_step to fib_next var fib_x = (fib_next => fib_next(fib_next)) (fib_next => (n,a,b) => n < 1 ? a : fib_next(fib_next)(n-1,b,a+b)); }
Ok, so where does that leave us?
{ var fib_x = (fib_next => fib_next(fib_next)) (fib_next => (n,a,b) => n < 1 ? a : fib_next(fib_next)(n-1,b,a+b)); // Let's try calculating different numbers in the Fibonacci series... return { fib0 : fib_x(0,0,1), fib1 : fib_x(1,0,1), fib2 : fib_x(2,0,1), fib5 : fib_x(5,0,1), fib20 : fib_x(20,0,1), fib50 : fib_x(50,0,1), fib100 : fib_x(100,0,1), fib1474 : fib_x(1476,0,1) } }
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: We have a partial function that receives a parameter called fib_next. (fib_next => fib_next(fib_next)) This partial functions calls whatever function it receives as a parameter and immediately passes that function to itself as a parameter. In other words: Some function is received in parameter fib_next We call this function 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. 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)) 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. 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 mystery function Y we're after. Some refactoring is still needed before this recursive example is what we're actually looking for. This will be the subject of my next blog. Chris W