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
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...
© Stack Overflow or respective owner