Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add tail recursion optimization #29

Closed
DartBot opened this issue Oct 10, 2011 · 24 comments

Comments

@DartBot
Copy link

commented Oct 10, 2011

This issue was originally filed by paulp...@gmail.com


Tailrec optimization is a well-known feature of functional languages.

I propose to add support for it in dart.

@DartBot

This comment has been minimized.

Copy link
Author

commented Oct 11, 2011

This comment was originally written by mprz1024@gmail.com


I think this is one of the most important features Dart is missing. Tail call elimination, or a subset of this functionality — tail recursion elimination — supports the implementation of certain algorithms in a recursive way that is easier to think for some programmers (especially those coming from mathemathical or more formal computing science background) and allows for the implementation of parts of programs without side effects, which has been proven to be less error-prone. It's a feature from many functional programming languages we would love to have in Dart.

Please note that this feature hurts no one: people without the understanding of it will simply not benefit from it, but it will not make their lives harder.

@dgrove

This comment has been minimized.

Copy link
Member

commented Oct 11, 2011

Removed Type-Defect label.
Added Type-Enhancement, Area-Language labels.

@DartBot

This comment has been minimized.

Copy link
Author

commented Oct 11, 2011

This comment was originally written by drfibonacci@google.com


Added Triaged label.

@gbracha

This comment has been minimized.

Copy link
Contributor

commented Oct 12, 2011

Tail recursion elimination needs to be balanced against issues like debugging. There are ways to do this, and maybe at some point we will do something, but honestly, it won't be very soon, if ever.

@gbracha

This comment has been minimized.

Copy link
Contributor

commented Oct 12, 2011

Set owner to @gbracha.

@floitschG

This comment has been minimized.

Copy link
Contributor

commented Oct 12, 2011

Just to comment on the "this feature hurts no one". Aside from the common debug arguments there is (or can be) also a runtime cost associated with them. Tail call optimization precludes some calling-conventions (which a VM normally can chose freely). I would compare it to disallowing --fomit-frame-pointer for gcc.

@DartBot

This comment has been minimized.

Copy link
Author

commented Oct 24, 2011

This comment was originally written by martin.elsman...@gmail.com


I would suggest adding tail-call optimization support quickly. For programming with continuations and other advanced control operators, tail-call optimization is essential. Tail-call optimization is also necessary for programming in a functional style using tail-recursion. Finally, DART could take off quickly as a target language for compilers for functional language compilers such as Hop, SMLtoJs, AFAX, and Links, to name just a few.

@polux

This comment has been minimized.

Copy link
Member

commented Oct 26, 2011

Let me just stress that with popular frameworks like Node.js who rely heavily on a continuation passing style, the tail call optimization does seem more than relevant.

@larsbak

This comment has been minimized.

Copy link

commented Oct 26, 2011

An important goal of Dart is ensuring we can generate efficient JavaScript code.
Adding tail-call optimizations or non-local-returns for that matter will deviate from this goal.
If you want to use Dart as a target language, one option is apply inlining and generating large methods will label jumps. This is no different from using Java or JavaScript.

@DartBot

This comment has been minimized.

Copy link
Author

commented Mar 16, 2012

This comment was originally written by LuoZhongYao...@gmail.com


This is a Bug?
main(){
   int a;
   print(a is num);
}

Run retunr is false.

@ghost

This comment has been minimized.

Copy link

commented Mar 16, 2012

main(){
   int a;
   print(a is num); // Prints false
}

This is not a bug. 'a' is initialized to null and (null is num) returns false.

(Please file a new issue for different bug reports)

@anders-sandholm

This comment has been minimized.

Copy link
Contributor

commented Apr 30, 2012

Added apr30-triage label.

@anders-sandholm

This comment has been minimized.

Copy link
Contributor

commented May 1, 2012

Removed apr30-triage label.

@anders-sandholm

This comment has been minimized.

Copy link
Contributor

commented May 1, 2012

Added triage1 label.

@anders-sandholm

This comment has been minimized.

Copy link
Contributor

commented May 2, 2012

Added this to the Later milestone.
Removed triage1 label.

@kasperl

This comment has been minimized.

Copy link
Contributor

commented Jul 10, 2014

Removed this from the Later milestone.
Added Oldschool-Milestone-Later label.

@kasperl

This comment has been minimized.

Copy link
Contributor

commented Aug 4, 2014

Removed Oldschool-Milestone-Later label.

@gbracha

This comment has been minimized.

Copy link
Contributor

commented Aug 27, 2014

It is unlikely that anything will happen on this front unless JS implements it reliably on all browsers. Even then there are interesting issues. See

http://gbracha.blogspot.com/2009/12/chased-by-ones-own-tail.html


Added Accepted label.

@DartBot

This comment has been minimized.

Copy link
Author

commented Dec 21, 2014

This comment was originally written by lessmem...@gmail.com


As I understand no changes happened with this case?

@truongsinh

This comment has been minimized.

Copy link

commented Apr 19, 2019

Since the Dart VM will not be going into browsers, tail-call elimination is no longer a compelling feature to enable functional languages on the web.

What about now, when Dart is used for Flutter?

@munificent

This comment has been minimized.

Copy link
Member

commented Apr 19, 2019

We still strongly support Dart on the web, so we still need to be able to target JS which does not reliably do tail call elimination.

@truongsinh

This comment has been minimized.

Copy link

commented Apr 20, 2019

We still strongly support Dart on the web, so we still need to be able to target JS which does not reliably do tail call elimination.

Hopefully Dart will have equal or better support for Flutter soon (I mean generally, not only specific to tail call elimination), if not on VM then at least on AOT first.

For more information, both Swift and Kotlin support TCO. In Kotlin case, it supports compile to multiple targets, but TCO is available in VM only (i.e. not JS), ref

Currently tail recursion is only supported in the JVM backend.

Furthermore, ES6 seems to support TCO

@munificent

This comment has been minimized.

Copy link
Member

commented Apr 22, 2019

Hopefully Dart will have equal or better support for Flutter soon (I mean generally, not only specific to tail call elimination), if not on VM then at least on AOT first.

One of the value propositions for Dart is that users can share code and libraries across platforms. If we only support TCO on the VM, then any library that relies on that can't be used on the web. That's a very large downside for a feature that doesn't actually add much value. Most code that you can write using TCO can usually trivially be converted to equivalent code using a loop.

Compatibility provides more real value than TCO does.

In Kotlin case, it supports compile to multiple targets, but TCO is available in VM only (i.e. not JS)

Even then, it only supports TCO on explicitly-marked singly-recursive functions. In other words, the ones that the compiler can transform into loops. Those are the exact cases where a user could write the loop themselves without any real loss in expressiveness.

Furthermore, ES6 seems to support TCO

Almost no JS implementations actually support it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
You can’t perform that action at this time.