[HN Gopher] Recursion, continuations and trampolines (2017)
___________________________________________________________________
Recursion, continuations and trampolines (2017)
Author : signa11
Score : 103 points
Date : 2024-05-24 07:00 UTC (1 days ago)
(HTM) web link (eli.thegreenplace.net)
(TXT) w3m dump (eli.thegreenplace.net)
| dang wrote:
| Discussed at the time (minimally):
|
| _On Recursion, Continuations and Trampolines_ -
| https://news.ycombinator.com/item?id=14087620 - April 2017 (1
| comment)
| fweimer wrote:
| Are there any good heuristics for adding trampolines if the
| underlying architecture does not support tail calls? (With the
| closed-world assumption.) Maybe breadth-first search on the
| callgraph, inserting trampolines at the first circle? And then
| somehow restart and deal with the remaining cycles, until none
| are left?
| odyssey7 wrote:
| > This trick is called tail-call optimization (TCO) [2]. Scheme
| has been doing it since the 1970s - indeed, since Scheme
| encourages programmers to write recursive algorithms, TCO is at
| the core of the language. More modern languages are catching up
| too - Lua supports TCO and JavaScript will too, once ES6 becomes
| the de-facto universal version.
|
| Alas, it's 2024, and of the leading browsers/implementations,
| only Safari/Webkit has managed to support JavaScript TCO. [1]
|
| [1] https://compat-table.github.io/compat-table/es6/#test-
| proper...
| neilv wrote:
| For terminology in Scheme, rather than "TCO", some people have
| suggested "PITCH" (Proper Implementation of Tail Call
| Handling).
|
| I think the reason for different terminology might be that, in
| most languages, TCO is the compiler thinking, "Oh, I see the
| programmer is doing recursion here, and I can actually optimize
| that particular one; though they'll probably never know, just
| like they don't know that their program is fast because of how
| I do register allocation and inlining; just another
| underappreciated silent optimization, but I take pride in my
| work, and don't need external validation."
|
| In Scheme, the compiler instead is thinking, "OK, those
| language designers encouraged programming with recursion in
| place of iteration constructs, and told everyone about tail
| position, and guaranteed that could not exhaust resources, so
| I'd better compile this entire named-`let` correctly, if I want
| to keep my job."
| odyssey7 wrote:
| That's useful background information. In ECMAScript 2015,
| it's referred to as "proper tail calls," rather than TCO,
| indicating that this is important in the language's design,
| rather than a mere performance optimization.
|
| Having proper tail calls expands the set of functions you can
| write without fear of overflowing the stack, so it
| fundamentally expands the expressiveness of the language for
| production use cases.
| quietbritishjim wrote:
| Agreed that it's more than just an optimisation if it's
| documented behaviour in the language, because then code is
| allowed to depend on its existence (which is not something
| you're allowed to do for a mere optimisation).
|
| There's a name that's both more accurate than TCO and more
| diplomatic than PITCH, which is TCE (tail call elision).
| That's certainly the name commonly used in the Python
| community when discussing (and rejecting!) it.
| unconed wrote:
| I think you also just described why browsers don't offer any
| useful way to give the garbage collector hints, like say,
| after every animation frame / GPU dispatch.
|
| It is exceedingly obvious that you have very regular idle
| times for it to do its thing, and yet, no way for it to make
| use of that.
|
| I don't think it's so much "pride in my silent work" tho as
| "has never actually talked to the users of their own
| software".
| weinzierl wrote:
| Rust has had a reserved keyword for proper TCO for a very long
| time but at the moment it looks very unlikely it will ever be
| implemented for more than one reason.
|
| https://web.archive.org/web/20230605150233/https://mail.mozi...
|
| (It's kinda sad that even with a relatively short history like
| Rust we need to resort to archive.org for this kind of
| documentation)
| odyssey7 wrote:
| Ah, that's a shame.
|
| So neither Python, JavaScript, nor Rust have fully adopted
| proper TCO across their communities. Whichever one gets
| there, I think that would be a strong point in favor of it
| being taught in university instruction, since recursion is
| one of the big concepts students explore.
___________________________________________________________________
(page generated 2024-05-25 23:02 UTC)