Hello everyone!

I've come up with the following code to compute in a tail-recursive way the result of an expression such as 3 4 * 1 + cos 8 * (aka 8*cos(1+(3*4)))

The code is in OCaml. I'm using a list refto emulate a stack.

type token = 
    Num of float
  | Fun of (float->float)
  | Op of (float->float->float);;

let pop l = let top = (List.hd !l) in l := List.tl (!l); top;;
let push x l = l := (x::!l);;
let empty l = (l = []);;
let pile = ref [];;

let eval data =
  let stack = ref data in

  let rec _eval cont =
    match (pop stack) with
      | Num(n) -> cont n;
      | Fun(f) -> _eval (fun x -> cont (f x));
      | Op(op) -> _eval (fun x -> cont (op x (_eval (fun y->y))));
  in _eval (fun x->x)
;;

eval [Fun(fun x -> x**2.); Op(fun x y -> x+.y); Num(1.); Num(3.)];;

I've used continuations to ensure tail-recursion, but since my stack implements some sort of a tree, and therefore provides quite a bad interface to what should be handled as a disjoint union type, the call to my function to evaluate the left branch with an identity continuation somehow irks a little.

Yet it's working perfectly, but I have the feeling than in calling the _eval (fun y->y) bit, there must be something wrong happening, since it doesn't seem that this call can replace the previous one in the stack structure... Am I misunderstanding something here?

I mean, I understand that with only the first call to _eval there wouldn't be any problem optimizing the calls, but here it seems to me that evaluation the _eval (fun y->y) will require to be stacked up, and therefore will fill the stack, possibly leading to an overflow...

Thanks!