praeclarum

Finally, a thumb drive that doesn't suck

2007-09-07T07:00:00.000-07:00

Way back in the spring, I was shopping at Fry's and decided it was time to upgrade my 16 MB thumb drive to something more... well... 21st century. So I picked up a bargain bin 1 GB drive for $20. Not the greatest bargain, but given that I once paid $400 for 4 MB of RAM, it was hardly worth debating.

I thought I was going to like it too - it had this neat mechanism that slid the USB connector to and fro - like a cheap geeky switchblade! Well, the drive worked fine, but the plastic covering and neat mechanism were complete trash. To add insult to injury, the hoop to connect to my key hoop was too small. All in all, the thing was worthless.

That is, worthless until I broke the plastic cover off and immersed it in epoxy. Now it's the greatest thumb drive I have ever owned. Check out this horrible pic:

What is this thing you ask? Well you're seeing a semi-profile of the finished product. It's just the circuit board, the USB connector, and the electronics submerged an encased in a nice epoxy (Super Glue SY-QS complements of Home Depot).

I got the idea from some work I did for the Indian navy. We bought this ridiculously priced router that was beyond military grade - it was apocalypse grade. It will exist on this earth long after we are gone. Anyway, I digress. Upon inspection, it was just a normal router fully submerged and encased in some form of epoxy (I'm sure it was military grade epoxy).

I knew epoxy wasn't a conductor so it was worth a shot to convert my crappy Fry's drive into something useable. Well, it's now beyond useable, I actually like it a lot. It's waterproof and pretty damned rugged. So far it works just fine. I wonder how long that will last?

Now, what else can I encase in epoxy...

Choosing C#/Java over C++ for a beginning programmer

2007-09-05T07:00:00.000-07:00

Christopher Diggins asked me present my view on whether beginning programmers should learn C++ as their first major language. Below is the response I wrote (slightly edited).

I think Christopher's original statement "you will find yourself to be much more productive in a shorter amount of time" just about sums up my feelings towards favoring C#/Java over C++. But you must understand that the debate is more complex than the conclusion.

Christopher presented the two pro lists for the languages, but the point about automatic garbage collection in C# should be emphasized even more. As Jamie Zawinski put it (http://www.jwz.org/doc/java.html):

That one point makes me able to forgive just about anything else, no matter how egregious. Given this one point, everything else in this document fades nearly to insignificance.

I am a decent enough programmer with enough experience that most of my C++ programs have only minor memory leaks. Sometimes I can even write one without any leaks, but such ones take some patience to design. My point is that C++ makes you think about memory ownership patterns. That's something you should think about, but C++ makes you think about it so much that you don't have much brain power left to tackle other problems (like getting your program to do what it needs to do).

With Java/C#, you are freed of this burden and you can focus on the problem domain.

His list for C# is pretty good, but I would add another feature that will soon be important: declarative style queries. When I find myself writing large data-backed applications, I end up performing a lot of queries. Doing this with just Sort, BinarySearch, and Hashtables is entertaining only for so long. The query syntax of C# 3.0 allows you to enter queries against object graphs similar to what's available in SQL.

In the debate between Java/C#, I have no opinion aside from the fact that they are nearly equivalent languages. Some syntactic differences, and C# is getting a bit of a power increase in then next version, but from a language standopint they are pertty similar. Both have fantastic libraries that will let you get things done fast. Both have good communities for support. Java's one benefit is that it is
applicable to businesses who do not drink Microsoft's juice.

---

My only reservation about favoring C#/Java over C++ stems from my own growth as a programmer. I began my programming career in BASIC but quickly moved on to learning Pascal/C/C++, the classic systems programming languages, so that I could do some classical systems programming. I believe that my abilities as a programmer have been
forever tainted, ahem, I mean influenced by that early work in low-level languages (by today's standards) writing low-level code.

Once you've written a fairly large programs in these languages, everything else seems easy and enjoyable to use no matter how screwed up it is (JavaScript).

Code and data become the same thing to you. You instinctively know the memory access patterns of your applications. You do not fear pointers or any other memory construct. You can read linux kernel code with ease. You will have a desire to perform meta-programming - code generation and the like - spawned by the greatness and simultaneous weakness of C++ templates.

But, frankly, it's like forcing professors to teach elementary school for 10 years before being allowed to teach students. Sure the lessons learned are valuable, but you will learn those lessons eventually anyway.

So my advice? Grab ahold of C#/Java and don't let go. Master the languages. Then learn a new language at least once a year. If you will be working with Cat, then you are already ahead in your studies. Learn C next, then C++ later on.

Dear Windows Vista

2007-09-03T23:58:00.000-07:00

Dear Windows Vista,

You are a wretched little operating system with no redeeming attributes.

-Frank

Extension Methods Make Code... Different

2007-08-30T07:00:00.000-07:00

Funny. When I saw extensions methods first introduced, Anders kinda treated them as hacks. They were just a little trick to make Linq compile down to standards conforming CLI assemblies.

But I like them a lot because it occurred to me that they could be used to relieve a little pain point I have when using delegates. I can't seem to conjur up the words to explain the problem succinctly, so let's just jump straight to an example.

Suppose I have a bunch of objects that have a function to query whether they are in a good state. Here's some code for that object and a little function that displays all good objects.


class Obj {
    int _val;
    public Obj(int val) { _val = val; }
    public int Value { get { return _val; } }
    public bool IsGood()
    {
        return (_val % 2) == 0;
    }
}

void DisplayGood()
{
    List<Obj> objs = new List<Obj>();
    foreach (Obj obj in objs.FindAll(delegate(Obj o) { return o.IsGood(); })) {
        Console.WriteLine(obj);
    }
}

END

This is pretty good, but there is one part I hate. This little bit: delegate(Obj o) { return o.IsGood(); } annoys the heck out of me. I wish I could just say Obj.IsGood, but that syntax isn't supported for some reason. Hmph. This isn't a huge problem, it's just an annoyance. Especially since C# 3.0 allows me to write something like objs.FindAll(o => o.IsGood()). That's pretty good.

But for fun, I could also restructure the code to take advantage of extension methods. I could do something like:


class Obj {
    int _val;
    public Obj(int val) { _val = val; }
    public int Value { get { return _val; } }
}
static class ObjFs {
    public static bool IsGood(this Obj o)
    {
        return (o.Value % 2) == 0;
    }
}

void DisplayGood()
{
    List<Obj> objs = new List<Obj>();
    foreach (Obj obj in objs.FindAll(ObjFs.IsGood)) {
        Console.WriteLine(obj);
    }
}

END

Hehe. I used extension methods to create a class that extends Objs with useful stuff. In this case, it's our goodness query function. Then when I want to call FindAll, I only need to pass ObjFs.IsGood.

Hmm, that was a bit work to achieve only a little. Ah well, good practice.

Why Dictionary is Great - Dynamic List with Indices

2007-08-28T07:00:00.000-07:00

I needed a list of objects that could be searched very quickly. I wanted to look up objects by ID, and also by property (e.g., person.City).

So I decided to write an enumerable container of objects with automatic indices. Out came the following code:


using Map = System.Collections.Generic.Dictionary<object,int>;
class Table<t> : IEnumerable<t>
{
  List<t> _data;
  Dictionary<string,Map> _indices;
  PropertyInfo[] _pis;
  public Table()
  {
    _data = new List<t>();
    _indices = new Dictionary<string,Map>();
    _pis = typeof(T).GetProperties();
    foreach (PropertyInfo pi in _pis) {
      _indices.Add(pi.Name, new Map());
    }
  }
  public T Add(T value)
  {
    _data.Add(value);
    int index = _data.Count - 1;
    foreach (PropertyInfo pi in _pis) {
      _indices[pi.Name][pi.GetValue(value, null)] = index;
    }
    return value;
  }
  public IEnumerator<t> GetEnumerator()
  {
    return _data.GetEnumerator();
  }
  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
  {
    return this.GetEnumerator();
  }
  public T SelectEq(string propName, object v)
  {
    return _data[_indices[propName][v]];
  }
}

It's short and sweet (if you ignore the Blogger butchery). The idea is simple: we automatically create indexes for common queries. Those common queries are chosen to be the properties of the object.

The final magic is in the SelectEq. It takes the name of the property (as a string unfotunately) grabs the right index for that property (_indices[propName]), then grabs the index of the item whose property is equal to the queried value, then returns that item. Phew... Did you get all that?

At first, I didn't think I would be using dictionaries for the indices. I thought something like SortedDictionary would be better. I mean, indices are supposed to be b-trees, not has tables. But Dictionary drastically outperformed SortedList and SortedDictionary. But there's one small problem...

Dictionary only stores unique keys. That means that the indices require that their associated property be unique (in order for that index to work). This is fine if we only want one result. But imagine a query like table.SelectEq("LastName", "Smith"). Here we expect more than one answer. The dictionary can't help us (without making the value of the index a list). Here, the b-trees can. So I guess I need to write more performance tests to see which performs best: b-trees or dictionaries with lists.

There are more possibilities too. With only a little work, new (dynamic) indices can be created based upon a passed-in comparison predicate. That would just be wonderful.

[Update - Some more thoughts]

I don't like the fact that the SelectEq takes a string. Strings don't change when identifiers are renamed. If comparison predicates are used, then we can just pass in the delegate as the select field.

For example, let's pretend we had people and we want an index on their full name:


string SortableFullName(this IPerson p) {
  return p.LastName + ", " + p.FirstName;
}

Now we can, hypothetically, create an index and begin querying:


Table<IPerson> people = ...;
people.AddIndex(SortableFullName);
people.SelectEq(SortableFullName, "Doe, John");

Yeah, that looks almost right.

My 1 Minute Trial of VB 2008 Beta 2

2007-08-27T16:29:00.000-07:00

Following my tour de force of trying WinFX for 20 minutes, I thought I would give the same treatment to the new version of VB. For reasons that are too varied to fit here, I have a special place in my heart for VB and think it's a pretty decent language (named parameters!), so I like to try it out from time to time.

VB, however, didn't get as thorough a treatment as WinFX - it pissed me off way too much within the first minute. This is too bad since I was looking forward to trying out some of its new features. (Maybe I'll come back to it when I'm more amiable.)

Also, I heard it's rude to complain about something without offering corrective action. So I decided to posts bugs for each of the problems that I will soon entertain you with.

Bug #1 lies with how annoying it is to post a bug. First you go to Help, File a Bug, then play with Micorosft's connect website. After about 6 pages of nonsense, I finally have a form where I can tell them what I think is wrong. To save you the pain, here is a direct link:

https://connect.microsoft.com/VisualStudio/feedback/CreateFeedbackForm.aspx?FeedbackFormConfigurationID=1160&FeedbackType=1

(Note to Microsoft, if you want feedback from users, make it easy for them to submit feedback.)

Now, here are the other bugs I filed:

Holding the control key and pressing arrows does not move the cursor. Holding control and pressing left or right should make the cursor move one "word" at a time (however VS defines "word" in this version). Instead, nothing happens. Can't believe they shipped Beta 2 with this bug.

Code formatter for VB automatically insists on inserting ByVal on all my params even though the documentation for VB clearly states that ByVal is the default:

"Passing Mechanism. The default mechanism for every argument is ByVal, which means the procedure cannot change the underlying variable element. However, if the element is a reference type, the procedure can modify the contents or members of the underlying object, even though it cannot replace or reassign the object itself." from http://msdn2.microsoft.com/en-us/library/cbs7z96t(VS.90).aspx.

I thought VB was a light-weight language? Why the hell then do I have to litter my code with all this ByVal noise? C# doesn't even require that.

Auto correction of missing subs is completely broken. So I type something like Call Foo("hello") when I still haven't defined Foo. The editor is nice enough to blue suiggle my Foo and to add an excruciatingly small outlined rectangle colored red under the last "o". Now in C# 2005, I just have to position my curso under "Foo", hit the context key on my keyboard, and choose "add stub method". VB, on the other hand, offers to create a unit test. Fine, so they screwed up the keyboard. Now if I position my cursor onto that 7x3 pixel rectangle...trying...trying...got it! Woohoow, it's expanded to something big and reminds me that I could have just hit Ctrl+Alt+F10. Thanks, that's a lot easier than just hitting the context key. Anyway, I can now easily click the big square, and, and, nothing. No corrections found. WTF? You can't even generate a stub for me? What about Ctrl+Alt+F10? Doesn't do anything. SOL I'm afraid.

And thus ended my one minute trial of VB 2008 Beta 2. My conclusion, it sucks. Oh my God, I can't even skip by word. It'll be a cold night in hell before I try to code in such a beast. When it ships again, I will give it another try. It is worth at least one minute of my time...

If you want a good development experience, just couple Resharper to VS2005. No, you don't get declarative queries, or extension methods, or literal XML. But you do get to write code. An ability that seems more and more difficult as these IDEs improve.

[Update 9:00 PM] Atleast Microsoft is fast with their initial responses. Two of the problems (the ByVal redundancy and the broken help for undeclared Subs) have been passed on to the appropriate teams. Given that Orcas is currently in it's endgame, it's possible that the issue might make it to the war team. Now the war team is responsible, essentially, for saying NO. It's their job to ship the product at a good level of quality on time. As we all know, introducing features (even options are features) at this time is generally a bad idea. Docs have to be changed, UIs changed, features implemented and tested, it's all a lot of work. Kinda late in the game to do that unless the feature is really worth it. So is removing ByVal, or fixing the Sub autogen worth it? My opinion is yes, but I can completely understand people's rejections.

Now the issue of the Ctrl word movement, the bug has been resolved pending their ability to reproduce. I guess you can't fix something unless you can analyze it. I understand. So I have two options, I can try to narrow the environmental characteristics down to the point where they can reproduce the problem, or I can just ignore it and hope it's a fluke of the machine. If I was a tester at MS and this happened on my machine, then I would be obligated to follow through with this problem. But if this is just me at home, then I'll just cross my fingers and hope for the best. Ship it.

[Update, the next day]

Looks like Microsoft threw down the hammer and has decided that both bugs won't be fixed. Guess I won't be using your language fellas. I'll catch you at version X. Perhaps you'll see the light by then.

Eben Moglen

2007-08-20T19:02:00.000-07:00

From Freeing the Mind by Eben Moglen:

Moglen's corollary to Faraday's Law says, wrap the Internet around every brain on the planet; spin the planet. Software flows in the network. It is wrong to ask, ``What is the incentive for people to create?'' It's an emergent property of connected human minds that they do create. The forms in which they create, like the evolution of spoken and written language, like the disposition of memes, cultural forms, patterns of pottery, shapes of musical endeavor, and so on, are structural characteristics of the human mind. We are a social species, and we create together; that's our nature.

Don't you just hate it when someone who represents a contrarian view to your own says something interesting, something you agree with, something that takes you aback for its eloquent statement of the greatest attribute of humanity?

Damn, and I really can't stand those GPL weenies...

Feynman my Hero

2007-07-02T11:46:00.000-07:00

There seems to be a lot of people who do not like the concept of heroes. Maybe it's a reaction against internet fanboys, but I think it's good to have someone to look up to. I have a lot of heroes in the various fields that I am interested in. Perhaps I should be calling them role-models, but I like the term Hero much more. These are the people that make our world worth sharing. Some heroes stick with you forever while others can be a bit transient. But it doesn't matter, once someone has touched your life you won't forget them. No need to burn incense or perform any silly rituals.

My heroes are of no surprise to anyone who knows me, and perhaps I'll even try enumerating my list some day. But there is no need now.

These last weeks however I was reminded of one of my heroes, Richard Feynman. I was recently re-captured by Feynman after reading QED, then by listening to his physics lectures, then by his book on the Character of Physical Law. Ealier, I really enjoyed his more playful books.

Today on Reddit I rediscovered my favorite article about Dr. Feynman. I can't do it justice by summarizing it, so instead I'll just plead with you to go read it. Please, kind reader, go read this article. I promise it is worth your time.

http://www.longnow.org/views/essays/articles/ArtFeynman.php?dupe=with_honor

Mr. Gore acting as Philosopher

2007-05-27T17:00:00.000-07:00

I read this in a coffee shop earlier today:

To understand the final reason why the news marketplace of ideas dominated by television is so different from the one that emerged in the world dominated by the printing press, it is important to distinguish the quality of vividness experienced by television viewers from the "vividness" experienced by readers. I believe that the vividness experienced in the reading of words is automatically modulated by the constant activation of the reasoning centers of the brain that are used in the process of cocreating the representation of reality the author has intended. By contrast, the visceral vividness portrayed on television has the capacity to trigger instinctual responses similar to those triggered by reality itself--and without being modulated by logic, reason, and reflective thought.

So says Mr. Al Gore in the Introduction to his book The Assault on Reason. I am not going to comment on the rest of the book, for I have only just begun reading it, but this paragraph stuck out fiercely in my mind. In fact, it me so hard, I put down my cup of hot chocolate that I was enjoying at Victor's (I was trying to add a link to Victor's coffee in Redmond, WA but Blogger's software is so shitty that it can't even handle links that I add in using their own editor, sheesh.) and came home to post this entry.

The reason it excites me so much is that I have spent a good amount of time considering Jeff Hawkin's ideas from On Intelligence, and the research his company Numenta is pursuing. His ideas can be (poorly) summarized as follows:

The neo-cortex of the brain functions similarly to a Neural Network.
The composition of the neo-cortex is homogeneous (that is, the same "cortical algorithm" is processed in all parts of the brain in the same fashion).
The differences between the two lies primarily with the use of feedback in the neo-cortex (outputs from higher up nodes in the hierarchy become inputs to nodes farther down).

This view of the brain allows one to imagine how the brain is able to develop invariant forms of objects (a cat is a cat regardless of how it appears), how it can store massive amounts of information (lower nodes capture invariant representation of simpler objects, nodes higher up use those representations to develop even more complex representations, etc.)

Really, I can't do it justice here primarily because I want to get back to Mr. Gore's quote.

In the Hawkin's model of the brain, varying sensory inputs are treated homogeneously -- hearing is processed similarly to sight, sight is processed like touch, nervous reactions (pain) are again processed similarly. Imagine the brain as one huge neural network that's constantly consuming input (of any kind!) and that is constantly driving outputs (feedback to lower neurons, drive currents for muscles).

This model of the brain explains a lot, but conscious thought is still something that is very difficult to subjugate to the cortical algorithm. Perhaps it's my desire that there is more to being human than simply containing an over-grown neo-cortex. I don't know, but I feel that there is more to me than a simple state machine.

Enter Al Gore's argument. He was in the process of exposing the reader to the fact that the American population has become numb to government and (perhaps rightly) politics. Part of his argument rests in the reader believing his point that television is a one-way medium and that we have become robots digesting our programming.

Given Hawkin's theory of cortical algorithm amplifies Mr. Gore's thesis. If our brain is just one big neural network -- feedback or not -- it will adapt to its sensory input. I will become emotionally attached to Peter's plight against Sylar, and I will wonder what exactly the Cylons intend to do next...

But there is this annoying consciousness of mine. The one that keeps nagging at me saying things like "people can't fly", "given a design capability beyond what we have today, super-intelligent robots would not re-create themselves in our image", "a Gundam's cockpit would place too much strain on the pilot", "Cheney looks creepy", "those angry people with the swords and guns don't seem to be getting any less angry".

It seems to me that Al Gore is stating that reading the written word naturally invokes this aspect of our brains while TV keeps us happy in the cortical algorithm.

God, I hope you were able to make sense of any of that. I apologize for the side topic, it just seemed interesting to me. Stay tuned for more programming-related fun. To keep this site balanced, I'll even throw in some pointer-arithmetic in the next post.

Assimilated by Win32

2007-05-27T16:11:00.000-07:00

This is a repost of an article I wrote back in March 2006. It seems to have fallen through the cracks as I moved from my own software to Blogger. Here it is for your enjoyment.

I always regarded straight Win32 development (that is, GUI app development using no wrappers over the Win32 API) as too time-consuming and tedious. Because of this, I have taught myself the big six: MFC, ATL, WTL, VCL, WinForms, and WPF (not at all in that order).

Nowadays I find myself using WinForms a lot. Even when not using the interactive designer of Visual Studio, WinForms makes a lot of GUI development trivial. However, there is a price you have to pay in order to use WinForms and the WPF; that price is managed code.

Now I love managed code. It provides a safe execution environment, a million classes that do two-million things (referring to the .NET library), garbage collection, excellent multi-language interoperability, and a very simple machine against which to write compilers. Let me repeat, I love managed code. But that’s not what this article is about.

Sometimes I feel the need or am forced to write unmanaged code. Even worse, sometimes I feel the need or am forced to write unmanaged GUI code. When it comes to native GUI code, I have a choice between MFC, ATL, WTL, VCL, or straight Win32. Prior to a month ago Win32 wasn’t even an option. It’s too ugly, it’s too old-school (where are my classes?), and nobody does it. Well, those were my opinions.

This last year, I have spent way too much time reading through all of The Old New Thing, Mark Russinovich’s Sysinternals Blog, Joel on Software, and Larry Osterman’s Blog (among others). These guys are old-school to be sure.

Old-school, in this instance, means not using C++’s (or C#’s, or Java’s, or Eiffel’s) object-oriented style of programming. You know the type: information hiding, single-object virtual function dispatch, lots of smart pointer, RAII, horrible function composition through bind, blah, blah, blah. No, instead, they tend to utilize more imperative function-based approaches. This is the style of coding that makes the source code of Project Oberon, and Quake (I, II, and III), and MMIXware, and the Linux Kernel, and SICP (and SICM), such a pleasure to read. They are devoid of the noise of modern object-oriented-programming languages, and contain nearly pure signal. This is also the style of the Win32 API.

Anyway, the point is that I have been thinking a lot about increasing the signal-to-noise ratio of my own code. I began to consider whether I could meet such an end by coding straight to the Win32 API. So I embarked on an experiment to write an application using straight Win32 and to compare that experience with writing WinForms apps.

I’ll summarize my conclusion: I like Win32 development. The Win32 API isn’t nearly as bad as I once thought, and some parts of it even scream out “I was designed very well!” This is not the conclusion I expected. I expected to get 1/4 of the way through development and to abandon the idea as just another waste of time.

So I was wrong, and I even look forward to the next time I get to write a native Win32 application. This article describes what I found along the way and the style of code that I eventually adopted that made development a breeze.

Let’s Begin with WinMain.

Open Visual Studio, create a new Win32 Project (without MFC or ATL) and you will get 8 files with the main C++ file consuming nearly 200 lines of code. Not
a great start at all. This is a part of the intimidation of Win32 projects. If it takes 200 lines and 8 files of overhead to create the base application, then how large is the Win32 overhead of the real application going to be?

As it turns out, not much overhead at all. These 200 lines, while foreign and a bit clumsy looking, aren’t bad at all. There are four functions generated for you (ignore the silly About function). These are WinMain, MyRegisterClass, WndProc, and InitInstance.

The first function WinMain is your entry point and the controller of the main GUI thread of your application. It is responsible for registering your window classes (more on those in just a moment), for creating the main (top-level) windows of the application, and for dispatching the messages for those windows. That’s just about all that your WinMain should do, and that’s all that the generated WinMain does do. There are of course some other trivial matters to accomplish such as initializing various services (Winsock, COM, CommonControls, etc.) but we only need to add that as necessary.

Object-oriented Windows.

So what about this registering window classes stuff? As it turns out, and this is the largest mental block to get through when first developing Win32 applications,
the windows API is object-oriented. That is, it has a notion of classes and instances. Every window on the screen has a class and that class dictates the behavior of that window and, often times, its child windows.

The class of the window, specifically, defines a few superficial traits: icons, cursors, and default background brushes, some esoteric traits: class styles, and “extra” information, and the most important trait: what to do when the window receives messages.

If we think about the Win32 notion of windows in terms of the C# object-oriented model, then the API defines an abstract Window class has one abstract method: HandleMessage. When you wish to create a new window class, you simply need to define a new class that overrides this function. To summarize in code, the OS would define the abstract window as:


class Window {
    public virtual Result HandleMessage(Message msg) {
        // Default processing of msg
    }
}

The application developer would then define their own windows as:


class MyWindow : Window {
    public override Result HandleMessage(Message msg) {
        // Special processing of msg
    }
}

The Win32 API is nearly identical to this setup with the only restriction that new window classes can only derive from Window and none of its (derived) base classes. Of course, the Win32 syntax is quite different too. Instead of the class definition of MyWindow above, one would instead write:


ATOM RegisterMyWindowClass(HINSTANCE hInstance)
{
    WNDCLASSEX wcex = { 0 };
    wcex.cbSize = sizeof(WNDCLASSEX);
    wcex.lpfnWndProc = MyWindow_HandleMessage;
    wcex.hInstance = hInstance;
    wcex.lpszClassName = L"MyWindow";
    return RegisterClassEx(&wcex);
}

Here, the function MyWindow HandleMessage overrides the default message handler (DefWindowProc) of the window. The registration process is a bit more verbose than the C# definition, but they are equivalent. Also, I should note that this is an incomplete registration, some important field assignments to wcex have been neglected to keep parity with the C# sample. Both the Win32 procedure and the C# class definition would have to be expanded to include all the options that
Win32 allows for window classes.

In C#, one would create a window by instantiating an object of the appropriate type (class). That would look something like:


Window wnd = new MyWindow(...);

In the Win32 world, window creation is just as simple:


HWND hWnd = CreateWindow(L"MyWindow", ...);

Again, I’m simplifying things, but the point is clear: the Win32 system is a class based system with one polymorphic function, the WndProc.

Once a window is created, the HandleMessage (or WndProc) function is responsible for defining the behavior of that window. Behavior here includes how the window responds to the user, how it responds to the OS, and how it displays itself.

It does all of this using the simple and robust method of message passing. When you want to tell a window to do something, you send it a message telling it what to do. When you want to get some information, you send it a message asking for information. When the window needs to tell other windows what to do (usually child windows), it sends them messages.

In the C# WinForms world, you add a bunch of public methods to a window class and invoke those methods in order to accomplish the same tasks. Message passing and function invocation are two means to the same end. Again we see the roots of OOP in the Win32 API.

In fact, the authors of SICP uses message passing to implement an object-oriented system. Since the Scheme programming language is quite a bit more powerful than the C programming language (against which the Win32 API has been designed), the Win32 message system isn’t nearly as rich as the SICP system; however, the ideas are the same. (Message passing can also be used to implement a very robust form of data sharing and control in concurrent applications. The programming language Erlang makes excellent use of this mechanism.)

Let’s take a step away from all these generalities now and answer the important question: how can I use the Win32 API to create rich applications with minimal effort.

My idea is to go with the flow. If the Win32 API is based around window classes and messagepassing, then let’s make full use of those ideas. Our assumption is that if we simply allow ourselves to be assimilated by the API, then we should find no resistance to using it and application development will become easier.

Assimilated Win32 Development.

The first step to coding a GUI application is to determine what classes of windows are needed. If I was writing a text editor, I may choose to create a new
window class that is superior to the built-in Edit and RichEdit classes of Windows. I could then use this “SuperEdit” wherever the user needed to enter data. If I was writing a simulation package, then I would develop a “WorldView” window class that could display some physical manifestation of the objects I was simulating. If I was writing a strip-chart viewer (think heart monitor, or seismograph, or lie detector), then I would create a class of window tailored to displaying strip-charts.

These are the types of things that the VCL refers to as components, and what WinForms refers to as controls. Me? I’ll just call them windows.

The first order of business for creating a new window class is to write the RegisterXClass function, where X is the class name of the window. This will be very similar to the one shown above. Refer to the documentation of WNDCLASSEX to learn of all the wonderful options you get.

Next, we need to implement some WndProc for that window. This function can begin simple and be added to as more functionality is required of the window. So we begin with a simple one:


LRESULT CALLBACK X_WndProc(HWND hWnd, UINT msg, WPARAM wParam, LPARAM lParam)
{
    switch (msg) {
    default: return DefWindowProc(hWnd, msg, wParam, lParam);
    }
}

We have now defined a window that does nothing more than emulate the default window. It accomplishes this by deferring all responses to the default WndProc. In order for the window to do something more interesting, we need to handle more messages.

As I mentioned briefly before, the Windows message system isn’t very rich. In fact, messages only carry three bits (not literally) of information: the message type, and two parameters, wParam and lParam. Because of this limitation, the true contents of a message are encoded into those two parameters. For instance, if you need to pass a complicated structure as a part of the message, then you can pass a pointer to that structure as one of the parameters. Windows makes use of this
and many, many more techniques for passing data with messages. For this reason, nearly every message has its own unique encoding based upon its type.

This is one of those things that at first makes Win32 coding seem so tedious. You end up spending a lot of time in MSDN figuring out just what the exact encoding of each message really is.

This must have gotten really old really fast for the Windows developer’s too since they ship a header file with the SDK that simplifies this whole process. The header file windowsx.h contains a macro for each of the pre-defined windows messages. This macro automatically decodes the parameters and invokes an event handler for each message. This makes writing the WndProc a breeze and leaves the developer only with the challenge of coding the logic of the handlers.

Let’s look at an example use of these macros. We know that we will need to override keyboard input to the window since a window that doesn’t react to the user is usually pretty annoying. To override the key input, we can handle the WM_KEYDOWN message.

Open windowsx.h and search for WM_KEYDOWN. There, we see a comment and a macro
definition:


/* void Cls_OnKey(HWND hwnd, UINT vk, BOOL fDown, int cRepeat, UINT flags) */
#define HANDLE_WM_KEYDOWN(hwnd, wParam, lParam, fn) \
    ...

The first commented line is a prototype of a function to handle the message. The second line begins a macro that will call that function from our WndProc.

We copy that prototype and paste into our own code to create our event handler:


static void X_OnKeyDown(HWND hwnd, UINT vk, BOOL fDown, int cRepeat, UINT flags)
{
    ...
}

This function will contain any process that should be taken whenever the user presses or hold a key down. Within switch statement of the WndProc for the window, we also have to add this simple line:


HANDLE_MSG(hWnd, WM_KEYDOWN, X_OnKeyDown);

The macro HANDLE_MSG will be sure to invoke the macro HANDLE WM KEYDOWN and
that macro will call our X OnKeyDown function. All messages will have a similar invocation of the HANDLE_MSG macro.

You should continue to repeat this process for each of the messages you wish to handle. Doing so will result in a very clean and simple WndProc and a set of event handlers that exactly match the messages you wish to handle.

Window State.

A window usually has some state associated with it. Text boxes must remember
their text; strip-charts must have access to the data to display; etc. Given the method for implementing a window class given in the previous section, we are never given a chance to record our state. (And let’s not even contemplate the idea of storing the state as a bunch of global variables. If we did that, then we would only be able to instantiate one instance of our window class. This defeats the whole purpose of using classes in the first place.)

Because we need the state of the window to be attached to each instance of a window, and because instances of a window are represented by HWNDs, we had better associate our state with the HWND. Fortunately, there is a very easy way to do this. All windows have a pointer-sized amount of memory in which the user (here, the programmer) can place anything they want. The function SetWindowLongPtr allows us to write to that pointer-sized area, and GetWindowLongPtr allows us to retrieve the value there.

Let us then create a single struct that contains all of the state of our window. When the window is created, we will allocate and initialize this data and store a pointer to it using SetWindowLongPtr. Then, whenever we need access to our state, we can use GetWindowLongPtr to retrieve it.

Here is a complete example of a window (well, minus the registration function) that implements such a scheme for storing its state.


struct X_State {
    int c;
};
template
BOOL CreateAndSaveState(HWND hWnd)
{
    BOOL fSuccess = FALSE;
    T *pt = (T*)calloc(1, sizeof(T));
    assert(pt);
    if (NULL != pt) {
        SetLastError(0);
        SetWindowLongPtr(hWnd, GWLP_USERDATA, (LONG_PTR)pt);
        if (0 == GetLastError())
            fSuccess = TRUE;
        else
            free(pt);
    }
    return fSuccess;
}
static BOOL X_OnCreate(HWND hWnd, LPCREATESTRUCT lpCreateStruct)
{
    return CreateAndSaveState(hWnd);
}
static void X_OnDestroy(HWND hWnd)
{
    free((X_State*)GetWindowLongPtr(hWnd, GWLP_USERDATA));
}
LRESULT CALLBACK X_WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
    switch (message)
    {
        HANDLE_MSG(hWnd, WM_CREATE, X_OnCreate);
        HANDLE_MSG(hWnd, WM_DESTROY, X_OnDestroy);
        default: return DefWindowProc(hWnd, message, wParam, lParam);
    }
}

In this example, we have a window with a single integer as its state. It creates and remembers this state when it is created by handling the WM CREATE message. I have given a complete version of the handler for that message, X OnCreate. This handler is robust in the sense that if there is any problem recording the state of the window, then the creation of the window is terminated all together. When the window is destroyed, the state is also destroyed.

Because the OnCreate handlers for all our windows will be pretty similar (they only differ in the type of state), I utilize a template function that handles the nitty gritty of creating and storing away the state. Please keep in mind that this template is only valid for plain old data (POD) structs and classes; that is, for structs and classes that do not have constructors, destructors, virtual functions, or contain classes with constructors, destructors, or virtual functions. If you wish
to make it a little more C++ friendly, then the calls to calloc and free should be replaced with new and delete. I preferred to use calloc and free simply because I wanted a guarantee that the code would not throw an exception. Exceptions are great in functional code, but really create disasters in imperative code.

Also, don’t forget that you’ll probably want to put a call to PostQuitMessage in the OnDestroy handler of your main window. If you do not do this then your application process will keep chugging along with no visible windows! That is not very user-friendly thing to do.

Commanding through Messages.

We have dealt with the definition of a window’s class and its
storage of state. Only one element remains: the control of the window by code. Up until now, our window operated solely on its own; to make it function cohesively with the rest of the application, we have to have a way to communicate with it. Again, we use messages to communicate with windows.

We can define our own message types for communication with our window. These messages mirror member functions of classes. We can have message for setting and retrieving state, and we can have messages that force the window to perform more complex operations. In the case of the strip-chart, we may define a message such as SC PAUSE that causes the display to stop updating with new data. In the case of the world view simulation window, we may define a message such as WV_ZOOM in order to zoom in and out.

Defining new messages is easy. We simply create a constant (either through a macro or a C++ const declaration) for the message type. The only stipulation that Windows places on these new messages is that their ordinal value should be no less than WM_USER.

So we could go ahead and state things such as:


#define SC_PAUSE (WM_USER+1)
#define WV_ZOOM (WM_USER+2)

And, with that, we have created new messages.

Our lives only become a little more complex when we decide to associate some data with the messages. We need to encode that data into the two parameters wParam and lParam. Life is simplest if we just bottle up the data into a struct and pass a pointer to that struct as the lParam. A lot of the Win32 functions do this, and it is pretty simple.

We must only force ourselves to make our own lives easier by writing HANDLE_* macros,
similar to those found in windowsx.h, for our own messages. This way our WndProc will have one uniform structure that is easy to interrogate and maintain.

We can also make the lives of the user of our window easier by implementing simple wrapper macros around SendMessage. Windowsx.h does this for the standard controls (see for example Edit GetLineCount amongst others) and it is a real time saver. Essentially these wrapper macros are defining a functional interface over the message passing system. We get the best of both worlds!

Putting it all Together.

Now that we have defined exactly what functions and macros we need
to create for our window classes, let’s talk briefly about code organization.

Under the principle of encapsulation, I try to put as much code as I can in its own translation unit (cpp file) and declare the functions as static so that they cannot be mistakenly called.

This means that each window class will have its own translation unit. In that unit, all functions (except one) will be marked as static. The WndProc will be static along with all the functions it calls. The one exception to this rule is the class registration function. This must necessarily be visible to the application code so that it can be called at initialization time. A prototype of the function will also be given in a header file for the window.

The message constants and macros of the previous section will also need to be contained in this header file. And that is it. The public header should be short and sweet: the register function, and the message macros. The state struct should not be in the header. That should exist only in the translation unit.

Following these rules creates a situation where all windows’ data are safely tucked away, and the clients of these windows have simple and strict means of interfacing with them.

Conclusion.

This article details my best understanding of the path of least resistance when
developing Windows GUI programs. In the past I have tried a variety of class libraries to make GUI development easier. What I have realized over time is that these libraries usually don’t make anything easier and typically reduce the signal to noise ratio of my own code. With that in mind, I have set a few simple rules to follow when developing these applications. When these rules are followed, I find Win32 development to be a simple and enjoyable.

Times Reader makes reading on the web enjoyable again

2007-05-15T15:17:00.000-07:00

I was lucky enough to stroll over to alarmingdevelopment.org today and catch a link over to the Times Reader. The Times Reader is a small client application (with a big footprint ) for (guess what) reading New York Times articles. Over the web.

That seems pretty lame doesn't it? I mean, isn't that what a browser is for? While HTML may stink to the high heavens for writing applications, isn't it pretty decent for documents? Now that I've seen the Times Reader, I see that while the browser (and I guess HTML 4.0) is good enough, the Times Readers is better.

Now there's controversy. So I'm going to write on two topics here. First, why I think it's better, and second on what this means for our little World Wide Web.

So how is it better? Columns - one of those features that you didn't know you needed until you saw it. Go try it out before I continue. Yes it's an install. Yes it requires .NET 3.0. Yes I know that's a pain in the ass. Just go do it please.

I'm waiting. Seriously, go try it.

Since this whole writing thing is a one-way medium (I have no readers to add comments!) I'll have to assume you went off and tried it.

You have just now whitnessed nicely formatted columns mixed with some very nice typography, all of which can be scaled to meet your current and ever changing preferences (sometimes I scale text to be HUGE). Did you try printing? Weren't the results, well, fantastic?

When I first started learning about typography (big Knuth TeX fan here) I learned the benefit of well chosen fonts in nice consistent layout (please, please, don't comment on this ugly standard Blogger skin). I learned the rule of controlling line lengths to make text easier to read, about rules of hyphenation, about picture placement. Others have learned these rules also. Paul Graham takes it to an extreme with his essays (cf. An Alternate Theory of Unions) but also publishes some very nice looking books. Problem is, HTML doesn't do columns. CSS (as supported by IE) doesn't either. And honestly, it doesn't do that great a job at typography either.

Times Reader, built upon WPF (yes the one I made fun of not too long ago), is able to take advantage of a smart document presenter. This little control solves the same problem that the early we browsers solved: displaying mostly text information to the user. But it does it better: it adapts the layout to your window size, it repaginates and recolumnates (ha!). That beautiful printout from before? That's the control simply adjusting itself to a new "window" size (one that just happens to fit nicely on a sheet of paper). It supports changing text size - not in that pathetic and ridiculous way that IE7 does it - nor in that pretty satisfactory way that Firefox does it - but in its own unique way where it can play with the number of columns, the column sizes, picture placement, and the number of pages.

I was first introduced to the idea of this type of dynamic layout with the paper Adaptive Grid-Based Document Layout. I have no idea what algorithm the WPF control uses, but it's pretty darned nice and achieves a lot of what that paper was proposing.

So why am I such a big fan of these columns? Because I like to read online, but hate reading online. If I'm online, then I am getting the latest info and I can perform research while reading. But the experience of reading online borders on painful for me. I have learned to hate scrolling. While reading, I have to sit poised with my hand over the mouse ready to tell the browser that I have digested everything. I can't just sit back with a beer and read Chris's latest craziness. This hate of scrolling has even lead me to consider retinal tracking to force the computer to respond to me (instead of the other way around). And then there is the whole loss of context when I do scroll. More columns = better context = less scrolling. If you disagree with me, fine. These are personal preferences, but I would ask you to go look at that Paul Graham article. Tell me it wouldn't be more enjoyable to read in a larger font with some columns. Be honest.

What does this mean for our WWW? It means that WPF just showed how basic our browsers actually are. While we bicker about conformance to arbitrary standards and wish for days when even the simplest CSS could handle proper column web pages on all browsers or (OMG) could adapt the page automatically to different viewing environments (1600x1200 windows over 20" vs. 640x480 displays at 2"), Microsoft just went out and wrote a control that did it. Score one for proprietary solutions.

But we can't all go out and write our own "Readers". Who would search them? I have no idea what Google's support for XAML documents is, but I can guess right now that it's not as good as its HTML support. So we're a bit stuck. There is a superior reading experience in a little proprietary app that uses a proprietary technology that runs on a proprietary OS.

Huh. What's more important to me? An enjoyable reading experience or my piece of mind knowing that I am using open standards. Hmm. I'm going to have to go with my reading experience on this one.

What's my conclusion? Browsers suck for reading. WPF makes reading more enjoyable.

Plan of action: I'm going to write an RSS reader using WPF, and it's going to be beautiful.

A Naive Implementation of MapReduce in C#

2007-04-03T07:00:00.000-07:00

After reading Ralf Lämmel's paper on MapReduce, I was inspired to code my own version in C#. Well, I didn't quite have the time to do a fully distributed and reliable version, so I just implemented the simplest, sequential, strongly-typed, and moderately efficient version I could think of.

I decided to utilize the IEnumerable`1 interface for the majority of my "collections" so that it could more efficiently handle very large data sets. That is, the IEnumerable`1 interface does not require that you store all elements in memory, but that you simply hand them out as requested. This seems to achieve what the Google authors mentioned in their original paper:

The intermediate values are supplied to the user's reduce function via an iterator. This allows us to handle lists of values that are too large to fit in memory.

In my version, you will see plenty of use of C#'s iterators in an attempt to emulate this feature:

class MapReduce
{
public delegate IEnumerable<KeyValuePair<TOK, TOV>> Map<TIK, TIV, TOK, TOV>(TIK key, TIV value);

public delegate IEnumerable<KeyValuePair<TOK, TOV>> Reduce<TIK, TIV, TOK, TOV>(TIK key, IEnumerable<TIV> value);

public static IEnumerable<KeyValuePair<TOK, TOV>> Run<TIK, TIV, TTK, TTV, TOK, TOV>(
Map<TIK, TIV, TTK, TTV> map,
Reduce<TTK, TTV, TOK, TOV> reduce,
IEnumerable<KeyValuePair<TIK, TIV>> input)
{
//
// Map and group all at once
//
Dictionary<TTK, List<TTV>> tempStorage = new Dictionary<TTK, List<TTV>>();
foreach (KeyValuePair<TIK, TIV> inputPair in input)
{
foreach (KeyValuePair<TTK, TTV> tempPair in map(inputPair.Key, inputPair.Value))
{
List<TTV> vals;
if (!tempStorage.TryGetValue(tempPair.Key, out vals))
{
vals = new List<TTV>();
tempStorage.Add(tempPair.Key, vals);
}
vals.Add(tempPair.Value);
}
}

//
// Reduce
//
foreach (KeyValuePair<TTK, List<TTV>> tempPair in tempStorage)
{
foreach (KeyValuePair<TOK, TOV> outPair in reduce( tempPair.Key, tempPair.Value))
{
yield return outPair;
}
}
}
}

As an example of its usage, I present the magical word counter:

class Program
{
private static IEnumerable<KeyValuePair<string, int>> WordCountMap(
string docId,
string doc)
{
char[] splitChars = {' ', '\r', '\n', '\t', '\x0085'};
foreach (string word in doc.Split(splitChars, StringSplitOptions.RemoveEmptyEntries))
{
yield return new KeyValuePair<string, int>(word, 1);
}
}

private static IEnumerable<KeyValuePair<string, int>> WordCountReduce(
string word,
IEnumerable<int> counts)
{
int wordCount = 0;
foreach (int count in counts)
{
wordCount += count;
}
yield return new KeyValuePair<string, int>(word, wordCount);
}

private static IEnumerable<KeyValuePair<string, string>> AllFilesInDirectory(
string path,
string searchPattern)
{
foreach (string fileName in Directory.GetFiles(path, searchPattern))
{
yield return new KeyValuePair<string, string>(fileName, File.ReadAllText(fileName));
}
}

private static void Main(string[] args)
{
foreach (
KeyValuePair<string, int> wordAndCount in MapReduce.Run<string, string, string, int, string, int>(WordCountMap,
WordCountReduce,
AllFilesInDirectory(args[0], "*.cs")))
{
Console.WriteLine("{0}: {1}", wordAndCount.Value, wordAndCount.Key);
}
}
}

I would like to end this entry with a reference to Christopher Diggins' (the inventor of the Cat's) implementation in Cat (a stack-based functional language). It's short, insanely short in fact:

define map_reduce { [map flatten self_join] dip map }

For an explanation of this function, please read Christopher's writeup.

Saturday

2007-04-02T17:30:00.000-07:00

On Saturday, I started out on reddit.com. Things seemed a little silly there so I moved on to programming.reddit.com. Nothing was really standing out but I rather enjoyed my read of The Architecture of Mailinator.

Then I happened to see this: Magic Ink. It's a pretty long, but kinda pretty article I thought (well, the font size could be increased, but most graphic designers yell when I say this). I didn't know if I had the time to do the article justice. You see, if an article is nicely formatted, and it's apparent the author spent some time making it so, then I assume that they spent an equal or greater amount of time thinking about its contents. So, in my world, pretty article = good article. I do read ugly articles, but they have to win me over in the first couple paragraphs (ironic considering this blog entry, eh?).

But it's still long, so I started with the damn fine pictures that immediately jumped out at me. I love the Amazon book search results, his movie time sheet, and his BART navigation software. Stunning! Go look now! (Why doesn't my software look that good? Oh yeah, I spend too much time thinking about improving the code than I do thinking about the UI...)

The author had me impressed. At this point, the article could be a big pile of Microspeak for all I cared - at least he sparked my imagination with his pictures.

I still wasn't sure whether to devote time to the article so I decided to investigate the author (talk about ADD). Turns out that he is a pretty prolific developer with a good eye for design. Check out his latest shirt design software - text entry is a little buggy but I found the whole experience very enjoyable.

So he's won me over, it's now time to read that article! Of wait, what's this? A quote from Alan Kay that I haven't read yet? A link to a video presentation? Uh, oh, more distraction!

Honestly, I haven't read much from Mr. Kay, but I am a big fan of his quotes. Given all those great memories, a video presentation must be worth the viewing.

It absolutely was worth the viewing. Though he speaks quite slowly (even with the video played in fast-forward) every minute (or fast-forward pseudo-minute) is well worth your time. Some of the most memorable ideas I got from it include:

Bob Barton was a pioneer in matching computer architectures (hardware) to software. The B5000 is such an example, the Alto seems to be another. Mr. Kay has a slide showing The Descriptor that intrigued me enough to surf around and find it. Now I just need to read it. I have been interested in these types of machines ever sense reading about the Scheme interpreters put into hardware - the electrical engineer in me gets all excited.
The Molecular Biology of the Cell as a very good book that uses strong fundamentals to take non-biologists/chemists all the way up to being pretty knowledgeable of the cell. Wow, if that sentence doesn't inspire you, I don't know what will! I just have a fascination with these types of books, from SICP to SICM, from QED to On Intelligence, from The Molecular Biology of the Cell to, well, I don't know yet.
Squeak is 250,000 lines of code compared to Windows' 50,000,000 lines. That's a huge difference! Obviously Windows is doing a bit more, but is it really doing 200 times more?
He wants to bring 250,000 down to 20,000. Impossible? Maybe. However I am quite excited about the idea. A single person can comprehend 20,000 lines of code, but they cannot (or I cannot) comprehend 250,000 nor 50,000,000.
Objects from the bottom to the top! From drivers up to presentation slide elements. Everything is programmable and extensible. (Again, from the proposal.)
Objects done right. Instead of C++ or .NET's concept of objects, systems should be based upon agents using message passing. As one of the devotees who saw the light with Erlang and can see where that technology can go, this is is very exciting to me.
Objects done simply. Checkout the bootstrapper. It's so simple!
The Golden Box. I wish Mr. Kay had given better references, but if you search around Ian P.'s work enough, you can find what he's talking about. God I want a Golden Box.

So my viewing of an hour and a half video took me 4 hours (even when watching parts in fast-forward!), and I still hadn't even read the Magic Ink article!

That was my Saturday.

Yes, I did finally read the article, and it was completely worth it. I recommend you do the same.

My 20 Minute Experience with WinFX

2006-05-25T07:00:00.000-07:00

The May CTP of WinFX is out (along with Beta 2’s of Vista and Office). This release should be functionally equivalent to the released product and therefore deserves some sort of play time and review. However, since I happen to be knee deep in another project, I could afford only 20 minutes.

First, a disclaimer. In my previous life I spent a year working on Avalon (WinFX’s real name) and have a pretty close relationship with it. Actually I spent most of my time playing with the imaging aspect of it. My contributions were all in the .NET namespace System.Windows.Media.Imaging and in the native COM DLL WindowsCodecs.dll. The code for the .NET imaging components is hosted in the managed DLL called PresentationCore.dll (along with everything else in the kitchen). However, that code isn’t at all interesting because it is just a thin wrapper over the real imaging code of WindowsCodecs.dll. While WindowsCodecs annoyingly does not include its own COM typelib, you can get a flavor for it by looking at the static classes under MS.Win32.PresentationCore that start with the letters “WIC”. Anyway, I’m pretty proud of that code even though my small contributions lay purely in its design and test. In WindowsCodecs.dll, you will find some of the most robust and easy to use imaging code available anywhere. Well, that’s how I feel about it anyway.

So what about the rest of WinFX Runtime Components? Well, it has a lot of rough edges.

Let’s start with the installation. All-in-all you’re talking about a 24 MB download (2 MB for the installation app which then downloads 22 MB for the actual product). That’s pretty steep considering you also need to install version 2.0 of the .NET framework if it’s not already there. That means you have 46 MB of downloading to do before you can witness your first WinFX application from a clean XP SP2 install. Oh well, we all have broadband connections now right? Also, this is a non-issue if you are running Vista.

Once the beast is installed things get boring from there since MS doesn’t ship any demos with it. This makes sense given that this is “just” a set of programming libraries and they need to keep the installation size down (if you consider 22 MB “down”). However, that doesn’t change the fact that it’s pretty boring.

If you want to see something interesting go on over to the Petzold Book Blog and his WinFX book site. There you will find a great tool called “XAML Cruncher”. XAML is the XML-based declarative language for describing application user interfaces. This is a simple text editor that gives a live preview of the UI that results from whatever XAML you enter. Think of it as the Read-Eval-Print-Loop (REPL) of WinFX.

XAML Cruncher uses WinFX’s new deployment system for applications. This deployment system attempts to give WinFX applications a standardized and safe method of installation. There are just two major problems with it.

First, it does not work with Firefox (at least, for version 1.5.0.3 and as the application is hosted by Mr. Petzold). I hope that this is a bug that will get fixed in the release, but it is pretty disheartening to see such malaise on the part of the programmers towards a user’s right to choose their own programs. What does the web browser have to do with downloading a someone’s application? NOTHING! And yet it makes or breaks the experience. I am an application developer. If I have the choice between a deployment system that can only reach 50% of my customers and another that reaches 100%, which should I choose? The answer’s obvious, and that is why this bug should be priority #1 for the Microsoft WinFX deployment developers.

Second, and this is just as important, the error reporting features suck. When the installation fails for whatever reason (perhaps because you are using Firefox?) the installation box simply gives a glib and misleading error message. For instance, when using Firefox, the error:

“Cannot Start Application: Cannot download the application. The application is missing required files. Contact the application vendor for assistance.”

So not only is a deployment bug not identified, but the vendor is blamed. Great! Sometimes you have to wonder what the Product Managers are thinking. As a smaller point, they also break the standard Windows message box functionality of allowing the user to copy the box’s text by hitting Ctrl+C.

When one clicks on the Details button, they are then greeted by a whole lot of programmer info. Woe to any non-programmer who has to read that mess to figure out what is going wrong.

OK, enough whining about the deployment app. Let’s move onto WinFX proper. When you get XAMLCruncher working, you will be greeted with some minimal XAML and a huge button. The huge button is actually the result of the XAML.

XAML is a very very very very verbose declarative language. When it was first being designed, it was supposed to be human readable and writable (like HTML). However, Microsoft has long since abandoned that goal. There are tools to generate XAML, but, just as in HTML, it is best to get familiar with the underlying language before giving up and using a tool. Some, like Mr. Petzold, think of the use of the tool as a crutch. His thoughts in Does Visual Studio Rot the Mind? are very fun reading.

I have a few issues with declarative languages, and one such issue was immediately brought up when I played with the first XAML file I grabbed from Mr. Petzold’s site: UnicycleMan.xaml. After loading the file, the little guy on the cycle was making his way around the curve just as expected and declared in the XAML. There is a problem though. On my system (AthlonFX 64 X2, Radeon X800GT) the guy is constantly followed by his ghost: a flickering afterimage of his state about 1 second previous.

Yes, this is a beta version of WinFX and bugs are to be expected. The problem lies here: WinFX will not be shipped bug free. That’s just a standard problem with large pieces of software developed by large groups of people. Let’s say that one of the bugs that makes its way into the final product is just as obvious and easy to replicate as this “ghost” bug. What is the application developer to do then? His code is perfect! It declares that a little guy should go around the curve. Know where does it declare that there should be a flickering ghost following him. The developer is then faced with three options: (1) Wait for MS to fix it, (2) Figure out a work around, (3) Stop using WinFX.

No rational company would delay the deployment of their own app on the hopes that another company will fix their bugs. It makes no business sense. So option 1 is out the door. What about 2? Workarounds are as familiar to developers as clipping shears are to a gardener. The problem with these workarounds in XAML however is that we have no experience debugging declarative languages. Where is the flicker bug? Is it in the matrix animation code? Is it in the video driver? Who knows! We have no debugger to help us. The best one can do is guess and check: try changing some XAML and see if that fixes it, if not, change something else. This is a horrible way to program.

And what about the third option? We could always go back to Win32, but for some reason not everyone likes to spend years implementing and debugging their own graphics engines. I don’t know why not, they just don’t!

So where is the programmer left? Well, between a rock and a hard place. That is why developing WinFX applications (and ASP.NET applications too) is sometimes so frustrating: everything works beautifully until it doesn’t. When you get to that point, you’re pretty much on your own.

That’s the thought that I last had when concluding my 20 minute experience with the May CTP of WinFX. And that’s the thought I’ll leave you with.

Patterns of Integer Usage

2006-04-30T07:00:00.000-07:00

Can stronger type systems help us write better code? I think so. As an example, I consider three patterns of integer usage and how stronger or more explicit type systems can help us avoid bugs when dealing with those integers.

There are three general uses of integers in programming languages: in the majority of cases they are used for indexing into arrays and other containers; alternatively, they are used for numerical computations; lastly, we use them as a poor-man’s bitfield or other general-purpose memory container. If we wanted to be so-last-year we could say that there are three patterns to the usage of integers.

Sometimes these usage patterns are given representations in the type systems of our programming languages. In C++ for example the type size_t (or its cousins vector<>::size_type, string::size_type, etc.) is used to index into things while we typically use a plain int for numerical computations and the wonders of stdint.h for bitpacking. Even though all of these are just aliases for C’s only notion of integers, these conventions at least force us as programmers to think through our own appropriate uses of them.

This representation of usage patterns as types helps the programmer avoid errors. Later on in this article though, we will see how a stronger type system can help us even more.

In his presentation The Next Mainstream Programming Language: A Game Developer's Perspective, Tim Sweeney notes that 90% of the integers in Unreal are used to index into arrays. The remaining 10% are then split between bitcoding and numeric computations. I think most of us will agree that his numbers are somewhat typical of our own C/C++ programs.

However, this is not always the case. Sometimes we use integers as a means of indirection and therefore have to code.

In this article I want to look for possible refinements in our use of these three kinds of integers. This article is a summary and in some cases an expansion of the ideas presented by Tim Sweeney in his presentation (see the previous link), Reg Braithwaite’s I'll take Static Typing for $800, Alex, and on Wirth’s Algorithms and Data Structures.

Integers are array indices

Some languages are strict in their uses of integers. Languages like Modula-2 and Ada give you very fine-grained control of your integers and subtypes thereof. In these languages emphasis is placed on static (compile time) checking. Other languages are looser and depend solely on runtime bounds checks (Lisp, C#).

I am a big fan of static type checking and static error analysis. This preference comes from my roots as an embedded systems developer. When writing these types of systems, the developer must be able to (1) describe every possible way the system can fail and (2) describe how the system should recover or fail (in the large) given these failures (in the small).

Imagine a language in which you can only index into arrays with an integer that is statically guaranteed to not generate out of bounds exceptions. If the size of the array is static, then it is trivial for a compiler to ensure this. However, things aren’t quite as simple when array sizes are dynamic. In that case we must rely upon runtime bounds checks.

Let us therefore consider two ways that these bounds can be made: one that relies upon the programmer being super anal-retentive (professional) and others that force the compiler to do that boring work for us.

Consider the prototype and comment for the function lubksb as given in Numerical Recipes in C++:

#include <vector>

typedef std::vector<double>                 Vec_DP;
typedef std::vector<double>                 Vec_INT;
typedef std::vector<std::vector<double> >   Mat_DP;
typedef Mat_DP                              Mat_I_DP;
typedef Vec_DP                              Vec_IO_DP;
typedef Vec_INT                             Vec_I_INT;

//
// Solves the set of n linear equations A*X=B.
// Here a[0..n-1][0..n-1] is input, not as the matrix A but rather as
// its LU decomposition, determined by the routine ludcmp.
// indx[0..n-1] is input as the permutation vector returned by ludcmp.
// b[0..n-1] is input as the right-hand side vector B, and returns the
// solution vector X...
//
void lubksp(Mat_I_DP &a, Vec_I_INT &indx, Vec_IO_DP &b);

That’s a lot of type definitions and a lot of explanation (7 lines of code and 6 lines of very important comment) for a function, and a lot for a programmer who uses this function to keep in mind.

If you think that is bad, consider all the code that the guy who writes lubksp needs to write to ensure that all these conditions are met.

The problem lies in the fact that C++ is not very descriptive of the necessary conditions for a function to succeed. Let’s consider for a moment a hypothetical language that is more descriptive. One that utilizes algebraic types in order to convey these preconditions. In this hypothetical language, the function’s prototype could be boiled down to:

func lubksp{n: nat}(
    in a: [n, n]float,
    in indx: [n]nat < n,
    inout b: [n]float
) : void;

In this notation or language:

n is any natural number

a is a matrix with dimensions n by n

indx is an array of n natural numbers that are all less than n

b is an array of floats with dimension n

When this function is run with unknown inputs, it is equivalent to the following C# function:

static void LU_Back_Substitute(float[,] a, int[] indx, float[] b)
{
    if (a == null) throw new ArgumentNullException("a");
    if (a.GetLength(0) != a.GetLength(1)) throw new Sys;
    int n = a.GetLength(0);

    if (indx == null) throw new ArgumentNullException("indx");
    if (indx.Length != n) throw new ArgumentOutOfRangeException("indx");
    for (int i = 0; i < n; i++) {
        if (indx[i] >= n) throw new ArgumentOutOfRangeException("indx");
    }

    if (b == null) throw new ArgumentNullException("b");
    if (b.Length != n) throw new ArgumentOutOfRangeException("b");
}

In Eiffel these argument assertions are called the preconditions of the function. They are written in a much nicer way than is available in C# because Eiffel supports the notion in its syntax. However, not even the Eiffel version is as succinct as the hypothetical language's version.

Now let’s consider one of the overloads of the Substring method of the String class in the .NET library. Its prototype is simply:

class String {
    public string Substring(int startIndex, int length);
}

We all know that there is a very fine relationship between startIndex, length and the actual length of the string being operated upon. That relationship, however, cannot be expressed in C++, C#, VB, Delphi, Python, or any other mainstream languages. However, the hypothetical programming language can express it completely. Consider this prototype:

func Substring(
    in str: String,
    in startIndex: nat < str.Length,
    in length: nat <= (str.Length - startIndex)
) : String;

This prototype spells out very clearly which values of startIndex and length are valid for every invocation of Substring.

The str parameter is required to be a valid String—no null values are allowed.

The startIndex must be a natural number that is less than the length of the string.

The length parameter depends on the first two parameters.

Now, all this parameter checking is actually performed by .NET’s implementation of Substring, but those checks do not occur until runtime. In the hypothetical language however, those checks occur at compile time.

To demonstrate this, consider a really boring application that allows a user to extract a substring of a string. The user will be asked to enter the string, the startIndex, and the length of the substring. Also imagine that our input validation code is good enough to verify that the startIndex and length are integers, but nothing more. Something like this:

func ProcessInput : (void -> string)
{
    obj str := ReadString() : string;
    obj startIndex := ReadInteger() : int;
    obj length := ReadInteger() : int;

    // Somehow call and return the value of Substring
}

(The syntax of this language borrows from Damian Conway’s SPECS.)

ProcessInput is a function that takes no arguments (void) and returns a string. The string to be returned must come from a call to Substring, but there is a problem. Our local startIndex and length are not type-compatible with the parameters of Substring!

To make them compatible, we need to cast them to the appropriate subtypes. Tim Sweeney proposes one syntax for such casts and I highly recommend you go through his PowerPoint slides. He proposes a casting operator that can either succeed at performing the cast and will execute a body of code, or will execute an alternative body of code. It’s essentially an if-else construct dedicated to casting. Continuing our example, the remainder of ProcessInput using such a cast would be:

    if cast (obj safeIndex := startIndex : nat < str.Length) {
        if cast (obj safeLen := length : nat <= (str.Length - safeIndex)) {
            Substring(str, safeIndex, safeLen);
        }
        else {
            ReportErrorToUser("You specfied too many characters ");
        }
    }
    else {
        ReportErrorToUser("Your starting index is too large");
    }

Writing this code is similar to writing the preconditions of a function. The important difference here is that the person writing the code has to immediately consider the repercussions of the failure. No precondition failures can occur in the call to Substring and therefore there can be no spurious runtime failures.

Again, going back to my roots in embedded systems, I prefer error paths in the code to be explicit and in your face. That way, we always can see what the software is going to do and do not have to look around at all call sites to figure out whether errors are being properly handled. This is the paranoia of systems programmers—we need to know everything.

If you are concerned about performance, consider this. If the entire program was written out using explicit and exact types, then the compiler can determine if the types of the values being provided in a function call are subtypes of the parameters of the function, then that function does not need to perform the parameter validation.

In reality, the implementation of this might be best if functions do not validate their parameters. Instead, the calling code must ensure that the values passed to the function are valid. In that way only one (fast) form of functions need exist and the validation code can be customized one invocation site at a time.

Calculating the set of assertions that match the declarative types (as given in the hypothetical language) is not a particularly easy thing to calculate. A future article will attempt to figure out a method to extract those assertions.

Integers for numeric computations

Languages like C do all integer math without a care in the world as to the range of integers it is actually able to represent. Cl version 14 (the Microsoft C/C++ Compiler) is more than happy to compile this program:

#include <iostream>
int main() {
    std::cout << 2000000000 * 2000000000 << std::endl;
    return 0;
}

that lazily outputs this silly answer:

-1651507200

Languages that take mathematics a little more seriously, such as Scheme, let us know what that value really is:

>(* 2000000000 2000000000)
4000000000000000000

The reason Scheme is able to compute that large number and C cannot (without implementing a library) is because Scheme allows integers to be of any magnitude so long as it is able to dynamically allocate enough memory to hold that value. C, sticking close to its down-to-the-hardware mantra, only performs arithmetic on integers whose values can be represented in the machine’s own word size and refuses to perform dynamic allocation for integers.

Because of this, C and C++ programmers have found the need to use libraries such as SafeInt by David LeBlanc or Michael Howard’s IntSafe.

(But we shouldn’t bash C. It wasn’t designed to be used like this. It’s only an odd reality that we as programmers have asked C to do so much more than what it was designed to do. Instead of pestering C any further we should take the logical step and use more powerful and applicable languages.)

Other languages know that they should take math more seriously, but simply refuse to even try. When attempting to compile the static expression 2000000000 * 2000000000, csc version 8 complains:

error CS0220: The operation overflows at compile time in checked mode

Checked code in C# will tell you it can’t do the math but will wait until runtime to complain. The following program:

class B {
    public static int Main(string[] args) {
        int v = int.Parse(args[0]);
        System.Console.WriteLine(checked (v * v));
        return 0;
    }
}

throws “System.OverflowException: Arithmetic operation resulted in an overflow” when executed with a parameter of 2000000000. However, if one forgets to use the checked syntax, then the compiler is just as happy as C++ to give -1651507200 as the answer. Needless to say, if you are writing a C# application, you should turn on default arithmetic checks! (Don’t worry, you can just as easily disable them in areas that you prove are safe.)

So why do old languages such as Lisp and Scheme support large integers, but modern languages like C# and Java do not? Well, I can guess at two reasons the designers would give. First, dynamically allocating integers and storing their values on the heap is certainly less efficient than using integers that fit nicely into the machine’s registers. Second, they would probably argue that a programmer should simply use a custom (dynamic) integer class in a library.

In fact, .NET “ships” with a BigInteger class tucked away in vjslib. The reason “ships” is here in quotes is because vjslib isn’t a part of the default .NET 2.0 redistributable, it is a part of the Visual J# redistributable (a separate download). Furthermore, vjslib is incompatible with 64-bit (or non-32-bit) assemblies. Bad news for all the high-end computers out there. Also, you will have to abandon infix notation and stick with prefix calls:

class C {
    public static int Main(string[] args) {
        java.math.BigInteger value = new java.math.BigInteger("2000000000");
        System.Console.WriteLine(value.multiply(value));
        return 0;
    }

}

If you can handle those restrictions though, BigInteger does the job.

There are of course other libraries. For example, F#’s library comes with a dynamic integer classes. And let’s not forget nice languages like Common Lisp, Scheme, and Erlang where all integers, by default, can have as large a magnitude as the computer’s memory can provide.

Integer as bitfields and other containers

We sometimes use integers in the most obscene ways because of limitations in the C programming language have persisted through time. Some of the most popular abuses include: integers as bitfields (sets of flags), integers as ports (in embedded hardware), and integers as pointers to objects and functions (see the Win32 API for numerous examples).

In fact, it is this use of integers that makes porting of programs from one system to another (32-bit to 64-bit, Intel to Motorola, etc.) so difficult. If the limitations of the C language had not forced us to write such unseemly code, then porting efforts wouldn’t be such, well, efforts.

So what are the alternatives to C? Well C# got flags (sets of Boolean values) partially right by providing the Flags attribute that can be applied to enumerations. I say partially because the enumeration type system is still weak (to allow compatibility with legacy code written in C) and can be overcome. A better solution is presented by the languages Modula-2 and Oberon. They implement sets as first-class types.

What about integers as pointers to objects and functions? Well this is typically a result of not having strong support for discriminating unions or polymorphism.

And what about as general-purpose binary data? Most language designers are content with forcing the user to regard an array of bytes as a general stream of binary data. This seems fin from the start except when you start doing a lot of communications code. In this code, we constantly need to convert types from their in-memory representation to some streaming representation. .NET has a library to assist this, but it does not operate at the language level. Erlang is the only language that I know of that decided to separate byte[] from the rest of the arrays and lists and that provides conversion routines with their own syntax.

I hope that you can see that this use of integers has largely been superseded with more powerful and safe constructs. So use the constructs! Don’t go packing your bits into an integer because everyone else is or was doing the same!

Thoughts on higher-level looping constructs

As we use more and more higher-level constructs, such as recursion, iterators, and enumerators for loops, in our day to day programming, our dependence on array indexing decreases and a whole class of bugs gets eliminated in our software. Eliminating a whole class of bugs is always a good thing.

However, in imperative languages where we sometimes modify the size of an array as we are iterating over it, using integer indexing is still necessary. In those cases it is still important to consider the ideas raised in this article.

If we can use higher-level constructs to eliminate 90% of our bugs, then let’s use other constructs to eliminate the remaining 10%.

Conclusion

As programmers it is our job to always think through how we are using the type systems of our languages and whether we are using it to assist us to the fullest degree. Even if we are using weakly typed languages such as C, we can still avoid whole classes of bugs simply by keeping in mind patterns of usage and how stronger languages deal with those patterns.

Knuth’s Solution to the Permutation Problem in C#

2006-04-14T07:00:00.000-07:00

Last week we considered the problem of permutation by developing code to generate all permutations of an n-tuple whose integral elements were less than some number m. Well, we’re in very good company. Dr. Donald Knuth also considered this problem in Section 7.2.1.1 of The Art of Computer Programming. His solution is a streamlined version of our same solution. This week, let’s look at his Algorithm M and consider how it can be used to solve permutation problems. To demonstrate the power of the solution, we’ll switch languages to C# and investigate the most idiomatic solution in that language.

Generate all n-tuples (a₁,…,a_n) where 0≤a_j<2 and 1≤j≤n

In this article we are going to switch our notation to that of Knuth’s. In this notation the elements are subscripted versions of a instead of n with subscripts that begin at 1 (purely to simplify the algorithm). Also, the number of elements in the tuple is now n instead of k.

Knuth’s algorithm is the natural extension of a powerful change in view: consider the case where each element of the tuple can be either 0 or 1. In this case, we can consider the tuple to be a binary string. Programming languages give us a lot of tools for manipulating binary strings. One of these tools, the use of binary strings to represent unsigned integers, enables us to write a very streamlined permutation solution.

Thanks to C#’s funny type system, we know that binary strings are easily represented as unsigned integers. We can therefore regard an 8-tuple as a byte, a 16-tuple as a ushort, a 32-tuple as a uint, and a 64-tuple as a ulong. Why should we do this? Well, to generate all permutations of a binary string represented as an integer, we merely have to initialize the integer to 0 and keep adding 1. At each step, we have a new permutation of the bit string!

In code, it would look something like:

class BinaryString8Permuter
{
    protected virtual void Visit(byte a)
    {
        for (int i = 7; i >= 0; i--) {
            System.Console.Write((a >> i) & 1);
        }
        System.Console.WriteLine();
    }

    public void VisitAll()
    {
        byte a = 0;
        do {
            Visit(a);
        } while ((++a) != 0);
    }
}

In this class, the public VisitAll function generates all the permutations. The virtual Visit function receives one of those permutations and does something with it. In the default case, I have written it to simply display the tuple’s value on the console.

In order to generate the permutations, VisitAll simply has to initialize the integer to 0, continuously increment it by 1 to generate the permutations, and detect when all the permutations have been generated. As C# does not provide the overflow result of arithmetic operations, we have to rely on the integer overflowing to 0 in order to detect that we have visited all permutations.

This code works well and displays the expected 256 permutations.

Generate all n-tuples (a₁,…,a_n) where 0≤a_j<m and 1≤j≤n

With the knowledge of that first example, let’s move on to the more interesting problem of generating tuples of any length (n) with any integer limit (m).

Knuth builds upon the last idea by recognizing that this problem can be solved by considering the tuple to be an m-ary number of n digits that is continuously incremented by unity (the number 1 represented as an m-ary number). In the last example, we considered a binary number of 8 digits that was incremented by the value 1. Now we will look at generalizing the algorithm.

Knuth’s Algorithm M actually allows for each element of the tuple to have a different termination value (called m_j). To keep things in line with last week’s work, let us focus only on the single terminator m. With this change, the modified form of his algorithm is:

M1. [Initialize.] Set a_j←0 for 0≤j≤n.

M2. [Visit.] Visit the n-tuple (a₁,…,a_n). (The program that wants to examine all n-tuples now does its thing.

M3. [Prepare to add one.] Set j←n.

M4. [Carry if necessary.] If a_j=m-1, set a_j←0, j←j-1, and repeat this step.

M5. [Increase, unless done.] If j=0, terminate the algorithm. Otherwise set a_j←a_j+1 and go back to step M2.

What does this look like in code? Well here’s my version of it in C#:

class IntNTuplePermuter
{
    protected virtual void Visit(int[] a)
    {
        string head = "";
        for (int j = 1; j < a.Length; j++) {
            System.Console.Write("{0}{1}", head, a[j]);
            head = ", ";
        }
        System.Console.WriteLine();
    }

    public void VisitAll(int m, int n)
    {
        // Initialize. Because C# automatically initializes
        // integers to 0, we need not explictely do so.
        // We allocate n + 1 integers to make room for a0.
        int   j;
        int[] a = new int[n + 1];

        for (;;) {
            Visit(a);

            // Prepare to add one.
            j = n;

            // Carry if necessary.
            while (a[j] == (m - 1)) {
                a[j] = 0;
                j -= 1;
            }

            // Increase unless done.
            if (j == 0) {
                break; // Terminate the algorithm
            }
            else {
                a[j] = a[j] + 1;
            }
        }
    }
}

The code after the call to Visit is very reminiscent of last week’s solution. All you have to do is realize that “fastest” in incr and “j” in Algorithm M play the same role. So there we are, instead of devising a solution ourselves, we could have just opened Knuth’s tome and received revelation.

Digressing with IEnumerable

Last week’s permutation article ended with a generic implementation of the incr function. That was nice, but in C# we can do much better! Using the clarity of Knuth’s solution and the venerable IEnumerable interface, we can create a permuter that is able to visit tuples whose elements are of any type that implements the IEnumerable interface. Let’s see how.

IEnumerable provides the GetEnumerator function that gives an object that implements the IEnumerator interface. This interface provides two methods and one property: Reset and MoveNext, and Current. Current simply returns the current value of the object pointed to by the enumerator. Reset sets the enumerator to point to the first element in the IEnumerable collection, and MoveNext advances the enumerator to the next element in the collection.

With these interfaces we can write a new permuter that loosely follows Knuth’s algorithm. The most important revelation is the use of two collections: a which holds the enumerators (and subsequently the values), and m which holds the IEnumerables. When we need to increment a value, we simply call MoveNext. When we need to reset a value, we simply call Reset followed by MoveNext. The call to MoveNext after Reset (and GetEnumerator) is required because reset enumerators actually point to the element before the first element in the collection.

With all that said, here is our best permuter to date:

class EnumerablePermuter
{
    protected virtual void Visit(System.Collections.IEnumerator[] a)
    {
        string head = "";
        for (int j = 1; j < a.Length; j++) {
            System.Console.Write("{0}{1}", head, a[j].Current);
            head = " ";
        }
        System.Console.WriteLine();
    }

    public void VisitAll(params System.Collections.IEnumerable[] m)
    {
        // Initialize.
        int n = m.Length;
        int j;
        System.Collections.IEnumerator[] a =
            new System.Collections.IEnumerator[n + 1];

        for (j = 1; j <= n; j++) {
            a[j] = m[j - 1].GetEnumerator();
            a[j].MoveNext();
        }
        a[0] = m[0].GetEnumerator();
        a[0].MoveNext();

        for (; ; ) {
            Visit(a);

            // Prepare to add one.
            j = n;

            // Carry if necessary.
            while (!a[j].MoveNext()) {
                a[j].Reset();
                a[j].MoveNext();
                j -= 1;
            }

            // Increase unless done.
            if (j == 0) {
                break; // Terminate the algorithm
            }
        }
    }
}

You can see that the most work is done in the initialization section when we have to create the enumerators (and the one dummy enumerator). The rest is just Knuth’s algorithm.

I find it very pleasing that we were able to move from using integers to permute binary strings to an algorithm for permuting tuples of any length comprised of any type of object in just a few steps.

Examples of the IEnumerable Permuter in Action

Let’s look at the above EnumerablePermuter in action by constructing a few simple tests. First, let’s generate some simple sentences:

string[] nouns = new string[] { "cat", "dog" };
string[] verbs = new string[] { "sniffs", "eats" };
(new EnumerablePermuter()).VisitAll(nouns, verbs, nouns);

This code generates the silly output:

cat sniffs cat
cat sniffs dog
cat eats cat
cat eats dog
dog sniffs cat
dog sniffs dog
dog eats cat
dog eats dog

The code works! We now know that some cat sniffed a dog, and that some other dog ate a dog!

What else can we permute? How about the cards in a deck?

object[] values = new object[] {
    "Ace", 2, 3, 4, 5, 6, 7, 8, 9, "Jack", "Queen", "King" };
string[] suits = new string[] {
    "Spades", "Hearts", "Clubs", "Diamonds" };
string[] of = new string[] { "of" };
(new EnumerablePermuter()).VisitAll(values, of, suits);

This code generates the predictable output:

Ace of Spades
Ace of Hearts
Ace of Clubs
Ace of Diamonds
…
King of Diamonds

Note that I used a dirty trick in order to inject the word “of” into the output. In a real application, I would override the Visit function of EnumerablePermuter. But this isn’t a real application, so we’re allowed to play dirty tricks!

Conclusion

I know Knuth’s The Art of Computer Programming is quite large and is difficult to understand at times, but there are a lot (what an understatement!) of gems to be found in it. Give it a try. Read it in small doses. Whenever he presents an algorithm, try coding it in your favorite language. I think you will find that there is a lot to be gained from this exercise; I certainly did.

Simplifying the Interview: Solving Permutation Problems

2006-04-04T07:00:00.000-07:00

I’m so tired of first-round interview questions. They always seem to boil down to “play with pointers” (linked lists, strings, trees, etc.) or “play with permutations or combinations”. The “play with permutations” questions are always the most annoying for me to answer, mostly because the solutions involve a bit of cookie cutter code that I know exists but have never taken the time to fully develop. Because of my laziness in defining a rigorous approach to solving these types of problems I am forced to invent a custom solution each time.

Well no more. Here is a cookie-cutter approach to solving permutation problems. Once you have read through this article, you will be able to tackle any of these problems with ease.

I will not just put the cookie-cutter code in front of you, but will instead build up to it through a series of examples. We’ll start with a very simple question and build up from it to harder and harder questions. The method developed in the earlier (easier) problems is shown to be of such value that the harder problems become trivial.

Once that is accomplished, I play around with C++ templates to create a function that directly implements the ideas of this article in such a manner that it can be plugged in to most situations.

With all that said, let’s move on to the first problem.

Generate all values for the integer n where 0 <= n < m

We can solve this problem most simply with a for loop:

void func1(int m)
{
    for (int n = 0; n < m; n++) {
        cout << n << endl;
    }
}

That solution is obviously correct but does not serve well as cookie cutter code when we move on to more complex problems. Let’s think about that for loop for a second; it contains three sections: initialization, a check (predicate) for continuation, and some mutation (change) of the value n to progress on to new values. We could in fact rewrite the function in parts (factored):

int init()
{
    return 0;
}

bool cont(int n, int m)
{
    return n < m;
}

void next(int &n)
{
    n++;
}

void func1a(int m)
{
    int n = init();

    while (cont(n, m)) {
        cout << n << endl;

        //
        // Increment
        //
        next(n);
    }
}

That sure is a lot more code, but it works identically to the first function.

First you’ll notice that I defined three functions: init(ialize), cont(inue), and next. We use these functions instead of their inline forms (= 0, <= m, n++) in order to force ourselves to recognize their roles. Because of their important role in these permutation problems, I call them the kernel functions. You may also recognize their similarity to the iterators of C++ and enumerators of .NET.

Notice also that we switched from a for loop to a while loop. That change wasn’t explicitly necessary for the refactoring, but made the structure of this solution match the structure of the solutions that will be presented later on.

Did we gain much over func1? No. However, we will soon see that the concept of the three functions init, cont, and next, and the layout of the code will make solving the harder problems much easier.

Generate all pairs n x n where n is an integer such that 0 <= n < m

Using the little kernel functions we developed in the previous section, we can easily solve this problem:

void func2(int m)
{
    int n0 = init();
    int n1 = init();
  
    while (cont(n1, m)) {
        cout << n0 << " x " << n1 << endl;

        //
        // Increment n0. If it reaches the end of its range,
        // reset it to 0 and increment n1.
        //
        next(n0);
        if (!cont(n0, m)) {
            n0 = init();
            next(n1);
        }
    }  
}

The trick to understanding this code is to recognize these three points:

When permuting more than one object, establish some order to things by declaring that one object will increment faster or slower than all the other objects. In this case, I decided to have n0 increment faster than n1.

The permutation is complete when you are no longer able to continue incrementing the slowest object.

When the fastest object can no longer increment (cont(obj) is false), then the object slower than that one must be incremented. If that one cannot be incremented, then the next slowest from that one must be incremented. And so on.

To see these rules in action, let’s move on to the next example:

Generate all triples n x n x n where n is an integer such that 0 <= n < m

Based upon our experience in the previous section, we might go about implementing this one as:

void func3(int m)
{
    int n0 = init();
    int n1 = init();
    int n2 = init();
  
    while (cont(n2, m)) {
        cout << n0 << " x " << n1 << " x " << n2 << endl;

        //
        // Increment
        //
        next(n0);
        if (!cont(n0, m)) {
            n0 = init();
            next(n1);
            if (!cont(n1, m)) {
                n1 = init();
                next(n2);
            }
        }
    }  
}

This code works (thanks to our rules) but the increment section of the code is already getting a bit unweidly. Just for a minute imagine what it would look like if we were dealing with four integers: we would keep nesting if statement after if statement. How redundant!

I hate redundancy in code, especially when it makes that code harder to understand. So let’s take a few minutes and think of a solution to simplify this whole mess.

What are we doing in that increment section? Well, we’re incrementing some value (the fastest object) and then checking whether that value has reached the end of its range. If it has not, then we do not need to do anything. If it has, then we need to reset it and increment the next fastest value. If that value has reached its end, then we need to reset it and increment the next fastest. And on and on.

I hope you made it through that last paragraph. If you didn’t have a cup of coffee and come back, because it’s important.

Good. Ok, so we have just described the generic algorithm that comprises all of the increment sections of all of the examples thus far. If we can code that algorithm, then our code should become simpler, less buggy (due to the code duplication removal), and hopefully easier to understand.

The algorithm states that we should increment the fastest object. That object will then either be able to continue or will have reached its end. If it is still able to continue, then we don’t need to do anything further. Instead, if it has reached the end, then we need to increment the next fastest object.

That sounds pretty easy to implement! For ease of implementation let’s assume that the current permutation values are stuck together in an array and are sorted from fastest moving to slowest moving. We then want to implement this mutating function:

bool incr(vector<int> &values, int m)
{
    size_t fastest = 0;

    while (fastest < values.size()) {
        next(values[fastest]);

        if (cont(values[fastest], m)) {
            return true;
        }
        else {
            //
            // Reinitialize this one, and move on to
            // increment the next fastest.
            //
            values[fastest] = init();
            fastest++;
        }
    }

    return false;
}

This function increases values just as we described in the algorithm. First the fastest value is incremented. If it is able to continue, then there is nothing more to do. If it has reached the end, then we need to reset it and increment the next value. We know that this algorithm will terminate because in each iteration it will either explicitly terminate (by using return) or it will increment the local variable called fastest. Because the loop is guarantees termination once the local variable has gotten to a certain size, the entire loop is guaranteed to terminate.

You should note that whatever extra data that the cont function needs, the incr function will itself need (since it calls cont). In our case, this extra information is simply the integer m.

A very important aspect of this function is its return value. The function will return true if there are still more permutations of values remaining. It returns false if we have already witnessed all permutations.

With this very convenient return value, we can re-implement func3 in a much more straight-forward manner:

void func3a(int m)
{
    vector<int> n(3, init());
  
    do {
        cout << n[0] << " x " << n[1] << " x " << n[2] << endl;
    } while (incr(n, m));
}

Generate all 6-tuples n x n x n x n x n x n where n is an integer such that 0 <= n < m

Given all our hard work in the last section, this is actually quite a breeze!

void func6(int m)
{
    vector<int> n(6, init());
  
    do {
        cout << n[0] << " x " << n[1] << " x " << n[2] << " x " <<
                n[3] << " x " << n[4] << " x " << n[5] << endl;
    } while (incr(n, m));
}

Generate all k-tuples n x n x … x n where n is an integer such that 0 <= n < m

This is just as easy:

void funck(size_t k, int m)
{
    vector<int> n(k, init());
  
    do {
        const char *head = "";
        for (size_t i = 0; i < k; i++) {
            cout << head << n[i];
            head = " x ";
        }
        cout << endl;
    } while (incr(n, m));
}

Here, we had to spend more thought coming up with a way to print the tuples rather than figuring out how to form then. I would say that we have mastered permuting integers at this point!

Generate all permutations of five letter words

As a final example, let’s consider a non-integer example. If our solution (or cookie-cutter code) is truly versatile then we should be able to implement this problem with little thought.

Let’s start with our kernel functions:

char init_letter()
{
    return 'a';
}

bool cont_letter(char ch)
{
    return (ch <= 'z');
}

void next_letter(char &ch)
{
    ch++;
}

These functions are very simple and very reminiscent of their integer counterparts. Notice here however, that the cont functions requires no additional information (unlike its integer counterpart). This is because we were able to statically hard-code the terminating condition.

Lastly we need to implement the incr function:

bool incr_letter(vector<char> &values)
{
    size_t fastest = 0;

    while (fastest < values.size()) {
        next_letter(values[fastest]);

        if (cont_letter(values[fastest])) {
            return true;
        }
        else {
            //
            // Reinitialize this one, and move on to
            // increment the next fastest.
            //
            values[fastest] = init_letter();
            fastest++;
        }
    }

    return false;
}

We can see that this function is nearly identical to the incr for the integer examples. This should clue you in to a pending refactoring of the code (something that we will do in the next section).

With the incr function written, it is a trivial matter to write the solution:

void print_words()
{
    vector<char> letters(5, init_letter());
  
    do {
        for (size_t i = 0; i < letters.size(); i++) {
            cout << letters[i];
        }
        cout << endl;
    } while (incr_letters(letters));
}

(Be careful running that program, there are a lot of 5-letter words!)

A generic incr

WARNING! Everything up until this point in the article addressed solving permutation problems. This last section is just riffing on that solution. Understanding this next bit is not necessary for understanding the rest of this article.

We noticed that the two incr functions in this article are essentially identical; they only differ by what functions they called. It is therefore beneficial to write a generic form of this function to reduce code duplication. Utilizing templates, we can write:

template<typename T, typename FInit, typename FCont, typename FNext >
bool incr_generic(vector<T> &values, FInit init, FCont cont, FNext next)
{
    size_t fastest = 0;

    while (fastest < values.size()) {
        next(values[fastest]);

        if (cont(values[fastest])) {
            return true;
        }
        else {
            //
            // Reinitialize this one, and move on to
            // increment the next fastest.
            //
            values[fastest] = init();
            fastest++;
        }
    }

    return false;
}

This generic form can be used just as easily as the custom form thanks to our kernel functions:

void print_words_generic()
{
    vector<char> letters(2, init_letter());
  
    do {
        for (size_t i = 0; i < letters.size(); i++) {
            cout << letters[i];
        }
        cout << endl;
    } while (incr_generic(letters, init_letter, cont_letter, next_letter));
}

I have chosen to use templates for the function parameters such that we can use functors (objects that act like functions, closures) for any of the passed functions. This simplifies passing the extra data needed by the cont function.

To demonstrate this, let’s consider the k-tuple example once more. Using incr_generic, we would first attempt to write something like:

incr_generic(n, init, cont, next)

in the while clause (look back at the funck function from before). However, this will not compile. The error lies in the cont function. The generic version of incr insists that the cont function only take one argument: the value to be checked. However, the cont that we passed requires two arguments: the value and the terminating integer.

To correct this, we will utilize an object that acts like a function and that stores away the terminal integer. Such an object can be defined simply as:

class Cont {
    int m_;
public:
    Cont(int m) : m_(m) { }
    bool operator () (int n) { return n < m_; }
};

It is the operator member function that makes this object act like a function that takes just one value.

Now we can write the generic version of funck:

void funck_generic(size_t k, int m)
{
    Cont cont(m);
    vector<int> n(k, 0);
  
    do {
        const char *head = "";
        for (size_t i = 0; i < k; i++) {
            cout << head << n[i];
            head = " x ";
        }
        cout << endl;
    } while (incr_generic(n, init, cont, next));
}

That’s enough code for one day. Thanks for sticking in to the end!

Using SQLite as an On-disk File Format, Part 2

2006-03-31T07:00:00.000-08:00

Herein we lay the groundwork for our application by writing a typical serialization module. Written in C++ these 75 lines of code are able to serialize any graph objects (including graphs with loops).

In Part 1 of this series, I gave a very cursory explanation of why I want to utilize SQLite as an on-disk file format. In this part, I would like to take a brief look at how I have traditionally written serialization frameworks and to code a simplified one right here.

I am going to write it in ISO C++ in an object-oriented style in order to balance it with the karma of my Win32 article. Also, in truth this article is only going to give half of the serialization story—writing from our in-memory representation of objects to the store. The second half, reading that stored data to re-create our object graph will be tackled in the next article.

On Classes

Let’s begin by considering the metadata of an object. In languages like C# and Lisp, we are given a very rich view of the type of an object. In C# we have the reflection library to query an objects type and to examine that type (we can also create types on the fly but will reserve doing that for the time being).

C++ offers very little in this realm. We are given access to little poorly defined things called type_infos via the special operator typeid. These objects give only a small (undefined) glimpse of the object’s type and its relationship to other types, and nothing else.

We can easily build a serialization system in C# because it has a rooted object hierarchy and a rich reflection system. We can build a serialization system in C++ only by enhancing it slightly to include the barest of metadata that we need.

Our metadata will contain a class name and a version number for every class that can be serialized.

class ClassInfo
{
public:
    ClassInfo(const wchar_t *name, int version)
        : version_(version), name_(name) { }
    int Version() const { return version_; }
    const wchar_t *Name() const { return name_; }
private:
    int version_;
    const wchar_t *name_;
};

We will enforce this by declaring an ISerializable interface and dictating that any class that wants to be serialized must fully implement the ISerializable interface.

class ISerializable
{
public:
    virtual ~ISerializable() { }
    virtual ClassInfo GetClassInfo() const = 0;
    …
};

We will add to this interface as we require more of the classes to be serialized, but this is sufficient for the time being.

We have added a version field to the class information so that in the future we can change our class definitions but still have the potential to load them stores that contain classes of earlier versions. This will be discussed further when it comes time to deserialize these objects.

The Serialization Scheme

We wish to be able to serialize whole graphs of objects—even graphs in which the same object appears multiple times.

The simplest way to represent such a graph is to output all the data and metadata of a class whenever it is encountered. In the case of a graph where an object is repeated, two entire copies of that object will be written to the store. That’s one problem. An even bigger problem with this scheme occurs when we have graphs that contain loops. Consider for instance a linked list where the tail points back to the head of the list. If we attempted to serialize objects as we encounter them, then we would end up serializing for an eternity (or at least until the hard disk filled up).

In order to avoid this, we need to differentiate between objects and references to objects. In the linked list example, all we really want to output are references to objects. That way, when we get to the tail of the list that needs to point back to the beginning, we need only output a reference to the head, not the head itself.

We will adopt the following policy during serialization in order to make this work: when we are asked to serialize an object, we will first check to see if we have already serialized it. If we have not, then we will write out the object (its data and metadata). If we already have serialized it, then we will write only a reference to the object (its metadata).

Ignore for a minute the difficulties that this will have in a multithreaded environment and just consider the simplicity of this solution. We can now represent arbitrary graphs of objects—even those that contain loops.

A Matter of Style

We of course still need to select an output medium for our objects. Of course the whole point of this article series is to explore the use of SQLite as this medium but we currently only want to consider the simple case of serialization.

For that reason, we will write our data to a simple XML file. Every object that we write will consist of an <Object> tag whose children are the various fields of the object being serialized. References to objects will likewise be specified with <Reference> tags.

The fields of objects (which can themselves be objects) are written in enclosing tags named after the field itself.

As an example, consider a Point object that contains two fields: X and Y. The XML for this object will look something like:

<Object class="Point" version="1" id="1"><X>0</X><Y>0</Y></Object>

Yes it’s verbose but its format is very simple. Now, if we wanted to reference this same object, then we would simply write:

<Reference class="Point" version="1" id="1">

On to the Code!

Now that we have specified how our serializer will work, it is a very simple matter to implement it. We shall create a class called Serializer that will orchestrate this whole thing.

That class is responsible for writing all data in the XML format and for maintaining the list of serialized objects so that loops can be avoided.

Currently, we will only support writing integers and conglomerate objects (those derived from ISerializable). When you are implementing a richer system, you will need to provide more fundamental object support (floating point numbers, strings, arrays, etc.).

class Serializer
{
public:
    Serializer();

    void Serialize(const wchar_t *name, const ISerializable &obj);
    void Serialize(const wchar_t *name, int n);

private:
    typedef map<const ISerializable*, int> ObjectIds;
    
    int depth_;
    ObjectIds objIds_;
    int objCount_;
};

The three fields, depth_, objIds_, and objCount_ are all used for managing objects and their references. Whenever an object is serialized, the Serializer assigns a unique identifier (an int) to that object and records its address. If that object is ever attempted to be serialized again, the Serializer will know to simply output a reference to it.

This scheme works just fine in single threaded environments, but becomes much more difficult to implement if the object graph is concurrently changing along with being serialized. This is one scenario that we must think hard about whether supporting. In this implementation we restrict ourselves to requiring the object graph be frozen while serialized. This is another area that we will have to revisit when considering the implementation of this serialization with SQLite.

Serializing an integer is the easiest operation that the Serializer performs since we will not differentiate between objects and references with integers. Instead, we will simply output their value wherever needed:

void Serializer::Serialize(const wchar_t *name, int n)
{
    //
    // If the depth is > 0, then we are serializing some fields of a parent
    // object. We must therefore label the field.
    //
    if (depth_ > 0) {
        wcout << L"<" << name << L">" << n << L"</" << name << L">";
    }
    else {
        wcout << n;
    }    
}

We see that every object being serialized is given a name. This name is used only when an object is the field of another object. That condition is monitored using the depth_ variable of the Serializer class. If the depth is greater than 0, then the object being serialized is a field of a larger conglomerate object. Given our schema defined earlier, we tag these fields with their names. If the object is not a field, then we simply output its value.

Also, for the sake of simplicity, all data is being dumped to the console. In reality we would have to pass around some “SerializationContext” that dictated which IO stream should be used for output.

Serializing objects is necessarily more difficult as we have to manage references. However, you will find that even with this complexity, the function is still easy to understand:

void Serializer::Serialize(const wchar_t *name, const ISerializable &obj)
{
    ClassInfo info = obj.GetClassInfo();

    //
    // If the depth is > 0, then we are serializing some fields of a parent
    // object. We must therefore label the field.
    //
    if (depth_ > 0) {
        wcout << L"<" << name << L">";
    }

    //
    // Have we already serialized this object?
    //
    ObjectIds::iterator iObj = objIds_.find(&obj);

    if (iObj != objIds_.end()) {
        //
        // Serialize just a reference.
        //
        wcout << L"<Reference class=\"" << info.Name() <<
                 L"\" version=\"" << info.Version() <<
                 L"\" id=\"" << (*iObj).second << "\" />";
    }
    else {
        //
        // Serialize the object itself and add it to the serialized table.
        //
        int id = objCount_++;
        objIds_[&obj] = id;

        wcout << L"<Object class=\"" << info.Name() <<
                 L"\" version=\"" << info.Version() <<
                 L"\" id=\"" << id << "\">";

        depth_++;
        obj.Serialize(*this);
        depth_--;

        wcout << L"</Object>";
    }

    //
    // End the labeled object.
    //
    if (depth_ > 0) {
        wcout << L"</" << name << L">";
    }
}

Once again we have the simple field tagging based upon the depth of this object. After that we follow one of two paths: the first if the object has already been serialized and the second if the object has not yet been serialized.

When it comes time for an object to output its data, we call the Serialize member function of that object. In the implementation of that function, the object must call back to the serializer with any data it needs serialized. For example, the Point class from above has this Serialize function:

void Point::Serialize(Serializer &s) const
{
    s.Serialize(L"X", X);
    s.Serialize(L"Y", Y);
}

In their Serialize functions, objects must simply enumerate through their fields and output whatever is needed to reconstruct the object at a later time.

As a word of warning, the Serialize method of the Serializer is not yet at production quality. In particular, we do no error checking and haven’t thoroughly examined the ramifications of exceptions being thrown in the object Serialize functions (it would be nice to give it a no throw specification). However, it is sufficient to be a starting place for our serialization system.

An Example

Let us consider a linked list of nodes that each contains an integer. The class declaration for the node is:

class Node : public ISerializable
{
public:
    Node(int value) : pNext_(0), value_(value) { }
    virtual ~Node() { }

    void SetNext(Node *pNext) { pNext_ = pNext; }

    virtual ClassInfo GetClassInfo() const;
    virtual void Serialize(Serializer &s) const;

private:
    Node *pNext_;
    int value_;
};

And the implementation of the ISerializable interface is:

ClassInfo Node::GetClassInfo() const
{
    return ClassInfo(L"Node", 1);
}

void Node::Serialize(Serializer &s) const
{
    s.Serialize(L"Value", value_);
    s.Serialize(L"Next", *pNext_);
}

Now, let’s consider what happens when we try to serialize a loop of four of these nodes. When we serialize the “first” in this loop, its metadata will be output by Serializer::Serialize and its data will be output by Node::Serialize because it has not been serialized before. This will continue for the second and third nodes: each one driving the next node to be serialized. When it comes time for the fourth node to serialize its next pointer, Serializer::Serialize will realize that the first node has already been serialized and will therefore output a mere reference to that node.

That’s what should happen, now let’s see what does happen by constructing a simple test:

int main()
{
    Node n3(300);
    Node n2(200);
    Node n1(100);
    Node n0(0);
    
    n0.SetNext(&n1);
    n1.SetNext(&n2);
    n2.SetNext(&n3);
    n3.SetNext(&n0);

    Serializer s;
    s.Serialize(L"n0", n0);
}

Here, we setup our graph and let the Serializer do its work. The output of this program is the following XML:

<Object class="Node" version="1" id="0">
  <Value>0</Value>
  <Next>
    <Object class="Node" version="1" id="1">
      <Value>100</Value>
      <Next>
        <Object class="Node" version="1" id="2">
          <Value>200</Value>
          <Next>
            <Object class="Node" version="1" id="3">
              <Value>300</Value>
              <Next>
                <Reference class="Node" version="1" id="0" />
              </Next>
            </Object>
          </Next>
        </Object>
      </Next>
    </Object>
  </Next>
</Object>

We see that indeed the Serializer operated as expected and fully recreated our loop.

On to Deserialization

Well I think that is enough for all of us to swallow today, so let’s take a break and move on to deserialization of this XML file next week. I’ll see you all then!

Using SQLite as an On-disk File Format, Part 1

2006-03-28T07:00:00.000-08:00

SQLite is a small but powerful cross-platform database engine that can easily be compiled and linked to native executables. This article introduces a series of articles that will explore the use of SQLite in the role of an on-disk file format.

I was browsing the SQLite website after finding a small reference to it in a Firefox 2.0 story. SQLite is a full database engine that implements most of SQL92. For the small price of 200 kb, a native application is given access to a very powerful data source. IBM has a really nice overview of the software in its Introduction to SQLite.

In the land of Windows client application development, when you need a database you usually think of Jet, MSSQL, or Borland’s DB engines. You can communicate with these engines using ODBC and they all work just fine so long as you have the appropriate DB engine installed (or, in the case of Jet, you install the redistributable package along with your app).

But that’s the clincher: sometimes you don’t want to install DB engines. This may be because you are worried about conflicts (the last two Microsoft products I installed each tried to install SQLExpress), you don’t want your application to modify the system at all, or you are happiest with a single-EXE solution for deployment. Or perhaps you aren’t developing for Windows at all and are required to implement your own solution regardless.

Well, I really like SQLite. It has a rich, but very easy to use API that manages SQL and the loading and unloading of DB files. I find it to be a fantastic alternative to ODBC in terms of simplicity.

In the online documentation for SQLite I noticed an enticing entry, “Appropriate Uses For SQLite”. In that article is this section that I wish to quote verbatim for it really got me excited:

“SQLite has been used with great success as the on-disk file format for desktop applications such as financial analysis tools, CAD packages, record keeping programs, and so forth. The traditional File/Open operation does an sqlite3_open() and executes a BEGIN TRANSACTION to get exclusive access to the content. File/Save does a COMMIT followed by another BEGIN TRANSACTION. The use of transactions guarantees that updates to the application file are atomic, durable, isolated, and consistent.

Temporary triggers can be added to the database to record all changes into a (temporary) undo/redo log table. These changes can then be played back when the user presses the Undo and Redo buttons. Using this technique, a unlimited depth undo/redo implementation can be written in surprising little code.”

A nice example of an application using a database engine as its file format is CityDesk by Fog Creek Software. That software uses the Jet DB engine and does so in a very polished and unobtrusive manner (strange message boxes with SQL arcana have yet to be experienced by this reporter!).

The benefits of using a database as an on-disk format largely come from the transaction model that is used. We can insure that large amounts of data are consistently written to the database by using explicit transactions. This helps alleviate the problems of power loss, program failure, bad writes to disk, etc.

As I have never tried working with a DB as an application file, I decided to write my own application to test the waters. I wanted to know if writing a DB-based system was any more difficult or any better than writing a custom serialization format. Does it offer simplifications or some added amount of robustness? Is setting undo/redo functionality really as simple as coding some triggers? I want to know.

To that end, I would like to introduce you to this article series. I don’t know exactly how many parts there will be (as I have yet to finish the demo app) but I am guessing that there will be somewhere around 5 at this moment.

Please stay tuned, the next article which will lay the groundwork for our application will be posted in just a couple days.

Travel Guide to India

2006-03-10T07:00:00.000-08:00

During my second trip to India in 2005, I decided to put together a 24 item guide to survival in the city of Hyderabad. Here is that guide.

I have the pleasure of living in a hotel that caters to international visitors. This affords me the opportunity to observe cultural differences every night as I enjoy my Tandoori Roti over the Vegetarian Masala. Not all of my observations are based over dinner, but a lot of them are. Here is my list of knowledge a traveler should have before coming to India:

When ordering a Roti, always ask for Tandoori Roti. All others come smothered in butter.

When walking down the street, try very hard to walk opposing traffic. This way, motorized vehicles will see you just before they hit you. HOWEVER, this means that the cars driving on the wrong side of the road will be closer to you (they always get close to the curb).

Always watch for buses while walking down the street. Forget about the danger of them hitting you, what you really have to avoid is their fracking horns. These guys have the most powerful horns – if caught unprepared the poor traveler may be driven into cardiac arrest.

While the curb seems to be a promising refuge from motored vehicles, its best to avoid it to limit your exposure to urine.

If a taxi asks for Rs. 50, give them 20. If they ask for 20, give them 40. This way, everyone's Karma is balanced.

Don't lose the decimal place! Rs. 295 is WAY too much to pay for shampoo (even if it does have conditioner integrated).

There are these little dudes at the gas station who will break your Rs. 100 bills into smaller change. You can find them by standing in the middle of the station, turning circles repeatedly, whilst waving the money in the air. While this is not the advertised method, it is the most efficient.

NEVER wear your nice shoes when going for a walk.

Wear goggles when taking a taxi and hold your breath. This way, your driver will fear you and give you a better rate (and it helps to survive the busier parts of the road).

Leave your room at least once every 5 hours. This is to remind you that it’s not really 62° F. “in the real world”.

Indian JELL-O does not have the same consistency as US JELL-O. Bear this in mind so as not to look like a fool in the dessert line.

Drink your tea quickly. The trick is to never let anyone see you do it. You should go from a full cup of tea to pacing the room with an empty cup without missing a step. The last guy to have tea in his cup is (a) a loser and (b) stuck as the dude trying to clean up after you stare him down.

Don't enjoy the tea too much. If you do so, more will come. Then more, then more. Pretty soon you won’t feel right unless there is some tea around. This is a problem.

Method of brushing your teeth while not drinking the tap water: (a) get a glass; (b) fill it with bottled water; (c) take a sip and rinse your mouth (adjust to the temperature); (d) swish the brush in the cup and apply toothpaste; (e) brush as normal; (f) sip some water and rinse your mouth; (g) swish brush in cup until clean; (h) drain out the remaining water and leave for the housekeeper to replace; (i) wipe mouth with towel.

When implementing (14), be sure to only use non-refrigerated water. This prevents the disastrous pain inherent to step (f).

If having trouble crossing the street, find a cab and offer him Rs. 10 to take you across. Safety is worth $0.25.

Channel 61 is the fashion channel. Endless parade of beautiful women in beautiful clothes. This is the best background TV in the world.

When the power goes off, pretend that it is still on. DO press the elevator button and look impatient. DO NOT skip a beat in your conversation. First person to pause loses. Only dorks get worried that the power won't come back on.

Even if the waiter offers to make you specialized food (hamburgers, ramen, etc.) politely decline. If you can’t handle the masala, try some briyani. If you can't handle that, try the rice with some fruit. Just don’t give in to their wonderful offers. STAY STRONG!

Make friends with your house keeper. This way, you can score more of those salted dry lentil snacks or aloo bhujia instead of the Lay’s Chips. This is essential. If you’re lucky, she will even leave you two pops (sodas) instead of one.

Just because a factory’s walls are falling down does not mean it’s out of business – it just means that the walls are falling down. Nothing more to see here, move along.

Foster’s Beer costs 2x as much as King Fisher. When eating the tomato chutney, it really doesn’t matter which you get. Go for the cheap.

Always order a dosa in the morning -- either masala or onion. This scores you points with the waiters because it makes you look like you know what you are doing. For bonus points, complain if the onions are not integrated with the dosa mixture before being put in the pan.

60% off sales are worthless if you can't figureout how to get in to the store in the first place. Watch for hidden cameras.

I wrote this travel guide in the summer of 2005 during my second trip to India. Since it was written during the first few weeks of the trip, I meant to write another guide that would reflect my experiences during the last few weeks. Alas, such a guide was never written.

Time Delays in IO

2006-02-23T07:00:00.001-08:00

There are certain time delays inherent to all systems that must read and write to IO ports. This paper attempts to classify those delays and describe a method to compensate for them utilizing state and parameter estimators and optimal control designers.

A typical reactive control loop goes something like this:

for (;;) {
    Read_Inputs();
    Process_Inputs_To_Decide_Outputs();
    Write_Outputs();
}

There are intrinsic delays in each of these functions. In the function Read_Inputs, one must first request for the hardware to read the values. The delay between the request for the read operation and the hardware actually reading the values is called t_rr. Those values must then be transmitted back to the program, this time delay is called t_ra. The total time for the Read_Inputs function is then t_r=t_rr+t_ra.

The function Process_Inputs_To_Decide_Outputs has a constant delay of t_p.

Write_Outputs is similar to Read_Inputs. In that there is a transmission time to make the request to hardware, and there is the time required for hardware to acknowledge that it has acted. This total time is t_w=t_wr+t_wa.

How to Compensate

In our control architecture, there are two fundamental units responsible for calculating the reactive control signal: the state and parameter estimator (SPE), and the optimal control designer (OCD).

Given the outputs of the system, and a perfect discrete-time non-linear model of the system, the SPE is capable of calculating value of the states and parameters of the system based upon the previously estimated states and parameters (in addition to some statistics that it keeps on those states and parameters).

Because it relies on previous knowledge, the SPE is most easily formulated using a discrete-time model of the system being estimated. Continuous-time models, however, are much easier to formulate and verify. Because of this, a time integrator is used to convert from the continuous-time model to the discrete-time model. This integrator is able to perform this conversion for any time step; its accuracy, however, depends greatly on the magnitude of this time step (smaller time steps produce more accurate results).

This “laziness” of storing a continuous model and then converting it to a discrete model has some unforeseen advantages when faced with the problem of IO delay compensation.

In a typical real-time environment, the maximum IO delays are calculated and the system is driven at a fixed time step based upon those delays. In a system where no hard limit can be placed upon the IO delays, or when those delays have a large variance, a variable time step system is often employed.

Let us consider this variable time step system and its relationship to the SPE. We will attempt to define a means by which we can provide the SPE with enough information that it can create an accurate view of the world even in the face of read delays.

Compensations for the SPE

The SPE is able to take the current outputs of the system and determine the current states and parameters of that system based solely of the last estimated states and parameters and some statistics that is has accumulated over time. It can do this assuming that the time between these outputs being provided to it and the time when the last set of outputs were provided to it is equal to the time step of the discrete system. That is, assuming that the time step of the discrete system is Δt, and that outputs were provided at times t_k−1 and t_k (in that chronological order), then this relationship must hold for the SPE to operate correctly:

Δt=t_k−t_k−1

In the face of variable delay IO, the expression t_k−t_k−1 is variable. This means that a fixed time step discrete-time model of the system is inapplicable. Fortunately, we never had one to begin with!

Our goal, then, is to use the integrator to convert our continuous-time model to a discrete model using a time-step that reflects the actual timing of the output measurements. In this way, the SPE can be given a more accurate view of the world—one in which it can best predict the states of that world.

Figure 1 Control Sequence and associated timing.

Figure 1 depicts the control sequence and the associated timings. It is a bit misleading because, in reality, the read and write time delays are greater than the processing delay.

Actual sampling of the world occurs at time t₀+t_rr; however, the SPE is not executed until t₀+t_rr+t_ra+t_pe. Keeping in mind that we are continuously running this control loop, the last time that the SPE was run is equal to t₋₁+t_−1rr+t_−1ra+t_−1pe where t₋₁ is equal to the starting time of the last control loop.

If we care to keep the SPE in sync with reality, then we want to make sure that we use an integration step equal to (t₀+t_rr)−(t₋₁+t_−1rr), this is the time difference between measurements of the outputs of the system. In the case that the two read delays are equal, this difference in time simplifies to t₀−t₋₁. While we cannot say that the read delays are ever equal to each other, it is safe to say that in the aggregate, there will exist a mean read delay t_rr. The instantaneous values of t_rr will fall either above or below this mean read delay in a uniform manner. Therefore, in the aggregate, we can use the simplification for the difference in output measurement times of t₀−t₋₁. This is convenient since measuring the time t_rr is a very difficult task (as it requires clock synchronization between the sensors and the controller).

We have now solved one piece of the IO delay compensation puzzle: tracking the current world state. The next part of the puzzle is to compensate our control signal for the write delay.

Compensations for the OCD

The OCD is responsible for creating a control law in order to meet some performance criteria. Given a continuous non-linear mathematical model of the system presented in a state-dependent form, and given the current state of the system, the OCD is able to calculate the control signal that should be provided to the system in order to meet the performance criteria.

This works wonderfully if there is no delay between reading from sensors and controlling actuators. However, if there is a delay, then there could be problems.

Imagine an actuator that is attempting to seek to a certain position. Its goal is to reach 30°. It is currently located at 0° and moving at a rate of 10°/s. If the total control loop delay is 0.1 s, then we will have 30 samples in order to slow the actuator down. If we want to drive the actuator at full speed until we reach 25°, then we will have only 0.5 s (5 samples) to slow it down. This should be adequate (assuming that the actuator is capable of coming to a stop within 0.5 s).

Now consider the possibility that a write delay may take up to 0.3 s to be transmitted to the actuator. At 24°, the control system will attempt to keep the actuator going at full speed because, as far as it knows, it will be able to slow it down again (at 25°) when the control loop is run again. However, consider the possibility that the write delay now increases to 0.3 s. This means that the control loop will not be able to execute until the actuator is already at 27°. At this point, the actuator is moving at the full 10°/s while it is only 2° away from its target. This transient spike in delay time has put the actuator in danger of overshooting its goal.

Here, we have to decide how to control the actuator. There are essentially two choices that can be made:

We output the control value that is appropriate for 27° under the assumption that the write delay will settle back down to its nominal value of 0.1 s.

We can assume that this delay is not transient and compensate for it by calculating the appropriate control signal for events 0.3 s in the future.

Which of these is the correct choice? Unfortunately, either one is the correct choice—it is simply impossible to predict the future. Either the extended write delays will go back down or they will continue, we have no way of knowing.

Let us now consider what happens if we choose option 1 over option 2. The optimal controller will calculate an aggressive but valid output signal that keeps the actuator moving in the direction of the goal. If the extended write delay vanishes for the next few seconds, all is fine and the actuator meets its goal. However, if the extended delay continues, then the actuator could overshoot its goal (depending on how aggressive the controller is at 27°).

Consider what would happen if we chose option 2. At 27°, the controller would calculate a control signal for 30°. This control signal is of course going to be to stop the actuator. If the extended delay vanishes, then the system has undershot its goal (and the actuator’s inertia must be re-established). If the delay continues, then the actuator will come to a proper stop.

As we can see, depending on whether the delay is transient or not, either option 1 or option 2 is valid.

One unifying feature of both the options, however, is the fact that the two rely upon some estimate of how long it will take for a new control signal to reach the actuator. Their only difference lies in how often this estimate is updated. Is the estimate for this control cycle equal to the delay of the last control cycle (option 2) or is the estimate equal to the average of the last 10 cycles (option 1)? Obviously, the estimated delay is some low-pass filter applied to the past measured delays. The difference between option 1 and option 2 lies in the aggressiveness of that filter.

We know that we want the controller to predict the future—specifically, we want it to predict the state of affairs at the moment that the new control value will actually be applied to the system. Using our timing notation, the time at which the control is applied is:

t₀+t_rr+t_ra+t_pe+t_pd+t_pdf+t_wr

The last time in that expression, t_wr is important. We know the system state at the time t₀+t_rr. If we can calculate the value of t_ra+t_pe+t_pd+t_pdf+t_wr, then we can calculate the time difference between the known state of the system and the state of the system when the control signal will actually be applied. Calculating t_pe+t_pd+t_pdf is as simple as establishing a timer in the control code.

We have much more difficulty calculating t_ra and t_wr, again, because doing so would require synchronizing a clock between the controller and the sensors. Instead, we will simply estimate the values. If one assumes that transducers act with a time constant much less than t_r and t_w, then we can assume that these delays represent the transit time of data between the transducer and the controller. If we further assume that the network has the same condition during the times of t_rr to t_ra and t_wr to t_wa, then we can estimate

t_ra=t_r/2

t_wr=t_w/2

These assumptions are very convenient though probably a bit from the truth. They are, fortunately, a better alternative to assuming that there are no delays at all.

Once we know how much time will have passed betweenve passed since we observed the world anduming there are no delays at all.the transducer and the controller. If we furthe observing the world and controlling it, we can use an integrator to calculate (extrapolate) the future state, design a control law for this state, and enact that law.

Putting it All Together

Now that we have an understanding of how the control algorithm should act, let us attempt to solidify that knowledge into code. We will assume the existence of a few classes to assist our controller.

void Perform_Control(Model mdl)
{
    SPE spe(mdl);
    OCD ocd(mdl);
    Integrator intOCD(mdl);
    Discrete_Model dismdl(mdl);
    State sEstimate(mdl), sFuture(mdl), sOutput(mdl);
    Real rControl;
    Timer timer;
    Time tNow, tLast, dtRead, dtProcess, dtWrite, dtFuture;

    while (true) {
        tNow = timer.Begin();
        sOutput = Sensors.Read();
        dtRead = timer.End();

        timer.Begin();
        dismdl.FromContinuous(tNow – tLast, sEstimate, mdl);
        tLast = tNow;
        sEstimate = spe.Estimate(sOutput, dismdl);
        dtFuture = dtRead/2 + dtProcess + dtWrite/2;
        sFuture = intOCD.Step(dtFuture, sEstimate, mdl);
        rControl = ocd.Design(sFuture);
        dtProcess = timer.End();

        timer.Begin();
        Actuators.Write(rControl);
        dtWrite = timer.End();
    }
}

Conclusion

In this paper, a simple methodology has been developed to create a reliable control system that is able to operate reliably in the face of variable delays between transducers and the control algorithms. A key factor in this methodology has been the use of a continuous-time non-linear model of the system that can be manipulated to account for the variable delays.

praeclarum

Finally, a thumb drive that doesn't suck

Choosing C#/Java over C++ for a beginning programmer

Dear Windows Vista

Extension Methods Make Code... Different

Why Dictionary is Great - Dynamic List with Indices

My 1 Minute Trial of VB 2008 Beta 2

Eben Moglen

Feynman my Hero

Mr. Gore acting as Philosopher

Assimilated by Win32

Let’s Begin with WinMain.

Object-oriented Windows.

Assimilated Win32 Development.

Window State.

Commanding through Messages.

Putting it all Together.

Conclusion.

Times Reader makes reading on the web enjoyable again

A Naive Implementation of MapReduce in C#

Saturday

My 20 Minute Experience with WinFX

Patterns of Integer Usage

Integers are array indices

Integers for numeric computations

Integer as bitfields and other containers

Thoughts on higher-level looping constructs

Conclusion

Knuth’s Solution to the Permutation Problem in C#

Generate all n-tuples (a1,…,an) where 0≤aj<2 and 1≤j≤n

Generate all n-tuples (a1,…,an) where 0≤aj<m and 1≤j≤n

Digressing with IEnumerable

Examples of the IEnumerable Permuter in Action

Conclusion

Simplifying the Interview: Solving Permutation Problems

Generate all values for the integer n where 0 <= n < m

Generate all pairs n x n where n is an integer such that 0 <= n < m

Generate all triples n x n x n where n is an integer such that 0 <= n < m

Generate all 6-tuples n x n x n x n x n x n where n is an integer such that 0 <= n < m

Generate all k-tuples n x n x … x n where n is an integer such that 0 <= n < m

Generate all permutations of five letter words

A generic incr

Using SQLite as an On-disk File Format, Part 2

On Classes

The Serialization Scheme

A Matter of Style

On to the Code!

An Example

On to Deserialization

Using SQLite as an On-disk File Format, Part 1

Travel Guide to India

Time Delays in IO

How to Compensate

Compensations for the SPE

Compensations for the OCD

Putting it All Together

Conclusion

Generate all n-tuples (a₁,…,a_n) where 0≤a_j<2 and 1≤j≤n

Generate all n-tuples (a₁,…,a_n) where 0≤a_j<m and 1≤j≤n