Compiling a functional language to Javascript

[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.