Hello Friends!

How are you doing?

For all those of you who browse hacker news, have you thought what does “Y-Combinator” mean?
I’m sure many of you know, since it’s taught in a computer science curriculum.
However for those of you who don’t know, the Y-Combinator is a an implementation of the fix operator.

The fix operator lets a language which doesn’t support recursion define a recursive function

Well, you may say  ‘do we need the fix operator in javascript?’ -of course not!

Javascript already supports recursion.

However you may find this post interesting: it’s an excuse to dive in further some functional programming topics in a language you may be more familiar with.

Let’s start:

How does one define the Fix operator? The definition can be stated somewhat like this

It takes a function f and returns the result of evaluating that function with itself evaluated with the function as a parameter.

That bold thing above is supper confusing to write and even more so to read.

So how do we understand it?

Maybe it’s better to look at the type definition of Fix:

That rule reads:

If M is a function that takes a parameter of type sigma, and returns a value of type sigma, then evaluating fix with M returns a unique value of type sigma.

What can we infer from this?

1. The fix needs to receive something of type function to work
2. The function passed to fix has to return something of the same type that what it is given as an argument

However… what values can sigma take?

can sigma be a number? Yes!

can sigma be a string? Yes!

can sigma be a function? Bingo! This is the crucial aspect.

We want fix M to return a function, in particular a recursive function.

We want sigma to be of the kind tau -> tau, for a given tau

But that means that M which had type function sigma -> sigma, now types:

M: (tau -> tau) -> (tau -> tau). I added parenthesis for clarity

What can we conclude of this?

If we want fix M to return a function, then M has to take a function as an argument, and return another function as a result.

 

The Operational Semantic of Fix

To reproduce the behaviour of fix in a language like javascript we need to understand how it should be executed.

There are two rules

The first rule

This rule can be interpreted: whatever thing fix takes as an argument, first reduce it to a value.

That is, reduce it until you can’t do it anymore. To give you an idea, a value is a number, a string, a function declaration, etc…

What isn’t a value? a function application, ie: plusOne(3).

The value of that would be 4.

The second rule:

This second rule says: once fix receives a function as an argument, take the body of the function and replace any occurence of the bounded parameter in the function body for the application of fix with the same function.

This second rule is the one which conveys fix’s real meaning.

So let’s do it in javascript:

//First we define M. M should take a function and return a function:
const factorial_step = f => x => x == 0 ? 1 : x * f(x - 1)

// Then we define the fix with everything we said above
const fix = (f) => {
    // We reduce f to a value
    f = eval(f)

    let parts = f.toString().split('=>')

    //We get the name of the bounded variable
    let var_name = parts[0].trim()

    //We get the body of the function
    let M = parts.slice(1).join('=>')

    //We replace the bounded variable, with fix called with the function name
    let bounded_variable = RegExp(var_name, 'g')
    M = M.replace(bounded_variable, 'fix(' + f.name + ')')

    // We evaluate the resulting string and get back the function
    return eval(M)
}

// Then we create the complete factorial function
let factorial = fix(factorial_step)

console.log(factorial(6)) // 720

// Another thing that good to notice is that the factorial function 
// it's not recursive in the sense that it doesn't call itself, see:
console.log(factorial.toString()) // x => x == 0 ? 1 : x * fix(factorial_step)(x - 1)

And with that, we conclude this post!

Please shoot me a message if there is something that wasn’t clear, I’ve just started blogging a little while ago and I’m still working my writing skills.

Also please tell me if you see a mistake somewhere

Hope you like it! 🙂