Closure of lexical environment in Scheme closures

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

Closure of lexical environment in Scheme closures

Dr. Rich Artym
Here's an example of a Scheme function capturing the state of its
environment at the point of closure, blocking further modification.

I've tried to replicate the conditions under which our example Lua
program showed sensitivity to environment change, although it's hard
to create exactly the same conditions in a purely functional program.

; ------------------------------------------------------------
; Demonstration of Scheme lexical scoping and function closure

; Gentle intro example without functions
(let* ((foo
            10)
       (bar
            65))
     foo)                       ; prints 10
)

; Defines and applies function incfoo1 using free variable foo
(let* ((foo                     ; define foo
            10)
       (incfoo1                 ; define incfoo1
            (lambda () (+ foo 0.1)))
       (bar                     ; define bar
            65))                ; bar not used (just for symmetry)
     (incfoo1))                 ; prints 10.1

; Defines and applies function incfoo1 using free variable foo
; but overrides (foo 10) with (foo 20) before function is used.
(let* ((foo
            10)
       (incfoo1
            (lambda () (+ foo 0.1)))
       (incfoo2
            (let* ((foo         ; Let's change foo (as in Lua)
                       20))     ; to try to make incfoo1 use 20.
                  incfoo1))     ; Will this closure be affected?
                  
       (bar
            65))
     (incfoo2))     ; No, prints 10.1 because incfoo1 is a closure
                    ; which protects it against the change in foo
; ----------------------------------------------------------------

That was a bit of a quickie.  I'll try to find a closer approximation.

Rich Artym.
-- 
Existing media are so disconnected from reality that our policy debates
spin around a fantasy world in which the future looks far too much like
the past.   http://www.zyvex.com/nanotech/MITtecRvwSmlWrld/article.html


Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Aaron Brown-2
Rich Artym wrote:

  ; Defines and applies function incfoo1 using free variable foo
  ; but overrides (foo 10) with (foo 20) before function is used.
  (let* ((foo
              10)
         (incfoo1
              (lambda () (+ foo 0.1)))
         (incfoo2
              (let* ((foo         ; Let's change foo (as in Lua)
                         20))     ; to try to make incfoo1 use 20.
                    incfoo1))     ; Will this closure be affected?
                    
         (bar
              65))
       (incfoo2))     ; No, prints 10.1 because incfoo1 is a closure
                      ; which protects it against the change in foo
  ; ----------------------------------------------------------------

A Lua equivalent of that is the following, which acts the
same way:

  do
    local foo = 10
    local incfoo1 = function()
                      return foo + 0.1
                    end -- incfoo1
    local incfoo2 = function()
                      local foo = 20 -- Changing a new foo in
                        -- a different scope; doesn't affect
                        -- incfoo1.
                      return incfoo1()
                    end -- incfoo2
    local bar = 65
    print(incfoo2()) -- Prints 10.1 because Lua is lexically scoped.
  end

Instead of thinking of 'local' as being like one of the
versions of 'let' (I can never remember which version is
which), think of the space between the 'do' and the 'end' as
being the 'let', and the individual 'local's are like
different variables being set within the same 'let'.

-- 
Aaron



Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Aaron Brown-2
I posted a Scheme program and an equivalent Lua program
earlier.  Here are improved versions.  (As I said, I'm not
fluent in Scheme, so they might not be exactly equivalent,
but they're close enough for our purposes.)

  ;; Scheme version:
  (define func nil)
  (let ((foo 'bar))
    (set! func (lambda ()
                    foo))
    (set! foo 'baz)) ;; Alters the foo within func.
  ;; Outside the 'let':
  (define foo 'quux) ;; If this were a 'set!', we'd get an
                     ;; error.
  (func) ;; Returns baz.

  -- Lua version:
  do
    local foo = "bar"
    function func()
      return foo
    end -- func
    foo = "baz" -- Alters the foo within func.
  end
  -- Outside the 'do' block:
  foo = "quux" -- This is global, but even if it had 'local'
    -- in front of it, the 'foo' inside 'func' is still
    -- unreachable.
  print(func()) -- Prints "baz"

Remember that every Lua program is one 'chunk' -- that is,
it's surrounded by an implicit 'do' block, kind of like
being in a giant 'let'.  (Or 'let*' or 'letrec' or
whatever.)

-- 
Aaron




Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Matt Hellige
In reply to this post by Aaron Brown-2
[Aaron Brown <[hidden email]>]
> 
> Instead of thinking of 'local' as being like one of the
> versions of 'let' (I can never remember which version is
> which), think of the space between the 'do' and the 'end' as
> being the 'let', and the individual 'local's are like
> different variables being set within the same 'let'.
> 

Yeah, comparing Lua's
  x = y
to "let" in Lisp or Scheme as totally wrong. Assignment in Lua is a
destructive update, like 'set!' in Scheme.

To translate 'let*' to lua, you need to use multiple scopes (i.e.,
multiple do...end blocks). To see how lua's lexical scoping behavior
exists also in Scheme, you need to use set!, as in the following:

    (define x 5)
    (define (inc-x)
     (set! x (+ x 1))
      (display x)(newline))

    (display x) ;; prints 5
    (newline)
    (inc-x)     ;; prints 6
    (display x) ;; prints 6
    (newline)
    (set! x 10)
    (display x) ;; prints 10
    (newline)
    (inc-x)     ;; prints 11
    (display x) ;; prints 11
    (newline)

(I've tried to dot the i's and cross the t's, to leave no room for
equivocation.) 

The proof is in the pudding:

    [mhellige: mhellige]$ guile -s foo.scm
    5
    6
    6
    10
    11
    11
    [mhellige: mhellige]$ 

Here's the precisely equivalent lua code:

    do
      local x = 5
      function inc_x()
        x = x + 1
        print(x)
      end

      print(x)
      inc_x()
      print(x)
      x = 10
      print(x)
      inc_x()
      print(x)
    end
 
and the proof:

    [mhellige: mhellige]$ lua foo.lua
    5
    6
    6
    10
    11
    11
    [mhellige: mhellige]$ 

Matt

-- 
Matt Hellige                  [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Brian Casiello-2
In reply to this post by Aaron Brown-2
On Thu, 11 Nov 2004 15:27:48 -0500, Aaron Brown
<[hidden email]> wrote:
> Rich Artym wrote:
> 
> 
> 
>   ; Defines and applies function incfoo1 using free variable foo
>   ; but overrides (foo 10) with (foo 20) before function is used.
>   (let* ((foo
>               10)
>          (incfoo1
>               (lambda () (+ foo 0.1)))
>          (incfoo2
>               (let* ((foo         ; Let's change foo (as in Lua)
>                          20))     ; to try to make incfoo1 use 20.
>                     incfoo1))     ; Will this closure be affected?
> 
>          (bar
>               65))
>        (incfoo2))     ; No, prints 10.1 because incfoo1 is a closure
>                       ; which protects it against the change in foo
>   ; ----------------------------------------------------------------
> 
> A Lua equivalent of that is the following, which acts the
> same way:
> 
>   do
>     local foo = 10
>     local incfoo1 = function()
>                       return foo + 0.1
>                     end -- incfoo1
>     local incfoo2 = function()
>                       local foo = 20 -- Changing a new foo in
>                         -- a different scope; doesn't affect
>                         -- incfoo1.
>                       return incfoo1()
>                     end -- incfoo2
>     local bar = 65
>     print(incfoo2()) -- Prints 10.1 because Lua is lexically scoped.
>   end
> 
> Instead of thinking of 'local' as being like one of the
> versions of 'let' (I can never remember which version is
> which), think of the space between the 'do' and the 'end' as
> being the 'let', and the individual 'local's are like
> different variables being set within the same 'let'.
> 
> --
> Aaron
> 

That's equivalent to the lua code I came up with as a translation of
the scheme. I think the point is that the
>               (let* ((foo         ; Let's change foo (as in Lua)
>                          20))     ; to try to make incfoo1 use 20.
in the scheme creates a new binding to foo, unrelated to the one
created by  the prior
>   (let* ((foo
>               10)
It doesn't assign a new value to the old foo.
So, what if the scheme were changed to 
>   ; Defines and applies function incfoo1 using free variable foo
>   ; but overrides (foo 10) with (foo 20) before function is used.
>   (let* ((foo
>               10)
>          (incfoo1
>               (lambda () (+ foo 0.1)))
(set! foo 12) ; assign a new value to the above bound foo
>          (incfoo2
>               (let* ((foo         ; Let's change foo (as in Lua)
>                          20))     ; to try to make incfoo1 use 20.
>                     incfoo1))     ; Will this closure be affected?
> 
>          (bar
>               65))
>        (incfoo2))     ; No, prints 10.1 because incfoo1 is a closure
>                       ; which protects it against the change in foo

and the lua to

>   do
>     local foo = 10
>     local incfoo1 = function()
>                       return foo + 0.1
>                     end -- incfoo1
foo = 12 -- assign a new value to the above bound foo
>     local incfoo2 = function()
>                       local foo = 20 -- Changing a new foo in
>                         -- a different scope; doesn't affect
>                         -- incfoo1.
>                       return incfoo1()
>                     end -- incfoo2
>     local bar = 65
>     print(incfoo2()) -- Prints 10.1 because Lua is lexically scoped.
>   end
> 

In that case, lua prints 12.1. What would scheme do? (WWSD ;-) I don't
have a scheme interpreter handy, but I suspect it would print 12.1 as
well.

-- 
Brian
"Clarifying the water with just a little more mud!"

Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Dr. Rich Artym
In reply to this post by Aaron Brown-2
On Thu, Nov 11, 2004 at 03:54:36PM -0500, Aaron Brown wrote:

> I posted a Scheme program and an equivalent Lua program
> earlier.  Here are improved versions.  (As I said, I'm not
> fluent in Scheme, so they might not be exactly equivalent,
> but they're close enough for our purposes.)
> 
>   ;; Scheme version:
>   (define func nil)
>   (let ((foo 'bar))
>     (set! func (lambda ()
>                     foo))
>     (set! foo 'baz)) ;; Alters the foo within func.
>   ;; Outside the 'let':
>   (define foo 'quux) ;; If this were a 'set!', we'd get an
>                      ;; error.
>   (func) ;; Returns baz.

Guile is not valid Scheme, since Scheme made the set! syntactic keyword
illegal because it broke closure encapsulation.  This is *precisely*
the issue --- if Scheme is our reference on this particular issue then
we're illegally modifying our Lua closures.

I gave some history on this in the old (slightly hijacked) thread, so
I'll repeat it here where it's more relevant:

||  Admittedly it used to be legal in older versions of Scheme (up to 5c4),
||  and then Scheme r4rs referred to it as a "compatible extension but not
||  a compliant implementation" of Scheme (lol, Scheme had a lot of politics
||  in those days).  And finally they bit the bullet and simply made it
||  illegal Scheme starting from r5rs.  Scheme's always tried to move in
||  the direction of lambda calculus purity.
||  
||  The Guile folks chose to be non-compliant on this point because they
||  needed the functionality of such a construct, which is fair enough.

Although Scheme makes a good reference, one should note too that there
are many other implementations of closures in functional programming,
and the property of creating pure functions is an absolutely key one.

It's what allows referential transparency --- Main Property #1 !! :-)

Rich Artym.
-- 
Existing media are so disconnected from reality that our policy debates
spin around a fantasy world in which the future looks far too much like
the past.   http://www.zyvex.com/nanotech/MITtecRvwSmlWrld/article.html


Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Brian Casiello-2
On Thu, 11 Nov 2004 21:23:31 +0000, Dr. Rich Artym
<[hidden email]> wrote:
> On Thu, Nov 11, 2004 at 03:54:36PM -0500, Aaron Brown wrote:
> 
> 
> 
> > I posted a Scheme program and an equivalent Lua program
> > earlier.  Here are improved versions.  (As I said, I'm not
> > fluent in Scheme, so they might not be exactly equivalent,
> > but they're close enough for our purposes.)
> >
> >   ;; Scheme version:
> >   (define func nil)
> >   (let ((foo 'bar))
> >     (set! func (lambda ()
> >                     foo))
> >     (set! foo 'baz)) ;; Alters the foo within func.
> >   ;; Outside the 'let':
> >   (define foo 'quux) ;; If this were a 'set!', we'd get an
> >                      ;; error.
> >   (func) ;; Returns baz.
> 
> Guile is not valid Scheme, since Scheme made the set! syntactic keyword
> illegal because it broke closure encapsulation.  This is *precisely*
> the issue --- if Scheme is our reference on this particular issue then
> we're illegally modifying our Lua closures.
> 
> I gave some history on this in the old (slightly hijacked) thread, so
> I'll repeat it here where it's more relevant:
> 
> ||  Admittedly it used to be legal in older versions of Scheme (up to 5c4),
> ||  and then Scheme r4rs referred to it as a "compatible extension but not
> ||  a compliant implementation" of Scheme (lol, Scheme had a lot of politics
> ||  in those days).  And finally they bit the bullet and simply made it
> ||  illegal Scheme starting from r5rs.  Scheme's always tried to move in
> ||  the direction of lambda calculus purity.
> ||
> ||  The Guile folks chose to be non-compliant on this point because they
> ||  needed the functionality of such a construct, which is fair enough.
> 
> Although Scheme makes a good reference, one should note too that there
> are many other implementations of closures in functional programming,
> and the property of creating pure functions is an absolutely key one.
> 
> It's what allows referential transparency --- Main Property #1 !! :-)
> 
> 
> 
> Rich Artym.
> --
> Existing media are so disconnected from reality that our policy debates
> spin around a fantasy world in which the future looks far too much like
> the past.   http://www.zyvex.com/nanotech/MITtecRvwSmlWrld/article.html
> 
> 

So it's the fact that assigments (i.e. set!) are allowed, not the
closure issue (since closures are handled the same way as scheme),
that make lua not a purely functional language?

-- 
Brian
"Seeking understanding through stupid questions"

Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Matt Hellige
[Brian Casiello <[hidden email]>]
> 
> So it's the fact that assigments (i.e. set!) are allowed, not the
> closure issue (since closures are handled the same way as scheme),
> that make lua not a purely functional language?
> 

Yes, basically. Scheme is also most emphatically *not* a purely
functional language, since it provides set! and many side-effecting
i/o operations. Scheme, Standard ML and friends are usually considered
"mostly-functional" languages, since they encourage programming in a
functional style, but rely on non-referentially transparent operations
at a basic level. 

For a much more rigorous (and quite beautiful, although challenging)
attempt to enforce a purely functional style, take a look at Haskell.
Be aware, though, that it's designers titled a relatively recent talk
"Wearing the Hair Shirt: a Haskell Retrospective," so it's not all
roses in purity-land... ;)

Matt

-- 
Matt Hellige                  [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Dr. Rich Artym
In reply to this post by Brian Casiello-2
On Thu, Nov 11, 2004 at 04:33:28PM -0500, Brian Casiello wrote:

> So it's the fact that assigments (i.e. set!) are allowed, not the
> closure issue (since closures are handled the same way as scheme),
> that make lua not a purely functional language?

Oh I don't think so, since Lua has never been described as a purely
functional language, or at least I've never heard anyone suggest that.

It's only the implementation of closures that gives me any worry here,
since closures are meant to create pure functions out of impure ones.
After all, that's what's being closed, the impact of the rest of the
universe on the function.

If the semantics of a function can be made to change by modifying the
values of its non-local and non-argument variables then those variables
haven't been closed, and you don't have a closure, you just have an
ordinary function with unclosed state.

Rich Artym.
-- 
Existing media are so disconnected from reality that our policy debates
spin around a fantasy world in which the future looks far too much like
the past.   http://www.zyvex.com/nanotech/MITtecRvwSmlWrld/article.html


Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Jamie Webb-3
On Thu, Nov 11, 2004 at 09:58:31PM +0000, Dr. Rich Artym wrote:
> On Thu, Nov 11, 2004 at 04:33:28PM -0500, Brian Casiello wrote:
> 
> > So it's the fact that assigments (i.e. set!) are allowed, not the
> > closure issue (since closures are handled the same way as scheme),
> > that make lua not a purely functional language?
> 
> Oh I don't think so, since Lua has never been described as a purely
> functional language, or at least I've never heard anyone suggest that.

Indeed.

> It's only the implementation of closures that gives me any worry here,
> since closures are meant to create pure functions out of impure ones.

And this I think is the problem with your argument, which sounded
quite reasonable at first: you're taking a definition from the purely
functional world and relating it to impure functions. How exactly, in
a pure functional language could one possibly have an un-closed
function? The notion simply makes no sense, because there is no
possibility of modifying any environment.

Your argument seems to be equivalent to saying that Lua variables
aren't proper variables because you can modify them. Naturally, the
addition of impure language features requires the modification of
these definitions, and claiming that Lua doesn't have lexical scoping
just because it doesn't match a purely functional definition of such
seems pointless.

> After all, that's what's being closed, the impact of the rest of the
> universe on the function.

Possibly the word 'closure' could be considered out-of-context in an
impure setting, but again that just depends on how you interpret it.

> If the semantics of a function can be made to change by modifying the
> values of its non-local and non-argument variables then those variables
> haven't been closed, and you don't have a closure, you just have an
> ordinary function with unclosed state.

Could you please define 'ordinary function'? And explain where that
definition came from?

-- Jamie Webb

Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Dr. Rich Artym
On Thu, Nov 11, 2004 at 11:01:08PM +0000, Jamie Webb wrote:

> > If the semantics of a function can be made to change by modifying the
> > values of its non-local and non-argument variables then those variables
> > haven't been closed, and you don't have a closure, you just have an
> > ordinary function with unclosed state.

> Could you please define 'ordinary function'? And explain where that
> definition came from?

Sure.  Lots of definitions coming up.

I wasn't using any esoteric meaning of "ordinary".  We were talking about
closures as one very special (or at least specially named) kind of function,
so I used "ordinary function" simply to mean anything that isn't a closure.

After all, the word "closure" must mean something, otherwise why bother
using it?  The plain unadorned word "function" would do just fine, if one
is not referring to a closure.  So, let's assume that a "closure" is the
special kind of function that 30+ years of literature has called a closure.

And what exactly is that?

-------------------------------------------------------------------------
Well, I guess Guy Steele and Gerald Sussman really ought to know, as the
authors of Scheme and of a ton of academic papers on related subjects:

***  http://c2.com/cgi/wiki?TransactionClosureObject ==>

"Closure - a closure is a function that captures the lexical environment
in which it was created."

That's right, captures the environment, ie. a set of {name, value} tuples,
and not a set of {name, address-of-cell} tuples.  Big difference! :-)

-------------------------------------------------------------------------
***  http://c2.com/cgi/wiki?LexicalClosure ==>

"A lexical closure is, first of all, an object--just like a string, integer,
list and so on. It's a special object that is constructed from a piece of
the program itself, when it evaluates a special notation. That notation
specifies an anonymous piece of code that can take arguments, and is in
fact an anonymous function. The anonymous function is a component of the
closure object, but not the only component. The other component of the
object is the lexical environment: a snapshot of all of the current
bindings of all of the local variables which are visible at that point."

Aha!  So, it takes a snapshot of all of the current bindings of all of
the local variables in the lexical environment.  Sounds clear to me.
The bindings of the variables are the values of the variables, not the
addresses that the names point to.  I sure hope nobody's disputing that.

-------------------------------------------------------------------------
***  http://en.wikipedia.org/wiki/Closure_(computer_science) ==>

"In programming languages, a closure is an abstraction representing a
function, plus the lexical environment (see static scoping) in which the
function was created, and its application to arguments. A closure results
in a fully closed term: one with no free variables left."

"Closures are typically implemented with a special data structure that
contains a pointer to the function code, plus a representation of the
function's lexical environment (i.e., the set of available variables and
their values) at the time when the function was created."

Great.  Note the "fully closed term: one with no free variables left", and
the "... and their values) at the time when the function was created".

-------------------------------------------------------------------------
***  http://wiki.cs.uiuc.edu/VisualWorks/Closures ==>

"For our purposes we can define a closure as the combination of a function-
procedure (some code that takes zero or more arguments, may have side-effects,
and returns a result) with an environment (a set of bindings from names to
values, or in Smalltalk's case from names to objects). The environment is the
set of name-value pairs of the free variables within the function-procedure.
Within some scope a free variable is a variable that is not bound within that
scope, i.e. that within some scope there is no declaration of that variable.
The name "Closure" comes from the terminology that the function-procedure
"closes-over" its environment, capturing the current bindings of its free
variables."

Multiple/varied explanations of the same idea:  capture of the ***current***
(name, value) pairs for each of the free variables in the unclosed function.

-------------------------------------------------------------------------
***  TI Scheme manual (Texas Instruments, my original prized copy):

"A procedure object, or "closure", is created by the evaluation of the LAMBDA
special form.  Since procedure objects must be able to access the bindings
in effect at the time of their creation, the environment in effect at that
time is "closed over" (preserved with the object) for future use.

When a closure is applied to a set of arguments, references to free identifier
in the body of the closure are resolved using the environment preserved with
the closure (the environment of the definition)."

Again, pretty clear, despite the early days.

TI Scheme was a very early and seminal precursor of the standards-based
Schemes that came long after, but you can already see the key ideas that
would end up in its big brothers after a decade or two.  No surprise there,
since Friedman, Abelson and Sussman + Indiana/MIT Scheme groups defined it.

-------------------------------------------------------------------------
***  Ake Wikstrom - Functional programming Using Standard ML ==>

"10.2 Semantics of Functions -- Closures.  When evaluating a function
application, we have to start with the environment valid when defining
the function and extend it with the bindings to the parameters.  Hence,
for any function declaration, we have to remember not only the function
expression, but also the environment valid at the time of declaration,
that is, we have to bind the name of the function to a closure.  The
reason it is called a "closure" is that an expression containing free
variables is called an "open" expression, and by associating to it the
bindings of its free variables, you close it."  (Then gives an example
showing the binding of the free variable "y" in a function being closed
using the binding {y = 3} from its environment.)

So crystal clear it really needs no comment.

Wikstrom was from the large ML group at Chalmer U in Sweden, and writes
very clearly.  I used this book a lot both for research and teaching.

-------------------------------------------------------------------------
These are just arbitrary pickings off the net and from LISP/Scheme/FP
books on my shelf.  If I had the time or energy I'm sure I could pick out
another 1,000+ such quotes, because they're all unanimous;  this is not
an area where there is any dispute, although the form of words varies.

So, where are we ....  You write:

> Possibly the word 'closure' could be considered out-of-context in an
> impure setting, but again that just depends on how you interpret it.

You may be right.  Unfortunately, there is only one way of interpreting
it that makes it different from "ordinary function with free variables",
because the definition of "free variable" is extremely precise across an
immense and undisputed amount of published literature on the subject.

And therein lies the problem.  We're using the term "closure" for a Lua
functional object which very testably has free variables in functions
which, if they were closures, would have hardwired them in to the closed
object that is the closure.  If they haven't done this, then they haven't
performed any closure.  I'm repeating myself, but this is so obvious that
it's hard to say anything at all about it without doing so.

In summary:  Lua "closures" aren't closures, they're "ordinary functions"
containing variables which have not been closed, ie. with free variables.
This isn't me being picky.  It's simply that they do not fulfil the most
important property required of any closure, which is to be closed.

Incidentally, Lua "closures" could be made into real closures, either by
making their free (non-local) variables immutable after closure, or by
taking a private copy of each of them.  I have my doubts that copying is
viable in the presence of tables, but immutability might be.  On the
other hand, a more pragmatic solution would be to drop the word "closure"
altogether and just accept Lua as a great language on its own merits.

Rich Artym.
-- 
Existing media are so disconnected from reality that our policy debates
spin around a fantasy world in which the future looks far too much like
the past.   http://www.zyvex.com/nanotech/MITtecRvwSmlWrld/article.html


Reply | Threaded
Open this post in threaded view
|

RE: Closure of lexical environment in Scheme closures

Quinn Tyler Jackson
> Aha!  So, it takes a snapshot of all of the current bindings of all of
> the local variables in the lexical environment.  Sounds clear to me.
> The bindings of the variables are the values of the variables, not the
> addresses that the names point to.  I sure hope nobody's disputing that.

OK. I've been following this topic.

What is the expected output of the following snippet if the function
returned by get_function is a closure?

k = 0;

function n(x)
   k = k + 1;
   return x + 10;
end

function get_function(x, y)
     return
	     function (y)
		    z = n(x);
		 end;
end

f = get_function(100, 100);

f(100);
f(110);

print ("n called " .. k .. " times");

--
Quinn Tyler Jackson
http://members.shaw.ca/qjackson/


Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Dr. Rich Artym
On Thu, Nov 11, 2004 at 10:11:34PM -0800, Quinn Tyler Jackson wrote:

> What is the expected output of the following snippet if the function
> returned by get_function is a closure?
> 
> k = 0;
> 
> function n(x)
>    k = k + 1;
>    return x + 10;
> end
> 
> function get_function(x, y)
>      return
> 	     function (y)
> 		    z = n(x);
> 		 end;
> end
> 
> f = get_function(100, 100);
> 
> f(100);
> f(110);
> 
> print ("n called " .. k .. " times");

Quinn, I can answer that without even looking at the declaration of
get_function() nor its call nor the two applications of f().  The
reason is that nothing touches "k" except function n(), and therefore
if n() were actually closed in respect of its free variable k then its
internal closed "k" would refer to an entirely different "k" than the
final print statement reads and prints out.

Consequently, if Lua created genuine closures, your code would print out:

                         n called 0 times

Here in Lua it doesn't, instead it finds that k has a value of 2 because
n(x) was called twice and hence it incremented its free (not closed)
variable k twice.

The example above doesn't attempt to make use of any closed internal k
that a Lua with closures might have created.  To do so, it would need
to use the k in its output expression, eg. "return x + 10 * k;".  This
k would be bound tightly to function n for the full lifetime of n, so
you could invoke n() repeatedly and the closed k would keep incrementing.

That's not the outer k though.  The outer k merely sets the value of the
initial closed k in the closure.  Or I should say, "would" set it. :-)

Rich Artym.
-- 
Existing media are so disconnected from reality that our policy debates
spin around a fantasy world in which the future looks far too much like
the past.   http://www.zyvex.com/nanotech/MITtecRvwSmlWrld/article.html


Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Mark Hamburg-4
In reply to this post by Dr. Rich Artym
To your quotes I will throw back Sussman's _Structure And Interpretation of
Computer Programs_ which shows all sorts of things that you can build
because closures capture variables rather than values. (It covers a lot of
other things but review Chapter 3, Modularity, Objects, and State.

The closure part has to do with the fact that unlike dynamic scoping,
evaluating the function won't go looking for the variable again. The
implementation determines which variable a token corresponds to at the time
the function is constructed based on the lexical scope of the token. A
function captures it's environment at the time it is created and that
environment is based on the lexical arrangement of code rather than the
dynamic arrangement. That environment provides a mapping from variables
names to values.

Mark


Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

David Given
In reply to this post by Matt Hellige
On Thursday 11 November 2004 21:37, Matt Hellige wrote:
[...]
> For a much more rigorous (and quite beautiful, although challenging)
> attempt to enforce a purely functional style, take a look at Haskell.
> Be aware, though, that it's designers titled a relatively recent talk
> "Wearing the Hair Shirt: a Haskell Retrospective," so it's not all
> roses in purity-land... ;)

My university was very keen on theory, and they taught us Haskell.

It's a beautiful language. It's simple, and subtle, and very elegant, and 
allows you do all kinds of interesting things with computer programs except, 
unfortunately, writing useful ones in a reasonable amount of time.

For those of you who don't know Haskell: it's a functional language quite 
similar to ML, and its main claim to fame is that no functions have side 
effects. *Ever.* This includes I/O. If you call a function with a particular 
set of parameters, you know that it will return the same result every time. 
*Always.* This provides a number of benefits, including the ability to do 
lazy evaluation: it now no longer matters when functions are actually 
executed, so the interpreter only executes them when it absolutely has to.

When trying to write useful programs in Haskell, the biggest stumbling block 
is I/O. What you actually write is a function that takes as an argument a 
stream of I/O events and returns a new stream of I/O events. Your function 
lazily pulls events off the input stream, and the run-time lazily pull events 
off the output stream. The result works but is, from the imperative 
programmer's point of view, a ghastly mess: you end up having to pass I/O 
streams about all over the place. Adding a simple printf statement in the 
depths of your logic code can require you to rearrange the parameters for a 
hundred different functions. There's syntactic sugar to make this easier, but 
it's still a pain.

If you want more information, look here:

 http://www.haskell.org/tutorial/io.html

-- 
+- David Given --McQ-+ 
|  [hidden email]    | "The further you are from your server, the more
| ([hidden email]) | likely it is to crash." --- Woodhead's law
+- www.cowlark.com --+ 

Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Dr. Rich Artym
In reply to this post by Mark Hamburg-4
On Fri, Nov 12, 2004 at 12:22:54AM -0800, Mark Hamburg wrote:

> To your quotes I will throw back Sussman's _Structure And Interpretation of
> Computer Programs_ which shows all sorts of things that you can build
> because closures capture variables rather than values. (It covers a lot of
> other things but review Chapter 3, Modularity, Objects, and State.
> 
> The closure part has to do with the fact that unlike dynamic scoping,
> evaluating the function won't go looking for the variable again. The
> implementation determines which variable a token corresponds to at the time
> the function is constructed based on the lexical scope of the token. A
> function captures it's environment at the time it is created and that
> environment is based on the lexical arrangement of code rather than the
> dynamic arrangement. That environment provides a mapping from variables
> names to values.

Thanks Mark, that's another good quote to make exactly the same point I
was making:  "A function captures it's environment at the time it is
created" ... and "That environment provides a mapping from variables
names to values", ie. very specifically not a mapping from names to
addresses of variable cells.

What Sussman is saying so very explicitly is very very key:  the (name,value)
pairs for each free variable in the open functional expression are "captured"
when the closure is made (it's not an arbitrary choice of words), because it's
precisely that capture that allows us to consider the resulting composite
functional object (function + state) as a closed function, one without any
to-be-evaluated dependencies apart from its lambda-bound function arguments.

In Scheme and related languages, the captured FV state data in the closure
still looks like the original environment from which the closure was made,
but that's just an implementation detail.

In other implementations of the same concept of closures the data may be
copied out from the lexical state directly into the closure space in a
copy-based interpreter, or the free variable references may be rewritten
with the defining expressions in a rewrite system, or new independent data
packets are created for the FV references in the open expression in a
dataflow-based system.  And there are many other approaches too, all
yielding exactly the same thing:  to turn what used to be free variables
into a new state invariant logically hardwired into the closed onject.  

The benefits of that closure are enormous, and that's why closures were
invented of course, otherwise we could have just continued using plain
old functions with free variables instead.  Closures give us referential
transparency, which in turn gives the ability to use the closed functions
in parallel computation without being sensitive to the order of evaluation,
they allow us to lazy-evaluate since closures are not dependent on the
time of evaluation relative to their environment, and in general they
allow allow us to reason mathematically with them as pure functions ---
and that's not just a benefit for theorists (I'm an engineer) because
it's just as good for writing game AI as for MIT theorem solvers.

Think I'll stop there. :-)

Rich Artym.
-- 
Existing media are so disconnected from reality that our policy debates
spin around a fantasy world in which the future looks far too much like
the past.   http://www.zyvex.com/nanotech/MITtecRvwSmlWrld/article.html


Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Jamie Webb-3
In reply to this post by Dr. Rich Artym
On Fri, Nov 12, 2004 at 05:47:16AM +0000, Dr. Rich Artym wrote:
> On Thu, Nov 11, 2004 at 11:01:08PM +0000, Jamie Webb wrote:
> > Could you please define 'ordinary function'? And explain where that
> > definition came from?
> 
> Sure.  Lots of definitions coming up.

None of them the one I asked for...

> I wasn't using any esoteric meaning of "ordinary".  We were talking about
> closures as one very special (or at least specially named) kind of function,
> so I used "ordinary function" simply to mean anything that isn't a closure.

That's not a definition. So I'll assume we mean "value-returning,
possibly side-effecting subroutine", since that's the only way this
discussion seems to make sense. Notice that this is nothing like the
mathematical definition. It has none of the nice properties of the
mathematical definition. And you're (presumably) quite happy to use
it. So why is 'closure' sacred?

> After all, the word "closure" must mean something, otherwise why bother
> using it?  The plain unadorned word "function" would do just fine, if one
> is not referring to a closure.  So, let's assume that a "closure" is the
> special kind of function that 30+ years of literature has called a closure.

<snip lots of mostly inapplicable definitions>

> You may be right.  Unfortunately, there is only one way of interpreting
> it that makes it different from "ordinary function with free variables",
> because the definition of "free variable" is extremely precise across an
> immense and undisputed amount of published literature on the subject.

'Free variable' may be well-defined, but 'variable' is defined
differently in the pure and impure worlds.

> And therein lies the problem.  We're using the term "closure" for a Lua
> functional object which very testably has free variables in functions
> which, if they were closures, would have hardwired them in to the closed
> object that is the closure.

I think you're having trouble with the semantics of imperative
languages. In a functional language, an environment is a mapping from
names to values. In an imperative language, an environment is a
mapping from names to mutable memory locations. So the environment
/is/ closed, it just contains mutable variables. Just as when you
close over reference cells in ML or subsequently use set! in Scheme.

> If they haven't done this, then they haven't
> performed any closure.  I'm repeating myself, but this is so obvious that
> it's hard to say anything at all about it without doing so.

It's obvious given a pure functional language.

> In summary:  Lua "closures" aren't closures, they're "ordinary functions"
> containing variables which have not been closed, ie. with free variables.
> This isn't me being picky.  It's simply that they do not fulfil the most
> important property required of any closure, which is to be closed.

The problem is that you're assuming that closures imply referential
transparency, because the definitions that you insist on taking from
the functional world assume that. Referential transparency is not a
property that Lua (or indeed any other imperative language) has.
Period. Even if locals behaved as you want, there would still be
globals, tables, and the OS.

As I said, one might decide that closures are defined always to be
referentially transparent, though others would disagree, but claiming
the same about lexical scoping (and throwing in references to dynamic
scoping, which is very different), is just plain wrong.

-- Jamie Webb

Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Mark Hamburg-4
In reply to this post by Dr. Rich Artym
on 11/12/04 5:19 AM, Dr. Rich Artym at [hidden email] wrote:

> On Fri, Nov 12, 2004 at 12:22:54AM -0800, Mark Hamburg wrote:
> 
>> To your quotes I will throw back Sussman's _Structure And Interpretation of
>> Computer Programs_ which shows all sorts of things that you can build
>> because closures capture variables rather than values. (It covers a lot of
>> other things but review Chapter 3, Modularity, Objects, and State.
>> 
>> The closure part has to do with the fact that unlike dynamic scoping,
>> evaluating the function won't go looking for the variable again. The
>> implementation determines which variable a token corresponds to at the time
>> the function is constructed based on the lexical scope of the token. A
>> function captures it's environment at the time it is created and that
>> environment is based on the lexical arrangement of code rather than the
>> dynamic arrangement. That environment provides a mapping from variables
>> names to values.
> 
> Thanks Mark, that's another good quote to make exactly the same point I
> was making:  "A function captures it's environment at the time it is
> created" ... and "That environment provides a mapping from variables
> names to values", ie. very specifically not a mapping from names to
> addresses of variable cells.
> 
> What Sussman is saying so very explicitly is very very key:  the (name,value)
> pairs for each free variable in the open functional expression are "captured"
> when the closure is made (it's not an arbitrary choice of words), because it's
> precisely that capture that allows us to consider the resulting composite
> functional object (function + state) as a closed function, one without any
> to-be-evaluated dependencies apart from its lambda-bound function arguments.

It's the pairs that are captured as in they continue to refer to the same
pairs. If that pair is visible elsewhere, however, then changes to that pair
within the function will be visible outside the function and vice-versa. No
new environment is constructed when the function is created. Instead it
retains a reference to the environment in which it was created.

This is in constrast to dynamic scoping which uses the environment in effect
when the function is called.

Lua closures work just like Scheme closures. I strongly urge you to read
chapter 3 of SICP.

Mark


Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Dr. Rich Artym
On Fri, Nov 12, 2004 at 08:15:55AM -0800, Mark Hamburg wrote:

> It's the pairs that are captured as in they continue to refer to the same
> pairs. 

Correct, and these pairs are (name,value) tuples, not (name,var-address)
tuples, which would be entirely foreign to the concept of closures.
The (name,value) pairs are in the closure so that each occurrence of
"name" can be replaced by "value" at eval time in this type of interpreter.
It simply provides one method of closing the open functional expression.

> If that pair is visible elsewhere, however, then changes to that pair
> within the function will be visible outside the function and vice-versa.

In which case you have not a closure but an ordinary open function.  And
that is *exactly* what Lua has --- my point precisely.  A closure implies
that the "value" of (name,value) pairs is not modifiable, since if it is
modified then it clearly wasn't closed.  Languages that derive from LISP
tend to use the old environmental implementation of the captured pairs
simply because it's easier.  But that is not fundamental to the concept
of closures, quite the opposite, it's just a particular implementation.

There's lots of other implementations, like I mentioned, which create the
closure in ways that guarantee that the state is closed and immutable.  It's
the basis of all that is good with closures via referential transparency.

> No new environment is constructed when the function is created. Instead it
> retains a reference to the environment in which it was created.

That's just an implementation detail.  It doesn't happen in copy-based
interpreters for example.

If yyou haven't closed the states of the free variables of the function
then you can't claim to have created a closed function, it's that simple.
What you have is still a function with free variables, not a closure.

Rich Artym.
-- 
Existing media are so disconnected from reality that our policy debates
spin around a fantasy world in which the future looks far too much like
the past.   http://www.zyvex.com/nanotech/MITtecRvwSmlWrld/article.html


Reply | Threaded
Open this post in threaded view
|

Re: Closure of lexical environment in Scheme closures

Mark Hamburg-4
set! modifies the pairs within an environment by changing the value portion
of the pair. The name is not replaced by the value, it is looked up in the
environment. Since the environment is mutable, the value associated with the
name is mutable. Since the environment may be shared with other functions,
the pair can be changed in multiple places.

Lua may not have lambda calculus closures, but it has the same closures as
Scheme. See SICP, Chapter 3. In the absence of assignment, these work just
like lambda calculus closures.

Mark


12