Fixing your Ubuntu suspend/resume problems

After some recent update, my Ubuntu box (currently "Intrepid Ibex") started having a problem where the networking wouldn't come back up when waking from suspend mode. My machine uses the "forcedeth" ethernet driver (quite a name \m/ ).

The fix! Mentioned tersely over here, and slightly more clearly over here, all I had to do was create a file /etc/pm/config.d/01-modules that contains this line:

SUSPEND_MODULES="forcedeth"

Apparently you can name the file something else, as long as it's in the same directory, but this one worked for me. And of course, if you're having trouble with a different driver, change "forcedeth" to the right module name.

It's 2008 -- why is power management still tricky on Linux? Users (like your non-technical family members) should never have to do this sort of thing.

I could have just emailed them a photo of my shelf

I seem to have just spent 20 minutes flipping through Amazon's book recommendations, finding books that I already own and checking the box that says so. This, of course, made other books that I already own pop up, which I then clicked. And it was kind of fun. Thoughts that ran through my head included "I have the first edition but not this latest one, does that count?" and "Lindsey has that one -- that's almost like I have it, right?"

Excellent design, Amazon dudes and dudettes. I don't begrudge you that training data at all.

Debian on the OLPC

I should go to bed, but I'm having so much fun setting up Debian on my XO laptop.

It was super-easy getting it installed (instructions here); you use the same command for updating to a new version of the standard olpc software and for installing Debian. Or Edubuntu, apparently.

For extra disk space, I blew away the default Sugar/Fedora install -- it's pretty easy to get back to a fresh state, just in case I want to set that up again later.

In 472 megs, I have the base Debian, X.org, subversion, vim, fluxbox, mzscheme, and the Glasgow Haskell Compiler, the install for which pulled in gcc, so was big.

sudokudlx: Automatic Sudoku Solving with Dancing Links

In case I hadn't shown you yet, here's my Python implementation of a Dancing Links sudoku solver, on appengine!

http://sudokudlx.appspot.com/

Also, I've written a bit about how to use Dancing Links (DLX) to solve sudoku puzzles. Soon, I'll write up how to implement DLX.

plats is Swedish for "locale".

My first pass for solving the problem from a few days ago is now live on appengine.

Check it out: http://plats.appspot.com

Just include a script in your page and you get a variable or a meta tag (for GWT apps) to tell you which locale you should be in. Details here.

figuring out the user's language preferences, client-side

Your browser sends an HTTP header field called "Accept-Language" (see 14.4) when you make a request to a web server. It tells the server which languages you prefer, and in which ordering, so the server can send you localized content with graceful fallbacks. You can muck with these, for example, in your Firefox settings under Preferences > Content > Languages.

So I'd like to do this on the client side. I had the bright idea that I would just build an XMLHttpRequest object and ask it what headers it was about to send (XHRs do send this field), but GWT's HTTP objects don't let you get at request headers that you haven't explicitly set. The very good reason for this is that XMLHttpRequest objects don't let you query their headers. Oh noes.

It may be that the way to do this is with a bit of server-side cleverness, but that's not the answer I want. Unless somebody happens to have a way to snag these settings from JavaScript...

GWT 1.5 release!

Wooooo, new version of GWT! This is huge. We've been working really hard on this for quite a while.

http://code.google.com/webtoolkit

What's new? Check check check it!

Firefox 3: you can drag tabs between windows!

That's a pretty neat feature: drag a tab from the tab bar on one Firefox window into another one. You can also drag them into your bookmarks toolbar.

I'd like a way to grab hold of a tab and drag it out into space, forming a new window, but this might be hard to implement -- some systems would make a link on the Desktop. Failing that, an "open this tab in new window" command would be nice.

I could put in a feature request, I suppose -- or even a patch! How hard could that be to implement?

Lisp snippets on a Tuesday night

The ICFP contest is coming up, and Lindsey Kuper and I have been building our Scheme muscles. I was looking for an implementation of hash tables (or just some quick way to do a map), and I ran across the SRFIs -- Scheme Requests for Implementation. It's a semi-standard library of useful stuff for Scheme, and it's bundled with recent PLT Schemes! You can just say: (require srfi/n) to load up the nth SRFI; they're numbered. Particularly, I've been playing with the extended libraries for lists, strings, and hash tables.

On the Common Lisp side of things; I just ran across the insanely useful describe, which prints out what the system knows about a given object -- if it's a function with a docstring, the docstring will be in there. Also potentially useful: disassemble. Give it a function; it does what it sounds like!

reconsidering applets

Applets are a really tempting idea. The JVM is a serious piece of machinery; despite its startup time, once it gets rolling, Java can go fast indeed. And although it hasn't been very widely used, applets and javascript have had a means of calling back and forth for quite a while. It's called LiveConnect. (although LiveConnect may be replaced at some point...)

So, a beefy, fast VM that runs inside the browser, coupled with a nice web UI, and no manual installs for your users -- big win? Maybe! On considering this, one of my first thoughts was to put Jython into an applet and build something akin to JES -- a little Jython IDE in the browser! The kids would love it! So I set out to make this happen, or at least build a proof-of-concept.

I ran into a serious snag, though -- the Jython interpreter works by compiling to bytecode and bringing it up with the class loader, the latter of which applets aren't typically allowed to do. Special permission can be granted with a Java policy file, but that's a very high barrier to entry. It's certainly not the sort of thing a person might do on a public terminal. Signing the applets may also be an option -- but that's also a pain, and anecdotally, I think signed applets may not always get the same rights, cross-platform.

Once I understood the permissions issue, I did get a little Jython repl going -- it just hooks "eval" up to some javascript for output. Nothing fancy, but kind of satisfying. For now, though, it doesn't look like Jython IDEs are coming to the browser. Until we rewrite it to not use of the class loader. Or just use some more modern approach.

Some other people have had similar thoughts!

• Interactive Jython Console: this one, for the exact same reasons that mine does, requires a java policy file.
• the ruby-in-browser project. It does exactly pretty much what it sounds like it does, also by means of an applet and LiveConnect. Interestingly, JRuby doesn't seem to use the class loader, it just works! Check out the demo! [thanks for the heads-up, Lindsey Kuper!]

GWT 1.5RC1 -- we're pretty pumped.

Google Web Toolkit 1.5 RC1 is live!
http://googlewebtoolkit.blogspot.com/2008/05/google-web-toolkit-15-release-candidate.html

Get the bits while they're hot.
http://code.google.com/webtoolkit/download.html

GWT 1.5 has a whole lot of wild improvements, detailed here -- but importantly, compiler now supports Java 5 features and produces even tighter code than before, and the UI library has had some pretty serious reworking -- there's a new API for working directly with the DOM in a typesafe way, and GWT apps now come with nice styling by default. We've been working pretty hard.

Oh, and don't miss the new documentation browser :) Much better than browsing the GWT wiki docs by hand.

Share and enjoy!

Real World Haskell

In case you haven't been exposed to enough Haskell buzz recently, there's a new book in the works: Real World Haskell by Bryan O'Sullivan, to be published by O'Reilly. In addition to the abstract functional loveliness that you expect, they're going to build webapps that talk to databases, which is not the first thing that pops into my mind when I think "Haskell".

Beta chapters are here.

(if you knew where to look, there was an announcement on LtU about being an alpha reviewer, to get at the pre-pre-release chapters...)

vim tip: don't mess up the indentation when you paste

vim does really lovely autoindenting. But what happens when you want to paste in pre-formatted text from somewhere else? All your code indents way off to the side, oh noes! Here's what to do.

:set paste
Okay, now paste.
:set nopaste

Perfect. I rated this tip "life-changing".

Penguin Parens: referenced by NLTK!

A while ago, I was working on remixing horoscopes and I gushed quite a bit about the lovely free Python NLP toolkit NLTK. And I was honored to get a comment from Steven Bird, one of the NLTK developers and an eminent natural language researcher.

It turns out that they quoted my blog post for the "Quotes" page. Aw :)

I'm checking out their circumstance again, so to speak -- and it's grown so much. They've got most of a textbook (free online!) put together. And the API is gigantic, so much code! Amazing. I'm going to have to dig back into it.

you need more retrocomputing: Mini vMac and old Apple software

So I was looking for cool activities for my new XO laptop, and I ran across Mini vMac, an emulator for the Macintosh Plus; it's cross-platform, but if you happen to have an XO, here's the .xo activity.

And it works really well! You'll need a ROM image, y'know, taken from the Mac Plus that you personally own, and also an image from a "System" disk (available on that same page).

But! As the Mini vMac page points out, you can get old Macintosh System software from somewhere else -- Apple's own Older Software Downloads page, which features all sorts of outdated Apple software. System disks, drivers for bizarre old SCSI hardware... and Hypercard.

The Mini vMac page also links to this fantastic compendium of old macintosh software from third parties, which has even more wild old stuff, like vim 3, forgotten Lisps and MLs, games that you might remember.

I'm going to have to run this fullscreen on my Macbook Pro, woo!

more retrocomputing: procedural graphics languages!

One of my first online experiences -- and probably the first for a lot of people, came in the form of Prodigy, over dialup, on an old DOS box. At the time, Prodigy wasn't an ISP as such -- it was an insular online community, with its own exclusive content and games and message boards and email. Of course, this model wasn't sustainable forever...

But! The interesting thing about Prodigy was the graphics. It was clear, at the time, that it wasn't downloading "images" as such -- y'know, like raster graphics -- it was drawing in terms of commands that would build pictures out of shapes. This was kind of cool; the dialup link was slow enough that you could see it building the picture, usually bigger background shapes first, then the details would get filled in. It occurs to me now that it must have been somebody's job to work out how to draw pictures like this...

It turns out that Prodigy was using the standard language for this: NAPLPS, the North American Presentation Level Protocol Syntax. And there were several other services that used the same approach -- some of them sent the commands over modems, like Prodigy, but some went over TV, during that mystical vertical blanking interval that broadcast engineers talk about.

Speaking of sending non-raster graphics down the wire: did you know that there's a set of drawing commands understood by some DEC terminals? It's true. It's called ReGIS. At one point, Brett and I got our hands on some old DEC terminals and spent a few afternoons messing around with this on something that must've been a vt340 or vt420. You can find out all sorts of wonderful things about DEC terminals at the super-top-notch vt100.net. These things seem to be indestructable; I held on to the vt220 for years, passing the joy forward sometime in college; it was still chatting amiably over the serial port on my Linux box, and almost as old as I was.

That's all for now. Happy hacking!

in which alexr surprises you by linking to Microsoft software

If you build web applications, you've got to contend with Internet Explorer, versions 6 and 7. The quandary is that it's not clear how to have both versions installed at the same time. Some people have resorted to using several virtual machines, but this turns out to be overkill.

Lindsey Kuper comes to our rescue, and points out this article: Using IE6 and IE7 together.

The first approach in that article was especially helpful for me: there's a version of IE6 bundled with all the libraries, ready to go even if the updates have installed IE7 for you. It works great, in as far as IE6 can be said to "work great".

What is surprisingly nice is the Internet Explorer Developer Toolbar. This is from those cats in Redmond, and I'm surprised it's not more widely publicized. It comes with a very functional DOM inspector that users of Firebug will figure out pretty quickly, and it works with that standalone IE6.

So! Now you can more easily and precisely diagnose just which inane and hateful things the IE rendering engine is doing to your app!

Happy hacking, and good luck :)

Today's viewing: Linus on git.

Not too many months ago, Linus gave a talk at Google about git, the distributed version control system he built for use in managing the Linux kernel. He spoke, in typical non-diplomatic Linus style, about why everybody should switch to git and why CVS, Subversion, Perforce, and non-distributed source control in general is broken.

"There's a few of them in the room, I suspect -- you're stupid!"
-- Linus calls out the svn developers on hand

The Linux kernel team had previously been using the proprietary BitKeeper, which a number of kernel developers (including Alan Cox, with his Mighty Unix Beard) chose not to use. Before that, source control for the kernel was handled by sending patches around -- preferable to using centralized source control, according to Linus.

So let it be known that I haven't actually /used/ git yet, or in fact any distributed source control system -- but I like the idea so far. In this post, I'll outline the reasons Linus lays out for why we should be using git.

First off, the distributed nature of git also has performance and convenience benefits, from the simple fact that it doesn't need to make network roundtrips. Having your own repository on the local machine means that you're always set to go, even if the network is slow or unavailable.

Secondly, traditional source control makes branching and merging branches hard (Linus points out that many real-live software developers have never done it), so you don't want to commit your work until it's ready to be seen by others -- this means that you can't do much version control during the actual code-writing process. Contrastingly, in distributed source control, every checkout acts as its own branch, so each developer has at least one. This has the benefit that you can commit to your own repository whenever you want -- and then back up to previous versions whenever you like.

Centralized approaches to source control are particular drag when people are depending on your committed code as correct, or at least non-breaking -- you're not allowed to commit until your changes are ready for the rest of the team. As a project gets bigger, the associated test suite (hopefully) does as well, eventually leading to a pretty involved testing procedure that developers are supposed to complete before committing. And as Linus puts it, "... people make one-liner changes and ignore the test suite, because they know that those one-liners can't /possibly/, /possibly/ break." And then these breaking changes get pushed out to the rest of the team. The alternative approach, with git, is that you commit to your own version of the repository whenever you want, and when you're ready, your teammates can pull from you -- but in the mean time, you get all the benefits of having your own branch(es).

Thirdly -- social benefits! In his development process, Linus only pulls code from ten or fifteen other developers, whom he trusts to have filtered "up" appropriate changes from the people that they interact with. As he puts it, "if you have determined that somebody else is smarter than you -- go for it!" So the Linux kernel source control process mirrors the social networks of trust that make the whole thing happen. In the end, a lot of people end up only looking at the Linus branch, the defacto "official" one.

This dodges the social issue of giving out commit access to the central repository. Traditionally when managing a project, you create this class of people who are "ostensibly not morons", and typically, you make that group of people too small. Distributed model makes this go away, because everybody has his own branch. And if you happen to do good work in your own branch, then people start pulling from you! "That alone means that every single open-source project should use nothing but a distributed model."

So. That's what Linus said. Will everyone switch to git or some other distributed source control? We'll find out. Adoption would certainly be helped out if major project-hosting sites like Sourceforge or Google Code added git support. But sort of the point of the distributed model is that there's no one central hosting point...

Maybe I'll try it out. I'll let you know.

today's reading: Neighbourhood Components Analysis

Goldberger, Roweis, Hinton, and Salakhutdinov: Neighbourhood Components Analysis. The punchline: ... learning a linear transformation of the input space such that in the transformed space, KNN performs well.

I've been making an effort to read more academic papers. This one came up for one of the many reading groups at the Goog, and I picked it out of my stack a few days ago. Here's the abstract.

In this paper we propose a novel method for learning a Mahalanobis distance measure to be used in the KNN classification algorithm. The algorithm directly maximizes a stochastic variant of the leave-one-out KNN score on the training set. It can also learn a low-dimensional lin- ear embedding of labeled data that can be used for data visualization and fast classification. Unlike other methods, our classification model is non-parametric, making no assumptions about the shape of the class distributions or the boundaries between them. The performance of the method is demonstrated on several data sets, both for metric learning and linear dimensionality reduction.

This is a very common, general problem for machine learning -- you want to build a classifier, and you think you might like to use K Nearest Neighbors; it's dead simple, and a lot of the time, it gets the job done. No complicated models to train up -- if you want to classify an instance (ooh, here's an animal -- is it a kitty?), you just find the k most similar instances in your bank of examples and let them vote it out. Four of the five most-similar things in your example set are kitties? Alright, we'll call the new one a kitty. You have to tune k as a parameter to work well with your dataset, of course, and you can get slightly more sophisticated by introducing weighted voting -- things that are less similar to the instance you're trying to classify are considered less important.

The remaining question, though -- how do you decide what counts as "similar"? Typically, you use some sort of distance metric (Euclidean or Manhattan, for example) -- plot all of your instances in some high-dimensional space and see what's close. What if some of your features are noisy or irrelevant, though? Well, you could do some feature selection and prune those features out. Worse! What if you have several informative features, but they happen to be on very different scales, such that distances in one overwhelm distances in another? Well, you could manually scale them until you get some good results...

This is starting to sound like maybe K-Nearest Neighbors isn't all that easy to use, out of the box.

This paper actually solves both of those cases. Goldberger et al harness the power of linear algebra and come up with a way to learn a projection -- just a matrix -- from the original feature space, where distance metrics might not be very useful for KNN, into a new feature space, where your distance metric does the right thing. In effect, this is the feature selection and the scaling, all in one go, and they do it in such a way as to minimize the Leave-One-Out error, all tuned for your particular data set.

That's kind of cool.

As an added bonus, if you restrict the transform to project into three or fewer dimensions (just make sure the matrix is the right shape, and you're good!), then the same algorithm produces what sounds like a very nice visualization of your data. Features that are informative in discriminating your classes will be stretched out, and instances in the same class will tend to clump -- otherwise, KNN wouldn't work very well.

Lovely paper, guys! Very well-written, clearly explained, and addresses a problem probably a lot of people have had. The only issue I can raise so far -- it's not clear how long it takes to learn the transformation. This might be a very slow process, and all we're given in the paper is something to the effect of "oh, just optimize this function and you're good..." ... the machine learning pros among us can probably just look at the formula and knock it out in a few lines of Matlab (or supposedly Lisp, if you're Charles Isbell), but I would've liked a little more discussion on the implementation side... maybe they posted some code somewhere.

Happy hacking :) alexr out!

Design Patterns Ahoy: Violator Pattern

So, at work, every so often somebody brings up the "Violator" Pattern, typically with a slight smirk. Up until recently, I wasn't at all well-versed in design patterns, but this seems like a field that one, as a professional programmer, should be at least familiar with. So I picked up the classic Gang of Four book and started reading through it.

And while, so far, it seems like just good, solid advice about software design -- and at the risk of sounding uncritical, is it really so bad to have common names for commonly-occurring software structures? -- ... no "Violator" pattern is to be found in Gang of Four. Or on the C2 design patterns wiki.

And I wanted to work out for myself what this mysterious Violator Pattern could be. And I figured it out today. In GWT, you can use the JavaScript Native Interface to make calls from code written in JavaScript into methods written in Java. And when you do this, the compiler totally ignores the access modifiers on the methods you're calling. That's the Violator pattern.

A paragon of OO design, verily :)