Tail call optimisation requires accumulator?

[romanauto]

Hello, I'm just learning programming, so please excuse me if this is not the place for such questions.

From what Bing AI told me this function will not make Gleam compiler use tail call optimisation, because it needs an accumulator. Is it the case that Gleam requires a helper function for TCO?

fn more_than_n(my_list, item, n) -> Bool {
  case my_list, n {
  _,  n if n < 0 -> True
  [], _ -> False
  [i, ..rest], n if i == item -> more_than_n(rest, item, n-1)
  [_, ..rest], n ->  more_than_n(rest, item, n)
  }
}

[lpil]

That's right! Often you need to have a new argument to hold that data that would previously be on the stack frame.

[romanauto]

Is this a matter of scope of the accumulator and variables being immutable? In my function compiler can't change "n" on stack because it's immutable?
Would you mind pointing to relevant documentation or material on the topic? Gleam looks like a potentially very nice starter language that enforces good practice.

[lpil]

Nope, it's the same in a mutable context too. If you are using the stack to store data before you need somewhere else if you're not using more stack frames.

[Rudxain]

There are special cases where we don't need an accumulator, such as:

/// ♾️
fn loop(callback) {
  callback()
  loop(callback)
}

which is equivalent to the following TypeScript (except for the mutable params):

/** ♾️ */
const loop: (callback: CallableFunction) => never = callback => {
  while (true)
    callback()
}

Notice how TS doesn't support retroactive type-inference, so we must specify the type of callback. TS does support "strict" type-inference, so the never is inferred, so (in this case) => never is just boilerplate.

If we wrote this instead:

/// ♾️
fn loop(cb: fn() -> Nil) {
  cb()
  loop(cb)
}

we would get:

/** ♾️ */
const loop: (cb: () => undefined) => never = cb => {
  while (true)
    cb()
}

Which forces API consumers to always pass callbacks that return nothing, instead of anything.

Please keep in mind that JS/TS undefined is equivalent to Java/Kotlin null and Python None, while Gleam Nil is akin to Rust () "Unit Type" (just an empty tuple)

[dahlbaek]

Coming from scala, that function looks very tail recursive to me 🤔 In scala it would be

object TailRec {
  @scala.annotation.tailrec
  def more_than_n(my_list: List[Int], item: Int, n: Int): Boolean = (my_list, n) match {
    case (_,  n) if (n < 0) => true
    case (List(), _) => false
    case (i :: rest, n) if (i == item) => more_than_n(rest, item, n-1)
    case (_ :: rest, n) =>  more_than_n(rest, item, n)
  }
}

which the compiler accepts according to godbolt https://godbolt.org/z/M3fh6MqM8. Are there some extra rules one must adhere to in Gleam compared to Scala in order to trigger tail call optimization?

[dahlbaek]

I also tried to drop the generated erlang into godbolt (https://godbolt.org/z/3n8Eaqz4r), and it seems like TCO is applied

-module(more_than_n).
-export([more_than_n/3]).

-spec more_than_n(list(integer()), integer(), integer()) -> boolean().
more_than_n(My_list, Item, N) ->
    case {My_list, N} of
        {_, N@1} when N@1 < 0 ->
            true;

        {[], _} ->
            false;

        {[I | Rest], N@2} when I =:= Item ->
            more_than_n(Rest, Item, N@2 - 1);

        {[_ | Rest@1], N@3} ->
            more_than_n(Rest@1, Item, N@3)
    end.

compiles to

{function, more_than_n, 3, 2}.
  {label,1}.
    {func_info,{atom,more_than_n},{atom,more_than_n},3}.
  {label,2}.
    {test,is_lt,{f,3},[{x,2},{integer,0}]}.
    {move,{atom,true},{x,0}}.
    return.
  {label,3}.
    {test,is_nonempty_list,{f,5},[{x,0}]}.
    {get_list,{x,0},{x,3},{x,0}}.
    {test,is_eq_exact,{f,4},[{x,3},{x,1}]}.
    {gc_bif,'-',{f,0},3,[{x,2},{integer,1}],{x,2}}.
    {call_only,3,{f,2}}.
  {label,4}.
    {call_only,3,{f,2}}.
  {label,5}.
    {test,is_nil,{f,6},[{x,0}]}.
    {move,{atom,false},{x,0}}.
    return.
  {label,6}.
    {test_heap,3,3}.
    {put_tuple2,{x,0},{list,[{x,0},{x,2}]}}.
    {case_end,{x,0}}.

where I believe label 2 is the first case branch, label 5 is the second, and label 3 and 4 are the last two branches respectively. If I understand correctly, the call_only instruction implies that the function was tail call optimized.

[dahlbaek]

The javascript target generates

function more_than_n(loop$my_list, loop$item, loop$n) {
  while (true) {
    let my_list = loop$my_list;
    let item = loop$item;
    let n = loop$n;
    if (n < 0) {
      let n$1 = n;
      return true;
    } else if (my_list.hasLength(0)) {
      return false;
    } else if (my_list.atLeastLength(1) && isEqual(my_list.head, item)) {
      let i = my_list.head;
      let rest = my_list.tail;
      let n$1 = n;
      loop$my_list = rest;
      loop$item = item;
      loop$n = n$1 - 1;
    } else {
      let rest = my_list.tail;
      let n$1 = n;
      loop$my_list = rest;
      loop$item = item;
      loop$n = n$1;
    }
  }
}

which also looks like it got correctly tail call optimized

[lpil]

That covers some cases but after that whether TCO happens is runtime specific. On Erlang it is always runtime specific and we don't have any way of easily guaranteeing it.

[dahlbaek]

Out of interest (I don't have any experience running Erlang in production), the phrasing in https://www.erlang.org/doc/reference_manual/functions#tail-recursion made me think Erlang guarantees TCO for any tail-recursive function 🤔 maybe I'm mis-interpreting the reference, or maybe there are other runtimes with different guarantees.