Tail call optimization

JavaScript does not (yet) support tail call optimization. To circumvent this limitation, and mitigate stack overflows, the Js_of_ocaml compiler optimize some common tail call patterns.

Self tail recursive

Self tail recursive function are compiled into a loop.

OCaml

let rec fact x acc =
  if x = 0
  then acc
  else fact (pred x) (acc * x)

JavaScript

function fact(x,acc){
  var x$0=x,acc$0=acc;
  for(;;){
    if(0===x$0) return acc$0;
    var acc$1=caml_mul(acc$0,x$0),
        x$1=x$0-1|0,
        x$0=x$1,
        acc$0=acc$1;
    continue
  }
}

Mutually tail recursive functions

Mutually tail recursive functions are compiled using a trampoline. Note that the generated code does not return to the trampoline at every recursive call to prevent too much slow down.

OCaml

let rec even n =
  match n with
  | 0 -> true
  | x -> odd (x-1)
and odd n =
  match n with
  | 0 -> false
  | x -> even (x-1);;

JavaScript

function even$0(counter,n){
  if(0===n)return 1;
  var _e_=n-1|0;
  if(counter<50){
    var counter$0=counter+1|0;
    return odd$0(counter$0,_e_)
  }
  return caml_trampoline_return(odd$0,[0,_e_])
}
function odd$0(counter,n){
  if(0===n)return 0;
  var _d_=n-1|0;
  if(counter<50){
    var counter$0=counter+1|0;
    return even$0(counter$0,_d_)
  }
  return caml_trampoline_return(even$0,[0,_d_])
}
function even(n){return caml_trampoline(even$0(0,n))}
function odd(n){return caml_trampoline(odd$0(0,n))}

Examples of pattern not optimized

Recursive function where the tail call is made inside an intermediate function.

let rec f x =
  let g delta = f (x - delta) in
  if x < 0 then 0
  else if x mod 2 = 0
  then g 2
  else g 1;;

Tail call of a function given as argument

let bind x f =
  match x with
  | None -> None
  | Some x -> f x

Note that in the future, more tail call optimizations could be perform with function specialization and better inlining.