Is this implementation truely tail-recursive?
- by CFP
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!
