I made a couple small improvements to my brain dump from last night. I added a few continuation-ish constructor and Wait(...) overloads that take a consequent and alternate Action<T> (a new delegate type in Whidbey). Action<T> is just a void(T) function that executes a set of statements (with no return value). If the guarded condition is met, the wait class just executed your consequent from within a locked context; if not, it will execute the alternate from the same context.

For example, here is the new definition of GuardedWait<T> (sorry--it's gotten a bit lengthy):

A guarded wait is a locking primitive which enters an object's monitor and performs some processing once a certain predicate condition arises. You could imagine a buffer which refills itself once its contents have been consumed, a consumer which empties a buffer once it reaches a certain capacity, and so on.

Using the new Predicate<T> class in the Framework 2.0, the following is a pretty straightforward implementation of such a construct:

public class GuardedWait<T>

{

 

    private Predicate<T> predicate;

 

    public GuardedWait(Predicate<T> p)

    {

        predicate = p;

    }

 

    public bool IsTrue(T on)

    {

        return predicate(on);

    }

 

    public bool Wait(T on)

    {

        return Wait(on, -1);

    }

 

    public bool Wait(T on, int millisecondsTimeout)

    {

        int counter = millisecondsTimeout;

        while (true)

        {

            long beginTick = DateTime.Now.Ticks;

            lock (on)

            {

                if (!Monitor.Wait(on, counter))

                    return false;

                if (IsTrue(on))

                    return true;

            }

            counter -= (int)new TimeSpan(

                DateTime.Now.Ticks - beginTick).TotalMilliseconds;

            if (counter <= 0)

                return false;

        }

    }

 

}

As you can see, the public contract is very simple and familiar. It has a constructor which takes a predicate operation. This is the condition to guard on, that is, when waiting this is the condition that must be true for the lock to be considered successful. Then we have two simple bool Wait(...) operations which are very much like the Monitor.Wait(...) methods. This relies on the use of Monitor.Notify*() in order to wake up the wait class to check for its predicate condition.

Lastly, consider a simple example of its use. In this snippet, we share a queue between a producer and a consumer. Assume there is a contract in place that the consumer never lets the queue get beyond a certain threshold, and will deplete the buffer to half of its capacity each time it reaches such a threshold. This code effectively accomplishes this:

class GuardedWaitTest

{

    public static void Main(string[] args)

    {

        Queue<int> q = new Queue<int>();

        Producer(q);

        Consumer(q, 150);

        Thread.Sleep(5000);

    }

 

    static void Producer(Queue<int> q)

    {

        Thread t = new Thread(delegate()

        {

            Random r = new Random();

            while (true)

            {

                lock (q)

                {

                    int next = r.Next();

                    q.Enqueue(next);

                    Console.WriteLine("Produced {0} [{1}]", next, q.Count);

                    Monitor.Pulse(q);

                }

            }           

        });

        t.IsBackground = true;

        t.Start();

    }

 

    static void Consumer(Queue<int> q, int count)

    {

        Thread t = new Thread(delegate()

        {

            GuardedWait<Queue<int>> wait = new GuardedWait<Queue<int>>(delegate(Queue<int> tq)

            {

                return tq.Count >= count;

            });

            while (true)

            {

                lock (q)

                {

                    if (wait.Wait(q))

                    {

                        while (q.Count >= (count / 2))

                        {

                            int consumed = q.Dequeue();

                            Console.WriteLine("Consumed {0} [{1}]", consumed, q.Count);

                        }

                    }

                }

            }

        });

        t.IsBackground = true;

        t.Start();

    }

 

}

This code is relatively straightforward, albeit verbose because I am trying to carefully orchestrate the interaction between threads. Producer simply generates random numbers and Enqueue()s them into the shared Queue. Consumer uses the GuardedWait<T> class to “wake up” when (in this case) 150 items have been placed into the queue. It then consumed half of these, and relinquishes the lock back to the Producer. Obviously a simple example, but it should give you a good idea of when such a construct might be useful.

I just read Soma's blog about the Avalon CTP, where he mentioned the microsoft.public.windows.developer.winfx.avalon newsgroup.

With so many channels through which customers can reach a MS employee nowadays, it's easy to forget about good ole' fashioned newsgroups. This is a GoodThing(tm). :) Luckily, Drew and others seem to be on top of things over there. It's great to have a community of folks who love our technology as much as we do.

I'm several chapters through my book. Well, rough draft chapters that is--I suppose there's a subtle difference. ;) And I have a question that hopefully at least one person out there can provide feedback on.

As I am writing, I'm constantly battling with the whole “know your user” dillemma. This fundamental tenet applies to building products, designing APIs, and writing books, too. If my book is under or over the head of my target audience, well... folks likely won't read it! At this point, it's hard to pinpoint exactly who my readers will be. My envisioned persona at this point is an IT software professional who either has a couple years of experience or a CS degree. This person enjoys reading about technologies, but at the same time has a job to do and will be using the book as a crucial tool to enable them in doing it.

Seeing as I've never explicitly said what the book is, let me do that: roughly, it is a whirlwind tour of the CLR and .NET Framework, with a focus on 2.0 stuff. There are several similar works out there already, so I'm trying to differentiate myself with a more technical, geekish edge, and great coverage of the new 2.0 features.

So here comes my constant internal debate. How much computer science-ish stuff should it contain? I mean, there's a certain level needed to understand some concepts, but many could just as easily be glossed over. Moreover, if folks need to learn about hardcore CS stuff, well... there are plenty of classic texts out there already. Take type systems, for example. I could just say: hey, there are these things called types, of which there are two categories... value and reference types. The differences are X, and you use them by doing Y. And so on. Or, I could take a step back, and briefly discuss the design decisions made when choosing strong vs. latent typing, a good mixture of static and dynamic type checking, and so on. I could easily spend 1/5 of the entire Type System chapter on this alone. But I fear that could be a mistake.

I suppose there is a subtle difference... however, I do know that many people out there just want to “see the code” when they buy a book. Not read through a whole bunch of geeky expositions.

Any opinions would be awesome! Thanks...

Streams are a construct which go hand in hand with Thunks. They enable lazy loading and calculation of algorithms, and can be particularly interesting due to the ease with which they compose. The examples I provide below make heavy use of new C# 2.0 features, such as anonymous delegates and iterators. Some will notice my undeniable influence by the Wizard book in the concepts presented here.

First, consider a new type Stream<T>:

    public class Stream<T> : IEnumerable<T>

    {

        //fields

        private List<T> memory = new List<T>();

        private Evaluator evaluator;

        private int count;

        public delegate Nullable<T> Evaluator();

        //ctors

        public Stream(Evaluator evaluator) : this(evaluator, -1)

        {

        }

        public Stream(Evaluator evaluator, int count)

        {

            this.evaluator = evaluator;

            this.count = count;

        }

        //properties

        public int Capacity

        {

            get

            {

                if (count == -1)

                    return int.MaxValue;

                return count;

            }

        }

        public int Count

        {

            get

            {

                if (count == -1)

                    return MemoryCount;

                return count;

            }

        }

        public int MemoryCount

        {

            get

            {

                return memory.Count;

            }

        }

        public T this[int index]

        {

            get

            {

                if (memory.Count <= index)

                    for (int i = memory.Count; i <= index; i++)

                        Memoize();

                return memory[index];

            }

        }

        //methods

        public IEnumerator<T> GetEnumerator()

        {

            int i = 0;

            while (i <= Capacity)

            {

                yield return this[i];

                i++;

            }

        }

        private void Memoize()

        {

            Nullable<T> n = evaluator();

            if (!n.HasValue)

                throw new ArgumentOutOfRangeException("No value for the specified index");

            memory.Add(n.Value);

        }

    }

This takes an Evaluator delegate, a no-args method which returns an instance of Nullable<T>. I have chosen to implement a memoized stream, to make re-accessing previously computed indexes possible. This simply means that calculated values are "remembered" once they have been generated. My implementation actually wouldn't work without memoization since it uses state variables to track its computation. This will lazily load up to the index which is requested.

This can be used, for example, to calculate numbers in the Fibonacci series.

Stream<long> CreateFibStream()

{

    long i1 = 1;

    long i2 = 1;

    return new Stream<long>(delegate

    {

        long t = i1;

        i1 = i2;

        i2 = t + i2;

        return t * 4;

    });

}

This code can be used to calculate the first 10 numbers in the Fibonacci series as follows:

Stream<long> fib = CreateFibStream();

for (int i = 0; i < 10; i++)

    Console.WriteLine(fib[i]);

The output of this program is as follows:

1

1

2

3

5

8

13

21

34

55

Notice that, because of the indexer, you can request, say, the 15th Fibonacci number directly:

This prints out the number 610.

Because streams are easily composable, I've easily created a few standard factory methods which construct an augmented stream. These simply wrap an existing stream and lazily change the output as it is requested. For example, Amplifier<T> will amplify the numbers generated by a target stream by a constant number as they are retrieved.

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.