Re: Proper tail recursion

[Roberto Ierusalimschy <roberto@...>]

> Still, lua has some ugly warts, such as the lack of real lexical
> scoping as evidenced by need for upvalues.  This particular wart makes
> implementing mutually recursive local functions very ugly, but this
> subject has been fully discussed on this list, so I will not pursue
> the topic here except to say that small Scheme implementations that
> implement true lexical scoping have been available for a long time.
> The issue I would like to discuss is proper tail recursion.

I would love to see real lexical scoping in Lua, too. But I don't know how 
to implement it within our requirements. As far as I know small Scheme 
implementations are not very efficient. We need an implementation that 
keeps Lua's performance, and at the same time does not increase too much 
the complexity of the compiler (Lua uses a one-pass compiler, without any 
form of intermediate representation). ET once gave an interesting 
sugestion, where "normal" local variables live in the stack, and only local 
variables that are used by inner-functions would be allocated in the heap. 
The problem is how to generate code without knowing where a variable is 
going to live (when the compiler sees the inner function it can be too 
late...) 


Proper tail recursion is not difficult to implement, but also it is not
as simple as in Scheme. In Lua, functions may be Lua functions or
C functions: C functions cannot be called using proper tail recursion,
and only at runtime we know whether a tail call calls a Lua function.
(Also we must take care of 'function' tag methods.)

Moreover, proper tail recursion spoils debug information, does it not?
(Maybe that is not a too high price to pay...).

-- Roberto