Subject: Re: processing character entities From: Brandon Ibach <bibach@xxxxxxxxxxxxxx> Date: Tue, 27 Jul 1999 19:18:59 -0500 |
Quoting Chris Maden <crism@xxxxxxxxxxx>: > I do not understand this whole tail-recursion thing. > I *thought* I did, but Brandon's post indicates otherwise. Gotcha, again, eh? :) Being an old assembly guy myself, perhaps I can put it in "assembler terms" for you... :) I'll use x86 terms, as that is my experience. Hopefully, that won't matter too much. > I had a loop of the form: > > (let loop > ((init value)) > (if loop-is-done > null-object > (append-objects this-one > (loop change-value)))) > > I thought the key feature of tail recursion was that the recursive > call was the last thing in the loop. In fact, I've been pretty > careful to write most or all of my loops with this form. "Last thing in the loop" can be accurate, depending upon how you define "last". Perhaps a better way to say it would be "the recursive call must be the direct result of the loop". In assembler terms, you return a value by putting it in register AX, then executing a RET. The "last" thing the loop above will do before the RET will be one of two things. It will either set AX to the value bound to "null-object", or it will set AX to the result of the (append-objects) call. You see, because the loop "uses" the result of the recursive call, we have to be able to resume the caller, so we have to save its state on the stack and do a CALL. > However, Brandon suggests a loop of the form: > > (let loop > ((init value) > (result empty-object) > (if loop-is-done > result > (loop change-value > (append-objects result > this-one))))) > The "last" thing this version will do is either set AX to the value bound to "result", or it will set AX to the result of the recursive call. Sounds pretty much like the previous version, but if you think about it, the procedure that it's calling (which is itself) will also set AX and execute RET, right? And it doesn't need to do anything after that happens except execute RET itself. So, why not just rebind the parameters (modify the input registers and/or the parameters we received on the stack, in assembler) and execute a JMP, instead? That's exactly what tail-recursion optimization does. As far as the "larger and larger result" goes, the second version may pass one down, but the first version passes one up, so what's the difference? Quoting Russell Steven Shawn O'Connor <roconnor@xxxxxxxxxxxxxxxxxxxxxxxxx>: > On Tue, 27 Jul 1999, David Carlisle wrote: > > 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. > > To add to your point, The idea is to get your recursive call as the > outer-most call. This is needed because parameters are always evaluated > first. > > But with both examples the recursive call was inside an if statement, so > it isn't the outer-most call. What's up with that? > > The answer is that a few basic routines in scheme such as if don't > evaluate all their parameters first. In the case of if it evaluates its > first parameter first, then only one of the next two paramters are > evaluated. > Actually, when you get right down to it, (if) isn't even a procedure call, even though it looks like one. Neither is the style language's (make), because it doesn't evaluate its first parameter (the name of the flow object you want to create). If it did, you'd have to write (make 'element ...). It's the old "everything follows this nice, clean, elegant evaluation model. Well, everything except ..." thing that all languages must deal with. :) -Brandon :) DSSSList info and archive: http://www.mulberrytech.com/dsssl/dssslist
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: processing character entities, Daniel Speck | Thread | RE: processing character entities, Steffen Heinrich |
Re: If xsl replaces dsssl, then may, didier ph martin | Date | Re: footnotes, Brandon Ibach |
Month |