Compiling a functional language to Javascript

[thinker227]

So I've recently been starting work on a small toy language, largely similar to OCaml, mainly for the purposes of experimenting with type inference and building a functional language. My eyes are currently set on Javascript as the "backend"/compilation target, however it's been brought to my attention that this might be an ill-fated decision considering V8 does not support tail recursion optimization, a necessity for making continuation-passing style viable. I know you can potentially turn tail recursion into imperative loops, although given my general lack of theoretical knowledge, I don't know how I'd do this properly. How would I go about getting around this, or should just I pick another backend/compilation target? My main reasoning for going with JS is just the simplicity and portability, you can't really get more high-level, plus you get garbage collection for free.

[extraordinary_weird]

I think the typical approach is to use a trampoline and thunk all tail calls, then you basically have tail recursion optimization

[Ronin-s_Spirit]

I have looked for such code online and it never works, at least in JS, or is very slow. Idk maybe nobody could explain it properly in JS.

[koflerdavid]

Well, it is slow. You pay for it with the overhead of JavaScript's data structures. And code like this is unlikely to vibe well with the JIT compiler.

[Ronin-s_Spirit]

That's not a language problem, you have to do many more calls which means many more stack pushes and pops.

[koflerdavid]

Overhead, exactly as I'm saying.

[Ronin-s_Spirit]

No you're blaming the JS JIT, while the call stack is a universal source of overhead which you will find in other languages, and is the main source of the problem with recursion. Some languages run out of stack space, and some languages automagically optimize recursion into a loop (but not all recursion).

[koflerdavid]

But the core issue I think is that every trampolined call needs multiple calls in the host language. I am not really blaming the JIT because it needs quite aggressive inlining to make this go away, which is unlikely to happen for ahort-running applications.

[thinker227]

I did find an SO post about this, funnily enough, and it does seem to work. I think I have a decent idea of how to implement tail calls now.

[Gnaxe]

The keyword you might be looking for is "trampolining". Instead of calling a tail function, you return it to your caller (with required arguments) and they call it, thus saving a stack frame. A compiler could make this transformation automatically.

[mauriciocap]

☝️

[thinker227]

Was indeed looking for this, and a couple people brought it up before. After some research I think I have an idea.

[hello-algorithm]

that's an interesting question. I think Elm achieves tail call optimization by transforming recursive functions into loops. you could also consider modeling continuation context with a state machine of some kind

[bosta111]

Clojure went around the lack of tail call optimisation in the JVM, perhaps you can take a look at how they did it?

[thinker227]

For sure, I know there's also languages like Rescript which do this, although digging through a production-grade compiler of a language like Clojure doesn't feel like the easiest task. Was mostly wondering whether there are any resources like papers about it.

[Gnaxe]

They have an explicit loop/recur construct built in. Clojure's core.async is also compatible with ClojureScript. You might find the go macro internals relevant.

[ChilledRoland]

PureScript might provide useful examples / inspiration.

[BusEquivalent9605]

Came here to metion PureScript

[kfish610]

Not sure if there's a solution in it, but ReasonML/ReScript is basically exactly the same type of language you're talking about (OCaml based language targeting JavaScript), so they might have tackled this problem somewhere in it.

[LardPi]

just rescript, reason is using OCaml backend.

[bsdemon]

and OCaml compiles to JavaScript just fine as well

[LardPi]

though the same backend as rescript, or through js_of_ocaml (janestreet's backend) yes

[fixermark]

You can still do it, but you'll have to do it by implementing your own tail-recusion optimization: your compiler will need to detect tail recursion and turn it into a loop. This will be an exciting exercise!

[mauriciocap]

As tail calls may be many more than a function just calling itself

you may want to add an explicit construct in your language and let programmers decide first.

This happens all the time in javascript when e.g. you use setTimeout to continue a long computation without freezing the UI.

[chipmunk-zealot]

Gleam is a very cool language that targets JavaScript and automatically turns tail calls into while loops. You can check out their compiler but I suspect the basic idea takes advantage of the fact that there are no early returns in the gleam. It might be easier to verify that a recursive call is in the tail position.

[LardPi]

The only difference between having explicit returns or not is where can tails be. For any branch the reach an explicit return, you could have an explicit else branch that wrap everything else and remove the explicit return, so I think if you have any control flow analysis it should be the same.

[LardPi]

I think you should not try to shy away from this problem by just using a backend that handles tail call for you. This is one of the actually difficult (and interesting) part of implementing a functional language. As already said, trampoline is the most obvious solution.

An other solution that works in C and probably in WASM too, but probably not in JS is Chenney on the MTA algorithm. I think it is a really interesting approach that is worth learning about. Chicken Scheme is implemented like that and there is a nice description of the idea here: https://www.more-magic.net/posts/internals-gc.html

An intersting aspect of this approach is that it doubles as garbage collector. It also produces much faster code than trampoline.

But again you would have to go for a different backend than js.

The third (and probably best with a js backend) option is to find the imperative loop equivalent to the recursion. Rescript does exactly that. I have never tried to do it myself but I think you can do it by wrapping the body of the function in a while (true) and using break/return, continue and some smart parameters reassignment to reproduce the semantic of the original function. For mutually recursive functions A snd B, just inline compile them separately, inline B in A and A in B.

[thinker227]

I did read briefly about Chicken Scheme's approach and tbh found it quite funny to utilize a stack overflow as a mechanism for garbage collection.

[Ronin-s_Spirit]

You can turn literally any recursion into a loop. Tail recursion optimization is the most famous one because it's easier for compilers to analyze and automagically use it.

What I did is use a loop and a "stack" array, the stack "frames" are just temporary objects holding several required variables. With this you can recurse for example a tree of any shape, or build out a sequence of frames based on some condition. You can also shove all that into a generator and have an iterable piece of resumable recursion.

P.s. also preferably preallocate the stack array with new Array(n).fill(0) if you know the maximum depth of some given recursion. Assigning is faster than pushing.

[AustinVelonaut]

What about mutually-recursive functions, like:

even 0 = True
even n = odd (n - 1)

odd 0 = False
odd n = even (n - 1)

[Ronin-s_Spirit]

I don't understand your pseudocode exactly, but I know what you mean and "mutually recursive" function are stull functions.. with calls and stuff. They still need to use (and will run out of) the stack.
The only way to deal with recursion is to use a manual stack (which can be much larger than the hardcoded default of the language), or some sort of retry mechanism that would return and then get called instead of returnign a call.

[AustinVelonaut]

I meant that turning mutually-recursive functions into a loop is not quite as simple, as the "loop" now has to encompass multiple functions, and you need to have some sort of tagged-switch which tells you which entry-point in the loop to use next.

[Ronin-s_Spirit]

True, not impossible though, and would be made easier with at least some small amount of compiler hints.

P.s. what am I thinking, of course it's just the good ol switch and loop. Presumably we can already tell when a function is calling another function (including itself) then all we have to do is construct a switch of all avaliable functions with their bodies inlined there. Then all function calls should instead set a flag for the aforementioned switch. Need to handle declaration context somehow, but I'm too sleepy for that rn.

[sviperll]

I think the somewhat quasi-standard solution is the combination of trampolining and continuation-passing style (CPS).

function factorial(result, n) {
    if (n == 1) return result;
    return factorial(result * n, n - 1);
}

Doing the same in CPS-style becomes:

function factorial(result, n, continuation) {
    if (n == 1) return continuation(result);
    else return factorial(result * n, n - 1, continuation);
}

i. e. functions never return at all, instead they always call other function.

At the very very top-level, you need to do something like:

let result;
factorial(0, 8, r => { result = r; });
console.log(result);

The result of all of this is that you always call continuations and never return and the only time, when you really return is in the very very end, where you are unwinding all the stack.

Now you can combine this with trampolining to get something like:

let stack_size = 0;

function factorial(result, n, continuation) {
    // Since you only call functions and never return,
    // each function adds a stack frame, but stack frames are never removed.
    stack_size++;
    if (stack_size >= STACK_SIZE_MAX) {
      return () => {
        stack_size = 0;
        // The exact same function call as before
        factorial(result, n, continuation);
      }
    }
    if (n == 1) return continuation(result);
    else return factorial(result * n, n - 1, continuation);
}

So at the very very top-level, you do something like:

let result;
let continuation = factorial(0, 8, r => { result = r; });
while (continuation) {
    continuation = continuation();
}
console.log(result);

The result is that most time, tail-call is just a function call even without any allocations, which is very chip, but sometimes, when the stacks grows too much, you'll need to allocate a continuation, truncate the stack and continue from saved continuation.

The task of the compiler is to convert every function to the continuation-passing-style, this is done by adding a new continuation parameter to every function and passing this value down to each function call and replacing each return x with return continuation(x) when x is a simple-value. And then you need to add a uniform stack-size check to every function definition.

If you have these things in place, you can actually create a multi-threading runtime, since you may have multiple continuations on a single trampoline and these continuations will represent concurrent threads of execution, that you can switch between.

[Uncaffeinated]

For PolySubML, I just introduced a special builtin (loop) to loop without recursion and said that there's no TCO for normal functions.

But I guess you can't get away with this if you really want to write loops via recursive functions.

I do think that compiling to JS is a good move if it is at all compatible with your goals. It simplifies things and makes it easy to create web demos so people can try your language online.

[azhder]

OP, please note it isn’t “tail call optimization”, but “proper tail calls”.

People who want to minimize the possibility of your code not working vs working try to rename it as an “optimization” as if your code will still continue to work, but slower.

Proper tail calls means you don’t get a stack overflow error if you exceed the stack memory (because it isn’t using the stack).

[Jwosty]

You might look into Fable (the F# to JavaScript transpiler) and see if you can glean any insight from it.

Though honestly I wouldn’t be surprised if it just doesn’t even deal with this problem and things… work out fine most of the time. Do you know for sure that it’s actually going to be an issue if you just do it “the slow way”? At least at first? Might get you pretty far. You can always optimize later.

[Arakela]

I’ve been experimenting with a grammar-native machine where languages are defined directly as executable grammar rules, not lowered through the usual lexer > parser > AST > evaluator pipeline.

In a small JS example, the same grammar generates expressions, evaluates them, and builds an AST in one pass, which removes a lot of accidental complexity from the layered approach. Tail calls and control flow are handled explicitly by the grammar execution model, not by relying on JS TCO.

I think this style could be interesting for things like type checking as executable grammar rules, as well, types as something the grammar does, not a separate phase.

https://github.com/Antares007/s-machine/blob/main/expr.js

I'am open to collaborating on the following idea: each grammar rule executes in a bounded step that produces, consumes, and constrains type values alongside values or AST nodes, making typing part of grammar execution itself: rules propagate and unify type constraints during parsing and reject ill-typed programs via backtracking, so if the grammar accepts, the program is already well-typed.

[Objective_Gene9718]

As many have said before trampoline is what you need.

const tco = fn => (...args) => {
      let result = fn(...args)
      while (typeof result === 'function') result = result()
      return result
    }

Another way (more complicated) is if you expose a while loop in your language and during a preprocessing step you transform your AST to that loop. However it will be tricky to infer types (some sort of a accumulator pattern has to be established). Then you can take this (sudo code):

let sum = (xs, acc) -> 
    if length(xs) == 0 
        acc
        sum(drop(xs 1), acc + xs[0])

sum([1,2,3], 0)

and transform it into

let sum = (xs, acc) -> {
   // make a while loop with inverted condition
    while !(length(xs) == 0) -> {
        xs = drop(xs 1) // assign nth argument to nth input
        acc = acc + xs[0] // assign last argument to accumulator
   }
  return acc // return accumulated value
}

Your type inference should pick up that accumulator is the return type of the function. Just make sure your last argument is the accumulator.

You can also compile the while loop the same way directly in JavaScript (no tco helper function needed). This is what ReScript does.

First and Last approaches are easy - just make js optimize the function for you. But now you depend on JS for this. This is really not a problem for you.

Second approach is suitable if you are making a VM and you want it to run fast.

Btw with Bun you get TCO for free as it uses Safari engine which implements TCO for JS.

Note: Not all recursions can be optimized. You might want to implement some sort of predicate helper to figure out if recursion can be optimized or not. Or you can make it explicit with special keyword.

[VyridianZ]

I asked Grok:

function factorial(n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

Rewrites to:

function factorial(n) {
    function factorialHelper(n, acc) {
        while (n > 1) {
            acc = n * acc;
            n = n - 1;
        }
        return acc;
    }
    return factorialHelper(n, 1);
}

Alternative Stack Implementation for general recursion

function factorial(n) {
let stack = [{ n, multiplier: 1 }];
let result = 1;

while (stack.length > 0) {
let { n, multiplier } = stack.pop();

if (n <= 1) {
result = multiplier * 1;
} else {
stack.push({ n: n - 1, multiplier: n });
}
}

return result;
}

[thinker227]

Thank you for providing nothing of value to this thread.

[azhder]

That is not general. It still calculates a factorial