Tail Call Optimization (TCO) implementation in compile time

[MiniMarvin]

Search Terms

Functional Programming, ES6, Tail Call Optimization, TCO

Suggestion

Would be pretty nice to add a tail call optimization, once present in V8 for NodeJS 7.x, but later removed for some reasons I don't really understand, but about some other performance issues created in the browser. The idea is to create a transpiler to generate the iterative code for some tail-call optimizations, feature already present in Elm for example.

Use Cases

That would allow typescript people to take advantage of some other resources of pure functions without any real worry with StackOverflow from using the functional programming advantages.
The current approach in Typescript is not to use it, use iterative loops or even model the problem such a way that will never impact the code but is a huge problem for people trying to make the code more functional. There's already some implementation of it in some more functional transpilers for JS like Elm and is pretty useful in order to make functions modeling in an easier way.

Examples

Once a programmer code something like:

function fact (x: number, acc: number): number {
  if (x === 0) {
    return acc;
  }
  else {
    return fact(x - 1, x*acc);
  }
}

The code generated for javascript would be something like:

function (x, acc) {
  while(true) {
    if(!x) {
      return acc;
    }
    else {
      let t1 = x - 1;
      let t2 = acc * x;
      x = t1;
      acc = t2;
    }
  }
}

[AnyhowStep]

Pretty sure this goes against one of those goals

[jcalz]

Yes, this part of the template has been deleted instead of filled out:

Checklist

My suggestion meets these guidelines:

• This wouldn't be a breaking change in existing TypeScript/JavaScript code
• This wouldn't change the runtime behavior of existing JavaScript code
• This could be implemented without emitting different JS based on the types of the expressions
• This isn't a runtime feature (e.g. library functionality, non-ECMAScript syntax with JavaScript output, etc.)
• This feature would agree with the rest of TypeScript's Design Goals.

The second guideline is quite strikingly unmet here so I'd guess this suggestion will be declined, however desirable such a feature in JS might be.

[MiniMarvin]

Yes, this part of the template has been deleted instead of filled out:

Checklist

My suggestion meets these guidelines:

• This wouldn't be a breaking change in existing TypeScript/JavaScript code
• This wouldn't change the runtime behavior of existing JavaScript code
• This could be implemented without emitting different JS based on the types of the expressions
• This isn't a runtime feature (e.g. library functionality, non-ECMAScript syntax with JavaScript output, etc.)
• This feature would agree with the rest of TypeScript's Design Goals.

The second guideline is quite strikingly unmet here so I'd guess this suggestion will be declined, however desirable such a feature in JS might be.

Oh, about the deletion, I tought this checklist was supposed to orient the author not to be really filled out.

But I don't really see how it would change the runtime behavior of existing javascript code, because the behavior would be pretty much the same right? Could you explain how would it be a different behavior at runtime?

[jcalz]

Hmm, maybe we are interpreting that guideline differently. I think TS operates under the principle that if you are using syntax that works in the targeted version of JS, the output will be produced from the TS as-is. So while one could certainly argue that a = a + 1 could be replaced with a += 1, it would be surprising if TypeScript's compiler just did that for you. Whether that's implied by the guideline hinges on the meaning of the word "behavior" here. TCO is discoverable when debugging code, so I tend to think of this as affecting runtime behavior. But I'm willing to rescind this particular objection.

However, if I look at TypeScript's goals and non-goals, I see that non-goal #2 is:

Aggressively optimize the runtime performance of programs. Instead, emit idiomatic JavaScript code that plays well with the performance characteristics of runtime platforms.

So that applies here, right?

[MartinJohns]

Also:

7. Preserve runtime behavior of all JavaScript code.

[RyanCavanaugh]

I think this is out of scope.

Tail call identification and rewriting can be done syntactically, so could be done at the same phase as minification, obfuscation, module tree shaking, etc., all of which we don't do.

I believe the existing emit pipeline plugin support would allow for a sufficiently motivated person to plug this in if they really wanted it to happen at the same time as the rest of TypeScript compilation.

Anyway 99.999% of JS devs are doing just fine without this feature and the "right" thing to do would be to lobby TC39 to put pressure on runtime authors to properly support something that's already in the ES spec.

[RaoulSchaffranek]

Proper tail call elimination [PCE] is part of the ECMAScript specification, so I don't see how a TypeScript-implementation would violate any of its goals. Furthermore, PCE is not a performance optimization - it's purpose is to prevent stack-growth and stack-overflows.

[jcalz]

Looking back at this, I think I originally wasn't interpreting this as a request for downleveling. Explicitly phrasing it in those terms, you get something like:

Please downlevel proper tail call elimination for ES3 and ES5 (and noncompliant ES2015+ runtime engines, I guess?!)

And then it being declined looks like

Yeah, we could do that, but we don't downlevel absolutely every aspect of every feature, see #14219 or #28756 for example. And given how few runtime engines seem to care about this feature, and the problems they ran into while trying, we're not going to spend the amount of effort it takes just to have the same problems ourselves.

At least that's how I'm seeing it now.