On 11/12/2018 10:45 AM, Rudi C wrote:
How is mutual recursion via a loop any better than mutual recursion
just by tail call elimination?
You can't necessarily turn recursion into a loop using only TCE.
TCE turns an ordinary call/return sequence into a non-returning jump [or
fall through for inline code] to the target function. In the recursive
it jumps back to the "start" of the function [for some definition of
"start"].
But there's a catch: you can't just overwrite the current stack frame
with your new one because, typically, you need information from the
current frame *while* constructing the new one ... in particular, you
need to evaluate the recursive call arguments. So how much trouble TCE
and TRO represent depend crucially on how you implement your stack.
If you allocate the stack as a linked list on the heap, then there is
little difference between a tail call and a normal one - in either case
you allocate a new frame but a TC links the new frame to its grandparent
instead of its parent, and the parent frame is unlinked and discarded.
The downsides to this stack strategy are that stack frames come and go
rapidly, and having to handle them puts more pressure on the garbage
collector. Moreover using C (or other conventional language) libraries
becomes more complicated if you aren't using the CPU's own hardware stack.
If you implement your stack as an array [the classic mark/release
allocation strategy] then you can use the CPU's hardware stack, but in
this case a tail call is very different from a normal one. The
arguments to the call often can't be evaluated directly into the
positions where the function code expects them to be, so you need
additional memory to stage the evaluations before moving the resulting
values into place.
Additionally, to implement TRO with an array stack, you may need to
generate ad hoc code to initialize the loop, and ad hoc code to update
loop variables and reenter the loop as necessary.
[There is a trick involving CPS code in which the CPU's hardware stack
is abused by allocating frames but never deallocating them - iow calling
functions but never returning from them. When the stack grows to some
predetermined extent, you copy the top frame back to the base of the
stack and reset the stack pointer, effectively deallocating all the
discarded stack frames at once. This has many of the same benefits as
allocating the stack on the heap, with the additional benefit that it
mixes well with use of conventional libraries. The problem is, it plays
hell with fetch prediction mechanisms that expect conventional
call/return code of rather limited depth - so code using this trick
often executes more slowly than more conventional call/return code.]
In a mutual recursion case, the transformation to a loop may subsume
many functions, and there may be multiple branching recursive execution
paths. The analysis required to identify and fuse mutually recursive
functions into one "super" function that can be made self recursive is
possible, but in the general case it is very difficult to do.
PS: Why do web-servers need CPS?
In general they don't. However, being a Scheme, Racket supports
arbitrary use of continuations, and the web-server framework allows the
handler for a given URL to be the persisted continuation of another URL.
Persisting a continuation involves saving the entire state of the
ongoing computation - in particular, it means saving the call/return
stack which is needed to continue executing from the save point. In CPS
code, the stack state consists of just one frame - the current one -
rather than an arbitrary number of frames. So, in general, in CPS code
a continuation requires far less memory to persist.
That is why #lang web-server converts programs to CPS. If your code
doesn't make heavy use of *general* continuations (co-routines), or
threads with continuations, or need to persist continuations for
arbitrarily long periods, then using the web-server language buys you
very little [in trade for much longer compilations].
George
--
You received this message because you are subscribed to the Google Groups "Racket
Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
