Tuesday, November 6, 2007

.NUTS: Yield Not, Waste Not

Everyone agrees that iterators are cool. They're so cool, they've got their own design pattern. Even cooler than that, they made the folks at Sun introduce some (gasp!) new syntax into Java. Not to be outdone, C# goes even further: not only can you use iterators easily, you can also roll your own generators using the yield keyword. How cool is that?

To Litter or Not to Litter
As it turns out, it's not as cool as it sounds. If you care about memory allocation and garbage, then using yield is a bad idea. Before I go any further, let's explore this concern itself. Why would anyone care about memory allocation in a language with a garbage collector? Isn't the whole purpose of the garbage collector to abstract away memory allocation and help avoid all those nasty pointer-related bugs? If you find yourself nodding along to these questions, then I suggest that you read Joel's Law of Leaky Abstractions.

The reasons to care about garbage are diverse. In my case, it's because I'm working with XNA. That means that if I make too much garbage at the wrong time, the garbage collector will fire up and mess up my frame rate. As Shawn Hargreaves explained, there are two ways to prevent this. Myself, I prefer what he calls the Right Frequency Path, which is why using yield is a bad idea for me.

There are other kinds of software, where garbage might not be as critical an issue as in games, but you should still be aware of it. Too much garbage can cripple the performance of any system.

Garbage Generators

So far I have only claimed that yield is wasteful. Let's take a look at why it's so. Consider this short program:
using System;
using System.Collections.Generic;
using System.Text;

namespace Sandbox
{
 static class IteratorTest
 {
     public static IEnumerable<int> FibonacciYield(int max)
     {
         if (max > 1)
         {
             int a = 1;
             int b = 1;

             yield return a;
             yield return b;

             int c = a + b;

             while (c < max)
             {
                 yield return c;
                 a = b;
                 b = c;
                 c = a + b;
             }
         }
     }
 }

 class Program
 {
     static void Main(string[] args)
     {
         int sum = 0;
         for (int l = 0; l < 100000; l++)
         {
             foreach (int i in IteratorTest.FibonacciYield(17))
             {
                 sum += i;
             }
         }
         Console.WriteLine(sum);
     }
 }
}

Running CLR Profiler on this program might surprise you. Although there is no explicit allocation in the code, plenty of memory winds up in the landfill. The culprit is a class with a weird name: <FibonacciYield>d__0. In this simple example, it is responsible for a whopping 3.4 MB garbage pile. Where did that come from?

That's the price one has to pay for the magic. After all, when you write your own generator with yield, you're returning IEnumerable<T>, without even instancing it, let alone implementing it. But the return value has to come from somewhere and that somewhere is a compiler-generated class. If you run Reflector on the program and then take a look at the method FibonacciYield, you'll get this:
public static IEnumerable<int> FibonacciYield(int max)
{
  <FibonacciYield>d__0 d__ = new <FibonacciYield>d__0(-2);
  d__.<>3__max = max;
  return d__;
}

Just as suspected, that's where and how allocation happens. But what about our mysterious compiler-generated class with an ugly name?

Under The Hood

The dissasembly of the <FibonacciYield>d__0 class shows not only an implementation of IEnumerable<int> interface, but also a full-fledged IEnumerator<int> implementation. It has all the stuff a generator should have: the Current property, the Reset method and the MoveNext method.

At first, the code might look intimidating -- all this came out of that short method?! -- but a closer look reveals certain patterns. For example, take a look at the fields:
private int <>1__state;
private int <>2__current;
public int <>3__max;
public int <a>5__1;
public int <b>5__2;
public int <c>5__3;
public int max;

The <1>__state and <2>__current fields have to do with how the yield keyword itself works and I'll get back to them in a few moments. The rest show an interesting pattern: the local variables in the original method turn into <a>5__1, <b>5__2 and <c>5__3 fields, whereas the max argument becomes <>3__max field. But what about the max field? Why have both max and <>3__max? And why convert local variables into fields in the first place?

To answer that, remember how the foreach loop works: by calling the MoveNext method of the IEnumerator<T> interface and inspecting its Current property, until MoveNext returns false. This means that the state of whatever you're doing in your generator has to be preserved between two calls to MoveNext. In our case, the local variables of the original method are a part of the state that has to be preserved.

Speaking of state, the magic is explained when you look at the implementation of the MoveNext method:
private bool MoveNext()
{
   switch (this.<>1__state)
   {
       case 0:
           this.<>1__state = -1;
           if (this.max <= 1)
           {
               break;
           }
           this.<a>5__1 = 1;
           this.<b>5__2 = 1;
           this.<>2__current = this.<a>5__1;
           this.<>1__state = 1;
           return true;

       case 1:
           this.<>1__state = -1;
           this.<>2__current = this.<b>5__2;
           this.<>1__state = 2;
           return true;

       case 2:
           this.<>1__state = -1;
           this.<c>5__3 = this.<a>5__1 + this.<b>5__2;
           while (this.<c>5__3 < this.max)
           {
               this.<>2__current = this.<c>5__3;
               this.<>1__state = 3;
               return true;
           Label_00C5:
               this.<>1__state = -1;
               this.<a>5__1 = this.<b>5__2;
               this.<b>5__2 = this.<c>5__3;
               this.<c>5__3 = this.<a>5__1 + this.<b>5__2;
           }
           break;

       case 3:
           goto Label_00C5;
   }
   return false;
}

This is the heart of the compiler-generated finite state machine designed to react correctly to subsequent calls to MoveNext. The initial state is 0. Every time the compiler encounters a yield return statement, it creates a new state and generates the code that:
  1. sets <>1__state to the new state
  2. sets <>2__current to the value in yield return
  3. returns true.
By the way, don't try to plug this code back into the sample program. The C# compiler will reject it, for reasons about which I will rant in another post.

The final mystery is resolved by looking at the GetEnumerator method implementation:
IEnumerator<int> IEnumerable<int>.GetEnumerator()
{
   IteratorTest.<FibonacciYield>d__0 d__;
   if (Interlocked.CompareExchange(ref this.<>1__state, 0, -2) == -2)
   {
       d__ = this;
   }
   else
   {
       d__ = new IteratorTest.<FibonacciYield>d__0(0);
   }
   d__.max = this.<>3__max;
   return d__;
}

After doing some tedious deciphering, this turns out to mean the following: if MoveNext That has already been called on this particular object, then create a fresh clone; if not, return this object. That's why we have both <>3__max and max: since arguments can be used as local variables within a method, the former is the original value supplied to FibonacciYield and the latter serves as a "local variable" field.

Making It Tidy

Now that we know how yield works, we can concentrate on avoiding memory allocation. Fortunately, C# allows you to write generators without implementing the IEnumerator<T> interface, as documented in help file:
In C#, it is not strictly necessary for a collection class to inherit from IEnumerable and IEnumerator in order to be compatible with foreach; as long as the class has the required GetEnumerator, MoveNext, Reset, and Current members, it will work with foreach. Omitting the interfaces has the advantage of allowing you to define the return type of Current to be more specific than object, thereby providing type-safety.

Omitting the interfaces, in this case, has the added advantage of being able to implement a generator as a struct, without it getting boxed later. Your final generator would look like this:
public struct ScroogeGenerator
{
    private int state;
    private int current;
    private int max;
    private int a;
    private int b;
    private int c;

    public ScroogeGenerator(int max)
    {
        this.state = 0;
        this.max = max;
        current = a = b = c = 0;
    }

    public int Current
    {
        get { return current; }
    }

    public bool MoveNext()
    {
        switch (state)
        {
            case 0:
                if (max <= 1) break;
                a = 1;
                b = 1;
                state = 1;
                current = a;
                return true;
            case 1:
                state = 2;
                current = b;
                return true;
            case 2:
                c = a + b;
                if (c >= max) break;
                a = b;
                b = c;
                current = c;
                return true;
        }
        return false;
    }

    public void Reset()
    {
        throw new Exception("The method or operation is not implemented.");
    }

    public ScroogeGenerator GetEnumerator() { return this; }
}

A few things to keep in mind:
  • When you write your own value-type generator, make sure you never cast it into an interface, or it will get boxed and make garbage. The best way to ensure that is not to implement any of the IEnumerable or IEnumerator interfaces.
  • The C# foreach loop does not call the Reset method. You can leave it unimplemented or empty if you'll use your generator in C# foreach loops only.
  • Don't reuse an instance of a value-type generator across different foreach loops. If you intend to do that, implement Reset and call it manually before reusing the generator.

Wednesday, September 19, 2007

.NUTS: Cemented Collections

Another month has passed. My intention was to write another post sooner -- especially because I already had material for it -- but time flies when one is immersed in work. Now that I have some free time, I can sit down and share another one of my .NET anecdotes. And so, without further ado, welcome back to my .NUTS column.

Deja Vu

If there's one thing that defines a modern language as much as its syntax, it's the way it handles collections. Therefore, it shouldn't be such a big surprise that most of my encounters with .NET quirks stem from the differences between its collection classes and those I've used in Java. Still, I hope this is won't turn out to be a tradition, otherwise I will have to rename this column to "Collection Corner".

This particular tale, just like the last one, starts with the Dictionary generic class. Specifically, it starts with my need to be informed when someone manipulates its contents. The classes I was writing had a rather simple purpose: associate event handlers with different input controller events. One class managed keyboard events, another mouse events and yet another gamepad events. Each one of these classes exposed at least one read-only property of appropriate Dictionary type. All went smoothly until I decided that I needed to know when someone added, removed or changed the handler for an event.

Keep Me Posted

The first logical thing to do was to check the documentation and see whether the Dictionary class itself offered the desired functionality. Despite my years of experience with Java collection framework, I hoped Microsoft would surprise me pleasantly. Good thing that I didn't bet on it, though. After all these years of evolution, the two most sophisticated mainstream languages still don't offer the fundamental courtesy provided by Delphi's good old TStringList class.

Just like I expected, I decided I would have to implement the desired behavior myself. The logical choice seemed to be to override whatever manipulates the collections contents: the Add, Remove and Clear methods, and the indexer. If you have any .NET experience, you're probably chuckling at my naïveté by now; if you don't, then I'll keep you in suspense a bit longer.

Virtually Polymorphic

Perhaps the greatest difference between Java and .NET, certainly the one I find most difficult to get used to, is the way they handle inheritance polymorphism. In Java, all non-private methods are virtual by default. If you don't want the derived classes to override a method, you have to explicitly declare it as final. Once a method is declared as final, your derived classes cannot contain a method with the same name.

In .NET, all methods are non-virtual by default. If you want a method to be overridable, you have to explicitly declare it as virtual. If you're overriding a method, you have to include the override keyword. If you want to keep a virtual method from being overridden, you have to declare it as sealed. And if you want to introduce a new method with the same name in the derived class, you have to use the new keyword.

At first, this seems like a lot of fuss to achieve virtually the same results, pardon the pun. However, these differences are extremely important, as they represent different design philosophies. The .NET way makes you think twice before you decide which parts of your code will be flexible and which set in stone. As Eric Lippert will tell you, this mitigates the notorious Fragile Base Class problem, which should be cool, right?

No Jack For Plug

The aforementioned philosophical differences are not all about how many polymorphic angels can dance on the head of a non-private pin. There are some very practical consequences of making all your methods non-virtual by default. One of these consequences is rather unfortunate: none of the methods in the Dictionary class are virtual. In other words, there's no way to modify the behavior of the Dictionary class so that you get a notification if its contents change. Or is there?

Everyone is really excited about the shiny new features in C# 3, such as partial methods. It will be interesting to see whether the collection classes will benefit from this change. I haven't downloaded Orcas yet, so I don't know. I won't hold my breath, though. Besides, a new version of the language and the surrounding framework won't help those who need to extend the collection classes now. What solution could they use?

Interface/Off

Fortunately, there is a way to hack around both the language limitations and the rigid design of the collection classes, without too much work. The key is to fall back to the interface polymorphism. Where before I exposed my dictionary as a read-only property of generic Dictionary type, now I have to change its type to generic IDictionary interface.

The second step is to include the IDictionary interface in the list of base types for my dictionary class, like this:
class MyDictionary<TKey, TValue> : Dictionary<TKey, TValue>, IDictionary<TKey, TValue>
{
// ...
}

How does this help? It makes sure that the compiler will remap the interface methods to the corresponding methods in the class. If there is a method in MyDictionary whose signature corresponds to an IDictionary method, it will be mapped to it; if not, an inherited method will be used.

The final step is to declare the methods you want to modify as new methods:
public new void Add(TKey key, TValue value)
{
   // ...
   base.Add(key, value);
   // ...
}

That's all there is to it, really. Some things haven't changed that much since the bad old times of COM and COM+.

Monday, August 13, 2007

.NUTS: Enum Conundrum

Welcome to .NUTS

I've been avoiding .NET for quite a long time. It's not that I'm an anti-Microsoft zealot, it's just that I used to code in Java at work and I figured that one platform full of frustrating limitations was more than enough. Recently, however, I decided to learn XNA on my own free time and that means getting involved with .NET and C#. It turned out to be just as frustrating as I feared, but at least it provided me with some nice blog material. Thus is the .NUTS "column" born in my blog, to document all that is weird in the .NET world. Expect stuff that might make you giggle, goggle and groan.

Enums Revisited

I first encountered the concept of enumerated types when I learned Pascal. Before that I owned a Commodore, so I dabbled in Simons' BASIC and 6502 assembler. Therefore, I didn't approach enums the way a C programmer might -- as a cleaner way of defining constants -- but as a way of defining a completely new type that accepts only those identifiers I define. The difference is subtle, but important: it shapes your attitude.

In .NET, enums have, obviously, inherited a lot of baggage from COM, which, in turn, comes from C. Furthermore, that baggage has been squeezed to fit the .NET luggage rack, where everything is an object, even the value types. Of course, value types are not really first-class objects, because they have to be boxed first. All in all, .NET enums are a part of a very leaky abstraction.

Starting Point

My journey of discovery started with an innocent little detail inside an excellent post on Shawn Hargreaves' blog. If you haven't read it yet, I strongly recommend it. I found it quite enlightening, especially the following advice:
If you use an enum type as a dictionary key, internal dictionary operations will cause boxing. You can avoid this by using integer keys, and casting your enum values to ints before adding them to the dictionary.
I found it strange that ints don't get boxed, while enums do. However, I was in a hurry to cobble my prototype together, so I just wrote it off as another one of those language eccentricities one encounters occasionally.

A couple of weeks later, I mentioned this to a friend of mine, who has been working in .NET since it first came out. He was even more flabbergasted: "That's weird. I mean, Microsoft keeps harping on how generic collections allow you to avoid unnecessary boxing. Seeing as how enum is one of the most common types for dictionary keys, the whole thing doesn't make sense at all."

That got me even more intrigued, enough to overcome my laziness and make me start poking around. This is where things started getting really interesting.

Now, those of you who don't care about the why and want the solution, skip to the part called "Finish Line", down below, near the end of this post.

Still reading? Okay, let's roll up those sleeves...

Stage 1: Observation

The obvious first step was to confirm Shawn's claim and work from there. For that, I armed myself with CLR Profiler (thanks to Mike Stall's blog) and I hammered out the following piece of code:
using System;
using System.Collections.Generic;
using System.Text;

namespace Sandbox
{
    enum TestEnum
    {
        e10,
        e9,
        e8,
        e7,
        e6,
        e5,
        e4,
        e3,
        e2,
        e1
    }

    class Program
    {
        static void Main(string[] args)
        {
            Dictionary<TestEnum, int> dict = new Dictionary<TestEnum, int>();

            for (int l = 0; l < 100000; l++)
            {
                TestEnum x = (TestEnum) (l % 10);
                dict[x] = 100000 - (int) x;
            }

            for (TestEnum x = TestEnum.e10; x <= TestEnum.e1; x++)
            {
                Console.WriteLine(dict[x]);
            }
        }
    }
}
The results were as bad as Shawn predicted: the code allocated 4,825,246 bytes (more than 4.5 MB), out of which 74.61% were instances of Sandbox.TestEnum type. If an enum is winding up on the heap like that, it must be getting boxed.

The next thing I did was to change the Main method to look like this:
        static void Main(string[] args)
        {
            Dictionary<int, int> dict = new Dictionary<int, int>();

            for (int l = 0; l < 100000; l++)
            {
                int x = l % 10;
                dict[x] = 100000 - (int) x;
            }

            for (int x = 0; x < 10; x++)
            {
                Console.WriteLine(dict[x]);
            }
        }
The profiler reported 24,692 allocated bytes, with nothing sticking out as especially wasteful. It was clear that .NET handled ints and enums differently, even though they are both value types.

CLR Profiler has a very neat feature that allows you to find out which part(s) of the code allocated the memory, by right-clicking on the offending bar in the histogram view and selecting the "Show Who Allocated" option. That will open the allocation graph view, which in my enum case looked like this:
(click on the image to enlarge)

Apparently, my enum was being boxed by ObjectEqualityComparer, inside the Insert method in the generic Dictionary class. Culprit identified, time to move on to the next stage.

Stage 2: Under the Hood

Contrary to my first impulse -- whip out the IL Disassembler -- I decided to first check whether the help files mentioned ObjectEqualityComparer. No such luck. ILDASM it is, then. The disassembly of Insert method in the generic Dictionary class revealed the following interesting snippet:
  IL_001e:  ldfld      class System.Collections.Generic.IEqualityComparer`1<!0> class System.Collections.Generic.Dictionary`2<!TKey,!TValue>::comparer
  IL_0023:  ldarg.1
  IL_0024:  callvirt   instance int32 class System.Collections.Generic.IEqualityComparer`1<!TKey>::GetHashCode(!0)
So my suspect, ObjectEqualityComparer, is an implementation of an IEqualityComparer interface, contained in the comparer field inside my Dictionary object. Here's what help file says about IEqualityComparer:
This interface allows the implementation of customized equality comparison for collections. That is, you can create your own definition of equality for type T, and specify that this definition be used with a collection type that accepts the IEqualityComparer generic interface. In the .NET Framework, constructors of the Dictionary generic collection type accept this interface.

A default implementation of this interface is provided by the Default property of the EqualityComparer generic class. The StringComparer class implements IEqualityComparer of type String.
A bit more digging in help files revealed this:
Dictionary requires an equality implementation to determine whether keys are equal. You can specify an implementation of the IEqualityComparer generic interface by using a constructor that accepts a comparer parameter; if you do not specify an implementation, the default generic equality comparer EqualityComparer.Default is used. If type TKey implements the System.IEquatable generic interface, the default equality comparer uses that implementation.
So how does the EqualityComparer.Default get defined? According to the help file, like this:
The Default property checks whether type T implements the System.IEquatable generic interface and if so returns an EqualityComparer that uses that implementation. Otherwise it returns an EqualityComparer that uses the overrides of Object.Equals and Object.GetHashCode provided by T.

In other words, the boxing happens because my enum doesn't implement IEquatable interface. The funny thing is that Int32 value type implements IEquatable, as does every other primitive numeric type. Yet enums don't. When you stop to think of it, it sounds logical: the Enum value type can't implement IEquatable because that would theoretically allow you to compare any enum to any other enum and obtain bogus results. Not that I'm convinced by that argument, but it's really a moot point, seeing as how I can't change that myself. That leaves looking for a workaround, which brings us to the last stage.

Stage 3: The Lesser Evil

Once you're reduced to looking for a workaround, your job is to look for the least dirty and the least ugly solution. The first thing I tried was to make my enum implement the IEquatable interface. Naturally, there was no way to make C# swallow that syntax. Next I tried setting the EqualityComparer<TestEnum>.Default property, but unfortunately it's read-only. Finally, grudgingly, I conceded to write my own implementation of IEqualityComparer. The first attempt was to write it as a generic class, but when C# complained about not being able to explicitly cast an unknown value type to int (within my GetHashCode method) it finally drove the lesson home: .NET generics are definitely not the same thing as C++ templates.

The final solution looked like this:
    class TestEnumComparer : IEqualityComparer<TestEnum>
    {
        public static readonly TestEnumComparer Instance = new TestEnumComparer();

        #region IEqualityComparer<TestEnum> Members

        public bool Equals(TestEnum x, TestEnum y)
        {
            return (x == y);
        }

        public int GetHashCode(TestEnum obj)
        {
            return (int) obj;
        }

        #endregion
    }
The dictionary declaration would then look like this:
            Dictionary<TestEnum, int> dict = new Dictionary<TestEnum, int>(TestEnumComparer.Instance);

Finish Line

To sum it up, for each enum type you intend to use as a dictionary key, you'll have to write your implementation of IEqualityComparer and pass it to Dictionary constructor. For each enum type you'll have to type 18 lines of boilerplate code -- you can squeeze it into less, I know -- but that's a relatively small price to pay for avoiding the memory waste caused by boxing your keys. I just wish it wasn't that ugly, but at least it's simple enough. Stay tuned for more .NUTS in the future.

Friday, June 1, 2007

Dark Side of Design Patterns

Every now and then I overhear someone excitedly talking to someone else about Design Patterns. They're so excited about it, you can hear the capital D and capital P quite clearly. And they use that tone: you know, the one usually reserved for great sports achievements. And, invariably, I can't resist the temptation to get involved. Things usually go downhill from there.

I can understand their chagrin. How would you like it if you just discovered something cool only to have some spoilsport tell you that roughly half of it is crap? Yet I just can't keep quiet; partly because I'm mean and love seeing their reactions, but mostly because I'm sick of the hype.

Patternitis
"The whole problem with the world is that fools and fanatics are always so certain of themselves, but wiser people so full of doubts."
Bertrand Russell

Don't get me wrong, I think design patterns are a great idea. Hardly a new one, but great nevertheless. The problem is that every Great Idea attracts its share of fanatics who think it's the coolest thing since sliced bread. It gets paraded around as a Silver Bullet and a Golden Hammer until its limitations percolate through the layers of hype. Inevitably, the general hype dies down -- if we're talking about a genuine Great Idea, not glossyware stuff like SOA -- and all that's left are pockets of hype that form about enthusiastic newbies or incompetent know-it-alls.

I personally love stamping out those little pockets and that's what I want to do with this blog post. I'll start by asserting the following:
  1. If you think that developing software can be reduced to applying and combining design patterns, you are wrong.
  2. If you think that a design pattern you don't completely understand must nevertheless be good, you are wrong.
  3. If you think that design patterns are a new invention made possible by OOP, you are wrong.
  4. If you think that someone is a good programmer just because they know design patterns, you are wrong.
  5. If you think that you must know design patterns to be a good programmer, you are wrong.
Now that the most common misconceptions are out of our way, we can get to separating the wheat from the chaff.

Gold vs. Other Glittery Stuff
"Any man whose errors take ten years to correct is quite a man."
J. Robert Oppenheimer

What is a design pattern? The original book by Gamma, Helm, Johnson and Vlissides (popularly known as GoF) takes a page and a half to answer this question. I prefer a shorter and simpler answer, even if it lacks all the accuracy of the original. Wikipedia has pretty good definition:
In software engineering (or computer science), a design pattern is a general repeatable solution to a commonly occurring problem in software design. A design pattern is not a finished design that can be transformed directly into code. It is a description or template for how to solve a problem that can be used in many different situations. Object-oriented design patterns typically show relationships and interactions between classes or objects, without specifying the final application classes or objects that are involved. Algorithms are not thought of as design patterns, since they solve computational problems rather than design problems.
Still a bit long for my taste, but it's quite usable. As a matter of fact, the first sentence is the most important; the rest just helps cement the scope.

The GoF book defines 23 design patterns: 5 creational, 7 structural and 11 behavioral. It took me a lot of conscious effort and quite a few years of working experience to admit that not all of those patterns are gold. In fact, the wheat-to-chaff ratio is quite close to 50 percent: there are 12 that I could describe as "okay", "good" or "great" and 11 that I see as "hack", "poor" or even "rubbish".


The Good
"The remarkable thing about Shakespeare is that he really is very good, in spite of all the people who say he is very good."
Robert Graves

If I learned something from my previous managers, it's to always dangle the carrot before using the stick. Seriously, though, the original GoF book has some really good patterns in it.

Take Bridge, for example. The best thing about this pattern is that it teaches you about the separation of concerns. You can adapt it to classless object-oriented languages, you can even apply it in structural programming languages. The main point is to keep the implementation primitives separate from the operations that use them.

Builder is another example of a highly useful pattern. Just look at SAX: they provide the director and you have to write the builder. Highly efficient and very elegant. By the way, I really recommend reading the original GoF book if you want to understand this pattern. Some of the other books attempt to explain it by applying it to convoluted problems such as constructing a MIME message or building a user interface. A word of advice to the authors: KISS.

A few other great patterns include Command, Composite and Template Method. These really make the best out of OOP and it shows. These are all nice examples of taking advantage of the benefits of OOP.

Then there is a whole range of patterns that have been around for a long time, long before OOP and long before GoF invented design patterns as we know them: Adapter, Façade, Flyweight, Chain of Responsibility and Observer.

Finally, I reserve a special place for Mediator, not because it's better than the rest, but because it's a perfect example of a good pattern that can be horribly abused. One word: Delphi. The "RAD paradigm" promoted by Delphi is to add objects to their containers and then write all the logic in a few huge Mediator classes. Delphi is based on an object-oriented language, has an excellent core framework and class library and yet it teaches its users to forget OOP. Bottom line: no matter how cool the pattern, don't overdo it.

The Ugly
"Beauty is the first test; there is no permanent place in the world for ugly mathematics."
G.H. Hardy

We have all, at some point in our lives, had to choose the lesser of two evils. That's most likely what you will be doing when you decide to apply one of the following: Proxy, Memento, Visitor, Decorator or State. All of these are a cumbersome solution for something that should have been supported or aided by the language itself.

Proxy, for example, is a necessary and useful pattern. The problem with it is that a lot of the languages require you to implement it by writing tons of boilerplate code. With some good metaprogramming facilities, Proxy becomes trivial.

Likewise, the motivation behind Memento is valid, but it should be solved by the language or its core library. Serializing and deserializing objects should be trivial, which means you shouldn't have to write gobs of code to do it. Look at the way you do it in Java:
ByteArrayOutputStream baos = new ByteArrayOutputStream();
ObjectOutputStream oos = new ObjectOutputStream(oos);
try {
  oos.writeObject(originator);
  oos.close();
} catch (IOException e) {
  // won't happen but we _still_ 
  // have to write code to ignore it
}
byte[] memento = baos.toByteArray();
Now compare it to Ruby:
memento = Marshal.dump(originator)
I rest my case.

Visitor is another example of hacking your way around language limitations. Most of the object-oriented code anyone writes needs only single dispatch. You can argue that supporting double or multiple dispatch in the language is wasteful, although there are ways around that. But when your language leaves you with no other choice and you need double dispatch, you will have to use Visitor. If you happen to need multiple dispatch, good luck writing and maintaining that code.

Finally, we come to Decorator and State. Both of these patterns are useful and both deal with the same issue: sometimes we want to adapt the behavior of individual objects depending on their state or some other trait we want to manipulate during run time. I believe that it should be possible without writing all the boilerplate code that you need for Decorator and State. I've learned and experimented with Self and Io languages and they both allow you to solve these needs very elegantly. Again, look at a sample implementation of State pattern in Java:
public class Bot {
  
  private int health;
  private BotState state;
  
  protected void changeState(BotState newState) {
    state = newState;
  }
  
  protected static final BotState HEALTHY = new HealthyState();
  protected static final BotState INJURED = new InjuredState();
  
  protected abstract static class BotState {
    public void takeDamage(Bot bot, int damage) {
      bot.health -= damage;
    }
    
    public void heal(Bot bot, int delta) {
      bot.health += delta;
    }
    
    public void enemySpotted(Bot bot, Object enemy) {}
  }
  
  protected static class HealthyState extends BotState {
    public void takeDamage(Bot bot, int damage) {
      super.takeDamage(bot, damage);
      if (bot.health <= 40) {
        bot.changeState(INJURED);
      }
    }
    
    public void enemySpotted(Bot bot, Object enemy) {
      bot.chase(enemy);
    }
  }
  
  protected static class InjuredState extends BotState {
    public void heal(Bot bot, int delta) {
      super.heal(bot, delta);
      if (bot.health >= 50) {
        bot.changeState(HEALTHY);
      }
    }
    
    public void enemySpotted(Bot bot, Object enemy) {
      bot.avoid(enemy);
    }
  }
  
  public void chase(Object enemy) {
    System.out.print("Chasing " + enemy);
  }
  
  public void avoid(Object enemy) {
    System.out.print("Avoiding " + enemy);
  }
  
  public void takeDamage(int damage) {
    state.takeDamage(this, damage);
  }
  
  public void heal(int delta) {
    state.heal(this, delta);
  }
  
  public void enemySpotted(Object enemy) {
    state.enemySpotted(this, enemy);
  }
}
Now compare it with the same thing in Io:
Bot := Object clone do (
  init := method(self health := 100)
  chase := method(enemy, ("Chasing " .. enemy) println)
  avoid := method(enemy, ("Avoiding " .. enemy) println)
  takeDamage := method(damage, health = health - damage)
  heal := method(delta, health = health + delta)
  enemySpotted := method(enemy, nil)
  changeState := method(newState, self setProto(newState))
)

HealthyBot := Bot cloneWithoutInit do (
  takeDamage := method(damage,
    resend
    if (health <= 40, changeState(InjuredBot))
  )
  enemySpotted := method(enemy, chase(enemy))
)

InjuredBot := Bot cloneWithoutInit do (
  heal := method(delta,
    resend
    if (health >= 50, changeState(HealthyBot))
  )
  enemySpotted := method(enemy, avoid(enemy))
)
I would even settle for hard, specific syntax supported by the language itself, like in UnrealScript.

Bottom line? Our languages really need to evolve. Combine prototype-based OOP that you can find in Self and Io with excellent metaprogramming offered by Lisp and you will have a language that kicks ass and doesn't need ugly patterns.

The Bad
"There is no stigma attached to recognizing a bad decision in time to install a better one."
Laurence J. Peter

Thus we come to the place where the bad things dwell. There's a variety of patterns that fall into this group and they do so for diverse reasons. Let's start with a couple that gave me nightmares for a long while.

Factory Method sounds like a good idea. Upon close examination, Abstract Factory is revealed to be Factory Method applied to Factory Method, which makes it sound even better. Only those who have been fooled by this pattern can appreciate the despair and the subsequent numbness brought on by writing tons and tons of the boilerplate code required by it. The worst thing is that it seems to be the only solution. Until you find out about Dependency Injection. Try it and you'll see the difference.

Another pattern that really fouls things up is Singleton. For a long time I couldn't find one good reason why I should have a class with only one instance, instead of making all that code static. Then someone asked what I would do if I had to pass an interface to it. Okay, that justifies it, I can even think of examples other than boilerplate Abstract Factory code. Another valid point is that you might want to switch from one instance to a pool and you don't want to rewrite the bulk of your code. Then there is the case mentioned in the GoF book that talks about subclassing the singleton and creating a registry of singletons. If you think that things are getting out of hand, you're right. The solution is the same as above: use Dependency Injection.

Then there's Iterator pattern. That one should be easy: use the foreach statement. And if your language doesn't have it, ask for your time back. It's simply unacceptable to have to write reams of ugly code for something we use so often. It deserves its own syntax.

What about Strategy pattern? According to the GoF and to all subsequent authors, you should use it to encapsulate a family of algorithms and make them interchangeable. That's about one thing for which I would not use it. If you want to do that use functions. Again, if you don't have them, ask for your time back. On the other hand, you could use Strategy pattern when your implementation strategy has to maintain state over time. But then it's not really Strategy, is it? Slippery things, these patterns.

Finally, there's Interpreter. I don't have any beef with its motivation: just look at how things have been evolving and you'll see several examples of minilanguages, scripting languages and XML-based stuff, all getting interpreted in the normal course of execution of your code. From printf format string of olden to XML configuration files of today, the idea has been in use for a loooong time. Thing is, this isn't a design pattern. It doesn't fit into the scope of a design pattern. And you won't make it fit by sketching out your favorite implementation of an interpreter for your favorite minilanguage. It just does not belong.


Patternitis Revisited
"When people are free to do as they please, they usually imitate each other."
Eric Hoffer

I have to give it to GoF though, they had some great ideas and the only time their scope slipped was with the Interpreter pattern. Sadly, the same couldn't be said about the later authors. I'll say it out loud: interface is not a design pattern. There are many things you could say about an interface. From a conceptual point of view, it's the definition of the contract your code will have to satisfy. From a language-specific point of view, it's a syntactic and semantic construct. But it is definitely not a design pattern. Neither is a symbolic constant name or an accessor method name.

It might seem that I'm beating a dead horse here, but I want to make it absolutely clear that not everything in software development is a design pattern. It's too easy to lose focus in enthusiasm, so do yourself a favor: learn the design patterns, keep using the ones you like (where applicable) and move on. There's a lot more to do.

Tuesday, February 6, 2007

Uneducational Crisis Pt. 3: Approach

Most of the things I wrote in the previous two posts can be disputed with counter-examples: not every professor is a Prima Donna; not all things they teach you at the university are irrelevant; there are great places where smart and likable people teach you good stuff; everything else is just "bad luck" and you "have to take the good with the bad". Let me tell you what I think about that:

I don't buy it.

There's a big problem with education as a system in general, not just in the CS field. And that problem involves the relevance of what we learn, from kindergarten to university. How many things did you learn in the ground school that you have completely forgotten? Let's face it, as a society we are doing a shoddy work of teaching our kids.

Why is education so bad? There is probably a variety of factors that enter the whole equation, but I think there are only two of major importance. One of them is the fact that teaching is not the number one motivation behind the existence of schools. Paul Graham has put it succinctly in his essay "Why Nerds are Unpopular":
Teenagers now are useless, except as cheap labor in industries like fast food, which evolved to exploit precisely this fact. In almost any other kind of work, they'd be a net loss. But they're also too young to be left unsupervised. Someone has to watch over them, and the most efficient way to do this is to collect them together in one place. Then a few adults can watch all of them.
The other major factor is that the basic approach to teaching is wrong. And that's what I want to explain here, so let's delve into it.

What Do You Want to Be When You Grow Up?

Whenever someone asks me how I came to be so obsessed with computers and programming, I tell them to blame my dad. No, he didn't teach me how to code, nor did he teach me anything important about the computers beyond turning them on and off and washing my hands before touching the keyboard. In fact, he can't code to save his life, which is perfectly fine, because he's a writer. What he did do, though, is much more important: he introduced me to computers.

How did he know I would like computers? That's the whole point: he didn't. When I was 5 or 6 years old -- I don't remember clearly anymore -- he started showing me the basics of photography. I found it entertaining, but I didn't take it too seriously. Then he tried with cinematography and the results were more or less the same. But then he showed me a computer and since that first look I am completely and totally fascinated with computers and the programs they run.

Why am I telling you this? Because I think I was extremely lucky. From that moment on, I knew what I wanted to be when I grow up; I had an interest that didn't pass and fade and I always had a new goal to achieve and a new way to improve myself.

I do know a few other people who have a passion in their life. I also know many more who never discovered anything they really like and lead largely disoriented lives. It sounds harsh, but it's true: having a spouse and kids cannot replace the feeling of having your own dreams. You can share your dreams with your family and complement one with the other, but in the end they are not interchangeable.

Nosce Te Ipsum

Here's the interesting part: I think everyone can and should have the chance to discover what they like. That's one of the most important things in our personal development and we usually don't have much help with it.

That's why most of the stuff they teach us at school is useless and irrelevant. How do you know something is relevant? You don't. You have to discover it. It's not something you can be taught, it's something you have to find out yourself. But that doesn't mean you shouldn't have help.

Educational institutions are ostensibly there to impart knowledge we will need in order to be useful and productive members of the society. But we don't know where and how we fit into that society. And the society doesn't know it either, so they just try to pour all sorts of stuff on our developing minds, hoping that after a while we'll get an idea where to head and how to specialize.

Optimism is good, but that's not optimistic: it's plain ridiculous. Imagine you had to pick what kind of food you want for your wedding party and the way to choose is to first learn by heart the recipes for a whole lot of different dishes and then use that to decide.

Yes, you will have an idea what each dish tastes like and yes, you might even make a dish or two to check out the taste. You might even get lucky and choose well. But if you made a mistake, there's no turning back: your wedding party will have food you don't like and that's it. You might get married again later and have another wedding party, but this one is gone for good. And the food sucked.

Of course, in real life you can get help from dedicated experts who specialize in that sort of stuff.
Imagine if you could get help with discovering your own talents and interests. Imagine if you could get that kind of help from people who specialize in it. Wouldn't life be a whole lot nicer?

Rat Races

Instead of that, what do we have now? We have to assimilate a considerable quantity of knowledge in a fixed time period, at the end of which our performance is rated and, if it is found satisfactory we can proceed to the next period and the next batch of knowledge.

There's a name you can slap on that description: competition. Our educational paradigm is based on competition and that makes it not merely misguided, but downright harmful. Instead of helping to find what our kids can do well, we force them to become "good enough" at doing a bit of everything. Worse, after passing through our educational maze, the kids are still not really good at doing anything of real worth.

Consider the most notable effect of our educational model: cheating. I really like how Wikipedia hit the nail on the head in their article:
A common venue for cheating is in education settings, where it takes a number of forms.
Of course it does. If you're competing for something that could bring you a gain you can clearly perceive, you might be tempted to cheat. But if you're forced to compete at something that you don't even perceive as lucrative (and nobody else really believes it either), you won't be tempted to cheat, you will consider it a natural option.

I'm not against the competition in education. Competition can be good, because it fosters a drive towards self-improvement. But you have to want to compete. And that happens either when you're competing at something you like or for something you perceive as lucrative.

Silver Bullet?

Of course, the solution is certainly a lot harder to implement than to propose. And I didn't even propose a complete solution, I just gave an idea. And I'm probably not the first to have it or even to voice it. And it certainly wouldn't solve all the problems and cure all the diseases and stop all the wars.

But don't you think it would be nice to try it?

Friday, January 19, 2007

Uneducational Crisis Pt. 2: Subject Matter

When I think about these last four years, I don't usually think about the university. Much more important and interesting things have been happening in my life. I think that says something about the quality of education as a life experience: you only consider it important when you're forced to do it during the better part of your day.

But when I do think about the university, the first thing that comes to mind are the professors. I've had a few excellent professors who were a pleasure to study with, but the rest ranged from merely disinterested to downright inept. In my previous post, I covered this topic in detail.

The second thing that comes to mind is what I learned. Or rather, what I was supposed to learn. Now that the things are drawing to their unceremonious end, it's amazing to look back and see just how many things I've been told were
  • misleading
  • wrong
  • obsolete
  • stupid
  • some or all of the above
With a lot of real-life experience in software industry, you can afford to be told such things because your brain will reject them automatically after a brief examination. But the reason I started writing about the educational problems in CS is not because I feel cheated out of my money, but because of the kids who go to the university to try to learn.

You see, I love programming and I like doing it for a living. And I enjoy the company of other people who do it. Sure, school might not matter if you're good enough (and infatuated enough). The knowledge is out there and you can learn it all by yourself. But you might not find it soon enough and you might get the wrong ideas at school and you might come out of it all utterly confused or frustrated or suffer some other damage. There's enough stuff in real life that will confuse and frustrate you, no need to start out like that.

So what's wrong with the stuff they teach you at the university?

Obsolescence

I agree that learning about the past is important. You need some context if you want to understand not only the how, but also the why of the things you see today. But that's no excuse for teaching obsolete stuff.

Take waterfall model, for example. For a big enough project, as most of real-world projects are, it simply does not work -- there are too many things that can go wrong and will go wrong. And yet the universities insist on teaching it as the way to execute software development projects.

Another good example is the insistence on Design Flow Diagrams. I'm not implying that DFDs are obsolete. Nor am I saying the same about any other concept from SSADM. Had any of our professors bothered to teach us SSADM well, I might have learned enough to compare it to what I'm used to working with.

As far as DFDs go, I find them stunningly imprecise and uncomfortable, compared to UML. This, of course, is a topic for a discussion that goes beyond the scope of this post, but it's also a bit beside the point. The point is that if the course is called Systems Analysis and Design, I don't think it can stay locked in time forever, covering SSADM in depth and merely mentioning the existence of UML and iterative processes and the myriad of other techniques that evolved in the mean time.

Scope

The problem with SSADM vs. UML is just an specific case of a bigger and more general problem: the scope is all wrong. If you are going to give an OOP course, you should take care to explain what OOP is, what OOP isn't, why it's been invented, how it works, etc. Sounds reasonable, but it doesn't happen. What you get instead is a Java course, where in the first few classes you get a very brief, confused and inaccurate summary of OOP concepts and then you delve into the language specifics.

I love learning new languages. As Kevin Kelleher notes, each language tries to solve some problem. That means that each new language you learn might teach you about a new class of problems or a new class of solutions. The thing is, you have to realize what the problems are and why they are problems before you can benefit from learning a new language. Otherwise you're just learning syntax.

You could do it the way I did it: learn a new language, compare it with the one you knew before and gradually become aware of the new problems. After enough time and enough new languages, you'll be able to think of languages in terms of problems and solutions. Indeed, nothing can completely replace the process of learning from your own experience. But that doesn't mean you aren't entitled to decent formal education.

It's like your parents telling you not to play with fire. You might heed their advice and still get burned by something you didn't know was hot. Or you might disregard their advice and get burned. But if they didn't tell you not to play with fire you would surely get burned out of ignorance.

Specialization

The problem of scope is what you'll see on the individual course level. But when you take a step back and examine the entire course curriculum, you'll find yourself facing the opposite extreme: breadth. The sheer breadth of subjects covered combined with the scope of each course makes you wonder why you got yourself into this at all.

Here's a bit of news for the guys who design the educational program: most of the software developers don't need to know about the implementation specifics of the datalink layer in ISDN. Nor do most network experts really need to know how to design a database in the third normal form.

I understand why the universities do this. It's a lot more manageable to have your courses flow sequentially and give everyone who survives the same diploma. Teach them all and let job sort them out. The question is, should ease of management excuse the poor results? Let's put it to a test: what would you think of a manager who told you, before the project started, that you'll have to implement a web-based user interface, a Swing GUI and an interactive textual interface, because it's easier to plan the project that way than to plan for capturing the UI requirements?

Relevance

All of the problems I've described here could be easily summarised in one word: relevance. Obsolete subjects are irrelevant to what you'll be doing. Courses with wrong scope teach you irrelevant things. Lack of specialization ensures you'll be learning a lot of irrelevant stuff. I postulate that every problem with the subject matter in CS education can be filed under relevance.

So how do we solve this? I hate doing this, but I'm afraid I have to do a Robert Jordan and leave you hanging. By now I've built enough context to engage in a discussion that I wanted to start from the beginning, but that discussion merits its own post. Therefore, I have no choice but to say RAFO.

At least I promise to finish in the third post.

Tuesday, January 16, 2007

Uneducational Crisis Pt. 1: Human Factor

If there's one thing worse than a bad programmer, it's a failed programmer turned professor. I don't know how common this is in United States, but here in Chile you see it a lot. And try as I might to pretend that I don't care, it's actually driving me nuts. Quite understandably, too: I could be doing interesting things instead of trying to guess what the latest in a row of brain-dead dilettantes wants me to write as a solution to his "ingenious" exam exercise.

On the other hand, this way I get the first-hand insight into the problems with education in CS field. Some of these problems, I suppose, are local and owe their existence to a variety of economic, political and technological factors, but I'm convinced that some are universal. Nonetheless, I shall not discriminate: I'll go over them all and a plague on both their houses.

This article, the first in the series, deals with the professors themselves.

Two Roads Diverged in a Yellow Wood...

Over the time, I learned to distinguish two types of CS professors:
  1. The Geek. This guy knows his stuff, because he actually works in computer industry and does his job well. Sometimes he is motivated by a genuine desire to teach new generations, but often he is teaching just to make a bit of money on the side or to lend a bit of academic weight to his name. More often than not, he is wonderfully inept at imparting his knowledge to the students, because he's a computer geek, not a teacher. All in all, he's guaranteed to be relaxed, easy-going and flexible. Mostly harmless.
  2. The Prima Donna. Who needs knowledge when you have Orwellian authority? This is the guy who will typically boast at least 20 years of experience in computer industry, who has a prominent consulting company and is certified by Carnegie Mello [sic] University. His classes are pure poetry. Vogon poetry, to be precise.
The Prima Donna is the type that does the most damage, so he merits detailed dissection.

Spot the Prima Donna

A Prima Donna professor is rather easy to recognize. He will exhibit a combination of several seamlessly coupled behavioral patterns from the following list:
  • Smugness. Usually one of the first signs that you're dealing with a Prima Donna is that self-satisfied attitude aimed to make you feel that some day, with lots of effort and a divine intervention or two, you'll get to be as good as this guy.
  • Hand Waving. One of the most valuable techniques for explaining the unknown is the hand waving. To those who came to learn, it seems that the Prima Donna is making a herculean effort to explain the concept and that they are simply too dumb to understand him.
  • Stating the Obvious. A good presentation slide will show only the key concepts and leave the explanation to the presenter. A bad presentation slide will show all the information in a pile of text you won't bother to read. In both cases, the Prima Donna will repeat the contents of the slide, with lots of Hand Waving, and you'll be left no wiser than before.
  • Exasperation. Sometimes a braver student will ask the Prima Donna to clarify something previously "explained" by Hand Waving and Stating the Obvious. If the Prima Donna is not in the mood to do it all again, he'll inform the audience that he explained it several times already.
  • Selective Hearing. If there's a student willing to press the issue despite the Exasperation, the Prima Donna might choose to answer another student's unrelated query or to simply go on to the next topic.
  • Condescension. You never know when you might get lucky: sometimes a Prima Donna will even give away unearned points when correcting an exam. But don't worry, he will make sure to inform you about it.
  • Objective Subjectivity. He might be teaching you how to solve problems that have more than one correct solution, but you better make sure you solve the problems the way Prima Donna taught you to do it.
  • Asserting the Authority. The Prima Donna will make sure you don't forget that he's the professor and you're the student, which means you owe him certain respect. He'll be especially sensitive about certain forms of disrespect, such as disagreeing with him.
  • Showcasing the Merits. In case you don't seem to be convinced of the Prima Donna's authority, you'll be informed of one or more of his certifications, nominations, recognitions, citations, publications, you-get-the-idea-tions.
Occasionally, you might get really unlucky and wind up with an embodiment of the archetypal Prima Donna. If there is an option to get the authorities to replace him, go for it.

Damage Done

It's becoming increasingly popular to be a nerd. Sure, you're still going to be bullied in school, but at least now you know you might be in store for a bright future. And those around you know it too. People tend to pay attention to things that might make them rich and when one of the richest persons in the world is downright nerdy, you can bet it won't go unnoticed.

The net result is that you get a lot of CS students who are in it for the glory and riches. These people don't know a lot about computers, but that's okay, because they're there to learn. The problem is that a lot of them also lack the talent. They're simply not good at computer science or any natural science at all.

Imagine all these people trying to learn about pointers from a Geek professor. Confusion abounds, chaos reigns supreme and in the end a lot of them will either fail the course (and hopefully change major) or pass the course having learned nothing.

Now imagine them trying to learn about pointers from a Prima Donna. Apart from becoming utterly frustrated and dejected, they'll learn a lot of garbage. The things that will stick the most are the parts that the Prima Donna invented or misinterpreted, because those are the most vivid explanations the Prima Donna will offer. That's the core of what makes him an "eminence" in the "computing world".

And now imagine yourself working with them on a project. Imagine working on a piece of code that has to traverse a tree with a co-worker who believes that "recursion is for programmers who have no style." Imagine hunting down an interoperability bug caused by bad handling of character encoding in a code written by a person who has been taught that "ASCII table is physically implemented in the microprocessor." Imagine writing business logic that has to use a database designed by someone convinced that a transactional database must satisfy the fifth normal form.

Not a cheerful thought, is it?

Foreword

Once I thought I wouldn't create a blog, ever. Then I started changing my mind, thanks to Joel Spolsky, Steve Yegge and Paul Graham. They had it all: interesting content, charismatic style and challenging opinions. But even so, my opinion of blogging went mostly along the lines that I had nothing substantial to say that these guys didn't already say or couldn't say it better. Which, of course, is quite irrelevant, true though it might be. As soon as that realization filtered through my thick skull, I decided to take the final step and inflict my thoughts on the rest of the world.

The first thing my blog needed was a name. Coming up with one wasn't nearly as hard as I dreaded -- I only went through three iterations:
  1. Paradogma Shift. Not bad, but it doesn't really represent what I want to talk about. Besides, I'd like to save the word paradogma for other purposes.
  2. Overflow Dump. Closer to the topic. Also, the initials are a nice touch: whenever I "overdose" on things that are stupid, ridiculous or utterly unacceptable, I can go and post to my blog. But, it makes it sound as if my posts are garbage and I'd like the benefit of a doubt.
  3. Beard's Eye. A modest word play and an obscure reference to Cryptonomicon -- what more could I wish for?
Here it is, then. My own beard's eye view onto society. I hope it's not too hairy.