Posted by Tom Moertel
Thu, 21 Aug 2008 01:50:00 GMT
Although at work I code mostly in Python – a language from which
lambda and map were nearly removed – I still find that functional-programming experience
has its benefits. One of the
“functional-programming dividends” I notice most often is insight
gained from considering problems from an algebraic perspective.
Recently, for example, I had a small parsing problem. I had to
write code that, given a simple grammar specification as input, emits
a regular expression that matches the language generated by the
grammar.
Here’s a simplified version of the problem. A grammar specification
is limited to a series of one or more atoms. For example, “a b c”
represents the atom “a”, followed by the atom “b”, followed by the
atom “c”. To generate the grammar, the series of atoms is interpreted
such that each atom (except the last) generates a production rule of
the following form:
atom_rule ::=
<the literal atom> (SPACE <the next rule> | NOTHING)
(SPACE represents literal white space and NOTHING represents an
empty string.) The grammar as a whole is rooted in the first atom’s
rule.
Thus the specification “a b c” represents the following grammar:
grammar ::= a_rule
a_rule ::= "a" (SPACE b_rule | NOTHING)
b_rule ::= "b" (SPACE c_rule | NOTHING)
c_rule ::= "c"
Note that the final atom’s production matches only the literal atom
itself: it has no following rule on which to chain.
The grammar, in turn, generates the following language:
a
a b
a b c
Thus, given the grammar specification “a b c”, my code had to produce
a regular expression that would match “a”, “a b”, or “a b c”.
At this point, please stop for a moment and think about this little
programming exercise. Do any solutions leap to mind? How would you
approach the problem? Form your opinions now, because I’m going to
ask you about them later. (If you’re feeling especially caffeinated, try
coding a solution before reading on.)
Read more...
Posted in functional programming
Tags folds, fp, haskell, python
20 comments
no trackbacks
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:
- 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.
- 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 testing
Tags nose, properties, python, testing, unittest
1 comment
no trackbacks
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 hacks
Tags centro, download, hotsync, images, movies, palm, python
15 comments
no trackbacks
readers