Subject: RE: processing character entities From: DPawson@xxxxxxxxxxx Date: Wed, 28 Jul 1999 09:05:29 +0100 |
A couple of simple examples would be very much appreciated here David C. TIA, DaveP David Carlisle wrote: >> So what, exactly, is the defining feature of tail recursion? > It seems >> to me that the second form involves passing a larger and >larger result >> object into the recursion, possibly with a new copy each >time. Now, I >> can see how that won't happen if the loop's execution is optimized, >> but I am really an assembly programmer in disguise, and don't like to >> assume magical optimization by some other entity. If someone can >> assure me that this is, indeed, The Lisp Way (preferably with an >> explanation of why), I'll deal with it, but I'd like to understand >> what's going on before I re-write a whole lot of code. >> > >In your first version, the recursive call happened _inside_ an >expression, that is bad, even though syntactically it looked to be at >the end, tail recursion implies structuring things the other way, as in >your second version. > >In a non tail recursive call the lisp engine has to maintain a >stack of all >the local state of the function, so that it is available when the >recursive call returns. > >In a tail recursive call then the body is typically some sort of if >construct, with each branch either not recursing, or being a single >recursive call, typically with all the interesting stuff happening in >the arguments. Any system dealing with recursion is supposed to >`notice' that structure and convert it essentially to a loop, without >the overhead of stacking the local state as it can never be used as >there is nothing else to do at that level once the recursive call >returns. Without tail recursion optimisation you can't really do any >looping without hitting some stack limit so it is fairly safe to assume >that it happens. >Some languages mandate that it happens, I can't remember off hand if >dsssl does. > > >David > > > DSSSList info and archive: http://www.mulberrytech.com/dsssl/dssslist > DSSSList info and archive: http://www.mulberrytech.com/dsssl/dssslist
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: processing character entities, Russell Steven Shawn | Thread | Re: processing character entities, Brandon Ibach |
Re: How to find a procedure given a, Brandon Ibach | Date | RE: If xsl replaces dsssl, then may, Pieter Rijken |
Month |