Is it theoretically possible to transform every kind of general-recursion into tail-recursion? Are they equivalent for example from a lambda-calculus point of view? That's a debate between me and an acquaintance.
My view is that it's not possible everytime. For example if you have a function which calls itself recursively twice or three times, then you can't make all the recursive calls into tail-calls, right? Or is there always a way to reduce the number of recursive calls to one single recursive call?
2 Answers 2
You should be able to do it using continuation passing style.
In CPS, each function takes an explicit continuation function which represents the rest of the computation. Instead of returning a value directly, a function in CPS passes the result to the continuation instead.
For example if you had the following Tree
data type:
type Tree = Empty | Node of Tree * int * Tree
and you wanted to sum the values, you could write function to sum the left and right subtrees in turn:
let rec sum_cps t f =
match t with
| Empty -> f 0
| Node(l, v, r) -> sum_cps l (fun lv ->
sum_cps r (fun rv -> f (lv + v + rv)))
let sumT t = sum_cps t (fun i -> i)
You can do that transformation using Continuation Passing Style.
Read for instance A.Appel Compiling with Continuations book
Intuitively, you replace -after CPS transformation- (nearly) each call frame of the call stack with a heap-allocated continuation frame (or "closure" when viewing continuations as functions). (so you might not win much: the avoided stack frames are replaced by garbage collected continuation frames).
See also Appel's old paper: garbage collection can be faster than stack allocation
(which might be less true today, perhaps because of cache issues)
-
Oh course the downside is that you build lots and lots of closures (the continuations). It's not a good way to improve performance or memory use.user7043– user70432014年07月17日 19:09:10 +00:00Commented Jul 17, 2014 at 19:09
Explore related questions
See similar questions with these tags.