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

classic Classic list List threaded Threaded
38 messages Options
12
Reply | Threaded
Open this post in threaded view
|

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

John D. Ramsdell-3
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

Reply | Threaded
Open this post in threaded view
|

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

John Belmonte-2
John D. Ramsdell wrote:
> 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.

I don't agree about the "far more" part... if Lua had full lexcial scoping,
my existing programs would immediately benefit as I could remove all those
ugly manual closures I build with tables.  Newcomers to Lua wouldn't have to
struggle with the mystery of upvalues.

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

Previously I had written a page of notes about Lua's scoping issues
(http://lua.swiki.net/13).  By your definition, if !set was removed from
Scheme the resulting language would not be lexcially scoped.  Granted Lua's
lexical scoping is severely limited, but it is lexical scoping.  Note that
Python just added lexcal scoping to the language, and it does not allow
rebinding just like Lua's upvalues.

-John



Reply | Threaded
Open this post in threaded view
|

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

Reuben Thomas-4
> I don't agree about the "far more" part... if Lua had full lexcial scoping,
> my existing programs would immediately benefit as I could remove all those
> ugly manual closures I build with tables.  Newcomers to Lua wouldn't have to
> struggle with the mystery of upvalues.

Hear hear. IMO lexical scoping would have a greater immediate beneficial
effect, as it both simplifies the language for newbies and makes
encapsulation easier for experts. Tail recursion might be more useful to
some, but its lack is more work-aroundable.

-- 
http://sc3d.org/rrt/
L'art des vers est de transformer en beautés les faiblesses (Aragon)


Reply | Threaded
Open this post in threaded view
|

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

John D. Ramsdell-3
In reply to this post by John Belmonte-2
John,

I went to http://lua.swiki.net/13 and read your page, and then
followed the reference it contains to a definition of lexical scope.
I quote from the link:

   In a lexically scoped language, the scope of an identifier is fixed
   at compile-time to be the smallest block (begin/end or
   function/procedure body) containing the identifier's
   declaration. This means that an identifier declared in some block
   is only accessible within that block and from procedures declared
   within it.

This definition is consistent with the one I gave, and also implies
that Lua is not lexically scoped.  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 those variables.

I don't understand your comment about how omitting set! from Scheme
would change the scoping rules of Scheme.  Even without set!, a Scheme
inner-function has access to the variable bindings in the function in
which it is defined.  

There are many good texts that describe lexical scoping.  I happen to
be looking at "Structure and Interpretation of Computer Programs", by
Harold Abelson and Gerald Jay Sussman, second edition, page 30, at
this time.  It's a good source of information on this subject.

Enjoy,

John

"John Belmonte" <[hidden email]> writes:

(snip)

> Previously I had written a page of notes about Lua's scoping issues
> (http://lua.swiki.net/13).  By your definition, if !set was removed from
> Scheme the resulting language would not be lexcially scoped.  Granted Lua's
> lexical scoping is severely limited, but it is lexical scoping.  Note that
> Python just added lexcal scoping to the language, and it does not allow
> rebinding just like Lua's upvalues.
> 
> -John


Reply | Threaded
Open this post in threaded view
|

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

John Belmonte-2
I understand Lua programs much better than scoping lingo.  Lua upvalues
cannot be said to be lexically scoped because the following program prints
"5" instead of "10"?

    do
        local a = 5
        local foo = function() print(%a) end
        a = 10
        foo()
    end



Reply | Threaded
Open this post in threaded view
|

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

John D. Ramsdell-3
"John Belmonte" <[hidden email]> writes:

> I understand Lua programs much better than scoping lingo.  Lua
> upvalues cannot be said to be lexically scoped because the following
> program prints "5" instead of "10"?
> 
>     do
>         local a = 5
>         local foo = function() print(%a) end
>         a = 10
>         foo()
>     end

Correct.  Statements inside the function bound to foo in the do block
cannot access its local variable a.  If it could, a function bound to
foo could be written that accesses the value of a and then prints it,
in this example displaying "10".  In Lua, the current binding of a
local variable is hidden from any function defined within the scope of
the local variable.  This is a problem only if the binding is changed
between the time at which the closure for the function is created, and
the time at which the function is executed.

John


Reply | Threaded
Open this post in threaded view
|

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

Nick Trout-2
----- Original Message -----
From: "John D. Ramsdell" <[hidden email]>|
| Correct.  Statements inside the function bound to foo in the do block
| cannot access its local variable a.  If it could, a function bound to
| foo could be written that accesses the value of a and then prints it,
| in this example displaying "10".  In Lua, the current binding of a
| local variable is hidden from any function defined within the scope of
| the local variable.  This is a problem only if the binding is changed
| between the time at which the closure for the function is created, and
| the time at which the function is executed.

So Lua is not lexically scoped because a) Upvalues only go up one level and b)
upvalues force a closure?

Does that mean that Python (2.2) is not lexically scoped either because it also
forces a closure? (but can look right to the outer level)
http://python.sourceforge.net/peps/pep-0227.html

So in order for a language to be truly lexically scoped rebinding must take
place on an assignment?

I have quite a limited knowledge of the practicalities but lexical scoping (and
the removal of upvalues) of the type employed in Python would be nice. ie.
closure at execution time.

Puzzled,
Nick




Reply | Threaded
Open this post in threaded view
|

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

John D. Ramsdell-3
"Nick Trout" <[hidden email]> writes:

> Does that mean that Python (2.2) is not lexically scoped either
> because it also forces a closure? (but can look right to the outer
> level) http://python.sourceforge.net/peps/pep-0227.html

I'm quite puzzled by the description of Python's new scoping rule, but
here is my best guess as to what it is saying: A local variable that
is referenced by one or more functions defined within the block in
which the local variable is defined cannot be changed.  In Lua terms:
the following code is illegal because local a cannot be modified since
it is referenced by the function bound to foo:

    do
        local a = 5
        local foo = function() print(a) end
        a = 10   -- Illegal under Python rules!
        foo()
    end

Even though this rule is more restrictive that Lua's rule, Python DOES
provide lexical scoping as functions defined within a block have
access to all the bindings made in the block.

John

Reply | Threaded
Open this post in threaded view
|

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

Nick Trout-2
----- Original Message -----
From: "John D. Ramsdell" <[hidden email]>
| I'm quite puzzled by the description of Python's new scoping rule,

You're not the only one!

| but here is my best guess as to what it is saying: A local variable that
| is referenced by one or more functions defined within the block in
| which the local variable is defined cannot be changed.  In Lua terms:
| the following code is illegal because local a cannot be modified since
| it is referenced by the function bound to foo:
|
|     do
|         local a = 5
|         local foo = function() print(a) end
|         a = 10   -- Illegal under Python rules!
|         foo()
|     end
|
| Even though this rule is more restrictive that Lua's rule, Python DOES
| provide lexical scoping as functions defined within a block have
| access to all the bindings made in the block.

It does say that it was Guidos (none too popular) decision to do this. The
workaround is to put the value of a in a container table and access this. I
think this is what John Belmonte does?

     do
         local a = {5}
         local foo = function() print(%a[1]) end
         a[1] = 10   -- Now legal for Python!
         foo()
     end

Since the "global" keyword is to be added in v4.2(?) what about a "static"
keyword so you could do lexical scoping? (as you suggest)

eg.
  function a()
    local b = 1
    static c = 2
    local d = function()
      print(b) -- cant do
      print(c) -- can do
    end
  end
  a()

Or: why not retain upvalues for fast immediate outer scope access and instead of
generating an error for locals not found perform a lexical scope search then.
This would be compatible with current functioning code (I think). Then you have
the option.

N





Reply | Threaded
Open this post in threaded view
|

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

Roberto Ierusalimschy
In reply to this post by John D. Ramsdell-3
> I was not pleased to see the claims made on pages 22 and 45, that Lua is
> lexically scoped.

I will correct that on page 22. On page 45, as you already quoted, I do not 
say that Lua is lexically scoped, but that it "has a form of proper lexical 
scoping through upvalues". The key point here is that, in a (pure)
functional language, variables do not change values, so semantically there 
is no difference whether I am accessing the variable itself or a copy.
Therefore, I can trivially translate any "program" from Lambda calculus to
Lua (assuming eager evaluation).


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

I thought about that. The problem is to change the design of the 
bytecode... Currently, most instructions have direct access to local 
variables (like any other temporary value). So, it seems that we need 
either to give instructions direct access also to "unlocal" variables (and 
therefore make them more complex and slow), or to generate extra 
instructions to more values between "unlocal" variables and temporaries 
(which involves moving code around, correcting jumps, correcting debug 
information, and other nasty detais...) 

As I said before, I really want lexical scoping in Lua, but programs that 
do not use it should not pay for it. 

An easy solution (but very ugly, I admit) would be to have a different 
declaration for locals that must be accessible by inner functions... 
(Something like "statically_scoped_local x" ;-)

-- Roberto

Reply | Threaded
Open this post in threaded view
|

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

David Jeske-3
In reply to this post by Reuben Thomas-4
On Fri, Jul 27, 2001 at 02:07:54PM +0100, Reuben Thomas wrote:
> Hear hear. IMO lexical scoping would have a greater immediate
> beneficial effect, as it both simplifies the language for newbies
> and makes encapsulation easier for experts. 

I appreciate any effort to make Lua simpler and more
functional. However, I want to point out a few things.

First, this mailing list is composed of language nuts who are
embeddeding lua, so I'm sure most of us are familiar with scoping
styles and recursion. However, from what I know the primary "newbie"
of Lua is NOT a user on this list. Lua is a simple embedded scripting
and configuration language, thus most "newbies" who write Lua code (by
configuring or extending something which has Lua embedded) really
don't know what lexical scoping is, and would struggle to make a
recursive function which terminated.

Second, most of us on this mailing list used lua for a year or two
before it even had upvalues and found it quite useful. In the current
project I have Lua embedded in I only use upvalues for subtle
performance reasons, and don't need full lexical scoping. 

I would be far happier if I had a mechanism for making my class system
have more bearable syntax. However, I recognize the likely-hood of Lua
ending up with the meta-syntax mechanisms that I think would go so
well with it's meta-language mechanisms is about zero. :)

-- 
David Jeske (N9LCA) + http://www.chat.net/~jeske/ + [hidden email]

Reply | Threaded
Open this post in threaded view
|

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

John D. Ramsdell-3
In reply to this post by Roberto Ierusalimschy
A language is either lexically scoped or it is not.  Adding the
adjective "proper" to the phrase "lexical scoping" is meaningless.
Adding the adjective "true" to the phrase "lexical scoping" is
meaningless.  Languages such as Algol, Pascal, Ada, Scheme, and Python
2.2+ (I suspect) are lexically scoped, while languages such as C,
Fortran, AWK, Elisp, and Lua as of 4.0 are not lexically scoped.

Roberto Ierusalimschy <[hidden email]> writes:

> > I was not pleased to see the claims made on pages 22 and 45, that
> > Lua is lexically scoped.
> 
> I will correct that on page 22. On page 45, as you already quoted, I
> do not say that Lua is lexically scoped, but that it "has a form of
> proper lexical scoping through upvalues".

My point was that since Lua is not lexically scoped, it does not have
a form of proper lexical scoping, whatever that means.  Lua is
statically scoped with local and global variable references, and a
construct that gives Lua programmers some of the benefits of lexical
scoping while allowing efficient implementations of the language.

By the way, the more I think about the suspected Python method for
making that language lexically scoped, the more I like it.  That is, I
like the idea that a language is lexically scoped, but as sacrifice to
allow efficient implementations, variables become immutable whenever
they are referenced by a closure.  This language design is in the
spirit of Lua's simplicity, and would allow the complexities of
upvalues to be purged from the language.

John

Reply | Threaded
Open this post in threaded view
|

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

John Belmonte-2
John D. Ramsdell wrote:
> By the way, the more I think about the suspected Python
> method for making that language lexically scoped, the more
> I like it.  That is, I like the idea that a language is lexically
> scoped, but as sacrifice to allow efficient implementations,
> variables become immutable whenever they are referenced
> by a closure.  This language design is in the spirit of Lua's
> simplicity, and would allow the complexities of upvalues
> to be purged from the language.

If you read the Python lexical scoping PEP, it states that the rebinding
limitation is due to Python's default local semantics (that is, its lack of
variable declarations).  It doesn't seem to have been for performance
reasons.



Reply | Threaded
Open this post in threaded view
|

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

Jay Carlson
In reply to this post by John D. Ramsdell-3
[John works down the hall from me, but I haven't commuted yet...]

John Ramsdell writes:

| while languages such as C,
| Fortran, AWK, Elisp, and Lua as of 4.0 are not lexically scoped.

C looks lexically scoped to me.  There aren't nested functions/functions as
values.  What am I missing?

Jay


Reply | Threaded
Open this post in threaded view
|

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

Philippe Lhoste
In reply to this post by John D. Ramsdell-3
John D. Ramsdell wrote:
> A language is either lexically scoped or it is not.  Adding the
> adjective "proper" to the phrase "lexical scoping" is meaningless.
> Adding the adjective "true" to the phrase "lexical scoping" is
> meaningless.  Languages such as Algol, Pascal, Ada, Scheme, and Python
> 2.2+ (I suspect) are lexically scoped, while languages such as C,
> Fortran, AWK, Elisp, and Lua as of 4.0 are not lexically scoped.

I though that I understood what "lexically scoped" means, but I am not sure
anymore.
Why C isn't lexically scoped? Is it because you can't define functions
inside functions, like in Pascal or Ada? (I don't know the other languages.)

> By the way, the more I think about the suspected Python method for
> making that language lexically scoped, the more I like it.  That is, I
> like the idea that a language is lexically scoped, but as sacrifice to
> allow efficient implementations, variables become immutable whenever
> they are referenced by a closure.  This language design is in the
> spirit of Lua's simplicity, and would allow the complexities of
> upvalues to be purged from the language.

Still trying to learn (the easy way ;-):
What do you mean by "referenced by a closure"?
Actually, I am not sure to understand what a closure is. But I suppose it is
like the upvalues: a view on the values of variables at function evaluation
(by parser? by VM?) time.
Then, referenced by a closure should be eg. the upvalue syntax.

How wrong am I?
Sorry to interrupt by stupid questions, but when I studied computer science
(some fifteen years ago), nobody told me about functional programming and
such. I hardly had a look at Lisp and Prolog by then...

Regards.

-- 
--._.·´¯`·._.·´¯`·._.·´¯`·._.·´¯`·._.·´¯`·._.·´¯`·._.--
Philippe Lhoste (Paris -- France)
Professional programmer and amateur artist
http://jove.prohosting.com/~philho/
--´¯`·._.·´¯`·._.·´¯`·._.·´¯`·._.·´¯`·._.·´¯`·._.·´¯`--

Sent through GMX FreeMail - http://www.gmx.net


Reply | Threaded
Open this post in threaded view
|

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

Jay Carlson
In reply to this post by John D. Ramsdell-3
John Ramsdell writes:

> By the way, the more I think about the suspected Python method for
> making that language lexically scoped, the more I like it.  That is, I
> like the idea that a language is lexically scoped, but as sacrifice to
> allow efficient implementations, variables become immutable whenever
> they are referenced by a closure.

This gives me the creeps.  To understand whether something is writable or
not you can't just look at its declaration; you have to inspect all of the
code inside its defining block.  As you pointed out to me on Friday, the
compiler can figure this out at compile time, but it's hard to explain to
people.

The way I think about Lua functions, btw, is that they are layer of sugar on
top of making apply-able tables, with the contents of the table consisting
of varname=initializer references, where the varnames come from all the
%upvars, and only the %upvars, mentioned in the body.  Is this a good thing?
I dunno.  The only way to make the sugar thinner is to require explicit
declaration of the %upvars as part of the function syntax, something like
"function (a1,a2) copying %uv1, %uv2 [...] end". This starts dancing around
the issue of first class environments....

Jay


Reply | Threaded
Open this post in threaded view
|

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

Reuben Thomas-4
In reply to this post by Philippe Lhoste
> I though that I understood what "lexically scoped" means, but I am not sure
> anymore.

Yes, I think some confusion has arisen.

As I understand it, "lexical" scoping is a term used in opposition to
"dynamic" scoping, i.e. whether an identifier's value arises from its inmost
enclosing textual definition (as in C, Pascal &c.), or from its most
recently executed enclosing function (as in LISP, BBC BASIC &c.).

Example:

function a()
  local x = 2
  c()
end

function b()
  local x = 1
  c = function ()
    print(x)
  end
end

Under dynamic scoping, the example above will print 2, because x's local
definition scopes dynamically over a's callees. Under lexical scope it'll
print 1, because x is bound by the textual (lexical) enclosing definition in
b().

Of course Lua allows neither at the moment, because local variables are not
visible inside function definitions (except via upvalues). Nevertheless, Lua
is lexically scoped: you can tell because if you run the simpler example:

function a()
  local x = 2
  b()
end

x = 1
function b()
  print(x)
end

you get 1, because a's x is not visible in b.

What proponents of "full lexical scoping" are really asking for might be
better described as "full closures", i.e. closures in which the free
variables are not fixed (but only bound) at instantiation time, and in which
you don't need special syntax to access them.

-- 
http://sc3d.org/rrt/ | Academics age by degrees


Reply | Threaded
Open this post in threaded view
|

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

Jay Carlson
In reply to this post by John D. Ramsdell-3
David Jeske writes:

> I would be far happier if I had a mechanism for making my class system
> have more bearable syntax. However, I recognize the likely-hood of Lua
> ending up with the meta-syntax mechanisms that I think would go so
> well with it's meta-language mechanisms is about zero. :)

What does your class system look like?  What help do you need from the
syntax?  Do you need reader macros, or can you get away with runtime
interpretation?

I've seen some places where it would be nice to have symbol-like strings,
strings with a surface syntax that makes them look like identifiers.  Like
:foo or foo: or something like that, sugar for "foo".  Except those break
the grammar in Lua, and I can't think of any nice looking alternatives.  I
suppose they don't have to be strings; easy enough to make them opaque.  But
so far I've managed to live without them, and I'm not sure I see the
advantage of adding a one-off feature relative to the complexity costs.

Jay


Reply | Threaded
Open this post in threaded view
|

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

Peter Prade
In reply to this post by Jay Carlson
Jay Carlson comments on John Ramsdell:
>> By the way, the more I think about the suspected Python method for
>> making that language lexically scoped, the more I like it.  That is, I
>> like the idea that a language is lexically scoped, but as sacrifice to
>> allow efficient implementations, variables become immutable whenever
>> they are referenced by a closure.
>This gives me the creeps.  To understand whether something is writable or
>not you can't just look at its declaration; you have to inspect all of the
>code inside its defining block.

I wholeheartedly agree, the current solution at least clearly marks those
upvalues as something special and readonly.

In my personal opinion, the current solution of upvalues in lua is quite
sufficient.
The only thing i'd like to see is upvalues from more than 1 level above:

local var
function level1()
  function level2()
    print(%var) -- or, as an uglier solution: print(%%var)
  end
  ...
end

currently, you have to propagate such values by hand:

local var
function level1()
  local _var = %var
  function level2()
    print(%_var)
  end
  ...
end

just my 2 (euro)cents,
Peter


Reply | Threaded
Open this post in threaded view
|

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

John D. Ramsdell-3
In reply to this post by Jay Carlson
"Jay Carlson" <[hidden email]> writes:

> C looks lexically scoped to me.  There aren't nested functions/functions as
> values.  What am I missing?

C's lack of nested functions is exactly why C is not lexically scoped.
A variable reference refers to either a local or a global value, a
popular choice for language implementors because of its ease of
implementation.  I'm sure you know that C can be compiled into very
efficiently code.

John

12