Explicit tail calls

[cGuille]

Hello,

I am quite inexperienced when it comes to fully functional programming.

When using recursion, tail calls seem to be very important for recursive functions. They would be the difference between a function that can be used with large input data or one that can not.

That a function is tail call recursive might be immediately obvious to experienced functional programmers, but I think it is not to many of us.

If you have tips or tools to easily check that your recursive functions are tail recursive, feel free to share them; they could be an alternative to this proposal.

Otherwise, since Gleam is super supportive of the developer experience, would you think it a good idea to add "something" to a function to explicitly require it to use tail call recursion?

I don't know about the syntax or name of the operator, maybe adding a @tail_recursive attribute to the function?
Using the tour's example code, it would look like:

pub fn factorial(x: Int) -> Int {
  // The public function calls the private tail recursive function
  factorial_loop(x, 1)
}

@tail_recursive 
fn factorial_loop(x: Int, accumulator: Int) -> Int {
  case x {
    0 -> accumulator
    1 -> accumulator

    // The last thing this function does is call itself
    // In the previous lesson the last thing it did was multiply two ints
    _ -> factorial_loop(x - 1, accumulator * x)
  }
}

Or maybe the opposite, an attribute to deny non-tail recursive calls?

It would be a compile error to define a function marked as tail recursive while making a non-tail recursive call, which means that:

• If you thought you had written a tail call recursive function but failed to do so (infix operators can be quite confusing in that regard), you get a compile error instead of a runtime failure once the function is given an input that produces lots of recursions.
• If later on, someone changes the function, it will ensure that the tail call is not removed implicitly without warning, as it will be obvious in code review that the keyword has been removed.

Or can/should it be implemented in userland?

[lpil]

This isn't something that the compiler can do as tail call behaviour is a factor of both the compiler and the runtime. Just the compiler isn't able to guarantee any particular behaviour.

You could make a linter tool to give you good-enough hints, that could be a fun project and useful for folks who are learning!

You'll perhaps find understanding this becomes trivial as you become used to working in the functional style, which may make building a static analysis tool not so interesting.

[cGuille]

I imagined that the compiler could do that because I assumed it would be possible for it to know what is the last expression of the function's body.

But that's probably a naive assumption.

Do people just usually use the eye test for this?

Thanks for the answer!

[lpil]

When compiling to JavaScript the compiler will rewrite some self recursive tail call functions to loops, but others are left as is.

The JavaScript specification says that tail calls should reuse the stack, however Google decided to break spec compatibility with Chrome, so code the spec says should run fine will instead fail with a stack overflow. We don't know what runtime you'll use or how it'll handle each tail calls, so we can't offer you guarantees.

Similar for for the BEAM: we don't do anything and it is left entirely up to the runtime to optimise tail calls.

Do people just usually use the eye test for this?

Yes, I think it becomes something you can see clearly with some experience.

[cGuille]

Well, that was interesting. Thanks for taking the time to explain!

So if I try to summarize with my own words: the compiler should be able to find out if a recursive call is syntactically a tail call, but since it does not know the runtime it cannot guarantee that the tail call will be optimised and actually reuse the stack frame.

Is that it?

(Also, Google really forgot about their former motto "don't be evil".)

[lpil]

Yup, you got it!