Generating and dealing with Scheme lambda expressions in IL is a relatively interesting problem. Scheme is statically-scoped, making the implementation a bit more straightforward than, say, Common LISP. I have not yet determined the best approach in all cases yet, but certainly have a workable approach. There are many optimizations to be had, but I’ll worry more about this at some point in the future. Interestingly, the approach I have arrived at is very similar to C# 2.0’s anonymous delegate syntax, albeit for the auto-generated delegates.

Consider a lambda expression as follows:

(let (y 0)
  (define (mkincadder x)
    (lambda (z)
      (begin
        (set! y (+ y 1))
        (+ x y z))))

This is a tad tricky, but can be roughly translated into the following C# 2.0 program:

delegate object _lambd(object z);
static int y = 0;
static _lambd mkincadder(object x)
{
  return delegate (object z) {
    y = y + 1;
    return x + y + z;
  };
}

Both a consumer in Scheme and C# will produce the same output. Here is a sample program for each, both of which print out the numbers “7,” “8,” and “9” to the console:

Scheme:
(let (a (mkincadder 5))
  (begin
    (print (a 2))
    (print (a 2))
    (print (a 2))))

C#:
_lambd a = mkincadder(5);
Console.WriteLine(a(2));
Console.WriteLine(a(2));
Console.WriteLine(a(2));

In fact, the implementation I've devised is nearly identical to the anonymous delegate example. The one optimization I make is that the programmer is not required to define a delegate signature, as this is a gory detail hidden by the Scheme compiler itself. The compiler reuses auto-generated delegates with the same signature, essentially building up a dictionary of unique delegate signatures.

What happens under the hood is that each lambda is captured in a class with a single apply method. The value of a lambda expression is simply a delegate to this method. Any free variables from within the lambda body that are bound to something other than an argument are teased out into a class variable and captured at the time an instance is constructed. So for example, the generated class for the lambda above looks like this (pseudo-code):

public class __lambd1
{
  private int x;
  private int y;

  public __lambd1(int x, int y)
  {
    this.x = x;
    this.y = y;
  }

  public delegate object __func(object z);

  public object apply(object z)
  {
    y = y + 1;
    return x + y + z;
  }
}

public class __global
{
  public __lambd1.__func mkincadder(object x)
  {
    __lambd1 ret = new __lambd1(x, 0);
    return new __lambd1.__func(ret.apply);
  }
}

Generating an entire class is overkill for simple lambdas which don’t contain non-arg free variables, an optimization I will likely make by accumulating such functions on a single static class similar to the generated __global class containing named lambdas. Additionally, I will likely place functions that share environments on the same class...

An interesting complication arises, however, when many lambdas begin to access and mutate state within a shared environment. In fact, the concept of an environment, while straightforward to do in an environment-passing interpreter, feels like a lost concept in the clumsy translation to IL. At this point, I see several options, a few of which seem feasible.

First, consider what I mean by this:

(let (y 0)
  (define (mkincadder x)
    (lambda (z)
      (begin
        (set! y (+ y 1))
        (+ x y z))))
  (define (dec x)
    (set! y (- y x))))

Here we now have two things that can access the y variable: mkincadder and dec. Why is this problematic? Well, now we cannot simply capture free variables and store them as instance fields on individual lambda classes. We need to use some sharable location in memory which can be mutated and where the function updates will be visible to each other. For this particular example, the answer is relatively straightforward: simply put an internal y variable on the __global class, and ensure the functions that must share an environment are declared on it. In this case, that means mkincadder and dec get defined on __global. There will end up being only a single instance of __global being used at runtime, accomplishing the goal of having a shared environment.

This is the example pseudo-code for __global; not much changes for the actual lambda implementations other than referencing __global for the y variable:

public class __global
{
  internal object y = 0;
  public __lambd1.__func mkincadder(object x)
  {
    __lambd1 ret = new __lambd1(this, x);
    return new __lambd1.__func(ret.apply);
  }
  public __lambd2.__func dec(object x)
  {
    __lambd2 ret = new __lambd2(this, x);
    return new __lambd2.__func(ret.apply);
  }
}

As mentioned above, the compiler now knows that any references to y from within the lambdas must get turned into a reference to __global.y. Notice that we pass this to the constructor so it can hook a reference to its “parent environment”.

This seems to work for most cases. Here are a couple other solutions I had previously considered which I might need to rely on slight variants for in cases where the above doesn't work.

An alternative approach is to use nested classes. Items with shared environments would get generated on the same class as above, while parent environments would be implemented simply by searching up the outer class hierarchy. This approach unfortunately gets pretty hairy quickly, though, as the number of chained environments increases. As long as the Scheme compiler hides this as an implementation detail that never surfaces to consumers, that’s fine. But this is unavoidable should somebody want to use us from C#.

A slight permutation of this solution would be to use inheritance rather than nesting. That is, shared environment variables would be “inherited” using static fields, and could be “hidden” by simply injecting identically-named fields on derived classes. At code generation time, we could detect the right place to reference in the class hierarchy based on what is defined where. This is also tricky, however, because sometimes we would want to use static variables and sometimes instance, depending on whether multiple environments with different bindings for the same variable could be created (yes in most cases).

Lastly, I could preserve the notion of an environment using a dictionary-like construct passed around at runtime. This could be like a standard environment-passing interpreter, and I would have fine-grained control over what is referenced and how environments are explicitly chained together. Unfortunately, I fear that the performance would suffer greatly with this approach. (Instead of ldfld/stfld instructions, I would now have to call methods to access and store variables. Ugh.)

These are certainly interesting problems, and I am just beginning to do a bit of research on what other IL-based compilers do.

The Avalon team has been working super hard at getting a CTP out the door. Well... it's here!!

What's amazing is that this drop aligns with the WinFX platform's long-term goal of shipping down level. In less PHB-ish terms: it runs on XP! Just a few months after the announcement that things would go down level. This means there's a very low barrier to entry for tinkering... i.e. no download and installation of the entire Longhorn OS, just a set of binaries with a cute little installer and the SDK. Unfortunately, you need to be an MSDN subscriber to get yer hands on it at this point.

The CTP runs on top of the 2.0.40607.51 stack, otherwise known as Whidbey Beta 1. And it's compatible with the Express SKUs as well. However, as JasonZ mentions, you're not going to get very far trying to get it to work with the recent Whidbey CTP. Our story here should get better over time.

There's already some buzz going around the MS blogosphere... ChrisAn has a pretty cool demo app which uses ClickOnce for deployment. I'm working on shoring up my recently promised application and will try to post something--now that a semi-comparative set of bits to what it was built on are available!

Update: Just noticed that RRelyea has a great post describing this drop.

I have a few things baking in the oven, but unfortunately not a great deal of time during which to work on them.

A quick little thing I began working on is an AOP-ish framework for IL munging. I've been able to hack together some really neat stuff in a relatively short amount of time using AbsIL. My first cut is in C#, but I would like to take a stab at writing the whole thing in OCaml/F#. I've used a variety of Java AOP frameworks in the past, but I never found one I really fell in love with.

What I've done thus far is, by using an external configuration file, created a simple set of controlled IL refactorings to wrap and redirect method calls and bodies. Essentially, there are two primary modes I'm worrying about at first: callsite interception, and method body interception. The fact that IL is a stack-based language leads to some interesting possibilities. For example, I have one mode that replaces calls to certain methods with another of a similar signature. This is actually quite straightforward and requires little work to the IL leading up to or after a method call.

Consider this IL:

  IL_0000:  ldstr      "**mcall:Add({0}, {1})"
  IL_0005:  ldc.i4.2
  IL_0006:  newarr     [mscorlib]System.Object
  IL_000b:  stloc.1
  IL_000c:  ldloc.1
  IL_000d:  ldc.i4.0
  IL_000e:  ldarg.1
  IL_000f:  box        [mscorlib]System.Int32
  IL_0014:  stelem.ref
  IL_0015:  ldloc.1
  IL_0016:  ldc.i4.1
  IL_0017:  ldarg.2
  IL_0018:  box        [mscorlib]System.Int32
  IL_001d:  stelem.ref
  IL_001e:  ldloc.1
  IL_001f:  call       void [mscorlib]System.Console::WriteLine(string,
                                                                  object[])

To mutate this so that we call an intercepting method of the same signature rather than Console.WriteLine, we merely change line 001f. The stack transition is the same (string, object[]) -> (nil). Moreover, I have a neat little hack that enables wrapping interceptors “around“ method calls. We simply write a new method that takes string and object[] parameters and returns void, but which also takes a delegate of the signature of Console.WriteLine. This might be a bit difficult to follow, but this enables our intercepting method to delegate to the original method in a very controlled fashion (if it wishes to do so). Rather than illustrating in IL, consider some code:

  void SomeMethod()
  {
    Console.WriteLine(“One, two, three, four: {0}, {1}, {2}, {3}“, 1, 2, 3, 4);
  }

We can easily munge the IL for this to be:

  void SomeMethod()
  {
    InterceptingMethod(new Intercepted(Console.WriteLine), “One, two, three, four: {0}, {1}, {2}, {3}“, 1, 2, 3, 4);
  }

  delegate void Intercepted(string s, params object[] o);

  void InterceptingMethod(Intercepted i, string s, params object[] o)
  {
    Console.WriteLine(“Before method call...“);
    i(s, o);
    Console.WriteLine(“After method call...“);
  }

Assuming the intercepting code provides the delegate, it's just a matter of creating the delegate at the right place on the stack... (a bit tricky if we need to find the right point to insert it at the beginning, but this is easily avoidable if it comes at the end of the parameter list... not easily conceptualized with the above C# signature because of the syntactic sugar of 'params', but remember it's just an array in IL). We then substitute the intercepting method, just as with the first example presented.

This is obviously not terribly flexible, as you'd need a new interceptor for each unique method signature. I'm working on that, and will likely get around it by passing detailed context which can easily be “applied“ to accomplish the delegate call as above.

Just outputting text to the console probably isn't very interesting, but there is a wealth of possibilities to what we could do instead. I would enumerate them now, I'm sure you can imagine. :) And of course more interesting things can be provided to the interceptor in addition to the delegate. For example, detailed captures of any locals at the time a method call is made, the arguments passed to a method, and so on. I'm creating a standard type which will capture all of this. There is a cost, of course, so you will have to opt in to receive it.

This is just one of many interesting patterns. I must say: I love AbsIL. :) The OM is a bit whacky and odd if you're working in C# (Reflector is your friend) but extremely powerful once you get used to it. Of course, I suppose a hardcore geek would be doing this in OCaml...

Of course, my Scheme compiler and interpreter is on the top of my stack. Still plugging away, but it's taking a bit longer than I had expected. I've been speaking with some folks at MS that have written compilers, and they echoed what I am finding: it takes much longer than you would first expect. :)

My DesignByContractInC# thing is still around, but I just haven't had a chance to really dive deep into it. Through some experimentation, I've found the SSCLI C# compiler isn't quite as pluggable/extensible as I had originally hoped.

3,894 lines of code.

First time successfully parsing an entire R5RS test script into a complete AST.

Able to emit a module that recognizes and creates IL for lambdas w/ only bound variables.

It feels good to actually see a real, live, breathing assembly. Thought I'd never get back above water.

When I should be writing and instead procrastinate, I come up with whacky ideas like identifying which words I make too liberal use of.

Breakdown of all words ocurring 25 or more times in my first chapter:

Interestingly, I have 59 opening curly braces {, but only 56 closing! Yikes... Wish I could do some lexical analysis on my Word document.

Interesting discussion going on over on Krzysztof's blog. We recently changed our guidance for generic type parameter naming from recommending single letter names to more descriptive ones. I personally think we as programmers simply need to discover the rest of the Unicode character set...

E.g.

class IList<α> {}

class IDictionary<α, β> {}

class Converter<α, β> { }

And so on. Of course I am being flippant, but I'm not a huge fan of this change. I prefer clear and concise, and actually like that there is a mathematical feel to generics. With that said, I suppose it might be less approachable, and Ada programs did, in fact, tend to use more descriptive generic type labels. I'd call that a historical precedent against my preference. :)

I wonder what Don thinks.

My Scheme compiler frontend is almost at the point where I can move my focus from syntax to semantics. It successfully recognizes 100% of the Scheme grammar's tokens and constructs an AST representation for about 75% of the constructs available in R5RS. Along with this lexer/parser comes a simple toplevel read-parse-print console that parses stdin or file input and, rather than evaluating it, just prints the AST out for inspection. This has been really useful for debugging. I also have some unit tests that validate certain Scheme input produces the expect tree, also proving to be rather useful. A test is written first for the construct I'm attempting to parse, and I know I'm pretty much there when it succeeds. Very nice.

Obviously most of the difficult tasks are still to come. I've done some work on the backend, but more experimentation than anything else. Most of my time here has been spent thinking about how to make interoperability with other “mainstream” managed languages palatable. I'm actually writing this so that it's pretty modular, thinking this would facilitate plugging in different steps along the way (e.g. so that extending it with an optimizer is easy; ripping an optimizer out and tossing a more efficient one in is even simpler).

Wish I had more time to throw at this. Some day. :)

A thunk is a relatively common construct in functional programming where the passing of arguments won't result in any side effects. In these cases, the compiler can silently emit code that bypasses computing the value of an argument altogether at the call site in case it isn't used in a method body at all. If it does end up being used, however, it will be lazily evaluated at the last possible moment. This is sometimes referred to as call-by-lazy-evaluation. It is said that the argument passed is frozen at the time of invocation, and thawed when it is needed. Further references typically avoid re-thawing once the initial thaw has ocurred.

It might sound odd that an argument would be passed in to a method but not used at all. But depending on the code paths a method takes, it could end up not needing to reference it at all. Consider the simplest case: where a caller spends time retrieving results from a database to construct some fancy input, but then the call fails before the target method even has a chance to inspect this data, possibly because one of the other arguments was in an invalid format or out of the valid range. It's terribly inefficient that the client had to compute this in the first place!

Just playing around, I've thrown together a Thunk<T> class. It's nothing special, but it seems to work rather nicely with C#'s new anonymous delegate syntax.

public class Thunk<T>

{

    private T value;

    private ThawFunction thaw;

    private bool thawed;

    public delegate T ThawFunction();

    public Thunk(ThawFunction thaw)

    {

        this.thaw = thaw;

    }

    public T Value

    {

        get

        {

            if (IsFrozen)

            {

                this.value = thaw();

                thawed = true;

            }

            return this.value;

        }

    }

    public bool IsFrozen

    {

        get { return !thawed; }

    }

}

As an example of its usage, consider this test class:

public class ThunkExample

{

    public static void Main(string[] args)

    {

        ThunkExample ex = new ThunkExample();

        string longText = "Pretend this is some long text that is expensive to split.";

        ex.WithThunk(longText);

        ex.WithoutThunk(longText);

    }

    public void WithThunk(string longText)

    {

        WithThunkDoWork(longText.Length, new Thunk<string[]>(delegate { return longText.Split(' '); }));

    }

    public void WithThunkDoWork(int strlen, Thunk<string[]> words)

    {

        if (strlen > 2048)

            throw new ArgumentOutOfRangeException("strlen", "Must be <= 2048");

        Console.WriteLine("-- WithThunk --");

        foreach (string w in words.Value)

            Console.WriteLine(w);

    }

    public void WithoutThunk(string longText)

    {

        WithoutThunkDoWork(longText.Length, longText.Split(' '));

    }

    public void WithoutThunkDoWork(int strlen, string[] words)

    {

        if (strlen > 2048)

            throw new ArgumentOutOfRangeException("strlen", "Must be <= 2048");

        Console.WriteLine("-- WithoutThunk --");

        foreach (string w in words)

            Console.WriteLine(w);

    }

}

If you take a look at the IL for the WithThunk vs. WithoutThunk method, you'll see a fundamental difference. Specifically, WithoutThunk computes a bunch of local values, and leaves them on the stack for the following call to the WithoutThunkDoWork(...) method.

  IL_0009:  newarr     [mscorlib]System.Char
  IL_000e:  stloc.0
  IL_000f:  ldloc.0
  IL_0010:  ldc.i4.0
  IL_0011:  ldc.i4.s   32
  IL_0013:  stelem.i2
  IL_0014:  ldloc.0
  IL_0015:  callvirt   instance string[] [mscorlib]System.String::Split(char[])

So the difference is that WithoutThunk evaluates the string[] argument at the call site, while WithThunk delays calculation to its first use in the *DoWork methods. If the data is not used at all, it doesn't get calculated. Obviously this is a contrived example, but if the delayed operation was expensive -- e.g. as in the database example cited above -- this could have tangible benefits at runtime.

A couple things would make this construct nicer sans first class CLR support. Consider if C# had mixins, for example. Thunk<T> could then derive from T, and some compiler generated code could implement simple wrapper methods that forwarded any calls to its value field. Of course this would only work if all methods were virtual, but it's a start. We could then pass thunks around pretending they were instances of a given type, and (in theory, at least) existing code would work with them just fine. Alternatively, overloading assignment and dereferencing operators might be nice, too. This would allow one to assign to and dereference a thunk as though it were just an instance of the type it wrapped. Similar to the Nullable<T> type, rarely does one actually want to access and use it as a typical object.

Lastly, a few caveats. All of this assumes that the performance hit resulting from late bound delegate calls is acceptable in your scenario. If you're wrapping an operation that has side effects, this is not a good idea for obvious reasons.

The FxCop team recently released a new version, 1.312. Check it out.

I've been working quite a bit lately with the guys responsible for this technology. They've poured a lot of energy into this product... and it shows. With this release, you can expect improved quality of existing rules (reducing false positives, increasing coverage), and a number of entirely new rules. This stuff is based entirely on real experience shipping managed code and is a great way to avoid common implementation mistakes and pitfalls. And it helps you to be consistent with the Framework, too, a real plus when you're shipping publically-consumable APIs.

If you're not already shipping FxCop'd code, I'd highly recommend it... :)