Re: Closure of lexical environment in Scheme closures

["Dr. Rich Artym" <rartym@...>]

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