Monads by stealth

Common coding idiom: A window sometimes has a tooltip associated with it. A file object may be currently open, and therefore has a current offset, or it may be closed in which case it doesn’t. In both of these cases, maybe we have the extra data or maybe we don’t – it depends on the object’s state.

Mostly in C++, people use pointers for this. The window object contains a pointer to the tooltip object which is valid when the tooltip is relevant, and null the rest of the time. To me, this is a mediocre solution.

Before I go any further, I’d better explain that one of my strong beliefs is that you should be able to get a really good idea of how a class works just by looking at the data members (ie. the state) of the class. You shouldn’t really need to read the implementation. I find this a pretty useful test of code quality and code complexity. Classes which have been prematurely optimised will show up as having more data/state than they Really Need To. Classes which don’t have a single well-defined responsibility will often stand out because they have extra “I’m currenlty in this state” flags. Well-written classes will have distilled their state down to the absolute essentials, and every data item should be able to justify their inclusion.

Furthermore, it’s always a good idea to convey as much of your intent in your source code as possible. If an object owns another object, it is much better to use an auto_ptr than a raw pointer, since that’s their raison d’etre. Spare a thought for the guys who have to read your code six months later, and be as precise as possible with your data types. If the object owns the other object from birth until death, use a const auto_ptr, since that’s all that a const auto_ptr will allow. (Of course, this only works if everyone understands the implications of the idiom. But describing idioms once to people is much easier than having to document the hundreds of places in the code where the idioms use would’ve made things cleaner).

Anyway, back to the “maybe has it, maybe doesn’t” story. Most people use pointers for this. I called this mediocre because using a pointer doesn’t convey the “might be valid, might not” intent. I’ve seen people using a convention of suffixing pointers with 00 to indicate “may be null” – as in “if (window->tooltip00) {..}”. That’s a useful convention, but it’s not something which a compiler can check.

Another common approach to this problem is to define a Maybe (aka Optional) datatype. It’s a simple thing – a Maybe value either currently holds an integer or it’s empty. You can call a method (eg. isPresent() ) to see if it currently holds proper data or not, and call a get() method to retrieve the data.

This has some advantages over using a pointer. For a start, it’s pretty clear this this “maybe data” may be present or may not be present, and so that’s a big win in terms of communication. Also, it doesn’t force you to switch to handling data by-reference like pointers do.

But it’s still not perfect because there’s no way for the compiler to verify that your program only calls get() on maybe-values which have real data. Sure, you can add a runtime check but it would be much nicer if we can verify this property of our program at compile time.

One thing which strikes me is that every place where processing of a Maybe<> value occurs we end up with an if-statement to check whether or not it’s valid. That’s a shame, since it’s basically code duplication all over the shop. Is there a way we could push this duplicate conditional code inside the Maybe<> class itself? Can we take the two bodies of the conditional and pass them to the Maybe<> class to process?

At this point, we’re kinda thinking upside down. Rather than thinking of Maybe as a passive container, we’re going to think of it as the active partner. It knows what it’s internal state is, but it won’t let you at it directly. Instead, the only thing you can do with a Maybe is pass it a couple of function pointers called “do this when you have data” and “do this when you’re empty”. It’s a bit of a shame having to turn the conditional bodies into fully-fledged functions, but that’s pretty much the best we can do in C++. So now the Maybe<> class gains a new method which, being unimaginative, we could call “doStuff” – it just checks whether it has real data, and runs the appropriate argument (ie. a function). Now we’ve managed to factor out all these conditionals.

(Well, it’s a pretty limited idea when we’re using C++ because creating functions is fairly work-intensive. You have to figure out what data they need, and pass it to them. If we used a better language (like, maybe, ocaml!) – which allowed you to treat functions as flexibly as values, creating them on the fly, automatically capturing their context, and passing them around as easily as if they were integers – then it’d be a much more powerful notion).

So, this has been a refactoring of the Maybe<> class from a simple passive data container into a more active participant (albeit a refactoring which can’t be expressed particularly elegantly in C++). It was driven by a desire to more fully express our intent in the source code, and to ensure that we always deal with the two cases (data, and no-data) every time we process a Maybe<> value. But what we’ve done is interesting. We went from a situation where the Maybe’s state was externally visible, to a situation where it was safely wrapped up inside the Maybe object and could only be acted upon by the “special tongs” of the two function we passed to the Maybe<> object.

A lot of work for a little advantage? Nah, now you’re basically playing with a monad, and you never even noticed.

Predicate objects

“Cecil has predicate objects, which allow virtual “subclasses” to be defined carrying specialized methods that override their parent’s methods whenever some boolean predicate over the object is true. In this way, inheritance can be used to model time-varying and/or state-dependent properties of objects just like permanent properties of objects” (from the Cecil homepage)

Now, this is kinda interesting because I was thinking about something a bit like this about a year ago. And furthermore, Cecil has a tasty looking feature list – multimethods, optional polymorphic static typesystem (if you don’t supply static type information, typechecking is done at runtime), closures, and a Self-like classless object system.

And for something completely different. Someone stole the front quick-release from my bike, outside work today. They didn’t take the whole wheel, which was left neatly in place. They just removed the quick release mechanism. How annoyingly strange. Time to arrange a webcam pointing at my bike ..

Compilers galore

Just released, gcc 3.4 and a free download of the MS C++ compiler. Go figure.

I’ve just got one of these (the thing on the right, not the coke can) which is now quietly humming away running my mail server. It is currently sitting on a few bits of wood in my cupboard (the best kind way to silence a PC – put it somwhere else and knock holes through walls for the cables) but maybe I should do something like this with it?

I’ve twice recently had cause to refer to this article on “upside-down inheritance”, which discusses a very flexible method of composing functionality together, without some of the problems of a purely multiple-inheritance based approach.

(Oh, I forgot to add: this weblog is now syndicated over at LiveJournal)

Pretty Printing Parsing Problems

Ah, I’ve returned to the Real World after a week of snowboarding fun. Culture shock, muchly.

I haven’t written much recently. That was’t due a lack of stuff to write about, but more due to me doing a little bit of this, then a little bit of that, and never really doing anything in large enough chunks to write cohesively about. Still, I want to play catchup so that in a years time I can remember where I spend my efforts.

My rough, sprawling plan is to finally write my own dream development environment. I’ve pondered lots about what this would look like, but what liberated me was deciding to wave a metaphorical middle finger at the rest of the world. This is going to be *my* dream development environment. I’ll make the tradeoffs which are sensible for me, and I don’t care if anyone other than me finds the end result useful. I’m waving goodbye to ascii source code. CVS, diff, grep and all the other text-based tools won’t be relevant any more. I’ve nothing against these fine tools, but the Big Number One tradeoff I’m making is to base the whole system around an abstract representation of source code rather than a concrete ascii representation. This isn’t a straightforward tradeoff to make. There are as many downsides as there are upsides, but after years of playing around with development tools I think I can tolerate the downsides in order to enjoy the upsides.

This development system will be targeted for, and written in ocaml – because it’s the finest language I’ve encountered. A few years ago, I looked through the gcc sources and spend weeks trying to untangle how they worked. In contrast, when I recently tried to use the lexer, parser and typechecker from the ocaml compiler in a stand-alone test application, it took me about 20 minutes to get it working.

So that’s the plan anyway, in the vaguest sense of the word. It opens the door to all sorts of interesting problems.

How will I edit the code then? Well, to get started, I’m going to pretty-print the abstract representation of each module back into (you guessed it) ascii source code, and use good old emacs! That’s the quick and easy way to get going. But the crucial point is that it’s not the *only* way to edit code in this system. I will also be able to apply semantic transformations (like rename) direct to the abstract source tree. I can write my own display routines to show the code using whatever crazy display or edit method I can conceive of. The raw information is all there ready to be used.

Previously, when I thought about writing a development environment I’d spend ages wondering about how to keep maintain the “original sources”(ie. the ascii files) when the user was busy applying refactorings. Well, I fixed that problem by getting rid of the ascii files! I’ll import my legacy sources into the system once and from that day on, I’ll be working with vastly improved tools and I’ll forget all about files. If I want to distribute an ascii-source version to someone else, I’ll pretty-print one.

“It won’t inter-operate with people’s existing toolsets”, you say. “Noone will buy it”, you say. You’re totally right. But I don’t care. I’m writing this for me, because it’s a Much Better Way to write software. Then, uhh, I’m going to take over the world, uhh, or make tea, or something … 😉

(I had an discussion once with Michelle once where I said that if you believe software patents are wrong, but you’re in a situation where the company you are running is going to go bust unless you pursue some patents, then the Right Things To Do is to stick to your principles and have the company go bust. I don’t often have many views which are strongly one way or the other – most of the time I end up arguing both sides – but when I do get round to strongly believing in something, I’m fairly solid in my beliefs. It annoys me on a daily basis that we monkeys keep ourselves busy with inferior, inefficient coding tools when if we used something better, we could spend more time outside enjoying the sun)

So, onto the concrete software problems! I was trying to find elegant solutions to pretty-printing of source code. There’s lots of literature on how to parse source code – that is, going from the crummy ascii-based representations which we humans have traditionally favoured with all it’s implicit conventions, into a clean structured representation. Pretty-printing, the opposite problem, gets less attention .. I guess because fewer people ever need to do it.

There’s two sides to the pretty-printing problem. One is how to lay the source code out on the page – where to put line-breaks and whitespace. The second is how to reconstruct the “optional” presentation elements – like, putting parenthesis in expressions where needed, and even sometimes adding extra ones where they’re not absolutely needed if that will make it easier for me to read.

Fortunately, this is an area where we people have been showcasing the power and elegance of functional programming languages such as ocaml and Haskell. I found papers describing a pretty printing method and an “unparsing” method which not only describe concise elegant solutions, but also prove all sorts of neat and useful properties of the algorithms. Tasty.

With pretty-printing up and running, I can choose what size of “slice” I want to edit – a single function, a whole module, or maybe a method and all its callees. Then I edit this by hand, and run a parser on it, and then integrate it back into the abstract source tree. If I’ve pretty-printed using the standard ocaml syntax, I can just reuse the standard ocaml parser. I could make up my own syntax too, but then I’d have to write a parser as well as a pretty printer. (There’s a bit of overlap with camlp4 obviously).

Anyhow, for me this is a “burn the diskpacks” project. I am cherry-picking the relevant bits from lisp and smalltalk, mixing them together with ocaml and getting rid of historical baggage like ascii files where necessary. As I said earlier, the real breakthrough was deciding to appoint myself as the single target user. And also, being arrogant enough to believe that most development tools and languages today really do suck beyond belief. Heh, having said all that .. watch me loose interest in computers for the next six months! 😉

Hardware read/write breakpoints

Intel processors have four hardware breakpoints, which means you can drop down into the debugger when someone writes *or reads* from a memory address. This is pretty handy when you’re working with crufty languages like C++ and you have to track down memory corruption. Of course, you could use Purify/Boundschecker but here’s a cheaper and often faster solution.

Include the header hwbreak.h in your project, and create a HWBreak object either on the stack or heap (depending on how long you want it to live for). There’s a quick example in the comments. Now when the memory at that address is modified or read, you’ll drop down into the debugger.

(After I wrote this, I found another webpage which describes a similar approach, whose URL I’ve now lost. The difference is that I jump through hoops to ensure that I only change the thread context on a suspended thread, since the API docs warn against doing it on a running thread).

Now, DevStudio already gives you access to break-on-write breakpoints via the “data breakpoints” pane – you enter WO(0x12345678) to break if the WOrd at that address is modified. But there’s no way to get break-on-read breakpoints from within DevStudio. Well, in a vanilla DevStudio. But if you’re stubborn you can hack the binary to use read-write breakpoints instead of write-only ones. Details to follow …