No Tail Call Optimisation

[Ezirius]

There was a previous issue dart-lang/sdk#29 that was opened in 2011 and subsequently closed without resolution. 9 years later Dart has become so much more than it was 9 years ago, now with Flutter integration and Isolates, and supporting Desktop, Mobile, Back-end, as well as, Web development. Functional Programming has seen a significant resurgence with the Functional Programming style, Immutability, Either and Option types being much more widely used today and no longer just being restricted to traditional Functional Programming languages.

Purely for example purposes, the following illustrates the issue (Examples):

Non-tail Recursion

int sumDownNonTailRecursive({@required int number}) {
  if (number >= 0) {
    print('Non-tail Recursive (Running): Number: $number');
  } else {
    throw 'ERROR: Number must be >= 0';
  }

  if (number == 0) {
    return 0;
  } else {
    return number + sumDownNonTailRecursive(number: number - 1);
  }
}

Tail Recursion

// ! Still no Tail Recursion Optimisation in Dart
int sumDownTailRecursive({@required int total, @required int number}) {
  if (total >= 0 && number >= 0) {
    print('Tail Recursive (Running): Total: $total Number: $number');
  } else {
    throw 'ERROR: Total (0 recommended) and Number must be >= 0';
  }

  if (number == 0) {
    return total;
  } else {
    return sumDownTailRecursive(total: total + number, number: number - 1);
  }
}

Both these functions will equally fill up the Stack and at a non-deterministic point will throw a Stack Overflow exception. However, with Tail Call Optimisation, the latter function should have never had such a Stack impact.

Platform:

• Dart SDK version: 2.10.0-4.0.dev.flutter-0341576448
• macOS

[lrhn]

Tail recursion is a different way to write a loop. Sometimes it's the best way (multiple mutually recursive functions where the one called is chosen at run-time, that's very hard to write as a loop). Other examples are trivial and more readable as loops:

int sumDown(int number) {
  if (number < 0) throw 'ERROR: Number must be >= 0';
  var total = 0;
  while (true)  {
    print(' Loop(Running): Total: $total Number: $number');
    if (number == 0) return total;
    total += number--;
  }
}

Tail call optimization only really works if you can depend on it. If it only works on some platforms, then you can't write a general tail-recursive function and expect it to work, because it might just overflow the stack instead. It's really not an optimization, it's a language feature at the same level as a for loop.

JavaScript does not support TCO/PTC, and likely never will, and it's not really something you can emulate efficiently. That alone is probably reason enough to not add the feature to Dart, since we effectively won't be adding it to Dart if it won't work when compiled to JavaScript. It would be like having for loops not working when compiled to JavaScript - not really an option.

Basically, I'm saying no for the same reasons the original issue was closed. Nothing of importance has changed since then.

[mateusfccp]

@lrhn I does not make much sense for me... Currently, Dart does not support TCO. If I make a recursive function it will be not TCOed both in Dart and in compiled JS.

If you implement TCO for Dart only, nothing will change for JS, but for Dart it will be better than without TCO. JS will be kept as it already is, so there's no negative on implementing for Dart.

Am I missing something?

[lrhn]

We compile Dart to JavaScript, and we can't compile TCO code to JavaScript efficiently until JavaScript also supports TCO.

[Ezirius]

Thanks, @lrhn.

Tail recursion is a different way to write a loop. Sometimes it's the best way (multiple mutually recursive functions where the one called is chosen at run-time, that's very hard to write as a loop). Other examples are trivial and more readable as loops:

In addition to the use case you pointed out above, Dart already embraces the premise that it serves a community of developers with different needs and coding styles/paradigms. Again, purely for example purposes, loops could be used to accomplish .map, .reduce, .where; however, these alternate options are offered to serve the segments of the community that prefer them.

Tail call optimization only really works if you can depend on it. If it only works on some platforms, then you can't write a general tail-recursive function and expect it to work, because it might just overflow the stack instead. It's really not an optimization, it's a language feature at the same level as a for loop.

JavaScript does not support TCO/PTC, and likely never will, and it's not really something you can emulate efficiently. That alone is probably reason enough to not add the feature to Dart, since we effectively won't be adding it to Dart if it won't work when compiled to JavaScript. It would be like having for loops not working when compiled to JavaScript - not really an option.

I still see this as a compiler optimisation, but that's not relevant in relation to the requirement for this capability, nor how it would be best implemented.

When you develop a language that is compiled/transpiled to various platforms/other languages, you will always have to deal with platform/language specific compromises. I'm sure that there are many such compromises in the Dart compiler/language already today.

Dart today is so much more than just the Web. That's why in my prelude to the issue I mentioned that Dart has grown in the last 9 years to be a development language for the Desktop, Mobile, Back-end, as well as, the Web. I'm sure the Dart development team have already or can find a much better approach to improving the Dart language for all these platforms, and not just holding it back by making the Web, or JavaScript for that matter, its lowest common denominator.

The JavaScript Language Specification ECMAScript 6, has already introduced Tail Position Calls into the JavaScript specification.

[mateusfccp]

@lrhn What about you don't? If you can't compile TCO to Javascript, compile it to Dart only. Leave JS without TCO. Is this not possible?

[leafpetersen]

There are (at least) two ways to think about tail call elimination.

One is as strictly an optimization that a compiler can choose to perform or not, in order to improve performance. There is nothing that I know of stopping us from implementing this optimization in any compiler, and if we have good reason to believe that it is worth the implementation effort then I would expect we would do so. This has nothing to do with the language though - it's strictly a compiler optimization, driven by performance considerations.

The other is as a specified part of the cost model of the language. There are a set of languages which implicitly or explicitly define an execution model in which it is expected that if one writes properly tail recursive code, such code will execute in constant space. Programmers may choose to write code in a style which relies on this property, and transpilers may take advantage of this guarantee to implement arbitrary control flow that can't otherwise be expressed efficiently in structured code. The point that @lrhn is making is that relying on such an execution model when writing code is only reasonable if all implementations actually provide the guarantee. Coding patterns that are reasonable on conformant implementations are not reasonable on non-conformant implementations, with the result that code written assuming the TCE cost model is no longer really portable.

So given that TCE cannot be efficiently implemented in javascript, we are unlikely to specify this at the language level. To do so would be to deny the realities of our underlying platforms, one of which simply doesn't support this, and would be a disservice to our users who might reasonably expect that a language which specifies that tail recursive code executes in constant space will in fact execute tail recursive code in constant space on all platforms.

[mateusfccp]

Thanks, @leafpetersen.

[Ezirius]

Thanks @leafpetersen.

One is as strictly an optimization that a compiler can choose to perform or not, in order to improve performance. There is nothing that I know of stopping us from implementing this optimization in any compiler, and if we have good reason to believe that it is worth the implementation effort then I would expect we would do so. This has nothing to do with the language though - it's strictly a compiler optimization, driven by performance considerations.

Yes, thanks, that's in-line with my thinking.

The other is as a specified part of the cost model of the language. There are a set of languages which implicitly or explicitly define an execution model in which it is expected that if one writes properly tail recursive code, such code will execute in constant space. Programmers may choose to write code in a style which relies on this property, and transpilers may take advantage of this guarantee to implement arbitrary control flow that can't otherwise be expressed efficiently in structured code. The point that @lrhn is making is that relying on such an execution model when writing code is only reasonable if all implementations actually provide the guarantee. Coding patterns that are reasonable on conformant implementations are not reasonable on non-conformant implementations, with the result that code written assuming the TCE cost model is no longer really portable.

So given that TCE cannot be efficiently implemented in javascript, we are unlikely to specify this at the language level. To do so would be to deny the realities of our underlying platforms, one of which simply doesn't support this, and would be a disservice to our users who might reasonably expect that a language which specifies that tail recursive code executes in constant space will in fact execute tail recursive code in constant space on all platforms.

In terms of Dart offering such a guarantee, isn't there another approach?

In the words of Guy Steele:

"...in general, procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly coded as [machine code] JUMP instructions."

I propose that TCO is offered as syntactic sugar in the Dart language to serve the segments of the Dart development community that prefer such a coding paradigm/style (please refer to the above in relation to further reasoning in relation to this point).

Thereafter you have at least 2 compiler options:

1. Compile to TCO for all platforms that support it and loops for the platforms that don't, a TCO compiler equivalent; or
2. Compile to loops, for simplicity, for all the platforms, a TCO compiler equivalent

[leafpetersen]

1. and loops for the platforms that don't, a TCO compiler equivalent;

I don't know what you mean by "loops for the platforms that don't". I can write properly tail recursive code which is not expressible as any structured loop whatsoever (e.g. CFGs with irreducible control flow). Such code cannot be implemented in terms of structured loops. Technically, you could probably simulate it by structuring the entire program as one large loop with a switch statement and managing your own stack but that's not a realistic approach.

[Ezirius]

Apologies for accidently closing the issue.

I don't know what you mean by "loops for the platforms that don't". I can write properly tail recursive code which is not expressible as any structured loop whatsoever (e.g. CFGs with irreducible control flow). Such code cannot be implemented in terms of structured loops. Technically, you could probably simulate it by structuring the entire program as one large loop with a switch statement and managing your own stack but that's not a realistic approach.

CFG theory is obviously very important in this design. My understanding is that based on language design one can ensure reducible graphs, and thus provide the previously said guarantees if certain criteria are met. I think that we are now delving into software design, and as interesting as that is, I don't want us to miss the point that this is a feature request. Well, potentially features if we starts delving into the detail and considering the CFGs for the various types of recursions, and obviously the focus can be on the most common Functional Programming use cases with the absence of mutability. Absolutely, in designing this solution one must not compromise such design or performance. My understanding, again, is that TCO can improve some types of recursion performance, depending on implementation.

I don't believe we need to reinvent the wheel, but rather stand on the shoulders of the giants that came before us.

These types of issues have been grappled with for years and numerous solutions have been implemented to work around similar constraints. Looping/Chicken Scheme/ShadowChicken/Trampoline... in various types of recursions. Compiler annotations (no shortage of annotations from the Meta package, but those are discussions for another day) to demarcate expectation so that the compiler can error if the said expectations can't be met. We can also turn to C++ compilers using loops and other TCO strategies, JavaScriptCore/WebKit having implemented ECMAScript 6 Tail Position Calls; Scala, Clojure, Kotlin that have successfully implemented TCOs by working around the JVM having no such support, ....

The point is that I believe that it is feasible to implement successfully, and still have the compatability and the same level of TCO guarantees when transpiling to JavaScript. I also believe that there is a significant segment of the Dart community that would benefit from this language/compiler capability.

Remember, Dart already supports Either and Option through the Dartz package and also completely immutable collections via built_collections. Dart also already embraces the premise that it serves a community of developers with different needs and coding styles/paradigms. For example, loops could be used to accomplish .map, .reduce, .where; however, these alternate options are offered to serve the segments of the community that prefer them.

Let's please add this feature request to the funnel and let's investigate how we can use what these other language/compiler teams have done to also bring this capability to the Dart language.

[mraleph]

We can also turn to C++ compilers using loops and other TCO strategies, JavaScriptCore/WebKit having implemented ECMAScript 6 Tail Position Calls; Scala, Clojure, Kotlin that have successfully implemented TCOs

Note that Kotlin and Clojure all support tail call optimisation for explicit tail recursion rather than arbitrary tail call optimisation, precisely because there is no efficient way to implement it on JVM. Scala silently tries to apply TCO to all eligible functions but that might fail - a @tailrec annotation is provided to make compiler tell you when it fails to perform TCO.

In JavaScript world only WebKit provides TCO as specified by ES6, neither V8 nor SpiderMonkey do - for various reasons. V8 actually shipped an implementation of ES6 tail calls but then unshipped it based on usability concerns (stack frames disappearing from exception stack traces and not-visible in debugger).

Given that JS does not have TCO means that we can't really add portable "silent" TCO to the Dart language (if we were that could lead to libraries appearing that rely on TCO and these libraries becoming silently unusable on the web - unideal).

We could add tail recursion specific TCO - just like Scala and Kotlin. Implementation is rather straightforward. However it is unclear if this is really all that useful: tail recursive functions can be trivially transformed to loops by hand without significant loss of readability (as already demonstrated by @lrhn with your example).

[mateusfccp]

We could add tail recursion specific TCO - just like Scala and Kotlin. Implementation is rather straightforward. However it is unclear if this is really all that useful: tail recursive functions can be trivially transformed to loops by hand without significant loss of readability (as already demonstrated by @lrhn with your example).

Tail recursive functions may be stateless, which means less error-prone. Also, they are usually more readable. So I think it's useful, specially considering that you said that the implementation is straightforward.

[lrhn]

My favorite example of arbitrary recursion which is not easy to unroll as a loop, is this finite machine implementation:

/// Whether string of a's and b's has #a-#b = 0 (mod 3).
bool abMod3(String input, [int index = 0]) {
  while (index < string.length) {
    var char = input[index++];
    if (char == "a") return /*tail*/ ab1Mod3(input, index);
    if (char == "b") return /*tail*/ ab2Mod3(input, index);
  }
  return true;
}

bool ab1Mod3(String input, int index) {
  while (index < string.length) {
    var char = input[index++];
    if (char == "a") return /*tail*/ ab2Mod3(input, index);
    if (char == "b") return /*tail*/ abMod3(input, index);
  }
  return false;
}

bool ab2Mod3(String input, int index) {
  while (index < string.length) {
    var char = input[index++];
    if (char == "a") return /*tail*/ abMod3(input, index);
    if (char == "b") return /*tail*/ ab1Mod3(input, index);
  }
  return false;
}

It's a three-state finite state machine, should be easy, but you can't implement it in JavaScript using loop constructs only.
Good luck getting there with anything but a trampoline loop.

[akshaykmalik]

Tail call optimized way to write this function will be

Int sumDown(int n,int a =1,int b=0){
If(n == 0)
Return b;
SumDown((n-1),a+1,a+b);
}

[OlegAlexander]

I recently came across a similar issue and was able to solve it with the reduce function. I believe @Ezirius's sumDown function can be written this way and still satisfy the requirement of being functional without causing a stack overflow:

int sumDownReduce(int n) =>
    Iterable<int>.generate(n + 1).reduce((total, number) => total + number);

void main() {
  print(sumDownReduce(3)); // 6
}

I agree that tail call optimization would be a nice to have feature, but I understand why we can't have it at the moment. And reduce seems to be a good workaround.

[unicomp23]

Tail calls are about to drop in wasm, right? Stage 4?