Strict, Lazy, and Hoisting – A Closer Look at Some Things to do with Y

The gist that I mentioned in yesterday’s entry on Y had an interesting little snippet on the way to getting to Y:

y = (fnGenerator) ->
  fakeFn = (arg) -> realFn(arg)
  realFn = fnGenerator(fakeFn)
  realFn

It’s a pretty explicit implementation of some of the ideas from that post. To recap, Y is a combinator that implements recursion. Being a combinator means that it can’t refer to anything bound outside its scope in its definition – in particular, it can’t refer to itself. This one meets the definition, since fnGenerator is a bound argument and all other variables are defined in the body. Y works by taking a single-argument function that returns a function. The single argument is the recursive component – i.e. the function in question is only not recursive because it takes its continuation ("what to do next") as an argument. This function then returns another function that takes the actual input. So, for factorial:

notyetrecursivefactorial = (f) ->
  (n) ->
    if n is 0
      1
    else
      n * f(n-1)

notyetrecursivefactorial is just a regular factorial function with the continuation (recursive component) abstracted out into an argument.

The idea is that the definition of Y given above can take it as an argument and return an actually recursive factorial function. Does it?

console.log y(notyetrecursivefactorial)(5)

I get 120, so it seems to work.

But that’s not really the point. The point is that this gives us a good chance to look more closely at somethign that might’ve been confusing yesterday (at least, is always a little confusing for me) – when various definitions are resolved in Coffeescript and why this means we can’t use the straightforward mathematical definition of Y.

So, if we expand this, fnGenerator will be replaced with notyetrecursivefactorial:

(y notyetrecursivefactorial) = 
  fakeFn = (arg) -> realFn(arg)
  realFn = notyetrecursivefactorial(fakeFn)
  realFn

And notyetrecursivefactorial expands to:

(y notyetrecursivefactorial) = 
  fakeFn = (arg) -> realFn(arg)
  realFn = (n) ->
    if n is 0
      1
    else
      n * fakeFn(n - 1)
  realFn

The interesting part is the next bit. It’s obvious that for this to have worked – which we know it does – that the expansion must’ve been something like:

(y notyetrecursivefactorial) = 
  realFn = (n) ->
    if n is 0
      1
    else
      n * ((arg) -> realFn(arg))(n - 1)
  realFn

And that indeed looks correct. We have a recursive function created by our Y function based on the definition of the function we passed it, and it returns that function so that we can use it whereever. Great!

It’s instructive, though, on how Javascript/Coffeescript variables get expanded. Because if everything were defined in order at runtime, you’d really expect it to choke on the definition of fakeFn since, after all, fakeFn depends on realFn, but realFn isn’t defined until after fakeFn is defined! Nor is this any Coffeescript magic at work. Coffeescript lifts all variable definitions to variable declarations at the top of their scope in the compiled Javascript. So, the definition of y we end up with in Javascript after running it through the transpiler is:

y = function(fnGenerator) {
  var fakeFn, realFn;
  fakeFn = function(arg) {
    return realFn(arg);
  };
  realFn = fnGenerator(fakeFn);
  return realFn;
};

So, at the time fakeFn is defited, realFn isn’t yet. And you can prove this to yourself by sticking in a call to fakeFn right after it’s defined but before realFn is:

y = function(fnGenerator) {
  var fakeFn, realFn;
  fakeFn = function(arg) {
    return realFn(arg);
  };
  fakeFn(5);
  realFn = fnGenerator(fakeFn);
  return realFn;
};

console.log( y(notyetrecursivefactorial)(5));

And you get the predictable error:

TypeError: undefined is not a function

The answer is straightforward, of course: variables are only looked up when they’re needed, and realFn isn’t needed until the body of fakeFn is evaluated, which doesn’t happen until fnGenerator is invoked, by which point realFn has a definition.

And it’s not Coffeescript magic, because hoisting the declarations to the top of their scope isn’t even necessary to make this work – it’s just a feature of Javascript. The following code gets the right result:

y = function(fnGenerator) {
  var fakeFn = function(arg) {
    return realFn(arg);
  };
  var realFn = fnGenerator(fakeFn);
  return realFn;
};

console.log( y(notyetrecursivefactorial)(5));

Knowing that variable values are looked up when needed is a good thing to know, but not a big revelation. The take-home point is just to remind yourself that this is why, in a (strict) language like Javascript/Coffeescript (but not a lazy language like Haskell), we have to pass the fnGenerator component of Y a single function – since this is a value and not an expression. If it were an expression, as in the more canonical definition of Y:

y = (f) ->
  ((x) -> f(x x))((x) -> f(x x))

where what gets passed to f (i.e. fnGenerator) is an expression ((x x)), Coffeescript will try to evaluate it right there, and it won’t work because the expansion continues forever. It’s NOT – and this is a subtle difference – because x isn’t defined yet. x IS defined. The problem is that it’s only ever looked up as a function invokation that is necessary to resolve an argument to another function invokation, and it’s defined in such a way that that operation never terminates. In the definition given above, though – the one with fakeFn and realFn – the x analogue is defined in a way that can be expanded as far as needed to get to the next step (because it is in the body of a function that doesn’t need to be invoked to resolve the argument it’s being passed as). And that makes all the difference.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>