The Real Y-Combinator (in JavaScript)
I want to get to this eventually in Naked JavaScript, but for the time being I wanted to share a great little code bit with you in JavaScript. Also given Paul's recent post, I decided it would be good to continue the functional JavaScript by providing a different, way off accomplishing tail call optimization. As I mentioned previously, JavaScript has a strict limit on the call stack of around 1,000 entries (varies based on interpreter implementation) which commonly prevents any level of deep recursion, especially if writing portable JavaScript for multiple browsers. Paul's method of leveraging an accumulator wrapped in a closure is a great method for accomplishing a recursive task in a stack or memory constrained environment. So great in fact that the basic pattern of detecting repetition and translating it to a linear fashion is very similar to the underpinnings of what TraceMonkey automatically accomplishes using Trace Trees.
From Paul's description of the problem at hand, we are trying to find the odds of becoming the next mega-millionare. The following is the imperative solution provided by Paul using a variable to accumulate the odds at any given step in the process as the multiple of the previous value and the new expression result.
Paul presents the conversion of this code segment to a simple recursive function that will help us to find the value of by calling the function over and over with varying values defined within the function until a termination clause is reached. In this case the termination clause is when the variable n equals the value 0.
With the basic code from those two examples and a utility for the spell books of lambda calculus, we can actually create a recursive function and then apply it to the exercise. Mind you that this will still suffer from the aforementioned call stack limitations placed on the JavaScript VM due to its applicative nature, and realistically there are far better ways for obtaining the same result (one of which shown at the end), but to hell with all that.
By using a technique known as Fixed Point Combinator, and specifically a Y-Combinator we will not on obtain the result but build recursion without using a named function. To begin, a Fixed Point Combinator is a special type of higher order function that has the unique transitive property that for any function F and value V, the value of the Y-Combinator function G when passed the parameter F will return the value V which is the same value as when V is passed to F. Lost? Lets look at this description as a the transitive function definition:
F(G(F)) == G(F)
The definition of a combinator relies on the lazy evaluation of functions in order to allow a function to be defined in terms of itself, often times referred to as anonymous recursion. This requires a deep understanding or interest in lambda calculus and this function is deviously complex and compact. For more details about a Y-Combinator, which is a specific formula of a Fixed Point Combinator, look here. Let us look at it as a JavaScript function:
This definition is from The If Works and happens to be one of the most compact, but readable implementations I have seen and it even slips a couple extra JavaScript specific enhancements to make it even more flexible. The definition of this function is near exact to the formulaic definition described in Scheme from the link above with one key advantage. Using the arguments object in combination with the apply function that is available on functions, we can make this more flexible than the one described in The Little JavaScripter by Douglas Crockford by allowing it to handle any number of arguments passed in.
With this definition of a Y-Combinator, let us revise the original problem set using the code from the recursive definition. The most important part that we can take from the recursive definition is the conditional logic, in fact that is all we will be taking. The Y-Combinator version of this looks like this:
Which looks similar to the recursive definition and it really should, because all we have done is create recursion using anonymous functions instead of named functions. As I said earlier, this method is most likely not going to win you fame or fortune (but if it does I claim 5% of the winnings), it is however a great example of the functional capabilities of the JavaScript programming language. All that said, here is probably the most terse definition of this function I could devise:
