gleam-lang/gleam

Implement mutual recursion TCO on JavaScript

Open

#3,830 opened on Nov 14, 2024

View on GitHub
 (17 comments) (8 reactions) (0 assignees)Rust (21,417 stars) (960 forks)batch import
help wanted

Description

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.

Contributor guide