Delegating closures to C# (26 Feb 2006)
Last time, I looked at how closures work in Lisp, and tried to mimick them in C++ (without success) using function objects. To recap, a closure can be thought of 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.
class TestDelegate
{
public delegate void MyDelegate();
public MyDelegate GetDelegate()
{
string s = "Hiya";
return delegate() { Console.WriteLine(s); }; // anon delegate
}
static void Main(string[] args)
{
TestDelegate p = new TestDelegate();
MyDelegate anonDel = p.GetDelegate();
anonDel();
}
}
In the anonymous delegate, s is a free variable; the code compiles because
the delegate refers to the definition of s in the surrounding code.
If you run the above code, it will indeed print "Hiya", even though
we are calling the delegate from Main, i.e. after we have left
GetDelegate() which assigns that string to a local variable.
This is quite cool, considering that the .NET CLR uses a conventional
stack and probably wasn't designed to run Lisp or Scheme all day. How do they
do this?
Let's look at the disassembled code of GetDelegate() (using .NET Reflector,
of course):
public TestDelegate.MyDelegate GetDelegate()
{
TestDelegate.<>c__DisplayClass1 class1 = new TestDelegate.<>c__DisplayClass1();
class1.s = "Hiya";
return new TestDelegate.MyDelegate(class1.<GetDelegate>b__0);
}
So the compiler morphed our code while we were looking the other way!
Instead of assigning "Hiya" to a local variable, the code instantiates
a funky <>c__DisplayClass1 object, and that object apparently has a
member called s which holds the string. The <>c__DisplayClass1 class
also has an equivalent of the original GetDelegate function, as it seems.
Hmmm.... very puzzling - let's look at the definition of that proxy
class now:
[CompilerGenerated]
private sealed class <>c__DisplayClass1
{
// Methods
public <>c__DisplayClass1();
public void <GetDelegate>b__0();
// Fields
public string s;
}
public void <GetDelegate>b__0()
{
Console.WriteLine(this.s);
}
Aha, now we're getting somewhere. The compiler moved the code in the anonymous delegate
to the function <>c__DisplayClass1::<GetDelegate>b__0. This function
has access to the field s, and that field is initialized by the
compiler when the proxy object is instantiated.
So when the C# compiler encounters an anonymous delegate,
it creates a proxy object which holds all "bindings" (in Lisp terminology)
of free variables in the code of the delegate. That object is kept on the heap
and can therefore outlive the original GetDelegate(), and that is why we
can call the delegate from Main and still print the expected string
instead of referring to where no pointer has gone before.
I find this quite a cool stunt; I'm impressed by how the designers of C# are
adding useful abstractions to the language. Lisp isn't the only language which
supports closures, and maybe wasn't even the first, but I'm pretty sure that
the folks at Microsoft were probably influenced by either Lisp (or Scheme)
while developing anonymous delegates. It is amazing how such an old
language continues to inspire other languages to this day.
And that is, after reading a couple of good books and enlightening articles,
what I understood about closures. Now, as a long-time boneheaded C++ programmer, I might
have gotten it all wrong, and this blog entry is actually one way to test
my assumptions; if my views are blatantly misleading, then hopefully somebody will
point this out. (Well, if anybody reads this at all, of course.)
What a simple and amazing concept those closures really are! I only had to
shed all my preconceptions about the supposedly one and only way to call and execute
functions and how to keep their parameters and variables on a stack...
Closures are definitely very handy in all situations where callbacks are registered.
Also, I already alluded to the fact that you could possibly build an object concept on top of
closures in Lisp. And doesn't "snapshot of a function in execution" sound
frighteningly close to "continuation"
or "coroutines"? (Answer: Yes, kind of, but not quite. But that's a different story.)
I'm still trying to learn what closures do and how to best apply them in practice.
But that doesn't mean they are constructs for the ivory tower: Knowing about them
helped me only recently to diagnose and explain
what originally looked like a memory leak in some Lisp test code that we had written.
The final word of the jury is still out, but this is probably not a real leak,
rather a closure which holds on to the binding of a variable, so that the garbage
collector cannot simply free the resources associated with that variable.
Closing in on closures (23 Feb 2006)
The other day, I battled global variables in Lisp by using this construct:
(let ((globalFoo 42))
(defun foobar1()
(* globalFoo globalFoo))
(defun foobar2(newVal)
(setf globalFoo newVal))
)
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.
globalFoo'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:
> (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) 400Hmmm - 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!
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.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.
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);
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
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
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
nested functions:
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;
}
Unfortunately, extensions like this didn't make it into the standards so far.
So let's move on to greener pastures. Next stop:
How anonymous delegates in C# 2.0 implement closures.
- Closures and Lexical Binding (Franz Lisp)
- Successful Lisp: Closures
- The Idiot's Guide to Special Variables and Lexical Closures
Fight globalization! (18 Feb 2006)
defvar and
defparameter - but this way, the variable not only becomes global,
but also special. They are probably called special because of
the special effects that they display - see my blog entry for an
idea of the confusion this caused to a simple-minded C++ programmer (me).
Most of the time, I would use defvar to emulate the effect of a
"file-global" static variable in C++, and fortunately, this can be
implemented in a much cleaner fashion using a let statement
at the right spot. Example:
// C++, file foobar.C
static int globalFoo = 42;
int foobar(void)
{
return globalFoo * globalFoo;
}
int foobar2(int newVal)
{
globalFoo = newVal;
}
;; Lisp
(let ((globalFoo 42))
(defun foobar1()
(* globalFoo globalFoo))
(defun foobar2(newVal)
(setf globalFoo newVal))
)
The let statement establishes a binding for globalFoo which is only
accessible within foobar1 and foobar2. This is even better than
a static global variable in C++ at file level, because this way precisely
the functions which actually have a business with globalFoo are
able to use it; the functions foobar1 and foobar2 now share a
variable. We don't have to declare a global
variable anymore and thereby achieve better encapsulation and at the same
time avoid special variables with their amusing special effects. Life is good!
This introduces another interesting concept in Lisp: Closures,
i.e. functions with references to variables in their lexical context.
More on this hopefully soon.
Blame CoCreate, for instance (14 Feb 2006)
The company I work for is called CoCreate. The name was chosen because the company's mission is all about collaboratively creating things. That's all nice and dandy, but I guess the team who picked the name didn't include a programmer, and so they overlooked something pretty obvious which causes mild confusion every now and then. Most programmers, when confronted with our company name, think of COM. After all, one of the most important functions in all of the COM libraries prominently displays our company name: CoCreateInstance. Now, if a programmer thinks about COM (and hence software) when she hears about us, that's probably fine, because, after all, we're in the business to make and sell software. However, customers are not necessarily that technology-savvy, nor should they have to be. A while ago, a customer complained that our software was sloppy because it wouldn't uninstall itself properly and leave behind traces in the system. Our installer/uninstaller tests didn't seem to confirm that. So we asked the customer why he thought we were messing with his system. "Well", he said, "even after I uninstall your stuff, I still get those CoCreate error messages."
The customer sent a screenshot - it showed a message box,
displayed by an application which shall remain unnamed, saying
that "CoCreateInstance failed" and mumbling some COM error
codes!
It took us a while to explain to the customer that no, we
did not install this CoCreateInstance thing on the system,
and that it is a system function, and if we actually tried to
uninstall it along with our application as he requested (kind of),
he wouldn't be terribly happy with his system any longer, and
that the other app was actually trying to report to the customer that
it had found a problem with its COM registration, and that this should
be looked after, not our uninstaller. Phew.
Now if only we had the time-warping powers of the publishers
of "The Hitchhiker's Guide To The Galaxy", we'd send our
company marketing materials back into time before Microsoft invented
COM, and then sue the living daylights out of them. Well, if we were
evil, that is 
My memory took a little longer to swap back in, but while writing
the above, it dawned on me that this incident wasn't the only one of
its kind: Somebody had upgraded to a new PC and installed all applications
except CoCreate's. Then, while syncing to his Palm Pilot, he got
an "OLE CoCreateInstance Failed" error message, and started to
search high and low on his shiny new PC for traces of CoCreate
applications or components.
Puzzled, he posted to a newsgroup, and I replied with tongue-in-cheek:
Let me explain: When we kicked off CoCreate as a company, we sat together and thought about awareness strategies for the new company. So we called our buddies from Microsoft and asked them to name some API functions after us, and in exchange we would port our software to Windows NT. Neat scheme, and as you discovered on your system, the cooperation between the two companies worked just fine. [... skipping explanation of the technical issue and hints on how to fix registry issue on the system ...] The next step for CoCreate towards world domination will be to talk to some of our buddies in, say, Portugal, and offer them to develop a Portugese version of our application if they name their country after us.Would I get away with a response like this if I was a support engineer? Maybe not. One more thing to like about being a software developer
(Everybody in the newsgroup had a good chuckle back then.)
I'm so special (11 Feb 2006)
int fortytwo = 42;
int shatter_illusions(void)
{
return fortytwo;
}
void quelle_surprise(void)
{
int fortytwo = 4711;
printf("shatter_illusions returns %d\n", shatter_illusions());
}
A seasoned C or C++ programmer will parse this code with his eyes shut and tell
you immediately that quelle_surprise will print "42" because shatter_illusions()
refers to the global definition of fortytwo.
Meanwhile, back in the parentheses jungle:
(defvar fortytwo 42)
(defun shatter-illusions()
fortytwo)
(defun quelle-surprise()
(let ((fortytwo 4711))
(format t "shatter-illusions returns ~A~%" (shatter-illusions))))
To a C++ programmer, this looks like a verbatim transformation of the code above
into Lisp syntax, and he will therefore assume that the code will still answer "42".
But it doesn't: quelle-surprise thinks the right answer is "4711"!
Subtleties aside, the value of Lisp variables with lexical binding is determined
by the lexical structure of the code, i.e. how forms are nested in each other.
Most of the time, let
is used to establish a lexical binding for a variable.
Variables which are dynamically bound lead a more interesting life: Their
value is also determined by how forms call each other at runtime.
The defvar
statement above both binds fortytwo to a value of 42 and declares the variable as
dynamic or special, i.e. as a variable with dynamic binding. Even if code
is executed which usually would bind the variable lexically, such as
a let form, the variable will in fact retain its dynamic binding.
"Huh? What did you say?"
-
defvardeclaresfortytwoas dynamic and binds it to a value of 42. - The
letstatement inquelle-surprisebindsfortytwoto a value of 4711, but does not change the type of binding! Hence,fortytwostill has dynamic binding which was previously established bydefvar. This is true even thoughletusually always creates a lexical binding. -
shatter-illusions, when called, inherits the dynamic bindings of the calling code; hence,fortytwowill still have a value of 4711!
defvar as follows:
(defmacro defvar (var &optional (form nil form-sp) doc-string)
`(progn (si:make-special ',var)
,(if (and doc-string *include-documentation*)
`(si:putprop ',var ,doc-string 'variable-documentation))
,(if form-sp
`(or (boundp ',var)
(setq ,var ,form)))
',var))
In the highlighted form, the variable name is declared as special,
which is equivalent with dynamic binding in Lisp.
This effect is quite surprising for a C++ programmer. I work with both Lisp and
C++, switching back and forth several times a day, so I try to minimize
the number of surprises a much as I can. Hence, I usually stay away from
special/dynamic Lisp variables, i.e. I tend to avoid defvar and friends
and only use them where they are really required.
Unfortunately, defvar and defparameter are often recommended in Lisp
tutorials to declare global variables. Even in these enlightened
times, there's still an occasional need for a global variable, and if
you follow the usual examples out there, you'll be tempted to quickly add a
defvar to get the job done. Except that now you've got a dynamically bound
variable without even really knowing it, and if you expected this variable
to behave like a global variable in C++, you're in for a surprise:
> (print fortytwo) 42 42 > (quelle-surprise) shatter-illusions returns 4711 NIL > (shatter-illusions) 42 > (print fortytwo) 42 42So you call
shatter-illusions once through quelle-surprise, and it tells
you that the value of the variable fortytwo, which is supposedly global,
is 4711. And then you call the same function again, only directly, and it
will tell you that this time fortytwo is 42.
The above code violates a very useful convention in Lisp programming which
suggests to mark global variables with asterisks
(*fortytwo*). This, along with the guideline that global variables should
only be modified using setq and setf rather than let, will avoid
most puzzling situations
like the above. Still, I have been confused by the dynamic "side-effect"
of global variables declared by defvar often enough now that I made it
a habit to question any defvar declarations I see in Lisp code.
More on avoiding global dynamic variables next time.
Environmental unconsciousness (4.2.2006)
Chances are that - by looking at my earlier blog entry on batch files - you think I'm a DOS lamer. Nothing could be further from the truth, because I'm really a UNIX lamer. (OK, so what really shaped my thinking even before that was the phrase "38911 bytes free". But I digress.) So I still write little one-off scripts using bash, typically in a Cygwin environment. One of these scripts recently ran berserk, reporting lots of errors like this one:./foo.sh: line 42: /usr/bin/find: Resource temporarily unavailableI couldn't really figure out what resources the shell was talking about. Memory? Certainly not - the test system had ample memory, and was hardly using any. Files or disk space? Nope, lots of free disk space everywhere, and noone was fighting over access to shared files or so. Too many processes? Process Explorer wouldn't think so. Hmmm... This test script then revealed the truth:
typeset -i limit=2200 # Create a file with 2200 environment variable definitions rm -f exportlist typeset -i i=0 while [ $i -lt $limit ] do echo "export FOO$i=$i" >>exportlist let i=i+1 done # Import the environment definitions source ./exportlist # Are we still alive? env | wc find . -name exportlistRun this script and watch it balk miserably about unavailable resources. So it's the environment which filled up and caused my scripts to fail! And indeed, the system for which the problem was originally reported uses a lot of environment variables for some reason, and this broke my script. Once I had found out that much, it was easy to google for the right search terms and learn more: In this Cygwin mailing list discussion, Mike Sieweke explains that we are actually suffering from a Windows limitation here - apparently, the environment cannot grow larger than 32K. Christopher Faylor, chief maintainer of Cygwin, even recommends a workaround, but I haven't tested that one yet; instead, I helped to clean up the polluted environment on the affected PC, and henceforth, no waldsterben anymore on that system. 32K - this would have filled almost all of those 38911 memory bytes assigned for BASIC programs on my good ol' 64...
Previous month: Click here. Next month: Click here.
Revision: r1.20 - 29 Jan 2007 - 18:59 - ClausBrod