Making Lua lexically scoped (was: Re: Proper tail recursion)

["John D. Ramsdell" <ramsdell@...>]

Roberto wrote:

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

The trick I have seen somewhere in a Scheme implementation is to
design the bytecode so that it can be easily backpatched in this
situation.  As the compiler moves forward through the source, it
maintains enough information about every local variable so as to allow
the changes required to move a local variable into the heap when it is
discovered that the variable is accessed by an inner-function.
Unfortunately, I cannot remember what implementation used this trick,
but I will query my Scheme sources to see if I can find an example of
it.

Let me say here that upvalues are not all that bad as long as they are
treated as what they are: a wart added to the language so as to make
the language easier to implement efficiently.  I think focusing
efforts on making the Lua bytecode interpreter properly tail recursive
is far more important that simplifying the Lua language by making it
lexically scoped.

By the way, I read the December 27, 2000 draft of the book on Lua.  I
was not pleased to see the claims made on pages 22 and 45, that Lua is
lexically scoped.  On page 45, you wrote that Lua functions "...have a
form of proper lexical scoping through upvalues".  Lexical scoping is
discipline for resolving variable references based on block
structure.  With lexical scoping, a reference to a variable within a
block refers to the binding defined is the nearest enclosing block.
In Lua, an inner-function does not have access to the local variables
in the function in which it is defined, it only has access to a copy
of the variables.  Therefore, Lua is not lexically scoped.

Also, Chapter 7 of the book, titled "More About Functions" fails to
note that upvalues are really a wart added to the language so as to
make the language easier to implement efficiently.  Instead, it tries
to promote upvalues as a feature of the language!  Upvalues are a
reasonable engineering trade-off, but that does not change a wart into
feature.

John