I recently ran into some “interesting” behaviour when using lambda in Python. Perhaps it’s only interesting because I learnt lambdas from a functional language background, where I expect that they work a particular way, and the rest of the world that learnt lambdas through Python, Ruby or JavaScript disagree. (Shouts out to you Objective-C developers who are discovering the wonders of blocks, too.) Nevertheless, I thought this would be blog-worthy. Here’s some Python code that shows the behaviour that I found on Stack Overflow:

Since I succumb to reading source code in blog posts by interpreting them as “blah”¹, a high-level overview of what that code does is:

1. iterate over a list of strings,
2. create a new list of functions that prints out the strings, and then
3. call those functions, which prints the strings.

Simple, eh? Prints “do”, then “re”, then “mi”, eh? Wrong. It prints out “mi”, then “mi”, then “mi”. Ka-what?

(I’d like to stress that this isn’t a theoretical example. I hit this problem in production code, and boy, it was lots of fun to debug. I hit the solution right away thanks to the wonders of Google and Stack Overflow, but it took me a long time to figure out that something was going wrong at that particular point in the code, and not somewhere else in my logic.)

The second answer to the Stack Overflow question is the clearest exposition of the problem, with a rather clever solution too. I won’t repeat it here since you all know how to follow links. However, while that answer explains the problem, there’s a deeper issue. The inconceivable Manuel Chakravarty provides a far more insightful answer when I emailed him to express my surprise at Python’s lambda semantics:

This is a very awkward semantics for lambdas. It is also probably almost impossible to have a reasonable semantics for lambdas in a language, such as Python.

The behaviour that the person on SO, and I guess you, found surprising is that the contents of the free variables of the lambdas body could change between the point in time where the closure for the lambda was created and when that closure was finally executed. The obvious solution is to put a copy of the value of the variable (instead of a pointer to the original variable) into the closure.

But how about a lambda where a free variable refers to a 100MB object graph? Do you want that to be deep copied by default? If not, you can get the same problem again.

So, the real issue here is the interaction between mutable storage and closures. Sometimes you want the free variables to be copied (so you get their value at closure creation time) and sometimes you don’t want them copied (so you get their value at closure execution time or simply because the value is big and you don’t want to copy it).

And, indeed, since I love being categorised as a massive Apple fanboy, I found the same surprising behaviour with Apple’s blocks semantics in C, too:

You can see the Gist page for this sample code to see how to work around the problem in Objective-C (basically: copy the block), and also to see what it’d look like in Haskell (with the correct behaviour).

In Python, the Stack Overflow solution that I linked to has an extremely concise way of giving the programmer the option to either copy the value or simply maintain a reference to it, and the syntax is clear enough—once you understand what on Earth what the problem is, that is. I don’t understand Ruby or JavaScript well enough to comment on how they’d capture the immediate value for lambdas or whether they considered this design problem. C++0x will, unsurprisingly, give programmers full control over lambda behaviour that will no doubt confuse the hell out of people. (See the C++0x language draft, section 5.1.2 on page 91.)

In his usual incredibly didactic manner, Manuel then went on to explain something else insightful:

I believe there is a deeper issue here. Copying features of FP languages is the hip thing in language design these days. That’s fine, but many of the high-powered FP language features derive their convenience from being unspecific, or at least unconventional, about the execution time of a piece of code. Lambdas delay code execution, laziness provides demand-dependent code execution plus memoisation, continuations capture closures including their environment (ie, the stack), etc. Another instance of that problem was highlighted by Joe Duffy in his STM retrospective.

I would say, mutability and flexible control flow are fundamentally at odds in language design.

Indeed, I’ve been doing some language exploration again lately as the lack of static typing in Python is really beginning to bug me, and almost all the modern languages that attempt to pull functional programming concepts into object-oriented land seem like a complete Frankenstein, partially due to mutability. Language designers, please, this is 2011: multicore computing is the norm now, whether we like it or not. If you’re going to make an imperative language—and that includes all your OO languages—I’ll paraphrase Tim Sweeney: in a concurrent world, mutable is the wrong default! I’d love a C++ or Objective-C where all variables are const by default.

One take-away point from all this is to try to keep your language semantics simple. I love Dan Ingall’s quote from Design Principles Behind Smalltalk: “if a system is to serve the creative spirit, it must be entirely comprehensible to a single individual”. I love Objective-C partially because its message-passing semantics are straightforward, and its runtime has a amazingly compact API and implementation considering how powerful it is. I’ve been using Python for a while now, and I still don’t really know the truly nitty-gritty details about subtle object behaviours (e.g. class variables, multiple inheritance). And I mostly agree with Guido’s assertion that Python should not have included lambda nor reduce, given what Python’s goals are. After discovering this quirk about them, I’m still using the lambda in production code because the code savings does justify the complexity, but you bet your ass there’s a big comment there saying “warning, pretentous code trickery be here!”

1. See point 13 of Knuth et al.’s Mathematical Writing report.

UPDATE: There’s a lot more subtlety at play here than I first realised, and a couple of statements I’ve made above are incorrect. Please see the comments if you want to really figure out what’s going on: I’d summarise the issues, but the interaction between various language semantics are extremely subtle and I fear I’d simply get it wrong again. Thank you to all the commenters for both correcting me and adding a lot of value to this post. (I like this Internet thing! Other people do my work for me!)

Update #2

I’ve been overwhelmed by the comments, in both the workload sense and in the pleasantly-surprised-that-this-provoked-some-discussion sense. Boy, did I get skooled in a couple of areas. I’ve had a couple of requests to try to summarise the issues here, so I’ll do my best to do so.

Retrospective: Python

It’s clear that my misunderstanding of Python’s scoping/namespace rules is the underlying cause of the problem: in Python, variables declared in for/while/if statements will be declared in the compound block’s existing scope, and not create a new scope. So in my example above, using a lambda inside the for loop creates a closure that references the variable m, but m’s value has changed by the end of the for loop to “mi”, which is why it prints “mi, mi, mi”. I’d prefer to link to the official Python documentation about this here rather than writing my own words that may be incorrect, but I can’t actually find anything in the official documentation that authoritatively defines this. I can find a lot of blog posts warning about it—just Google for “Python for while if scoping” to see a few—and I’ve perused the entire chapter on Python’s compound statements, but I just can’t find it. Please let me know in the comments if you do find a link, in which case I’ll retract half this paragraph and stand corrected, and also a little shorter.

I stand by my assertion that Python’s for/while/if scoping is slightly surprising, and for some particular scenarios—like this—it can cause some problems that are very difficult to debug. You may call me a dumbass for bringing assumptions about one language to another, and I will accept my dumbassery award. I will happily admit that this semantics has advantages, such as being able to access the last value assigned in a for loop, or not requiring definitions of variables before executing an if statement that assigns to those variables and using it later in the same scope. All language design decisions have advantages and disadvantages, and I respect Python’s choice here. However, I’ve been using Python for a few years, consider myself to be at least a somewhat competent programmer, and only just found out about this behaviour. I’m surprised 90% of my code actually works as intended given these semantics. In my defence, this behaviour was not mentioned at all in the excellent Python tutorials, and, as mentioned above, I can’t a reference for it in the official Python documentation. I’d expect that this behaviour is enough of a difference vs other languages to at least be mentioned. You may disagree with me and regard this as a minor issue that only shows up when you do crazy foo like use lambda inside a for loop, in which case I’ll shrug my shoulders and go drink another beer.

I’d be interested to see if anyone can come up an equivalent for the “Closures and lexical closures” example at http://c2.com/cgi/wiki?ScopeAndClosures, given another Python scoping rule that assignment to a variable automatically makes it a local variable. (Thus, the necessity for Python’s global keyword.) I’m guessing that you can create the createAdder closure example there with Python’s lambdas, but my brain is pretty bugged out today so I can’t find an equivalent for it right now. You can simply write a callable class to do that and instantiate an object, of course, which I do think is about 1000x clearer. There’s no point using closures when the culture understands objects a ton better, and the resulting code is more maintainable.

Python summary: understand how scoping in for/while/if blocks work, otherwise you’ll run into problems that can cost you hours, and get skooled publicly on the Internet for all your comrades to laugh at. Even with all the language design decisions that I consider weird, I still respect and like Python, and I feel that Guido’s answer to the stuff I was attempting would be “don’t do that”. Writing a callable class in Python is far less tricky than using closures, because a billion times more people understand their semantics. It’s always a design question of whether the extra trickiness is more maintainable or not.

Retrospective: Blocks in C

My C code with blocks failed for a completely different reason unrelated to the Python version, and this was a total beginner’s error with blocks, for which I’m slightly embarrassed. The block was being stack-allocated, so upon exit of the for loop that assigns the function list, the pointers to the blocks are effectively invalid. I was a little unlucky that the program didn’t crash. The correct solution is to perform a Block_copy, in which case things work as expected.

Retrospective: Closures

Not all closures are the same; or, rather, closures are closures, but their semantics can differ from language to language due to many different language design decisions—such as how one chooses to define the lexical environment. Wikipedia’s article on closures has an excellent section on differences in closure semantics.

Retrospective: Mutability

I stand by all my assertions about mutability. This is where the Haskell tribe will nod their collective heads, and all the anti-Haskell tribes think I’m an idiot. Look, I use a lot of languages, and I love and hate many things about each of them, Haskell included. I fought against Haskell for years and hated it until I finally realised that one of its massive benefits is that things bloody well work an unbelievable amount of the time once your code compiles. Don’t underestimate how much of a revelation this is, because that’s the point where the language’s beauty, elegance and crazy type system fade into the background and, for the first time, you see one gigantic pragmatic advantage of Haskell.

One of the things that Haskell does to achieve this is the severe restriction on making things immutable. Apart from the lovely checkbox reason that you can write concurrent-safe algorithms with far less fear, I truly believe that this makes for generally more maintainable code. You can read code and think once about what value a variable holds, rather than keep it in the back of your mind all the time. The human mind is better at keeping track of multiple names, rather than a single name with different states.

The interaction of state and control flow is perhaps the most complex thing to reason about in programming—think concurrency, re-entrancy, disruptive control flow such as longjmp, exceptions, co-routines—and mutability complicates that by an order of magnitude. The subtle difference in behaviour between all the languages discussed in the comments is exemplar that “well-understood” concepts such as lexical scoping, for loops and closures can produce a result that many people still don’t expect; at least for this simple example, these issues would have been avoided altogether if mutability was disallowed. Of course mutability has its place. I’m just advocating that we should restrict it where possible, and at least a smattering of other languages—and hopefully everyone who has to deal with thread-safe code—agrees with me.

Closing

I’d truly like to thank everyone who added their voice and spent the time to comment on this post. It’s been highly enlightening, humbling, and has renewed my interest in discussing programming languages again after a long time away from it. And hey, I’m blogging again. (Though perhaps after this post, you may not think that two of those things are good things.) It’s always nice when you learn something new, which I wouldn’t have if not for the excellent peer review. Science: it works, bitches!

Just before I left Sydney, I gave one last talk at the revived Sydney Cocoaheads user group about Objective-C Internals. It’s similar to the presentation that I gave at fp-syd a few months ago about Objective-C and Mac OS X programming, but was tailored for a Mac audience rather than a functional programming audience. As a result, the Cocoaheads talk has a lot more detail on the object model, memory layout, and how message-sending works, and less info on higher-order messaging and language features (e.g. I didn’t talk about categories at all.)

If you’re a Mac coder, hopefully you’ll find something new in there. As always, drop me an email if you have any questions!

P.S. For all the voyeurs out there, the San Francisco move & Pixar are both going great! More news on that soon, too.

Quite often, you may have simple setter methods that need to do a just a tiny bit of work before or after setting an instance variable. For example, maybe you need to redraw something after setting the property of an object. So, instead of writing this:

You’d probably want to move the relevant code to your -setBackgroundColor: accessor instead:

Then you can simply call -setBackgroundColor: and expect it all to work nicely:

(You could use Key-Value Observing to do this, but I generally avoid KVO for simple intra-class property dependencies like this. I don’t think the overhead of maintaining all the KVC dependencies and KVO-related methods is worth the cost.)

Of course, the above method requires that you write all that stupid boilerplate memory management code in the accessor. Instead of doing that, I tend to declare a private _backgroundColor property in the class, @synthesize a method for the private property, and then use the private property’s generated accessors instead:

With that technique, it’s possible to completely directly setting ivars, and thus avoid -retain and -release altogether. (You’ll still need to use -autorelease at various times, of course, but that’s reasonably rare.) We have some source code files that are well over 2000 lines of code without a single explicit [_ivar retain]; or [_ivar release]; call thanks to this technique. (Yeah, 2000 lines is also large and the class needs refactoring, but that’s another story.)

Of course, you could just use garbage collection which avoids 99% of the need for this bollocks:

But plenty of us don’t have that luxury yet. (iPhone, ahem.)

For the UNIX users out there who use the git revision control system with the oldskool less pager, try adding the following to your ~/.gitconfig file:

[core]
    # search for core.pager in
    # <http://www.kernel.org/pub/software/scm/git/docs/git-config.html>
    # to see why we use this convoluted syntax
    pager = less -$LESS -SFRX -SR +'/^---'

That’ll launch less with three options set:

• -S: chops long lines rather than folding them (personal preference),
• -R: permits ANSI colour escape sequences so that git’s diff colouring still works, and
• +'/^---': sets the default search regex to ^--- (find --- at the beginning of the line), so that you can easily skip to the next file in your pager with the n key.

The last one’s the handy tip. I browse commits using git diff before committing them, and like being able to jump quickly back and forth between files. Alas, since less is a dumb pager and doesn’t understand the semantics of diff patches, we simply set the find regex to ^---, which does what we want.

Of course, feel free to change the options to your heart’s content. See the less(1) manpage for the gory details.

As the comment in the configuration file says, you’ll need to use the convoluted less -$LESS -SFRX prefix due to interesting git behaviour with the LESS environment variable:

Note that git sets the LESS environment variable to FRSX if it is unset when it runs the pager. One can change these settings by setting the LESS variable to some other value. Alternately, these settings can be overridden on a project or global basis by setting the core.pager option. Setting core.pager has no affect on the LESS environment variable behaviour above, so if you want to override git’s default settings this way, you need to be explicit. For example, to disable the S option in a backward compatible manner, set core.pager to "less -+$LESS -FRX". This will be passed to the shell by git, which will translate the final command to "LESS=FRSX less -+FRSX -FRX".

(And sure, I could switch to using a different pager, but I’ve been using less for more than a decade. Yep, I know all about Emacs & Vim’s diff-mode and Changes.app. It’s hard to break old habits.)

Four little announcements, all of them Mac-related:

First, myself and my comrades at Realmac Software are very proud to announce the release of LittleSnapper 1.0, our swiss-army-knife picture, screenshot and website organisation utility thingamijiggo. We’ve all worked hard on this for the past few months and sweated over a ton of details to try to make it a polished user experience and be a joy to use; we hope you agree. (You would not believe how long we spent figuring out how the blur and highlighting tools should work before they became their final incarnations, or how much pain was involved when we decided to add FTP and SFTP¹ support late in the development cycle.) If you’re a Mac user, give it a whirl; it’s a hard program to describe because it has a lot of different workflows, but between the quick annotation tools, easy Web sharing with QuickSnapper/Flickr/SFTP¹, website DOM snapping, and the iPhoto-like forget-about-what-folder-you-need-to-put-your-picture-in snapshot management, I’m sure you’ll find something useful for you in there. Hopefully our hard work can make life just a little easier for you!

¹ FTP must die.

I blogged earlier that I was speaking at MacDev 2009 in April, but didn’t mention exactly what I was talking about. Well, the talk abstract’s up now:

One reason for Mac OS X’s success is Objective-C, combining the dynamism of a scripting language with the performance of a compiled language. However, how does Objective-C work its magic and what principles is it based upon? In this session, we explore the inner workings of the Objective-C runtime, and see how a little knowledge about programming language foundations—such as lambda calculus and type theory—can go a long way to tackling difficult topics in Cocoa such as error handling and concurrency. We’ll cover a broad range of areas such as garbage collection, blocks, and data structure design, with a focus on practical tips and techniques that can immediately improve your own code’s quality and maintainability.

So, two sections: first, low-level hackery of the Objective-C runtime. Second, a different kind of low-level hackery, and one that’s arguably far more important: understanding the essence of computation and programming languages, and why I fell in love with both Haskell & Objective-C, two languages at completely opposite ends of the planet.

I’d like to point out that while the MacDev registration fee seems fairly expensive at £399, keep in mind that covers your accommodation and also meals, which easily covers £100-£150. Scotty’s done a lot of organising so that you don’t have to. There’s also a Christmas special on at the moment where a few applications are included in the registration price; check the MacDev 2009 website for details.

If you’re an imsoniac and are having trouble sleeping, you’ll hopefully enjoy a recent Late Night Cocoa episode where I talk to Scotty about Garbage Collection. (Actually, you probably won’t enjoy it so much after you find out exactly how -retain & -release are implemented under-the-hood. The words CFBag and “lock” should hopefully scare you enough.) It’s a bit of a long episode at over an hour and a quarter long, but next time I’ll say “um” a bit less which should shorten it to about half an hour. Have fun. And use GC! (LittleSnapper and RapidWeaver both aren’t GC yet, but you bet your ass they will be for the next major versions.)

I’ve had a pretty long exodus away from the fp-syd user group since I was off getting drunk overseas for about four months. That, of course, meant that somehow my brain was rather misplaced when I arrived back in Sydney, so I decided to give a talk at fp-syd upon my return… on the same day that LittleSnapper 1.0 was due to be released, leaving pretty much no margin for error. Oops. I’ll glad to say that the gusto prevailed, and that both the talk seemed to go OK (well, I wasn’t booed off the stage anyway), and LittleSnapper was released on time. (Just; thanks Alan and Danny!) My talk there was similar to the one I gave at Galois in Portland earlier this year: a whirlwind tour of the Objective-C programming language and Mac OS X technologies for a functional programming audience. In particular:

• basics of the runtime system,
• higher-order messaging and its analogy to higher-order functions in functional languages,
• some details on the engineering marvel that is the Objective-C garbage collector, and
• (updated!) information on Blocks, LLVM and Clang, and a wee tiny bit of info on Grand Central Dispatch and OpenCL.

I’ve updated the talk with a few extra slides, since Apple have made a little more information to the public now. (In particular, brief information on Blocks, Grand Central Dispatch and OpenCL.) Enjoy all!

A website named Neat Little Mac Apps is not the kind of place you’d expect to find an interview with a operating systems and filesystems hacker. Nevertheless, one of their podcasts was just that: an interview with UNIX and BSD legend Marshall Kirk McKusick. (He has his own Wikipedia page; he must be famous!)

There’s some great stuff in there, including the origin of the BSD daemon (Pixar, would you believe? Or, well, Lucasarts at the time…), and a great story about how a bug was introduced into the 4.2 BSD version of the pervasive UNIX diff utility. Marshall’s full of energy, and it’s a great interview; it’s a little amusing to see the stark contrast between the interviewer and McKusick, both of whom have rather different definitions of what constitutes an operating system.

I’ve written before about git-svn and why I use it, but a major stumbling block with git-svn has been been a lack of support for svn:externals. If your project’s small and you have full control over the repository, you may be fortunate enough to not have any svn:externals definitions, or perhaps you can restructure your repository so you don’t need them anymore and live in git and Subversion interoperability bliss.

However, many projects absolutely require svn:externals, and once you start having common libraries and frameworks that are shared amongst multiple projects, it becomes very difficult to avoid svn:externals. What to do for the git-svn user?

If you Google around, it’s easy enough to find solutions out there, such as git-me-up, step-by-step tutorials, explanations about using git submodules, and an overview of all the different ways you can integrate the two things nicely. However, I didn’t like any of those solutions: either they required too much effort, were too fragile and could break easily if you did something wrong with your git configuration, or were simply too complex for such a seemingly simple problem. (Ah, I do like dismissing entire classes of solutions by wand-having them as over-engineering.)

So, in the great spirit of scratching your own itch, here’s my own damn solution:

git-svn-clone-externals

This is a very simple shell script to make git-svn clone your svn:externals definitions. Place the script in a directory where you have one or more svn:externals definitions, run it, and it will:

• git svn clone each external into a .git_externals/ directory.
• symlink the cloned repository in .git_externals/ to the proper directory name.
• add the symlink and .git_externals/ to the .git/info/excludes/ file, so that you’re not pestered about it when performing a git status.

That’s pretty much about it. Low-tech and cheap and cheery, but I couldn’t find anything else like it after extensive Googling, so hopefully some other people out there with low-tech minds like mine will find this useful.

You could certainly make the script a lot more complex and do things such as share svn:externals repositories between different git repositories, traverse through the entire git repository to detect svn:externals definitions instead of having to place the script in the correct directory, etc… but this works, it’s simple, and it does just the one thing, unlike a lot of other git/svn integration scripts that I’ve found. I absolutely do welcome those features, but I figured I’d push this out since it works for me and is probably useful for others.

The source is on github.com at http://github.com/andrep/git-svn-clone-externals/tree/master. Have fun subverting your Subversion overlords!

I have the small honour of being a speaker at the maiden conference of MacDev 2009, a grass-roots, independently run, Mac developer conference in the UK that’s being held in April next year. MacDev looks like it’ll be the European equivalent of C4, which was absolutely the best Mac developer conference I’ve ever been to; I’d say it’s the Mac equivalent of Linux.conf.au. If you’re a Mac developer at all, come along, it should be great fun, and give your liver a nice workout. Plus, how can you ignore such a sexy list of speakers?

Update: My talk abstract is now available…

One reason for Mac OS X’s success is Objective-C, combining the dynamism of a scripting language with the performance of a compiled language. However, how does Objective-C work its magic and what principles is it based upon? In this session, we explore the inner workings of the Objective-C runtime, and see how a little knowledge about programming language foundations—such as lambda calculus and type theory—can go a long way to tackling difficult topics in Cocoa such as error handling and concurrency. We’ll cover a broad range of areas such as garbage collection, blocks, and data structure design, with a focus on practical tips and techniques that can immediately improve your own code’s quality and maintainability.

I am a great believer in getting the foundations right. Similarly to how bad code design or architecture often leads to a ton of bugs that simply wouldn’t exist in well-designed code, building a complex system on unsteady foundations can produce a lot of unnecessary pain. What are the foundations of your favourite programming language?

It’s 2008 and we’re still seeing buffer overflows in C.

We use Subversion for our revision control system, and it’s great. It’s certainly not the most advanced thing out there, but it has perhaps the best client support on every platform out there, and when you need to work with non-coders on Windows, Linux and Mac OS X, there’s a lot of better things to do than explain how to use the command-line to people who’ve never heard of it before.

However, I also really need to work offline. My usual modus operandi is working at a café without Internet access (thanks for still being in the stone-age when it comes to data access, Australia), which pretty rules out using Subversion, because I can’t do commits when I do the majority of my work. So, I used svk for quite a long time, and everything was good.

Then, about a month ago, I got annoyed with svk screwing up relatively simple pushes and pulls for the last time. svk seems to work fine if you only track one branch and all you ever do is use its capabilities to commit offline, but the moment you start doing anything vaguely complicated like merges, or track both the trunk and a branch or two, it’ll explode. Workmates generally don’t like it when they see 20 commits arrive the next morning that totally FUBAR your repository.

So, I started using git-svn instead. People who know me will understand that I have a hatred of crap user interfaces, and I have a special hatred of UIs that are different “just because”, which applies to git rather well. I absolutely refused to use tla for that reason—which thankfully never seems to be mentioned in distributed revision control circles anymore—and I stayed away from git for a long time because of its refusal to use conventional revision control terminology. git-svn in particular suffered more much from (ab)using different terminology than git, because you were intermixing Subversion jargon with git jargon. Sorry, you use checkout to revert a commit? And checkout also switches between branches? revert is like a merge? WTF? The five or ten tutorials that I found on the ‘net helped quite a lot, but since a lot of them told me to do things in different ways and I didn’t know what the subtle differences between the commands were, I went back to tolerating svk until it screwed up a commit for the very last time. I also tried really hard to use bzr-svn since I really like Bazaar (and the guys behind Bazaar), but it was clear that git-svn was stable and ready to use right now, whereas bzr-svn still had some very rough edges around it and isn’t quite ready for production yet.

However, now that I’ve got my head wrapped around git’s jargon, I’m very happy to say that it was well worth the time for my brain to learn it. Linus elevated himself from “bloody good” to “true genius” in my eyes for writing that thing in a week, and I now have a very happy workflow using git to integrate with svn.

So, just to pollute the Intertubes more, here’s my own git-svn cheatsheet. I don’t know if this is the most correct way to do things (is there any “correct” way to do things in git?), but it certainly works for me:

* initial repository import (svk sync):
git-svn init https://foo.com/svn -T trunk -b branches -t tags
git checkout -b work trunk

* pulling from upstream (svk pull):
git-svn rebase

* pulling from upstream when there's new branches/tags/etc added:
git-svn fetch

* switching between branches:
git checkout branchname

* svk/svn diff -c NNNN:
git diff NNNN^!

* commiting a change:
git add
git commit

* reverting a change:
git checkout path

* pushing changes upstream (svk push):
git-svn dcommit

* importing svn:ignore:
(echo; git-svn show-ignore) >> .git/info/exclude

* uncommit:
git reset <SHA1 to reset to>

Drop me an email if you have suggestions to improve those. About the only thing that I miss from svk was the great feature of being able to delete a filename from the commit message, which would unstage it from the commit. That was tremendously useful; it meant that you could git commit -a all your changes except one little file, which was simply deleting one line. It’s much easier than tediously trying to git add thirteen files in different directories just you can omit one file.

One tip for git: if your repository has top-level trunk/branches/tags directories, like this:

trunk/
  foo/
  bar/
branches/
  foo-experimental/
  bar-experimental/
tags/
  foo-1.0/
  bar-0.5/

That layout makes switching between the trunk and a branch of a project quite annoying, because while you can “switch” to (checkout) branches/foo-experimental/, git won’t let you checkout trunk/foo; it’ll only let you checkout trunk. This isn’t a big problem, but it does mean that your overall directory structure keeps changing because switching to trunk means that you have foo/ and bar/ directories, while switching to a foo-experimental or bar-experimental omits those directories. This ruins your git excludes and tends to cause general confusion with old files being left behind when switching branches.

Since many of us will only want to track one particular project in a Subversion repository rather than an entire tree (i.e. switch between trunk/foo and branches/foo-experimental), change your .git/config file from this:

[svn-remote "svn"]
    url = https://mysillyserver.com/svn
    fetch = trunk:refs/remotes/trunk
    branches = branches/*:refs/remotes/*
    tags = tags/*:refs/remotes/tags/*

to this:

[svn-remote "svn"]
    url = https://mysillyserver.com/svn
    fetch = trunk/foo:refs/remotes/trunk
     ; ^ change "trunk" to "trunk/foo" as the first part of the fetch
    branches = branches/*:refs/remotes/*
    tags = tags/*:refs/remotes/tags/*

Doing that will make git’s “trunk” branch track trunk/foo/ on your server rather than just trunk/, which is probably what you want. If you want to track other projects in the tree, it’s probably better to git-svn init another directory. Update: Oops, I forgot to thank Mark Rowe for help with this. Thanks Mark!

As an aside, while I believe that distributed version control systems look like a great future for open-source projects, it’s interesting that DVCS clients are now starting to support Subversion, which now forms some form of lowest common denominator. (I’d call it the FAT32 of revision control systems, but that’d be a bit unkind… worse-is-better, perhaps?) Apart from the more “official” clients such as command-line svn and TortoiseSVN, it’s also supported by svk, Git, Bazaar, Mercurial, and some great other GUI clients on Mac OS X and Windows. Perhaps Subversion will become a de-facto repository format that everyone else can push and pull between, since it has the widest range of client choice.

For Mac developers in Australia, I’ll be speaking at the inaugural conference of DevWorld 2008, which will be held from September 29-30 this year in Melbourne. You can check out the full list of sessions; I’ll be giving the very last talk on that page: The Business of Development.

Coding is just one part of what makes a great product, but there’s always so much else to do and learn. So, what can you do to help ship a great product—besides coding—if you’re primarily a developer? In this talk, learn about important commercial and business issues that you, as a coder, can help to define and shape in your company, such as licensing and registration keys, adopting new technologies, software updates, handling support, your website, and crash reports.

Note that DevWorld 2008 is unfortunately only open to staff and students at an Australian university (“AUC member university”, to be exact), so unless you’re a student right now at one of those Unis, you’ll have to miss out on this incredibly exciting opportunity to hear me talk at you for an hour (snort). I hear the story behind this is that if this year’s DevWorld is successful, next year’s will be a more standard open conference. Anyway, hopefully catch some of you there in September!

The Mac Developer Network features an excellent series of podcasts aimed at both veteran Mac developers and those new to the platform who are interested in developing for the Mac. If you’re a current Mac coder and haven’t seen them yet, be sure to check them out. I’ve been listening to the podcasts for a long time, and they’re always both informative and entertaining. (Infotainment, baby.)

Well, in yet another case of “Wow, do I really sound like that?”, I became a guest on The Mac Developer Roundtable episode #11, along with Marcus Zarra, Jonathan Dann, Bill Dudney, and our always-eloquent and delightfully British host, Scotty. The primary topic was Xcode 3.1, but we also chatted about the iPhone NDA (c’mon Apple, lift it already!) and… Fortran. I think I even managed to sneak in the words “Haskell” and “Visual Studio” in there, which no doubt left the other show guests questioning my sanity. I do look forward to Fortran support in Xcode 4.0.

It was actually a small miracle that I managed to be on the show at all. Not only was the podcast recording scheduled at the ungodly time of 4am on a Saturday morning in Australian east-coast time, but I was also in transit from Sydney to the amazing alpine village of Dinner Plain the day before the recording took place. While Dinner Plain is a truly extraordinary village that boasts magnificent ski lodges and some of the best restaurants I’ve ever had the pleasure of eating at, it’s also rather… rural. The resident population is somewhere around 100, the supermarket doesn’t even sell a wine bottle opener that doesn’t suck, and Vodafone has zero phone reception there. So, it was to my great surprise that I could get ADSL hooked up to the lodge there, which was done an entire two days before the recording. Of course, since no ADSL installation ever goes smoothly, I was on the phone to iPrimus tech support¹ at 10pm on Friday night, 6 hours before the recording was due to start. All that effort for the privilege of being able to drag my sleepy ass out of bed a few hours later, for the joy of talking to other Mac geeks about our beloved profession. But, I gotta say, being able to hold an international conference call over the Intertubes from a tiny little village at 4am in the morning, when snow is falling all around you… I do love technology.

Of course, since I haven’t actually listened to the episode yet, maybe it’s all a load of bollocks and I sound like a retarded hobbit on speed. Hopefully not, though. Enjoy!

¹ Hey, I like Internode and Westnet as much as every other Australian tech geeks, but they didn’t service that area, unfortunately.

I’ve given a few talks so far this year, which I’ve been kinda slack about and haven’t put up any slides for yet. So, if you’re one of the zero people who’ve been eagerly awaiting my incredibly astute and sexy opinions, I guess today’s your lucky day, punk!

Earlier this year, on January 2, 2008, Earth Time, I gave a talk at Kiwi Foo Camp in New Zealand, also known as Baa Camp. (Harhar, foo, baa, get it?) The talk was titled “Towards the Massive Media Matrix”, with the MMM in the title being a pun on the whole WWW three-letter acronym thing. (Credit for the MMM acronym should go to Silvia Pfeiffer and Conrad Parker, who phrased the term about eight years ago :). The talk was about the importance of free and open standards on the Web, what’s wrong with the current status quo about Web video basically being Flash video, and the complications involved in trying to find a solution that satisfies everyone. I’m happy to announce that the slides for the talk are now available for download; you can also grab the details off my talks page.

A bit later this year in March, Manuel Chakravarty and I were invited to the fp-syd functional programming user group in Sydney, to give a talk about… monads! As in, that scary Haskell thing. We understand that writing a monad tutorial seems to be a rite of passage for all Haskell programmers and was thus stereotypical of the “Haskell guys” in the group to give a talk about, but the talk seemed to be well-received.

Manuel gave a general introduction to monads: what they are, how to use them, and why they’re actually a good thing rather than simply another hoop you have to jump through if you just want to do some simple I/O in Haskell. I focused on a practical use case of monads that didn’t involve I/O (OMG!), giving a walkthrough on how to use Haskell’s excellent Parsec library to perform parsing tasks, and why you’d want to use it instead of writing a recursive descent parser yourself, or resort to the insanity of using lex and yacc. I was flattered to find out that after my talk, Ben Leppmeier rewrote the parser for DDC (the Disciplined Disciple Compiler) to use Parsec, rather than his old system of Alex and Happy (Haskell’s equivalents of lex and yacc). So, I guess I managed to make a good impression with at least one of our audience members, which gave me a nice warm fuzzy feeling.

You can find both Manuel’s and my slides online at the Google Groups files page for fp-syd, or you can download the slides directly from my own site. Enjoy.

Finally, during my three-week journey to the USA last month in June, I somehow got roped into giving a talk at Galois Inc. in Portland, about pretty much whatever I wanted. Since the audience was, once again, a Haskell and functional programming crowd, I of course chose to give a talk about an object-oriented language instead: Objective-C, the lingua franca of Mac OS X development.

If you’re a programming language geek and don’t know much about Objective-C, the talk should hopefully interest you. Objective-C is a very practical programming language that has a number of interesting features from a language point of view, such as opt-in garbage collection, and a hybrid of a dynamically typed runtime system with static type checking. If you’re a Mac OS X developer, there’s some stuff there about the internals of the Objective-C object and runtime system, and a few slides about higher-order messaging, which brings much of the expressive power of higher-order functions in other programming languages to Objective-C. Of course, if you’re a Mac OS X developer and a programming language geek, well, this should be right up your alley :). Once again, you can download the slides directly, or off my talks page.

Two years ago, I had a wonderful job working on a truly excellent piece of software named cineSync. It had the somewhat simple but cheery job of playing back movies in sync across different computers, letting people write notes about particular movie frames and scribbling drawings on them. (As you can imagine, many of the drawings that we produced when testing cineSync weren’t really fit for public consumption.) While it sounds like a simple idea, oh boy did it make some people’s lives a lot easier and a lot less stressful. People used to do crazy things like fly from city to city just to be the same room with another guy for 30 minutes to talk about a video that they were producing; sometimes they’d be flying two or three times per week just to do this. Now, they just fire up cineSync instead and get stuff done in 30 minutes, instead of 30 minutes and an extra eight hours of travelling. cineSync made the time, cost and stress savings probably an order of magnitude or two better. As a result, I have immense pride and joy in saying that it’s being used on virtually every single Hollywood movie out there today (yep, even Iron Man). So, hell of a cool project to work on? Tick ✓.

Plus, it was practically a dream coding job when it came to programming languages and technologies. My day job consisted of programming with Mac OS X’s Cocoa, the most elegant framework I’ve ever had the pleasure of using, and working with one of the best C++ cross-platform code bases I’ve seen. I also did extensive hacking in Erlang for the server code, so I got paid to play with one of my favourite functional programming languages, which some people spend their entire life wishing for. And I got schooled in just so much stuff: wielding C++ right, designing network protocols, learning about software process, business practices… so, geek nirvana? Tick ✓.

The ticks go on: great workplace ✓; fantastic people to work with ✓; being privy to the latest movie gossip because we were co-located with one of Australia’s premiere visual effects company ✓; sane working hours ✓; being located in Surry Hills and sampling Crown St for lunch nearly every day ✓; having the luxury of working at home and at cafés far too often ✓. So, since it was all going so well, I had decided that it was obviously time to make a life a lot harder, so I resigned, set up my own little software consulting company, and start working on Mac shareware full-time.

Outside of the day job on cineSync, I was doing some coding on a cute little program to build websites named RapidWeaver. RapidWeaver’s kinda like Dreamweaver, but a lot more simple (and hopefully just as powerful), and it’s not stupidly priced. Or, it’s kinda like iWeb, but a lot more powerful, with hopefully most of the simplicity. I first encountered RapidWeaver as a normal customer and paid my $40 for it since I thought it was a great little program, but after writing a little plugin for it, I took on some coding tasks.

And you know what? The code base sucked. The process sucked. Every task I had to do was a chore. When I started, there wasn’t even a revision control system in place: developers would commit their changes by emailing entire source code files or zip archives to each other. There was no formal bug tracker. Not a day went by when I shook my fist, lo, with great anger, and thunder and lightning appeared. RapidWeaver’s code base had evolved since version 1.0 from nearly a decade before, written by multiple contractors with nobody being an overall custodian of the code, and it showed. I saw methods that were over thousand lines long, multithreaded bugs that would make Baby Jesus cry, method names that were prefixed with with Java-style global package namespacing (yes, we have method names called com_rwrp_currentlySelectedPage), block nesting that got so bad that I once counted thirteen tabs before the actual line of code started, dozens of lines of commented-out code, classes that had more than a hundred and twenty instance variables, etc, etc. Definitely no tick ✗.

But the code—just like PHP—didn’t matter, because the product just plain rocked. (Hey, I did pay $40 for it, which surprised me quite a lot because I moved to the Mac from the Linux world, and sneered off most things at the time that cost more than $0.) Despite being a tangled maze of twisty paths, the code worked. I was determined to make the product rock more. After meeting the RapidWeaver folks at WWDC 2007, I decided to take the plunge and see how it’d go full-time. So, we worked, and we worked hard. RapidWeaver 3.5 was released two years ago, in June 2006, followed by 3.5.1. 3.6 followed in May 2007, followed by a slew of upgrades: 3.6.1, 3.6.2, 3.6.3… all the way up to 3.6.7. Slowly but surely, the product improved. On the 3rd of August 2007, we created the branch for RapidWeaver 3.7, which we didn’t realise yet was going to be such a major release that it eventually became 4.0.

And over time, it slowly dawned on me just how many users we had. A product that I initially thought had a few thousand users was much closer to about 100,000 users. I realised I was working on something that was going to affect a lot of people, so when we decided to call it version 4.0, I was a little nervous. I stared at the code base and it stared back at me; was it really possible ship a major new revision of a product and add features to it, and maintain my sanity?

I decided in my naïvety to refactor a huge bunch of things. I held conference calls with other developers to talk about what needed to change in our plugin API, and how I was going to redo half of the internals so it wouldn’t suck anymore. Heads nodded; I was happy. After about two weeks of being pleased with myself and ripping up many of our central classes, reality set in as I realised that I was very far behind on implementing all the new features, because those two weeks were spent on nothing else but refactoring. After doing time estimation on all the tasks we had planned out for 4.0 and realising that we were about within one day of the target date, I realised we were completely screwed, because nobody sane does time estimation for software without multiplying the total estimate by about 1.5-2x longer. 4.0 was going to take twice as long as we thought it would, and since the feature list was not fixed, it was going to take even longer than that.

So, the refactoring work was dropped, and we concentrated on adding the new required features, and porting the bugfixes from the 3.6 versions to 4.0. So, now we ended up with half-refactored code, which is arguably just as bad as no refactored code. All the best-laid plans that I had to clean up the code base went south, as we soldiered on towards feature completion for 4.0, because we simply didn’t have the time. I ended up working literally up until the last hour to get 4.0 to code completion state, and made some executive decisions to pull some features that were just too unstable in their current state. Quick Look support was pulled an hour and a half before the release as we kept finding and fixing bugs with it that crashed RapidWeaver while saving a document, which was a sure-fire way to lose customers. Ultimately, pulling Quick Look was the correct decision. (Don’t worry guys, it’ll be back in 4.0.1, without any of that crashing-on-save shenanigans.)

So, last Thursday, it became reality: RapidWeaver 4.0 shipped out the door. While I was fighting against the code, Dan, Aron, Nik and Ben were revamping the website, which now absolutely bloody gorgeous, all the while handling the litany of support requests and being their usual easygoing sociable selves on the Realmac forums. I was rather nervous about the release: did we, and our brave beta testers, catch all the show-stopper bugs? The good news is that it seems to be mostly OK so far, although no software is ever perfect, so there’s no doubt we’ll be releasing 4.0.1 soon (if only to re-add Quick Look support).

A day after the release, it slowly dawned on me that the code for 4.0 was basically my baby. Sure, I’d worked on RapidWeaver 3.5 and 3.6 and was the lead coder for that, but the 3.5 and 3.6 goals were much more modest than 4.0. We certainly had other developers work on 4.0 (kudos to Kevin and Josh), but if I had a bad coding day, the code basically didn’t move. So all the blood, sweat and tears that went into making 4.0 was more-or-less my pride and my responsibility. (Code-wise, at least.)

If there’s a point to this story, I guess that’d be it: take pride and responsibility in what you do, and love your work. The 4.0 code base still sucks, sitting there sniggering at me in its half-refactored state, but we’ve finally suffered the consequences of its legacy design for long enough that we have no choice but to give it a makeover with a vengeance for the next major release. Sooner or later, everyone pays the bad code debt.

So, it’s going to be a lot more hard work to 4.1, as 4.1 becomes the release that we all really wanted 4.0 to be. But I wouldn’t trade this job for pretty much anything else in this world right now, because it’s a great product loved by a lot of customers, and making RapidWeaver better isn’t just a job anymore, it’s a need. We love this program, and we wanna make it so good that you’ll just have to buy the thing if you own a Mac. One day, I’m sure I’ll move on from RapidWeaver to other hopefully great things, but right now, I can’t imagine doing anything else. We’ve come a long way from RapidWeaver 3.5 in the past two years, and I look forward to the long road ahead for RapidWeaver 5. Tick ✓.

[Sorry if you get this post twice—let’s say that our internal builds of RapidWeaver 4.0 are still a little buggy, and I needed to re-post this ;)]

Xcode, Apple’s IDE for Mac OS X, has this neat ability to perform distributed compilations across multiple computers. The goal, of course, is to cut down on the build time. If you’re sitting at a desktop on a local network and have a Mac or two to spare, distributed builds obviously make a lot of sense: there’s a lot of untapped power that could be harnessed to speed up your build. However, there’s another scenario where distributed builds can help, and that’s if you work mainly off a laptop and occasionally join a network that has a few other Macs around. When your laptop’s offline, you can perform a distributed build with just your laptop; when your laptop’s connected to a few other Macs, they can join in the build and speed it up.

There’s one problem with idea, though, which is that distributed builds add overhead. I had a strong suspicion that a distributed build with only the local machine was a significant amount slower than a simple individual build. Since it’s all talk unless you have benchmarks, lo and behold, a few benchmarks later, I proved my suspicion right.

• Individual build: 4:50.6 (first run), 4:51.7 (second run)
• Shared network build with local machine only: 6:16.3 (first run), 6:16.3 (second run)

This was a realistic benchmark: it was a full build of RapidWeaver including all its sub-project dependencies and core plugins. The host machine is a 2GHz MacBook with 2GB of RAM. The build process includes a typical number of non-compilation phases, such running a shell script or two (which takes a few seconds), copying files to the final application bundle, etc. So, for a typical Mac desktop application project like RapidWeaver, turning on shared network builds without any extra hosts evokes a pretty hefty speed penalty: ~30% in my case. Ouch. You don’t want to leave shared network builds on when your laptop disconnects from the network. To add to the punishment, Xcode will recompile everything from scratch if you switch from individual builds to distributed builds (and vice versa), so flipping the switch when you disconnect from a network or reconnect to it is going to require a full rebuild.

Of course, there’s no point to using distributed builds if there’s only one machine participating. So, what happens when we add a 2.4GHz 20” Aluminium Intel iMac with 2GB of RAM, via Gigabit Ethernet? Unfortunately, not much:

• Individual build: 4:50.6 (first run), 4:51.7 (second run)
• Shared network build with local machine + 2.4GHz iMac: 4:46.6 (first run), 4:46.6 (second run)

You shave an entire four seconds off the build time by getting a 2.4GHz iMac to help out a 2GHz MacBook. A 1% speed increase isn’t very close to the 40% build time reduction that you’re probably hoping for. Sure, a 2.4GHz iMac is not exactly a build farm, but you’d hope for something a little better than a 1% speed improvement by doubling the horsepower, no? Gustafson’s Law strikes again: parallelism is hard, news at 11.

I also timed Xcode’s dedicated network builds (which are a little different from its shared network builds), but buggered if I know where I put the results for that. I vaguely remember that dedicated network builds was very similar to shared network builds with my two hosts, but my memory’s hazy.

So, lesson #1: there’s no point using distributed builds unless there’s usually at least one machine available to help out, otherwise your builds are just going to slow down. Lesson #2: you need to add a significant amount more CPUs to save a significant amount of time with distributed builds. A single 2.4GHz iMac doesn’t appear to help much. I’m guessing that adding a quad-core or eight-core Mac Pro to the build will help. Maybe 10 × 2GHz Intel Mac minis will help, but I’d run some benchmarks on that setup before buying a cute Mac mini build farm — perhaps the overhead of distributing the build to ten other machines is going to nullify any timing advantage you’d get from throwing another 20GHz of processors into the mix.

If you love programming, and especially if you love programming languages, there’s an episode of the Software Engineering Radio podcast that has a fantastic interview with Dick Gabriel, titled “Dick Gabriel on Lisp”. If you don’t know who Gabriel is, he’s arguably one of the more important programming language people around, is one of the founding fathers of XEmacs (neé Lucid Emacs), wrote the famous Worse is Better essay (along with a pretty cool book that I’ll personally recommend), and also gave one of the most surreal and brilliant keynotes that I’ve ever heard that received a standing ovation at HoPL III and OOPSLA.

The episode’s about fifty minutes long, and Gabriel talks about a lot more than just Lisp in the interview: among other things, he gives some major insight into the essence of object-oriented message-passing, how functions are objects and objects are functions, what continuations are, metacircularity, and the relationship between XML and S-expressions (and why XML is just a glorified half-assed version of Lisp). There’s also some great stories in the interview for computing historians: how the Common Lisp Object System was initially inspired by Scheme and the original Actor language (yep, “actors” as in “Erlang processes”), what AI research was like in the 1960s and ’70s, and the story of how John McCarthy and his students implemented the first Lisp interpreter in one night.

A wonderful interview, and well worth listening to if programming languages is your shindig.

I found this short article about law and code on builderAU rather interesting. The money quotes are the first and last paragraphs:

Technology has outpaced the legal system’s ability to regulate its use in matters of privacy and fair use rights, said Kirby… “We are moving to a point in the world where more and more law will be expressed in its effective way, not in terms of statutes solidly enacted by the parliament… but in the technology itself—code,” said Kirby.

I think that’s a great quote, and it shows that Justice Kirby has a pretty solid understanding of what code is, how it interacts with law, and that the USA’s Digital Millennium Copyright Act (DMCA)—and Australia’s Digital Agenda Act—are dangerous things. (I do think that the builderAU article emphasis on Google and Yahoo being the two culprits seem odd, although it’s hard to say this without listening to Kirby’s original speech.) I’ve always been a fan of Justice Kirby, and it’s nice to know that somebody-on-high understands that code-as-law is a problem, and it’s a complex one.

Haskell magician Don Stewart echoes my own opinion on lines of code in his Haskell Workshop demo on xmonad:

A couple of nice refactorings happened when we found data structures that fit better, and you dramatically drop down in the number of lines of code. So we use lines of code as a bit of a heuristic for working out when code sucks. If something gets really big, it probably needs to be rewritten.

I’m staring at a 60,000 line code base right now that I’m positive could be under 30,000 lines of code if it had a good rewri… erm, refactoring. Sometimes when you can’t figure out what’s going on in a function that’s a thousand lines long, the best solution is to rewrite the thing in a hundred lines instead. (And that time, I really did mean rewrite, not refactor.)

Update: Steve Yegge writes a good essay about code size, and believes that “the worst thing that can happen to a code base is size”. (If only he applied that principle to his blog posts as well…)

Reg Braithwaite has said very eloquently something I’ve been meaning to express for a long time:

When someone says something outrageous, like “f*ck compilers and their false sense of security”, it is not important whether I happen to think that programming languages with strong, expressive type systems are valuable (hint: I do). What is important is to look at this statement and ask yourself: Is there just one thing in there, one kernel of wisdom that I can extract and use to be a better programmer?

I wrote about geek culture and criticism earlier, but Braithwaite knocks it up a notch and hammers the point home in a single paragraph. To use an analogy, being a good geek is like being a good partner in a relationship… step one: listen. Step two: empathise. (Step three: profit!)

Quoteth Manuel Chakravarty:

Dungeons and Dragons is the C++ of role-playing games.

It seems that I’ve been interviewed by BuilderAU about The Importance of Being Erlang. (And I quite like the pun, even if it wasn’t my idea.) Feedback on it is always welcome, of course—shoot me an email if you have any questions.

And yeah, I know I haven’t been blogging in nearly three months; I’ve been secretly working on an image editor in my spare time. (Sorry, that was a small Mac developer in-joke.) I’ve got nearly two dozen articles that are half-written here that I’ve been meaning to finish. However, there’s nothing like being sick to make you catch up on reading books and updating your blog. (… and play more Bioshock, even if it basically just a normal-mapped phong-shaded bastard child of System Shock 2. All hail SHODAN!)

Mike Melanson—a primary author of the Linux Flash plugin, xine, ffmpeg, and a general crazy-good multimedia hacker—on the state of Linux Audio APIs:

There are 2 primary methods of sending audio data to a DAC under Linux: OSS and ALSA. OSS came first; ALSA supplanted OSS. Despite this, and as stated above, there are numerous different ways to do the DAC send. There are libraries and frameworks that live at a higher level than OSS and ALSA. In the end, they all just send the data out through OSS or ALSA.

The zaniest part is that some of these higher level libraries can call each other, sometimes in a circular manner. Library A supports sending audio through both OSS and ALSA, and library B does the same. But then library A also has a wrapper to send audio through library B and vice versa. For that matter, OSS and ALSA both have emulation layers for each other. I took the time to map out all of the various libraries that I know of that operate on Linux and are capable of nudging that PCM data out to a DAC:

Barry Schwartz would be shaking his head, methinks. And yes, I’m well aware of efforts to unify this mess. That doesn’t excuse that this jungle has been the state of Linux audio for the past ten years. I love the comments too: instead of admitting how dumbass this is, they give suggestions for using even more APIs (“try KDE4’s Phonon! That’ll fix everything!”)… totally missing the amusing irony, and also missing the point that Mike needs something that works on as many Linux distributions as possible.

What’s happened to Kathy Sierra, and what she wrote about angry and negative people, inspired me to write a bit, so let me indulge myself a little. I live in the computing community, with other like-minded geeks. Computing geeks have a (deserved) reputation for being a little negative. This is not without cause: there’s a lot of things wrong in our world. A lot of the technology we use and rely on every day is brittle and breaks often, and as Simon Peyton-Jones says, we’re quite often trying to build buildings out of bananas. Sure, you can do it, but it’s painful, and it’s downright depressing when the bricks are just over there, just out of reach. Our efforts for releasing software is often met with never-ending bug reports and crash reports, and it’s quite sobering looking at our task trackers.

It’s impossible to resist ragging on something or abusing something. This is part of geek computing culture. We have to work with a lot of crap, so it’s easy to be critical and complain about everything around you. However, from this day forward, I’m going to try to at least make any criticism not totally destructive. (I don’t think I’m vitriolic, mind you, but I’ll make a conscious effort to be more constructive now.) Wrap it up in some humour; offer some suggestions or alternatives. Resist using inflammatory language as much as you can when you’re personally attacked, or simply walk away from it. Re-read everything you write and think “Is what I’m writing simply making people more bitter? Is it actually worth somebody’s time to read this?”

Be more gentle with your language and kinder to your fellow netizens. Don’t participate in flamewars. Don’t join the mob mentality and rail on Microsoft or C++ or Ruby or Apple or Linux when everyone else does. (You’re meant to be a scientist after all, aren’t you?) Break away from that self-reinforcing sub-culture that often comes with being a geek.

Now that I’ve got that off my chest, back to work!

Here are a short list of things that possess more elegance than Movable Type’s export file format:

• XML,
• SMTP,
• the C string API,
• the C multibyte string API (mbsinit, wcrtomb, mbsnrtowcs, etc),
• the C++ grammar specification,
• C++ template error messages,
• the BIND zone file format,
• Bourne shell parameter expansion involving spaces,
• PHP,
• CSV,
• GNU libtool,
• wGetGUI,
• POSIX regular expressions,
• MPEG-7,
• the mplayer code base,
• the Cisco VPN client,
• the ld(1) manpage on the UNIX system of your choice,
• the sudoers(5) manpage,
• Makefiles generated by GNU autogoats,
• Eric S. Raymond,
• ICCCM,
• pretty much everything.

Feel free to extend this list in the comments.

I always used to get confused between UCS-2 and UTF-16. Which one’s the fixed-width encoding and which one’s the variable-length encoding that supports surrogate pairs?

Then, I learnt this simple little mnemonic: you know that UTF-8 is variable-length encoded¹. UTF = variable-length. Therefore UTF-16 is variable-length encoded, and therefore UCS-2 is fixed-length encoded. (Just don’t extend this mnemonic to UTF-32.)

Just thought I’d pass that trick on.

¹ I’m assuming you know what UTF-8 is, anyway. If you don’t, and you’re a programmer, you should probably learn sometime…

I was chatting to a mate of mine about a remarkable book that I found the other day:

One of the greatest intellectuals of our century writes about computing systems and fundamental aspects of the brain. What’s there not to like here? I’m only halfway through the book, and it’s already got so much worthy material in it that I will recommend it to any other computing folks. It’s worth it for the Foreword alone.

Alas, von Neumann passed on a while ago. Right after our discussion, I find out that John Backus passed away last Saturday. Phil Windley comments that “Computer Science has always been a discipline where the founders were still around. That’s changing.”

Arguably computing’s most famous face-person right now is Bill Gates. I don’t see Gates being famous as bad: after all, the guy is a multi-billionaire, which naturally gives him a little bit of a reputation, and his philanthropic acts are to be admired even if one despises his business tactics. However, what does the greater public know about our real heroes? Alan Turing? John von Neumann? Grace Hopper? Alan Kay? John Backus? Donald Knuth? Edsgar Dijkstra? Doug Engelbart?

I remember when John Shepherd taught me CS2041 at university, he spent 5 minutes at the start of each lecture talking about “famous geeks” and what they did for our industry. We need to educate ourselves as an industry and learn and respect what these folks did; go back to our roots; respect our elders. I’d wager that a lot more mathematicians know about Bertrand Russell and Leonhard Euler than self-described programmers and computing geeks know about Alan Turing and Edsgar Dijkstra.

If you’re a programmer (or even if you’re not), go to Wikipedia’s list of Turing Award winners sometime and just start reading about people you don’t know, starting with the man who the Turing award’s named after. (I’m ashamed to say that I only recognise a mere 22 out of 51 names of the Turing Award winners, and I’m scared to think that I’m probably doing a lot better than a lot of other folks.)

I understand that people such as Knuth and Dijkstra made specialised contributions to our field, and that the greater public won’t particularly care for them (in the same way that a lot of the general public won’t know about Bertrand Russell or even Euler, but they’re known by pretty much every single mathematician). However, there are lots of computing legends who we can talk about at dinner with all our non-geek friends and family. Go get Doug Engelbart’s Mother of All Demos or Ivan Sutherland’s Sketchpad demo and show it to your friends. Tell your family about the role that Turing played in World War II, and the amusing story of Grace Hopper finding an actual bug inside her computer.

As Dijkstra said, “in their capacity as a tool, computers will be but a ripple on the surface of our culture. In their capacity as intellectual challenge, they are without precedent in the cultural history of mankind.” Computing is one of the most important things to emerge from this entire century. I hope that in twenty years’ time, at least Alan Turing will be a household name alongside Bill Gates. Let’s do our part to contribute to that.

I like Objective-C. It’s a nice language. However, having to write accessor methods all day is boring, error-prone, and a pain in the ass:

I mean, c’mon. This is Objective-C we’re talking about, not Java or C++. However, until Objective-C 2.0’s property support hits the streets (which, unfortunately, will only be supported on Mac OS X 10.5 and later as far as I know), you really have to write these dumb-ass accessors to, well, access properties in your objects correctly. You don’t need to write accessors thanks to the magic of Cocoa’s Key-Value Coding, but it just feels wrong to access instance variables using strings as keys. I mean, ugh—one typo in the string and you’ve got yourself a problem. Death to dynamic typing when it’s totally unnecessary.

As such, I got totally fed up with this and wrote a little script to generate accessor methods. I’m normally not a fan of code generation, but in this case, the code generation’s actually designed to be one-shot, and it doesn’t alter the ever-picky build process. It’s meant to be used in Xcode, although you can run it via the commandline too if you like.

Given the following input:

It will spit out the following:

There’s a couple of dandy features in the script that I find useful, all of which are demonstrated in the above output:

1. It will detect whether your instance variables start with a vowel, and write out anInteger instead of aInteger as the parameter names for the methods.
2. It will copy rather than retain value classes such as NSStrings and NSNumbers, as God intended.
3. For all you gumbies who prefix your instance variables with a leading underscore, it will correctly recognise that and not prefix your accessor methods with an underscore.¹
4. IBOutlet and a few other type qualifiers (__weak, __strong, volatile etc) are ignored correctly.
5. It will emit Xcode-specific #pragma mark places to make the method navigator control a little more useful.
6. It will emit Xcode-specific %%%{PBXSelection}%%% markers so that the accessor methods meant to go into your .m implementation file are automatically selected, ready for a cut-and-paste.

Download the objc-make-accessors script and throw it into your “~/Library/Application Support/Apple/Developer Tools/Scripts” folder. If you don’t have one yet:

Done. You should now have a Scripts menu in Xcode with a new menu item named “IVars to Accessor Methods”. Have fun.

¹ Note that older versions of the Cocoa Coding Guidelines specified that prefixing instance variables with underscores is an Apple-only convention and you should not do this in your own classes. Now the guidelines just don’t mention anything about this issue, but I still dislike it because putting underscores every time you access an instance variable really lowers code readability.

To all the Mac users out there: would you be interested in a Cocoa Users’ Group in Sydney? If so, please drop me an email—my address is at the bottom of the page—and if there’s enough numbers, perhaps we can organise something. The idea’s to have a local forum for geekupsmeetups, random presentations, mailing lists, and all that sort of fun stuff.

Oh yeah, and please also let me know your self-described level of expertise: none, novice, intermediate, expert.

(For those who closely track the Cocoa scene in Australia: yep, this is the same call for interest that Duncan Campbell has initiated.)

It’s rare that I find a good, balanced article on the (dis)advantages of static vs dynamic typing, mostly because people on each side are too religious (or perhaps just stubborn) to see the benefits of the other. Stevey’s blog rant comparing static vs dynamic typing is one of the most balanced ones that I’ve seen, even if I think half his other blog posts are on crack.

I lean toward pretty far toward the static typing end of the spectrum, but I also think that dynamic typing not only has its uses, but is absolutely required in some applications. One of my favourite programming languages is Objective-C, which seems to be quite unique in its approach: the runtime system is dynamically typed, but you get a reasonable amount of static checking at compile-time by using type annotations on variables. (Survey question: do you know of any Objective-C programmers who simply use id types everywhere, rather than the more specific types such as NSWindow* and NSArray*? Yeah, I didn’t think so.) Note that I think Objective-C could do with a more a powerful type system: some sort of parameterised type system similar in syntax to C++ templates/Java generics/C# generics would be really useful just for the purposes of compile-time checking, even though it’s all dynamically typed at runtime.

One common thread in both Stevey’s rant and what I’ve personally experienced is that dynamic typing is the way to go when your program really needs to be extensible: if you have any sort of plugin architecture or long-lived servers with network protocols that evolve (hello Erlang), it’s really a lot more productive to use a dynamic typing system. However, I get annoyed every time I do some coding in Python or Erlang: it seems that 50% of the errors I make are type errors. While I certainly don’t believe that static type systems guarantee that “if it compiles, it works”, it’s foolish to say that they don’t help catch a large class of errors (especially if your type system’s as powerful as Haskell’s or Ocaml’s), and it’s also foolish to say that unit tests are a replacement for a type system.

So, the question I want to ask is: why are programming languages today so polarised into either the static and dynamic camp? The only languages I know of that strive to accommodate for the benefits of both are Objective-C, Perl (though I’d say that writing Perl without use strict is an exercise in pain, since its only three types are scalars, arrays and hashes), and (gasp) Visual Basic. Programming languages and programming language research should’ve looked at integrating static and dynamic typing a long time ago. C’mon guys, it’s obvious to me that both approaches have good things to offer, and I ain’t that smart. I think a big reason they haven’t is largely for religious reasons, because people on both sides are too blinded to even attempt to see each other’s point of view. How many academic papers have there been that address this question?

I hope that in five years, we’ll at least have one mainstream programming language that we can write production desktop and server applications in, that offer the benefits of both static and dynamic typing. (Somebody shoot me, now I’m actually agreeing with Erik Meijer.) Perhaps a good start is for the current generation of programmers to actually admit that both approaches have their merit, rather than simply get defensive whenever one system is critiqued. It was proved a long time ago that dynamic typing is simply staged type inference and can be subsumed as part of a good-enough static type system: point to static typing. However, dynamic typing is also essential for distributed programming and extensibility. Point to dynamic typing. Get over it, type zealots.

P.S. Google Fight reckons that dynamic typing beats static typing. C’mon Haskell and C++ guys, unite! You’re on the same side! Down with those Pythonistas and Rubymongers! And, uhh, down with Smalltalk and LISP too, even though they rule! (Now I’m just confusing myself.)

While learning about the immaculate DeathStation 9000, I came across the homepage of Armed Response Technologies. That page nearly had me snort coffee out of my nose on my beautiful new 30” LCD monitor. Make very sure you see their bloopers page.

(This is quite possibly the best thing to ever come out of having so much stupidit… uhh, I mean, undefined behaviour, in C.)

If you haven’t had much experience with the wonderful world of multithreading and don’t yet believe that threads are evil¹, Edward A. Lee has an excellent essay named “The Problem with Threads”, which challenges you to solve a simple problem: write a thread-safe Observer design pattern in Java. Good luck. (Non-Java users who scoff at Java will often fare even worse, since Java is one of the few languages with some measure of in-built concurrency control primitives—even if those primitives still suck.)

His paper’s one of the best introductory essays I’ve read about the problems with shared state concurrency. (I call it an essay since it really reads a lot more like an essay than a research paper. If you’re afraid of academia and its usual jargon and formal style, don’t be: this paper’s an easy read.) For those who aren’t afraid of a bit of formal theory and maths, he presents a simple, convincing explanation of why multithreading is an inherently complex problem, using the good ol’ explanation of computational interleavings of sets of states.

His essay covers far more than just the problem of inherent complexity, however: Lee then discusses how bad threading actually is in practice, along with some software engineering improvements such as OpenMP, Tony Hoare’s idea of Communicating Sequential Processes², Software Transactional Memory, and Actor-style languages such as Erlang. Most interestingly, he discusses why programming languages aimed at concurrency, such as Erlang, won’t succeed in the main marketplace.

Of course, how can you refuse to read a paper that has quotes such as these?

• “… a folk definition of insanity is to do the same thing over and over again and to expect the results to be different. By this definition, we in fact require that programmers of multithreaded systems be insane. Were they sane, they could not understand their programs.”
• “I conjecture that most multi-threaded general-purpose applications are, in fact, so full of concurrency bugs that as multi-core architectures become commonplace, these bugs will begin to show up as system failures. This scenario is bleak for computer vendors: their next generation of machines will become widely known as the ones on which many programs crash.”
• “Syntactically, threads are either a minor extension to these languages (as in Java) or just an external library. Semantically, of course, they rhoroughly disrupt the essential determinism of the languages. Regrettably, programmers seem to be more guided by syntax than semantics.”
• “… non-trivial multi-threaded programs are incomprehensible to humans. It is true that the programming model can be improved through the use of design patterns, better granularity of atomicity (e.g. transactions), improved languages, and formal methods. However, these techniques merely chip away at the unnecessarily enormous non-determinism of the threading model. The model remains intrinsically intractable.” (Does that “intractable” word remind you of anyone else?)
• “… adherents to… [a programming] language are viewed as traitors if they succumb to the use of another language. Language wars are religious wars, and few of these religions are polytheistic.”

If you’re a programmer and aren’t convinced yet that shared-state concurrency is evil, please, read the paper. Please? Think of the future. Think of your children.

¹ Of course, any non-trivial exposure to multithreading automatically implies that you understand they are evil, so the latter part of that expression is somewhat superfluous.

² Yep, that Tony Hoare—you know, the guy who invented Quicksort?

svk—a distributed Subversion client by Chia Liang Kao and company—is now an essential part of my daily workflow. I’ve been using it almost exclusively for the past year on the main projects that I work with, and it’s fantastic being able to code when you’re on the road and do offline commits, syncing back to the main tree when you’re back online. Users of other distributed revision control systems do, of course, get these benefits, but svk’s ability to work with existing Subversion repositories is the killer reason to use it. (I’m aware that Bazaar has some Subversion integration now, but it’s still considered alpha, whereas svk has been very solid for a long time now.)

The ability to do local checkins with a distributed revision control client has a nice side-effect: commits are fast. They typically take around two seconds with svk. A checkin from a non-distributed revision control client such as Subversion requires a round-trip to the server. This isn’t too bad on a LAN, but even for a small commit, it can take more than 10 or 15 seconds to a server on the Internet. The key point is that these fast commits have a psychological effect: having short commit times encourages you to commit very regularly. I’ve found that since I’ve switched to svk, not only can I commit offline, but I commit much more often: sometimes half a dozen times inside of 10 minutes. (svk’s other cool feature of dropping files from the commit by deleting them from the commit message also helps a lot here.) Regular commits are always better than irregular commits, because either (1) you’re committing small patches that are easily reversible, and/or (2) you’re working very prolifically. Both of these are a win!

So, if you’re still using Subversion, try svk out just to get the benefits of this and its other nifty features. The svk documentation is quite sparse, but there are some excellent tutorials that are floating around the ‘net.

If you are:

1. a Mac OS X user,
2. a coder, web developer, or hacker of some sort (C/C++, Cocoa, Python, Ruby, Web dude(tte),

I just found a mighty good use of Quicksilver that I wanted to share—getting at reference documentation when you’re coding. Now, I hit Cmd-Space to invoke Quicksilver, and then type in, say:

• NSString to bring up the Cocoa Foundation documentation about the NSString class,
• sscanf to bring up the sscanf(3) manpage, or
• dict to bring up the Erlang dict module.

Nice, no?

Quicksilver uses a number of catalogs to create its big list of items that you can search. For example, there’s a Quicksilver plugin that catalogs applications on your hard disk, so that when you start typing iTun, Quicksilver searches the applications catalog to find iTunes. If you start typing in a person’s name, the Address Book plugin has catalogued your Address Book and will search on that.

The neat thing is, you can add your own custom catalogs pretty easily, by indexing text files and HTML files. Quicksilver comes with a File and Folder scanner plugin that you can use to index reference documentation. Adding a custom catalog is easy:

1. go to Quicksilver’s Preferences,
2. select the Catalog tab,
3. select the Custom catalog type on the left-hand pane,
4. click the + button and pick “File & Folder Scanner”,
5. add the text/HTML file to be used as a catalog, and
6. set the “Include Contents” pop-up button in the Inspector pane (the i button in the bottom-right hand corner) to HTML Links or Text Lines, as appropriate.

You probably want to also set Quicksilver to rescan your catalog once in a while: I’ve set mine to rescan every hour.

Here’s some example usage scenarios:

• Cocoa developers: Add /Developer/ADC Reference Library/documentation/Cocoa/Reference/Foundation/ObjC_classic/index.html as a catalog to index the Foundation kit classes, and /Developer/ADC Reference Library/documentation/Cocoa/Reference/ApplicationKit/ObjC_classic/index.html to index the AppKit classes. Now, you can type any class name (such as NSString or NSWindow) at the Quicksilver prompt to immediately bring up the Cocoa documentation in your preferred Web browser.
• UNIX developers: Install Bwana, which provides a kickass HTML version of your system’s manpages. (It dynamically generates them on demand, so don’t worry, it won’t take up another 100MB of space.) An an aside, Bwana’s the very first manpage viewer I’ve liked besides running man(1) itself in a shell. Run Bwana once and hit the Index button so it can index all the manpages. Add ~/Library/Caches/Bwana/manindex-.html to your Quicksilver catalog, and all of your manpages will now be indexed. Bam, type in printf at a Quicksilver prompt, and behold as all those formatting specifiers you forgot magically appear in your Web browser.
• Erlang developers: Download the Erlang documentation and keep it somewhere on your local hard disk. Add the doc/index.html file as a catalog, and bam, type in dict to bring up the Erlang dict module functions in your Web browser.

Of course, this works for any HTML documentation, so whether you’re a Java, Python, Ruby, C++ weenie or whatever, just grab some HTML documentation and let Quicksilver index it for you. Bam! (With kudos to Zapp Brannigan, my hero.)

I came across the following quote about threads while reading The Evolution of Lua:

… we did not (and still do not) believe in the standard multithreading model, which is preemptive concurrency with shared memory: we still think that no one can write correct programs in a language where ‘a=a+1’ is not deterministic.

That is quite possibly the best one-line summary I have read about why shared-state concurrency is evil. Just say no!

An engaging quote from Paul Johnson, from the January 9, 2007 issue of Haskell Weekly News:

Mutable state is actually another form of manual memory management: every time you over-write a value you are making a decision that the old value is now garbage, regardless of what other part of the program might have been using it.

My little theory: there is no reason to ever change the value of a variable except for efficiency. Instead, make a new immutable variable based on the old value, which gives you freedom to name your new variable to better describe what it does. My C and C++ code is littered with const almost everywhere, and it helps enormously when you look back at the code a month later to figure out what it’s doing.

And, just to throw in a little more Haskell evangelism from someone else who’s merrily had their brain reconfigured to to see the awe of the lambda calculus:

So far I’ve written about 300 LOC replacing about 1500 LOC of a system written in Perl… The thing that totally, utterly blows my mind is that I’ve done all this without any loops and using only 3 conditional statements. (One if and two case, if it matters. And I don’t mean this in the cheap sense that Haskell doesn’t have any looping constructs and so I’m writing recursive functions instead, which everyone knows is the same thing. There is no explicit recursion in my code. I’m just flabbergasted.

I found a pretty interesting paper the other day about Failure-Oblivious Computing. The idea is simple: when a program encounters an error, simply have your runtime return some garbage value instead of crashing, throwing an exception, or go into error-handling mode.

If you’re a programmer, this suggestion will likely cause you to recoil in horror because the very idea that your functions will be getting back undefined values seems contradictory to everything we’ve been taught. However, it’s hard argue with the results: the authors tested eight fairly well known programs, from mail user agents to Apache and Samba, and in every case the failure-oblivious version arguably did the right thing — and did a better job — than the ‘safe’ versions that would throw an exception or shutdown in a controlled manner when they hit unexpected territory. Read the paper if you’re doubtful about this.

This idea is somewhat in opposition to the Erlang philosophy of Let it crash. However, in both these scenarios, the underlying motivation is the same: large complex systems will inevitably have bugs, and both philosophies not only plan for it, but code to ensure that the system as a whole keeps running in the face of serious errors.

It’s quite easy to react emotionally to these ideas and say that it’s all just too dangerous and unpredictable — coders have always had it hammered into them to check for error values and exceptional conditions. However, there’s also something to be said about the brittleness of software vs more organic systems: the latter will often recover successfully in the face of unexpected conditions, whereas software will simply break. Failure-oblivious computing may not be the answer, but it’s a pretty good first research step. It would be an interesting follow-up experiment to modify the runtimes of the dynamic languages such as Python and Ruby and make them return sentry values instead of throwing exceptions. How many dynamic programs would continue to run successfully rather than die with some weird programmer-centric error?

Joe Armstrong, the Main Man behind Erlang, shows how to write an FTP client in Erlang in a couple of lines of code. Some of my own points:

• People on his blog who comment that “what operating system comes without an FTP server?” are totally missing the point, which is that Erlang makes it easy to write network programs. How many lines of code do you think it would have taken to do that in C? That file transfer program he wrote is less than half a dozen lines.

• Yes, it’s not a real FTP client, duh. Erlang does actually come with an FTP module which you can use in your own program, though.

Namespaces vs Static Methods

In C++, if you want a bunch of plain functions that you can put into a library, you can either do this:

class UtilityFunctions
{
public:
  static void Foo();
  static void Bar();
};

or this:

namespace UtilityFunctions
{
  void Foo();
  void Bar();
}

Either way, you call the functions with the same syntax:

void SomeFunction()
{
  UtilityFunctions::Foo();
  UtilityFunctions::Bar();
}

So, what’s the difference between using a class full of static methods vs using namespaces? While I’m sure there’s plenty of differences about how they’re implemented internally, the big difference is that namespaces are extensible, while a class full of static methods isn’t. That means that in another file, you can just add more functions to the namespace:

namespace UtilityFunctions
{
  void Baz();
  void Quux();
}

but you can’t add more static methods to the class.

The Expression Problem

This is rather handy, since it means that C++ can quite nicely solve the expression problem, a problem that plagues nearly all modern programming languages, even ones with expressive type systems such as Haskell and Ocaml. (Note that the expression problem specifically concerns statically typed languages, so while there are solutions for it in modern dynamic languages such as Python, Perl and Ruby, they don’t really count since they’re not statically typed. It’s easy to solve the problem if you’re prepared to throw away all notions of type safety at compile time!)

The expression problem is basically this:

• You want to able to add new data types, and have existing functions work on those data types. This is easy in an object-oriented language: just subclass the existing data types, and all existing functions will work just fine with your new subclass. This is (very) hard in a functional language, because if you add new cases to a variant type, you must update every pattern match to work properly with the new case.
• However, you also want to add new functions that will work with those data types. This is very easy in a functional language: just define a new function. This is solvable in an object-oriented language, but isn’t very elegant, because most object-oriented languages can’t add new methods to existing classes (Objective-C is a notable exception; see the footnote below). This means that you are forced to declare a function when you really wanted to add a new method to the class, or, in OO languages which don’t even have normal functions (e.g. Java), you have to declare a totally new class with a static method instead. Ouch.

However, since C++ provides (1) objects, (2) normal functions, and (3) extensible namespaces, this means that you solve the expression problem nicely using the above techniques. It still requires some forethought by planning to use a namespace for sets of functions that you expect to be able to extend, but it’s an elegant solution to the expression problem, as opposed to no solution or a crappy solution. (And I thought I’d never say “C++” and “elegant” in the same sentence).

Extensible Object Factories

There’s one more piece to the puzzle, however. If you’re making your own new subclass, you also want to be able to create objects of that class. However, what if you only know the exact type of object you want to create at runtime? Use a runtime-extensible object factory instead.

Let’s say you’re designing an extensible image library, to read a bunch of image formats such as JPG, PNG, GIF, etc. You can design an abstract Image class that a JPGImage, PNGImage, or GIFImage can then subclass. If you want a uniform interface to create such images, you can use the factory design pattern:

Image* image = ImageFactory::CreateImage("/path/to/image");

In this case, CreateImage() is a factory function that will return you an appropriate Image* object. (Well, if you’re really disciplined, you’ll be using the wonderful boost::shared_ptr rather than an evil raw pointer, but I digress…)

Now, let’s say you want to make this library extensible, so users could add in their own JPEG2000Image subclass outside of your library. How, then, do you let the CreateImage() function know about the user’s new JPEG2000Image class?

There are plenty of solutions to this, but since this is meant to be a didactic post, here’s a cheap’n’cheery solution for you: use a data structure to hold references to functions that are responsible for creating each different type of JPGImage, PNGImage, etc. You can then add to the data structure at runtime (usually called registering the creation function). The CreateImage() function can then look up the registered functions in the extensible data structure and call the appropriate function, no matter whether the image class is provided by your library (JPG, PNG), or by the user (JPEG2000).

If you put together all the above techniques, what you have is a fully extensible framework. A user can:

• register new data types with the library at run-time,
• use exactly the same interface to create new types of objects,
• add new functions to your library without the awkwardness of using a different namespace,
• … and still retain complete static type safety.

Footnote: Objective-C has a particularly interesting solution to the expression problem, via categories, which are statically type-checked despite Objective-C being a “dynamic” language.

I recently encountered a paper written by William Cook about a mysterious little programming language that even many programming languages researchers don’t know about: AppleScript. Yep, that’d be the humble, notoriously English-like Mac scripting language that’s renown to be slow and annoying more than anything else. The paper is a fascinating look at the history of AppleScript, and details many insights and innovations that were largely unknown. Here’s some things that I was pleasantly surprised about.

Cook had never used a Mac before he was employed to work on AppleScript: in fact, he had a very strong UNIX background, and had a great amount of experience with UNIX shell scripting. So, one can instantly dismiss the notion that whoever designed AppleScript had “no idea about the elegance of interoperating UNIX tools”: a remark that I’m sure many would have made about the language (myself included). Cook even remarks that Apple’s Automator tool, introduced in Mac OS 10.4 Tiger, was quite similar to UNIX pipes:

The most interesting thing about Automator is that each action has an input and an output, much like a command in a Unix pipe. The resulting model is quite intuitive and easy to use for simple automation tasks.

More on UNIX pipes, he writes that

the sed stream editor can create the customized text file, which is then piped into the mail command for delivery. This new script can be saved as a mail-merge command, which is now available for manual execution or invocation from other scripts.

He then continues with something seemingly obvious, but is nevertheless something I have never thought about UNIX scripts:

One appealing aspect of this model is its compositionality [emphasis mine]: users can create new commands that are invoked in the same way as built-in commands.”

Indeed! In a way, the ability to save executable shell scripts is the equivalent of writing a named function to denote function composition in a functional programming language: it enables that composed code to be re-used and re-executed. It’s no coincidence that the Haskell scripts used in Don Stewart’s h4sh project are semantically quite similar to their equivalent Bourne shell scripts, where Haskell’s laziness emulates the blocking nature of pipes.

More on UNIX: Cook later writes that

A second side effect of pervasive scripting is uniform access to all system data. With Unix, access to information in a machine is idiosyncratic, in the sense that one program was used to list print jobs, another to list users, another for files, and another for hardware configuration. I envisioned a way in which all these different kinds of information could be referenced uniformly… A uniform naming model allows every piece of information anywhere in the system, be it an application or the operating system, to be accessed and updated uniformly.

The uniform naming model sounds eerily familiar who had read Hans Reiser’s white paper about unified namespaces. Has the UNIX world recognised yet just how powerful a unified namespace can be? (For all the warts of the Windows registry, providing the one structure for manipulating configuration data can be a huge benefit.)

Cook was also quite aware of formal programming language theory and other advanced programming languages: his Ph.D thesis was in fact on “A Denotational Semantics of Inheritance”, and his biography includes papers on subtyping and F-bounded polymorphism. Scratch another urban myth that AppleScript was designed by someone who had no idea about programming language theory. He makes references to Self and Common LISP as design influences when talking about AppleScript’s design. However,

No formal semantics was created for the language, despite an awareness that such tools existed. One reason was that only one person on the team was familiar with these tools, so writing a formal semantics would not be an effective means of communication… Sketches of a formal semantics were developed, but the primary guidance for language design came from solving practical problems and user studies, rather than a-priori formal analysis.

(There’s some interesting notes regarding user studies later in this post.) Speaking of programming language influences,

HyperCard, originally released in 1987, was the most direct influence on AppleScript.

Ah, HyperCard… I still remember writing little programs on HyperCard stacks in high school programming camps when I was a young(er) lad. It’s undoubtedly one of the great programming environment gems of the late 80s (and was enormously accessible to kids at the same time), but that’s an entire story unto itself…

The Dylan programming language is also mentioned at one point, as part of an Apple project to create a new Macintosh development environment (named Family Farm). ICFPers will be familiar with Dylan since it’s consistently in the top places for the judge’s prize each year; if you’re not familiar with it, think of it as Common LISP with a saner syntax.

AppleScript also had a different approach to inter-appication messaging. Due to a design flaw in the classic MacOS, AppleScript had to package as much information into its inter-application data-passing as possible, because context switches between applications on early MacOS systems were very costly:

A fine-grained communication model, at the level of individual procedure or method calls between remote objects, would be far too slow… it would take several seconds to perform this script if every method call required a remote message and process switch. As a result, traditional RPC and CORBA were not appropriate… For many years I believed that COM and CORBA would beat the AppleScript communication model in the long run. However, COM and CORBA are now being overwhelmed by web services, which are loosely coupled and use large granularity objects.

Web Services, eh? Later in the paper, Cook mentions:

There may also be lessons from AppleScript for the design of web services. Both are loosely coupled and support large-granularity communication. Apple Events data descriptors are similar to XML, in that they describe arbitrary labeled tree structures without fixed semantics. AppleScript terminologies are similar to web service description language (WDSL) files. One difference is that AppleScript includes a standard query model for identifying remote objects. A similar approach could be useful for web services.

As for interesting programming language features,

AppleScript also supports objects and a simple transaction mechanism.

A transaction mechanism? Nice. When was the last time you saw a transaction mechanism built into a programming language (besides SQL)? Speaking of SQL and domain-specific languages, do you like embedded domain-specific languages, as is the vogue in the programming language research community these days? Well, AppleScript did it over a decade ago:

The AppleScript parser integrates the terminology of applications with its built-in language constructs. For example, when targeting the Microsoft Excel application, spreadsheet terms are known by the parser—nouns like cell and formula, and verbs like recalculate. The statement tell application “Excel” introduces a block in which the Excel terminology is available.

Plus, if you’ve ever toyed with the idea of a programming language that could be written with different syntaxes, AppleScript beat you to that idea as well (and actually implemented it, although see the caveat later in this note):

A dialect defines a presentation for the internal language. Dialects contain lexing and parsing tables, and printing routines. A script can be presented using any dialect—so a script written using the English dialect can be viewed in Japanese… Apple developed dialects for Japanese and French. A “professional” dialect which resembled Java was created but not released… There are numerous difficulties in parsing a programming language that resembles a natural language. For example, Japanese does not have explicit separation between words. This is not a problem for language keywords and names from the terminology, but special conventions were required to recognize user-defined identifiers. Other languages have complex conjugation and agreement rules, which are difficult to implement. Nonetheless, the internal representation of AppleScript and the terminology resources contain information to support these features. A terminology can define names as plural or masculine/feminine, and this information can be used by the custom parser in a dialect.

Jesus, support for masculine and feminine nouns in a programming language? Hell yeah, check this out:

How cool is that? Unfortunately, Apple dropped support for multiple dialects in 1998:

The experiment in designing a language that resembled natural languages (English and Japanese) was not successful. It was assume that scripts should be presented in “natural language” so that average people could read and write them. This lead to the invention of multi-token keywords and the ability to disambiguate tokens without spaces for Japanese Kanji. In the end the syntactic variations and flexibility did more to confuse programmers than help them out. The main problem is that AppleScript only appears to be a natural language on the surface. In fact is an artificial language, like any other programming language… It is very easy to read AppleScript, but quite hard to write it… When writing programs or scripts, users prefer a more conventional programming language structure. Later versions of AppleScript dropped support for dialects. In hindsight, we believe that AppleScript should have adopted the Programmerís Dialect that was developed but never shipped.

A sad end to a truly innovative language feature—even if the feature didn’t work out. I wonder how much more AppleScript would be respected by programmers if it did use a more conventional programming language syntax rather than being based on English. Cook seems to share these sentiments: he states in the closing paragraph to the paper that

Many of the current problems in AppleScript can be traced to the use of syntax based on natural language; however, the ability to create pluggable dialects may provide a solution in the future, by creating a new syntax based on more conventional programming language styles.

Indeed, it’s possible to write Perl and Python code right now to construct and send AppleEvents. Some of you will know that AppleScript is just one of the languages supported by the Open Scripting Architecture (OSA) present in Mac OS X. The story leading to this though, is rather interesting:

In February of 1992, just before the first AppleScript alpha release, Dave Winer convinced Apple management that having one scripting language would not be good for the Macintosh… Dave had created an alternative scripting language, called Frontier… when Dave complained that the impending release of AppleScript was interfering with his product, Apple decided the AppleScript should be opened up to multiple scripting languages. The AppleScript team modified the OSA APIs so that they could be implemented by multiple scripting systems, not just AppleScript… Frontier, created by Dave Winer, is a complete scripting and application development environment. It is also available as an Open Scripting component. Dave went on to participate in the design of web services and SOAP. Tcl, JavaScript, Python and Perl have also been packaged as Open Scripting components.

Well done, Dave!

As for AppleScript’s actual development, there’s an interesting reference to a SubEthaEdit/Gobby/Wiki-like tool that was used for their internal documentation:

The team made extensive use of a nearly collaborative document management/writing tool called Instant Update. It was used in a very wiki-like fashion, a living document constantly updated with the current design. Instant Update provides a shared space of multiple documents that could be viewed and edited simultaneously by any number of users. Each userís text was color-coded and time-stamped.

And also,

Mitch worked during the entire project to provide that documentation, and in the process managed to be a significant communication point for the entire team.

Interesting that their main documentation writer was the communication point for the team, no?

Finally, AppleScript went through usability testing, a practice practically unheard of for programming languages. (Perl 6’s apocalypses and exegeses are probably the closest thing that I know of to getting feedback from users, as opposed to the language designers or committee simply deciding on everything without feedback from their actual userbase!)

Following Appleís standard practice, we user-tested the language in a variety of ways. We identified novice users and asked them “what do you think this script does?” As an example, it turned out that the average user thought that after the command put x into y the variable x no longer retained its old value. The language was changed to use copy x into y instead.

Even more interesting:

We also conducted interviews and a round-table discussion about what kind of functionality users would like to see in the system.

The survey questions looked like this:

The other survey questions in the paper were even more interesting; I’ve omitted them in this article due to lack of space.

So, those were the interesting points that I picked up when I read the paper. I encourage you to read it if you’re interested in programming languages: AppleScript’s focus on pragmatics, ease of use for non-programmers, and its role in a very heavily-based GUI environment makes it a very interesting case study. Thankfully, many Mac OS X applications are now scriptable so that fluent users can automate them effectively with Automator, AppleScript, or even Perl, Python and Ruby and the UNIX shell these days.

Honestly, the more I discover about Apple’s development technologies, the more impressed I am with their technological prowess and know-how: Cocoa, Carbon, CoreFoundation, CoreVideo, QuickTime, vecLib and Accelerate, CoreAudio, CoreData, DiscRecording, SyncServices, Quartz, FSEvents, WebKit, Core Animation, IOKit… their developer frameworks are, for the most part, superbly architectured, layered, and implemented. I used to view AppleScript as a little hack that Apple brought to the table to satisfy the Mac OS X power users, but reading the paper has changed my opinion on that. I now view AppleScript in the same way as QuickTime: incredible architecture and power, with an outside interface that’s draconian and slightly evil because it’s been around and largely unchanged for 15 freaking years.

OK, this is both ridiculous and cool at the same time. I need to write code for Mac OS X, Windows and Linux for work, and I like to work offline at cafes since I actually tend to get more work done when I’m not on the Internet (totally amazing, I know). This presents two problems:

1. I need a laptop that will run Windows, Mac OS X and Linux.
2. I need to work offline when we use Subversion for our revision control system at work.

Solving problem #1 turns out to be quite easy: get a MacBook (Pro), and run Mac OS X on it. Our server runs fine on Darwin (Mac OS X’s UNIX layer), and I can always run Windows and Linux with Parallels Desktop if I need to.

For serious Windows coding and testing, though, I actually need to boot into real Windows from time to time (since the program I work on, cineSync, requires decent video card support, which Parallels doesn’t virtualise very well yet). Again, no problem: use Apple’s Boot Camp to boot into Windows XP. Ah, but our server requires a UNIX environment and won’t run under Windows! Again, no problem: just install coLinux, a not very well known but truly awesome port of the Linux kernel that runs as a process on Windows at blazing speeds (with full networking support!).

Problem #2 — working offline with Subversion — is also easily solved. Download and install svk, and bingo, you have a fully distributed Subversion repository. Hack offline, commit your changes offline, and push them back to the master repository when you’re back online. Done.

Where it starts to get stupid is when I want to:

• check in changes locally to the SVK repository on my laptop when I’m on Mac OS X…
• and use those changes from the Mac partition’s SVK repository while I’m booted in Windows.

Stumped, eh? Not quite! Simply:

• purchase one copy of MacDrive 6, which lets you read Mac OS X’s HFS+ partitions from Windows XP,
• install SVK for Windows, and
• set the %SVKROOT% environment variable in Windows to point to my home directory on the Mac partition.

Boom! I get full access to my local SVK repository from Windows, can commit back to it, and push those changes back to our main Subversion server whenever I get my lazy cafe-loving arse back online. So now, I can code up and commit changes for both Windows and the Mac while accessing a local test server when I’m totally offline. Beautiful!

But, the thing is… I’m using svk — a distributed front-end to a non-distributed revision control system — on a MacBook Pro running Windows XP — a machine intended to run Mac OS X — while Windows is merrily accessing my Mac HFS+ partition, and oh yeah, I need to run our server in Linux, which is actually coLinux running in Windows… which is, again, running on Mac. If I said this a year ago, people would have given me a crazy look. (Then again, I suppose I’m saying it today and people still give me crazy looks.) Somehow, somewhere, I think this is somewhat toward the evil end of the scale.

A web comic about everybody’s favourite open-source evangelists: Richard Stallman, Linus Torvalds, and, of course, Eric Raymond. (Occasionally even starring John Dvorak).

(Kudos to Chuck for the heads-up.)

Maybe this is why there’s a crazy-good bunch of functional programmers in Japan:

That’s right, it’s Mount Lambda baby.

(Props to kfish for the link.)

There’s a draft paper named “A History of Haskell” on the Haskell Wiki right now, which will be submitted to the History of Programming Languages conference (HoPL) in 2007. I wasn’t even aware there was a conference dedicated to programming language history, and the idea is a great one: after reading the paper, I’ll be tracking down papers about other significant languages, such as LISP, Smalltalk and C++. (Hey, whatever your opinion of C++, it seems to be universally respected that Stroustrup’s The Design and Evolution of C++ is a title worthy of being on every serious programmer’s bookshelf. Seeing why a language is the way it is today is a huge key in understanding how to wield it.) The paper’s a long read (~40 pages) but a very easy read (no Greek in the entire thing!), and it’s fascinating hearing the inside stories from some obviously incredibly clever people. I’m also glad the authors mixed in some humour into the paper, which abounds in the Haskell community: not enough papers dare to inject (and successfully deliver) humour into their materials.

So, here’s some of my commentary on quotes that I particularly liked from the paper. First, it looks like the authors of the paper agree with me about Haskell’s problem with unpredictable performance:

The extreme sensitivity of Haskellís space use to evaluation order is a two-edged sword. Tiny changes—the addition or removal of a in one placeócan dramatically change space requirements. On the one hand, it is very hard for programmers to anticipate their programís space behaviour and place calls of correctly when the program is first written… As designers who believe in reasoning, we are a little ashamed that reasoning about space use in Haskell is so intractable.

Mind you, they do also point out something I didn’t mention in my writings at all:

On the other hand, given sufficiently good profiling information, space performance can be improved dramatically by very small changes in just the right place—without changing the overall structure of the program… Yet Haskell encourages programmers—even forces them—to forget space optimisation until after the code is written, profiled, and the major space leaks found, and at that point puts powerful tools at the programmerís disposal to fix them. Maybe this is nothing to be ashamed of, after all.

Note that Don Stewart’s incredible Data.ByteString library has pretty much nailed the performance gap between Haskell and C for string processing and binary I/O, which is one area where Haskell was notoriously weak at. (Haskell’s also risen to the top of the heap in the Great Language Shootout as well, largely thanks to Don’s efforts.)

There’s one paragraph on the great importance of profiling tools in finding the cause of performance problems, in one case leading to an absolutely amazing reduction in heap usage:

… there was no practical way of finding the causes of space leaks in large programs. Runciman and Wakeling developed a profiler that could display a graph of heap contents over time, classified by the function that allocated the data, the top-level constructor of the data, or even combinations of the two (for example, ìshow the allocating functions of all the cons cells in the heap over the entire program runî). The detailed information now available enabled lazy programmers to make dramatic improvements to space efficiency: as the first case study, Runciman and Wakeling reduced the peak space requirements of a clausification program for propositional logic by two orders of magnitude, from 1.3 megabytes to only 10K (Runciman and Wakeling, 1993)… A further extension introduced retainer profiling, which could explain why data was not garbage collected… With information at this level of detail, Runciman and Rˆjemo were able to improve the peak space requirements of their clausify program to less than 1K—three orders of magnitude better than the original version. They also achieved a factor of two improvement in the compiler itself, which had already been optimised using their earlier tools.

And, two paragraphs that lend more credence to the idea that Haskell really does lead to less lines of code:

Darcs was originally written in C++ but, as Roundy puts it, “after working on it for a while I had an essentially solid mass of bugs” (Stosberg, 2005). He came across Haskell and, after a few experiments in 2002, rewrote Darcs in Haskell. Four years later, the source code is still a relatively compact 28,000 lines of literate Haskell (thus including the source for the 100 page manual). Roundy reports that some developers now are learning Haskell specifically in order to contribute to darcs.

One of these programmers was Audrey Tang. She came across Darcs, spent a month learning Haskell, and jumped from there to Pierceís book Types and Programming Languages (Pierce, 2002). The book suggests implementing a toy language as an exercise, so Audrey picked Perl 6. At the time there were no implementations of Perl 6, at least partly because it is a ferociously difficult language to implement. Audrey started her project on 1 February 2005. A year later there were 200 developers contributing to it; perhaps amazingly (considering this number) the compiler is only 18,000 lines of Haskell (including comments) (Tang, 2005). Pugs makes heavy use of parser combinators (to support a dynamically-changable parser), and several more sophisticated Haskell idioms, including GADTs (Section 6.6) and delimited continuations (Dybvig et al., 2005).

For verification and comparison, here’s a very rough lines-of-code count generated using David A. Wheeler’s ‘sloccount’ for Darcs, Bazaar-NG, Mercurial, Arch and Subversion. Note that I excluded test cases, supporting libraries and other non-essentials, which can be massive (e.g. total omission of hackerlab for Arch, which comprises another 50,000 lines, and the Apache Portable Runtime for Subversion, which is another 85,000 lines):

• Darcs: 21,135 lines
• Bazaar-NG: 47,084 lines
• Mercurial: 20,537 lines
• Arch: 48,639 lines (~100,000 with hackerlab)
• Subversion: 98,736 lines (~185,000 with APR and APR-util)

So Darcs and Mercurial are pretty similar, Bazaar-NG and Arch are nearly around the same size code base now (and it’s written in Python rather than C!), and Subversion is, well, a crapload bigger than all the others.

Plus, I didn’t realise that Pugs was a mere 18,000 lines of code, which is quite amazing. I’m not sure whether I’m more impressed by that figure, or that Erlang’s incredible Mnesia distributed database is a mere ~30,000 lines of code…

Let’s say you’re a Mac OS X developer, and you have the following scenario:

• You have an application that’s required to start up without a particular Mac OS X class, framework or function definition, because it may not be installed yet on the user’s system, or they’re running an older version of Mac OS X that doesn’t have the relevant library installed. (Note that this requirement may only be there so that you can check for the presence of a particular framework, and throwing up a simple error message to the user when your application starts that tells the user to install the framework, rather than simply terminate with some obscure output to stderr.)
• On the other hand, your application also uses some features of the potentially missing class/framework/function on Mac OS X. This is normally pretty easy to do by using weak linking and checking for undefined functional calls (or using Objective-C’s -respondsToSelector method), except when…
• You need to subclass one of the Cocoa classes that may not be present on the user’s system.

The problem here is that if you subclass an existing class that may not be present on the user’s system, the Objective-C runtime terminates your application as it starts up, because it tries to look up the superclass of your subclass when your application launches, and then proceeds to panic when it can’t find the superclass. The poor user has no idea what has happened: all they see is your application’s icon bouncing in the dock for the short time before it quits.

Here’s some examples where I’ve needed to do this in real-life applications:

• You use Apple’s QTKit framework, and you’re subclassing one of the QTKit classes such as QTMovie or QTMovieView. QTKit is installed only if the user has QuickTime 7 or later installed, and you’d like to tell the user to install QuickTime 7 when the application starts up, rather than dying a usability-unfriendly death.
• You need to use all-mighty +poseAsClass: in a +load method to override the behaviour of existing class, but the class you’re posing as only exists on some versions of Mac OS X.

There are several potential solutions to this (skip past this paragraph if you just want a solution that works): the first one I thought of was to use a class handler callback, which gets called when the Objective-C runtime tries to lookup a class and can’t find it. The class handler callback should then be able to create a dummy superclass so that your subclass will successfully be loaded: as long as you don’t use the dummy superclass, your application should still work OK. Unfortunately this approach encountered SIGSEGVs and SIGBUSs, and I ended up giving up on it after half an hour of trying to figure out what was going on. Another method is to actually make your subclass a subclass of NSObject, and then try to detect whether the superclass exists at runtime and then swizzle your class object’s superclass pointer to the real superclass if it does. This causes major headaches though, since you can’t access your class’s instance variables easily (since the compiler thinks you’re inheriting from NSObject rather than the real superclass)… and it doesn’t work anyway, also evoking SIGSEGVs and SIGBUSs. One other possibility is to simply create a fake superclass with the same name as the real Objective-C class, and pray that the runtime choses the real superclass rather than your fake class if your application’s run on a system that does have the class.

The solution that I eventually settled on is far less fragile than all of the above suggestions, and is actually quite elegant: what you do is compile your subclass into a loadable bundle rather than the main application, detect for the presence of the superclass at runtime via NSClassFromString or objc_getClass, load up your bundle if it’s present, and finally call your class’s initialisers.

Practically, this means that you have to:

• add a new target to your project that’s a Cocoa loadable bundle,
• compile the relevant subclass’s source code files into the bundle rather than the main application,
• ensure that the bundle is copied to your application’s main bundle, and
• detect for the presence of the superclass at runtime, and if it’s present, load your bundle, and then initialise the classes in the bundle via the +initialize method.

Here’s some example code to load the bundle assuming it’s simply in the Resources/ directory of your application’s main bundle:

    NSString* pathToBundle = [[NSBundle mainBundle] pathForResource:@"MyExtraClasses"
                                                             ofType:@"bundle"];
    NSBundle* bundle = [NSBundle bundleWithPath:pathToBundle];
    
    Class myClass = [bundle classNamed:@"MyClass"];
    NSAssert(myClass != nil, @"Couldn't load MyClass");
    [myClass initialize];

You will also have to end up specifying using the -weak* parameters to the linker (such as -weak_framework or -weak-l) for your main application if you’re still using normal methods from that class. That’s about it though, and conceptually this technique is quite robust.

Credit goes to Josh Ferguson for suggesting this method, by the way, not me. I’m merely evangelising it…

Alastair Tse finally got fed up with Google Maps — despite having a Sydney development branch — not having Google Maps in Australia. As such, he’s put an incredible amount of work into fixing this anomaly, and announced his little Mashup Maps project yesterday. Nice work liquidx: that’ll be going on my browser toolbar indeed!

http://foldl.com/
http://foldr.com/

Scott Johnson has an excellent comment on the Lambda the Ultimate forums titled “Different levels of mutable state badness”:

The vestuble: Non-mutable state. Just so we have a frame of reference. (Some may argue that this is Heaven rather than the outermost circle of Hell, but in Heaven all the problems are already solved. :) )

1st circle: Mutable state which is not externally observable (given the programming model). Such things as variables cached in registers and other optimizations performed by the machine.

2nd circle: “Monotonic” mutable state. Discussed a bit in CTM, these correspond to variables which can be bound separately from their definition (but once bound cannot be re-bound), lazy evaluation, etc. In general, preserve referential transparency, and are well-behaved.

3rd circle: Linear mutable state. Mutable variables which are accessed from only one place; and generally aren’t subject to aliasing. Examples include local variables in functions (ignoring the issues of lexical closures which might alias such variables, and call-by-reference), “private” variables within objects, etc.

4th circle: Managed mutable state. State in a database or some other system which provides transaction semantics and other means of arbitrating access to the shared variables.

5th circle (getting hotter): Aliased mutable state. Mutable variables/objects which are “used” in numerous different contexts (and therefore aliased)—and thus frequently used as a backdoor communications channel (often unintentionally). Often described as a “feature” of certain OO languages (much the same way pointer arithmetic is trumpted as a feature of C).

6th circle (even hotter): Global (unmanaged) mutable state. As bad as the previous, but as the state is globally exported, you don’t know WHO might be messing with it, or where.

7th and 8th circles: Currently unoccupied, though I await suggestions. :) Feel free to interpose suggestsions above too, and we can demote intervening circles to fill in the gap.

9th circle: Concurrent mutable state. The obnoxious practice of mutating shared state from multiple threads of control, leading into a predictable cycle of race conditions, deadlocks, and other assorted misbehavior from which there is no return. And if a correct solution (for synchronization) is found for a given program, chances are any substantial change to the program will make it incorrect again. But you won’t find it, instead your customer will. Despite that, reams of code (and TONS of middleware) has been written to try and make this tractable. And don’t get me started on a certain programming language which starts with “J” that saw fit to make EVERY object have its very own monitor….

The traditional solution to providing a high-availibility Internet service is to throw a bunch of (preferably geographically diverse) servers together and set up a round-robin DNS record that will somewhat balance the load between them. However, if your Internet service supports real-time collaboration between users, as in the case of a bunch of clustered worldwide Jabber servers, a round-robin DNS solution doesn’t work very well, because it dramatically increases your server-to-server traffic as users will end up logging into different servers.

Assuming that scalability isn’t too much of a problem and that your main goal is high availability, what you really want is a failover queue of servers for a single DNS record: first, try server1; if that fails, try server2; if server2 fails, try server3, and so on…

The traditional solution for this is either (a) run your own DNS server and use BIND 9’s obscure rrset-order option to define a round-robin order, or, if you’re uncomfortable with doing that, outsource your DNS to a managed DNS hosting service that supports failover monitoring, such as ZoneEdit or PowerDNS, which can be expensive.

However, Horms suggested a brilliant little solution: use one of the many freely available dynamic dns services. Write a simple script to poll your servers in order, and update the dynamic DNS entry’s IP address to point to whatever the first server you’ve detected as online. You can still point users to the normal hostname in your domain, by adding a CNAME record that points to the hostname provided by the dynamic DNS service.

We’ve used this technique in practice for several weeks and it’s worked extremely well: so well, in fact, that we cancelled the outsourced DNS failover service that we had before, because it didn’t update as quickly or work as reliably as it does now. Writing the monitoring script is the hardest part of this solution, and that’s pretty easy: if you’re really curious, email me and I’ll be happy to lend the monitor script that we use.

I have the weirdest things in my .zshrc file sometimes…

~ % which -a makex0r
makex0r: aliased to make

Ever wanted to view the classes and methods in your code via FTP? If not, why not?

Paul Graham writes in his “Revenge of the Nerds” article:

… in the OO world you hear a good deal about “patterns”. I wonder if these patterns are not sometimes evidence of … the human compiler, at work. When I see patterns in my programs, I consider it a sign of trouble. The shape of a program should reflect only the problem it needs to solve. Any other regularity in the code is a sign, to me at least, that I’m using abstractions that aren’t powerful enough — often that I’m generating by hand the expansions of some macro that I need to write.

To quote part of the abstract from Arch D. Robinson’s awesome paper, The Impact of Economics on Compiler Optimization:

Compile-time program optimizations are similar to poetry: more are written than are actually published in commercial compilers. Hard economic reality is that many interesting optimizations have too narrow an audience to justify their cost in a general-purpose compiler, and custom compilers are too expensive to write. This has already happened accidentally for C++, albeit imperfectly, in the form of template metaprogramming.

In a nutshell, writing optimisations is hard. Often, it’s too much of an engineering effort to implement tons of optimisations in a production-quality compiler: the gains you see simply aren’t worth the amount of effort. I won’t ramble on about this, since that’s the focus of Robinson’s paper, and it’s an enlightening read if you’re interested in that topic. (It’s also an enlightening read of you’re wondering what all the fuss is about with C++ templates.) Related to Robison’s paper is a talk given by Bill Pugh, titled “Is Code Optimization Research Relevant?”. One standout slide from that talk is this one:

18 years from now, if we pull a Pentium III out of the deep freeze, apply our future compiler technology to SPECINT2000, and get an additional 2x speed improvement … I will be impressed/amazed.

And Bill is pretty much right. But I won’t talk about whether research on optimisations is relevant or not — again, have a browse of Bill’s talk if you want to debate that with him.

What I do want to talk about is that both Robinson’s paper and Pugh’s talk both hint at something which is never explicitly stated: the successful optimisations which have been done in the past few years are mostly domain-specific optimisations. These are optimisations which apply to only to a particular problem area, e.g. graphics (thus the word “domain” in domain-specific). Pugh gives the example that optimising matrix multiplication is quite successful: here, the domain that is being optimised is matrices, a well-defined and well-known area of maths. Robinson makes the point that C++ templates are successful because they can be used to create domain-specific optimisations, since they can be used to meta-program the compiler.

One interesting example of a domain-specific optimisation are the vector units on a modern desktop system: AltiVec on the PowerPC, the PlayStation 2’s Emotion Engine, MMX/SSE on Intel x86s. While they’re not part of the compiler, they are a perfect example of just how well you can optimise code when you start having domain-specific constructs available (in this case, vector operations). Modern-day programmable graphics cards such as the latest NVidias and ATI Radeons are proof that native language (and hardware) support for vectors can reap massive speed benefits, and IBM’s new Cell CPU begs for properly vectorised code to get any decent performance out of it. The point of all this is: if your programming language natively supports expressing the problem domain you want to solve, you can really optimise the hell out of it.

In the future, I hope that languages or compilers will enable us to easily write domain-specific optimisations, because language optimisation research — especially for imperative languages — simply aren’t going to give us that much of a speedup anymore. Look at the number of optimisation options in the gcc manpage and count how many of them will really give you a significant speedup. Beyond some basic, well-known optimisations, such as constant propagation and inlining, are the rest of those obscure optimisations really worthwhile? Is it worth it to put the engineering effort into those optimisations when you not only have to code them up, but also maintain them and make sure that they don’t cause optimised program to behave differently to non-optimised programs?

I’d rather that all that engineering effort be put into making the language and compiler more extensible, so that libraries can come bundled with their own optimisations that can be added to the compiler. This potentially gives a much greater speed increase. In low-level languages such as C, this doesn’t make such a big difference because you’re programming so close to the hardware (though it certainly can sometimes: observe the success of C++ templates). High-level languages that enable the programmer to more closely express the problem domain in the language, such as Python and Haskell, have much more to gain.

From an interview with Julian Seward, author of the superb Valgrind (as well as cacheprof, bzip2, and a co-author for the Glorious Glasgow Haskell Compiler: quite a remarkably productive fellow, huh?):

Valgrind is loaded with assertion checks and internal sanity checkers which periodically inspect critical data structures. These are permanently enabled. I don’t care if 5 percent or even 10 percent of the total run-time is spent in these checksóautomated debugging is the way to go. As a result, Valgrind almost never segfaultsóinstead it emits some kind of a useful error message before dying. That’s something I’m rather proud of.

Nice indeed; I wonder if programming languages of the future will be able to do automatic assertions of such data structures in their run-time systems. All you’d need is to annotate the structures with some simple boolean conditions, and the language can merrily check them whenever a garbage collection pass is executed (since programming languages of the future will all have automatic memory management, of course. Right? Helllllllo?)

And, one more little quote (sorry, I couldn’t resist):

Valgrind is only useful because C and C++ are such crappy programming languages.

A-men to that, Haskell brother. Snigger snigger snigger …

From Apple’s Universal Binary Programming Guidelines:

Note: The terms big-endian and little-endian come from Jonathan Swiftís eighteenth-century satire Gulliverís Travels. The subjects of the empire of Blefuscu were divided into two factions: those who ate eggs starting from the big end and those who ate eggs starting from the little end.

Good to see Apple addressing the important questions in their guides.

Ryan Gordon, the lone gunman who’s responsible for porting quite a number of Wintendo games to Linux and Mac OS X, was interviewed recently. He had this to say about coding for games:

None of the games are rewarding. Is that bad of me to say? Game development has nothing to do with quality and everything to do with shipping what you can get away with. That’s just how it is; I didn’t make this horrible world.

Nothing unexpected, I guess. I wonder how many fields haven’t succumbed to the “it’s all a matter of what you can get away with” mantra of quasi-engineering? Writing academic papers, maybe? Nahh …

If you’re a Unix hacker on Mac OS X, chances are you’ll be using a very large number of open-source projects that use GNU autotools: these are the projects that you typically compile with the ./configure script. It turns out that building a Mac OS X “Universal Binary” that runs on both PowerPC and Intel isn’t too hard at all, with the appropriate magic incantations to the ./configure script:

CFLAGS="-isysroot /Developer/SDKs/MacOSX10.4u.sdk -Wl,-syslibroot,/Developer/SDKs/MacOSX10.4u.sdk -arch i386 -arch ppc" \
./configure 

Notes about this:

• You will get a ton of warnings from the linker during the compile that the -syslibroot parameter was ignored since no linking was done. Just ignore them. (If you find out how to shut ld up, do email me!)
• You may need to pass the --disable-dependency-tracking to ./configure, especially for projects that use GNU libtool. Yeah, this means you won’t get proper dependency tracking for your project, so (just like the Universal Binary Programming Guidelines suggests) I’d suggest you compile a universal binary only when you build a proper release package.

Update: Note that this is merely a way to get autotools to build universal binaries. It definitely does not mean that your project will automagically work with on both PowerPC and x86. (In particular, you’ll have to change autoconf-supplied architecture and endian macros such as AC_C_BIGENDIAN: see the autoconf section of the Universal Binary Programming Guidelines for more details.)

Update (2): It seems that this technique has officially been sanctioned by Apple: technical note TN2137 uses the exact CFLAGS that I’ve described here.

Ars Technica has an new article (that Slashdot seemed to miss) titled A History of the GUI. The first couple of pages of the article are great, but unfortunately it soon degenerates into screenshots of various GUIs that were introduced in the late 1980s.

However, it does talk for nearly a full page about Doug Engelbart’s Mother of All Demos, given in 1968. As befits its name, Engelbart’s demo is one of the most important events to ever happen in the history of computing. It not only featured the first demonstration of the mouse, but also …

… featured hypertext linking, full-screen document editing, context-sensitive help, networked document collaboration, e-mail, instant messenging, even video conferencing!

Hypertext linking and networked document collaboration guys, in 1968. We still don’t have a decent networked document collaboration system today, bar wikis (which aren’t real-time), and SubEthaEdit (which is great, but is limited to plaintext, and only works on the Mac). Engelbart was doing stuff 37 years ago that we still haven’t managed to conquer today.

Anyway, to get to the point of this post, I really encourage you to check out the following two video recordings if you can make time for them — they’ve been lovingly digitized and preserved so that we can view them so many, many years later:

• Doug Engelbart’s 1968 Mother of All Demos
• Steve Jobs’s Unveiling of the Macintosh in 1984.

They’re absolutely amazing. So damn amazing, this will probably be the one and only time I’ll tell you to download and install RealPlayer just so you can view Doug’s 1968 demo. You can feel history in the making as you watch the videos, I kid you not. To some extent, I almost despise Kernighan and Ritchie for spawning a culture and mindset that ultimately won, despite being more mediocre. Where would we be today if the world had embraced Smalltalk instead? Ah, time to stop being sentimental and crank out more C code, so I don’t look like such a starry-eyed kid again …

Are you a totally k-rad coder who just can’t stop cutting code to spare time for those silly comments? Cenqua’s Commentator was made just for you:

The Commentator uses revolutionary real-time language processing to actually grok your code and add the necessary comments on the fly. No more doco to slow you down. Just install The Commentator and watch as your coding elegance is eloquently decorated with insightful, nuanced commentary … as you type. What’s more, The Commentator’s powerful Personality Controls allow you to tweak it’s output so completely that it’s as if The Commentator is speaking for you. In your voice. Explaining to those that need it, so that you can get on and get busy.

It’s worth checking out just for the personality controls screenshot. SCO or chicks indeed!

I’m frequently surprised whenever I see veteran coders whittling away in Windows using Courier New or some equally horrible monospace font. (Yeah, I know this is all subjective, so if you don’t like my opinions, go back to using Comic Sans MS, OK?) Considering how much you can stare at the screen all day if you’re a professional coder, a readable pleasant font could actually improve your productivity and lifestyle, in every Dilbertesque sense.

Windows actually comes with a great monospace font that unfortunately seems to be reserved for use by its console windows only. Macintosh folks have been lucky to have had an excellent monospace font (Monaco 9) since its inception in 1984, and UNIX/X11 people have been blessed with truly excellent monospace fonts (schumacher-clean and good ol’ fixed, whoever made that.)

So, if you’re never thought about your choice of a coding font, check out the following fonts which were made for heavy-duty programmers (complete with slashed zeros; long live the IBM PS/2!). Most of them are available for Windows, the Mac and Linux, too.

• ProFont, my current coding font of choice.
• Metrowerk’s MPW font (Mac OS X only).
• Triskweline
• Proggy Fonts

There’s been a reasonable amount of publicity about Guido van Rossum’s comments on the usefulness of the reduce function in Python, but there’s quite an interesting comment on Lambda the Ultimate about how reduce() in Python is quite, well, broken:

Heh. reduce() is broken in python (in that it’s not actually a fold function), so I don’t blame Guido for not being able to figure it out in his head. Rather than handling the zero- and one-element list cases properly, it (a) doesn’t take a basis element, (b) raises an error on empty lists and © RETURNS THE SINGLE ELEMENT WITHOUT CALLING A FUNCTION ON IT in the one-element case (true even in recursion). … The way it’s defined, reduce is not fold, it’s a broken fold.

Folding an empty list results in an error? If that is the case, well, it’s no wonder it wasn’t used in Python very much. I’d very much rather Python rip out a half-arsed fold function altogether rather than trying to make it semi-functional (pun intended). That only gives a bad impression about functional programming, and doesn’t benefit anyone. (Disclaimer: I haven’t double-checked the above claim myself, so I don’t know if what Jacob says it’s true. The Lambda the Ultimate folks usually have their heads screwed on very right when it comes to anything to do with programming language semantics, though …)

For the record, I also disagree with Guido’s assertions that map() and filter() should go away just because list comprehensions exist. map and filter have single purposes: to transform lists, and filter lists. Since list comprehensions can do the job of both map and filter, it’s not immediately obvious what they do, because they now give you more choice, and more choice means less immediate obviousness. If you see a map or filter, you know it’s just doing a list tranformation or a list filter, and that’s it. If you see a list comprehension, you have to read its innards to understand what it’s doing. Or (using Haskell syntax) do you really think [ x | x <- [1..10], isEven x ] more immediately obvious filter (isEven) [1..10]? Considering Python’s heavy emphasis on code readability, that sounds like a step backwards to me.

Update: As pointed out, if you use an initialiser with reduce(), you get sane behaviour back. That’s good. However, I find it a bit odd that an initialiser is optional, rather than mandatory. (It’s managed to fool at least one user into thinking fold is broken — how many more people had the same misconception?)

Update #2: Shane Stephens points out that the optional-initialiser-version of reduce() is actually quite useful. Rather than try to repeat it abysmally, I’ll just clag in a part of Shane’s email here:

… there’s a very good (but possibly non functional-programming-oriented) reason for the optional lack of a basis in python’s reduce function: sometimes you don’t WANT to run the function on a single element. A good example is concatenating strings: reduce(lambda a, b: a + ", " + b, some_array).

Indeed, this is 100% analagous to the foldl1 function in Haskell, which is the same as a fold, but doesn’t take an initialiser element. So, it looks like half of this article of mine is full of crap. :)

Coders of the world rejoice, for Martin Pool is building a distributed revision control system:

I am not working directly on Ubuntu, but rather on improving the tools used by open source developers inside and outside of Canonical. The charter is to build a distributed version-control system that open-source hackers will love to use.

Knowing Martin, this will have the usability of Subversion and Darcs, the algorithms of Arch, and the pure leetness of rsync. Beware, other RCS authors: your days are numbered!

Hmm, so Guido’s blogged even more about adding static typing to Python. I’m not sure if that’s a good idea. While I’m certainly a static typing evangelist, Python has always been a dynamic language, and shoe-horning a static type system on to a language which was never designed for it sets off alarm bells in my head. Objective-C deals with ‘static typing’ quite nicely: you get compiler warnings if the types don’t match. This doesn’t limit any of its dynamism, but you get some extra safety if you decide to use types in your program. Patrick Logan doesn’t like Guido’s proposal either, although that’s no surprise.

So, Python might just get static typing in the future. What’s next, Haskell getting more dynamic?

I was thinking of writing a parser combinator library for C++ today so that I could write a C++ parser in a style similar to using Daan Leijen’s awesome Parsec Haskell library. Then, I came across Spirit, part of the excellent C++ Boost libraries. Of course, they’re advertised as template-based parsers rather than parser combinator-based parsers, since C++ programmers will go blank in the face when you say ‘parser combinators’. If you’re not familiar with parser combinators, here should be all the motivation you need for using Spirit, from its introduction page:

A simple EBNF grammar snippet:

    group       ::= '(' expression ')'
    factor      ::= integer | group
    term        ::= factor (('*' factor) | ('/' factor))*
    expression  ::= term (('+' term) | ('-' term))*

is approximated using Spirit's facilities as seen in this code snippet:

    group       = '(' >> expression >> ')';
    factor      = integer | group;
    term        = factor >> *(('*' >> factor) | ('/' >> factor));
    expression  = term >> *(('+' >> term) | ('-' >> term));

Mapping an EBNF directly on to the language syntax: ahh, so good. If only more people realised that the whole embedded domain-specific language approach is so nice!

The propellerheads at Lambda have an interesting discussion that started with RDF (at least, interesting if you’re already familiar with RDF)), and evolved to discussing not only RDF, but also the semantic web, data schema, and ReiserFS and file systems.

A nice quote I found from a comment on Slashdot:

Languages like OCAML and Java are defective as general purpose languages because they don’t support efficient data abstraction for numerical types. The fact that their designers just don’t get that fact is a testament to the ignorance of their designers. It’s also what people really mean when they say that those kinds of languages are “just not efficient as C/C++”: it means that in C/C++, you can get whatever code you write to run fast, while in OCAML or Java, there are always problems where you have to drop down to C.

I’ll insert the usual “I agree” here. This is especially a problem with language benchmarks, which typically have benchmarks that operate on huge numbers of tiny bits of data. This usually destroys any chances that a functional language has of competing with a very low-level language like C/C++, because often these big arrays are represented as a series of pointers to the actual data, rather than simply big arrays that directly contain the data. This means one more pointer indirection for every index operation in the array, blowing away your cache hits and thus making your program run several orders of magnitudes slower. (If your language is also lazy, like Haskell is, you basically cannot work around this performance restriction unless you make your data structure strict … in which case, well, you’re not using laziness any more.)

This problem needs to be solved, without forcing the programmer to spend lots of time annotating exactly what data structures should be unboxed and what should be boxed, and what functions are OK to work with unboxed/strict data structures. Otherwise, people just aren’t going to these other languages for processing large quantities of small data. And in this day and age of computing, processing large quantities of small data is required for quite a lot of applications …

There’s also some interesting comments about Python 2.4’s new generator expressions, and how they are similar yet different to lambda expressions/anonymous functions: in particular, how they appear to give rather nice performance benefits. I haven’t given generators too much thought at all yet, assuming they were less elegant, ad-hoc implementation of representing lazy data structures. Sounds like I have some investigation to do!

Oliver Steele writes an excellent article on language mavens vs tool mavens, or: do you use Emacs/Vim+insert obscure language of your choice here vs do you use a mainstream language such as C#/Java with an excellent supporting IDE, such as Visual Studio or Eclipse? (Or maybe you use a mainstream language without any sort of IDE, in which case you’re doing yourself a great disservice.) Two quotes I liked from the article:

Why canít one be a language maven and a tool maven? Itís hard. One reason is that developers have limited time, especially for learning new skills. You can use any given block of time to master language features, or to master development tools … in fact, the most powerful languages may initially have the least powerful tool support. The reason for this is that the language developer, like the language adopter, has to make a choice: whether to dedicate limited development resources towards language features, or towards tool support.

Kudos to the Lambda community for finding the article.

Patrick Logan writes an insightful blog entry about problems with ‘rigid’ languages:

I am not sure why Python is changing or needs to. But the core language is more limited than Lisp or Smalltalk in the sense that it is “C”-like and distinguishes significantly between function calls, operators, and control structures … A more uniform language would not have as many of these backward-compatibility issues. This is the main issue I have with Python… it’s syntax is OK, but not great for extension.

This is also one issue that I have with Haskell (its syntax and semantics aren’t quite malleable enough for some embedding of domain-specific languages), but I’ll save that rant for a rainy day.

This thread (still currently active at the time of writing this blog entry) on the haskell-cafe mailing list is a nice example of the one big, major problem I have with Haskell: performance.

To summarise the thread, the infamous great language shootout (which is only infamous if you’re into alternative languages like Haskell, which get their asses handed to them in microbenchmarks for varying numbers of silly reasons) showed that Haskell placed last in the word count test. (Note that the benchmark results have since been updated with a new GHC-specific version of the solution, which is far uglier, but also about 60x faster than the original version.) The Ocaml guys went to town on this result, and of course claimed that Haskell was dreadfully inefficient, with a half-condescending remark at the end that “Haskell’s approach has been expensive in terms of performance”. The Haskell community ignites, and comes up with a version within a day or two that is twice as fast as GNU wc@, which is more or less on par with the Ocaml @wc version. This is good. However, two rather bad things stand out to me:

• Malcolm Wallace’s Space leak or what? post. Sure, Haskell has a space leak here. The problem is, you don’t notice these space leaks unless you’re an expert Haskell programmer. (I certainly can’t tell that code has a space leak, and I’ve been using Haskell for quite a while now.) The bigger problem is how to fix those space leaks.
• The final solution to the wc@ program submitted for the contest "looks like a goat":http://shootout.alioth.debian.org/lang/ghc/wc.ghc.html. Why should I have to use @unsafeRead (and thus potentially destroy any guarantees that Haskell’s awesome type system gives me) to get decent performance out of this thing, and why do I need to resort to IOUArray and lots of uses of seq? Compare the Haskell version to the O’Caml version, and draw your own conclusions about which is more declarative, high-level, and most importantly, which one doesn’t require an expert in the language to write.

The main problem I see with all this is that it’s just too hard for an average Haskell programmer to get good performance out of Haskell. As people have shown on the haskell-cafe mailing list, you certainly can get very good performance out of Haskell: in plenty of cases, surpassing an equivalent version written in C. However, you can only do that if you’re a complete Haskell guru, and even then, things start looking really ugly: you might as well just rewrite that part of the program in C and call it via the Haskell Foreign Function Interface. I think the main cause of this is that Haskell is simply too unpredictable: in most cases, it’s laziness which causes the unpredictability. Note that this is different from saying laziness leads to slower performance: this is untrue, because in many cases, laziness can improve performance. Predictability is the important factor.

For optimisation, you must know what factors are causing things to be slow, otherwise you’ll be searching in the dark for what bits to optimise. So, Haskell users will tell you to profile (which is sound advice no matter what language you’re using). That’s fine. The problem then is you have to know why something is slow, and there’s where Haskell can get complex. Is there a space leak? (Do you even know what a space leak is?) Is your array strict instead of lazy? If it’s strict, is it boxed instead of unboxed? (Do you even know what unboxing is?) Can you use unsafeRead instead of readArray? (Did you know that unsafeRead exists? I sure didn’t!)

I think if Haskell were to give the programmer slightly more control (or, in more formal terms, enable the programmer to choose from different operational semantics), Haskell optimisation could be moved from the expert’s domain to the novice’s domain. This is one area where the Clean language has innovated over Haskell: one may claim that uniqueness types and heavyweight use of strictness/unboxing annotations make Clean programs far less pretty than their Haskell version (and I agree), but if you need speed, you can get it in Clean much more easily in than Haskell. The language specification gives you more control over what’s going on; strictness annotations are one example of such a control mechanism. GHC does give the programmer access to many new operations intended for optimisation, but in a syntactically-heavy manner, which discourages you from using them. This is in contrast to Clean, where you can, for example, make an unboxed, strict array just by writing [# 1, 2, 3 !] rather than [1, 2, 3]. I don’t know how to make a strict, unboxed array in Haskell without looking up GHC’s library documentation.

It’ll be interesting to see whether the Haskell language itself evolves to plug this problem. I know I would recommend Haskell rather than O’Caml to more people if it made performance optimisation easier. Note that what I’m discussing here is convincing a Haskell compiler to give good performance, rather than blazing performance: if you absolutely require blazing performance and nothing else will do, code that small fragment in C or Assembly, and call it via the FFI. Multi-language approaches are good. However, the goal is to make it easy to optimise programs from an abysmal run time to a good run time: a run time that you wouldn’t be embarrassed about demonstrating to non-Haskell folks.

Update: This was originally written toward the end of 2004. I’m glad to say that things have changed since then: Don Stewart’s Data.ByteString library has nailed the performance gap between Haskell and C for string processing and binary I/O (even beating C occasionally, thanks to GHC’s far superior compiler optimisations vs C and gcc), which is arguably the main area where you’d run into serious performance problems easily. GHC 6.6 has also gained bang patterns and some syntactic sugar for arrays. (The latter isn’t quite as nice as Clean’s strict array syntax, but it’s a huge improvement.) Both these features greatly lower the barrier to entry if you’re trying to coax blazing performance out of Haskell.

A quote from a nice comment from Dave Benjamin on Lambda:

… I really wish Python had gotten a ternary operator; having to abuse “and” and “or” just to embed a conditional in an expression is tacky. I don’t care what the syntax is! Pick one! I feel like that feature died because of the noise, because nobody could agree on anything, and if that’s the direction of Python’s future, it’s a little bit scary.

Look, we’re not all going to agree on anything. I thought that’s why Guido was chosen as “Benevolent Dictator for Life”. Lately, his strategy has been to say something like “Well, I don’t care if we add the feature, and I don’t care if we don’t, but if you all can decide on a syntax, we’ll do it.” I think that this approach is killing progress. Of course we won’t all agree. We’re a bunch of opinionated hackers, and we like things our way. That’s why you’re dictator, Guido. Dictate!

Language is the one concrete dependency that we never seem to be able to abstract away. Changing a language affects more people the more successful a language becomes. Is it the destiny of every language to eventually grind to a halt, for no other reason than people’s inability to agree on the next step for growth? I hope not, but I’m glad we have lots of other languages that are not so constrained.

Totally agreed. Design by committee rarely turns out elegantly.

A snippet from a post by Guy Steele on the ll1-discuss list:

And you’re right: we [the Java language designers] were not out to win over the Lisp programmers; we were after the C++ programmers. We managed to drag a lot of them about halfway to Lisp. Aren’t you happy?

Spotted this little gem in a thread about programming languages and software engineering, on (where else?) Lambda the Ultimate:

John Reynolds told me that he once described a correctness proof for XORing together pointers in a doubly-linked list to someone. This person asked why he would ever want to prove such a disgustingly nasty hack correct, to which he replied that it was no longer a disgusting hack, because he had a clean proof of correctness for it.

Patrick Logan talks about Yet Another Python implementation named pycore, a Python VM implemented in Smalltalk. Yawn, you say? Well, right now it’s completely unoptimised, and seems to benchmark better than CPython. I can see this giving the much-more publicised IronPython a run for its money. Isn’t it great how Smalltalk can still compete well with today’s modern VMs?

By way of Joel Spolsky, a good article on Great Hacker != Great Hire. (And in case you haven’t guessed yet, I agree with the article by the simple action of linking to it from my blog ;-).

Matthew Thomas writes about the lack of usability advancements in the past two decades in this excellent blog entry. Why, indeed, do we still make people use filepickers at all? (Though, I should note that KDE’s File Open dialog box is actually a fully-embedded Konqueror view, which is a step in the right direction.)

Lambda the Ultimate has some pretty interesting discussion about compile-time checking for taking the tail of an empty list, which is generalisable to compile-time checking of any partial function (functions which are not defined for their domain, i.e. their input values). Some particularly interesting comments I found in that thread:

• “I see the empty list as being like null, which Nice has static checking for”. Wow, impressive (probably not impressive from the type theory angle, but particularly impressive from a practical viewpoint: all NullPointerException exceptions detected at compile-time? Cool indeed. Something tells me I should have a closer look at Nice. Maybe for my Ph.D, I can write a type inference engine for Objective-C. Nehhh …
• [On modifying the tail function to return Maybe [a] instead of just [a]]: “Using Maybe for this is like saying - let’s turn this partial function into a total one by lifting its range to include Nothing. It became total by obtaining permission to return something I have no use of.”
• “My point is that [the] Hindley-Milner type system is not expressive enough to allow two (or more) consent programmers to state their mutual expectations. As an author of tail function I can’t promise to always return list given non-empty list and expect the compiler to reject all programs that try to call tail on empty list. I suspect it’s possible to stretch Haskell a bit to encode this particular constraint, but as you said, dependent types are way to go for those who seek more static expressiveness.”
• “In Epigram type checking is decidable, because all functions are total. Conor McBride plans to add general recursion, but its use would be tracked by the system so that types can only depend on terms from the total fragment.”

And of course, the obligatory type wizardry post from Oleg:

• “I’d like to point out that it is possible in Haskell98 to write non-trivial list-processing programs that are statically assured of never throwing a `null list’ exception. That is, tail and head are guaranteed by the type system to be applied only to non-empty lists. Again, the guarantee is static, and it is available in Haskell98. Because of that guarantee, one may use implementations of head and tail that don’t do any checks. Therefore, it is possible to achieve both safety and efficiency. Please see the second half of the following message: http://www.haskell.org/pipermail/haskell/2004-June/014271.html”.

Wolfgang Thaller’s been working on bringing the Glasgow Haskell Compiler into the 1990s:

Yes. In fact, I already have a “Hello, world” program linked against dynamic libraries libHSrts.dylib, libHSbase.dylib and libHShaskell98.dylib on Mac OS X, and another one doing the same thing on PowerPC Linux.

All I can say is: thank God! Wolfgang, you rule. I can’t wait for this to hit the GHC stable tree!

Martin Pool writes yet another excellent blog entry, this time about Rusty on Interface Simplicity. His OLS 2003 keynote had an “interface simplicity spectrum”, which is so good, Martin reproduced it in his blog, and I’m going to reproduce it in mine, for my own reference:

1. Compiler/linker won’t let you get it wrong.
2. Compiler will warn if you get it wrong.
3. The simplest use is the correct one.
4. The name tells you how to use it.
5. Do it right or it will break at runtime.
6. Follow common convention and you’ll get it right.
7. Read the documentation and you’ll get it right.
8. Read the implementation and you’ll get it right.
9. Read the correct mailing list thread and you’ll get it right.
10. Read the documentation and you’ll get it wrong.
11. Follow common convention and you’ll get it wrong.
12. Do it right and it will break at runtime.
13. The name tells you how not to use it.
14. The obvious use is wrong.
15. Compiler will warn if you get it right.
16. Compiler won’t let you get it right.
17. It’s impossible to get right.

(Obligatory Haskell plug: a nice one-line summary of the Haskell language is that just using it for your code, puts you at #1 on that spectrum an incredible amount of the time.)

Doug Bagley’s most excellenté functional programming koans, courtesy of Sean Seefried. Here’s one example:

The Koan of Lazy Evaluation: Michel Mauny was giving a guest lecture to new computer science students. After the students were seated, Michel pronounced “Today’s lecture will be about Lazy Evaluation”, he paused for a moment then concluded with, “Are there any questions?”

Martin Pool has a really nice blog entry on how to use -Wall to turn on all warnings in gcc, and stop it from complaining when you have unused parameters. This is quite a common scenario when you’re using callbacks (a.k.a. delegate or visitor methods).

Lambda the Ultimate has a story on a new CLR (.NET) language named Boo. Ian Bicking’s comparison of Boo vs Python is a nice, succinct summary of it. Looks quite interesting: type inference, duck typing, macros, and string interpolation. Seems that the CLR does seem to be breeding all sorts of new languages …

In imperative languages, you usually get a new random number by calling a function (such as C’s rand(3)) when you need a new one. You can do this in a functional language like Haskell too, but then you’re forced into an imperative style, which isn’t very functional. (An imperative style would be required because generating a new random number depends on the current state of the random number generator.) You can keep a functional programming style by having a random number generator produce a (lazy) list of numbers, rather than a single number: any code which wants a random numbers simply pulls the next one out of the list. I posted some example code to the haskell-cafe mailing list recently to demonstrate this, in answer to a Haskell newcomer’s post. Lazy lists are often also called streams.

Normally, monads are used to encapsulate state changes in Haskell in a purely functional manner, but you can use streams too: any state changes which occur can be represented with new list elements. It’s no coincidence that streams are monads: they’re powerful enough to sequence non-deterministic operations. The Haskell Ports Library gives you even more convenience when working with streams by modelling time as a list, and the awesome iHaskell and Fudgets libraries for Haskell manage to model an entire GUI in a purely functional manner. Just to show that this is also has a practical benefit, the Fudgets code examples show how succinct writing GUI code can be. The Fudgets thesis is a great introduction and explanation to how it all works.

Closely related is the newer concept of arrows, which provide a formal framework to reason about stream-based (and also various other non-stream-based) computations. Anyone up for writing a Haskell library to interface to the gstreamer media framework as an arrow?

Bryn Keller (a.k.a. Xoltar) takes on Bruce Eckel’s comments about Python and static typing, and does a pretty good job at poking all the holes in Eckel’s arguments while remaining objective. Worth a read, especially if you’re wondering what all the hoopla is about Haskell and O’Caml’s type systems.

My Comments

Bryn comments toward the end of his article about how duck typing can lead to ‘dangerous’ situations. He uses the example of a method named draw, which has different semantics for the Gunslinger class (where draw means ‘Bang!’) vs a Artist class (where draw means ‘paint’). While it’s possible to have such name clashes with different semantics, in reality I don’t think it’s a big problem: certainly one not worth spending a few paragraphs on in an article. (When would this situation ever crop up, for example?)

He points out that in the Nice language, you can write a class, and make them part of the interface later. In his words: “We also got additional power in the bargain, because now we can selectively bless any class we like into the Speaker interface, without including classes we don’t want - we can ensure that our Artist doesn’t end up in a gunfight by mistake!”. In languages such as Java or C++, you must declare that a class implements an interface when you write the class: you cannot write a class and declare later that it implements the interface. It is very cool to program in a language which enables you to separate the code you write, from declaring how that code is used as part of your whole system design. Some other examples of this feature in other languages are:

• Haskell, which enables you to declare a type class to capture common functionality provided by different functions. So, you could write a Haskell module which provides a new Hashtable data type, and another Haskell module to provide a new balanced tree data type. You can then later write a type class to capture operations common to such colletion/aggregate types, by writing a new type class that declare type signatures for functions such as inserting objects into the collection, or retrieving objects from the collection. Note that you could have completely different interfaces to the hashtable/tree classes with completely different type signatures: the type class performs the ‘glue’ code necessary to provide one clean, consistent interface to both of them. (Plus, the very small glue code required to do that will be optimised away by any optimising Haskell compiler, such as GHC.) This is the same idea as Nice’s separation of code declaration vs interface declaration, though type classes are a far more powerful and generic concept.
• Objective-C’s categories, which enable you to add new methods to existing classes. You don’t like it how the NSFileHandle class doesn’t have a method to create a new temporary file and return you a file descriptor for it? No problem, just add your own method to do that to the class — no subclassing necessary. Categories are possibly the greatest thing I miss about Objective-C when I use any other language (Haskell included: it would be really cool to be able to extend type classes by adding new methods to them!). C# has a similar feature named partial types, although it’s nowhere near as elegant as categories. Perl 6 takes this idea even further than Objective-C does: it differentiates between open classes, which can have methods added to them, and closed classes, which can’t. The clever bit is that all classes are open by default, but any users of that class will close the class unless it’s specifically declared open. This is really smart because it means that you can have the same flexibility that open classes give you, but you gain all the optimisation opportunities that come with closed classes, such as performing static dispatch rather than dynamic dispatch on a function call, which opens up a whole new set of optimisations that weren’t previously possible, such as inlining.

One of the points of Bryn’s article seems to be that static typing detects different errors from unit tests: while this is true, I’d phrase this a different way. One benefit of unit testing is that it helps you develop your code faster because unit tests enable your code to be more robust as you develop it, saving you from hunting down those stupid bugs later on. Modern static type systems give you different test coverage, and I think they speed up your development even more, because they often pick up a lot more errors than unit tests do. If you’re a Perl programmer, the use strict; pragma that Perl has basically turns on static type checking. Think about how many bugs you’ve found thanks to its warnings and errors, and imagine how much of a nightmare it’d be if you didn’t have that facility at all. Now think about extending Perl’s simple type system (which is limited to only type checking of scalars/arrays/hashes), so that types are pervasive in your program design that enable far better coverage by the type checker, and you’ll hopefully have some idea of what I’m talking about.

He remarks right at the end of his article that “We need both strong testing and strong typing” — I think he means static typing, not strong typing, considering that was what his entire article was about :). Mind you, static and strong typing seems to be confused quite easily: even Guido van Rossum confuses strong typing with static typing. I personally find it a bit worrying that the designer of such a popular (and great!) language gets it wrong, but hey, nobody’s perfect.

Bryn, I think, doesn’t point out the biggest benefit of modern static typing systems: it saves you time because so often, when that anal type checker finally does let your program compile, it just works a really surprisingly large amount of the time. (This is closely related to the increase in productivity that I discussed above, but it’s not quite the same thing.) It’s downright unnerving just how many times your program performs correctly: one thread on the cvs-ghc mailing list gives an anecdote, where most of the Glasgow Haskell Compiler back-end was ripped out and re-written (14000 lines of code!), and the PowerPC code generator worked first-go. I’m yet to nail down whether this phenomenon is only due to the advanced type systems alone, or whether it’s a combination of the powerful type system and a (purely?) functional programming style; I suspect it’s the combination of the two. Programs are much easier to reason about when state changes are made explicit.

Here’s a few tips that I’ve discovered to ease working with Subversion.

Long URLs

Tired of those long URLs, like svn+ssh://foo@bar.com/long/directory/hierarchy/to/svn/repo/trunk? Use a shell alias, function or shell script which simply prints the URL. e.g.

#!/bin/sh
echo "svn+ssh://foo@bar.com/long/directory/hierarchy/to/svn/repo/$@"

Save the shell script as, say, FooSVN. Now, instead of typing those long URLs on the commandline, you can just write svn co `FooSVN trunk` instead.

Here are some patches for the VideoLAN cross-platform multimedia player, to enable support for Annodex bitstreams.

• Annodex support for the Ogg demuxer (modules/demux/ogg.c): vlc_modules_demux_ogg.c.diff (MERGED)
• A modification to the vout_ShowTextAbsolute function in src/video_output/video_text.c, so that it returns the subpicture_t created. This is required for the upcoming CMML support: vout_STA_returns_subpicture_t.diff (MERGED)

VLC now supports playback of Annodex files and CMML tracks as of version 0.7.2. Woo!

This took way too much futzing around to get working (or perhaps I’m just too used to Mac OS X now), so here’s a no-frills guide to get it working:

• Add the lines
  deb http://marillat.free.fr/ unstable main
  and
  deb http://pessoal.onda.com.br/rjamorim/debian/ ./
  to your /etc/apt/sources.list file.
• apt-get update; apt-get install libfaad2-dev
• apt-get -t unstable install libstdc++5
• If you’re on x86, download the i386 .deb of my patched version of Frederic Fondriest’s xmms-mp4plugin XMMS input plugin.
• If you’re exotic enough to not have an x86, download the debian source, and run
  fakeroot debian/rules binary
  to build the .deb for you. You need the g++-3.3 and automake1.7 packages installed to compile this thing.
• Execute sudo dpkg -i xmms-mp4plugin_0.2-1.andrep_*.deb to install the package.
• Run XMMS and enjoy.

Useful links:

• http://rarewares.hydrogenaudio.org/debian.html: RareWares Debian repository for faad2, faac, aac/mp4, lame, lame-ha, lamip, cue2toc, shntool
• http://www.xmms.org/comments.php?show=P211: Original sources for Frederic Fondriest’s MP4 XMMS input plugin

(Random keywords to be more search-engine friendly: Debian, Linux, XMMS, iTunes, MPEG-4, MP4, AAC, M4A.)

MochΛ is a Haskell to Objective-C language binding for Mac OS X. Using Mocha, Haskell code can send messages to Objective-C objects, and Objective-C class declarations can be written in Haskell. Haskell API definitions are provided for the entire Mac OS X Cocoa framework, and automated interface generation can be performed for any user-supplied frameworks.

Update: Mocha has been officially discontinued—but never fear, Wolfgang Thaller and I have been working on HOC, which fulfils much of the same goals that Mocha strived for, and furthermore, it’s actually released and working! See the HOC release announcement for more details.

What is Vimacs?

• Conrad Parker: “Dude, I gotta get you doing some serious hacking projects”
• Erik de Castro Lopo: “Oh, so you’re the insane guy that K was talking about”
• Wichert Akkerman: “Gross. Horror. Vim abuse. Mind if I include this as an example in the Debian vim packages? :)”

Yep, it’s Emacs in Vim:

http://www.algorithm.com.au/vimacs/

Note: Since I wrote this dynamic loader for Haskell a long time ago, quite a few advancements have been made, so I’m no longer supporting this package. See the end of the page for discussion on the state-of-the-art in Haskell dynamic loading.

Introduction to Dynamic Loading & Plugins

Dynamic Loading is an important feature for building extensible programs and larger applications. It allows the program to load in code contained in a file, at runtime, and execute it. It’s a simple concept, but it leads to applications which can be very easily extended, sometimes in ways the original author never imagined.

If you’re still not convinced of the power of dynamic loading, think of WinAmp (a.k.a. XMMS :), which uses plugins to read files and perform device-specific output (not to mention all of its fantastic visualisation plugins). Each file type (MP3, WAV, OGG, XM, etc) is handled by a separate plugin, which means that it’s incredibly easy to extend WinAmp to play different types of media files.

Other notable projects which extensively use plugins are the Linux kernel (think kernel modules), Emacs, the Windows device driver model, the entire DirectX/gstreamer media framework, and the Apache web server. These projects would not be what they are today without their modular, extensible design.

Plugins in Haskell

The good news is: GHC has had, for quite a while now, the capability to load in Haskell modules at runtime. (If you use GHCI, that’s exactly what it does!) The bad news is: you can’t normally get at the functions which will do this for you. The better news is: thanks to some handiwork, you now can get at the functions which perform runtime (un)loading of modules; you’ll need to download a special RuntimeLoader module which allows you to do this.

To use it,

  import RuntimeLoader

  ...

  -- Load the plugin file
  plugin <- loadObject "MyPlugin.so"

  -- Load the function inside the plugin
  adder <- loadFunction plugin "addFunction" :: IO (Int -> Int -> Int)

  -- Execute the function
  let i = adder 2 3

That’s all you need to do to load a plugin. (Okay, not quite, you have to add a few flags to the ghc commandline too ;-).

If you’re interested, I’ve packaged up a small, example program called “TextFilter” which includes the RuntimeLoader module and demonstrates how to use it. Download it and get hacking!

• TextFilter-1.3.tar.gz

Sorry, there’s no separate package for just the RuntimeLoader by itself: I think the TextFilter example is small enough that packaging it separately from the RuntimeLoader isn’t worth the hassle for you or me.

Since the release of RuntimeLoader in 2002, a few other people have taken up the challenge to make Haskell a more dynamic language. If you’re interested in this, have a look at:

• HWS-WP, a.k.a “Haskell Web Server With Plugins”. Martin Sjöaut;ren took the original Haskell Web Server written by Simon Marlow many moons ago, and extended it to have Apache-style modules.

• Hampus Ram’s DynamicLoader, which provides a higher-level API than my RuntimeLoader module.

• I worked with Don Stewart, Sean Seefried and Manuel Chakravarty on a paper named Plugging Haskell In, which is complemented by an implementation of a far more complete dynamic framework for Haskell named hs-plugins. Thanks to the incredible work of Crazy Don, hs-plugins has become mature enough to write an interactive Haskell shell in less than 100 lines of code, and even lets you call Haskell functions from C far too easily. Check it out, dude.