An example of a tail-call that can easily be compiled to a loop is:
let sum list =
let rec loop a = function
| [] -> a
| x::xs -> loop (a+x) xs
in
loop 0 list
An example of a more tricky case which may be compiled to a loop is the following mutual recursion:
let rec even_then b n =
if n = 0 then b else odd_then (not b) (n - 1)
and odd_then b n =
if n = 1 then b else even_then (not b) (n - 1)
And this may be compiled either to a loop which uses a trampoline (or switch on the next function to run, which is a bit like a static trampoline) or to two separate functions that duplicate some code and are implemented as loops. A simple way this might get compiled is:
fn even_then_or_odd_then(which_function, b1, n1, b2, n2) {
loop {
match(which_function) {
Even => {
if n1 = 0 { return b1 }
else {
b2 = not(b1);
n2 = n1 - 1;
which_function = Odd;
}
},
Odd => { similar }
}
}
}
fn even_then(b,n) {
even_then_or_odd_then(Even, b, n, null, null)
}
...
An example of a tail-call that is hard to compile would be in a parser combinator library for example:
let parse_both p1 p2 =
fun buf pos success ->
p1 buf pos (fun pos r ->
p2 buf pos (fun pos r2 ->
success pos (r, r2)))
;;
(As I’ve written it this design has some issues but they aren’t so relevant). Here it is important to be able to tail-call a function that you take as an argument (e.g. you want the parser p2 to tail call the success callback you give it, and if you parse and arbitrary-length list you want to do it tail-recursively). Speaking more generally, general tail-calls are like a safe long-distance goto. Wasm doesn’t have goto and so a whole-program transformation (or a trampoline[1] which may have performance issues) is required to support tail-calls.
[1] A trampoline means that functions effectively return continuations except typically they call their continuations (up to some max number of times) and only occasionally return them to the trampoline (which pops everything off the stack) which immediately calls the continuation again. But implementing continuation passing style this way is pretty slow.