Those who haven't heard of or played around on TopCoder don't know what they're missing.

For example, I just spent the last 45 minutes working on a set of three different algorithmic problems. Each rises in difficulty, and you are awarded points based factors such as the amount of time it takes you to finish. There's a set of test suites that validate your solution after you finish. You can program in essentially whatever language you feel most comfortable in (C#, Java, VB, C++), and a practice room is available if you need some time to get used to things. “Real” competitions are scheduled regularly.

The hardest of these three exercises I just completed was an English to “Taglish” translator. It essentially just does some verb conjugation and other hackery to transform an input string. My solution can be seen here. I encourage you to give it a try before looking. It's in the SRM 220 DIV 2 set of problems.

What's amazing is how elegant and ugly solutions to the same problem can be. (The code I have shared is certainly in the latter category! ;) ) Once you submit your answer, you can take a look at what other folks submitted.

I'm making PongFX available as a v0.1 release. Lots of remaining work to do, and an endless number of bugs left to iron out. Networking support was cut for the time being.

My ISP doesn't have .deploy files enabled on their server, which means that I can't use ClickOnce to get this out there. Sorry 'bout that. The binary drop should work fine. Note: you need the Avalon CTP to run this.

• Binary: get it
• Source: get it

Poor man's documentation:

• Up: Move your token up
• Down: Move your token down
• Left-Ctrl: When held, will “grab“ the ball in sticky mode (releasing shoots it back)
• Escape: Quit the game

Feel free to report bugs, but I will likely respond with an “I know”... just haven't found the time to address most of them. I'm doing a few things quote unconventionally, and one of my largest mistakes was to couple the game logic and layout so tightly. Hey: it's a v0.1 release, cut me some slack!

Some notes:

• Yes, I stole the Avalon “shield“ logo from ChrisAn's XamlPad-clone application.
• I absolutely love the animation support in Avalon, although I haven't used it in many places I should have.
• The ball's rotation doesn't change as it should. I've had a hard time figuring out how to change animations on the fly.
• Resizing the window causes the playing area to extend beyond the bottom. It's weird. Maximize the window to see what I mean.
• Animation is a bit choppy, and I know I'm not using the graphics engine to its full potential. I'm moving widgets around in a very GDI-ish manner.
• Any physics major (or anybody who actually paid attention in high school physics 101) would laugh at my “physics“ simulation code. While you can fling the ball off of your paddle by moving it in a certain direction while hitting it, that's about as complex as it gets.
• 4-player support is nonexistent, and will be enabled once I pour the Indigo-networking on top.
• Game tick resolution is whacky. I think it's too granular at the moment, although the choppiness indicates otherwise.
• Etc., etc., etc.

I'd love to hear any feedback you have!

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. :)