Fixed-point Combinator - Explanation For Imperative Programmers

Explanation For Imperative Programmers

In most imperative programming languages (C, C++, Java, BASIC, ...), it is easy to write a recursive function because the function can call itself directly. So, the factorial function might look like:

factorial(integer n) { if n=0 then return 1; else return n * factorial(n-1); --- recursive call to factorial }

In some languages, a direct recursive call is not allowed. In these languages, functions are values and the value for the function "factorial" hasn't been assigned yet at the time the recursive call would be made. (The value isn't assigned to the name until the end of the function's definition has been reached.)

How is a recursive function written in these languages? It is done by breaking the function into two parts. The first part looks very similar to the recursive version of the function. The difference is that it takes a function as a parameter and calls that parameter instead of calling itself recursively. (Remember, functions are values so they can be passed as arguments to functions. This isn't often done in imperative programming.)

factorial_helper(function foo, integer n) { --- added function as a parameter if n=0 then return 1; else return n * foo(n-1); --- recursive call replaced with call to parameter }

Now, if that function parameter was "factorial", then this helper function would calculate the factorial. So, the second part of building the recursive function is to create a function "factorial" and set it equal to "factorial_helper" with "factorial" as the first parameter.

factorial(integer n) { factorial_helper(factorial, n) --- "factorial" is passed as the function parameter }

This doesn't quite work because we've run into the same problem as before: the function "factorial" is using its value before we get to the end of its definition. The fixed-point function solves this for us. Due to its special structure, it is able to call "factorial_helper" recursively without using a value before it is defined. The fixed point function takes the helper as an argument and returns the recursive function. (Remember functions are values - they can be passed as arguments and returned by functions.)

factorial = fixed_point(factorial_helper)

It is difficult and confusing to try to write fixed_point in imperative terms, so we will not attempt it.

Why is the fixed point function so important? Most languages allow recursive functions to be declared directly, but that only works with functions that have names. Languages that have functions-as-values usually allow the programmer to declare functions without names or to compose existing functions. (The "fixed_point" function is an example of a function that composes existing functions!) Since these functions don't have names, it is impossible to call them recursively. In those cases, the fixed point operator allows the programmer to build "anonymous" recursive functions.

It is also important for theoretic languages, where direct recursive calls might be considered "less pure" or a redundant (and therefore unrequired) feature.