Rich and Strange Aeons

So I've learned that gcc/g++ do tail call optimization with the -O2 option; supposedly MS Visual Studio and clang do it when they can as well. I have tested this:

void b();
void c();

void a() {
    b();
}
void b() {
    c();
}
void c() {
    a();
}

//segfaults
void d(int &vin) {
    int v = vin;
    d(v);
}
int main() {
    //a();

    int v=0;
    d(v);
}

The 3 mutual recursive functions happily loop, when not commented out, while d() segfaults, as there are references back into the calling stack frame, so it can't be eliminated. Makes sense.

But then I tried replicating d() in ocaml:

let rec d vin =
  let v = ref (!vin) in
  d v
  ;;

d (ref 0);;

and it happily chews up CPU without any growth in memory usage, despite my attempt to break the preconditions for TCO. I wonder how. Trampolining? Or, ocaml is garbage collected, maybe it doesn't have a notion of a function stack? Or the analyzer can tell it's never going to need return values? Hmm.

I'm told (by mdl) ocaml has uniform representation, so everything's on the heap.

let rec e vin n =
  match n with
  | 0 -> !vin
  | _ -> (
    incr vin;
    let v = ref (!vin) in
    e v (n - 1);
(* v *)
    )
  ;;

print_int (e (ref 0) 2000000000);;

This still works, without even growing in memory usage. (But if you uncomment the commented line, the stack overflows right aways, as it should -- no longer a tail call.) Oh, I guess a smart GC could tell that the 'vin' won't be needed any more, and collect it in short order. Hmm, neat.

So, C++ with optimizing compilers: more functional than Python, but still outmatched.

mdl said that exception handling could cause overflow. I haven't see it yet, but

let rec d vin =
  try
    let v = ref (!vin) in
    incr vin;
    d v;
  with x -> x
  ;;

d (ref 0);;

simply returns right away, rather than looping. I don't see why. If I add print_int !vin in the middle, 116,643 1s get printed out, before it quits, with 0 exit code and no printed error.

mdl submitted

let rec definitely_kaboom () =
  try definitely_kaboom () with
    Invalid_argument _ (* won't be caught *) -> print_endline "whew";;

which does overflow.

Oh, apparently my try is catching the stack overflow exception itself! Haha. Whereas definitely_kaboom introduces the stack overhead of exception handling but doesn't catch the overflow exception.