ICFP 2009 paper on Haskell in the Real World

Here’s a good paper on using Haskell to write a commercial application. The authors are practical commercial programmers who tried Haskell to see if it was a more effective language than Ruby: Experience Report: Haskell in the “Real World” Writing a Commercial Application in a Lazy Functional Language Of special interest is the “Problems and Disadvantages” section. It seems that space leaks which are a continuing source of trouble in the authors’ application. Reading this paper reminds me of Tenerife Skunkworks Haskell vs Erlang Reloaded. In that experiment a developer found that Erlang was much better than Haskell for real-time programming.

Back to gnome

Well, 8 hours using wmii was enough for me. Too many apps didn’t quite work right. So I’m back to plain-old-boring-but-familiar Gnome.

Technology Trends I'm Keeping an Eye On

In no particular order, here’s what I’ve been studying lately:

  • Javascript. I’ve avoided this language over the years because of its low speed and shoddy reputation. But the language implementations seem to be getting faster and the available libraries seem to be getting more interesting. I’ve just watched all of Doug Crockford’s YUI lectures on JavaScript, and I’m thinking about trying to use the language in some toy projects.
  • git gui - this git command, available in recent builds of git, make Git changes pretty easy to author.
  • The Undercover Economist - this is a great book about economic theory. It’s pretty easy to read while shaving, or waiting for compiles. Lots of good anecdotes and tools for modeling the behavior of consumers and firms. I took 3 economics classes in college, and they didn’t teach me as much practical information as I’ve learned from reading this book.
  • Hacker News - this link voting site has replaced alterslash and reddit programming as my daily comp-sci news site. I like the emphasis on start-up news.
  • wmii - yet another tiling window manager. I tried a bunch of tiling window managers, and this one seemed to “click” with me. I found that I could customize it easily, and it mostly “just worked” the way I wanted it to. We’ll see if I stick with it or go back to Gnome. [Follow-up. I went back to Gnome (and then to OSX). Oh well.]
  • Chrome - now that the Linux and OSX versions have Flash support, Chrome has become my default web browser. I like its clean UI.

Dual XHD7714 Road Trip Report

After a month of using the Dual XHD7714, during which my family and I took a 4000 mile road trip, I have to say it’s a pretty nice system. We used it almost exclusively as an MP3 player, rather than an HD Radio or a CD player. I loaded 800 songs from our home music collection onto an 8GB memory stick. It was great introducing my kids to some new music. By the end of the trip their favorite songs were Shock the Monkey and The Magical Mr. Mistoffelees.

Some problems specific to the Dual XHD7714:

Bluetooth issues:

  • Bluetooth headset mode only syncs with one phone at a time. This seems to be a common limitation of low-end bluetooth car stereos, but it’s quite frustrating for two-driver families like mine.
  • Bluetooth audio streaming mode doesn’t sound very good on this radio. However, I didn’t experiment with this very much, so it may have been source-material related.

USB MP3 player issues:

  • It takes about 5 seconds per GB to index USB stick music each time it starts up.
  • It only recognizes US-ASCII characters. If any non-ASCII characters are present in the album or song name the entire name is replaced with the string “Not supported”. We had a lot of Chinese-language tracks that displayed that way, making them very difficult to navigate.
  • It can’t fast-forward or rewind through MP3s.
  • When you turn on the radio, it does remember where in the current MP3 it is playing, but it takes a long time to resume playing an MP3 in the middle. So it’s awkward listening to long podcasts.

Still, even with all these flaws, I’m quite happy with the radio. We really enjoyed being able to conveniently listen to so many different songs during our trip.

Nehalem machines are very fast

I’ve just had a chance to use a Nehalem HP Z600 workstation with 2 Xeon E5520 CPUs. The machine has 8 cores, 16 hardware threads, and an absurd 12 GB of RAM.

It’s very fast. It’s about 2.5 times as fast (when building the Android sources) as the previously fastest machine I’d used, which was an HP xw6600 with a single Xeon E5420 CPU.

The machine’s relatively small, no larger than an ordinary ATX tower. One way that HP kept the case small is by making the motherboard an odd shape: it is “C” shaped, with a cutout that leaves room for the DVD drive.

Too Many Words about Car Stereos

The other day my wife said to me, “Jack, we’re going on a road trip soon. Is there any way we could hook up our MP3 player to the car stereo, so that the kids could listen to their favorite songs during the trip?”

Twenty hours of web research and $250 later we’ve got a new car stereo. It’s a Dual XHD7714 from Crutchfield. I’m getting it installed by Best Buy tomorrow. Let’s hope their AV installers do a good job!

First, why did I get a new stereo at all? Well, all I wanted to do was hook up an MP3 player. But there was no easy way to do that. My 2005 minivan came with a factory installed stereo that didn’t have an auxiliary input. There are cheap FM transmitter systems that work with any radio, but they look clunky and the sound quality is supposed to be poor. A lot of web searching turned up some aftermarket accessories that allow hooking up either an audio input jack ($75

  • $50 installation = $125) or an MP3 player and/or iPod ($125 + $50 = $175.) But the for just a little more money I was able to get a a whole new radio with lot of additional features.

Why this particular model? It was well reviewed and relatively inexpensive. The features I was interested in were:

  • MP3 player / USB memory stick player.
  • Hands-free bluetooth calling with a built-in microphone.
  • Streaming audio from a bluetooth phone.
  • Charging USB devices.
  • HD radio.
  • Good fast text UI for navigating a MP3 player.
  • Play MP3s stored on CDs.
  • Wireless remote control for “back seat DJs”

General thoughts on the car stereo market

  • Crutchfield is a good place to research and buy car stereos. For research purposes they have a wide selection, and they have very good information, especially in the form of user reviews. For buying they offer free shipping and more importantly a free installation and wiring kit. They also seem to offer very good telephone help for do-it-yourself installers.
  • The add-on car stereo market is in long-term decline. I think that in the next few years the car stereo will become little more than a mobile phone docking station. People will keep their music collection on their phone, or stream it from the internet.
  • Car stereo makers are not going down without a fight. They are experimenting with iPhone-inspired full-screen touch-screen UIs and built-in internet radios. While very creative, I don’t think people will buy them. They will just use their phones instead.
  • Many people want to connect their iPods to their car stereo. In the short term Apple is making this difficult by changing their communication protocols with every generation of iPod. In the long term iPods are going to be replaced by iPhones, which will probably be forced to support bluetooth stereo streaming.

Using a Mac keyboard with Ubuntu Linux

I frequently switch between Mac and Linux, and it’s been troublesome to remember to type Command-whatever on the Mac, but Control-whatever on Linux. (For copy-and paste, for example.)

I did a quick web search and found out that it’s easy to make Ubuntu Linux recognize the Command keys as an extra set of control keys:

Choose menu: System : Preferences : Keyboard
Select the Layouts tab
Choose "Layout Options"
Open the "Alt / Win Key Behaviour" tab
Check the "Control is mapped to the Win-keys" checkbox.

ICFP 2009 contest blog - Team Blue Iris

I just threw in the towel on the ICFP 2009 Programming Contest.

The problem this year was a set of 4 sub- problems related to orbital mechanics, plus a virtual machine spec. The virtual machine was used to enable the problems to be specified exactly, without worrying about differences in the order of math operations.

Implementing the virtual machine was easy and fun. Unfortunately, actually solving the final sub-problem required learning too much math and physics. I was able to solve problems 1 and 2, and make an entry for the lightning round. And I brute-forced a solution for problem 3. But now, 56 hours into the contest, I am giving up on problem 4.

I can see the general outline of how to solve it, but it would take sharper tools than I have now. For example, I’d like a way of solving Lambert’s equations, but I’m having trouble deriving the code on my own, and the best example I’ve found while searching the web is a 30-year-old NASA Space Shuttle Fortran program. Also, I’m pretty tired, and this is affecting my judgment. I don’t think it’s worth going on at this point.

Some fun things I did during the contest:

  • Learned Orbital Mechanics, the study of how bodies move in space.
  • Learned what a Hohmann Transfer Orbit is and why to use it.
  • Learned what Lambert’s Theorem is, and how to apply it to missile guidance.
  • Wrote a Python program that did efficient calculations by generating a C program, compiling it, and then running it and talking to it via a pipe.
  • Read a ton of Wikipedia articles, Google Books books and old NASA tech reports on orbit planning and course corrections.
  • Learned how old-school Q-system guided missiles work. Very clever use of ground-based computers to compute coefficient matrices that were fed into simple on-board analog computers for the duration of the flight.

Highlights of the contest:

  • Hanging out on IRC with 20 other contestants, trying to get the simulator to work.
  • Getting problems 1 and 2 to work.
  • Giving up on problem 3, then thinking of a brute-force way of solving it while in the parking lot, about to drive home. (Too bad I wasn’t further inspired to solve problem 4.)
  • Seeing the pretty pictures of the satellite orbits for problem 4.

Low-lights of the contest:

  • Wasting an hour or so due to bugs in the specification
  • Wasting an hour writing a Tkinter alternative to turtle graphics, then not being able to get a Tkinter window to show up, then realizing that Tkinter graphics are so limited that there’s no feature benefit over using the already-working turtle graphics.
  • The buggy scoring in problem 1 encourages people to program-to-the-scorer rather than solve the stated problem. I could probably increase my position in the standings by 10 places by hacking an “optimal” solution to problem 1 that uses all of the available fuel. But it seems like a waste of time.
  • Having to give up on problem 4.

My advice to (future) contest organizers:

  • Consider avoiding problems that require deep domain expertise. There’s only so much orbital mechanics and numerical methods one can learn in 72 hours.
  • Do whatever it takes to ensure that your VM machine spec is correct. In this case, just asking someone to spend a couple of hours implementing the spec would have exposed the show-stopping problems that everyone encountered.

Advice to myself for future contests:

  • Pace yourself on day two, to avoid burning out on day 3.
  • Be sure you understand the scoring system. For example problem 4 had partial credit, so a solution for problem 3 might have worked on problem 4.
  • Scheduling work and family life to enable a free weekend for the contest worked out very well.
  • Do more planning, and keep an eye on how the work is progressing, to avoid spending too much time on unnecessary work. “What’s the simplest thing that could possibly work”, and “you aint going to need it” are both good mottoes for this kind of contest.
  • Take a little time to refactor the code as you go along, to avoid slowing down due to barnacles. (Example, passing the problem number all over the place because it was one of the inputs to the simulation, rather than special-casing it and setting it once in the VM.)

Analysis of programming languages I used in the contest

I used Python and C. I actually completed the lightning round in pure Python.

Benefits of Python

  • Rapid development due to no compilation time, clean sparse syntax, well designed libraries, plenty of documentation and help available on-line.
  • Turtle graphics made it dead simple to display satellite orbits
  • The “struct” package made it dead simple to import and export binary data.
  • The “subprocess” package made it easy to start and control other programs.
  • Python 3.1’s exact printout of floating point values made it easier to tell what the math was doing. (Other projects ran into problems with almost-zero values printing as zero.)

Drawbacks of Python

  • Slow. I had to switch the simulation to C to have it run fast enough for problems 3 and 4
  • Global Interpreter Lock (GIL) - meant I couldn’t use multiple calculation threads written in Python in one process. (And my machine’s got 8 hardware threads. :-) )
  • Lack of static type checking is frustrating when program run times are long: I had a half-hour period wasted debugging simple errors that only occurred after 2 minutes of simulation run-time that a static type checker would have caught immediately. To be fair, I could also have caught them with unit testing.

Benefits of C

  • Very simple to write code.
  • Runs really fast. :-)

Why My VM’s Cool

I wanted to explain how my VM implementation worked, because I think it probably ran faster than most other VMs.

I wrote a Python-based VM as a reference. Then I wrote a VM generator that would read a VM spec and generate hard-coded C to implement that specific spec. I used a “comparer” VM to compare the output of the two VMs to make sure that there were no bugs in the generated C version.

The hard-coded C VM was really hard coded to each problem. All the VM instruction interpretation overhead was removed. In addition, because the VM didn’t have any indirection, the “mem” array was replaced by hundreds of individual local variables. This allowed the C compiler to do a very good job of optimizing the code, because it could easily tell there was no aliasing.

I included a simple interactive shell in each generated hard-coded C program. The console let you set inputs, run “n” simulation steps, and read the outputs. This made it easy for me to control the simulation from Python. It also made it easy to hand-test the C simulation.

One feature I meant to add, but ran out of time/energy for, was to save and restore the state of the simulation. This would have been very helpful in solving problem 4.

How I solved the problems

Problem 1: Wrote Python VM. Implemented Hohmann transfers as described in a Wikipedia article.

Problem 2: Calculated the correct time to start the Hohmann transfer analytically. (I read about how to do this in a textbook I found through Google books.) Added simple brute-force docking code to match orbits exactly. No fancy “S” curves for me. (And wasted about an hour wondering why I didn’t score, because early versions of the contest problem spec didn’t say you had to turn off your engine for 900 seconds. I finally figured this out by disassembling the VM to see why the score wasn’t being set properly.)

Problem 3: Used my fast VM to compute a table of where the satellites would be over time, then wrote a set of nested for loops that tried various Hohmann transfers at various times looking for a solution. The precomputed tables meant I could just look up where the target satellite would be for any time in the future, rather than having to do complex elliptical math.

Problem 4: Only got as far as simulating and visualizing this one (boy the orbits are pretty!) Too tired to continue. I was planning on using a variation of the brute-force approach that solved problem 3, with save-and-restore of the simulator state, because I would have to recompute the table of locations for my rocket each time its orbit changed.

Conclusions

Upon reflection, I think that this particular contest, especially problems 3 and 4, is best suited to a C/C++ solution. This is due to the heavy reliance on numerical methods to calculate the optimal trajectories.

I liked that there were multiple versions of each problem. It made it easier to tell if we were making progress, and also allowed whole-program-level parallelization to make use of muticore machines to solve the problems in parallel.

While I expect the ultimate contest winners will code in a mutable- state static-type-checked compiled language like C/C++, I predict Haskell will do fairly well in the contest, due to its speed and the ease with which it handles math. However, the winners will probably have a good grasp of orbital mechanics, and it seems that someone who knows the math is more likely to be using C-like-languages.

Well that’s it, now I’m looking forward to next year!

P.S. Here’s a Wiki with other team writeups:

FUN Team ICFP 2009 Writeup / Wiki

Dandy in JavaScript

Dandy game

This weekend I wrote a JavaScript version of my old Atari 800 game Dandy.

Check it out: Web Dandy

It was my first JavaScript application. It was about as easy as writing the Python version. I have only tested it in two browsers so far (Firefox 3.0 and Chrome), and only on one platform, OSX. I have already run into differences between the two browsers: Firefox 3.0 for OSX seems to double-post keydown events.

No sound or multiplayer yet. Oh, and I use the CANVAS tag, so I think older browsers (like IE 7) won’t work.