Eli Dowling (Jan 30 2024 at 00:43): Eli Dowling (Jan 30 2024 at 00:43):I saw in this issue someone mentioned this idea Understanding Performance.
I remember when i was first learning functional programming I really wished there was some way for me to quickly check if a function was tail recursive. I was learning fsharp at the time which uses the "rec" keyword to denote recursive functions and i wished there was t-rec keyword that required it to be tail recursive.
So i was thinking we could display a code lens above each recursive function that indicates if it is tail recursive or recursive.
I prototyped this by including that info in the hover
image.png
image.png
I may have found a bug too, I'm using the DeclarationTag to see if the function declaration is tail recursive. It has marked this function as recursive not tail recursive:
g2 = \x ->
if x>10 then
g2 (x-1)
else x
That's a super cool idea. I like it a lot for general perf validation check
Eli Dowling (Jan 30 2024 at 03:59):Well I made a PR for anyone who wants to try this out and provide some feedback.
I also fixed the if else tail recursive bug and added some tests.
https://github.com/roc-lang/roc/pull/6466
Anne Archibald (Jan 30 2024 at 17:42):Very cool to get it working already! But I think there might be a problem: it's not functions that are or aren't tail recursive, but function calls. I could write a function with an if that did a tail call on one branch (easy case) but a non-tail call on the other (hard case, result needs some post processing). For that matter, a function f might call a function g in a tail call; if g called f in a tail call as well then the whole cycle could avoid filling the stack.
I think a tail call recognition tool has to mark call sites as tail calls or not. Probably they should be easy to spot - the return value is the direct result of another function - but with the pipe operator that's not always so simple for a beginner. And an apparently minor code change that causes a segfault is not nice.
Brendan Hansknecht (Jan 30 2024 at 17:48):It really is more at the function level. The question is, can the compiler remove the recursion in the function and make that specific function into a loop instead
Of course getting info at the call site is quite useful for actual debugging and correction. Probably want both labels if possible. Then you can see that a function you expect to be tail recursive isn't and check each exit path to see which one is breaking that.
Anne Archibald (Jan 30 2024 at 20:28):Tail call optimization is a general feature that can be applied to any call site (although it's not especially powerful except in recursion of some pattern or another). According to the web site, roc has full tail call optimization, not just the specific case where you call the same function. So it does safely handle cycles of tail-calling functions. (Which is good, since a bit of refactoring can turn a single tail-recursive function into a pair of mutually tail-recursive functions.) Trying to decide whether a whole function is tail-recursive is a hard-to-define problem: I guess you could report whether all the places it directly calls itself are tail calls, but what about indirect calls? Splitting a function into two could look like it was breaking tail call optimization when it wasn't.
Richard Feldman (Jan 30 2024 at 20:53):Anne Archibald said:
According to the web site, roc has full tail call optimization, not just the specific case where you call the same function.
I tried to be careful about the wording on that, what it says on /fast is "tail recursion optimization" rather than "tail call optimization" to reflect that we do it for recursive functions but not (yet!) for arbitrary tail calls :big_smile:
Eli Dowling (Jan 30 2024 at 22:12):Anne Archibald said:
It's not functions that are or aren't tail recursive, but function calls. .
I actually wasn't aware of tail call optimisation outside of recursive functions. It's certainly possible to mark the call site. I was thinking perhaps a code action that you can run on recursive functions would highlight the locations where a call is not a tail call. Otherwise I worry it would be quite noisy showing them all the time.
Or if I display it as a code lens, it would be clickable and that could be the result, like "Goto references" but it shows non-tail recursive calls of the current function.
From what Richard said it sounds like TCO isn't applied to mutually recursive functions, so there isn't much I can do there.
Brendan Hansknecht (Jan 30 2024 at 22:17):In current roc, we have two cases:
Eli Dowling (Jan 30 2024 at 22:19):Ahh, okay, well I don't think there is a lot of point showing info on random tail calls, I think it's generally pretty obvious if a call is a tail call anyway tbh. But it might be helpful for beginners to be able to show specifically why their functions aren't tail recursive. What do you think?
Brendan Hansknecht (Jan 30 2024 at 22:21):Sorry if my message came off wrong there. Mostly just wanted to clarify that I would expect to get some of these optimizations through llvm.
Kiryl Dziamura (Jan 30 2024 at 22:21):A bit aside: the long-standing problem with stack overflow caused by alloca is the result of the first case or the second?
Brendan Hansknecht (Jan 30 2024 at 22:21):As for showing it with the lsp. I think labelling the function and being able to query which exits aren't tail calls would be great.
Brendan Hansknecht (Jan 30 2024 at 22:24):Stack overflows and allocas come from the first. Same with the incorrect mutations (though that may be a general pointer thing and not specifically an alloca thing).
The performance related alloca issues don't specifically relate to tco.
Also, just to be clear. If we didn't do our own tco, llvm would see the allocas in the wrong location and refuse to do TCO. As a result, you would just get a regular stack overflow.
Eli Dowling (Jan 30 2024 at 22:26):Brendan Hansknecht said:
Sorry if my message came off wrong there.
No, no not at all, I was just wanting to check if you thought there was any value in showing those non-tail call non recursive functions :)
Brendan Hansknecht (Jan 30 2024 at 22:29):I think that is too low level of a detail for roc users to regularly care about. It only matters in cases where it leads to tail recursive functions. If in the future, roc guarantees some sort of mutual recursive tail call optimizations, I think we should figure out how to add/expose that as well.
Anne Archibald (Jan 30 2024 at 22:47):In general, that is for tail calls to other functions (that are not yet optimised), I think it makes sense to highlight the calls that are tail calls - the majority of function calls (Num.add n 1 for example) aren't tail calls, and highlighting them all will indeed be noisy. But when it's specifically single-functin tail recursion that gets optimised, there is a slight advantage to highlighting the calls that aren't tail calls over highlighting those that are - you might not notice a non-highlighted self-call among all the non-highlighted other-calls.
Brendan Hansknecht (Jan 30 2024 at 23:09):Num.add n 1 could be a tail call. Depends on how it is used.
Brendan Hansknecht (Jan 30 2024 at 23:10):Anytime it is the last call in a function (and directly returned result), it would be a tail call.
Brendan Hansknecht (Jan 30 2024 at 23:11):ex:
someFn = \n, bool ->
if bool then
Num.add n 1
else
n
Well I tried to implement the code lens/code action feature but sadly there is no way for a code action or code lens to take you somewhere. Not in a way that is editor agnostic at least. It is possible within vscode using their custom editor extension based code lenses, but it's not part of the usual LSP spec.
Richard Feldman (Feb 04 2024 at 12:14):if you're up for it, I think doing it for vs code is worth it anyway
Richard Feldman (Feb 04 2024 at 12:15):LSP is great for getting started, but long term with Roc's custom editor plugins I expect we'll end up moving past LSP anyway
Richard Feldman (Feb 04 2024 at 12:16):and need to implement per-editor extensions anyway (which can of course delegate to LSP for lots of things at first, so there's no UX regression)
Richard Feldman (Feb 04 2024 at 12:17):anyway, I wouldn't consider it a blocker that LSP doesn't support it, because we'll eventually doing C FFI in every editor in order to load and run compiled Roc plugins on the fly, and LSP certainly won't support that! :big_smile:
Eli Dowling (Feb 04 2024 at 12:39):I'll definitely add it to a to-do list. Though I think I'll try get the generic, "works in all editors", hover version looking nice and merged in for the meantime.
I don't actually use vscode personally, and for now I think my time is better spent on enhancements that benefit all editors.
Anne Archibald (Feb 04 2024 at 13:18):Eli Dowling said:
Well I tried to implement the code lens/code action feature but sadly there is no way for a code action or code lens to take you somewhere. Not in a way that is editor agnostic at least. It is possible within vscode using their custom editor extension based code lenses, but it's not part of the usual LSP spec.
I'm afraid I've slightly lost track of the threat of conversation here: is the goal to make it visible why one's function is/is not tail recursive?
I still like the idea of highlighting (self-)call sites in different colours depending on whether or not they were tail calls. Then making one's function tail-recursive amounts to fixing that one call that is blue instead of green.
Eli Dowling (Feb 04 2024 at 13:26):That's not something we can do with tree sitter or textmate highlighting. Technically it's possible with semantic tokens generated by the language server but doing that would likely be too slow, and I'd say confusing.
I was suggesting showing a codelens above the function that would then show you a list of the non tail recursive calls. Like "Goto references" but just showing those calls.
However that's not something that can be done within the language server at this time, so it would have to be built directly into the vscode extension and only work in vscode.
I'm suggesting neatening up the hover part that shows if a function is tail recursive or not, because that's easy and works in all editors, and just leaving anything vscode specific for later.
Eli Dowling (Feb 04 2024 at 13:29):Though we could make a setting that shows an info diagnostic at the non-tail-recursive call site, that would work in all editors.
Anne Archibald (Feb 05 2024 at 19:01):Richard Feldman said:
Anne Archibald said:
According to the web site, roc has full tail call optimization, not just the specific case where you call the same function.
I tried to be careful about the wording on that, what it says on /fast is "tail recursion optimization" rather than "tail call optimization" to reflect that we do it for recursive functions but not (yet!) for arbitrary tail calls :big_smile:
Very carefully worded!
As an experiment, I wrote a call that was supposed to be tail-recursive, except it used backpassing and Result.try. Since this is actually a pair of mutually recursive functions - the main function and the lambda produced by the backpassing - I expected my stack to explode when I ran it on large numbers, but it was fine. Is this a property I should count on, or did I get lucky with the optimiser?
The (silly) function:
convertSmash : I64 -> Result U32 [OutOfBounds]
convertSmash = \n ->
x <- Num.toU32Checked n |> Result.try
convert (n - 1)
I would expect llvm to inline that 100% of the time. Long term, we definitely want to manually inline single use lambdas like that to guarantee it always happens.
Brendan Hansknecht (Feb 05 2024 at 19:29):If you make a long enough backpassing chain, llvm may decide functions get too big to inline, so it could theoretically hit problems.
Brendan Hansknecht (Feb 05 2024 at 19:29):I'm pretty sure this is all llvm and won't be any of rocs guaranteed tail recursion.
Eli Dowling (Feb 29 2024 at 08:20):Alright this is now working how I expect it to! https://github.com/roc-lang/roc/pull/6466
It currently is just always on, I'll sort out the method for turning it on and off soon.
If some folks could give it a go I'd love to hear some feedback.
I'm thinking in the final version:
It can either be on for the whole file, or just a function.
There is a config option to either show verbose errors for beginners or a super short version for more advanced users.
eg: Just "TailRec" and "Rec"
Eli Dowling (Feb 29 2024 at 08:24):
Last updated: Jun 16 2026 at 16:19 UTC