Re: processing character entities

Subject: Re: processing character entities
From: Daniel Speck <dspeck@xxxxxxx>
Date: Tue, 27 Jul 1999 17:35:16 -0400

Chris Maden wrote:

> I do not understand this whole tail-recursion thing.

I'll give it a shot. A recursive function is one that (directly or
indirectly) calls itself. A tail-recursive function is a recursive function
that only calls itself as the last thing it does.

>
>
> I *thought* I did, but Brandon's post indicates otherwise.  I had a
> loop of the form:
>
> (let loop
>     ((init value))
>   (if loop-is-done
>       null-object
>       (append-objects this-one
>                       (loop change-value))))

This is not tail-recursive because (append-objects ...) must wait for the
recursive call to loop to finish before it can be called. This builds up
data on the stack.

>
>
> 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.  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)))))
>
> 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.

The alternative that you provide builds up the result implicitly on the
stack instead of explicitly in a parameter. The size of the result isn't
important (both solutions eventually need to return the same result) the
way the result is constructed is what matters.

>  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.

Scheme and DSSSL are guaranteed to be properly tail-recursive, i.e., they
treat tail-recursive calls as jumps not procedure calls.

> 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.

This is indeed the Scheme/DSSSL way.

-dan

--
Daniel Speck
Bureau of National Affairs, Inc.               Voice: +1 202.452.6596
1231 25th Street, NW                             Fax: +1 202.331.5178
Washington, DC 20037                          e-mail:  dspeck@xxxxxxx



 DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist


Current Thread