Nested funcs and "upvalues"

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

Nested funcs and "upvalues"

Mark Ian Barlow
In message <9710301707.AA01718@...> [hidden email] writes:
 > > I doubt the latter is identical to the proposed
 > > "foreach" function because of scope, although I could be wrong.
 > 
 >   The reason why Lua 3.0 doesn't have nested functions is scope. At one
 > hand, it is almost useless to be able to write a nested function without
 > access to local variables of the enclosing environment. On the  other hand,
 > it is well known the problem of "dangling references" to these variables,
 > like below:
 > 
 >     function f(x) return function (y) return x+y end end
 >
 >     a = f(4)
 >     print(a(5))   -- where/what is "x"??

I'm not sure why this is a problem. Here, you appear to be returning the
result of a function declaration as the result of the outer function.
What's the problem with making this an error, or at least making it
nil by convention. Surely the unnamed function is a local of f()?
How is this different from writing:

       function f(x) return local z end

... which is equally pointless. My question would be where/what is the
call to our unnamed function? In other languages with nested functions you
write things like:

      function f(x)
        local z = x*x
        function g(y)
          return z+y -- z looks like a free variable of g(), same as the globals
        end
        return g(4)+g(7)
      end

... and it's all statically checkable when you're compiling f() into
bytecode. You might want to mandate that the nested function be declared
as 'local function g(y)', to emphasise the point to the user. All you're
effectively doing is using your knowledge of where outer-scope locals
belonging to f() are on the stack to treat them like hidden reference
parameters passed into g().

 >   In Lua 3.1, we are proposing a solution to this problem which we have
 > called "upvalues" (don't pay much attention to the name...). An upvalue
 > is an expression of the form "%name", which is evaluated when a function
 > is *created*, and not when it is called. "name" can be any variable
 > visible at the point where the function is created, that is, a local
 > variable of the enclosing environment or a global variable. With this,
 > the above example could be written as:
 > 
 >     function f(x) return function (y) return %x+y end end
 > 
 > Now, when "f(4)" is executed, the inner function is created and the "%x" is
 > evaluated to the constant "4"; so "a" will get a function like
 > "function (y) return 4+y end", and "a(5)" will give the correct result.
 > (Notice that if you write "x+y" in the function body you get a
 > compiler error, since 'x' is out of scope; therefore it is not that
 > difficult to remember to use the '%'. On the other hand, the '%' reminds
 > that this is not an usual variable access.)

Ah, I see. This is "late binding" with a vengance! Will it be efficient
enough for practical use, with every call to f() re-creating the nested
unnamed function?

 <snip stuff on foreach>

--  Mark Ian Barlow                Non-Linear Control Consultants Ltd.
    -----------------------------------------------------------------
    [hidden email]            Voice / Fax: +44 (0)1207 562 154

Reply | Threaded
Open this post in threaded view
|

Re: Nested funcs and "upvalues"

Roberto Ierusalimschy
> Ah, I see. This is "late binding" with a vengance! Will it be efficient
> enough for practical use, with every call to f() re-creating the nested
> unnamed function?

  The implementation uses two structures, which we have called "closure" and
"proto". The "proto" keeps the static description of a function (bytecode,
debug information, etc; in short, everything but the upvalues), and it is
created once when the function is compiled (like in Lua 3.0). Then only
the closure (a small record with a reference to the proto and the upvalues)
is re-created when f() re-creates the nested function; all these closures
refer to the same proto. Therefore, the cost to create a new instance of a
function is smaller than the cost to create a table.

  Notice that, unlike other languages such as Scheme, these closures are
created only when a new function is *created*, not when it is called.
Therefore, programs that do not use nested functions will have a completely
negligible overhead (the creation of a single closure for each function it
declares). 


> I'm not sure why this is a problem. Here, you appear to be returning the
> result of a function declaration as the result of the outer function.
> What's the problem with making this an error, or at least making it
> nil by convention. Surely the unnamed function is a local of f()?

  First it is difficult to detect such "errors", since functions are first
class values. Consider:

    function f(x)
      local a = function (y) return x+y end   -- 'a' is local, so access to x
                                              -- is safe...
      ...
      g(a);  -- use OK
    end

    function g(x)
      global1 = x  -- how to detect this?
    end

  Second, and more important, there are many useful things we can do
when we are able to return nested functions with a proper environment
(that is, the "unnamed function" *not* being local). As a small example,
the following function creates "counters":

    function newcounter()
      local t = {n=0}
      local f = function () %t.n=%t.n+1; return %t.n end
      return f
    end

    c1 = newcounter(); c2 = newcounter();
    print(c1())  -- prints 1
    print(c1())  -- prints 2
    print(c2())  -- prints 1
    print(c1())  -- prints 3
    ...

  Each call to 'c1' returns a new integer, the same for 'c2', but both are
completely independent from each other (and the counter variables themselves
are completely "protected" inside the closures).

  For a much more powerful example, see:

    "Haskell vs. Ada vs. C++ vs. Awk vs. ... An Experiment in Software
      Prototyping Productivity." by Paul Hudak & Mark Jones.
     (ftp://nebula.systemsz.cs.yale.edu/pub/yale-fp/papers/NSWC/jfp.ps) 

-- Roberto