Oleg's great way of explaining delimited continuations

Posted by Tom Moertel Mon, 05 May 2008 13:58:00 GMT

There’s a great way to explain delimited continuations in the notes of Oleg’s Continuation Fest talk on using delimited continuations for CGI programming. Just so it doesn’t get overlooked, here it is:

I’m obsessed in pointing out that every programmer already knows and understands the delimited continuations; they might not know that word though. Everyone knows that when a process executes a system call like read, it gets suspended. When the disk delivers the data, the process is resumed. That suspension of a process is its continuation. It is delimited: it is not the check-point of the whole OS, it is the check-point of a process only, from the invocation of main() up to the point main() returns. Normally these suspensions are resumed only once, but can be zero times (exit) or twice (fork).

I especially like the final part about exit and fork, which drives home the notion that something more subtle than returning from a typical function call is going on. If anybody is confused over what suspended means, that last part ought to clear things up.

The next time I need to explain delimited continuations, I know how I’m going to do it.

Posted in
Tags , ,
no comments
no trackbacks
Reddit Delicious

That looks about right

Posted by Tom Moertel Fri, 11 Apr 2008 15:58:00 GMT

Via Chris:

$ history | awk '{print $2}' | sort | uniq -c | sort -rn | head
    196 git
    110 l
    102 cd
     70 make
     34 darcs
     30 pushd
     23 ssh
     23 m
     23 ls
     20 rm

The l and m commands are aliases:

  • l = ls –CF
  • m = less

Posted in
Tags , ,
1 comment
no trackbacks
Reddit Delicious

Property checking with Python's nose testing framework

Posted by Tom Moertel Thu, 20 Mar 2008 02:34:00 GMT

At work recently I was writing some tests with Python’s out-of-the-box unit-testing framework unittest. I’m new to Python and accustomed to Perl and Haskell’s testing frameworks, which are lightweight and let you write tests without much hoop-jumping. In particular, QuickCheck and LectroTest make it easy to test at the property level instead of the test-case level. With unittest, I was having to write a lot of code to get the same level of abstraction.

By “property level,” here’s what I mean. Say I’m testing this thing, let’s call it a subscriber pool. It has two fundamental properties:

  1. Subscribe. For all initial states of the pool, if you call subscribe(user), then, assuming there have been no other operations on the pool, user must be in the pool.
  2. Unsubscribe. For all initial states of the pool, if you call unsubscribe(user), then, assuming there have been no other operations on the pool, user must not be in the pool.

That’s it. If my implementation satisfies both properties, it’s correct. (This is a simplified version of my real testing problem, which required additional property checks.)

To test whether my implementation satisfies each property, I must write individual test cases that together “cover” the property. For example, to test whether the Subscribe property holds, I might write four test cases:

class SubscribeProperty(unittest.TestCase):

    def setUp(self):
        initialize_pool()

    def tearDown(self):
        destroy_pool()

    def testEmpty(self):
        load_pool_with_members([])
        subscribe("1")
        self.assert_("1" in pool_members())

    def testOtherGuyAlreadyInPool(self):
        load_pool_with_members(["2"])
        subscribe("1")
        self.assert_("1" in pool_members())

    def testSubscriberAlreadyInPool(self):
        load_pool_with_members(["1"])
        subscribe("1")
        self.assert_("1" in pool_members())

    def testSubscriberAndOtherGuyAlreadyInPool(self):
        load_pool_with_members(["1", "2"])
        subscribe("1")
        self.assert_("1" in pool_members())

Every one of the test cases has the same form. The repetition makes me want to refactor the whole thing.

Okay, let’s do it:

Read more...

Posted in
Tags , , , ,
1 comment
no trackbacks
Reddit Delicious

PXSL Tools 1.0: Your ticket out of XML Hell

Posted by Tom Moertel Tue, 18 Dec 2007 03:33:00 GMT

XML is fine for representing document-like things, but when it’s twisted to represent build recipes, configuration files, and little programming languages, it opens the gates to XML Hell. Once the gates are opened, the demons of cargo-cult thinking are loosed upon the world, where they are free to trick innocent programmers into working with grotesquely twisted XML documents – something no human mind was designed to comprehend. Ensnared, these programmers are slowly drawn into the depths of XML Hell, from which their lamentations echo across the universe.

When the demons of cargo-cult thinking come for you, don’t be ensnared! Instead, be prepared – with PXSL – the Parsimonious XML Shorthand Language (pronounced “pixel”).

What’s PXSL? It’s a luxurious, thermonuclear smoking jacket that you can slip on using a convenient preprocessor. Use it whenever you see grotesque XML on the horizon. Within PXSL’s plush (and stylish) protection, you can create all the nasty, twisted XML that may be demanded of you, but you need not descend into XML Hell to do it. Instead, you can work from the comfort of a well-stocked lounge, where clarity and conciseness are always on tap.

For example, here’s a snippet from an XSLT stylesheet, in the original XML:

<xsl:template match="/">
  <xsl:for-each select="//*/@src|//*/@href">
    <xsl:value-of select="."/>
    <xsl:text>&#10;</xsl:text>
  </xsl:for-each>
</xsl:template>

And here’s the same snippet, written in PXSL:

template /
  for-each //*/@src|//*/@href
    value-of .
    text <<&#10;>>

Isn’t that refreshing?

Why PXSL?

There are lots of XML shorthands available. (The PXSL FAQ lists about ten of them.) So why choose PXSL? Here’s why:

Also, PXSL is battle tested. It was first released in 2003 and has been saving people from XML Hell since. People who try it seem to like it:

  • I think PXSL could do wonders for soothing my irrational hatred for all things XML.kowey
  • Impressive… I converted some of my files from XML to PXSL and the readability was much improved.chris
  • Quite aside from the fact that XSLT is finally somewhat readable, the fact that you’ve added a serious macro system means that some serious scripting of XML can occur. I’m very impressed.invisible

The next time you’re headed for XML Hell, why not give the venerable PXSL a try? You might just find that you like it, too.


This public service announcement was brought to you in celebration of the 1.0 release of the pxsl-tools package. The PXSL-to-XML compiler pxslcc is written in Haskell and uses the cross-platform Haskell Cabal build/package system to let you use PXSL just about anywhere.

Posted in
Tags , , ,
6 comments
no trackbacks
Reddit Delicious

How I stopped missing Darcs and started loving Git

Posted by Tom Moertel Mon, 10 Dec 2007 21:52:00 GMT

About three years ago, I switched to Darcs as my primary source-code management system. It was simple, intuitive, and powerful, and it made managing my projects more fun and less frustrating than any centralized VCS ever had. That it was written in Haskell, one of my favorite programming languages, made it even better. I was hooked.

Since then, the distributed SCM landscape has changed. Darcs hasn’t improved much, but its competitors have made long strides, especially Git and Mercurial. Both are crazy fast, vigorously developed, and widely used on large, highly active real-world projects, such as the Linux kernel and Mozilla 2. In comparison, Darcs has stagnated.

When I started working for a new company recently, I had to consider whether to advocate Darcs or something else. In the end, I decided that Darcs would be a hard sell. Nobody else at the company uses Haskell, and having to explain how to avoid the occasional corner case seemed liked a losing proposition.

After researching and playing around with Git and Mercurial, I settled on Git. I like Git’s underlying hashed-blobs model better than Mercurial’s revlogs, and Git seems to have slightly more development momentum. Still, it was a close call. Either choice would have been completely reasonable.

Missing Darcs

When I started using Git on real projects, the one thing I really missed was the ability to easily amend earlier patches, something Darcs made trivial. Let me explain. The typical development workflow goes something like this:

  1. Checkout copy of upstream code base.
  2. Implement feature X.
  3. Commit.
  4. Implement independent feature Y.
  5. Commit.
  6. Implement independent feature Z.
  7. Commit.
  8. Push new features back upstream.

Now, what really happens is that when I’m implementing Y or Z, I’ll realize that I made a mistake in X. The trick is then fixing X so that my fix is part of the changeset/patch for X that ultimately gets pushed upstream in the last step. That way, the upstream folks will see only a single, clean patch for feature X – not a mishmash of patches that together represent X.

In Darcs, amending the original patch is easy because its patch theory lets me tweak the patch for X independently of the other patches. Darcs will simply ask me which patch I want to amend, and I’ll select the orignal patch for X:

$ emacs               # fix X
$ darcs amend-record  # amend original patch for X

Mon Dec 10 14:43:13 EST 2007  Tom Moertel <tom@moertel.com>
  * Implemented Z
Shall I amend this patch? [yNvpq], or ? for help: n

Mon Dec 10 14:42:12 EST 2007  Tom Moertel <tom@moertel.com>
  * Implemented Y
Shall I amend this patch? [yNvpq], or ? for help: n

Mon Dec 10 14:41:46 EST 2007  Tom Moertel <tom@moertel.com>
  * Implemented X
Shall I amend this patch? [yNvpq], or ? for help: y
hunk ./x 1
-X1
+X2
Shall I add this change? (1/?)  [ynWsfqadjkc], or ? for help: y
Finished amending patch:
Mon Dec 10 14:43:25 EST 2007  Tom Moertel <tom@moertel.com>
  * Implemented X

That’s it. The exact same process will work regardless of when I realize I need to fix X: before I start Y, while I’m implementing Y, after I’ve committed Y, while I’m working on Z, or after I’ve committed Z.

Learning to love Git

With Git, however, I can amend a commit only if I haven’t committed anything else before making my fix. In Git’s mind, Y depends on X, and Z depends on Y, even if they really are independent of one another.

So if I commit the original patch for X and then immediately realize I need to make a fix, before I start working on Y or Z, it’s easy:

$ emacs               # implement X
$ git commit -m 'Implemented X'

# discover problem in X

$ emacs               # fix X
$ git commit --amend  # amend original patch

More typically, it’s only while I’m working on Y that I’ll realize I need to fix X. Then it’s more complicated to amend the original commit:

$ emacs               # implement X
$ git commit -m 'Implemented X'
$ emacs               # start working on Y

# discover problem in X

$ git stash           # stash away half-completed work on Y
$ emacs               # fix X
$ git commit --amend  # amend original patch for X
$ git stash apply     # restore work on Y
$ emacs               # continue working on Y

While not as convenient as Darcs’s workflow, it’s perfectly workable.

Now let’s consider another fairly typical case: I commit X and Y and then start working on Z before I notice the problem in X. I used to think that Git couldn’t handle this case, but it can, thanks to git rebase --interactive:
$ emacs               # implement X
$ git commit -m 'Implemented X'
$ emacs               # implement Y
$ git commit -m 'Implemented Y'
$ emacs               # start working on Z

# discover problem in X

$ git stash           # stash away half-completed work on Z
$ emacs               # fix X
$ git commit -m 'Fixed X'
$ git rebase --interactive HEAD~3  # see comments below
$ git stash apply     # restore work on Z
$ emacs               # continue working on Z
The git rebase --interactive command is powerful. What the command does, as called in the snippet above, is invoke my editor of choice on a text file describing the last 3 commits (that’s the HEAD~3 part):
# Rebasing 3ad99a7..b9a8405 onto 3ad99a7
#
# Commands:
#  pick = use commit
#  edit = use commit, but stop for amending
#  squash = use commit, but meld into previous commit
#
# If you remove a line here THAT COMMIT WILL BE LOST.
#
pick 0885540 Implemented X
pick 320b115 Implemented Y
pick b9a8405 Fixed X

I can then edit the file to reorder, merge (squash), and/or remove the commits. In this example, I want to merge the fix for X into the original commit that implemented X. So I edit the file like so:

pick 0885540 Implemented X
squash b9a8405 Fixed X
pick 320b115 Implemented Y

Then I save the file, at which point Git takes over and makes the requested changes, merging the fix for X into the original commit for X. Now the log shows the original implementation and fix as one commit:

$ git log
commit f387d650976246c0854d028b040cca40e542be56
Author: Tom Moertel <tom@moertel.com>
Date:   Mon Dec 10 15:11:26 2007 -0500

    Implemented Y

commit 82a1c849ffd1bd688d5bc9d99be0e63548a89c4c
Author: Tom Moertel <tom@moertel.com>
Date:   Mon Dec 10 15:13:03 2007 -0500

    Implemented X

    Fixed X

commit 3ad99a7ef537b7ae99e435e0d2b4b0d03de92c65
Author: Tom Moertel <tom@moertel.com>
Date:   Mon Dec 10 15:11:14 2007 -0500

    Initial checkin

Once I figured out how to use git rebase --interactive, I stopped missing Darcs and started loving Git.

Posted in
Tags , , , ,
19 comments
no trackbacks
Reddit Delicious

TMR 9!

Posted by Tom Moertel Mon, 19 Nov 2007 18:07:00 GMT

Issue 9 of The Monad.Reader is hot off the presses! The issue focuses on three Google-Summer-of-Code projects for Haskell: Cabal configurations, Darcs’s Patch Theory, and the typechecker-framework TaiChi. Good stuff.

I know what I’ll be reading for lunch today.

Posted in
Tags ,
no comments
no trackbacks
Reddit Delicious

A couple of tips for writing Puppet manifests

Posted by Tom Moertel Thu, 15 Nov 2007 07:30:00 GMT

I recently started using Puppet to automate my server-build processes. The basic idea behind Puppet is that you create “manifests” that declare a directed graph of “resources” that represents the desired state of your machines. Puppet-managed machines on your network then query a master server to obtain the latest copy of the graph, which they then reconcile with their current states to make whatever changes are necessary to bring themselves up to date.

For the most part, everything works well. I have encountered a couple of snags when writing manifests, however, so I’m going to explain them here as reminder until I get the time to fix them in the Puppet code and send patches upstream.

First, don’t use hyphens in class names. While hyphens are legal in class names, they are not allowed in qualified variables, thus variables defined within hyphen-named classes are inaccessible from the outside world.

Second, and this one is both tricky and important, Puppet handles prerequisites for definitions by silently passing those prerequisites on to all of the resources within the definitions. Definitions, in effect, don’t really have their own prerequisites, they just pass them on to their children. But – and here’s the problem – if those child resources declare their own prerequisites, those prerequisites will overwrite the passed-on prerequisites, effectively causing them to be ignored.

This problem bit me hard when trying to create a definition for installing Ruby Gems from a local cache of gems:

define local_gem($gem) {
    $path = "/var/local/local-gems/$gem" 
    file { $path:
        ensure  => present,
        source  => "puppet://puppet/files/gems/$gem",
        require => File["local-gems-dir"],
        owner   => root,
        group   => root,
        mode    => 0664,
    }
    package { $title:
        ensure   => installed,
        provider => "gem",
        require  => [ Package["rubygems"], File[$path] ],
        source   => $path,
    }
}

The intent was to be able to declare a local gem like so:

local_gem { "sqlite3-ruby":
    gem     => "sqlite3-ruby-1.2.1.gem",
    require => Package["sqlite-devel"]
}

Thus the “sqlite3-ruby” local gem has the single prerequisite of the “sqlite-devel” package – or at least that’s what I expected. What happened on deployment was that the prerequisite was ignored because when it was passed on to the inner file and package resources, those resources had their own require parameters, and those parameters overwrote the passed-on prerequisite.

The work-around is somewhat hacky. I augmented the definition with a do-nothing resource that has no require parameter of its own. This resource does nothing but capture the passed-on prerequisites. Then I made all of the other resources in the definition include the do-nothing resource as one of their prerequisites. Thus they are made to inherit the passed-on prerequisites.

My final definition looks like this:

define local_gem($gem) {

    # dummy exec to propagate requires from local_gem
    exec { $name: command => "/bin/true" }

    $path = "/var/local/local-gems/$gem" 
    file { $path:
        ensure  => present,
        source  => "puppet://puppet/files/gems/$gem",
        require => [ Exec[$name], File["local-gems-dir"] ],
        owner   => root,
        group   => root,
        mode    => 0664,
    }
    package { $title:
        ensure   => installed,
        provider => "gem",
        require  => [ Exec[$name], Package["rubygems"], File[$path] ],
        source   => $path,
    }
}

Notice how the file and package resource both require the dummy exec resource. That’s the trick that allows them to require the prerequisites passed on from the local_gem definition.

It’s not pretty, but it works. See this email on the puppet-users mailing list for more on the problem.

Posted in
Tags , , ,
no comments
no trackbacks
Reddit Delicious

How to download photos and movies from the Palm Centro to a Linux desktop

Posted by Tom Moertel Fri, 02 Nov 2007 19:32:00 GMT

I recently got a Palm Centro smartphone, and so far I love it. Like most modern cell phones, it has a built-in camera and takes decent snapshots and even records short movies. It’s great for spur-of-the-moment shots when I don’t have my real camera. The trick – and there’s always a trick when it comes to cell phones – is getting the photos off the camera and onto my computer.

To get at my pictures, Sprint would prefer that I sign up for their ludicrously expensive “PictureMail” service. Leave it to weasely telecom execs to come up with another way to squeeze money from teenagers: charge them $5 each month for the “privilege” of sharing their pictures with friends. This fee, of course, is in addition to the fee for “unlimited” mobile Internet use. I guess picture bits are somehow more expensive to move over the air than other kinds of bits.

In any case, my next goal after getting my Centro to hotsync with my Linux workstation was to figure out how to download my photos and movies.

After a bit of hacking, I figured out that the Centro stores images in a typical digital-camera-image (DCIM) hierarchy. For example, I have a 4-GB microSD card installed in my Centro, and I store my photos in the “Palm” album on it. This album ends up stored in the /DCIM/Palm directory on the card.

Using the pilot-xfer program from the pilot-link project, I was able to find the directory and its contents. The trick was to use the sparsely documented –D flag to work with the Centro’s virtual filesystem. Here, for example, is how I list the contents of the Palm album:

$ pilot-xfer -p usb: -D /DCIM/Palm -l

   Listening for incoming connection on usb:... connected!

   Directory of /DCIM/Palm...
        652 Fri Nov  2 08:17:06 2007  Album.db
     292053 Fri Nov  2 09:04:20 2007  Photo_110207_001.jpg
      78493 Fri Nov  2 08:17:06 2007  Video_110207_001.3g2
         20 Wed Oct 31 12:09:20 2007  Thumbnail.db

   Thank you for using pilot-link.

Here, you can see that I have one photo and one movie in the album. (Movies are stored in .3g2 files that contain MPEG4 video.)

To download the files, I again turned to pilot-xfer, this time using the –f (fetch) flag to fetch a list of files. Here, for example, I’ll fetch the image from the listing above:

$ pilot-xfer -p usb: -D /DCIM/Palm -f Photo_110207_001.jpg

   Listening for incoming connection on usb:... connected!

   Fetching '/DCIM/Palm' ... (292053 bytes)   285 KiB total.

   Thank you for using pilot-link.

So that’s the process. It’s kind of clunky, so I wrote a small Python program to automate it. (I’m learning Python. If you’re a Pythonista, please consider critiquing my code. I would be especially thankful if you could point out any helpful idioms that I may have overlooked.)

Here’s how to use the program:

$ get-pilot-photos.py --help
Usage: get-pilot-photos.py [options]

Options:
  -h, --help            show this help message and exit
  -s SRCDIR, --srcdir=SRCDIR
                        VFS dir on Palm device from which to fetch images
  -d DESTDIR, --destdir=DESTDIR
                        Where to save the images on your computer

Both the —srcdir and —dstdir options are optional. If you omit the first, the program will download photos and movies from the /DCIM/Palm album. If you omit the second, the program will save the downloads to a new, timestamped directory within your home directory.

That’s it. The code is below.

Read more...

Posted in
Tags , , , , , ,
10 comments
no trackbacks
Reddit Delicious

How to hotsync the Palm Centro with a Fedora 7 Linux desktop via USB

Posted by Tom Moertel Wed, 31 Oct 2007 04:35:00 GMT

I just got a Palm Centro smartphone, and I love it. Getting it to sync with my Linux workstation, however, was tricky, so I’m posting this recipe in hopes that it might save you some time.

The “visor” kernel driver is supposed to make compatible Palm handhelds look like serial devices when attached via a USB cable. For me, it didn’t work. Instead, I had to blacklist the driver and then use libusb to talk to the Centro. Here’s the recipe:

First, blacklist the “visor” kernel driver:

# echo blacklist visor >> /etc/modprobe.conf
# modprobe -qr visor

Second, make sure libusb is installed:

# yum install libusb

Third, edit the system’s udev rules to make sure your user account can access the device files used to talk to the Centro. On my Fedora 7 setup, I found the right rule in /etc/udev/rules.d/50-udev.rules:

ACTION=="add", SUBSYSTEM=="usb_endpoint", \
ATTR{bEndpointAddress}=="?*", ATTRS{devnum}=="?*", ATTRS{busnum}=="?*", \
NAME="bus/usb/$attr{busnum}/$attr{devnum}_ep/$attr{bEndpointAddress}", \
MODE="0644", SYMLINK+="%k" 

I edited the last line of the rule, changing the mode to 0664 and adding a GROUP key to assign the Centro devices to my exclusive user group:

MODE="0664", SYMLINK+="%k", GROUP="thor" 

This change lets my account talk to the Centro without having to take on root privileges. (For bonus points you could set up a more-specific rule to match just your Centro. The rule above, as is, will actually match other devices, too.)

Fourth, tell udev to reload the rules:

# udevcontrol reload_rules

Finally, set up a Palm-device connection via gnome-pilot. Be sure to select USB for the Type and “usb:” from the Device drop-down list.

That’s it. If you’re lucky like me, you should now be ready to hotsync your Palm Centro!

Update: Even better, this handy HOWTO shows you to sync via Bluetooth, which is more convenient than hooking up a USB cable. I’m now using this method.

Update 2: If you want to use USB to hotsync your Centro, there is a method that’s more convenient than setting up udev rules. Just create a perms file for pam_console_apply that tells it to give the console user permission to access your Centro. To do so, create a file /etc/security/console.perms.d/60-libpisock.perms and put the following in it:

<libpisock>=/dev/usbdev* /dev/bus/usb/[0-9]*/[0-9]*
<console> 0644 <libpisock> 0644 root

That’s it. (You’ll still need to use libusb.)

Posted in
Tags , , , , ,
4 comments
no trackbacks
Reddit Delicious

Perl helps prove universality of 2, 3 Turing machine

Posted by Tom Moertel Fri, 26 Oct 2007 17:23:00 GMT

Alex Smith, a 20-year-old EE student in the UK, proved that the 2, 3 Turing machine is universal. In doing so, he was able to claim the $25,000 prize that Stephen Wolfram offered for the first proof (or disproof) of the 2, 3 machine’s universality.

This story has been getting a lot of attention lately, but one part of the story has not: that the Perl programming language is featured in the proof. In his documentation of the proof, Universality of Wolfram’s 2, 3 Turing Machine, Smith wrote, “I have written several Perl programs, to demonstrate the constructions given in the proof and to interpret the systems given in various conjectures.” Smith’s proof includes no fewer than 7 Perl programs.

Go Perl!

Posted in
Tags , ,
1 comment
no trackbacks
Reddit Delicious

Older posts: 1 2 3 ... 15