lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


> > So this is what tail calls are for. This means that there is no
threat
> > of stack overflow in a state machine like you suggest, is there? I
> > certainly couldn't get stackoverflow in my quick test based on two
> > functions calling each other. No memory growth either! Very sweet.
> 
> That's the meaning of *proper* in "proper tail calls".  (Usually
people
> call this "proper tail recursion", I guess because it is kind of
boring
> without recursive calls.)
> 
> Notice that you only get this behavior when you do tail calls. In Lua,
> this means "return f(...)".  None of these apparently equivalent forms
> works:

How very interesting. I didn't know that either. From
(http://www.cs.oberlin.edu/classes/dragn/labs/control/control410.html)
:-

	"1. A proper tail recursive call to G never returns to its
caller F, yet the computation can proceed as though it had. 

	2. From the point of view of control, a proper tail recursive
call is equivalent to a goto."

I guess you don't need to retain the local stack because the call is the
last thing that is done in the function and it doesn't require any of
the variables as soon as the call is made.

More info (the above statement in CS mumbo jumbo):
http://www.swiss.ai.mit.edu/cgi-bin/info2www?(r5rs)Proper%20tail%20recur
sion

--Nick (mmmm must add note to tutorial)