6 ms·
Tail Call Optimization: The Musical (2019) [video]
- discardable_dan 4y agoThis is brilliant, except that one recurs -- just as one incurs debt. Recursing is a thing one does to a throne in Nethack, not something done with code.
- stingraycharles 4y agoWhat do you mean, you mean typical JavaScript code doesn’t use recursion? Because I can assure you that as someone who works mostly in FP languages, recursion is, in fact, done a lot with code and not just nethack. :)
- pgorczak 4y agoI think GP means it’s “I recur, he/she recurs” rather than “I recurse, he/she recurses”
- discardable_dan 4y agoWhen an incurrence of debt occurs, we say that someone incurs it. Similarly, English demands that for a recurrence relation (the source of recursion schemes and basis of the term "recursion"), we recur. "Recurse" is a backronym adopted by people who were ignorant about english, math, or possibly both. And now it's become a part of literal coder camp names.
- stingraycharles 4y agoOhh thanks for explaining this. I totally missed this was a grammatical correction. I’m not a native speaker, and I actually learned something from it. So how should I say “this code is recursing” instead? “This code is ..” ? Or is it solely about the form of “This code recurses”, which should instead be “This code recurs” ? Which also sounds somewhat wrong, because wouldn’t that refer to “recurring” instead of “recursing” ? Thanks for your explanation, and of course the grandparent as well.
- dmurray 4y ago"This code recurs" or "this code is recursive". "This code is recurring" is correct, but not so idiomatic. But English is a living language, grammarians should be descriptive not prescriptive etc... "Recurse" (and "Recursing") is a perfectly good backformation, especially because it performs a useful function in distinguishing between two uses of the overloaded verb "to recur".
- mlashcorp 4y agoUnless you're using a functional programming language that does not support iteration. (and even if it does support it, it's typically preferred to use tail recursion)
- discardable_dan 4y agoI think in those cases, you'll also find that those programmers use recursion, and write programs that recur -- not ones that recurse.
- 082349872349872 4y agoWhile others are by GOs possessed, And WHILE-DO, CASE, and all the rest, The LISPing hackers will prefer With COND their programs to invest And let their functions all recur When searching trees in maddened quest. https://www.ultimate.com/phil/pdp10/quux.poem https://www.ultimate.com/phil/pdp10/quux.poem
- mlashcorp 4y agoAh gotcha. Apologies not a native speaker so the nuance was lost on me
- thfuran 4y agoThe bigger issue is that they're essentially entirely incorrect. "Recurse" is both in common use and well understood. I'd even argue that it's more correct than "recur", since it's unambiguously about recursion.
- jacobmartin 4y agoI appreciate your nit, but I have one myself: Can you curse the throne itself? Afaik you can only curse items, not dungeon features, and the NethackWiki doesn't list anything about a throne having B/U/C status. I don't see any way to capture it as an item. So I don't think recursing can happen to a throne in nethack.
- pxc 4y agoThey had to do it for the rhyme! I also kind of like 'recurse' as a new construction for recursion in computer science to immediately disambiguate it from recurrence in ordinary language.
- runarberg 4y agoI’m sure there are plenty of parsers out there written in JavaScript that use recursion, simply by the fact that many parsers are much easier written with recursion.
- japanman425 4y ago[flagged]
- Snild 4y agoPeople having fun? Not on my watch!
- dang 4y agoCould you please stop posting unsubstantive and/or flamebait comments to HN? You've been doing it repeatedly, unfortunately. It's not what this site is for, and destroys what it is for, so we have to ban that sort of account. If you'd please review https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html and stick to the rules when posting here, we'd appreciate it.
- s-macke 4y agoThe process of writing an optimized compiler involves utilizing hundreds of algorithms and strategies, one of which is tail call optimization. It seems that this particular optimization technique is frequently discussed and written about, leading me to wonder if it holds a unique level of importance among the other strategies. Is my perception incorrect, or is there more to the significance of tail call optimization that I am unaware of?
- mhh__ 4y agoIt doesn't require almost any advanced compiler techniques, and you can implement it without constructing the playpen typical of compilers (doing optimization on an AST directly is quite hard, tail calls are easy)
- toolslive 4y agoTell that to the Rust Compiler people ;)
- 3836293648 4y agoI thought the rustc people were against guaranteeing TCO, not having it at all
- blagie 4y agoTail recursion isn't just an optimization technique. It enables a broad range of algorithms to work. Anything where the stack grows O(n) can't be done without tail recursion because of stack overflows. There are two camps of programmers: 1) Ones who are used to writing such algorithms (e.g. in Lisp) who cry bloody murder because they can't use them in Python. It's painful to lose that type of expressiveness. 2) Ones who have never used them, and don't realize what they're missing. These will usually complain about surface issues (like nicer stack traces for debugging). Camps like camp #2 comes up a lot in history. - In the eighties and nineties, most BASIC programmers had never used pointers, references, or real data structures, and saw them as abstract theoretical constructs without any real-world use. - C / C++ programmers would call Java programmers lazy for wanting garbage collection (ignorant of the broad set of algorithms enabled if you don't need to keep track of when memory is no longer needed manually). - Java / C / C++ programmers saw closures and a lot of other functional tools as pointless, complex, theoretical abstractions, until Python / JavaScript / etc. ate their lunch. - Many people who have never used relational databases before see them as pointless complexity for most systems, aside from very specific use-cases. ... and so on. The other argument always made hinges on the Turing Completeness of languages ("I'd like to do X!" "Well, here's how you do it without Y. If you were just more clever, you'd see why Y is useless complexity.") You can ALWAYS implement any use case in any Turing-complete language. BASIC programmers stuck things into arrays. Java/C++ programmers could use objects instead of a closure. And tail-recursive code can always be translated into iteration.
- pshirshov 4y agoThe lost stack traces aren't necessarily unrecoverable, it's still possible to have useful "stack traces" in trampolined/tcoed code without direct support from the language runtime. First time we've (7mind) implemented that in ZIO in 2019 ( see https://m.youtube.com/watch?v=mGxcaQs3JWI https://m.youtube.com/watch?v=mGxcaQs3JWI ), now it's a norm in Scala world.
- soegaard 4y agoI am curious, did you look at "continuation marks" too?
- pshirshov 4y agohttps://docs.racket-lang.org/reference/contmarks.html https://docs.racket-lang.org/reference/contmarks.html ? Nope. But from what I see that's a dnfferent story, there you have support from the language runtime, if you have that the problem is trivial.
- soegaard 4y agoYes, a different story. The idea is that attaching information on "stack frames" might be useful for other things than stack traces. The reference linked to is precise, but do not show the utility. The rationale here gives a better quick introduction: > https://srfi.schemers.org/srfi-157/srfi-157.html https://srfi.schemers.org/srfi-157/srfi-157.html A more thorough treatment: https://www2.ccs.neu.edu/racket/pubs/dissertation-clements.pdf https://www2.ccs.neu.edu/racket/pubs/dissertation-clements.p...
- tippysdemise 4y agoI tried and failed to solve Advent of Code 2022 using F# in a purely functional style. Trying to write a tree fold function in a continuation-passing style broke my resolve. Hoping to learn something here.
- aaws11 4y agoprevious discussion: march 2021 https://news.ycombinator.com/item?id=26470532 https://news.ycombinator.com/item?id=26470532
- dang 4y agoThanks! Macroexpanded: Tail Call Optimization: The Musical (2019) [video] - https://news.ycombinator.com/item?id=26470532 https://news.ycombinator.com/item?id=26470532 - March 2021 (37 comments)
- samsquire 4y agoTo refer to the post, I don't know how a tail call optimisation would look for a coroutine. My async/await implementation has overhead of scheduling but the scheduler is very simple. Above this code is a switch statement and it's in a loop. The nestged switch statement switches on currentTask and loop task state. for (int i = -1; i < state.size(); i++) { int task = (currentTask + i + 1) % state.size(); if (state.get(task) == 0) { currentTask = task; } } No stack but 3 integers are used per coroutine. How do you have multiple instances of coroutines without destroying state of each one? I am interested in coroutines and there's a corollary between recursion and coroutines and stacks. I am trying to work out how to implement coroutines or async/await. I've written an unrolled switched based multithreaded implementation. Currently coroutines can async fork/eagerly start on another thread but it only supports one forked coroutine at a time at this time. This is similar to other async/await engines. You can have stackful coroutines (allocated on the heap) or stackless coroutines data presumably in your stackful langauage as a local variable or class variable or global. If I have N coroutines, I need to allocate three integers for each coroutine instance. One is the task state which is running or not running. Then there is integer/string for top level state (where in the coroutine are we) and then there is loop level state. A coroutine can be executing in any depth of loops, but these two integers or strings in my case represent all execution environments. Code of my unrolled state machine that uses switch statements and multithreading is here https://github.com/samsquire/multiversion-concurrency-control/blob/main/src/main/java/main/TokenRingTimer2AsyncAwait3.java https://github.com/samsquire/multiversion-concurrency-contro... I want to redesign the architecture of the async/await to be easier to understand. I want to use a state machine somehow.
- mgaunard 4y agoIt's the same. A coroutine that does ``` lazy<int> f(int i) { if (i == 0) co_return i; co_return co_await f(i-1); } ``` should be tail-optimized.
- swyx 4y agoI love this performance so much. in the best of days it can feel incredibly intimidating to sing a song parody at a technical conference, but then to do it well and have all the lyrics and slides lined up with interesting points made, that is truly art. i've met anjana enough that we're now friends. she's an incredible dev and speaker (https://www.youtube.com/results?search_query=anjana+vakil https://www.youtube.com/results?search_query=anjana+vakil) and even for her this performance was extremely out there and i imagine unbelievably challenging and somewhat vulnerable to do. its sad that people (incl myself [0]) don't take more professional risks doing this kind of "talk", and instead stick to the kind of tell-em-tell-em-told-em kind of format they think is expected in a talk, rather than thinking about the most creative, memorable, worthwhile way to get their ideas across. who else does these kinds of "risky but good" talks? i can only think Bret Victor (future of programming) and Gary Bernhardt (wat) but those are usual suspects at this point. who else? [0]: this was as far as i went, directly inspired by TCO the Musical https://www.youtube.com/watch?v=1WNT5RCENfo https://www.youtube.com/watch?v=1WNT5RCENfo
- ricklamers 4y agoHear hear Another talk that for me hits the same level where the line between art and technology is blurred is one by David Beazley at PyCon 2015 about concurrent programming [0]. Truly remarkable how some people turn their mastery into this extremely enjoyable tour of ideas. [0] https://m.youtube.com/watch?v=MCs5OvhV9S4 https://m.youtube.com/watch?v=MCs5OvhV9S4
- scrollaway 4y agoI want to highlight Dylan Beattie while we're posting our favorites. https://www.youtube.com/@DylanBeattie https://www.youtube.com/@DylanBeattie His song DMCA is my little favourite, but "You Give REST a Bad Name" is also excellent. And he does perform at conferences! (Mostly .NET ones) https://www.youtube.com/watch?v=nSKp2StlS6s https://www.youtube.com/watch?v=nSKp2StlS6s
- ricklamers 4y agoDylan rocks! Thanks for giving me something I didn’t know I needed in my life.
- surume 4y ago[flagged]