---------- Forwarded message --------- From: Rudi C <rudiwillalwayslove...@gmail.com> Date: Mon, Nov 12, 2018 at 11:20 PM Subject: Re: [racket-users] Does Racket support tail call elimination? To: George Neuner <gneun...@comcast.net>
Thanks! Very informative! ๐๐๐ I have some more questions but I should google them responsibly first๐ฌโบ๏ธ On Mon, Nov 12, 2018 at 10:52 PM George Neuner <gneun...@comcast.net> wrote: > > 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.
