Refactoring Towards the Y Combinator: Part 4

This is a multi-part series. Part 1. Part 2. Part 3. Part 4. Part 5. Part 6.

I finished the previous post with the following code:

public delegate T SelfApplicable<T>(SelfApplicable<T> self);

public class Solution05 : ISolution
{
    public Factorial MakeFactorialFunction()
    {
        SelfApplicable<Factorial> factorial = (SelfApplicable<Factorial> self) => 
        {
            return (int x) =>
            {
                return x < 2 ? 1 : x * self(self)(x - 1);
            };
        };
        
        return factorial(factorial);
    }
}

The next step, as I mentioned previously, is to attempt to remove the self(self) business from the factorial algorithm. The self calling aspect is really a technical concern, while the algorithm is more like business logic – it makes sense to want to separate the two. To do this, I’m going to apply a variation on the Extract Method refactoring. I’ll define the factorial algorithm using a new RecursiveFactorial delegate, and let the existing factorial function call it:

public delegate int RecursiveFactorial(int x, Factorial f);

/// <summary>
/// Lets try to seperate the algorithm definition for factorial from the infrastructure that is applying the recursion.
/// I extract the bit that calculates the factorial as a seperate function, and call it "algorithm". The existing factorial function now calls
/// the algorithm, applying itself to itself as it does.
/// </summary>
public class Solution06 : ISolution
{        
    public Factorial MakeFactorialFunction()
    {
        RecursiveFactorial algorithm = (int x, Factorial f) =>
        {
            return x < 2 ? 1 : x * f(x - 1);
        };

        SelfApplicable<Factorial> factorial = (SelfApplicable<Factorial> self) =>
        {
            return (int x) =>
            {
                return algorithm(x, self(self));
            };
        };

        return factorial(factorial);
    }
}

If you compare the two versions, you should be able to see that I have replaced the “return x < 2…” line of code with a call to “algorithm”, but I left the self(self) part where it was. The two concerns are seperated. But the RecursiveFactorial delegate should look familiar to you. Its sort of like my old friend, the SelfCallingFactorial, except it doesn’t seem to call itself, it just calls the factorial function you pass it. The funny thing is that it IS calling itself. Suprised? Perhaps I can help..

At the last line of the function, I return the result of evaluating the factorial function, passing in itself as an argument. I will try to expand this out by performing substitutions:

           
            // Redefine factorial to use more compact syntax.
            factorial = self => x => algorithm(self(self))(x);

            // This is the line of code to expand.
            return factorial(factorial);

            // Substitute the body of factorial in, replacing the self parameter with factorial
            return x => algorithm(factorial(factorial))(x);            

            // If you look inside, you can see that the line we just substituted has another factorial(factorial). Lets substitute that one too.
            // I will have to rename the integer parameter when I do so, to avoid a clash. I'll call it x1.
            return x => algorithm(x1 => algorithm(factorial(factorial))(x1))(x);

            // Whoops! That pesky factorial(factorial) has appeared again! Substitute, substitute!
            return x => algorithm(x1 => algorithm(x2 => algorithm(factorial(factorial))(x2))(x1))(x);

            // Is there no end in sight?

No, there is not. Doing it this way, it looks like I am stuck in some sort of infinite loop, but this is because I’ve expanded the code incorrectly. The first few substitutions are fine – its when I attempted to expand this line that I made a mistake:

return x => algorithm(x1 => algorithm(factorial(factorial))(x1))(x);

The point to notice about this line is that the factorial(factorial) is inside the body of a lambda, being passed as an argument. It will only be evaluated if x is >= 2. If I called the function this line returns with the argument of 1, then that factorial(factorial) part will never be called. I would like to show you the correct expansion of this line but I struggled to get an expansion that compiled properly. Perhaps it would suffice to say that the next step would be to expand the algorithm call, rather than the factorial call.  Hopefully this expansion discussion has illuminated the self calling nature of the solution, but also explained how an infinite loop is avoided.

Getting back on track, the reason why I pointed out that RecursiveFactorial bares some resemblance to SelfCallingFactorial is because I intend to repeat an operation I performed in part 3; I want to apply the currying technique to ‘algorithm’. I will define yet another delegate to represent the curried version of algorithm and call it HigherOrderFactorial. Why “higher order”? Because the curried version accepts a Factorial function and returns a Factorial function –  it operates on functions rather than operating on integers:

public delegate Factorial HigherOrderFactorial(Factorial factorial);

/// <summary>
/// Apply the currying techinque again, this time to algorithm, we arrive at a higher order function. 
/// Now algorithm takes a factorial function, and returns a factorial function.
/// </summary>
public class Solution07 : ISolution
{        
    public Factorial MakeFactorialFunction()
    {
        HigherOrderFactorial algorithm = (Factorial f) =>
        {
            return (int x) =>
                {
                    return x < 2 ? 1 : x * f(x - 1);
                };
        };

        SelfApplicable<Factorial> factorial = (SelfApplicable<Factorial> self) =>
        {
            return (int x) =>
            {
                return algorithm(self(self))(x);
            };
        };

        return factorial(factorial);
    }
}

If you take a look at the changes made to ‘algorithm’ in this step, you will see that they are really quite similar to the changes made in Part 3, where the factorial function was curried. Of course, when I modified the signature of ‘algorithm’, I also had to modify the call to it:

This should be really familiar. Go back and reread part 3 if you are not comfortable with this transformation.

The next step is to address the fact that ‘algorithm’ is a captured variable inside the factorial closure. It would be better to pass in the algorithm as an argument to the factorial function. I will tackle this in the next post.