TCO

[jashkenas]

6to5 just landed a JavaScript TCO implementation. Investigate?

babel/babel#714

[archaeron]

just came to see if there was already an Issue with this and here I see it 👍

[raganwald]

An observation:

Full TCO has some trade-offs. There are lots of functions that make calls in tail position but are not tail-recursive. If CoffeeScript adopts TCO, then all of these functions have to be trampolined just in case one of them is used in a co-recursive set of functions.

This comes up with function decorators:

maybe = (fn) =>
  (args...) ->
    if nullish = args.find((x) -> x == null)
      nullish
    else
      fn.apply(this, args)

The expression maybe((a) -> a.length) returns a function that makes a tail call, and has to be trampolined. But of course, this means that every single use of maybe will incur the overhead of trampolining, even though few (if any) will actually be involved in co-recursive function calls.

There is also the It's just JavaScript issue. A trampolined version of maybe is not going to retain the simplicity of CoffeeScript's usual generated code. That may surprise some people, especially if they have no idea what a trampoline is or why they should care.

There is a simpler way. If CoffeeScript were to adopt some kind of syntax or convention for named functions, then the special case of tail-recursion could be optimized into a loop. For example, foo = () -> "SNAFU" is translated into:

var foo;

foo = function() {
  return "SNAFU";
};

If this special case of binding a function literal to a name were translated into a named function expression, it would look like this:

var foo;

foo = function foo() {
  return "SNAFU";
};

If CoffeeScript always did this, there would be some semantic changes for the edge case of a function that calls itself and the name is rebound dynamically. If it is necessary to preserve that behaviour (I'd argue it is not), then the compiler could do some analysis and only name functions when teh name does not appear to be rebound.

Either way, if we end up with a named function, we can rewrite tail-recursive functions into loops. Here's what 6to5.org is doing right now with that:

function even (n) {
  return n === 0 ? true : n === 1 ? false : even(n - 2);
}

Becomes:

function even(n) {
  var _arguments = arguments,
      _this = this,
      _shouldContinue,
      _result;
  do {
    _shouldContinue = false;
    _result = (function (n) {
      if (n === 0) {
        return true;
      } else if (n === 1) {
        return false;
      } else {
        _arguments = [n - 2];
        _this = undefined;
        return _shouldContinue = true;
      }
    }).apply(_this, _arguments);
  } while (_shouldContinue);
  return _result;
}

Optimizing just tail-recursion is much less ambitious that optimizing all tail-calls, but it is the common case people think of, and I believe it would be much less surprising than finding trampolines for all sorts of ordinary functions that are unlikely to be used in co-recursive functions.

[raganwald]

Update:

After investigation, 6to5 appears to have reverted to optimizing for tail-recursion only.

[vendethiel]

Tailbrush does something like that for any js code, IIRC.

[michaelficarra]

puffnfresh/brushtail

[vendethiel]

Whoops, I got the name backwards indeed - thanks @michaelficarra

[epidemian]

I think a sane first approach for TCO in CoffeeScript could be to make sure that function calls that are in tail position in CS compile to function calls in tail position in JS. I can't think of a case where the CS compiler transforms a tail call in CS to a non-tail-call in JS, but we might want to formalize what "tail position" actually means in CS (something akin to this), and have some tests for that.

That way, the code generated by CS could run with proper tail calls on environments that support them†, and the generated code will still have the "it's just JS" feel to it.

†: Which right now would be none, except for 6to5 which only applies TCO in the simplest case: self-recursive functions.

[raganwald]

I think a sane first approach for TCO in CoffeeScript could be to make sure that function calls that are in tail position in CS compile to function calls in tail position in JS

I'd call that the absolute no-negotiation minimum. As in, if I wrote a tail-calling function in CoffeeScript and it didn't compile into a tail-calling function, I'd file a bug. It is, as they say "just JavaScript," and if JavaScript is evolving such that making tail calls is semantically significant, CoffeeScript should co-evolve to respect that.

After that, I'd say that emulating 6to5 is a good idea. There are people evaluating whether to code for ES-6 and use a transpiler+shims, or whether to use CoffeeScript. No one little thing like this will sway people, but over time a preponderance of features could tilt someone's decision. Adopting yield was a fantastic call. I suspect this is very much in the same vein, another signal to the community that CoffeeScript is progressing and not falling behind ES-6.

[epidemian]

@raganwald, i agree. But i can't see a way in which CS could support proper tail calls without compiling every tail call to something performance horrific.

Even if it applied TCO to only self-recursive functions, like 6to5 does, the performance penalty for current browsers would be too high. A jsPerf comparing a recursive factorial function to the 6to5 TCO output: http://jsperf.com/6to5-factorial-tco. The numbers on my machine, in ops/sec:

	Vanilla	6to5 TCO
Firefox	6,435,022	156,692
Chrome	2,611,722	17,792

That's between 1 and 2 orders of magnitude slower when applying 6to5's TCO. I wouldn't like to see that kind of transformation happily applied by the CS compiler.

Now, i really really wish that we can rely on JS having proper tail calls soon. I think it is ridiculous that in a high level language, where you normally don't have to make the distinction between heap-allocated and stack-allocated things, the runtime chokes if you exceed a meager limit of a couple thousand stacked function calls, when, on the same hardware, you can easily have data structures of millions of elements. (Proper tail calls would not remedy this stupid limit for all function calls, but at least for some of them they would provide a saner escape mechanism than transforming code to imperative loops.)

I just think that, in order for TCO to gain some adoption in real JS code, it mustn't have such an enormous performance penalty. And the only way i see that penalty going away is having TCO implemented in JS engines themselves, which i hope will be sooner than later once ES6 is finalized 😺

[sebmck]

@epidemian See babel/babel#736, @RReverser has managed to improve it's performance signifcantly. See this jsperf suite.

It's a bit more complicated than brushtail as it doesn't look like brushtail preserves arguments and this.

[raganwald]

@epidemian:

That's between 1 and 2 orders of magnitude slower when applying 6to5's TCO

I wonder if it's because they are creating an IIFE on every execution of their loop? I imagine they are trying to preserve arguments and this, but surely that can be avoided for a number of common cases. Rewriting fat arrows comes to mind.

[sebmck]

@raganwald Yep, it was the easier way to implement it at the time.

I just created a new jsperf suite containing @epidemian's recursive factorial function with the new output in the PR I linked. It's available here. Performance is on par with the original and sometimes actually faster depending the browser.

[raganwald]

Ok, naïve suggestion:

function factTco(n) {
  function f(n, acc) {
    var _arguments = arguments,
        _this = this,
        _shouldContinue,
        _result,
        _worker_fn = function (n, acc) {
                if (n === 0) {
                  return acc;
                } else {
                  _arguments = [n - 1, acc * n];
                  _this = undefined;
                  return _shouldContinue = true;
                }
              };
    do {
      _shouldContinue = false;
      _result = _worker_fn.apply(_this, _arguments);
    } while (_shouldContinue);
    return _result;
  }
  return f(n, 1);
}

[sebmck]

@raganwald If you're going to go through the effort of remapping arguments and this then you may as well go the whole nine yards and transform it into:

function factTco(n) {
  function f(_x, _x2) {
    _function: while (true) {
      var n = _x,
          acc = _x2;
      if (n === 0) {
        return acc;
      } else {
        _x = n - 1;
        _x2 = acc * n;
        continue _function;
      }
    }
  }
  return f(n, 1);
}

[raganwald]

@sebmck:

I was just taking 6to5.org's existing transformation and hoisting the IIFE so that it wouldn't create a new function on each iteration of the loop. I'm about to test it to see whether that is, as I conjectured, the source of the expensive runtime cost.

[sebmck]

@raganwald Partially. Firefox is the only engine that's smart enough not to create the IIFE on each iteration. I've already made that change in the commit babel/babel@ee5cb8d, it'll available in the next patch release, that's if the new implementation doesn't land before then.

[sebmck]

Does CoffeeScript even have support for doing these complex transformations anyway? I'm not aware of any feature where similar behaviour occurs.

[epidemian]

@sebmck Wow! Thanks for the pointer. That performance boost is phenomenal!

👏 🎉 @RReverser

In Firefox the TCO code actually beats the recursive form manifold! 😺

So, in conclusion, forget everything i said in my previous message! (except the part about the browsers' couple-thousand call stack limit being too low...). Compiling to TCO for self-recursive functions in not only viable: it can even put to shame the equivalent recursive form in terms of performance (without mentioning it won't have that low stack limit, which is the whole point of TCO in the first place).

Should CoffeeScript implement TCO in a similar way? I now think it would be nice if it did; if only for having self-recursive functions that don't die with low numbers of recursive calls.

Cheers! 🍻

Side note: i was setting up 6to5 locally to update the code in the jsPerf with the changes from that PR, but it was taking forever to download all dependencies. So thanks @sebmck also for saving me some time!

[jashkenas]

After investigation, 6to5 appears to have reverted to optimizing for tail-recursion only.

Why?

[lydell]

Doesn't it work to run the CoffeeScript output JS through 6to5?

[michaelficarra]

@lydell: It should.

[lydell]

If so, why bother?

[raganwald]

@lydell:

Doesn't it work to run the CoffeeScript output JS through 6to5?
If so, why bother?

If the proposition to developers is, “For tail recursion optimization, put CoffeeScript and 6to5 in your tool chain,” I think developers will say, “If 6to5 gives me fat arrows, iterators, let, const, and tail recursion, I will just use that, I don’t need two transpilation tools.”

Of course, once JavaScript engines natively optimize tail recursion and hopefully full TCO, that’s another story, CoffeeScript can omit the optimization without asking developers to add another tool with overlapping benefits.

JM2C, YMMV, &c.

[RReverser]

Why?

@jashkenas Because figured out that implementation was actually incomplete and there is too much cases where it requires more advanced analysis with value tracking. Also, even where it worked, it wrapped function call with own helper and so engine became unable to optimize / inline it, and this overhead made performance much, much worse than with regular call.

As for recursion, this doesn't happen and performance benefit is clear while covering most common use-cases for TCO.

[lydell]

I don’t need two transpilation tools..

I thought people already used several transpilation tools: JS dialect, linter, module whatever-it-is-called, things like groundskeeper, minifier. IMO, asking CoffeeScript to do TCO is like asking it to output minified JS.

[jashkenas]

A couple of brief points:

• TCO is a language semantics change. It's something that would change the nature of CoffeeScript, and how you write it, and the mutual compatibility of one CoffeeScript file interacting with another. It's something that the language should either intentionally do, or not do.
• If the 6to5 implementation is incomplete, and can't handle TCO with more than one function involved, then this ticket is premature. Adding TCO for only directly tail-recursive cases — and this is not a criticism, things are clearly still being worked on — would be half-assed.

[RReverser]

@jashkenas Not all the features can be transparently (and in a fast way) done from the transpiler/compiler side unless you eventually reinvent VM. Tail call optimization is one of those.

[raganwald]

If the 6to5 implementation is incomplete, and can't handle TCO with more than one function involved, then this ticket is premature. Adding TCO for only directly tail-recursive cases — and this is not a criticism, things are clearly still being worked on — would be half-assed.

I dont’ know if it would be half-assed, but I certainly can agree with the sentiment that CoffeeScript does not need to do anything until there is a “competitor” that performs TCO. I think it makes sense to monitor their progress.

[raganwald]

I thought people already used several transpilation tools

Ok, two semantic transpilation tools. ;-)

[RReverser]

@raganwald

CoffeeScript does not need to do anything until there is a “competitor” that performs TCO. I think it makes sense to monitor their progress.

Umm, don't get me wrong, but why waiting for another tool to implement some feature and then copy implementation as part of own feature set instead of trying to implement it on your own? 😉

[jashkenas]

Not all the features can be transparently (and in a fast way) done from the transpiler/compiler side unless you eventually reinvent VM. Tail call optimization is one of those.

Indeed. If that's in fact the case here, then we should just wait until the engines actually do it.

but I certainly can agree with the sentiment that CoffeeScript does not need to do anything until there is a “competitor” that performs TCO.

That's not what I'm saying ;) For any feature or potential feature in CoffeeScript, if it's a good idea and can be implemented — we should do it. If it's not a good idea for CoffeeScript, we shouldn't. Competition has nothing to do with it.

Umm, don't get me wrong, but why waiting for another tool to implement some feature and then copy implementation as part of own feature set instead of trying to implement it on your own?

Quite.

[RReverser]

Quite.

Well, I had to ask as it looks like there is some underestimation of efforts involved in investigations and performant implementation of TCO in 6to5, and "makes sense to montior their progress" just to take feature when it's completely implemented doesn't feel right.

[raganwald]

Progress in languages happens on two fronts. First, languages have their own unique character, and they innovate along those lines. Second, features are “borrowed” from other languages the way natural languages acquire idioms and loanwords.

If feature X is core to CoffeeScript’s philosophy, of course CoffeeScript should pursue it independently. And if feature X runs counter to CoffeeScript’s philosophy, then it simply shouldn’t be done. But in between those two extremes are lots of features that aren’t core, but aren’t harmful either.

Taking demand from users and the implementation progress of other languages into account is perfectly normal for features that aren’t deemed to be part of the core vision. JavaScript did that with CoffeeScript’s arrows, where is the moral conundrum in CoffeeScript doing that with transpiling TCO?

And no, I never said copy anybody’s implementation.

[RReverser]

where is the moral conundrum in CoffeeScript doing that with transpiling TCO

I'm not saying TCO should not be implemented in CoffeeScript (while it's still rather engine-level feature, but nevermind) - I'm just saying that doing own investigations and helping to implement solution for proper cross-function and cross-file TCO would be much more helpful for both sides than just monitoring progress in another project.

[raganwald]

I'm just saying that doing own investigations and helping to implement solution for proper cross-function and cross-file TCO would be much more helpful for both sides than just monitoring progress in another project.

I as just writing out another comment along these lines. I am also against a knee-jerk snarfing of 6to5’s strategy. CoffeeScript is its own language, and there is an opportunity to step back and solve the underlying problem rather than copy JS’s solution to the problem.

Comprehensions are a good example of this. Python and CoffeeScript have a completely different way to make working with collections less painful. It could be that there is a completely different way to make co-recursive functions less painful, or to make function decorators faster.

So... No I am not suggesting that CoffeeScript copy 6to5 or EcmaScript-6 (or whatever they’re calling it).

[GeoffreyBooth]

I don’t really see a concrete proposal here that can be acted upon. If someone wants to propose a specific implementation for tail call optimization (or related) in CoffeeScript, please create a new issue and we can discuss it.

[lydell]

Also note that ES2015 has native tail call optimization.