Editing Recursion
The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 85: | Line 85: | ||
All the examples on this page use tail calls and run in Lua which implements tail call optimization. This means every program on this page is immune to stack overflows. | All the examples on this page use tail calls and run in Lua which implements tail call optimization. This means every program on this page is immune to stack overflows. | ||
The 1977 [https://en.wikisource.org/wiki/Index:AIM-443.djvu AI Lab Memo 443] talks more broadly about how tail calls are like goto statements that you can pass arguments to. Huge | The 1977 [https://en.wikisource.org/wiki/Index:AIM-443.djvu AI Lab Memo 443] talks more broadly about how tail calls are like goto statements that you can pass arguments to. Huge shoutout to the folks at Wikisource that transcribed this to an accessible text form. | ||
The significant downside of tail call optimization from a user perspective is that it can make debugging more difficult as you lack a proper stack trace. | The significant downside of tail call optimization from a user perspective is that it can make debugging more difficult as you lack a proper stack trace. | ||
Line 91: | Line 91: | ||
From an implementer perspective the problem is that stack cleanup is tricky: A function that tail calls another cannot clean up any temporary variables it passes along. The solution to this is to make sure function stack use is identical and have the caller clean up, or to implement garbage collection. | From an implementer perspective the problem is that stack cleanup is tricky: A function that tail calls another cannot clean up any temporary variables it passes along. The solution to this is to make sure function stack use is identical and have the caller clean up, or to implement garbage collection. | ||
== | ==Mainstream support== | ||
Despite languages slowly adding features from functional languages developed 40 years ago, tail call optimization is still unpopular. I'm guessing that the reason is because not many people see the use of recursion. | Despite mainstream languages slowly adding features from functional languages developed 40 years ago, tail call optimization is still unpopular. I'm guessing that the reason is because not many people see the use of recursion. | ||
Here's an incomplete list of languages that support it automatically: | Here's an incomplete list of languages that support it automatically: | ||
Line 127: | Line 127: | ||
* Anything JavaScript or transpiling to JavaScript (TypeScript, CoffeeScript) | * Anything JavaScript or transpiling to JavaScript (TypeScript, CoffeeScript) | ||
Things look decent for desktops, but not so much for phones or web browsers. | Things look decent for desktops, but not so much for phones or web browsers. | ||