Re: closures

[Michael Bevilacqua-Linn <michael.bevilacqualinn@gmail.com>]

While HOP probably does a better job of explaining closures than I do...

When someone says that a language 'has closures', what they generally seem to mean is that the language has first-class functions (usually, more accurately, procedures since most practical languages allow side effects, but that distinction doesn't seem to be made much) that 'close over' their surrounding scope.  

A first-class function (or procedure) means that there's a facility in the language that allows you to create procedures at execution time, store a reference to them in a variable, basically treat them as you would any other piece of data that your program is working with.  

Like I mentioned above, the 'closure' refers to the procedure 'closing over'* the scope that it was created in, which just means that the free variables in the procedure are bound in the environment that existed when the closure was created.  This sounds impressive and hard to grok, but it's actually pretty clear with an example, so let's see if I can fit one in here.

Let's say we have the following psuedocode, in a language that allows nested procedure definitions.

defproc outerProcedure(){
  def x = 1
  def y = 1
  print "In outerProcedure"
  print x
  print y
  
  defproc innerProcedure(){
      def y = 2
      print "In innerProcedure"
      print x
      print y
    }
}

An easy way to visual the lexical scope as this program executes is as a linked list of symbol tables.  When x and y are defined in outerProcedure, they're placed into a symbol table along with their values.  When innerProcedure executes, a new symbol table is created and y is placed in that symbol table (along with its new value).  This second table also contains a link back to the table for outerProcedure.

To look up the value that a variable is bound to at any given point in the program, start at the bottom-most symbol table and see if there's a binding for the variable, and then work your way up the chain.  So in this case, in innerProcedure, we'd get a value of 2 for y and 1 for x, just like we'd expect.  

So a closure is a structure that contains not only the procedure that you've created, but a way to get at the scope it was defined in.  I tend to think of it as having not only the chunk of code, but a linked list of symbol tables like I described above (though I can't imagine that's how it's implemented anywhere outside of CS class...)  You can then pass this structure around, add new layers of scope to it, etc.  

So while C function pointers and closures may serve the same purpose some of the time (you could probably use either to, say, pass a sorting algorithm into a procedure), closures are a lot more powerful, and can help lead to better factored code.  Since they carry their scope with them, you can be a lot more sure that some piece of code a hundred thousand lines away hasn't reached in and mucked with some of your state.  

Also, HOP is worth a browse even for non perl people (like myself).

Thanks,
MBL

* I've never been able to figure out what, if any, this has to do with mathematical closures.  I think the term might just be overloaded?

On Mon, Mar 15, 2010 at 4:35 PM, <mjd-phillylambda@plover.com> wrote:

> So I'd like to test my understanding with this group...
>
>       int x;
>
>       void foo(int x);
>       void baz(void (*F)(void));
>
>       void callback(void)
>       {
>               foo(x);
>       }
>
>       void bar(void)
>       {
>               baz(&callback);
>       }
>
> C doesn't "support" closures, but the code above has one.

Only in a trivial sense.  C doesn't support nested function scopes, so
in C one can't construct an interesting example of closures or of
their failure in C.  I wanted to construct a C example for you, but
none of my constructions made sense as C.

To not-answer your question:

> The above is a closure, if you could do such a thing in C.

I think the only thing you could usefully do with this question is to
unask it.  Trying to understand closures by studying the non-behavior
of the nonexistent closures of C is pointless.

If you like Perl, I suggest that you read chapter 3 of "Higher-Order
Perl", available for free download at:

       http://hop.perl.plover.com/

I think the explanation there is both clear and rigorous.

If you like some other language that has closures, I suggest you ask
for an example in that language.

If you only like C, I suggest you either forget about closures
(because C doesn't have them) or learn to like some language that does
have them.

> The word closure
> is used here because we create an instance of foo() over which x is "closed".
>
> Do I have it right so far?

No:

* You have not created an instance of foo, or indeed of anything.
 Functions always have static duration in C.  Instances of functions
 are created at compile time, and not afterward.

* The jargon is that the function is closed over the variable, not the
 other way around.

> I would appreciate it if someone could propose a few problems which
> are trivial to solve with closures, but difficult without.

a. Implement an object-oriented programming system.  Closures make
  adequate objects.  This is discussed in detail in _Structure and
  interpretation of Computer Programs_, should you want to know more.

b. Almost anything in _Higher-Order Perl_; see the table of contents.