Claus Brod: Closing in on closures (23 Feb 2006)

topic end
<!--
   * Set TOPICTITLE = Claus Brod: Closing in on closures (23 Feb 2006)
-->

<style type="text/css">
pre {background-color:#ffeecc;}
</style>

%STARTINCLUDE%
<a name="23"></a>
---+++ [[BlogOnSoftware20060223][Closing in on closures]] (23 Feb 2006)

The other day, I [[BlogOnSoftware200602#18][battled global variables]] in Lisp
by using this construct:

<pre>
(let ((globalFoo 42))
    (defun foobar1()
      (* globalFoo globalFoo))

    (defun foobar2(newVal)
      (setf globalFoo newVal))
  )
</pre>

=globalFoo= is neither declared nor bound within the functions =foobar1= or =foobar2=;
it is a _free variable_. When Lisp encounters such a variable, it will search
the enclosing code (the _lexical environment_) for a binding of the variable; in
the above case, it will find the binding established by the =let= statement, and 
all is peachy.

<tt>globalFoo</tt>'s scope is limited to the functions =foobar1= and =foobar2=;
functions outside of the =let= statement cannot refer to the variable.
But we can call =foobar1= and =foobar2= even after returning from the =let=
statement, and thereby read or modify =globalFoo= without causing a runtime
errors.

Lisp accomplishes this by creating objects called _closures_. A closure is a
function plus a set of bindings of free variables in the function. For 
instance, the function =foobar1= plus the binding of =globalFoo= to a
place in memory which stores "42" is such a closure.

To illustrate this:

<verbatim>
> (load "closure.lsp")  ;; contains the code above
T
> globalFoo     ;; can we access the variable?
*** Variable GLOBALFOO is unbound
> (foobar1)     ;; we can't, but maybe foobar1 can
1764
> (foobar2 20)  ;; set new value for globalFoo
20
> (foobar1)
400
</verbatim>

Hmmm - what does this remind you of? We've got a variable which is shared between
two functions, and only those functions have access to the variable, while outside
callers have not... he who has never tried to encapsulate data in an object shall cast
the first pointer!

<blockquote><i>
Proofreading this, I realize that the simple Lisp code example
is probably not too instructive; I guess closures really start to shine when you let functions
return anonymous functions with free variables in them. Hope to come up with
better examples in the future.
</i></blockquote>

So this is how closures might remind us of objects. But let's
look at it from a different angle now - how would we implement closures
in conventional languages?

Imagine that while we invoke a function, we'd keep its
parameters and local variables on the heap rather than on the stack, so instead
of stack frames we maintain heap frames. You could then think of a closure
as:
   * A function pointer referring to the code to be executed
   * A set of references to frames on the heap, namely references to all 
     bindings of any free variables which occur in the code of the
     function.

Because the "stack" frames are actually kept on the heap and we are therefore no
longer obliged to follow the strict rules of the hardware stack, the contents
of those frames can continue to live even beyond the scope of the executed function.

So we're actually storing a (partial) snapshot of the execution context of a function, 
along with the code of the function!

Let's see how we could implement this. The first obvious first-order
approximation is in C++; it's a function object. A function object encapsulates a function
pointer and maybe also copies of parameters needed for the function call:

<pre>
  typedef bool (*fncptr)(int, float);
  fncptr foobar_fnc; // declaration

  class FunctionObject {
  private:
    int m_i;
    float m_f;
    fncptr m_fnc;
  public:
    FunctionObject(fncptr fnc, int i, float f) : m_fnc(fnc), m_f(f), m_i(i) {}
    bool operator() { m_fnc(m_i, m_f); }
  };

  FunctionObject fo(foobar_fnc, 42, 42.0);
</pre>

=FunctionObject= captures a snapshot of a function call with its parameters.
This is useful in a number of situations, as can be witnessed by trying to enumerate
the many approaches to implement something like this in C++ libraries such as
[[http://www.boost.org][Boost]]; however, this is not a closure. We're "binding"
function parameters in the function object -  but those are, in the sense described
earlier, not _free_ variables anyway. On the other hand, if the code of the function
referred to by the =FunctionObject= _had_ any free variables, the =FunctionObject=
wouldn't be able to bind them. So this approach won't cut it.

There are other approaches in C++, of course. For example, I recently found the
[[http://www.boost.org/doc/html/lambda.html][Boost Lambda Library]] which
covers at least parts of what I'm after. At first sight, however, I'm not
too sure its syntax is for me. I also hear that GCC implements 
[[http://linuxgazette.net/112/ramankutty.html][nested functions]]:

<verbatim>
typedef void (*FNC)(void);

FNC getFNC(void)
{
  int x = 42;
  void foo(void)
  {
    printf("now in foo, x=%d\n", x);
  }
  return foo;
}

int main(void)
{
  FNC fnc = getFNC();
  fnc();
  return 0;
}
</verbatim>

Unfortunately, extensions like this didn't make it into the standards so far.
So let's move on to greener pastures. Next stop: 
[[BlogOnSoftware20060226][How anonymous delegates in C# 2.0 implement closures]].

   * [[http://www.franz.com/support/documentation/6.2/ansicl/subsecti/closures.htm][Closures and Lexical Binding]] (Franz Lisp)
   * [[http://psg.com/~dlamkins/sl/chapter15.html][Successful Lisp: Closures]]
   * [[http://www.flownet.com/gat/specials.pdf][The Idiot's Guide to Special Variables and Lexical Closures]]

%COMMENT{type="below" nonotify="on"}%

---

%STOPINCLUDE%
to top
End of topic
Skip to action links | Back to top
You are here: Blog > BlogOnSoftware20060223

r1.6 - 27 Feb 2006 - 05:36 - ClausBrod to top
Blog