Tuesday, April 19, 2011

Call Me Crazy: Calling Conventions

It's been said that the most significant contribution to computer science was the invention of the subroutine. Every major programming language has its own variation on how subroutines work. For instance, there are procedures, functions, methods, coroutines, etc. When implementing a compiled language or a virtual machine, you must decide how to implement subroutines at the assembly language level. For instance, you must decide how to pass arguments, what goes on the stack, what goes on the heap, what goes in registers, what goes in statically allocated memory, etc. These conventions are called calling conventions. You might not think of calling conventions very often, but they're an interesting topic.

First of all, what does a subroutine provide over a simple goto? A subroutine provides a way to pass arguments, execute a chunk of code, and return to where you were before you called the subroutine. You can implement each of these yourself in assembly, but standardizing calling conventions in a language makes the process more stable, repeatable, and less prone to error.

The way you implement calling conventions in a language like C is at least conceptually something like the following. You push all your arguments onto the stack; you push your current location in the code (i.e. the IP register) onto the stack; and then you jump to the subroutine. The subroutine executes its code, puts its return value in a register, and then jumps to the return-to address you put on the stack. The caller is responsible for popping the arguments off the stack (this is necessary to support varargs). Often, the compiler may optimize the code by putting values into registers rather than on the stack.

What's the difference between subroutines, procedures, functions, and methods? I think of subroutines as a low-level, catch-all term. In Pascal as well as some other languages, a procedure is expected to have side effects but not return a value, whereas a function is not supposed to have side effects but is supposed to return a value. Of course, not having side effects is a convention, not something enforced by the compiler. A method is a function call on an object. Typically, the object is implicitly passed as the first argument, although that may not be explicit in the syntax for the language.

Coroutines are a twist on subroutines. When you call a subroutine, it'll eventually return to the caller. If A calls B, then eventually B will return to A. Coroutines don't have to behave in this manner--i.e. they don't have to return to the caller. A may call B which may call C which may call A in a circular manner, without maintaining a stack of return-to addresses.

Recursion is a technique in which a function can call itself. Some languages like Lisp provide recursion as a low-level operation, and all looping constructs are built on top of recursion. There are some algorithms that are more elegantly implemented using recursion than looping such as the Ackermann function.

Recursion implies that you have some sort of stack (whether or not you use a C-level stack). That's because if a function takes one argument and recurses five times, you need a places for five arguments. Languages like COBOL put arguments in statically allocated memory instead of on a stack. Hence, COBOL lacks recursion.

Tail call optimization is an interesting technique that reduces the use of the stack. If function A calls function B, and then B's last step is to call function C, rather than having a return-to address for A and a return-to address for B, you can just have C return directly to A since there's nothing else in function B that needs to be done.

This works really well when a function calls itself as its last step. If F calls itself as its last step, rather than having a large stack of return-to addresses for F, you can optimize it away. In this way, what would normally be a recursive algorithm can be translated into simple interation. This is a critical technique in languages like Lisp that rely on recursion for looping; however, it's not present in languages like Python. (Guido van Rossum has argued that it's harder to debug bugs if parts of the stack have been optimized away. It's possible to end up in a function with no way of knowing how you got there.)

Stacklessness is a technique whereby the language's stack does not rely on an assembly or C-level stack, but rather exists on the heap. Because of the way C stacks require contiguous space, it's difficult to allocate space for 1000s of them at the same time. In a stackless interpreter, because stack frames are allocated dynamically from the heap, you can allocate a greater number of them stacks. This technique is used by stackless interpreters such as Lua as well as the greenlets library in Python in order to implement something like lightweight multithreading.

Some languages provide more flexibility than others in the way arguments are passed. C has the ability to pass a fixed number of arguments, but there's also a facility to pass an arbitrary number of arguments call varargs. Some languages like Perl and Ruby allow you to pass additional keyword arguments in the form of a hash to the function (e.g. "f(1, 2, :arg => 1)"). Some languages like Common Lisp and Python have advanced support for keyword arguments allowing you to call a method that looks like "def f(a, b, c=1, d=2, e=3)" like "f('a', 'b', e=3, d=3)". Notice that you can leave out or rearrange the order of keyword arguments. Python allows you to pass a variable number of positional arguments as well as a variable number of keyword arguments and it will even raise an exception if you pass a keyword argument that isn't expected. Common Lisp was one of the first languages to have extremely sophisticated parameter passing, including sophisticated support for keyword arguments.

Currying is a technique whereby if a function accepts two parameters, A and B, then what you really have is a function that takes an argument A and then returns another function that takes an argument B. In this way, all functions can be reduced to a list of functions that accept 0 or 1 arguments. When a language supports currying, you can pass a value for A and then later pass a value for B. Haskell supports currying.

Partial application is a related technique that lets you pass an arbitrary number of arguments, perhaps in a random order if keyword arguments are supported, and then actually call the function later. If you have a function that takes one parameter, then you can partially apply it to one argument, and you are left with a function that takes no parameters that you can call at a later time. Partial application is more general than currying. It's supported in Python. However, in languages like Python, Haskell, Lisp, etc., it's always possible to create a new function that takes no parameters that simply executes another function passing a particular value to that function. Hence, it's trivial to implement partial application manually.

Lazy evaluation is a technique whereby the arguments to a function are not evaluated until they are used within the function. If you call f(1/0) in Python, you will always get a DivisionByZero exception. However, in languages such as Haskell, if you call f (1/0), as long as f never evaluates its argument, you'll won't get an error. Languages that do not have lazy evaluation are said to be "strict". Hence, Haskell is not strict.

It is an error prone situation to have a language that is not strict (i.e. it supports lazy evaluation) but also supports side effects. For instance, consider writing the expression f(print(1), print(2) in a language that wasn't strict but permitted side effects. Depending on whether or not f evaluated its parameters, 1 and 2 may or may not be printed, and you couldn't be sure which order they would be printed in. Hence, functions in Haskell are both lazy and side-effect free.

Inlining is an optimization technique that helps avoid the overhead of a function call. If a function A calls a very small function B, an optimizing compiler might take a copy of the compiled code for B and put it "inline" in the compiled code for A. This reduces the function call overhead but results in larger binary sizes.

In some situations, some compilers can aggressively inline all functions. Alternatively, the compiler may be able to put all the code for all the functions side by side and simply jump between the different parts of the code without using the stack. Some programmers use this technique manually in order to write small, but highly efficient programs. In general, the way you think calling conventions work in a language may be a simplified, idealistic way of how they actually work. In the case of inlining, the function call completely disappears.

Continuation passing style is a technique whereby all function calls can be transformed in a way that makes tail call optimization possible. Consider the following function:
def sum(n):
if n == 0:
return 0
return n + sum(n - 1)
This function cannot natively take advantage of tail call optimization because after it recurses, the return value must be added to n. It's easy to change this to a function that takes advantage of tail call optimization manually:
def sum(n, _accum=0):
if n == 0:
return _accum
return sum(n - 1, _accum + n)
In this case, an accumulator is passed explicitly. (Remember, however, that even though I'm using Python syntax, Python does not support tail call optimization.)

Rather than passing an accumulator that contains a value, you can pass an accumulator that contains what other code needs to execute after the recursive call. Here is an example of that:
def sum(n, _callback=lambda x: x):
if n == 0:
return _callback(0)
return sum(n - 1, lambda x: _callback(x + n))
By the way, if you find that code difficult to understand, don't feel bad! It took me more than half an hour to write it, despite the fact that I had seen the technique before! That goes to show you that switching to continuation passing style isn't easy. However, it can be accomplished via a mechanical (i.e. "just follow the steps") process, and there are languages that can do it for you automatically. Scala has a compiler flag that turns on continuation passing style so that the JVM behaves differently (conceptually it uses a lot of anonymous functions that exist on the heap rather than return-to addresses that exist on the stack).

Returning to C, you might think that the calling conventions of C were decided upon years ago, and the only variations would have to do with compiler optimizations. Surprisingly, that is not the case. For instance, AMD helped define the new calling conventions for System V on AMD64. In fact, the calling convention are neither C nor AMD64 dependent. It's entirely defined by the operating systems application binary interface standard. Hence, the calling conventions for AMD64 systems are slightly different under Windows (specifically in relation to what registers are used to pass variables). See here and here for more information.

So if you're thinking about implementing a new language, and you wonder what's in a subroutine, you make the call!

Perl: Text-based Address Books

Over the years, I've stored my addresses in a variety of formats. I used to have a Palm Pilot. These days, I have an Android phone, and Google keeps track of my addresses. However, I've always had a second copy of my addresses in a text file. The format looks something like this:
A & R Stock to Performance:
Address: 2849 Willow Pass Rd. #A, Concord, CA 94519
Work Phone: (925) 689-1846
There are many advantages to using a text-based format. For instance, since I'm an expert Vim users, I can search and edit the file extremely quickly. Best of all, the format works on every operating system and never goes obsolete. The only downside is that I have to input the address twice: once for Google and once for my own notes.

Long ago, I wrote a Perl script to convert my notes file into a Palm Pilot database. Even though I don't have a Palm Pilot anymore, I keep the script around. I can easily alter it to output the addresses in different formats.

If you like the format I used above, here's the source code so that you can hack it to do whatever you want:
#!/usr/bin/perl -w

# Author: Shannon -jj Behrens
# Email: jjinux@gmail.com
# This program converts the addresses stored in my notes file into a Palm
# database file (a pdb), which I can then import into my Handspring Visor.
# See usage for more details.
# Global variables:
# $_0 - This is $0, but without the path.
# $pdb:: - This is a handle to the Palm address database being edited.

# %phone_mappings - Mappings from things such as "Cell" to integers. These
# values were deduced from the @Palm::Address::phoneLabels array as well
# as usage in my notes.txt file.
%phone_mappings:: = (
Work => 0,
Home => 1,
Fax => 2,
Other => 3,
Email => 4,
Cell => 7

# $MAX_PHONES - The maximum amount of "Phone" type fields.
$MAX_PHONES:: = 8;

use strict;
use Palm::PDB;
use Palm::StdAppInfo;
use Palm::Address;

# Output usage information to the user and exit with value 64 (see man
# sysexits on a FreeBSD machine).
# By the way, here's how I use this program:
# mkdir palm
# pilot-xfer -b palm
# ./notes_to_palm ~/notes.txt palm/AddressDB.pdb
# pilot-xfer -r palm
# rm -r palm
sub usage {
print "usage: $_0:: notes.txt AddressDB.pdb\n";
exit 64;

# There's an ugly "bug" that causes Perl 5.6 to complain about unamed
# categories. Hence, I have to do a little bit of initializing or else I get a
# whole bunch of uninitialized warnings.
sub init_category_names {
for (my $i=0; $i < Palm::StdAppInfo::numCategories; $i++) {
if (!defined($pdb::->{appinfo}{categories}[$i]{name})) {
$pdb::->{appinfo}{categories}[$i]{name} = "";
$pdb::->{appinfo}{dirtyFields} = 1;

# Return a new record. I have to do a little bit of initializing or else I get
# a whole bunch of uninitialized warnings. I wonder why the libraries don't do
# this automatically since they initialize everything to undef anyway. Also,
# I'll insert a phoneIndex variable into the $record so that I can use the
# phone slots on a first come first serve basis.
sub new_record {
my $record = $pdb::->new_Record;
foreach my $field (qw( name firstName company phone1 phone2 phone3
phone4 phone5 phone6 phone7 phone8 address
city state zipCode country title custom1
custom2 custom3 custom4 note )) {
$record->{fields}{$field} = "";
$record->{phoneLabel}{reserved} = 0;
$record->{fields}{phoneIndex} = 1;
return $record;

# Process a name line, such as "Shannon -jj Behrens (author)".
sub handle_name {
my ($fullname) = @_;

# Check for note.
if ($fullname =~ /^(.*)\((.*)\)/) {
$fullname = $1;
$record::->{fields}{note} = $2;

# Assume last word is last name, everything else is first name.
my @name = split / /, $fullname;
$record::->{fields}{name} = pop @name;
$record::->{fields}{firstName} = join " ", @name;

# Process a phone type (e.g. Cell) and a value (e.g. "(925) 209-6439"). Please
# read p5-palm's Address.pm module to see the interesting way Palm phone
# numbers work. When possible, use the email address as the primary "Phone"
# field.
sub handle_phonelike_field {
my ($type, $value) = @_;

my $phone_index = $record::->{fields}{phoneIndex};
return if ($phone_index > $MAX_PHONES::);
my $phone_field = "phone$phone_index";
$record::->{fields}{$phone_field} = $value;
$record::->{phoneLabel}{$phone_field} = $phone_mappings::{$type};
$record::->{phoneLabel}{display} = $phone_index - 1
if ($type eq "Email");

# Process an address line, such as "125 Gilger Ave., Martinez, CA 94553".
sub handle_address {
my ($fulladdress) = @_;

my @address = split /, /, $fulladdress;
$record::->{fields}{address} = $address[0];
$record::->{fields}{city} = $address[1];
my @state_zip = split / /, $address[2];
$record::->{fields}{state} = $state_zip[0];
$record::->{fields}{zipCode} = $state_zip[1];

# Handle one line, $_, from the notes.txt file. Remember, there must be at
# least one blank line after every address record in the notes.txt file in
# order to flush it to disk.
# Creates globals: $section::, $record::.
sub handle_line {
# Ignore anything not in the Contacts section.
if ($_ =~ /-{5,} ([^\-]+) -{5,}/) {
$section:: = $1;
return if (!defined($section::) or
$section:: ne "Contacts");

# A blank line is a signal to flush the current record, if any. Otherwise,
# it can just be ignored.
if ($_ =~ /^[ \t]*$/) {
if (defined($record::)) {
$record:: = undef;
return ;

# If the line doesn't start with a space, this is a new record's name.
# Start a new record, and then handle the name.
if ($_ =~ /^([^ ].*):/) {
my $fullname = $1;
$record:: = new_record;
handle_name $fullname;

# Check for phone numbers and email addresses.
foreach my $type (keys %phone_mappings::) {
if ((($type eq "Email") and ($_ =~ / Email: (.*)/)) or
(($type ne "Email") and ($_ =~ / $type Phone: (.*)/))) {
handle_phonelike_field $type, $1;

# Check for address.
if ($_ =~ / Address: (.*)/) {
handle_address $1;

# Check for company.
if ($_ =~ / Company: (.*)/) {
$record::->{fields}{company} = $1;

# Anything else can be appended to the additional notes section.
$record::->{fields}{note} .= $_;
print STDERR "Additional notes: $_";

my @pieces = split /\//, $0;
$_0:: = $pieces[$#pieces];
usage if (scalar(@ARGV) != 2);
my $notes = shift;
my $addresses = shift;
open(NOTES, $notes) || die "$_0::: $notes: $!\n";
$pdb:: = new Palm::Address;
handle_line while (<NOTES>);
close NOTES;

Of Neuroscience and Jazz

I am neither a neuroscientist nor a very accomplished musician, but I'd like to talk about the intersection of neuroscience and music. I have a theory that there is a neuroscience basis for why it takes a mature musical palate to enjoy jazz.

First, let me say a little something about neuroscience (based on the limited understanding I've gained by watching a bunch of talks). One of the things your brain is particularly good at is recognizing patterns and predicting patterns. At the lowest level, if two nerves are close to each other, and they both fire, it's counted as a pattern--i.e. those two things are connected. Similarly, if a nerve fires and then a short while later it fires again, that's a pattern as well. Hence, if both of my fingers feel something, there's a pattern, or if I feel a tapping on a single finger, that's a pattern as well.

However, the brain is not limited to low level patterns. Rather, it can respond to a hierarchy of patterns. Paraphrasing Pavlov, if a dog hears a can opener and then smells food and then gets fed, we all know that the dog will soon recognize the pattern and start salivating as soon as he merely hears the can opener. My point is that a sophisticated pattern is composed of lower level patterns recursively, all the way down to the level of individual neurons firing.

Next, let me talk about sine waves and chords. Let's start with a single note. A single note might look something like y = sin(x):This wave is very simple, and somewhat boring.

(By the way, I'm using wolframalpha.com to create these graphs. WolframAlpha is really interesting. It's a computational knowledge engine, and graphing things is just one of a ton of things it can do.)

Now, let's look at a chord consisting of a single note as well as the note that is an octave above it. Here's y = sin(x) + sin(2 * x):This curve is somewhat more sophisticated. However, you can still recognize the pattern by the time x = 10.

Now, let's look at what I think is a fifth, which is still a nice sounding chord. Here's y = sin(x) + sin(1.5 * x):This pattern is slightly more sophisticated, but it's still pleasingly recognizable.

Now, let me show you something that is not pleasing to the ear. This curve represents what might happen if you hit two keys that are right next to each other on the keyboard. Here's y = sin(x) + sin(1.1 * x):This curve pulses in an ugly way. You have to get all the way out to x = 120 or so to even see the pattern. In a manner of speaking, the pattern is only there by "brute force".

So what's my point? Simple patterns are easy to recognize, and they can be recognized in less time (i.e. for smaller variations of x, which I probably should have called t).

Here's something that I think is more of a jazz chord. Here's y = sin(x) + sin(1.25 * x) + sin(1.5 * x) + sin(2 * x):This curve is really interesting. You can recognize what's going on by the time you get to x = 50, but the "texture" of the curve is a lot more interesting. Whenever I play this sort of chord, it sounds deep, rich, and interesting. If the first chord reminds me of "Mary had a Little Lamb", this last chord reminds me of the forbidden love between Lancelot and Guinevere and the pain it caused King Aurthur.

So what's my point? You have to go higher up the pattern recognition pyramid in order to recognize more sophisticated patterns. A more sophisticated musical palate is able to recognize patterns that a simpler musical palate may not recognize. That's why jazz requires a sophisticated palate--it uses chords that require more effort to recognize.

Of course, there are many dimensions to music, and individual chords are just one dimension. There are also chord progressions and beats. The same sort of thing applies to these other dimensions.

Here's the circle of fifths (thanks Wikipedia!):Pick any three chords in a row on the circle of fiths, such as C, G, and D, and you have the basis for a simple, feel-good song. If you just bounce around between the different chords on a guitar using different strumming patterns, you'll immediately recognize a song you already know or create a new song that sounds pleasing. Throw in a few 7th chords and a few minor chords, and the song starts taking on additional richness because the pattern becomes less simple.

If you try to use more than three chords from the circle of fifths, your brain might be left thinking, "Wait a minute. What key am I supposed to be in?" It may be more difficult to recognize the pattern. However, this is exactly the sort of thing that happens in jazz.

The same thing applies to beats. Here's a simple walz, "Um pa pa. Um pa pa." Here's a typical rap beat, "Bum chbum bum chbumbum ch bum bum ch." More sophisticated beats require more sophisticated pattern recognition.

Every song is composed of some pattern repetition and some pattern violation. Simple, pop songs that are enjoyable by youthful palates involve a lot of pattern repetition and less pattern violation. Sophisticated music palates enjoy songs with less pattern repetition and more pattern variation. Furthermore sophisticated music palates get bored of songs more quickly. They recognize the patterns quickly, and they're ready to move on.

Furthermore, popular songs are played more often on the radio so that your brain has a better chance to become more familiar with the patterns. A listener will usually enjoy the song more after listening to it 10 times than if he's only listened to it once. If a song has so much pattern repetition that you enjoy it the first time, you'll often grow bored of it very quickly. Conversely, it's very difficult to enjoy sophisticated classical pieces the first time you hear them. All the popular classical pieces have been driven into our heads since we were kids.

Why is this? I think this can be explained by neuroscience as well. The brain works hard to find patterns, and when it does, the simple recognition of a pattern is somewhat calming. It's says something like, "Hmm, I've seen that pattern before. Coooooool." However, if a pattern is repeated too often, the brain starts to filter it out; it becomes boring. It says, "Nothing new here. Pay attention to something else." Pattern violations catch your attention. You brain says, "Hey, wait a second. I didn't expect that! You should pay attention because something new is happening!" Hence, composers must always straddle the line between calming pattern repetitions and exciting pattern violations. How far you go in either direction dictates how sophisticated a musical palate will be required to enjoy the song, and thus, who will enjoy it.

Ok, so that's my theory of neuroscience and music. I don't have any MRIs to back it up, nor do I have the educational background to claim real expertise on the subject. Nonetheless, I think there's some truth to it.

Gaming: How Do Characters Know What to Say?

My wife and I like to play games like Paper Mario together. Paper Mario is a long game with a lot of dialog. At any point in the game, you can talk to any character, and that character will say something "sensible". For instance, they'll ask you to help them out, or they'll thank you if you've already helped them out. I've always wondered how that's coded. Similarly, I've always wondered how many ways I could think up to code it.

The simplest approach is to use a complicated set of possibly nested if/else statements. For instance, if Mario has this item, then say this. Otherwise, if he has beaten this level, say that. Certainly that's a valid approach, and it doesn't even matter if it's slow. Since people read so slowly, trying to optimize how quickly you can come up with what text to show next is absolutely the last thing you would ever need to optimize in a video game.

At the opposite extreme, this problem could be solved with a rules engines. There are libraries that let you wrangle control of complex if/else hierarchies. (The first time I heard about rules engines was when I was interviewing at a consulting company where they were building a welfare system for various counties in California. Apparently, the rules surrounding welfare systems are so complex that a rules engine is a necessity.)

You can also use a mix of if/else statements and switch statements. For instance, the main game is a mostly linear progression from one state to the next, which is easily solved by a switch statement. If you are in this state, say this. If you're in that state, say that. However, sometimes Mario goes on side quests. In cases like that, a particular character might need to have a separate switch statement to know what to say for that side quest.

Similar to using a switch statement, you can use a non-sparse array per character where each state is an index into that array, and each spot in that array has a pointer to a message. Since the array contains every state, many of the states will point to the same message.

You can create a mapping from state to message using a sparse tree. To find out what to say, traverse the tree to find the state that is closest to, but still less than the current state. A sparse tree has a benefit over a non-sparse array in that the tree is only as large as the number of messages the character might say.

Rather than having an array of states for each character, you could also have a single array of states for the entire game. When you save the player's position in the game, you simply save his index into the array. The first spot in the array has a mapping of what every character would say at the beginning of the game. Each new spot in the array has a list of updates for all the characters who would say something different for that new state. This works like a database transaction log. Since there are only a few hundred or a few thousand characters, you can easily store in memory what each character would say at the current state in the game.

I'm going to take a guess and say that they probably just used a simple set of nested if/else statements, but it's kind of fun to think of other approaches.

Monday, April 18, 2011

Ruby: My Take on Pivotal Labs, Part II

As I mentioned in my previous post, I have tremendous respect for how Pivotal Labs builds software. In this blog post, I want to cover why practices used at Pivotal Labs may not always be appropriate at other companies. The core of my argument is that Pivotal Labs is a consultancy; hence, their priorities are not always the same as the priorities for a startup building its own software.

First of all, let me talk about full-time pair programming. In the book Professional Software Development, Steve McConnell states that NASA discovered that the single most effective way to reduce defects (in manufacturing, etc.) is to always have a second pair of eyes present (i.e. to work in pairs). However, NASA must go to extreme lengths to avoid defects because lives are on the line. That's rarely the case with most startups. Most defects are merely embarrassing. In many cases, code review may be more efficient than full-time pair programming. In some cases involving purely aesthetic matters, it may sometimes be acceptable to even skip the full code reviews and settle for aesthetic reviews instead.

Full-time pair programming is also a great way to train newbies. It's definitely in Pivotal Lab's interest to have all of its employees extremely well trained and interchangeable. However, it's really the customer that's paying for this training, and it's certainly expensive. In a startup building its own code, this expense may not be warranted. Certainly, there's huge value in having overlap between employees so that no one employee who gets hit by a bus can take out the entire company. However, some specialization may be appropriate. When I worked at IronPort, we had a low-level, FreeBSD kernel guy. He spent a lot of time tweaking the kernel in a way that only a FreeBSD kernel guy can. We also had people who specialized in JavaScript. Expecting every person to be capable of pair programming on FreeBSD kernel development as well as ajax hacking is simply asking for too much, and it's too expensive in terms of programmer time. Sometimes a little specialization can be helpful.

Full-time pair programming may also help a particular task get done faster. However, if you have a limited number of engineers at a small startup, certainly the total time to completion for all programming tasks will go down if all programming must be done in pairs. Pivotal Labs has the advantage that they can scale up the number of people on a project if a job calls for it, and they make more money when they do so. It's the opposite at a small startup. The number of programmers at a small startup is often somewhat limited and fixed, and there are economic advantages to getting more done with fewer people. If you only have two programmers, and one of them is a Ruby expert and the other an ActionScript expert, it might be best to just let them do their thing individually so that at least two things are getting done at the same time.

Don't get me wrong. I'm not saying that pair programming isn't extremely valuable. I'm just saying that full-time pair programming is extremely expensive, and sometimes the cost isn't justifiable for smaller startups that aren't consultancies.

The next thing I'd like to cover is tests. Pivotal Labs writes a lot of tests. It makes sense for them because they get paid to write them, and they never want to get caught with their pants down. If Pivotal Labs has a choice of implementing two features with a 30% chance of having a defect or of implementing one feature with a 2% chance of having a defect, they're only going to implement one feature. Since they don't get paid by the feature, they get paid the same either way.

The economics just aren't the same at a startup building its own software. Don't get me wrong--I really appreciate the value of testing, but I also try to keep in mind the cost. My approach to building software at a small startup is to consider the return on investment when writing tests. Some tests provide a very high return on investment. They catch a lot of potential bugs and require very little work. I'm thinking of high-level Cucumber and Webrat tests. Some tests require a lot of work, but don't catch very many actual bugs. I'm thinking of view tests. A view test neither tests that a view looks right, nor does it test that its interface with the controller is correct. My point is that it may be in Pivotal Lab's best interest to implement view tests, but if I'm working at a small startup that isn't a consultancy, it probably isn't in my interest to implement view tests.

So what's my point in bringing all of this up? As much as I appreciate how Pivotal Labs does things, I understand that those practices may not always be appropriate for a small startup building its own software. It reminds me of that old essay, The Rise of "Worse is Better". As much as I hate to admit it, sometimes worse is better.

Ruby: My Take on Pivotal Labs, Part I

Pivotal Labs is one of my favorite companies. I have a tremendous amount of respect for how they develop software. They put the "extreme" in extreme programming, and more importantly, they get stuff done. However, there are some things that Pivotal Labs tend to do that I disagree with.

I have such high regard for Pivotal Labs that I specifically try to find startups that started at Pivotal Labs when I'm looking for a job. Since these companies often make you do a three hour pair programming session on their code, I've seen the code of multiple companies that started at Pivotal Labs. Hence, although I don't know if Pivotal Labs has an official opinion on these topics, I've seen these things at enough companies that I feel it's worth commenting on.

First of all, many of the companies that I interviewed at didn't use database-level foreign key constraints and database constraints in general. I know that it's trendy in the Rails world to try to enforce your constraints at the application level. (I'll admit that in some cases involving sharding, you can't use foreign key constraints. However, very few Rails applications are built with sharding.) Unfortunately, the application is simply incapable of truly enforcing certain constraints such as uniqueness constraints and foreign key constraints. Only the database can apply these constraints because they interact with ACID and transactions.

Secondly, as far as I can tell, several of the companies I interviewed at are susceptible to mass assignment vulnerabilities because they don't properly lock things down with attr_accessible such that things are not accessible by default. Perhaps this problem is going away in Rails 3, I don't know. However, many of the companies I talked to didn't want me to explain to them why their code was vulnerable.

Thirdly, a lot of projects at Pivotal Labs tend to use view tests. I think that unit testing views is a total waste of time. Apparently, so does Sarah Mei at Pivotal Labs.

Rather than unit testing the model, view, and controller separately, I prefer to rely on Cucumber and Webrat more heavily. I still write some model tests using RSpec, but I never duplicate things that are already tested by Cucumber and Webrat. I explained my approach and my reasoning in another blog post. Unfortunately, not everyone agrees with me, and this is a hot topic right now.

Last of all, I've seen several Pivotal Labs code bases that use Rails 2.3.X, but haven't switched to using the rails_xss plugin. The rails_xss plugin can really help avoid XSS vulnerabilities. It allows you to remove most of the h() calls in your templates since it escapes things by default. I think this behavior is the norm in Rails 3, so this complaint will soon go away for new code bases.

There's an old saying that if two people agree on everything, than only one of them is doing all the thinking. Hence, it should come as no surprise that I disagree with a few things that I've seen in various Pivotal Labs projects. Hopefully no one at Pivotal Labs will think worse of me for pointing those things out.

Math: Sierpinski's Triangle is a Variation of Pascal's Triangle

Here's a picture of Pascal's triangle from Wikipedia. It's animated just in case you don't remember how Pascal's triangle is created:

Here's a picture of Sierpinski triangle, also from Wikipedia:

You can see in the top image that to calculate a spot in Pascal's triangle, you just add the two above spots. To get Sierpinski's triangle instead of Pascal's triangle, you just xor the above two spots. Cute trick, eh?

I learned this trick while reading Concepts, Techniques, and Models of Computer Programming, which is a fantastic book, by the way. Here's my Oz code for printing out Pascal's triangle:
% This is a generic version of Pascal's triangle that let's you specify the
% operation instead of just using "+".

declare GenericPascal OpList ShiftLeft ShiftRight
fun {GenericPascal Op N}
if N==1 then [1]
else L in
L={GenericPascal Op N-1}
{OpList Op {ShiftLeft L} {ShiftRight L}}

fun {OpList Op L1 L2}
case L1 of H1|T1 then
case L2 of H2|T2 then
{Op H1 H2}|{OpList Op T1 T2}
else nil end

fun {ShiftLeft L}
case L of H|T then
H|{ShiftLeft T}
else [0] end

fun {ShiftRight L} 0|L end

fun {FastPascal N} {GenericPascal Number.'+' N} end

for I in 1..10 do {Browse {GenericPascal Number.'+' I}} end

JavaScript: Jasmine

I went to a talk the other day on Jasmine:
Jasmine is a behavior-driven development framework for testing your JavaScript code. It does not depend on any other JavaScript frameworks. It does not require a DOM. And it has a clean, obvious syntax so that you can easily write tests.
describe("Jasmine", function() {
it("makes testing JavaScript awesome!", function() {
Jasmine started life at Pivotal Labs and is like RSpec for JavaScript. Thanks to the flexibility of JavaScript, it has a powerful mocking / stubbing framework. Jasmine is not a replacement for Selenium. It's good for testing JavaScript functions that calculate things, but it doesn't try to make testing the DOM any easier. Just as unit tests written using RSpec are not a replacement for integration tests written using Cucumber and Webrat, similarly unit tests written using Jasmine are not a replacement for integration tests written using Selenium. Nonetheless, it looks useful.

Ruby: nil is a Billion Dollar Mistake

The fact is, I really like Ruby. However, there are some ways in which it uses nil that I really disagree with. For instance, in Ruby, if you try to look up something in a hash that doesn't exist, you get a nil. Similarly, if you try to reference an @attribute that hasn't been set yet, you'll get a nil.

That reminds me of this article, Null References: The Billion Dollar Mistake:
Tony Hoare introduced Null references in ALGOL W back in 1965 “simply because it was so easy to implement”, says Mr. Hoare. He talks about that decision considering it “my billion-dollar mistake”.
Compounding this problem is Ruby's current lack of real keyword arguments (although, I know they're coming). Hence, if you pass a keyword argument like f(:foo => 1), and then try to use the keyword argument in the function like options[:foooo], the misspelling will result in a nil as if the argument hadn't been passed. This masks a real problem. All of these have resulted in real bugs in my code and lots of frustration.

It doesn't have to be this way. In Python, if you try to look up something in a dict that doesn't exist, you get a KeyError exception. If you try to use an attribute that doesn't exist, you get an AttributeError exception. If you misspell a keyword argument, you get a TypeError exception. Exceptions are nice because they catch the problem right away instead of allowing it to fester. In Ruby, if I get a nil that I'm not expecting, I might not find out that there's a problem until much, much later in a different part of the code when I try to call a method on the nil thinking it's a real object.

Since I'm on the subject of hashes, I think I should mention that Haskell and Scala take a different approach. If you look up something in Scala that may not exist, it returns an Option instance. An Option instance may or may not contain a real value. (Similarly, Haskell uses the Maybe monad.) You have to do work to get the value out of the Option instance, and the type system will catch you if you just blindly assume that there's always something in the Option instance. This is one case where the ML type system can help you avoid a whole class of bugs.

Python: Adding New Methods to an Instance

It's easy to dynamically add new methods to a class in Python, but all my attempts to add new methods directly to an instance had always involved hacks. When I discovered that Ruby had syntax to add methods directly to an instance, my curiosity in the subject was rekindled. Fortunately, someone pointed me to this blog post that shows how.

Why should you care? Most of the time, you shouldn't. You might want to use this trick if you were trying to do something like JavaScript's prototypal-based inheritance system. In my case, I think I was trying to do some funky monkey patching where I only wanted to monkey patch a particular instance instead of the class as a whole. Anyway, even if I can't come up with a good use case, I'm still glad I know how to do it ;)

Linux: Fish Hanging

fish is a "user friendly command line shell for UNIX-like operating systems such as Linux." I've been using fish for about a year, and I really like it. Unfortunately, until recently, I had a problem that I couldn't log into virtual consoles in Linux. If I hit Cntl-Alt-F1 and tried to log in, fish would just hang. This was mentioned on the mailing list a long time ago. I'm pleased to say that I finally solved the problem.

I had the following code in my ~/.config/fish/config.fish:
type fortune > /dev/null
and begin
Basically, this code says, "If fortune exists, run it. Otherwise, don't complain." I figured out through a process of elimination that was the culprit. I replaced it with:
if status --is-interactive
This code will result in an error if fortune doesn't exist, but it won't die. It turns out to be fine for me since I only run fish on my laptop, and I usually install fortune at the same time I install fish.

JavaScript: Perfectly Encapsulated May Mean Perfectly Untestable

It's no secret that JavaScript is like Lisp in that you can accomplish amazing things using a huge number of small, nested functions. In fact, you can write things like:
(function () {
function pickNose() {

function fart() {

In this code, an anonymous function is defined and immediately called. pickNose() and fart() are two internal functions that are used by the outer function, but they are not available to the outside world.

It's amazing what you can get done using nested closures like this, but there's a cost. How do you write tests for pickNose() and fart()? Certainly, you can write a test for the outer function as a whole, but there's no way to test those inner functions in a standalone way without doing some refactoring. In a certain sense, the code is like a script in that you can test the thing as a whole, but you can't test the parts in a standalone way.

What's the solution? I'm sure there are many. You could have the outer function take a parameter such that when the correct value is passed, the code could flip over to testing mode and test itself. Another approach is to use Douglas Crockford's module pattern. The outer function could return an object that has references to the inner functions. That way you can call them externally and test them. However, that may not be an option if you are really paranoid about the outside world getting references to those functions.

In my opinion, getting overly paranoid about people calling your inner functions isn't very fruitful. JavaScript doesn't have much to help you keep modules away from each other. As soon as you have hostile JavaScript on the page, it's sort of game over. All of the JavaScript operates with the same permissions--it's not like you can sandbox a particular module.

Furthermore, it's difficult if not impossible to prevent people from just grabbing your JavaScript source code and hacking it to do whatever they want (especially if they can rely on the help of an external server). To state the obvious, JavaScript doesn't have very good internal security boundaries, so your server must always be distrustful of the JavaScript that it's talking to. Of course, that's the way the web has worked for as long as I've been coding.

Python: Using Louie with Twisted

Louie "provides Python programmers with a straightforward way to dispatch signals between objects in a wide variety of contexts. It is based on PyDispatcher, which in turn was based on a highly-rated recipe in the Python Cookbook." Louie is like an event system used in a GUI toolkit. Similarly, you can think of Louie as an internal pubsub system. Twisted is a framework for building asynchronous network servers. Using Louie in your Twisted applications can make your applications a little less "twisted".

When you code a Twisted application, you often put a lot of your logic in custom Factory and Protocol classes. However, if you have one application that has to talk to, say, three different types of servers, and you have a custom Protocol and Factory class for each server (perhaps each server speaks a different network protocol), it can be confusing to have your application logic broken up all over the place. Louie can help with that.

When you are implementing a Protocol class, when you receive a new Twisted event, you can generate a Louie event. In that way, you can have a single application-specific class that responds to events from a wide variety of Twisted Protocol classes. When I used this approach on my Twisted application, the code went from being very "scatter brained" to something more linear. I had a bunch of small functions that each responded to Louie events, and all the functions were in order in the same class. It certainly helped me wrangle control of the complexity of the system.

It may seem strange to translate Twisted events into Louie events, but considering the fact that Louie has support specifically for Twisted and considering the fact that I learned this trick from Drew Pertulla, a Twisted user, I know I'm not the only one using this trick.

I have a couple more tips. First of all, Louie tries really hard to pass only the arguments that your function is looking for. Hence, if your function doesn't accept a sender argument, it won't pass a sender argument. This is really helpful, but it can bite you. The magic tends to break down if your function is wrapped by a decorator or if your function is a closure (i.e. a nested function). In these cases, Louie can't figure out exactly which arguments to pass, and stuff can break. However, it's usually easy to work around situations like this once you figure out what's going on.

I have one other mildly off-topic trick for working with Twisted. Queues and Twisted work really well together. If you have one piece of Twisted code that simply reads from a queue and then does something, then other parts of the Twisted code can put things in the queue in a synchronous manner. It sounds simple, but this one trick really helped me out a few different times.

Last of all, I wanted to mention gevent. Twisted is certainly a mature library with support for a range of protocols, but if you're working with green field code, you might want to take a peek at gevent instead. Aside from having excellent performance, it also lets you write code in a synchronous manner, which is helpful for mere mortals like myself. If you're thinking about using Twisted vs. gevent, check out this talk that the Meebo guys gave at PyCon.

JavaScript: JS.IO is Solid, Hookbox Might be the Bee's Knees

Recently, I needed to add realtime (i.e. comet, websockets, flash sockets, etc.) support to an application. JS.IO is a JavaScript library that provides a long polling system using the Comet Session Protocol (CPS). It doesn't try to do what Socket.IO does, i.e. abstract all the various transport mechanisms such as websockets and flash sockets. Rather, it provides long polling and leaves the switch to websockets or flash sockets to the user. There are server-side libraries to integrate with JS.IO using Twisted, Eventlet, Erlang, etc.

My experiences with JS.IO were very positive. Although the documentation was sorely lacking, Michael Carter (the author) was extremely helpful when I was getting started. Furthermore, my testing with crossbrowsertesting.com proved that JS.IO was very reliable across an incredible range of browsers. It was the most reliable comet library I tried. By the way, I was doing this cross-domain.

These days, Michael Carter has started a new project called Hookbox:
Hookbox is a Comet server and message queue that tightly integrates with your existing web application via web hooks and a REST interface.
I blogged about Michael's talk at PyCon. Although Hookbox doesn't perfectly solve all my problems (it doesn't yet having clustering support), I'm extremely hopeful that this will turn out to be a great project!

JavaScript: Socket.IO Didn't Meet Needs

Recently, I needed to add realtime (i.e. comet, websockets, flash sockets, etc.) support to an application. Socket.IO is a library built on top of Node.JS that "aims to make realtime apps possible in every browser and mobile device, blurring the differences between the different transport mechanisms." Since Socket.IO did exactly what I needed, I was hoping it would solve my problems easily and that I wouldn't have to implement what Socket.IO did myself.

Unfortunately, things didn't work out so well. I had to do things in a cross-domain manner. Although the browser support list for Socket.IO is very good, that didn't match up with my actual experience. I built a simple application that tried to send and receive a message using Socket.IO, and then it reported on which transport was used. Unfortunately, many of the browsers that I wanted to support such as IE 6 and 7 and Opera just didn't work, even though they were supposed to. Here are some of my results.

Furthermore, if you watch the mailing list, a lot of questions just get dropped on the floor. I'm sure this is because the authors of Socket.IO are completely overwhelmed. Hopefully as Socket.IO matures and the list of expert users grows, this will improve.

By the way, you might wonder how I tested so many browsers. I paid for an account on crossbrowsertesting.com. It was worth every penny! First, I would use it to try to take a snapshot of my test page on all the different browsers. Then, I would use the web-based VNC system to log into the systems and view the page manually in order to see what was going wrong. This was very helpful to determine exactly which browsers did and didn't work.

Anyway, as I said, I hope Socket.IO gets better because it solves a real need. Perhaps it already has, since I was doing this testing several months ago. However, if you need to use Socket.IO, I heartily recommend you make use of crossbrowsertesting.com to make sure that the browsers you need to support actually work.

In my next post, I'll cover JS.IO.

ZeroMQ is Amazing!

Recently, I had to improve the performance of mesh networking in a mesh of, say, 10 nodes. The original code used a simple RPC system built using JSON on top of netstring. Every message to every node involved a new connection. On a cluster of 10 nodes, I was getting 30 messages per second.

I enhanced the code by using persistent connections. I also switched from RPC (i.e. using a whole roundtrip that blocks the whole connection) to message passing (i.e. passing a message doesn't necessarily result in a response and doesn't tie up the socket). This improved the performance to 300 messages per second.

Next, my buddy encouraged me to try out ZeroMQ. Man was I amazed! I hit something like 1800 messages per second on a cluster of 10 nodes! I can only imagine what ZeroMQ was doing in order to hit this number. Perhaps it was batching messages more intelligently (from my experience, that's an amazingly effective technique).

I ran the same test on a range of cluster sizes, from 2 to 10. The performance graph had a sawtooth shape. The shape was consistent between runs. I'm inferring that ZeroMQ doesn't try to have one node send the message to all the other nodes. Rather, the message filters through the cluster in a tree-like manner.

Anyway, I'm sorry I can't share the graphs or the code, but let me just say that I was very impressed with ZeroMQ!

Linux: ^\

Am I the only one who didn't know that you could use ^\ (i.e. control backslash) to kill a process when ^c doesn't work? Usually, I have to use ^z to background the process, and then type kill -9 %1. I think ^\ makes the process dump core, but since dumping core seems to be turned off by default, it works out well. Here's an example of my killing a process under fish (my shell):
fish: Job 1, “nosetests” terminated by signal SIGQUIT (Quit request from job control with core dump (^\))
Thanks to Jeff Lindsay for the tip.

Saturday, April 16, 2011

Videos: IBM Centennial Film: 100 X 100 - A century of achievements that have changed the world

IBM Centennial Film: 100 X 100 - A century of achievements that have changed the world
The film features one hundred people, who each present the IBM achievement recorded in the year they were born. The film chronology flows from the oldest person to the youngest, offering a whirlwind history of the company and culminating with its prospects for the future.
I found the film to be very moving.

Wednesday, April 13, 2011

Python: I'm Looking for a Python Instructor

I'm looking for a talented, friendly Python programmer to do corporate training. I'm helping out a company called Marakana. They do corporate training and have multiple gigs lined up for Python. Unfortunately, their normal Python instructor is getting a little bit busy right now, and so am I. If you're interested in giving a four day training session on Python, please send email to me at jjinux at gmail dot com. My buddy Robert Zuber has already prepared the course materials, and the pay is pretty decent. They're also looking for people to teach Ruby on Rails, HTML5, JavaScript, and Android, but I figured most of my readers are Python programmers.

I'm sure this is obvious, but you must be comfortable with public speaking. You get bonus points if you've given a talk at PyCon or a local users group. You get double bonus points if you're well known in the Python community, especially if I know you ;)

Update: The response was pretty overwhelming, so I think I can stop looking. Thanks, guys.

Wednesday, April 06, 2011

PyCon: Closing Lightning Talks

PyCon will be held in Montreal in 2014 and 2015.

Twiggy is a new Pythonic logger. It has a totally new design (i.e. it's not like log4j). It's the first really new logging design in 15 years. It uses lots of chaining method calls like jQuery. It makes parsing logs easier. It has a modern config system. It has better traceback printing. It has an asynchronous logger.

Askbot is a Stack Overflow clone in Python.

The Python Miro Community has Python videos. They're rolling out universal subtitle support.

Minuteman is a tool to replace your build.sh. It acts as a workspace and project manager. It is like zc.buildout. It's also like Maven and Gentoo. It's a "metabuild system." It has no docs, no tests, and no users.

Hold Old is My Kid? is a website that helps you figure out your kid's age in days, months, and years.

flufl.enum is an enum library written by Barry Warsaw.

MOE_write is a library for dealing with Python2 vs. Python3. It's from Google. It allows you to maintain 2 or 3 branches (?). It runs 2to3 and 3to2 to patch back and forth between branches. It's a scary hack.

Microsoft stopped funding IronPython. It's still going forward in the open source community. There's a project called IronPython Tools for Visual Studio. It has intellisense that can do crazy, static type analysis. It can figure out the type of a variable even through function calls.

A guy wrote Adventure in Python3. He ported it from the original Fortran code. He even did a weird thing where you can play it within the Python shell. What's weirder is that he wanted people to be able to do things like write "north" in the Python shell, without needing to add the parenthesis to make it a function call. Hence, he overwrote the __repr__ method so that calling "north" would automatically call the function. Cute hack.

Python has a ton of mock testing libraries. Almost everyone should make use of mocks, at least to mock out services only available over the Internet or to test your exceptions handling. There's a new library called "Fudge" that was inspired by "Mocha".

Side note: my buddy Kyle wrote a mocking library called ditto at IronPort/Cisco which has various useful features.

PyCon: Hidden Treasures in the Standard Library

Hidden Treasures in the Standard Library

The talk was by Doug Hellmann. He writes Python Module of the Week. By the way, that is the most popular Python blog according to Google Reader, at least the last time I checked. Doug is publishing the series of blog posts as a book. Oh, and he's a nice guy :)

Side note: I met a guy who worked at a company that provided mapping software. The software was used by Google maps. He worked on the routing algorithms. He said the whole system consisted of 200 million lines of code. (I'm not sure how that's possible.) However, he also said that they distribute an SDK that contains .NET, the JRE, and Python within it.

Use the csv module with your own "dialects" to handle data that has fields with characters between each field.

SQLite3 has been added to the standard library. You can create custom column types in Python.

You can create signed, serialized data using the hmac library.

You can serialize data using the built in JSON support. Look at json.dumps(default=...).

You can override sys.excepthook with your own function.

You can create complex logging handlers. For instance, you can send non-verbose messages to the console, or you can send verbose messages to a log file. You can even combine these two things. For instance, you can configure it so that it logs tracebacks, only to file, and only on error.

Tuesday, April 05, 2011

PyCon: Greasing the Wheels of Exploration with Python

Greasing the Wheels of Exploration with Python

Here's the talk summary:
The control of the Mars Exploration Rovers (MER) requires a complex set of coordinated activites by a team. Early in the MER mission the author automated in Python much of the task of one of the operation positions, the Payload Uplink Lead, for 7 of the 9 cameras on each rover. This talk describes the MER rovers, the operation tasks and that implemented system.
They used gigapan images.

They use virtual reality to visualize what's going on.

Dust was a serious problem for the rovers.

There's lots of Python on the rovers used to control the rovers.

The speaker's background is in machine learning and robotics.

The rovers have been running for 6-7 years. They find 1-2 bugs a year. Bugs are usually fixed in a matter of hours.

They uses Ames Vision Workbench, Nebula, and OpenStack. All three of these are open source.

The speaker was from Ames Research Center, NASA.

Side note: unfortunately, I missed the first five minutes.

PyCon: Fun with Python's Newer Tools

Fun with Python's Newer Tools

collections.namedtuple works just like normal tuples, but it lets you assign a name to each field. It's fast, and there is no additional per-tuple space cost.

There's a lot of cool stuff in the collections package.

Named tuples can be used for "instance prototypes" by using "other_tuple._replace(field=5)". Don't be discouraged by the "_"--they had to do that so as to avoid a namespace conflict.

You can subclass a named tuple. It's based on __slots__.

In Python 3.2, there is a functools.lru_cache. It's a decorator. It accepts a maxsize argument.

Side note: I missed the first five minutes of the talk.

PyCon: An Open success for the cloud: OpenStack

Side note: I missed part of the talk because I had to leave early to go to mass.

OpenStack turns a pile of hardware into a cloud.

Swift is their object storage system.

Nova is their system for provisioning virtual machines.

Glance is their system for image storage.

Burrow is their distributed message system.

Dash is a Django user interface for managing virtual machines.

NASA uses OpenStack.

Rackspace is going to use it. They were acquired by Rackspace.

PyCon: Disqus: Serving 400 million people with Python

Disqus is a commenting system for blogs.

It's the largest Django application.

They get 500 million visitors a month.

It's used by CNN, IGN, MTV, etc.

Every engineer at the company is also a product manager.

They have a flat company structure.

They're experiencing exponential traffic growth.

They have 100 servers.

They rent hardware.

Their Python code is CPU bound.

They're using Apache + mod_wsgi.

Their background tasks are IO bound. They use Celery + gevent for background tasks. This saves memory over using separate processes for each background job.

They use Graphite for monitoring. They use Etsy's statsd proxy for Graphite.

"Measure anything and everything."

They had to fork and monkey patch Django in order to scale.

They deploy to production 3-7 times a day.

They use Hudson for continuous integration. They have a large test suite that takes 30 minutes to run. They love Hudson, but they said it's too Java oriented.

They do not suffer from not invented here syndrome (NIH).

They have rolling deploy with fast rollbacks.

They use the unittest module and nose.

They use coverage.py and Pyflakes.

They love pep8.py and Pyflakes.

They learned Django and then learned Python.

Python package management is a mess.

They're a good Python shop, and they have a good engineering culture.

They have open sourced a bunch of stuff.

PyCon: Going Full Python - Threadless

The keynote was by a guy from Threadless.

Threadless sells clever, artistic T-shirts.

The company has lots of culture. It's very hip.

The designs are community driven. The community votes on them.

They don't actually print the shirts themselves.

Threadless is in Chicago. Rahm Emanuel visited. After he visited, he Twittered, "Seriously, this city used to build things. Now we're just assholes with novelty t-shirts. I'm with motherfucking stupid."

They switched from PHP to Django. They're still fighting a lot of technical debt.

Threadless is an "art community".

The speaker was hilarious.

PyCon: Lightning Talks

Read the Docs is a site that hosts documentation. The speaker said "shit" a lot.

Chef or Puppet--choose one.

Haystack is a project for doing full-text search.

"Emacs pinky" is a real problem.

DjangoZoom enables turnkey deployment for Django.

PyCon did a donation drive for Japan. People could donate by texting to 90999. It wasn't actually very successful, but the Python Software Foundation pitched in to help out.

JavaScript is like English--it's a real mess, but it works.

In ECMAScript 5 (ES5), you can start your script with '"use strict";'.

Firefox (because of the ES Harmony project) has added all sorts of weird additions to JavaScript. Many of them were taken from Python.

flufl.i18n is a high level API for i18n. It's higher level than gettext. It makes it easy to handle multiple languages at the same time. It was written by Barry Warsaw at Canonical.

PyWO is the "Python Window Organizer". It works on top of your existing window manager. It allows you to move and resize windows in useful ways. It support tiling. However, it's less controlling / automatic than a normal tiling window manager.

Grace Law (a Python recruiter) said that you should be learning and hacking in your spare time. It helps with interviews to talk about something you're excited about in your coding life. Speed is also important. You should be quick.

Side note: I saw lots of Ubuntu users and lots of Macs. Windows users were more unusual this year.

PyCon: Supercomputer and Cluster Application Performance Analysis using Python

Supercomputer and Cluster Application Performance Analysis using Python

The speaker was from Sandia labs.

The goal of his project was measure and track the performance of super computers.

His software used Python, matplotlib, MySQL, etc. It was a Tkinter application.

The interface was definitely created by an engineer ;) It was somewhat overwhelming.

There was some UI in the application to manage database schemas.

It's weird to see Tk applications when you're so accustomed to "dot-comish" web apps.

It seems painful to me to have to recreate an admin to manage database schemas when good ones already exist.

I think the speaker was running Windows 2000.

There was some UI in the application for creating queries to query the database.

The application could show graphs plotted by matplotlib.

Kiviat charts are hard to code, but they're very useful for plotting multivariable data.

His projects were called Pylot, Co-Pylot, and eCo-Pylot. He plans on open sourcing them, but that type of thing takes a while at a big lab.

His project, Mantevo, is already open source.

Since the goal of the project is to measure and track the performance of super computers, I asked if they had come up with any interesting results yet. They haven't yet because they're just getting started.

PyCon: HTTP in Python: which library for what task?

HTTP in Python: which library for what task?

The talk was by a Mercurial guy. He works on Google Code.

When you think of HTTP, what you're probably thinking of is RFC 2616, i.e. HTTP/1.0. HTTP/1.1 has features that you're probably not remembering to handle correctly. This resulted in a bug that took him a very long time to diagnose.

HTTP/1.1 allows pipelining, which means you send all the requests right away and then wait for the responses to come in serialized over the same socket.

Using chunked encoding lets you keep the connection open between requests even if you don't know how much data will be streamed. Did you know that you can specify additional headers between chunks?

Did you know the "100 Continue" response gets sent before you finish sending the body?

httplib (used by urllib2) is very minimal. It doesn't even do SSL certificate validation! It doesn't support keepalive. It doesn't have unit tests.

httplib2 is just a wrapper around httplib that adds some stuff.

There is PycURL. It's based on libcurl, which is the gold standard for HTTP libraries. However, it's not very Pythonic and it has a steep learning curve.

twisted.web.http only supports HTTP/1.0 [or perhaps it doesn't support very much of HTTP/1.1].

The author is working on a new library. It uses select and is thus non-blocking. It has "100 Continue" support. It has lots of unit tests. However, it doesn't support pipelining.

Using httplib (via urllib2) is okay if your needs are simple.

PycURL is awesome if you can tolerate the steep learning curve.

You can get the author's new library from http://code.google.com/p/py-nonblocking-http/.

PyCon: Advanced Network Architectures With ZeroMQ

Advanced Network Architectures With ZeroMQ

This was a talk on ZeroMQ by Zed Shaw. He and his talk were a lot more sedate than I expected. He's also older than I thought he was.

He uses Emacs, screen, and Ubuntu.

ZeroMQ servers should not be exposed to the naked internet. If you send it invalid protocol data, assertions will kill the process.

The talk was very fast, but most of it was like the ZeroMQ guide.

PyCon: Exhibition of Atrocity

Exhibition of Atrocity

Here's the summary:
Believe it or not, but you can write pretty horrendously awful code even in a language as elegant as Python. Over the years, I've committed my share of sins; now it's time to come clean. Step right up for a tour of twisted, evil, and downright wrong code, and learn some strategies to avoid writing criminally bad code--if you dare!
This was a fun talk full of fun examples.

The speaker showed code he had worked on over the course of 11 years.

They used Hungarian notation at one point!

snake-guice is a simple, lightweight Python dependency injection framework based on google-guice.

PyCon: Using Coroutines to Create Efficient, High-Concurrency Web Applications

Using Coroutines to Create Efficient, High-Concurrency Web Applications

Here's the summary:
Creating high-concurrency python web applications is inherently difficult for a variety of reasons. In this talk, I'll discuss the various iterations of application server paradigms we've used at meebo, the advantages/disadvantages of each approach, and why we've settled on a coroutine-based WSGI setup to handle our high-concurrency web applications going forward.
They started with CGI. Then they switched to mod_wsgi. Then they switched to Twisted. Finally, they switched to gevent and Gunicorn. They said that this was the best of both worlds.

Guido said, "I hate callback based programming."

The speaker showed a great chart which showed the strengths and weaknesses of the various approaches.

Gunicorn is a lightweight WSGI server. It has worker processes. It supports gevent.

mod_wsgi is fast. However, if you use Gunicorn with multiple processes, it'll beat mod_wsgi.

Use Greins to manage Gunicorn.

gevent-profiler is useful.

I Code Sooooo Slowly!

One thing I've learned over and over is that a programmer's skill with his preferred editor is no indication of his skill as a programmer. One of the best programmers I know stuck with Pico for years! Certainly many of the programmers mentioned in "Coders at Work" use Emacs without even trying to learn it well.

If you've been reading my blog for a while, you know that I'm obsessed with productivity, especially when it comes to editors. There's a reason why. I'm slow...really slow!

When I was at PyCon, I participated in a coding challenge. The grand prize was a MacBook Air, and there were only 8 participants. I figured I stood a good chance at winning the MacBook Air which I needed since I was leaving Twilio.

The challenge used SingPath:
SingPath is the most FUN way to practice software languages! SingPath provides a platform to those that want to test their programming skills in a competitive and fun environment.
(By the way, did you notice that it's spelled Singpath in the title and SingPath in the introductory paragraph?)

Anyway, the challenge consisted of 10 questions that you have to write Python code to solve. I finished 6th out of 8! I was the slowest programmer among the professional programmers. It gets worse ;) The guy who won the competition was a Russian guy (I think). He finished all 10 problems in 10 minutes. I only finished 8 problems after 30 minutes. I would have finished the others, but I ran out of time.

It was definitely humbling to realize just how slow I am. What's ironic, though, is that I'm really fast at manipulating text in an editor. (Sometimes I use Vim and sometimes I use NetBeans with the jVi plugin so that it feels like Vim.) I can make text fly, but that doesn't translate into coding faster.

Fortunately, I have other assets as a programmer. For instance, my code is well known for being extremely clean, and I rarely have very many bugs. Nonetheless, it's frustrating that I'm so slow, and I really wish there was something I could do to improve my speed.

Having spent so much time futzing with my editor, I think it's clear that that isn't the problem. I think the problem is that my mind is constantly in "proof mode". I double check everything, code review my own code multiple times, think about all the edge cases, etc. Trying to code fast just doesn't work for me. When I did the programming competition, I was coding as fast as I possibly could. If I had taken my time like normal, I probably would have taken 2-3 times as long (but the code would have had really nice documentation and tests too).

Does anyone have any realistic advice for how I can increase my speed without sacrificing quality?

Python: Python IDEs Panel

Python IDEs Panel

Side note: There were surprisingly few people at this talk. It seems like most Python programmers get started with either Vim or Emacs and then don't change. It's ironic that I'm so obsessed with programmer productivity given that I'm such a slow coder ;)

The panel consisted of representatives who worked on Python Tools for Visual Studio, PyCharm, Komodo IDE, Wing IDE, and a Python mode for Emacs (pythonmode.el). There was no one present to champion PyDev or NetBeans.

Michael Foord prefers Wing IDE.

Python Tools for Visual Studio has debugging support for high performance computing (HPC). It supports MPI. It can debug a program that uses multiple processes. It supports both IronPython and cPython. You can use iPython within Visual Studio to control a cluster of machines. You can write Python code to analyze the variables in the individual frames of a stack.

PyCharm makes test driven development (TDD) fast! The speaker was using PyCharm to test drive the development of a class which he was creating quickly in the test file. PyCharm can automatically create the scaffolding for a class as you use the class in your test. It can create the scaffolding for methods, add imports, add constructors, etc. all automatically as you try to use those things in your tests. It has helpful coding suggestions and refactoring support. It has code snippets. It's crazy how much it can guess what to create automatically. It has great Django support. It has Django-specific code completion. The demo for PyCharm was flat out amazing!

Komodo Edit is free and open source. However, Komodo IDE is commercial. It adds support for debugging, etc. It opens very quickly. It's good at working with multiple languages at the same time. It has an HTML preview feature that can show you an HTML page within Komodo (presumably because it's written in XUL). It has a regular expression debugger. There are about 80 extensions. In 2011, InfoWorld rated Komodo IDE as the best Python IDE.

Wing IDE is commercial. It supports multiple keyboard personalities. It has a debug shell. The debugger and intellisense work well together.

The champion for Emacs was Barry Warsaw. He showed how to integrate Pyflakes. The demo wasn't particularly inspiring.

Most of the IDEs have been around for about 10 years.

When I brought up the fact that so many successful programmers use Emacs, the general consensus was that the people who succeed using Emacs have been doing the same sort of thing for a really long time. They have it entirely in their head. They don't really need an IDE, and an IDE isn't really helpful for their situation.

PyCon: The Data Structures of Python

The Data Structures of Python

Use types idiomatically.

Sometimes you don't have a choice.

Be efficient when it doesn't cost you anything.

Think about set vs. frozenset, mutable vs. immutable.

There is now a collections.OrderedDict class in Python 2.7 and 3.1.

Sometimes you need your data structure to address more than one concern. Use combinations of things from the standard library.

collections.deque is a linked list. It's pop(0) and insert(0, item) operations are O(1), whereas those operations are slower with normal lists. In Python 2.7, there's a maxlen parameter for the deque class (which I assume turns it into a circular queue).

You can use the array type to efficiently represent an array of ints, etc.

heapq is also interesting.

collections.abc contains abstract base classes.

"Don't subclass dict ever!" He said this is true of other containers as well. He said there are too many edge cases. You should instead subclass things like collections.Mapping instead.

There's an ordered set class on the Python Cookbook site. (Presumably, it combines a set with a list.)

Don't do more than necessary. ABCs (abstract base classes) can help.

You can use a frozenset as a dict key, and you can use frozensets as members in other sets.

Tuples are more efficient than lists.

Side note: htraf.htsql.org is an insanely good WSGI / ReST interface for databases.

PyCon: Ten Years of Twisted

Ten Years of Twisted

The talk was by Glyph Lefkowitz, the original author of Twisted.

He mentioned Medusa and Sam Rushing.

Twisted started because Glyph wanted to add email and HTTP handling to his video game, Twisted Reality. He started by using the "select" function call.

Twisted is good because it unifies the protocols.

Glyph is only the 3rd most prolific Twisted committer.

When you write tests for Twisted code, you can have both the client and server in the same process.

Twisted is event-driven and asynchronous.

Before switching to Python, Glyph wrote Twisted Reality in Java using threads.

Twisted is powerful and flexible.

Twisted is switching from the term "framework" to "engine".

"Reactor included."

Use "twistd --help" to see which servers are available for free with Twisted.

Glyph said, "I hope we have another 10 years of Twisted."

Side note: Gevent was really popular this year. During his keynote (which I missed because I overslept, unfortunately), Guido said that he rejected the "everything is a callback approach". However, he also said he didn't like approaches using Greenlets because you couldn't be exactly sure where the context switches were happening. I know he also doesn't like threads. He seems to prefer explicit yields for asynchronous IO. As far as I can tell, many Python programmers aren't following his suggestions because Gevent seemed really, really popular this year. It's certainly my favorite approach for asynchronous network servers.

Monday, April 04, 2011

PyCon: Lightning Talks

Qtile is a tiling window manager written in Python. It's an alternative to Awesome.

In Tunesia, they were using flame throwers against protesters.

In a "do-ocracy", you don't govern, you just do.

PyParsing and SPARK are good parsing libraries.

Resolver is a Python-powered spreadsheet that works on Windows.

Dirigible is the same thing as Resolver, but it runs as a web application.

PyCon: Hookbox: All Python web-frameworks, now real-time. Batteries Included

Hookbox: All Python web-frameworks, now real-time. Batteries Included

Hookbox is a new server written by Michael Carter (of JS.IO and Orbited fame) for doing comet. It is a simple comet server that uses web hooks to talk to your normal web server. Your normal web server can take care of all the business logic, and Hookbox can take care of the comet.

Side note: SF.net uses MongoDB and has ugly denormalization problems.

Hookbox replaces what you would have had to do with RabbitMQ + Orbited.

Michael called Hookbox a "web-enabled message queue".

It's based on Eventlet.

It uses the comet session protocol (CSP).

It takes care of pub/sub, history, presence, moderation, etc.

The documentation is not very complete.

It doesn't support clustering.

Hookbox is really good at delegating business logic to your application.

PyCon: Porting to Python 3

Porting to Python 3

py3ksupport.appspot.com has a list of the top 50 Python projects and which of them support Python3. As of the talk, 34% of the top 50 Python projects supported Python3. I just checked, and it's up to 54%.

There are multiple strategies to porting to Python3:
  • Only support Python3.
  • Use separate trees for Python2 and Python3.
  • Include both versions in a single download and set package_dir in setup.py
  • Implement "continuous conversion" using 2to3. This approach is recommended for libraries. Distribute can help.
  • Use a single codebase with no conversion. This requires loads of compatibility hacks. It's fun, but it's ugly. Check out the "six" project if that's what you want to do.
Try 2to3 first. If in doubt, use distribute.

Libraries should port as soon as possible.

In order to prepare, use Python 2.7 with the -3 flag. Fix all the deprecation warnings.

Use separate variables for string vs. binary data.

Add "b" and "t" to file flags.

For sort, switch from "cmp" to "key".

Reminder: __foo__ is often pronounced "dunder foo" (aka "double under foo").

Increase your test coverage. This significantly helps!

Use "2to3 -w ." to port an entire directory.

In setup.py for distribute, use use_2to3=True.

urllib2.urlparse is not right. Use the urlparse module directly.

Bytes vs. unicode is the hard part.

Using == to compare bytes and str doesn't work. b"a"[0] does not equal "a"[0]. Hence, the comparison will return False in a way that is unexpected and silent.

Trying to support Python 2.5 and Python3 at the same time is REALLY hard. It's much easier to support Python 2.7 and Python 3.0 at the same time.

Seeking in a UTF-8 text file is slow because it involves decoding, not simple indexing.

See http://docs.python.org/py3k/howto/pyporting.html.

There's a book called "Porting to Python 3".

Saturday, April 02, 2011

PyCon: Status of Unicode in Python 3

Status of Unicode in Python 3

The talk was by Victor Stinner. I went to dinner with him and a few other people. He was a nice, French guy.

The encoding for source code defaults to UTF-8 in Python 3.

Surrogate escapes are a new feature in Python 3.2. They let you deal with stuff that can't be decoded as UTF-8. For instance, you can decode a filename string to a unicode object without losing data even if the decoding isn't clean.

There are still issues to work on.

Victor had bootstrap issues implementing all this stuff.

It took a lot of hard work to improve all this stuff.

Check out Programming with Unicode, which is a book that Victor wrote.

Victor has event more Unicode fixes in store for Python 3.3.

Side note: I had an idea. It'd be cool to create a tool that shows you a call tree for your application. In the call tree, it can show you where all the encodes and decodes are done. This would help you know where to do encodes and decodes. This would really help when porting from Python2 to Python3. Figuring out where to do encodes and decodes is a lot more subtle than you might think. It doesn't always make sense to do it at the very edges of your application.

PyCon: Opening the Flask

Opening the Flask

The talk was by Armin Ronacher, one of the authors of Flask.

Flask started as an elaborate April Fool's joke.

The guys who did Flask did a lot of cool stuff before doing Flask, such as Jinja2.

Flask was originally Jinja2, Werkzeug, and some glue code cleverly embedded in a single file download.

Marketing beats quality.

Originally, they didn't do any testing or any code review. That's changed.

They wanted to restart with good docs and good tests. They documentation and tests are pretty good these days.

The name "Flask" is a play on another framework, "Bottle".

Flask is still based on Werkzeug and Jinja2.

Flask can use Blinker as a signalling system (?).

Flask is about 800 lines of code, 1500 lines of tests, and 200 A4-sized pages of documentation.

There are lots of extensions.

Flask uses decorator-based routes, but there are other options.

Flask supports URL routing as well as URL generation.

Jinja2 uses template inheritance.

They use context locals to make writing apps simper. Armin suggests that you might as well embrace context locals--you'll end up needing them anyway.

Armin is very against import-time side effects.

Flask is in favor of explicit application setup. For Flask, this has occasionally led to circular imports that they had to find workarounds for.

WSGI middleware works with Flask.

Flask has several advantages over Bottle.

You can override various aspects of how Flask works. For instance, you can use the "@app.before_request" and "@app.after_request" decorators.

They make use of lots of extensions.

Flask has a goal of keeping the core very small.

You can use other templating engines if you want, but Jinja2 will always be a dependency just in case any extensions need it.

Documentation matters.

Communication matters. It's very easy to submit issues to Flask. You don't even need to create an account.

It's important to keep committing to projects otherwise the project looks dead.

Consistency matters.

It's important that even the documentation be beautiful.

Flask uses Sphinx for documentation.

Armin didn't have a strong rule of thumb for when you should use Flask vs. Pyramid. Neither the Flask guys nor the Pyramid guys are overly religious about their frameworks.

The audience turnout was about the same for both the Flask and Pyramid talks.

The Flask guys are thinking about redoing the code for reverse routing.

PyCon: State of Pylons/TurboGears 2/repoze.bfg

State of Pylons/TurboGears 2/repoze.bfg

There are about 2000 people on the Pylons mailing list.

Ben Bangert said that Pylons relies too heavily on subclassing. When people subclass and override stuff in a framework's parent class, it makes it difficult to alter the parent class without breaking people's code.

Side note: The new Pyramid T-shirt is beautifully done, but evil aliens (or anything else for that matter) are a big turn off for me.

Pylons is big, but Ben said that too much of Pylons is dependent on him.

Pylons is merging with repoze.bfg. It's going to be called "The Pylons Project", but it's based on the code in repoze.bfg.

Chris McDonough wrote repoze.bfg. It's a great, but relatively unknown framework. Pylons has better name recognition.

TurboGears 2 is built on Pylons.

The new framework is called Pyramid and is part of "The Pylons Project".

TurboGears 2 and Pylons are going to be maintained together so as not to strand a bunch of legacy projects.

Side note: There were a lot of big beards at this PyCon. Big beards have always been popular among hackers, but it's even more popular right now. I wonder if this has anything to do with the Giants pitching staff and with the Giants winning the World Series.

TurboGears will experiment and innovate on top of Pyramid in the same way it used to experiment and innovate on top of Pylons.

repoze.bfg has a catchphrase: "Plumbing Zope 2 into the WSGI pipeline." It actually doesn't take any code from Zope, but it does borrow some ideas.

There are about 200 people on the repoze.bfg mailing list. It has 100% statement coverage. 100% of the code is documented--if a feature isn't documented, then it doesn't exist. There are 80 committers to the repoze.bfg project!

Pyramid is just repoze.bfg renamed.

There is a Paster template for Pyramid--multiple actually.

These are the features in repoze.bfg: it maps URLs to code; it has an authentication framework; it supports I18N; it supports single file applications as well as larger projects; it makes use of PasteDeploy; it has unit, functional, and integration testing; it uses WSGI; it has great docs; it supports multiple templating engines; it supports Google App Engine; it has plugins; it can serve static files; it has sessions; it has cross site request forgery (CSRF) protection; it supports events; it has good exceptions handling; it supports WSGI middleware; it's extremely fast; it has 100% statement coverage.

One reason that it is so fast is that a lot of work is done at startup so that less work needs to be done at runtime.

It is not a full-stack framework. It has no persistence layer.

It currently has 16 dependencies, but single file applications are still possible.

It is "unopinionated".

Chris (the repoze.bfg guy) said, "I'm a Django fan. I love Django." Obviously, he doesn't think Django is appropriate for all situations.

Pyramid != Zope. It's not Pylons. It's not MVC. Chris hates that term.

Flask may be more appropriate for small projects. Pyramid may be a better fit for larger applications.

Pyramid exposes plug points all over the place.

Pyramid supports row-level security.

There's a Pyramid OpenID library.

They use Lettuce together with a web driver. It can work without Selenium.

WebTest from Ian Bicking looks interesting.

The next version of Pyramid will target Python3.

Paste is in a state of flux, but it's too important to be abandoned.