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.

C# 2.0 introduces anonymous delegates. Their implementation actually goes beyond simple delegates; they are, in fact, closures (I think). Here is an example:

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.


When asked for a TWiki account, use your own or the default TWikiGuest account.


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)
400

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!

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.

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:

  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.


When asked for a TWiki account, use your own or the default TWikiGuest account.


Fight globalization! (18 Feb 2006)

A few days ago, I talked everybody to sleep about special variables and dynamic bindings in Lisp. I somehow managed to avoid this topic for years, but then I finally had to understand it to fix subtle issues in our code when dealing with what I thought were simple global variables.

In Lisp, you usually declare a global variable using 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.


When asked for a TWiki account, use your own or the default TWikiGuest account.


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 big grin

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 wink (Everybody in the newsgroup had a good chuckle back then.)


When asked for a TWiki account, use your own or the default TWikiGuest account.


I'm so special (11 Feb 2006)

The large application which I help to develop has an embedded Lisp interpreter and compiler, and over time I also left my marks in that subsystem. It was only after a considerable amount of tinkering with the innards of the interpreter that my insights into Lisp finally reached critical mass. I guess I understand now why Lispniks are so devoted to their language and why they regard all those other languages as mere Lisp wannabees.

While learning Lisp, bindings and closures were particularly strange to me. It took me way too long until I finally grokked lexical and dynamic binding in Lisp. Or at least I think I get it now.

Let us consider the following C code:

  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?"

  1. defvar declares fortytwo as dynamic and binds it to a value of 42.
  2. The let statement in quelle-surprise binds fortytwo to a value of 4711, but does not change the type of binding! Hence, fortytwo still has dynamic binding which was previously established by defvar. This is true even though let usually always creates a lexical binding.
  3. shatter-illusions, when called, inherits the dynamic bindings of the calling code; hence, fortytwo will still have a value of 4711!

Kyoto Common Lisp defines 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
  42

So 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.


When asked for a TWiki account, use your own or the default TWikiGuest account.


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 unavailable

I 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 exportlist

Run 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...


When asked for a TWiki account, use your own or the default TWikiGuest account.


Previous month: Click here?. Next month: Click here?.

Revision: r1.19 - 30 Mar 2006 - 19:03 - ClausBrod
Blog > BlogOnSoftware200602
Copyright © 1999-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback