Re: processing character entities

[David Carlisle <davidc@xxxxxxxxx>]

> 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