Re: processing character entities

[Brandon Ibach <bibach@xxxxxxxxxxxxxx>]

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