This 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.
When 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.
Ohh 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.
"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".
Unless 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)
While 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.
The 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.
I 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.
I also kind of like 'recurse' as a new construction for recursion in computer science to immediately disambiguate it from recurrence in ordinary language.
I’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.
Could 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.
The 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?
It 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)
Tail 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.
Languages like LISP, Clojure and Erlang would be a whole lot less useful in practice without tail call optimization, it allows you to write the 'naive' version of an algorithm and magically it 'just works'. Otherwise you'd have to explicitly code a loop where you would much rather use recursion.
> Otherwise you'd have to explicitly code a loop where you would much rather use recursion.
I find it much easier to reason about loops than to reason about recursion. Likewise I find it much easier to write loops than to write recursive functions.
It probably comes down to experience mainly. I spent some time with functional languages, but I have spent far far far more time writing imperative procedural code.
Even a simple problem such as the 'Towers of Hanoi' looks to me like a pretty messy solution when done with loops and with recursion it all just falls into place.
Recursion is great due to the implicit stack. The cases where you don't have an implicit stack, ie where tail call optimization works, are usually easier and much clearer to just do in a loop.
> Otherwise you'd have to explicitly code a loop where you would much rather use recursion.
The language would have to change for you to be able to code a loop. And that would have all sorts of consequences: in Erlang, preemption happens at function calls and no loops means a bounded time until you make a function call or terminate, with loops, that changes and preemption gets more difficult.
I didn't think this was true. The secret sauce was that Erlang preempted on reduction counts, so as a result nothing has any responsibility to yield itself.
edit: ah, literally no difference between the two in the implementation.
That's mostly an implementation detail though, the thread switch could happen just about anywhere. Function calls are a convenient stopping point but the way the reductions are implemented in Erlang it could theoretically be done on any boundary.
In this particular case though I don't think it would matter much. I've looked pretty closely at how the BEAM does it's thing and it's a work of art, this particular trade-off is more one of convenience than of necessity. But you are right that Erlang is full of such clever (and beautiful) tricks which make it a very interesting codebase to study.
What is special about tail call optimisation is that it actually changes the semantics of your program: You now get a guarantee that certain recursive functions do not exhaust the stack space, but behave like a loop. There should really be a language level feature such that you can be sure your functions are not fully recursive, but tail-recursive.
Yes, algebraising your control flow to become independent of implementation details like that is a possibility. Of course, you need a language that makes that a) easy, b) performant.
> ... is there more to the significance of tail call optimization that I am unaware of?
Looking at TCO in isolation is missing the big picture. You need to consider other language features that uses TCO.
In Scheme/Racket the specification says that implementations must support an "unbounded number of active tail calls" (for implementations that use stack frames to implement function calls, this means that TCO must be supported).
This requirement is a global requirement.
The other feature of Scheme/Racket that compelled the authors of the Scheme standard to require an "unbounded number of active tail calls" are macros. Macros in Scheme allow users of the language to add new bindings constructs (e.g. pattern matching), new control constructs etc to the language using syntax rewrite rules. In Scheme these rewrite rules work locally. [Racket allows for global program rewrites too].
There is a range of constructs that are possible to specify locally - if tail calls don't allocate that is. As an example: There are embeddings of Prolog in Scheme.
If Scheme didn't support TCO then a global transformation of the program is needed.
So instead of writing local macros - a full compiler is needed.
These days it is common to see JavaScript as a compilation target.
Babel compiles JavaScript+NewFeatures to GoodOldJavaScript.
The features that allow local rewriting are much easier to implement than the
ones that require a global transformation. If JavaScript had TCO it would
be much easier to use JavaScript as a compilation target.
One thing to add: It's idiomatic for Scheme (or Racket) code to use tail calls in places that would be unnecessary and inappropriate in many languages.
This can combine with other language features and idioms, to get effects such as (in addition to what soegaard mentioned) reducing mutations, and avoiding `return` exits. Which can increase the readability/maintainability -- and therefore correctness -- of the code.
So some suggest that Tail Call Optimization for Scheme should instead be called Proper Implementation of Tail Calls.
>leading me to wonder if it holds a unique level of importance among the other strategies.
Nah, it's just very easy to understand while being of technical nature. People tend to feel smart when they grasp it and then they can't shut up about it. They even write musicals...
It's ok to wonder at new (to you) knowledge and relay it with passion, even as grizzled vets look on, some scoffing, some with hope. This is the exact type of reaction that makes people turn off the YT comments ... came here to see how deep in the comments this would be; it's the 4th one
For functional programming it is a required optimization for performant programs.
This is because loops don't exist in functional programming. The base way of imitating looping in functional programming is recursion then building abstractions on top of the recursion like map and reduce.
The 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.
I 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.
To 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.
I 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) 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?
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.
59 comments
[ 6.8 ms ] story [ 141 ms ] threadBecause 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. :)
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.
"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".
I also kind of like 'recurse' as a new construction for recursion in computer science to immediately disambiguate it from recurrence in ordinary language.
If you'd please review https://news.ycombinator.com/newsguidelines.html and stick to the rules when posting here, we'd appreciate it.
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?
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.
I find it much easier to reason about loops than to reason about recursion. Likewise I find it much easier to write loops than to write recursive functions.
It probably comes down to experience mainly. I spent some time with functional languages, but I have spent far far far more time writing imperative procedural code.
The language would have to change for you to be able to code a loop. And that would have all sorts of consequences: in Erlang, preemption happens at function calls and no loops means a bounded time until you make a function call or terminate, with loops, that changes and preemption gets more difficult.
I didn't think this was true. The secret sauce was that Erlang preempted on reduction counts, so as a result nothing has any responsibility to yield itself.
edit: ah, literally no difference between the two in the implementation.
If you take out enough simplifying implementation details, you no longer have a powerful system built from simple parts.
Instead, there's loop/recur where the recur call won't compile except in tail position.
Haskell: https://hackage.haskell.org/package/recursion-schemes
Scala: https://github.com/precog/matryoshka
Looking at TCO in isolation is missing the big picture. You need to consider other language features that uses TCO.
In Scheme/Racket the specification says that implementations must support an "unbounded number of active tail calls" (for implementations that use stack frames to implement function calls, this means that TCO must be supported).
This requirement is a global requirement.
The other feature of Scheme/Racket that compelled the authors of the Scheme standard to require an "unbounded number of active tail calls" are macros. Macros in Scheme allow users of the language to add new bindings constructs (e.g. pattern matching), new control constructs etc to the language using syntax rewrite rules. In Scheme these rewrite rules work locally. [Racket allows for global program rewrites too].
There is a range of constructs that are possible to specify locally - if tail calls don't allocate that is. As an example: There are embeddings of Prolog in Scheme.
If Scheme didn't support TCO then a global transformation of the program is needed. So instead of writing local macros - a full compiler is needed.
These days it is common to see JavaScript as a compilation target. Babel compiles JavaScript+NewFeatures to GoodOldJavaScript. The features that allow local rewriting are much easier to implement than the ones that require a global transformation. If JavaScript had TCO it would be much easier to use JavaScript as a compilation target.
This can combine with other language features and idioms, to get effects such as (in addition to what soegaard mentioned) reducing mutations, and avoiding `return` exits. Which can increase the readability/maintainability -- and therefore correctness -- of the code.
So some suggest that Tail Call Optimization for Scheme should instead be called Proper Implementation of Tail Calls.
Nah, it's just very easy to understand while being of technical nature. People tend to feel smart when they grasp it and then they can't shut up about it. They even write musicals...
For functional programming it is a required optimization for performant programs.
This is because loops don't exist in functional programming. The base way of imitating looping in functional programming is recursion then building abstractions on top of the recursion like map and reduce.
First time we've (7mind) implemented that in ZIO in 2019 ( see https://m.youtube.com/watch?v=mGxcaQs3JWI ), now it's a norm in Scala world.
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.
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
A more thorough treatment: https://www2.ccs.neu.edu/racket/pubs/dissertation-clements.p...
march 2021 https://news.ycombinator.com/item?id=26470532
Tail Call Optimization: The Musical (2019) [video] - https://news.ycombinator.com/item?id=26470532 - March 2021 (37 comments)
Above this code is a switch statement and it's in a loop. The nestged switch statement switches on currentTask and loop task state.
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-contro...
I want to redesign the architecture of the async/await to be easier to understand. I want to use a state machine somehow.
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.
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) 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
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://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