Saturday, December 29, 2007

Dunce Cap Removal

OK, I have something to admit. I realized the other day that I totally misunderstood how variable bindings in Haskell do blocks propagated to later statements in the block. Once I realized this and saw how wrong I had been it was sort of like taking off a dunce cap that I didn't know I was wearing. I guess it was a good thing that I never went shooting my mouth off about this subject else my dunce cap would have become visible to everybody else as well.

To be a bit more explicit about what I was so wrong about consider this bit of Haskell code:

   do
    x <- someAction
    y <- someOtherAction
    putStrLn $ show $ x + y

How does the last line access the x binding? For some reason I had concocted this crazy complicated mechanism where the compiler was creating ever longer tuples containing all the variables bound in the do block and then automatically extracting the proper element from the tuple in each statement that a variable was used in. It was really hand-wavey and looking back on it I guess I was being a bit lazy. Had I really sat down and worked out how this ever-growing tuple thing worked I would have seen how clunky it was and probably noticed the dunce cap a lot sooner.

Then the other day I decided to manually de-sugar a do block in some code that I was working on. Doing the same to the above results in

 someAction >>= 
        (\x -> someOtherAction >>= 
        (\y -> putStrLn $ show $ x + y))

It was at this point I realized how big of an idiot I had been. The compiler doesn't need to start creating tuples of ever-growing length. In the putStrLn expression y is passed in so it is obviously available. But notice that the lambda expression containing putStrLn is defined within another lambda expression that x is passed into. x is part of the putStrLn lambda's environment and thus is accessible. So instead of building bigger and bigger tuples as we go further into the do block the compiler is instead nesting more and more lambda expressions. Since the previous lines in a do block become lambda expressions containing the current expression any parameters they take are available in the inner lambda expressions.

So now my dunce cap is off. Maybe if I had exposed it to someone earlier they would have disabused me of my misunderstanding earlier. Maybe they would have just pointed and laughed or let me go on thinking the way that I was, sort of an intellectual kick-me sign. At least getting rid of this dunce cap means that I am learning. Though now I'm left wondering how many more dunce caps I'm wearing that I don't know about.

Saturday, November 17, 2007

Poor-man's Closure

So C++ is lacking in some areas of modern programming language design, that's not a big secret. But given the flexibility of C++ the question becomes: how hard is it to add missing features? Here I'm going to take a look at closures and lambda expressions.

First off we can talk about closures. As far as I know there it isn't possible to add full closures to C++. But we can get a poor man's closure using the boost::bind library. If you don't know about this library yet you should run (not walk) over to boost.org and check it out. If you work at all with STL algorithms it will cut down on the amount of code you write immensely. So for a demonstration of the usefulness of boost::bind as a sort of closure mechanism lets say that you want to add two to all the elements in some std::vector<int>. You could do this using std::binder1st and std::mem_fun but that's kind of a pain in the ass. Instead you can do

std::transform(values.begin(), values.end(), 
               values.begin(),
               boost::bind(std::plus<int>(), _1, 2));

Things start getting interesting when you want to use bind to modify a value from outside of your STL algorithm. Take a look at this:

int lastVal = 0;
std::for_each(values.begin(), values.end(),
              boost::bind(sum, boost::ref(lastVal), _1));

Assuming that sum is a function that takes two ints and puts the result into it's first argument then this would leave the sum of the vector in lastVal 1.

This last example also can be used to illustrate why boost::bind doesn't create a true closure. Suppose that instead of using our bind expression immediately we return it using boost::function 2. When we try to use the bind object very bad things will happen, a crash if we're lucky. This happens because the boost::ref object in the bind object is referencing a variable that no longer exists3. If we had a true closure then the variable would continue to exist as long as the closure did and we'd be safe. Without garbage collection I don't see how to make this work4.

Once you have closures then lambda expressions (or local function definitions) become very useful. Unfortunately C++ has neither. There is the boost::lambda library which can be useful in this area but it is somewhat limited and in my experience it doesn't work so hot with VC++, even the newest incarnation of the compiler5. We can get local function definitions though by making a local structure definition6:

int sum(const std::vector<int>& values)
{   
    int total = 0;

    struct Calculate
{
    Calculate(int& total_) : m_total(total_) {}

    int& m_total;

    void operator()(int v2)
    {
    m_total += v2;
    }           
}

std::for_each(values.begin(), values.end(), Calculate(total));

return total;
}

One thing to note about the above is that in order to pull total in to the Calculate closure we had to have Calculate hold a reference to it7. Local structures like Calculate can refer to local variables in the enclosing function but only if they are static. Now we probably don't want to go declaring total static since that will lead to reentrancy problems. This is unfortunate, if we didn't have this static only restriction then Calculate would be much more compact. We can use bind to build the closure though and make things a bit more compact8:

int sum(const std::vector<int>& values)
{   
    int total = 0;

    struct Calculate
{
    static void run(int& total_, int v)
    {
    total_ += v;
        }           
}

std::for_each(values.begin(), values.end(), 
              boost::bind(Calculate::run, boost::ref(total), _1));

return total;
}

While this makes things a bit more compact the difference when you're binding more variables is much more dramatic. If we could make local function definitions the change in size would be slightly better still. If we didn't have the refer only to static local variables restriction it would be even better.

So we can get pretty close to closures and local function definitions in C++ without having them built into the language. Obviously you have to be careful to keep your local function definitions short in order to maintain readability. While it's nice to have a short block of code that you're passing into a function defined right where you pass it in, once the code gets too long it will start obscuring the enclosing functions flow and really belongs off on its own. But even if the block of code in question is defined outside of your function you can still close over it with bind.


  1. I realize this is a really contrived example and that there are much better ways to sum a sequence (std::accumulate comes to mind). But this example is a simple illustration of a technique that is useful when combined with the poor man's lambda that I talk about later.
  2. Note that we can't return the bind expression directly because the type of boost::bind(sum, boost::ref(lastVal), _1)) is some hideous thing that the documentation calls various variations on unspecified. Instead we need to capture the bind expression in a boost::function<void(int)> and return that.
  3. You might be debating the usefulness of this construct and you'd be right. In this case it's not so useful to create a bind the binds to a local variable and is returned from the function where that local variable exists. But we could instead bind to a member variable in an object and register that bind object as a callback somewhere. This is useful but puts you on dangerous ground where we need the object that contains the bound member variable to outlast the callback registration.
  4. One could address this by cluttering up the code with boost::shared_ptr's but that can quickly get messy. I've heard that the C++ standardization committee is talking about adding closures to the language but for the life of me I can't figure out how that's going to work without garbage collection. Maybe they're only talking about adding closures to Managed C++.
  5. Visual C++ * with the service pack at the time of this writing.
  6. Yep, you can make structure definitions within a function definition. I didn't know about this until a few months ago and it has made my life a lot easier. One thing to note is that you cannot have static members in a local structure so their usefulness can be somewhat curtailed in some situations. You also can't use templates at all in the local structure.
  7. The underscore on the end of total_ is only there to make explicit that the constructor parameter is different from the total local variable. The constructor parameter could just as well have been called total since nothing in Calculate can refer to the local variable total.
  8. Note that if you're using VC++ 2005 without the service pack a compiler bug could prevent this code from compiling.

Thursday, September 13, 2007

Missing the point

OK, I'll admit. I've jumped on the SICP bandwagon. I've worked through about half the book1 and am really liking it. Of course I've come to it a bit late to the book not being a computer science graduate, though it seems these days one probably wouldn't get exposed to it anyway or so I hear. It seems like one of those books that's great but people dread taking a class that uses it, kind of like Jackson or Goldstein for physics majors. Anyways, had the bandwagon not come by for me to jump on I probably wouldn't have ever found it so here's to bandwagons.

Enough blowing smoke up Abelman and Sussman's asses about their book. It's great, we all get it. Though it seems like some people have decided they liked the book but not the language and are going to do something about it. And to me it seems like that's missing the point. Sort of like how people go all ga-ga over peanut butter and chocolate together2, like somehow these two things are just meant to go together. Well in this case they are. A&B chose lisp for a reason, and not just because they're lisp weenies.

The way I feel about it is that there are certain language categories that everyone programmer should learn at least one language from. They are machine level 3, static imperative 4, dynamic 5, functional 6 and lisp 7.

Learning a machine level language will help you understand what the machine is doing with your code. Learning lisp will teach you what the compiler is doing with your code. Think of it as the assembly language of computation, whereas assembly is the, well, assembly language of computers. That's why A&B chose it. While there are other languages that look more like lambda calculus (ML anyone?), when you're writing lisp you're writing out the abstract syntax trees for your program. And understanding how you're programs goes from source code to a computation is powerful stuff.

Now I don't want to bag on the folks at SICP in other language but if you use another language when working through SICP then you're sort of missing the point. Going back and using the exercises later when you're learning a new language is fine, but the first time through use lisp. It won't bite but you might wear out your ( and ) keys.


  1. Kind of slow going, but when you've got a two year old at home you don't get a many solid blocks of time to too deeply into things.
  2. Never understood that one myself. Sure they taste OK together but I'm actually happier keeping them apart. But what do I know, I don't Even like my ice cream with chunky bits in it and have problems using my microwave.
  3. C is probably good enough but some assembly wouldn't hurt.
  4. Java, C#, C++, etc. For better or worse it's where the jobs are so you probably can't avoid learning at least one of these language.
  5. Python, Ruby, Javascript, etc.
  6. Preferably pure, lazy and strongly typed, but I guess we can compromise on a point or two.

Monday, June 25, 2007

pointer-less?

One thing I remember about Java back when I was working on enterprisey sorts of things is that for a language that supposedly has no pointers it sure seemed like we got a lot of NullPointerExceptions. NullPointerException was definitely the biggest cause of production bugs followed closely by ClassCastException. So if a language is purported to not have pointers why do they seem to be causing so many problems? Isn't Java supposed to be better than C++ due to this lack of pointers?

The problem is that Java does have pointers. In fact everything that isn't a primitive type is handled through pointers. There is no stack/heap dichotomy like there is in C/C++: you either have a primitive type that lives on the stack (or is part of a non-primitive object) or you have a non-primitive type that lives on the heap in the object store. These non-pointer pointers do have some advantages over their C/C++ cousins, the biggest being that dereferencing a null pointer doesn't bring your whole program crashing down around you. Ah the advantages of a managed run-time where an invalid pointer dereference doesn't have to treated as a possible attack and require the slaying of the perpetrator with extreme prejudice.

While it is nice that you can catch NullPointerExceptions, it would be nicer if people actually did it more than half the time. Like I said above: when I worked on enterprisey stuff NullPointerException was the single biggest cause of production problems. Now I don't think that me or any of the people I was working with in said shop were morons. And it seemed like failure to account for the possibility of null pointers was one of the biggest problems we saw in programming tests we gave during interviews. I'd say that this is a product of the "java has no pointers" mentality but C/C++ programmers make their fair share of the same sort of error. Maybe certain languages that have done away with pointers altogether are on to something. Anyway, maybe keep this in mind the next time you're bagging on C/C++ pointers compared to Java/C# keep in mind that you're not really that far ahead of the game, a few steps maybe but not leaps and bounds.

Wednesday, April 18, 2007

Bacon

My Microwave oven really wants me to eat a lot of bacon. I'm vegan and live in California, I'm already quite aware that my culinary habits are not exactly in sync with those of the average American. Even so, every time I go to nuke a tofu dog my microwave dutifully reminds me of this fact. TV, magazines and just about everything else also remind me of this fact so I really don't need the microwave giving me a bunch of crap about it as well. When I hit the "Microwave" button to get its attention it responds with "Bacon" every time. It doesn't think that I might just want it to zap something for 30 seconds or a minute, it immediately jumps to the conclusion that I must want bacon. If I want something else it requires that I convince it of this by pressing buttons and turning a knob.

Now you might be wondering why the microwave would want me to hit a button labeled "Microwave" before it will microwave something. It does seem a bit redundant if you don't know that my microwave oven is a microwave/convection combo oven. Given this fact it shouldn't surprise you that it also has a "Convection" button. In addition to this it also has "Speed Cook" button that puts the microwave in a mode that's similar to convection but it's faster. I don't remember why I would want to use the slower convection mode. It's one of those things that's in the manual and if you don't use it all the time your brain dumps it in preference to something more useful. And considering how much I've ended up using the convection mode of the oven this difference has never spent much time in my brain.

So I guess it's not all that illogical that I have to hit the "Microwave" button if I want to nuke something. Of course the bulk of the time I want to use the microwave and not the convection or mysterious speed-cook modes and I'm willing to bet that the majority of users of microwave/convection combo ovens are the same way. Even if they aren't I still think that defaulting to the microwave mode is the right thing to do. It seems to me that the amount of effort that you put in to starting some process should correspond to the amount of time that the process is going to be running relative to the other possible processes that a device could run. I'm not a usability or interaction design expert but the preceding seems reasonable to me. Maybe it's called "the principle of proportional effort" in user interface expert circles or something.

In my case I often want to nuke a tofu-dog or heat up some leftovers for my kid, both of which have run times of say 30 seconds. Running the convection oven for 30 seconds doesn't accomplish much of anything. On the rare occasion I actually use the convection oven I'd say I always run it for at least 5 minutes. So I would want to optimize the interface so that the shorter nuking session takes less time to start than the convection oven. Of course with my oven both operations take roughly the same amount of work to start. To nuke a tofu-dog I have to hit the "Microwave" button, turn a knob to get from "Bacon" to "Timed" mode, press the knob to select "Timed" mode, turn the knob again to select a time, press the knob again to lock in that time and finally press the knob one last time to confirm that, yes, I actually do want to cook something. If I want to convect1 some food I have to hit the "Convection" button, turn the knob to select a time and then press it lock in the time, turn the knob to select the heat level and press it to lock in the level and then press the knob again to confirm that I'm happy with my choices. Note that if the microwave wasn't convinced that I wanted bacon then there would be one less knob turn and push when using microwave mode and it would technically beat convection mode by a hair. Both modes could also eliminate one knob press by not asking for confirmation. Instead the oven could rely on the cancel button that I would hit the instant I realized that I had screwed something up. And, as these things usually go, the confirmation is now useless since I've been conditioned to press the knob twice after I get the time dialed in and if I screwed something up the time I just hit cancel.

Instead of having the interface assume that I want to do the quick and common operation it feigns ignorance and requires me to jump through a bunch of hoops. By default it should be assumed that I want a timed microwave run and if I start turning the knob without hitting a mode button then it should start setting the cooking time. When I press the knob it should just start, no confirmation. I can just hit the cancel button if I entered the wrong amount of time, a few stray microwaves isn't going to ruin my food. The oven does have a minute button that starts the microwave at one minute and then adds a minute to the run time for each successive press. Often if I'm nuking something for less than thirty seconds I'll just hit the minute button and stand there until the amount of time I actually wanted has passed at which point I'll hit cancel2.

Having to jump through all the hoops to nuke a tofu dog is annoying, but making bacon the default microwave setting just mystifies me. Am I really that out of touch with mainstream America that I don't realize that cooking bacon is the number one use of microwave's? I don't see members of my extended family using their microwaves for this, but they also live in California and thus might also be outliers when it comes to microwave oven market research. I know that obesity and heart disease are out of control in the US, but could bacon pushers microwave ovens be the reason? Or do the people at Kenmore like bacon so much that they assumed that everyone would like to have the bacon as their first microwaving choice? Did they sell the top slot to the pork industry? Am I reading too much into this. All I wanted to do is nuke a tofu dog, but every time I do I get all these questions in my head. And it also gets me wondering if there are people out there getting ready to write their own bacon screed after having used software that I've written.


  1. I suppose that convect is probably the wrong word to use here since really it's the air that is convecting in the oven, not the food. But cook doesn't exactly nail down what it is that is being done to the food so convect it is.
  2. It turns out that once the microwave is going, i.e. after I hit the minute button, turning the knob adjusts the run time. This moots my complaint about how long it takes to get the microwave going to some degree. It isn't exactly the most discoverable of interfaces though since we've had the oven for about six months and my wife just discovered this feature a couple of days ago. Either that or we're morons.