[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Proper tail recursion
- From: Roberto Ierusalimschy <roberto@...>
- Date: Thu, 26 Jul 2001 16:52:07 -0300
> 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
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...).