How can we make it easier to verify tail call optimisation is applied

[SoTeKie]

This would enforce any function with the attribute to be tail recursive, throwing a compiler error otherwise.

This can make ensuring a function is tail recursive much easier, as it removes the need for the programmer to manually test it, look at the compiled result etc.

[SoTeKie]

If this sounds like a good idea, I'd love to take a stab at adding support for this

[MystPi]

I like this idea a lot! It is annoying to have to look at the generated code to see if the function was generated as expected.

(Previously suggested in this discussion thread #1789 but doesn't have any comments.)

[lpil]

I don't like the idea of having this attribute scattered throughout Gleam code, especially since it largely does nothing and so is entirely noise then.

I can see the value in checking whether functions are tail recursive, but I think this should be done through tooling instead. For example, the LSP could say on hover, or with a third party CLI tool made using the Glance parser.

To make matters more complex when the optimisation is applied will vary depending on the target being used.

[SoTeKie]

I guess it depends on what type of code you're working on, but imho having a way to enforce tail recursion is pretty nice.

For example when implementing functions where exceeding the stack limit is a reasonable worry it would be somewhat insufficient to manually check it through the LSP definition/resulting compiled code.

I can't think of a edit: less noisy way to enforce tail recursion on a function easily outside of an attribute 🤔

For verifying it instead, having it on LSP hover sounds pretty cool

[jdsee]

I really like the idea of being able to enforce tail recursion for specific functions. It's just too easy to design a function in a tail recursive style and then have it changed by another programmer (aka future me) and lose the guarantees.

Would it really be so bad to offer something like @tailrec? It could still be optional for the cases in which the extra noise isn't worth the reassurance. I find this also valuable in terms of documentation.

Anyway it would be great if the language server offered support for this. I'm wondering if it's possible to provide separate syntax highlighting for tail recursive functions in an editor agnostic way.

BTW: Gleam looks great! Thanks for your big effort on this project :)

[SoTeKie]

I agree with the recommendation to highlight tail recursive functions in the LSP.

I was just wondering @lpil if there's any alternative syntax/system to attributes you would find acceptable for enforcing tail-recursiveness on a function or if the enforcing part should be left to third party tooling all together.

In the future I can imagine myself making some sort of tool to enforce this, but if it's outside of the language it would mean I'd have to introduce some non-standard comment/naming scheme for the tool to be able to enforce it.

[dahlbaek]

Coming from scala, I would feel uneasy using recursion instead of looping if there was no way to ask the compiler to enforce TCO 🤔 I guess there's always options like using iterators with helper functions such as

fn iterator_loop(init: e, acc: acc, f: fn(acc) -> iterator.Step(e, acc)) -> e {
  iterator.unfold(acc, f)
  |> iterator.fold(init, fn(_, last) { last })
}

[lpil]

Note this would be much slower than using looping with recursion or list functions as there is an overhead to lazy data structures.

[dahlbaek]

True, though lists carry their own performance barriers in terms of memory 🤔 . One could also do something like

type Loop(a, b) {
  Continue(a)
  Break(b)
}

fn loop(a: a, f: fn(a) -> Loop(a, b)) -> b {
  case f(a) {
    Continue(a) -> loop(a, f)
    Break(b) -> b
  }
}

I wonder what the the relative performance of each would be:

1. iterators
2. lists
3. loop helper
4. direct recursion

I guess it shouldn't be too hard to set up a benchmark...

[lpil]

It would be direct recursion fastest, then a list module function list, then an iterator module function

[dahlbaek]

I wrote down a stupid benchmark, computing the 1000th fibonacci number by brute force 10000 times, ran it a few times and noted down the quickest run. For this case, using lists didn't make sense. As expected, direct recursion was fastest, and an iterator based solution was significantly slower in this example, around a factor 2-5 depending on which iterator methods where used.

The loop solution suggested above was slower than direct recursion by around 25% on Erlang, but on javascript it was slower by an order of magnitude. I inspected the generated erlang/javascript briefly, and afaict the difference in performance derives from the fact that erlang distinguishes varieties by looking at lightweigth atoms, whereas javascript uses runtime reflection to determine the class. On the other hand, a while style helper

fn while(a: a, predicate: fn(a) -> Bool, f: fn(a) -> a) -> a {
  case predicate(a) {
    True -> while(f(a), predicate, f)
    False -> a
  }
}

was relatively fast on both targets: approximately 25% overhead on Erlang, and approximately 100% overhead on javascript (afaict, the overhead here stems entirely from the fact the gleam products map to javascript arrays, so a tail-recursive function with multiple arguments is more performant than a tail-recursive function with a single array argument).

@lpil I understand that you're against a noisy attribute that would mostly do nothing, and that some type of guaranteed TCO is out of scope. Do you think it could be a good idea to instead provide a helper function (for instance something like above) that people can use for cases where you want to make sure you're protected against recursion beyond the stack limit, and that also has reasonable performance characteristics on both targets? I'm, of course, thinking specifically of cases where you don't want to fold over an already existing data structure.