Implement mutual recursion TCO on JavaScript

[lpil]

V8 (the most widely used JS engine) doesn't implement tail calls for some bad reason, so we need to implement tail call optimisation in the compiler.

Today we support self-recursion. Extend this to support mutual recursion.

My thought was that we could compile this code

pub fn up(a) {
  case wibble(a) {
    True -> down(a)
    False -> a
  }
}

pub fn down(a) {
  case wobble(a) {
    True -> up(a * a)
    False -> down(a + 1)
  }
}

To something like this

export function up(a) {
  return mutual$up$down(0, a);
}

export function down(a) {
  return mutual$up$down(1, a);
}

export function mutual$up$down(mode, up$a, down$a) {
  if (mode == 0) {
    // This is the `up` function
    if (wibble(up$a)) {
      mode = 1;
      down$a = up$a;
    } else {
      return up$a;
    }
  } else {
    // This is the `down` function
    if (wibble(down$a)) {
      mode = 1;
      down$a = down$a * down$a;
    } else {
      mode = 0;
      up$a = down$a;
    }
  }
}

The exact names etc we would use would need some thought, but you get the idea.

We already identify functions reference loops during analysis, so perhaps we could use that as a starting point for identifying when this optimisation can be applied.

This would be a challenging item of work.

[inoas]

It cannot be a circle of 3 functions? If it can, does Erlang support this?

[lpil]

It would support any number of mutually recursive functions.

[giacomocavalieri]

Something is wrong with the gift wrapping machines at Santa's facilities in Swindon. You're the lucky elf who's been selected to take a look and fix it!

Louis, the lil british Elf, gives you a schematics of the Gift-Wrapp-inator and with great horror you discover it's powered by Gleam code!

Upon further inspection you notice that these two functions are the source of the problem, causing the machine to stack overflow when there's 1_000_000_000 of gits to wrap:

pub fn wrap(gifts) {
  case gifts {
    [] -> we_can_go_home()
    [gift, ..gifts] -> do_wrap(gift, gifts)
  }
}

pub fn do_wrap(gift, rest) {
  case is_fragile(gift) {
    True -> bubble_wrap(gift)
    False -> Nil
  }
  wrap_with_paper(gift)
  put_christmas_cockade(gift)
  wrap(gifts)
}

It looks like some naughty elf has not been careful enough with their recursive functions!

There's no time to change the Gift-Wrapp-inator code (Santa is really slow at code reviewing), so the only solution left to save Christmas is to implement proper tail call optimisation for mutually recursive functions!

[GearsDatapacks]

Am I the only one that can see that message? It feels targetted

[richard-viney]

Would this also address cases like the following which overflow the stack on JS even though only a single top-level function is defined?

import gleam/bool

pub fn main() {
  go(10_000)
}

fn go(i: Int) -> Int {
  use <- bool.guard(i < 0, -1)

  case i {
    0 -> 0
    _ -> go(i - 1)
  }
}

The anonymous function created by use is the culprit. I've run into this on several occasions and am now careful to avoid use in recursive functions that target JS.

Alternatively, with some extra smarts could the codegen for use <- bool.guard(...) avoid the anonymous function by inlining its conditional check? It could become a single if in JS, which could be both a performance win as well as fixing the stack overflow above. If this works it could be extended to work for other common functions used with use (e.g. result.map, result.try).

The above Gleam would then generate the following JS:

export function go(i) {
  if (i < 0) {
    return -1;
  } else {
    if i === 0 {
      return 0;
    } else {
      return go(i - 1);
    }
  }
}

Just an idea at this stage!

[giacomocavalieri]

I don't think the compiler can do this as It would require full program compilation to know it can inline bool.guard from another module

[richard-viney]

Ok, so fixing the stack overflow on JS caused by a use <- bool.guard(...) in a recursive function would require full program compilation of some kind, and so wouldn't be addressed by this issue as it's for handling mutually recursive functions in a single module.

Shall I open a separate issue?

[GearsDatapacks]

If we implemented function inlining, as discussed in #3722, in addition to mutual recursion TCO, that would fix the issue. However, neither of those are a small task and it's likely going to be a while before we get them

[lpil]

I don't think we would be able to solve that with mutual recursion TCO as it's not mutual recursion, bool.guard does not call go.

It would be solved by inline though: #3722

edit: oops, I now see that I am too late to this conversation! ahaha