Word Aligned

Bike charts by Google

tag@wordaligned.org (Thomas Guest) — 2010-02-18

I’ve liked the Google chart API ever since I first discovered it. Pack a text definition of an image into a URL http://chart.apis.google.com/chart?YOUR-IMAGE-HERE and you’ll be served up a freshly cooked PNG. It’s free. There’s not even a watermark.

http://chart.apis.google.com/chart?  # A chart, please
    &chs=320x160                     # sized 320x160 pixels
    &cht=gom                         # of type swingometer
    &chd=t:70                        # with 70% swing
    &chl=Nice!                       # labeled "Nice!"

Gone are the days when the documentation fitted on a single web-page. The API has fattened up and filled out. Every time I visit something new has been added: mathematical formulae written in TeX; a playground where you can sketch a chart directly; a validation option which tells you where you went wrong — much more helpful than a bare 404.

New to me: dynamic icons, which let you create “a variety of interesting callouts, pins, or bubbles that mix text and images”.

Mercurial manxman Mark Cavendish won an incredible 6 stages of last year’s Tour. Here he is, becoming the first Briton ever to win the final showdown on the Champs-Élysées, and winning it by an immense margin. For me, it was a bitter-sweet moment: that sprint should have put Cav in the green jersey, but he’d thrown away his chance in the points competition earlier in the race with an act of petulance which I still struggle to understand.

The Champs-Élysées may have a cobbled surface but it’s level and straight — definitely one for the sprinters. How about something twisted and mountainous? This second tableau recreates Fabian Cancellara’s dare-devil descent during stage 7 of last year’s tour. Defending the maillot jaune, Cancellara got dropped by the peleton following a wheel change. Watch him weave between team cars and camera bikes at top speed to regain his place. Awesome!

Now for a real classic — when Stephen Roche dug deep during an epic mountain stage in the 1987 Tour. Pedro Delgado, wearing yellow, had built a substantial lead over his rival on the climb up La Plagne. Yet somehow Roche clawed his way back into contention, appearing at the finish line just 5 seconds down on Delgado. He surprised everyone. He collapsed, exhausted, and had to be given oxygen, but he’d done enough. Roche went on to win the Tour. Formidable!

When you comment on a comment

tag@wordaligned.org (Thomas Guest) — 2010-02-10

@ianbicking these days, I very rarely bother reading anything where I cannot comment. — @drjtwit

You’ll notice there are no comments here. I hate discussing things via blog comments. If you’d like to talk, drop me a line. If you’d like to discuss things in public, post on your blog.

— Coda Hale

When you leave a comment on a comment, how often do you wonder what your rights are? Not too often, I’d guess. Over the years, it has become an accepted fact that content contributed to a website simply belongs to that website. If the website, or blog for today’s web, goes away then all of your contributions disappear along with it. A real world analogy would be sending in letters or artwork to a magazine. There’s usually that disclaimer which says the publication can do whatever with your submission. And, of course, they can’t return anything to you. It belongs to the magazine now.

— Daniel Ha, A commenter’s rights

In a recent blog post Dan Twining writes about blog comments and asks what I think of Disqus, the commenting service used here at Word Aligned. The question comes at an interesting time.

Unlike Blogger, Wordpress, Typepad etc. Disqus isn’t a blogging platform. Disqus do comments, and their central idea is integration. You don’t need yet another online id to leave a disqus comment. Sign in using your OpenID or Yahoo! account, for example. You can have your comments tweeted or posted on Facebook. Disqus works with whatever blogging system you use and it works across different systems: if a blog uses disqus and you post a comment on that blog, then that comment remains yours — the blog owner can’t edit it, and other readers can click through to see comments you’ve posted on other sites. Well, other comments posted using disqus that is. Clearly these connections extend as more sites adopt disqus, and this seems to be happening.
I used to use Haloscan for comments. I switched to Disqus about this time last year. I had no particular complaints with Haloscan; installation was simple, I didn’t get any spam comments, and the service proved reliable enough. It just seemed Haloscan wasn’t going anywhere. As it turns out, Haloscan will soon be gone. They’re shutting down the service this week.
It so happens Dan’s question comes when the action on this site is happening in the comments section. Which makes me think.

Back to Daniel Ha, the Disqus CEO, who has clearly thought harder about comments than I ever will. Towards the top of this note is a quote from his article “A Commenter’s Rights”. Daniel Ha goes on to point out that times have changed, and that online publishers are able to involve their readers and include their input in more sophisticated ways. It’s better for both commenters and publishers, he suggests, if commenters retain rights over their original material.

So what are a commenter’s rights? I’m going to make an initial attempt to materialize what some rights should be.

The ability to edit and remove their comments

Access to all of their comments, even if it has been deleted on a blog

The right to use their own comments as blog posts. After all, a commenter is just a publisher not writing on his own website.

A life for the comment beyond a single blog. I want to take my comments with me, even if the blog shuts down.

This may seem threatening to the publisher, but it really isn’t. A commenter should have rights to what they post, but bloggers should still have control over content that appear on their blogs. Bloggers should still control:

Whether or not someone is allowed to comment on his blog

The deletion of a comment

The modification of a comment, as long as the original copy is still accessible and the edit is transparent
— Daniel Ha, A commenter’s rights

Why bother with site-hosted comments at all? If people want to comment they can do so on specially designed community sites like Proggit or Hacker News. This is the internet: we go where we please, we find what we like.

Well, I guess I included comments on this site because that’s what other blogs did, and because I thought it was a way to engage readers and persuade them to return. The truth is, most readers arrive here via proggit; if I did away with comments here I might get more comments on reddit, and consequently more visits.

Look again at Daniel Ha’s words

When you leave a comment on a comment …

I’m guessing this is a typo, and that he meant “When you leave a comment on a website …”. If so, it’s an interesting slip. Modern comment systems are designed for comments on comments as much as for comments on the original article. Why bother with the original if the comments are more interesting? Jump straight into the discussion!

[…] It’s not that I don’t like sites with comments on, but when you read a site with comments it automatically puts you, the reader, in a defensive mode where you’re saying, “what’s good in this comment thread? What can I skim?”

These are John Gruber’s words but you won’t find them on his Daring Fireball website (the quotation has been transcribed by Shawn Blanc from an interview), and you won’t find comments there either. Have a look at an article on Daring Fireball. Here’s a recent one about Adobe Flash. Now try to imagine how the article would look with comments.

I’ve exported any Haloscan comments left on this site and imported them into Disqus using the disqus developer API. My thanks to Roberto Alsina for his helpful pointers on how to do this. Links to comments will have broken, but everything else should be fine. I’m sticking with comments and I’m sticking with Disqus, which gets better all the time. Please let me know if you spot any problems.

I’ll shut up now.

Power programming

tag@wordaligned.org (Thomas Guest) — 2010-01-26

Powerful or dangerous?

Recently I wrote about one of the Google Code Jam challenges, where, perhaps surprisingly, the best answer — the most elegant and obviously correct answer, requiring the fewest lines of code, with virtually zero space overhead, and running the quickest — the very best answer was coded in C++.

Why should this be surprising? C++ is a powerful language.

In my experience there is almost no limit to the damage that a sufficiently ingenious fool can do with C++. But there is also almost no limit to the degree of complexity that a skillful library designer can hide behind a simple, safe, and elegant C++ interface.

— Greg Colvin, “In the Spirit of C”

Yes. And yes! But in this article I wanted to discuss something C++ can’t do. Let’s start with another challenge from the same round of the 2009 Google Code Jam.

Decision trees

Decision trees — in particular, a type called classification trees — are data structures that are used to classify items into categories using features of those items. For example, each animal is either “cute” or not. For any given animal, we can decide whether it is cute by looking at the animal’s features and using the following decision tree.
(0.2 furry
  (0.81 fast
    (0.3)
    (0.2)
  )
  (0.1 fishy
    (0.3 freshwater
      (0.01)
      (0.01)
    )
    (0.1)
  )
)
— Decision Trees, Google Code Jam 2009

The challenge goes on to describe the structure more formally, then steps through an example calculation. What is the probability, p, that a beaver is cute?

For example, a beaver is an animal that has two features: furry and freshwater. We start at the root with p equal to 1. We multiply p by 0.2, the weight of the root and move into the first sub-tree because the beaver has the furry feature. There, we multiply p by 0.81, which makes p equal to 0.162. From there we move further down into the second sub-tree because the beaver does not have the fast feature. Finally, we multiply p by 0.2 and end up with 0.0324 — the probability that the beaver is cute.

The challenge itself involves processing input comprising a number of test cases. Each test case consists of a decision tree followed by a number of animals. A solution should parse the input and output the calculated cuteness probabilities.

Cuteness calculator

def cuteness(decision_tree, features):
    """Return the probability an animal is cute.
    
    - decision_tree, the decision tree
    - features, the animal's features,
    """
    p = 1.0
    dt = decision_tree
    has_feature = features.__contains__
    while dt:
        weight, *dt = dt
        p *= weight
        if dt:
            feat, lt, rt = dt
            dt = lt if has_feature(feat) else rt
    return p

Calculating an animal’s cuteness given a decision tree and the animal’s features isn’t hard. In Python we don’t need to code up a specialised decision tree class — a nested tuple does just fine. The cuteness() function shown above descends the decision tree, switching left or right according to each feature’s presence or absence. The efficiency of this algorithm is proportional to the depth of the tree multiplied by the length of the feature list; as far as the code jam challenge goes, it’s not a concern.

>>> decision_tree = (
...     0.2, 'furry',
...         (0.81, 'fast',
...             (0.3,),
...             (0.2,),
...         ),
...         (0.1, 'fishy',
...             (0.3, 'freshwater',
...                  (0.01,),
...                  (0.01,),
...             ),
...             (0.1,),
...         ),
...     )
>>> beaver = ('furry', 'freshwater')
>>> cuteness(decision_tree, beaver)
0.032400000000000005

No, the real problem here is how to parse the input data to create the decision trees and feature sets. As you can see, though, the textual specification of a decision tree closely resembles a Python representation of that decision tree. Just add punctuation.

Specification	Python
(0.2 furry (0.81 fast (0.3) (0.2) ) (0.1 fishy (0.3 freshwater (0.01) (0.01) ) (0.1) ) )	(0.2, 'furry', (0.81, 'fast', (0.3,), (0.2,), ), (0.1, 'fishy', (0.3, 'freshwater', (0.01,), (0.01,), ), (0.1,), ), )

Specification

Python

(0.2 furry
  (0.81 fast
    (0.3)
    (0.2)
  )
  (0.1 fishy
    (0.3 freshwater
      (0.01)
      (0.01)
    )
    (0.1)
  )
)

(0.2, 'furry',
  (0.81, 'fast',
    (0.3,),
    (0.2,),
  ),
  (0.1, 'fishy',
    (0.3, 'freshwater',
      (0.01,),
      (0.01,),
      ),
      (0.1,),
  ),
)

Rather than parse the decision tree definition by hand, why not tweak it so that it is a valid Python nested tuple? Then we can just let the Python interpreter eval the tuple and use it directly.

Eval

A program’s ability to read and execute source code at run-time is one of the things which makes dynamic languages dynamic. You can’t do it in C and C++ — no, sneaking instructions past the end of a buffer doesn’t count. Should you do it in Python? Well, it won’t hurt to give it a try.

spec = '''\
(0.2 furry
  (0.81 fast
    (0.3)
    (0.2)
  )
  (0.1 fishy
    (0.3 freshwater
      (0.01)
      (0.01)
    )
    (0.1)
  )
)
'''

tuple_rep = re.sub(r'([\.\d]+|\))', r'\1,', spec)
tuple_rep = re.sub(r'([a-z]+)', r'"\1",', tuple_rep)
decision_tree = eval(tuple_rep)[0]

Here, we start with the input specification of the decision tree (imagine this has been read directly from standard input). The first regex substitution inserts commas after numbers, and right parentheses. The second substitution quotes and inserts a comma after feature strings. This turns the decision tree’s specification into a textual representation of a nested Python tuple. We then eval that tuple and assign the result to decision_tree — a Python decision tree we can go on and use in the rest of our program. And that’s the code jam challenge cracked, pretty much.

>>> from pprint import pprint
>>> pprint(decision_tree)
(0.2,
 'furry',
 (0.81, 'fast', (0.3,), (0.2,)),
 (0.1, 'fishy', (0.3, 'freshwater', (0.01,), (0.01,)), (0.1,)))

(Minor wrinkle: you’ll have spotted the final decision tree is the first element of the evaluated tuple. That’s because the regex substitution puts a trailing comma after the right parenthesis which closes the decision tree specification, which turns tuple_rep into a one-tuple. The single element contained in this one-tuple is what we need.)

Dynamic or hacky?

As you can see, it doesn’t take much code to pull the decision tree in ready for use. Python allows us to convert between text and code and to execute code within the current environment: you just need to keep a clear head and remember where you are. Regular expressions may not have the first class language support they enjoy in Perl and Ruby, but they are well supported, and the raw string syntax makes them more readable.

Certainly, this code snippet is easier to put together than a full blown parser, but I think it will take more than this to convince a C++ programmer that Python is a powerful language, rather than a dangerous tool for ingenious fools. It fails to convince me. I can’t remember ever using eval or exec in production code, where keeping a separation between layers is more important than speed of coding.

Jam to golf

That said, Python is a fine language for scripting, and speed of coding is what matters in this particular challenge. Just for fun, what if there were a prize for brevity? Then of course Perl would win!

Code Jam golf, by gnibbler, Stack Overflow

say("Case #$_:"),
$_=eval"''".'.<>'x<>,
s:[a-z]+:*(/ $&\\s/?:g,s/\)\s*\(/):/g,
eval"\$_=<>;say$_;"x<>for 1..<>

Note that this does more than simply parse a decision tree — it’s a complete solution to the code jam challenge, reading trees, features, calculating cutenesses, and producing output in the required format. Sadly that’s all I can say about it because the details of its operation are beyond me.

Code vs data

Using Python to dynamically execute code may not generally be needed or welcomed in Python production code, and over-reliance on the same trick risks reinforcing Perl’s “write only” reputation, but Python and Perl aren’t the only contenders. The equivalence of code and data marks Lisp’s apotheosis. Take a look at a Lisp solution to the challenge. This one is coded up in Arc.

(def r () (read))
(for i 1 (r)
  (prn "Case #" i ":")
  (r)
  (= z (r))
  (repeat (r)
    (r)
    (loop (= g (n-of (r) (r))
             c z
             p 1)
       c
       (= p (* (pop c) p)
          c (if (pos (pop c) g)
                (c 0)
                (cadr c))))
    (prn p)))

Which challenge does this solve?

I meant the code golf challenge, of solving the decision tree problem using the fewest keystrokes. At 154 characters this Arc program is nearly half as long again as the winning Perl entry, but it’s hardly flabby. What really impresses me, though, is that the code is (almost) as readable as it is succinct. It’s elegant code. The only real scars left by the battle for brevity are the one character variable names. Here’s the same code with improved variable names and some comments added. It’s the (read) calls which evaluate expressions on standard input. The (for ...) and (repeat ...) expressions operate as you might expect. The third looping construct, (loop ...) initialises, tests and proceeds, much like a C for loop.

(for i 1 (read)               ; Read N, # test cases, and loop
  (prn "Case #" i ":")
  
  (read)                      ; Skip L, # lines taken by decision tree
  (= dtree (read))            ; and read the tree in directly
  
  (repeat (read)              ; Repeat over A, # animals
    (read)                    ; Skip animal name
    ; Read in the animal's features and walk down the 
    ; decision tree calculating p, the cuteness probability
    (loop (= features (n-of (read) (read)) 
             dt dtree
             p 1)
       dt
       (= p (* (pop dt) p)
          dt (if (pos (pop dt) features)
                (car dt)
                (cadr dt))))
    (prn p)))

You could argue the elegance of this solution is due to the fact the input comprises a sequence of tokens and S-expressions. If commas had been used to separate input elements and the text fields had been enclosed in quotes, then maybe a Python solution would have been equally clean. Or if the input had been in XML, then we’d be looking to a library rather than eval for parsing the input.

It’s a fair point, but the equivalence of code and data counts as Lisp’s biggest idea. Where Python’s eval is workable but rarely needed, Lisp’s (read) is fundamental.

Powerful language vs power user?

So, the most elegant answer to the code jam decision tree challenge would also be the quickest to write, and it would be written in Lisp. Did code jam champion, ACRush, submit a Lisp solution?

Absolutely not!

Another fundamental thing about Lisp is that it’s straightforward to parse. A C++ expert can knock up an input parser for decision trees and features to order. ACRush brushed this round aside with a perfect score, taking just 45 minutes to code up working C++ solutions to this question and two others. I’ve reproduced his solution to the decision tree challenge at the end of this article. It’s plain and direct. Given the time constraints, I think it exhibits astonishing fluency — the work of someone who can think in C++.

In this article we’ve encountered four programming languages:

Python
Perl
Lisp
C++

These languages are very different but they share features too. They are all mature, popular and well-supported^[1]. Each is a powerful general purpose programming language. But ultimately, the power of the programmer is what matters.

Appendix A: First impressions of Arc

Here’s another revision of the Arc solution, this time decomposed into subfunctions. I found no complete formal documentation of Arc. You’ll have to read the source and follow the forum, and to actually run any code you’ll have to download a an old version of MzScheme. The official line is: by all means have a play, but expect things to change. That said, the language looks delightful, practical, and quite onion free. The tutorial made me smile. Recommended reading.

; The input is a sequence of valid Arc expressions.
; Create some read aliases to execute these.
(= skip read
   decision-tree read
   n-features read 
   n-tests read
   n-animals read)

(def animal-features ()
     ; Get an animal's features
     (skip) ; animal name
     (n-of (n-features) (read)))

(def cuteness (dtree features)
     ; Calculate cuteness from a decision tree and feature set
     (= dt dtree
        p 1.0)
     (while dt
          (= p (* (pop dt) p)
             dt (if (pos (pop dt) features)
                (car dt)
                (cadr dt))))
     p)

; Loop through the tests, printing results
(for i 1 (n-tests)
     (prn "Case #" i ":")
     (skip) ; # lines the tree specification takes
     (= dtree (decision-tree))
     (repeat 
         (n-animals)
         (prn (cuteness dtree (animal-features)))))

Appendix B: C++ solution

Here’s champion ACRush’s C++ solution. I’ve removed some general purpose macros from the top of the file. You can download the original here.

#include <set>
#include <string>
#include <vector>
#include <sstream>
#include <cstdio>
#include <cstdlib>

using namespace std;

vector<string> A;
vector<int> P;
set<string> M;

#define SIZE(X) ((int)(X.size()))

double solve(int H,int T)
{
    H++;T--;
    double p=atof(A[H].c_str());
    if (H==T) return p;
    if (M.find(A[H+1])!=M.end())
        return p*solve(H+2,P[H+2]);
    else
        return p*solve(P[T],T);
}
int main()
{
    freopen("A-large.in","r",stdin);freopen("A-large.out","w",stdout);
    int testcase;
    scanf("%d",&testcase);
    for (int caseId=1;caseId<=testcase;caseId++)
    {
        int nline;
        scanf("%d",&nline);
        A.clear();
        char str[1024];
        gets(str);
        for (int i=0;i<nline;i++)
        {
            gets(str);
            string s="";
            for (int k=0;str[k];k++)
                if (str[k]=='(' || str[k]==')')
                    s+=" "+string(1,str[k])+" ";
                else
                    s+=str[k];
            istringstream sin(s);
            for (;sin>>s;A.push_back(s));
        }
        P.resize(SIZE(A),-1);
        vector<int> stack;
        for (int i=0;i<SIZE(A);i++)
            if (A[i]=="(")
                stack.push_back(i);
            else if (A[i]==")")
            {
                int p=stack[SIZE(stack)-1];
                P[i]=p;
                P[p]=i;
                stack.pop_back();
            }
        int cnt;
        printf("Case #%d:\n",caseId);
        for (scanf("%d",&cnt);cnt>0;cnt--)
        {
            scanf("%s",str);
            M.clear();
            int length;
            for (scanf("%d",&length);length>0;length--)
            {
                scanf("%s",str);
                M.insert(str);
            }
            double r=solve(0,SIZE(A)-1);
            printf("%.12lf\n",r);
        }
    }
    return 0;
}

Appendix C: A Python Solution

import re
from itertools import islice

def cuteness(decision_tree, features):
    p = decision_tree[0]
    if len(decision_tree) > 1:
        _, feat, lt, rt = decision_tree
        p *= cuteness(lt if feat in features else rt, features)
    return p

def read_decision_tree(spec):
    tuple_rep = re.sub(r'([\.\d]+|\))', r'\1,', spec)
    tuple_rep = re.sub(r'([a-z]+)', r'"\1",', tuple_rep)
    return eval(tuple_rep)[0]

def take_lines(lines, n):
    return ''.join(islice(lines, n))

def main(fp):
    lines = iter(fp)
    n_tests = int(next(lines))
    for tc in range(1, n_tests + 1):
        print("Case #%d:" % tc)
        tree_spec = take_lines(lines, int(next(lines)))
        dtree = read_decision_tree(tree_spec)
        n_animals = int(next(lines))
        for line in islice(lines, n_animals):
            features = set(line.split()[2:])
            print(cuteness(dtree, features))

import sys
main(sys.stdin)

Notes

[1] (Arc may not be mature, popular or well-supported; but Lisp certainly is.)

Python, Surprise me!

tag@wordaligned.org (Thomas Guest) — 2009-12-15

A Simple Function

Here’s a simple function which converts the third item of a list into an integer and returns it, returning -1 if the list has fewer than three entries or if the third entry fails to convert.

def third_int(xs):
    '''Convert the third item of xs into an int and return it.
        
    Returns -1 on failure.
    '''    
    try:
        return int(xs[2])
    except IndexError, ValueError:
        return -1

Unfortunately this simple function is simply wrong. Evidently some exceptions aren’t being caught.

>>> third_int([1, 2, 3, 4])
3
>>> third_int([1])
-1
>>> third_int(('1', '2', '3', '4',))
3
>>> third_int(['one', 'two', 'three', 'four'])
Traceback (most recent call last):
    ....
ValueError: invalid literal for int() with base 10: 'three'

How ever did a ValueError sneak past the except clause?

The Real Surprise

There’s nothing mysterious or surprising going on here, but I’ll delay answering this question for a moment. For me, the real surprise about Python is that, generally, I get it right first time. Python similarly caught Eric S. Raymond by surprise. His first surprise was that it took him just 20 minutes to get used to syntactically significant whitespace. And just 100 minutes later …

My second [surprise] came a couple of hours into the project, when I noticed (allowing for pauses needed to look up new features in Programming Python) I was generating working code nearly as fast as I could type. When I realized this, I was quite startled. An important measure of effort in coding is the frequency with which you write something that doesn’t actually match your mental representation of the problem, and have to backtrack on realizing that what you just typed won’t actually tell the language to do what you’re thinking. An important measure of good language design is how rapidly the percentage of missteps of this kind falls as you gain experience with the language.

— Eric S. Raymond, Why Python?

I certainly don’t generate working code as fast as I can type, and I’m not even a particularly quick typist, but I rarely make syntactic errors when writing Python — and I don’t often need to consult the documentation on such matters. As Chuck Allison memorably puts it: “the syntax is so clean it squeaks”.

Parentheses Required(?)

There are some oddities and gotchas though. I don’t object to the explicit self in methods, but I do sometimes forget to write it — especially if I’ve just switched over from C++.

A side-effect of the whitespace thing is that you can’t just wrap a long line. The line ending needs to be escaped.

if 1900 < year < 2100 and 1 <= month <= 12 \
    and 1 <= day <= 31 and 0 <= hour < 24 \
    and 0 <= minute < 60 and 0 <= second < 60: # Looks like a valid date
    return 1

Alternatively, parenthesize.

if (1900 < year < 2100 and 1 <= month <= 12
    and 1 <= day <= 31 and 0 <= hour < 24
    and 0 <= minute < 60 and 0 <= second < 60): # Looks like a valid date
    return 1

In the above, the parentheses aren’t required to group terms, but instead serve to implicitly continue the line of code past a couple of newline characters.

Parentheses serve more than one role in Python’s syntax. As in all C-family languages, they can group expressions. They also get involved building tuples, (1, 2, 3) or ('red', 0xff0000) for example. Beware the special case: a one-tuple needs a trailing comma, ("singleton",). This isn’t something I forget or accidentally omit, but it can make things fiddly. Here’s a tuple-tised tree, where we represent a tree as a tuple whose first element is a node value, and any subsequent elements are sub-trees. Careful with those commas!

tree = (2, (7, (2,), (6, (5,), (11,))), (5, (9, (4,))))

Actually, tuples are just comma-separated lists of expressions — no parentheses required — so we might equally well have written.

tree = 2, (7, (2,), (6, (5,), (11,))), (5, (9, (4,)))

Here, the superfluous outermost parentheses have been omitted; the inner ones are still required for grouping.

How about we always append a trailing comma to our tuples so the one-tuple no longer looks different?

tree = 2, (7, (2,), (6, (5,), (11,))), (5, (9, (4,))),

That’s allowed and fine. Unless we need an empty tuple, that is, in which case the parentheses are required. And a comma would be wrong.

>>> ()
()
>>> (),
((),)
>>> ,
   ....
SyntaxError: invalid syntax
>>> (,)
   ....
SyntaxError: invalid syntax
>>> tuple()
()

Python 3 introduces a nice new syntax for set literals, reusing the braces which traditionally enclose dicts.

>>> ls = { 1, 11, 21, 1211, 111221, 312211 }

Again, beware the edge case: {} is an empty dict, not an empty set.

>>> zs = {}
>>> type(zs)
<class 'dict'>
>>> zs = set()
>>> type(zs)
<class 'set'>

Python 3 allows non-ascii characters in identifiers, but not any old character, so we cannot get away with

>>> ∅ = set()
      ^
SyntaxError: invalid character in identifier

Parentheses are used for function calls too, and also for generator expressions. Here’s a lazy list of squares of numbers less than a million.

>>> sqs = (x * x for x in range(1000000))

Here’s the sum of these numbers.

>>> sum((x * x for x in range(1000000)))
333332833333500000

Actually, we can omit the generator-expression parentheses in the sum. The function call parentheses magically turn the enclosed x * x for x in range(1000000) into a generator expression. As usual, Python does what we want.

>>> sum(x * x for x in range(1000000))
333332833333500000

Serious about Syntax

If you’ve read this far you may well be thinking: “So what?” I haven’t shown any gotchas, merely a few quirks and corner cases. As already mentioned, the real surprise is that Python fails to surprise. Part of this, as I hope I’ve shown here, can be attributed to the interpreter, which positively invites you to experiment; but mainly Python’s clean and transparent design takes the credit. Repeating Eric S. Raymond: you don’t have to “actually tell the language to do what you’re thinking”.

Since I first started using Python the syntax has grown considerably, yet the extensions and additions seem almost as if they’d been planned from the start^[1]. Generator expressions complement list comprehensions. The yield statement fits nicely with iteration.

Even more remarkably, Python 3 has chosen to break backwards compatibility, so it can undo those few early choices which now seem mistakes. Which brings us back to the broken function at the top of this article. Here it is again, docstring omitted for brevity.

def third_int(xs):
    try:
        return int(xs[2])
    except IndexError, ValueError:
        return -1

I really did write a function like this, and I really did get it wrong in just this way. The code is syntactically correct, but I should have written

def third_int(xs):
    try:
        return int(xs[2])
    except (IndexError, ValueError):
        return -1

The parentheses in the except clause are crucial. The formal syntax of this form of try statement is

try1_stmt ::=  "try" ":" suite
               ("except" [expression [("as" | ",") target]] ":" suite)+
               ["else" ":" suite]
               ["finally" ":" suite]

In the corrected version of third_int(), the parentheses group IndexError, ValueError into a single expression, a tuple, and the except clause matches any object with class (or base class) IndexError or ValueError. The broken version is very different, as becomes clear if we use the alternative "as" form.

def third_int(xs):
    try:
        return int(xs[2])
    except IndexError as ValueError:
        return -1

Here, the except clause will match an object with class or base class IndexError, and assigns that object to the target, which is called ValueError (and which shadows the “real” ValueError in the rest of the function definition). If int() raises a ValueError, it will not be matched.

Won’t Get Fooled Again

Oh, I get it, now. It is a bit subtle, but I won’t make that mistake again.

Wait, there’s more! In Python 3k, my broken implementation is properly broken — a syntax error.

Python 3.1
>>> def third_int(xs):
...     try:
...         return int(xs[2])
...     except IndexError, ValueError:
  File "<stdin>", line 4
    except IndexError, ValueError:
                     ^
SyntaxError: invalid syntax

The Python 3k syntax of this form of try statement reads.

try1_stmt ::=  "try" ":" suite
               ("except" [expression "as" target]] ":" suite)+
               ["else" ":" suite]
               ["finally" ":" suite]

You can’t use a comma to capture the target any more. It’s an advance and a simplification. Why am I not surprised?

[1]: With the possible exception of conditional expressions, that is.

Next permutation: When C++ gets it right

tag@wordaligned.org (Thomas Guest) — 2009-11-19

The Next Number Problem

Suppose you have a fixed list of digits chosen from the range 1..9. What numbers can you make with them? You’re allowed as many zeros as you want. Write the numbers in increasing order.

Exactly this puzzle came up in the recent Google Code Jam programming contest:

You are writing out a list of numbers. Your list contains all numbers with exactly D_i digits in its decimal representation which are equal to i, for each i between 1 and 9, inclusive. You are writing them out in ascending order.
For example, you might be writing every number with two ‘1’s and one ‘5’. Your list would begin 115, 151, 511, 1015, 1051.
Given N, the last number you wrote, compute what the next number in the list will be.

The competition has closed now, but if you’d like to give it a go sample input files can be found on the website, where you can also upload your results and have them checked.

Here’s a short section from a trial I ran on my computer. Input numbers are in the left-hand column: the corresponding output numbers are in the right-hand column.

50110812884911623516 → 50110812884911623561
82454322474161687049 → 82454322474161687094
82040229261723155710 → 82040229261723157015
43888989554234187388 → 43888989554234187838
76080994872481480636 → 76080994872481480663
31000989133449480678 → 31000989133449480687
20347716554681051891 → 20347716554681051918

Choice of Algorithm

Like many of the code jam challenges, you’ll need to write a program which runs fast enough; but choosing the right algorithm is more important than choosing the right language. Typically a high-level interpreted language like Python allows me to code and test a solution far more quickly than using a low-level language like C or C++.

In this particular case, though, like most successful candidates, I used C++. Here’s why.

Next_permutation transforms the range of elements [first, last) into the lexicographically next greater permutation of the elements. […] If such a permutation exists, next_permutation transforms [first, last) into that permutation and returns true. Otherwise it transforms [first, last) into the lexicographically smallest permutation and returns false.

Although the next number problem appears to be about numbers and lexicographical ordering appears to be about words, std::next_permutation is exactly what’s needed here.

Lexicographical Ordering

A dictionary provides the canonical example of lexicographical ordering. Words are built from characters, which can be alphabetically ordered A, B, C, … , so in the dictionary words which begin with A appear before words which begin with B, which themselves come in front of words beginning with C, etc. If two words start with the same letter, pop that letter from the head of the word and compare their tails, which puts AARDVARK before ANIMAL, and — applying this rule recursively — after AARDMAN. Imagine there’s an empty word marking position zero, before A, right at the front of the dictionary, and our recursive definition is complete.

Next permutation in action

Here’s a simple program which shows next_permutation() in action.

#include <algorithm>
#include <cstdio>

int main()
{
    char xs[] = "123";
    do
    {
        std::puts(xs);
    }
    while (std::next_permutation(xs, xs + sizeof(xs) - 1));
    return 0;
}

This program outputs lexicographically ordered permutations of 1, 2 and 3. When the main function returns, the array xs will have cycled round to hold the lexicographically smallest arrangement of its elements, which is "123". Note that we never convert the characters '1', '2', '3' into the numbers 1, 2, 3. The values of both sets of data types appear in the same order, so all works as expected.

If we tweak and rerun the same program with xs initialised to "AAADKRRV" we get rather more output.

AAADKRRV
AAADKRVR
AAADKVRR
...
AARDVARK
...
VRRKAADA
VRRKADAA
VRRKDAAA

The sequence doesn’t start by repeating "AAADKRRV" 6 times, once for every permutation of the 3 A’s. Only strictly increasing permutations are included. And although the repeated calls to next_permutation generate a series of permutations, the algorithm holds no state. Each function call works on its input range afresh.

This second run of the program yields 3360 lines of output, even though there are 8! = 40320 possible permutations of 8 characters. Each unique permutation corresponds to 3! × 2! = 12 actual permutations of the 8 characters (because there are 3 A’s and 2 R’s), and 40320 ÷ 12 is 3360.

Snail sort’s revenge

As you can see, next_permutation sorts an input range, one step at a time. When next_permutation eventually returns false, the range will be perfectly ordered. Hence we have snail_sort(), hailed by the SGI STL documentation as the worst known deterministic sorting algorithm.

template <class Iter> 
void snail_sort(Iter first, Iter last)
{
    while (next_permutation(first, last)) {}
}

Very witty, and evidence that code can be both elegant and inefficient.

In two important edge cases, though, snail_sort performs on a par with super-charged quicksort!

I snail sorted an array filled with 100000000 zeros in 0.502 seconds. Running quicksort on the same array took 5.504 seconds.
Starting with an array of the same size filled with the values 99999999, 99999998, 99999997, … 1, 0 snail sort’s 0.500 seconds trounced quicksort’s 4.08 seconds.

The Next Number, Solved

Here’s an outline solution to the next number problem. (I’ve glossed over the exact input and output file formats for clarity.) It reads numbers from standard input and writes next numbers to standard output. Next_permutation does the hard work, and there’s a bit of fiddling when we have to increase the number of digits by adding a zero.^[1]

#include <algorithm>
#include <iostream>

/*
 Given a string of digits, shift any leading '0's
 past the first non-zero digit and insert an extra zero.
 
 Examples:
  
 123 -> 1023
 008 -> 8000
 034 -> 3004
*/
void insert_a_zero(std::string & number)
{
    size_t nzeros = number.find_first_not_of('0');
    number = number.substr(nzeros);
    number.insert(1, nzeros + 1, '0');
}

/*
 Outline solution to the 2009 code jam Next Number problem.
 
 Given a string representing a decimal number, find the next
 number which can be formed from the same set of digits. Add
 another zero if necessary. Repeat for all such strings read
 from standard input.
*/
int main()
{
    std::string number;
    while (std::cin >> number)
    {
        if (!next_permutation(number.begin(), number.end()))
        {
            insert_a_zero(number);
        }
        std::cout << number << '\n';
    }
    return 0;
}

Implementation

Having used the C++ standard library to solve the puzzle, let’s take a look at how it works. Next permutation is a clever algorithm which shuffles a collection in place. My system implements it like this^[2].

template<typename Iter>
bool next_permutation(Iter first, Iter last)
{
    if (first == last)
        return false;
    Iter i = first;
    ++i;
    if (i == last)
        return false;
    i = last;
    --i;
        
    for(;;)
    {
        Iter ii = i;
        --i;
        if (*i < *ii)
        {
            Iter j = last;
            while (!(*i < *--j))
            {}
            std::iter_swap(i, j);
            std::reverse(ii, last);
            return true;
        }
        if (i == first)
        {
            std::reverse(first, last);
            return false;
        }
    }
}

We start with a range delimited by a pair of bi-directional iterators, [first, last). If the range contains one item or fewer, there can be no next permutation, so leave the range as is and return false. Otherwise, enter the for loop with an iterator i pointing at the final item in the range.

At each pass through the body of this for loop we decrement i by one, stepping towards the first item in the range. We are looking for one of two conditions:

the value pointed to by i is smaller than the one it pointed to previously
i reaches into the first item in the range

Put another way, we divide the range into a head and tail, where the tail is the longest possible decreasing tail of the range.

If this tail is the whole range (the second condition listed above) then the whole range is in reverse order, and we have the lexicographical maximum formed from its elements. Reversing the range returns it to its lexicographical minimum, and we can return false.

If this tail is not the whole range, then the final item in the head of the range, the item i points to, this item is smaller than at least one of the items in the tail of the range, and we can certainly generate a greater permutation by moving the item towards the end of the range. To find the next permutation, we reverse iterate from the end of the range until we find an item *j bigger than *i — that’s what the while loop does. Swapping the items pointed to by i and j ensures the head of the range is bigger than it was, and the tail of the range remains in reverse order. Finally, we reverse the tail of the range, leaving us with a permutation exactly one beyond the input permutation, and we return true.

What’s happening here?

It’s clear from this paper analysis that the algorithm is of linear complexity. Essentially, it walks up and down the tail of the list, comparing and swapping. But why does it work?

Let xs be the range (first, last). As described above, divide this range into prefix and suffix subranges, head and tail, where tail is the longest monotonically decreasing tail of the range.

If the head of the range is empty, then the range xs is clearly at its lexicographical maximum.

Otherwise, tail is a lexicographical maximum of the elements it contains, and xs is therefore the largest permutation which starts with the subrange head. What will the head of the next permutation be? We have to swap the final item in head with the smallest item of tail which exceeds it: the definition of tail guarantees at least one such item exists. Now we want to permute the new tail to be at a its lexicographical minimum, which is a matter of sorting it from low to high.

Since tail is in reverse order, finding the smallest item larger than head[-1] is a matter of walking back from the end of the range to find the first such items; and once we’ve swapped these items, tail remains in reverse order, so a simple reversed will sort it.

As an example consider finding the next permutation of:

8342666411

The longest monotonically decreasing tail is 666411, and the corresponding head is 8342.

8342 666411

666411 is, by definition, reverse-ordered, and cannot be increased by permuting its elements. To find the next permutation, we must increase the head; a matter of finding the smallest tail element larger than the head’s final 2.

8342 666411

Walking back from the end of tail, the first element greater than 2 is 4.

8342  666411

Swap the 2 and the 4

8344 666211

Since head has increased, we now have a greater permutation. To reduce to the next permutation, we reverse tail, putting it into increasing order.

8344 112666

Join the head and tail back together. The permutation one greater than 8342666411 is 8344112666.

Beautiful C++?

C++ has its detractors, who characterise it as subtle, complex, and dangerous; but sometimes it excels. Look once more at the C++ implementation of this algorithm.

template<typename Iter>
bool next_permutation(Iter first, Iter last)
{
    if (first == last)
        return false;
    Iter i = first;
    ++i;
    if (i == last)
        return false;
    i = last;
    --i;
    
    for(;;)
    {
        Iter ii = i;
        --i;
        if (*i < *ii)
        {
            Iter j = last;
            while (!(*i < *--j))
            {}
            std::iter_swap(i, j);
            std::reverse(ii, last);
            return true;
        }
        if (i == first)
        {
            std::reverse(first, last);
            return false;
        }
    }
}

With its special cases, boolean literals, multiple returns (4, count them!), disembodied and infinite loops, this code fails to exhibit conventional beauty. Yet it is beautiful. All the next permutation algorithm needs are iterators which can advance forwards or backwards, step by step. And that’s all this implementation uses.

I’m as excited as anyone by the mathematical rigour of functional programming, but sometimes computer science is about algorithms with virtually no space overhead, algorithms which loop rather than recurse. Sometimes it’s about shuffling, nudging and swapping — operations which map directly to the machine’s most primitive operations. In such cases, C++ gets it right.

Permutations in Python

For the code jam, though, as mentioned earlier, having a super-fast program rarely matters. More often, it’s about developing a fast enough program super-quickly.

I find Python a far quicker language for developing code than C++. (Indeed, sometimes when it’s obvious from the outset that a final program will need implementing in C++, I put together a working prototype using Python, which I then translate.) Could we solve the next number problem using code from the standard Python library?

At a first glance, itertools.permutations looks promising.

itertools.permutations(iterable, r=None)
Return successive r length permutations of elements in the iterable.
If r is not specified or is None, then r defaults to the length of the iterable and all possible full-length permutations are generated.
Permutations are emitted in lexicographic sort order. So, if the input iterable is sorted, the permutation tuples will be produced in sorted order.
Elements are treated as unique based on their position, not on their value. So if the input elements are unique, there will be no repeat values in each permutation.

However, this algorithm doesn’t care about the values of the items in the iterable, and the lexicographic sort order applies to the indices of these items. So although the ordering of the generated items is well-defined:

we get repeats, and
it’s not the ordering we want (in this case)

>>> from itertools import permutations
>>> concat = ''.join
>>> list(map(concat, permutations('AAA')))
['AAA', 'AAA', 'AAA', 'AAA', 'AAA', 'AAA']
>>> list(map(concat, permutations('231')))
['231', '213', '321', '312', '123', '132']

It is possible to code up next_permutation using nothing more than the standard itertools, but it isn’t advisable.

Snail permute

from itertools import permutations, groupby

def next_permutation(xs):
    """Calculate the next permutation of the sequence xs.
    
    Returns a pair (yn, xs'), where yn is a boolean and xs' is the 
    next permutation. If yn is True, xs' will be the lexicographic 
    next permutation of xs, otherwise xs' is the lexicographic 
    smallest permutation of xs.
    """
    xs = tuple(xs)
    if not xs:
        return False, xs
    else:
        ps = [p for p, gp in groupby(sorted(permutations(xs)))]
        np = len(ps)
        ix = ps.index(xs) + 1
        if ix == len(ps):
            return False, ps[0]
        else:
            return True, ps[ix]

As it happens, a solution based on this exhaustive search would score points in the code jam since it copes with the small input set. For the large input set its factorial complexity rules it out, and we’d need to implement the next permutation algorithm from scratch.

[1]: A more cunning solution avoids the special case by pushing the extra zero to head of the string before applying next_permutation, then popping it if it hasn’t been moved.

[2]: I’ve tweaked the layout and parameter names for use on this site.

Python on Ice

tag@wordaligned.org (Thomas Guest) — 2009-10-28

A moratorium on Python changes is probably a good thing—the last edition of my book nearly made my head explode. — @dabeaz

Python?

“Python?”

“Yes, Python. It’s a high-level language, we used it for the prototype. We can use it for parts of the system where performance isn’t critical. Connecting components together. The web server.”

“But what will we do when Python changes? It’s a developing language, right? How can we maintain our system.”

Not an issue, I explained. Python takes backwards compatibility very seriously. Besides, we choose which version of Python to deploy with, we choose when we migrate — maybe never. Look, you can download the source for every version of Python ever released. All you need is a C compiler. C is the porting layer, if you like, and C isn’t going anywhere in a hurry.

In all honesty, I expected more maintenance issues with the C++ parts of our product, where the language may not have changed in a decade but compilers are only just catching up with it; and in fact I didn’t have to argue for long to persuade senior management, not on this issue at least. They’d already seen how quickly I could get things up and running using Python. Even though the company had more experience with C, C++, Java, and even .Net, I convinced them Python had a role on the server-based system we were developing.

Nonetheless, I didn’t think it the right time to mention Python 3. Why confuse things?

Twisted 8.1 on Python 2.5

I won’t go into detail about the product. Data flowed through it, redirected dynamically using tees and filters, and robots were attached to the resulting streams to monitor them. A web UI presented controls and a view of the system. We used C and C++ for managing the bulk of the flow. The robots we coded in both Python and C++. We connected and coordinated everything using Twisted, a Python networking engine. Our initial deployment used Python 2.5 and Twisted 8.1. We’ve since upgraded to Python 2.6 and Twisted 8.2.

Python 3 on Word Aligned

At work there was no question of using Python 3 even though it became available when we started development. Twisted hadn’t been released against Python 3 (it still hasn’t) and even if it had been, we wouldn’t have trusted it immediately. Here at Word Aligned, though, I switched to Python 3 pretty much as soon as it was officially released. Since the start of 2009, any Python code published on this site has been written in Python 3.

Since then I’ve come to question my decision. I want people to visit my site and I want them to stay long enough to read any code here. Python is perfect because it’s readable and accessible. Anyone who’s ever written a program, whatever the language, can understand Python. But many times I’ve felt the need to explain my Python 3 code, not to Java, C#, C++ and C users, not even to Perl and Ruby users, but to Python users!

Note that in Python 3 … whereas in Python 2 … available in Python 3.1 only … you’d need to write … from __future__ import print_function

I wouldn’t have felt the need to say any of this if I’d stuck with Python 2.

Python 3 absent from Europython

At Europython 2009 I was struck by the absence of Python 3 from the agenda. None of the sessions covered Python 3, used Python 3, or even mentioned Python 3 (unless you count David Jones’ talk on Loving Old Versions of Python). The only Python 3 code I saw appeared on the conference bag; a lightly obfuscated script which printed out the conference destination. Note that print is being used in a way which works with both 2.x and 3.x — that is, with parentheses and taking a single parameter. Very few systems resolve /usr/bin/env python as Python 3, though^[1], which is lucky since even this simple function raises an exception under Python 3 (and transforming the code using 2to3 makes it worse).

This Python 3 silence was at last broken during the question and answer session which followed the final keynote on the final day of the conference. An audibly nervous member of the audience asks Python Software Foundation supremo Steve Holden a question:

Audience member: A source of confusion is the Python 2 Python 3 thing. How are you going about getting people to move from Python 2 to Python 3?

Steve Holden: I’m not trying to get people to move to Python 3. [Audience applauds].

Steve Holden went on to round out this answer, saying that 2.6 is the recommended production version of Python. Anyone who took Python 3.0 into production, he said, would have been “kicked in the teeth by the fact that the IO subsystem performed execrably slowly, it was really dreadful” — a fact the 3.0 release notes failed to mention, but which has been fixed in Python 3.1. For teaching purposes, or for greenfield development which doesn’t need to reuse other people’s code, by all means try Python 3, he said. Python 3 is the future of Python. There’s a migration strategy in place.

And what about the overhead on the core Python development team, who now have two versions to maintain? Well, Steve Holden said, there are tools to automate patching and merging, but yes, there’s an overhead.

(To hear the question and full response, there’s a video at blip.tv. Fast forward to 52 minutes and 40 seconds.)

Python 3 Literature

How have book authors reacted to Python 3? Mark Pilgrim has dived in with aplomb. His introductory book, Dive into Python 3, uses Python 3 as Python 3 was intended. For example, you won’t find % characters used in string formatting; {up to date braces are used exclusively}. It’s an engaging, painstakingly-written book, and (bonus!) the online version is an object lesson in how to craft HTML.

David Beazley attacks the problem in a different way, but then his subject is different. His comprehensive Python Essential Reference aims to cover the core language and its standard library in its entirety: think of it as the reference any serious Python programmer would like to have within reach. David Beazley’s approach is to concentrate on the common subset of Python 2 and 3, omitting features of 2 which aren’t in 3 and avoiding features of 3 which haven’t been backported to 2. His book succeeds but it does raise some awkward questions. Will Pythonistas find themselves maintaining parallel code-bases, and end up twisting their code until it fits into the intersection of two flavours of the language?

Or will they simply avoid Python 3?

David Beazley eventually covers new Python 3 features in an appendix, by which time the strain has started to show:

Finally, even though Python 3.0 is described as the latest and greatest, it suffers from numerous performance and behavioral problems […] in the opinion of this author, Python 3.0 is really only suitable for experimental use by seasoned Python veterans.

The Cost of Python 3

David Beazley may have ended up feeling like a Python 3 beta tester, but, as discussed at the start of this article, most Python users have a free choice. We can live a little longer with Python 2 warts in exchange for a proven platform and an excellent set of supporting libraries. We can try and write to a language subset. We can use Python 2 and import much of the future. Or we can dive into Python 3.

The people who must find the language fork tough are the Python suppliers. Our choice, as consumers, means work for them: we’ve mentioned the core Python team, who must surely spend more time patching and testing; think of Python library writers (such as the wizards behind Twisted).

There’s another important class of supplier: the people working on alternative Python implementations, the ones which work on Java, or .Net, the ones which have no global interpreter lock, the ones which can run deeply recursive functions. Pythonistas are understandably excited about Unladen Swallow, a development branch of CPython 2.6. Just look at the project goals!

We want to make Python faster, but we also want to make it easy for large, well-established applications to switch to Unladen Swallow.

Produce a version of Python at least 5x faster than CPython.

Python application performance should be stable.

Maintain source-level compatibility with CPython applications.

Maintain source-level compatibility with CPython extension modules.

We do not want to maintain a Python implementation forever; we view our work as a branch, not a fork.

In summary, if Unladen Swallow touches down safely, it will become CPython, and anyone using CPython will benefit from a high-level language capable of performing at native speeds.

I’d like to highlight the final goal, the one about maintaining, branching and forking. Unladen Swallow is a branch taken from CPython 2.6^[2]. If it succeeds, much hard and unglamorous work will be needed to merge it to the latest CPython 2, and patch it across to CPython 3. Python implementers must pay a high price, in terms of increased workload, for the Python 2, Python 3 fork.

Could Python have evolved in a more linear way, by deprecating then removing features, while adding in new ones? I guess not, a mature language wouldn’t dare break backwards compatibility.

Would it?

Evolution of Python

My employers were right to characterise Python as a developing language. On the subject of incremental change, I wanted to highlight again the evolution of the multiset in Python, from Python 1.4, released in 2001, through to Python 3.1, just 4 months old.

Evolution of the Multiset in Python

def multiset_14(xs):
    multiset = {}
    for x in xs:
        if multiset.has_key(x):
            multiset[x] = multiset[x] + 1
        else:
            multiset[x] = 1
    return multiset

def multiset_15(xs):
    multiset = {}        
    for x in xs:
        multiset[x] = multiset.get(x, 0) + 1
    return multiset

import collections

def multiset_25(xs):
    multiset = collections.defaultdict(int)
    for x in xs:
        multiset[x] += 1
    return multiset

def multiset_31(xs):
    return collections.Counter(xs)

Lovely!

multiset_14() won’t work in Python 3, and multiset_31() won’t work in Python 2 (not yet, anyway).

Accepting Python 3

The main goal of the Python development community at this point should be to get widespread acceptance of Python 3000. — Guido van Rossum, 2009-10-21

Unlike Steve Holden, Guido van Rossum is trying to get people to move to Python 3, or at least to accept it. Here’s how:

I propose a moratorium on language changes. This would be a period of several years during which no changes to Python’s grammar or language semantics will be accepted. The reason is that frequent changes to the language cause pain for implementers of alternate implementations (Jython, IronPython, PyPy, and others probably already in the wings) at little or no benefit to the average user (who won’t see the changes for years to come and might not be in a position to upgrade to the latest version for years after).

Wow!

I’m not close enough to Python development to know exactly what’s involved here, but a scan of the email thread suggests this proposal has been widely accepted. I think it’s clear from the rest of this article that I sympathise with the motivation behind it. Yet I can’t help feeling uneasy about putting Python on ice. Yes, there have been changes to the language grammar over the past fifteen years. I wouldn’t say they’ve been frequent, and there aren’t many I’d want to do without, even if I only get to use them (in production) a year or two after they’ve been released. Yes, these changes cause pain to implementers^[3], but that’s not the whole story. Who said implementing a language would be easy? Perhaps much of the pain comes from implementing the changes twice, once for 2 and once for 3.

Soon there’ll be a PEP stating more formally what exactly a moratorium on language changes will mean. That is,

A Python Enhancement Proposal which Proposes: Stop Enhancing Python!

[1] I wonder if anyone can guess why this code fails, just by looking at it? As a hint, highlight the rest of this paragraph. Some Python 2 codecs are byte rather than text oriented, and Python 3 prohibits this kind of confusion.

[2] More details of the Unladen Swallow branch approach.

In order to achieve our combination of performance and compatibility goals, we opt to modify CPython, rather than start our own implementation from scratch. In particular, we opt to start working on CPython 2.6.1: Python 2.6 nestles nicely between 2.4/2.5 (which most interesting applications are using) and 3.x (which is the eventual future). Starting from a CPython release allows us to avoid reimplementing a wealth of built-in functions, objects and standard library modules, and allows us to reuse the existing, well-used CPython C extension API. Starting from a 2.x CPython release allows us to more easily migrate existing applications; if we were to start with 3.x, and ask large application maintainers to first port their application, we feel this would be a non-starter for our intended audience.

[3]: C++ compiler writers, gear up for C++0x!

Steady on Subversion

tag@wordaligned.org (Thomas Guest) — 2009-10-13

My secret shame

In a world of distributed version control systems I’m ashamed to confess I still use Subversion. We use it at work, exclusively. I use it at home, by default. Worse still, in a small way, I help promote and perpetuate this antiquated version control system: if you want to mirror a Subversion repository or set up a Subversion pre-commit hook, you may well find some faded notes I wrote on these subjects.

Whisper the words. I still like Subversion.

What do I like most? The command to revert a change. Merge it backwards.

$ svn merge --change -666

Branches and tags are one and the same. For someone who grew up with CVS, that’s quite a relief. Anyone can grasp the versioned file tree model. No one wants their version control system to surprise them. My boss, who doesn’t get to program as much as he’d like, has discovered a shiny Subversion client — and he doesn’t even use Windows. The sales team, who do use Windows, can use Subversion to collaborate on their office documents. TortoiseSVN interfaces to the Word diff tool, a nice touch. And software developers can surely find stable Subversion plug-ins for whatever tools they use.

The Subversion documentation is solid and has been for some while. I’m surprised anyone ever arrives at my website seeking tips, but arrive they do, and in ever-increasing numbers.

Subversion does enough. The hard parts of my job are deciding what software to write, writing it, and working as a team. Version control should be frictionless, the easy bit. Which it is.

Of course Subversion has weak points. It should be faster (whee, see how git flies!) and merging can be irksome (improving on CVS wasn’t much of a target). But the biggest annoyance I’ve had with Subversion is caused by its ubiquity and its continuing upgrade trajectory. Somehow I’ve ended up accessing 1.4 and 1.5 format repositories on a machine which hosts 1.4, 1.5 and 1.6 clients in /usr/local/bin, /usr/bin and /opt/local/bin, not necessarily in that order. Silly me, I’m sorted now, I think, but I’d happily see Subversion go into maintenance mode. For managing change, give me stable software.

Do it the same, but better!

As mentioned at the start of this post, though, the world of version control has itself changed. Subversion represents evolution: by being a better CVS, it aimed to supplant its ancestor and become the VCS of choice for open source projects. CVS has indeed been supplanted, but true progress has come from the distributed version control revolution.

We’ve been talking about a single, central source tree which develops in discrete steps. Everyone has a local working copy of the files in this tree, which they keep up to date, routinely merging changes back to base. Check out, check in. It is an easy model to understand, but in practice there can be problems. What happens when you can’t access the tree? Or when it gets pulled in different directions? Or when you lose track of who merged what where when? Now consider the distributed version control world, where the model extends to multiple trees. Everyone copies the entire repository as needed. Clone, merge.

In this distributed world a project needn’t have a single, central repository^[1]. What’s more, there is no single leading distributed version control system. As a result, open source projects are spoiled for choice.

The rise of the DVCS is a fascinating history, though one I’ve yet to directly engage with — unless you count the growing collection of DVCSes taking root on my hard disk (none of which shipped with my operating system). I like the feel of git. Python will migrate to mercurial. For now, I’m staying put.

Definitive commentary

Ben Collins-Sussman is one of the original designers and developers of Subversion, and co-author of Version Control with Subversion. His essays on the changing field of version control make fine reading. A couple of years ago he wrote:

Today, Subversion has now gone from “cool subversive product” to “the default safe choice” for both 80% and 20% audiences. The 80% companies who were once using crappy version control (or no version control at all) are now blogging to one another — web developers giving “hot tips” to each other about using version control (and Subversion in particular) to manage their web sites at their small web-development shops. What was once new and hot to 20% people has finally trickled down to everyday-tool status among the 80%.

The great irony here … is that Subversion was originally intended to subvert the open source world. It’s done that to a reasonable degree, but it’s proven far more subversive in the corporate world!

— Ben Collins-Sussman, Version Control and “the 80%”, October 2007

In April last year he followed up with:

[…] we think that [Subversion] will probably be the “final” centralized system that gets written in the open source world — it represents the end-of-the-line for this model of code collaboration.

It will continue to be used for many years, but specifically it will gain huge mindshare in the corporate world, while (eventually) losing mindshare to distributed systems in the open-source arena … Subversion isn’t anywhere near “fading away”. Quite the opposite: its adoption is still growing quadratically in the corporate world, with no sign of slowing down. This is happening independently of open source trailblazers losing interest in it. It may end up becoming a mainly “corporate” open source project (that is, all development funded by corporations that depend on it), but that’s a fine way for a piece of mature software to settle down.

— Ben Collins-Sussman, Subversion’s Future, April 2008

Long live Subversion

Ben Collins-Sussman backs up his essay with a graph showing the increasing numbers of Apache Subversion servers discoverable on the internet. His claims square with my personal experience. I’m a corporate Subversion user and I don’t see my employer switching version control systems any time soon (it’s my decision as much as anyone’s). What’s more, Subversion is used in most of the companies I know of, where it has supplanted both legacy and proprietary systems. As stated already, version control isn’t the hard part of my job, but should I ever need to change jobs, Subversion won’t stand in my way.

[1]: A project may well choose to nominate a single central repository as the “master” repository. The functionality offered by distributed version control systems is effectively a superset of that offered by centralised ones.

Favicon

tag@wordaligned.org (Thomas Guest) — 2009-09-16

On the subject of this site, I wanted to mention the recent addition of a favicon . Per pixel, it’s cost me more effort than any other feature; but then it’s accessed more than any other asset. It’s meant to be a piece from a jigsaw puzzle. I got the idea when re-reading Life A User’s Manual. I like puzzles and piecing things together.

Perec’s great masterpiece is packed with interwoven stories and trickery, but at its heart is the epic battle between the millionaire, Bartlebooth, and the puzzle-maker Gaspard Winckler. Bartlebooth begins his campaign by learning how to paint, which takes him 10 years. For the next 20 years he travels the world, painting a water colour picture of a different port every couple of weeks. He sends the paintings back home to Paris. On receipt, Winckler glues each picture to a board which he then cuts, making a series of jigsaw puzzles for Bartlebooth to solve on his return. Once Bartlebooth completes each puzzle, an ingenious process is used to glue its pieces together and re-join the cut fibres of the paper; then the picture itself is lifted from the board, returned to the port it depicts, and washed clean in the sea; and finally the paper is returned in something close to its original state to Bartlebooth.

Thus, after 50 years of work, there will be nothing to show.

In the book’s preamble Perec describes familiar die-cut jigsaws, classifying the best known pieces of such puzzles as “little chaps”, “double crosses” and “crossbars”. Such diversions are eschewed by the true puzzler:

The art of jigsaw puzzling begins with wooden puzzles cut by hand, whose maker undertakes to ask himself all the questions the player will have to solve, and, instead of allowing chance to cover his tracks, aims to replace it with cunning, trickery and subterfuge. All the elements occurring in the image to be reassembled — this armchair covered in gold brocade, that three-pointed black hat with its rather ruined black plume, or that silver-braided bright yellow livery — serve by design as points of departure for trails that lead to false information.

My thanks to Tim Beard for scanning a couple of pages from his edition of La Vie, Mode d’Emploi. I wanted to know what the “little chaps” etc. were before they got translated into English. I realise my favicon could be improved but I don’t know how to go about it. Anyone?

Code Rot

tag@wordaligned.org (Thomas Guest) — 2009-09-03

Those of us who have to tiptoe around non-standard or ancient compilers will know that template template parameters are off limits.

— Hubert Matthews (PDF)

Dvbcodec Fail

Long ago, way back in 2004, I wrote an article for Overload describing how to use the Boost Spirit parser framework to generate C++ code which could convert structured binary data to text. I went on to republish this article on my own website, where I also included a source distribution.

Much has changed since then. The C++ language may not have, but compiler and platform support for it has improved considerably. Boost survives — indeed, many of its libraries will feed into the next version of C++. Overload thrives, adapting to an age when printed magazines about programming are all but extinct. My old website proved less durable: I’ve changed domain name and shuffled things around more than once. But you can still find the article online if you look hard enough, and recently someone did indeed find it. He, let’s call him Rick, downloaded the source code archive, dvbcodec-1.0.zip, extracted it, scanned the README, typed:

$ make

… and discovered the code didn’t even build.

At this point many of us would assume (correctly) the code had not been maintained. We’d delete it and write off the few minutes it took to evaluate it. Rick decided instead to contact me and let me know my code was broken. He even offered a fix for one problem.

Code Rot

Sad to say, I wasn’t entirely surprised. I no longer use this code. Unused code stops working. It decays.

I’m not talking about a compiled executable, which the compiler has tied to a particular platform, and which therefore progressively degrades as the platform advances. (I’ve heard stories about device drivers for which the source code has long been lost, and which require ever more elaborate emulation shims to keep them alive.) I’m talking about source code. And the decay isn’t usually literal, though I suppose you might have a source listing on a mouldy printout, or an unreadable floppy disk.

No, the code itself is usually a pristine copy of the original. Publishers often attach checksums to source distributions so readers can verify their download is correct. I hadn’t taken this precaution with my dvbcodec-1.0.zip but I’m certain the version Rick downloaded was exactly the same as the one I created 5 years ago. Yet in that time it had stopped working. Why?

Standard C++

As already mentioned, this was C++ code. C++ is backed by an ISO standard, ratified in 1998, with corrigenda published in 2003. You might expect C++ code to improve with age, compiling and running more quickly, less likely to run out of resources.

Not so. My favourite counter-example comes from a nice paper “CheckedInt: A policy-based range-checked integer” (PDF) published by Hubert Matthews in 2004 which discusses how to use C++ templates to implement a range-checked integer. The paper includes a source code listing together with some notes to help readers forced to “tiptoe around non-standard or ancient compilers” (think: MSVC6). Yet when I experimented with this code in 2005 I found myself tripped up by a strict and up-to-date compiler.

$ g++ -Wall -c checked_int.cpp
checked_int.cpp: In constructor `CheckedInt<low, high, ValueChecker>::CheckedInt(int)':
checked_int.cpp:45: error: there are no arguments to `RangeCheck' that
depend on a template parameter, so a declaration of `RangeCheck' must
be available
checked_int.cpp:45: error: (if you use `-fpermissive', G++ will accept
your code, but allowing the use of an undeclared name is deprecated)

I emailed Hubert Matthews using the address included at the top of his paper. He swiftly and kindly put me straight on how to fix the problem.

What’s interesting here is that this code is pure C++, just over a page of it. It has no dependencies on third party libraries. Hubert Matthews is a C++ expert and he acknowledges the help of two more experts, Andrei Alexandrescu and Kevlin Henney, in his paper. Yet the code fails to build using both ancient and modern compilers. In its published form it has the briefest of shelf-lives.

Support Rot

Code alone is of limited use. What really matters for its ongoing health is that someone cares about it — someone exercises, maintains and supports it. Hubert Matthews included an email address in his paper and I was able to contact him using that address.

How well would my code shape up on this front? Putting myself in Rick’s position, I unzipped the source distribution I’d archived 5 years ago. I was pleased to find a README which, at the very top, provides a URL for updates, http://homepage.ntlworld.com/thomas.guest. I was less pleased to find this URL gave me a 404 Not Found error. Similarly, when I tried emailling the project maintainer mentioned in the README, I got a 550 Invalid recipient error: the attempted delivery to thomas.guest@ntlworld.com had failed permanently.

Cool URIs don’t change but my old NTL homepage was anything but cool; it came for free with a dial-up connection I’ve happily since abandoned. Looking back, maybe I should have found a more stable location for my code. If I’d set up (e.g.) a Sourceforge project then my dvbcodec project might still be alive and supported, possibly even by a new maintainer.

How did this ever compile?

Wise hindsights wouldn’t resurrect my code. If I wanted to continue I’d have to go it alone. Here’s what the README had to say about platform requirements.

REQUIREMENTS and PLATFORMS

To build the dvbcodec you will need Version 1.31.0 of Boost, or later.

You will also need a good C++ compiler. The dvbcodec has been built and tested on the Windows operating system using: GCC 3.3.1, MSVC 7.1

A “good C++ compiler”, eh? As we’ve already seen, GCC 3.3.1 may be good but my platform has GCC 4.0.1 installed, which is better. If my records can be believed, this upperCase() function compiled cleanly using both GCC 3.3.1 and MSVC 7.1.

std::string
upperCase(std::string const & lower)
{
    std::string upper = lower;
    
    for (std::string<char>::iterator cc = upper.begin();
         cc != upper.end(); ++cc)
    {
        * cc = std::toupper(* cc);
    }
    
    return upper;
}

Huh? Std::string is a typedef for std::basic_string<char> and there’s no such thing as a std::basic_string<char><char>::iterator, which is what GCC 4.0.1 says:

stringutils.cpp:58: error: 'std::string' is not a template

The simple fix is to write std::string::iterator instead of std::string<char>::iterator. A better fix, suggested by Rick, is to use std::transform(). I wonder why I missed this first time round?

std::string
upperCase(std::string const & lower)
{
    std::string upper = lower;
    std::transform(upper.begin(), upper.end(), upper.begin(), ::toupper);
    return upper;
}

Boost advances

GCC has become stricter about what it accepts even though the formal specification of what it should do (the C++ standard) has stayed put. The Boost C++ libraries have more freedom to evolve, and the next round of build problems I encountered relate to Boost.Spirit’s evolution. Whilst it would be possible to require dvbcodec users to build against Boost 1.31 (which can still be downloaded from the Boost website) it wouldn’t be reasonable. So I updated my machine (using Macports) to make sure I had an up to date version of Boost, 1.38 at the time of writing.

$ sudo port upgrade boost

Boost’s various dependencies triggered an upgrade of boost-jam, gperf, libiconv, ncursesw, ncurses, gettext, zlib, bzip2, and this single command took over an hour to complete.

I discovered that Boost.Spirit, the C++ parser framework on which dvbcodec is based, has gone through an overhaul. According to the change log the flavour of Spirit used by dvbcodec is now known respectfully as Spirit Classic. A clever use of namespaces and include path forwarding meant my “classic” client code would at least compile, at the expense of some deprecation warnings.

Computing dependencies for decodeout.cpp...
Compiling decodeout.cpp...
In file included from codectypedefs.hpp:11,
                 from decodecontext.hpp:10,
                 from decodeout.cpp:8:
/opt/local/include/boost/spirit/tree/ast.hpp:18:4: warning: #warning "This header is deprecated. Please use: boost/spirit/include/classic_ast.hpp"
In file included from codectypedefs.hpp:12,
                 from decodecontext.hpp:10,
                 from decodeout.cpp:8:

To suppress these warnings I included the preferred header. I then had to change namespace directives from boost::spirit to boost::spirit::classic. I fleetingly considered porting my code to Spirit V2, but decided against it: for even after this first round of changes, I still had a build problem.

Changing behaviour

Actually, this was a second level build problem. The dvbcodec build has multiple phases:

it builds a program to generate code. This generator can parse binary format syntax descriptions and emit C++ code which will convert data formatted according to these descriptions
it runs this generator with the available syntax descriptions as inputs
it compiles the emitted C++ code into a final dvbcodec executable

I ran into a problem during the second phase of this process. The dvbcodec generator no longer parsed all of the supplied syntax descriptions. Specifically, I was seeing this conditional test raise an exception when trying to parse section format syntax descriptions.

    if (!parse(section_format,
               section_grammar,
               space_p).full)
    {
        throw SectionFormatParseException(section_format);
    }

Here, parse is boost::spirit::classic::parse, which parses something — the section format syntax description, passed as a string in this case — according to the supplied grammar. The third parameter, boost::spirit::classic::space_p, is a skip parser which tells parse to skip whitespace between tokens. Parse returns a parse_info struct whose full field is a boolean which will be set to true if the input section format has been fully consumed.

I soon figured out that the parse call was failing to fully consume binary syntax descriptions with trailing spaces, such as the the one shown below.

" program_association_section() {"
"    table_id                   8"
"    section_syntax_indicator   1"
"    '0'                        1"
....
"    CRC_32                    32"
" }                              "

If I stripped the trailing whitespace after the closing brace before calling parse() all would be fine. I wasn’t fine about this fix though. The Spirit documentation is very good but it had been a while since I’d read it and, as already mentioned, my code used the “classic” version of Spirit, in danger of becoming the “legacy” then “deprecated” and eventually the “dead” version. Re-reading the documentation it wasn’t clear to me exactly what the correct behaviour of parse() should be in this case. Should it fully consume trailing space? Had my program ever worked?

I went back in time, downloading and building against Boost 1.31, and satisfied myself that my code used to work, though maybe it worked due to a bug in the old version of Spirit. Stripping trailing spaces before parsing allowed my code to work with Spirit past and present, so I curtailed my investigation and made the fix.

(Interestingly, Boost 1.31 found a way to warn me I was using a compiler it didn’t know about.

boost_1_31_0/boost/config/compiler/gcc.hpp:92:7: warning: 
#warning "Unknown compiler version - please run the configure tests and report the results"

I ignored this warning.)

Code inaction

Apologies for the lengthy explanation in the previous section. The point is, few software projects stand alone, and changes in any dependencies, including bug fixes, can have knock on effects. In this instance, I consider myself lucky; dvbcodec’s unusual three phase build enabled me to catch a runtime error before generating the final product. Of course, to actually catch that error, I needed to at least try building my code.

More simply: if you don’t use your code, it rots.

Rotten artefacts

It wasn’t just the code which had gone off. My source distribution included documentation — the plain text version of the article I’d written for Overload — and the Makefile had a build target to generate an HTML version of this documentation. This target depended on Quickbook, another Boost tool. Quickbook generates Docbook XML from plain text source, and Docbook is a good starting point for HTML, PDF and other standard output formats.

This is quite a sophisticated toolchain. It’s also one I no longer use. Most of what I write goes straight to the web and I don’t need such a fiddly process just to produce HTML. So I decided to freshen up dead links, leave the original documentation as a record, and simply cut the documentation target from the Makefile.

Stopping the rot

As we’ve seen, software, like other soft organic things, breaks down over time. How can we stop the rot?

Freezing software to a particular executable built against a fixed set of dependencies to run on a single platform is one way — and maybe some of us still have an aging Windows 95 machine, kept alive purely to run some such frozen program.

A better solution is to actively tend the software and ensure it stays in shape. Exercise it regularly on a build server. Record test results. Fix faults as and when they appear. Review the architecture. Upgrade the platform and dependencies. Prune unused features, splice in new ones. This is the path taken by the Boost project, though certainly the growth far outpaces any pruning (the Boost 1.39 download is 5 times bigger than its 1.31 ancestor). Boost takes forwards and backwards compatibility seriously, hence the ongoing support for Spirit classic and the compiler version certification headers. Maintaining compatibility can be at odds with simplicity.

There is another way too. Although the dvbcodec project has collapsed into disrepair the idea behind it certainly hasn’t. I’ve taken this same idea — of parsing formal syntax descriptions to generate code which handles binary formatted data — and enhanced it to work more flexibly and with a wider range of inputs. Whenever I come across a new binary data structure, I paste its syntax into a text file, regenerate the code, and I can work with this structure. Unfortunately I can’t show you any code (it’s proprietary) but I hope I’ve shown you the idea. Effectively, the old C++ code has been left to rot but the idea within it remains green, recoded in Python. Maybe I should find a way to humanely destroy the C++ and all links to it, but for now I’ll let it degrade, an illustration of its time.

Is it possible that software is not like anything else, that it is meant to be discarded: that the whole point is to see it as a soap bubble? — Alan J. Perlis

Thanks

I would like to thank to Rick Engelbrecht for reporting and helping to fix the bugs discussed in this article.

This article first appeared in Overload 92, and I would like to thank the team at Overload for their expert help.

A useful octal escape sequence

tag@wordaligned.org (Thomas Guest) — 2009-08-09

Previously I grumbled about octal integer literals, suggesting:

they aren’t much use, not when you’ve got hexademical and binary literals.
they’re risky. As Doug Napoleone noted in a comment, 011 is all too easily read as eleven rather than nine.

Python 3 attempts to patch the readability issue: octal nine must be written as 0o11 or 0O11. Choose your fonts with care, O and 0 look similar!

>>> 0o11, 0O11
(9, 9)

Octal numbers can also appear in escape sequences embedded in string and bytes literals. The syntax hasn’t changed for Python 3 and the rules are as in C: the escape sequence \OOO embeds a character/byte with octal value OOO. Up to three octal digits are allowed in an octal escape sequence.

Like octal integers, these octal escape sequences may appear to be of limited use — a syntactic oddity rarely seen in the wild — but in fact there’s one particular use case which is so common we don’t even notice it.

char const terminator = '\0';

Converting integer literals in C++ and Python

tag@wordaligned.org (Thomas Guest) — 2009-08-06

An integral literal in a C program can be decimal, hexadecimal or octal.

int percent = 110;
unsigned flags = 0x80;
unsigned agent = 007;

This snippet would be equivalent to (e.g.):

int percent = 0156;
unsigned flags = 128;
unsigned agent = 0x7;

So programmers can choose the best of these options when including numbers in their code.

Python adopted this same C syntax, but has recently gone on to extend and modify it. Some Python 2.6 numbers:

Python 2.6
>>> 0x80, 110, 007, 0O7, 0o7, 0b10000000
(128, 110, 7, 7, 7, 128)

I’m pleased to see support for binary literals, which are useful for (e.g.) bitmasks. I’ve never really seen the point of octals; nonetheless, they’ve been enhanced for Python 3. Python 2.6 backports the new improved octal literal syntax whilst retaining support for classic C-style octals. Python 3 drops C-style octals.

Python 3.1
>>> 007
  File "<stdin>", line 1
    007
      ^
SyntaxError: invalid token
>>> 0O7
7

Now consider the compiler/interpreter writer’s problem. Clearly it must be possible to take a string representing an integer literal and work out what number it represents. At a first glance, the int() builtin isn’t quite smart enough to do the job without us supplying an explicit base for the conversion:

>>> int('0xff')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: invalid literal for int() with base 10: '0xff'
>>> int('0xff', 16)
255

We might consider reading any prefix from the literal and dispatching the string to an appropriate handler. Something like this:

def integer_literal_value(s):
    if s.startswith('0x'):
        return int(s, 16)
    if s.startswith('0b'):
        return int(s, 2)
    ...

Yuck! Surely there’s an easier way to do something this fundamental? Well, there’s always eval(), which turns the interpreter on itself.

>>> def integer_literal_value(s): return eval(s)
... 
>>> v = integer_literal_value
>>> v('0x80'), v('0o7'), v('0b1010101'), v('42')
(128, 7, 85, 42)

We should have looked more carefully at the int() documentation:

int([x[, radix]]) … The radix parameter gives the base for the conversion (which is 10 by default) and may be any integer in the range [2, 36], or zero. If radix is zero, the proper radix is determined based on the contents of string; the interpretation is the same as for integer literals.

Perfect!

>>> from functools import partial
>>> integer_literal_value = partial(int, base=0)
>>> v = integer_literal_value
>>> v('0x80'), v('0o7'), v('0b1010101'), v('42')
(128, 7, 85, 42)

(Notice, by the way, that radix is used in the online documentation but the actual argument name is base. I’ll confess that before I wrote this note I hadn’t spotted this use of zero as a special value for string→integer conversions even though it’s been available since Python 2.1)

C++ also offers a way to convert integer literals into the numbers they represent, but it’s not very well known. As is usual for format conversions, we use streams — stringstreams typically, but here I show an example using standard input and output. The trick is to disable any numeric formatting of the input stream.

integer_literal_value.cpp

#include <iostream>

int main()
{
    int x;
    std::cin.unsetf(std::ios::basefield);
    while (std::cin >> x)
    {
        std::cout << x << '\n';
    }
    return std::cin.eof() ? 0 : 1;
}

It works by magic.

$ g++ integer_literal_value.cpp -o integer_literal_value
$ echo 007 0x80 110 | ./integer_literal_value
7
128
110

Inner, Outer, Shake it all abouter

tag@wordaligned.org (Thomas Guest) — 2009-07-29

C++ programmers enjoy three levels of access control: private, protected and public. Some programmers use protected instead of private just in case someone might want to derive from their class some day. Others keep everything as private as possible, hiding nested classes in anonymous namespaces; these inner classes never seem to work quite the way you’d want, but if you get tangled up a friend can cut through the knots!

Python is less sophisticated. Prefix class members with a double underscore and their names are disguised to the world outside. Prefix module members with a single underscore to indicate they won’t be exported from that module. Many Python programmers use single underscore prefix in classes too (no mangling but better looking).

Once you’ve used Python for a while you may well question the benefits of the C++ model. Recently a C++ question came up on the accu-general mailing list. It involved nested classes, operator<<() and code which refused to compile. You’ll have to trawl through the list archives if you want the exact question: I didn’t give it much attention since it seemed an example of the kind of struggle with the language which causes me to throw in the towel. I would like to quote from one of the answers though.

Surely your issue is that f() is a friend of Inner only. f() is not a friend of Outer. Inner is private to Outer. Therefore in the global scope, outside Outer, f() cannot access Inner via Outer::Inner, as that is private.

Wow, some brain twister!

Time to get back to basics.

Encapsulation is about allocating responsibility and easing utility rather than protecting data, which is a side effect. — @KevlinHenney

My thanks to Jason McGuiness for allowing me to quote from his expert answer to a tricky C++ question. The photo shows Cliff Stoll holding the world’s largest glass klein bottle, which was produced by the company he owns, operates and mismanages, Acme Klein Bottles. Klein bottles get a mention here because they don’t have an outside or an inside, they just have a side. You can solve every computing problem with an extra dimension, except the problem of too many dimensions.

Blackmail made easy using Python counters

tag@wordaligned.org (Thomas Guest) — 2009-07-27

The Obsessive Blackmailer

An obsessive blackmailer writes anonymous messages by by cut-and-pasting letters from newspapers. Being obsessive, the blackmailer only writes messages which can be composed entirely from a single newspaper.

Devise an algorithm which determines whether a given message can be written using a given newspaper.

Modeling the Problem

This is a nice little problem but I’m about to spoil it since I’m using it here as a study in Python’s evolution. So if you’d like to try it yourself, look away now.

We can represent both inputs to the algorithm as sequences of characters: a message string, length M, and a newspaper string, length N. We could process the message string one character at a time, at each step scanning through the newspaper and noting the first occurrence of that character we haven’t used before; but this is inefficient since we potentially read the whole paper M times.

It’s better to think of this problem in terms of multisets, sometimes known as bags. A multiset is a set which can have repeated elements. Our blackmailer can proceed if the multiset of letters used in the message is contained entirely within the multiset of letters used in the newspaper.

The evolution of multisets in Python

A dictionary provides a compact and efficient way to represent a multiset in Python: each dictionary key represents an item in the multiset, and the value associated with that key is the number of times the key appears in the multiset. Python dictionaries are implemented as hashed arrays, meaning that member insertion and access take constant time, on average.

It’s not hard to create such a multiset from a sequence but it’s interesting to see how advances in the Python language have simplified the code.

The complete documentation for Python 1.4, released in 1996, is still available on the Python website. In version 1.4 you could write:

def multiset_14(xs):
    multiset = {}
    for x in xs:
        if multiset.has_key(x):
            multiset[x] = multiset[x] + 1
        else:
            multiset[x] = 1
    return multiset

This code works unchanged in the current Python release, 2.6 (though note dict.has_key() doesn’t exist in Python 3.*). Alternatively, you might catch the KeyError raised when trying to access the dict with an invalid key:

def multiset_14(xs):
    multiset = {}        
    for x in xs:
        try:
            multiset[x] = multiset[x] + 1
        except KeyError:
            multiset[x] = 1
    return multiset

Python 1.5 introduces an exception-free dictionary access method, dict.get(), which returns a user supplied default (defaulting to None) for missing keys.

def multiset_15(xs):
    multiset = {}        
    for x in xs:
        multiset[x] = multiset.get(x, 0) + 1
    return multiset

It’s certainly shorter, a little cleaner maybe, but perhaps it takes more effort for readers to see what exactly is going on.

At Python 2.2, x in multiset improves on the equivalent multiset.has_key(x) and we can use augmented arithmetic operators (+=, -=, *=, /=, %=, **=, <<=, >>=, &=, =, |=), allowing:

def multiset_22(xs):
    multiset = {}
    for x in xs:
        if x in multiset:
            multiset[x] += 1
        else:
            multiset[x] = 1
    return multiset

I think I prefer the dict.get() version, though.

The collections module makes its first appearance in Python 2.4 offering a deque and a promise of more high performance container types to come. Python 2.5 makes good on this promise, adding defaultdict to the module. A defaultdict is a specialised dictionary which calls a client supplied factory function for missing keys. Setting this factory function to int turns the defaultdict into a multiset. No need for dict.get() any more.

from collections import defaultdict

def multiset_25(xs):
    multiset = defaultdict(int)
    for x in xs:
        multiset[x] += 1
    return multiset

Wait, there’s more!

The final improvement is available in Python 3.1 right now (or in Python 2.7, coming soon), courtesy once again of the collections module. Collections.Counter is exactly what we’ve been waiting for.

from collections import Counter

def multiset_31(xs):
    return Counter(xs)

Back to Blackmail

So our blackmailer should first generate a multiset representation of the letters in the message. Then it’s a matter of iterating through the newspaper and reducing the multiset each time a letter matches up. We keep a tally of the number of letters we still need to match, and stop when this tally is zero or when we get to the end of the newspaper. Here’s a sketch of an implementation.

def blackmailable(message, newspaper):
    """Return True if newspaper can be used to write the blackmail 
    message, False otherwise.
    """
    m = len(message)
    if m == 0:
        return True
    counts = multiset(message)
    for ch in newspaper:
        if counts[ch] > 0:
            counts[ch] -= 1
            m -= 1
            if m == 0:
                return True
    return False

This code assumes the multiset is represented as a Counter or a defaultdict, since it depends on counts[ch] returning 0 for any character not in the message. If we’d used a plain dict, we’d need to employ dict.get(ch, 0).

I’m not entirely happy with the code shown. It’s what I first came up with. Here’s an alternative, which I also find a bit clunky. I’d welcome any improvements. It’s also worth noting that the algorithm locates the matching characters in the newspaper, so we might want to cache some indices for later use.

def blackmailable(message, newspaper):
    """Return True if newspaper can be used to write the blackmail 
    message, False otherwise.
    """
    counts = multiset(message)
    m = len(message)
    n = len(newspaper)
    i = 0
    while m != 0 and i != n:
        ch = newspaper[i]
        if counts[ch] > 0:
            counts[ch] -= 1
            m -= 1
        i += 1
    return m == 0

We can avoid the ugly code by persuading the obssessive blackmailer to generate and maintain multiset representations of the entire newspaper library. Then blackmailable() can be implemented as multiset containment, something which the Counter class handles nicely using the subtraction operator. Note here that multiset subtraction never results in any negative counts, even though a Counter instance could itself have negative counts.

>>> from collections import Counter
>>> missing_letters = Counter(message) - Counter(newspaper)
>>> blackmailable = len(missing_letters) == 0

Alternatively:

>>> blackmailable = not missing_letters

Generic Code

Suppose the blackmailer prefers to compose a message from words, rather than letters? (For an example, see the threat to stay away from Grimpen Moor delivered to Sir Henry Baskerville discussed later in this article.) The code works as is — just pass in message and newspaper as word sequences, rather than character sequences. Anything we can hash can be counted.

End of Message

In the age of the interweb anonymous cowardice is far easier and blackmailers don’t need to resort to manual cut and paste techniques unless they’re after a retro threatening effect.

What’s more, a detective can figure out plenty from these messages: so when Sir Henry Baskerville receives a threatening letter during his stay at the Northumberland Hotel, he shows it promptly to Sherlock Holmes:

Across the middle of it a single sentence had been formed by the expedient of pasting printed words upon it. It ran: “As you value your life or your reason keep away from the moor.” The word “moor” only was printed in ink.

In a virtuso display of deductive reasoning, Holmes shows the author of the message was in a hurry, afraid of being interrupted, and working in a hotel room using nail-scissors. (He also deduces something else, which he does not reveal at the time.) Identifying the source of the words to be yesterday’s Times leader is elementary.

The detection of types is one of the most elementary branches of knowledge to the special expert in crime, though I confess that once when I was very young I confused the Leeds Mercury with the Western Morning News. But a Times leader is entirely distinctive, and these words could have been taken from nothing else.

— Sherlock Holmes, The Hound of the Baskervilles

Can anyone identify the newspaper I used to create the image at the start of this article?

My thanks to jay for a correction to the original version of this article.

Could OCR conquer the calligraphylion?

tag@wordaligned.org (Thomas Guest) — 2009-07-14

Optical character recognition (OCR) algorithms typically process an image in stages:

convert the image to monochrome
identify blocks of text
find lines of text within those blocks
separate out words, then characters
extract character outlines
match outlines to archetypes
match candidate words to dictionary

These algorithms can be tuned and trained, to particular fonts and dictionaries for example, and the later stages can feedback into earlier ones; but the strategy basically tackles the picture character by character. This form of OCR is a mature and successful technology. It works very effectively with, for example, a page from a Western newspaper; but as with all things language-related, varying cultural conventions can lead to complications. The fundamental assumption that the atoms of a text image are characters may no longer be true. Tesseract, the leading open source OCR engine, comes clean

Tesseract is unlikely to be able to handle connected scripts like Arabic. It will take some specialized algorithms to handle this case, and right now it doesn’t have them.

Mohammad S. M. Khorsheed’s Phd dissertation describes such algorithms, explaining the dimensions of the challenge in more detail:

Arabic scripts are inherently cursive: writing isolated characters in ‘block letters’ is an unacceptable and unused writing style. The letters are context sensitive. Certain character combinations form new ligature shapes which are often font dependent. Some ligatures involve vertical stacking of characters. Since not all characters connect, word boundary location becomes an interesting problem, as spacing may not only separate words but also certain characters within a word.

Here’s an illustration of Arabic characters taking on different forms, depending on position.

There are some commercially available specialised Arabic OCR packages but I haven’t been able to try them out. They don’t provide information about the algorithms they use.

Could OCR software ever conquer the calligraphylion?

This magical beast demonstrates OCR in reverse: an image which has been converted by hand into text.

This image of a lion originates from Lahore, Pakistan and is part of a rich tradition of zoomorphic calligraphy. This practice, developed in the sixteenth century, employs the flexibility and beauty of Arabic script to delineate living forms such as tigers, parrots, ostriches and cockerels. This is done without disobeying religious injunctions that prohibit their direct depiction.

— Tate Gallery, East West exhibition, 2006-2007

(More zoomorphic calligraphy.)

Undogfooding

tag@wordaligned.org (Thomas Guest) — 2009-07-08

David Jones perfectly captures the look and feel of Sir Tony Hoare’s presentation at Europython 2009

Tony Hoare is clearly old skool. His slides had the calm and aged patina of the OHP era, and I thought they were all the better for that. If you have a message, then that message can be conveyed without all the flash and shine that PowerPoint tempts you with (although, being a Microsoft man, of course his slides were in PowerPoint).

Note the parenthetical comment: Tony Hoare works for Microsoft and he uses Microsoft software, an activity developers refer to as “eating your own dogfood”. Also eating dogfood at Europython, Gregor Lingl employed his very own turtle to guide the audience through a nifty presentation belying the reptile’s slow-and-steady reputation. I’ve always enjoyed sketching code using the Python interpreter, and sketching pictures with a turtle feels very pythonic.

My first turtle sketch

Python 3.1
>>> from turtle import *
>>> shape('turtle')
>>> circle(100)
>>> fillcolour('red')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'fillcolour' is not defined
>>> fillcolor('red')
>>> begin_fill(); circle(100); end_fill()
>>> def grey(pc): c = pc/100; fillcolor(c, c, c)
... 
>>> clear()
>>> def doit(r): begin_fill(); grey(r); circle(r); end_fill()
... 
>>> for r in range(100): doit(r)
... 
^C^C
Traceback (most recent call last):
...
>>> clear()
>>> for r in range(100, 0, -5): doit(r)
...
>>> fillcolor('white')
>>> forward(150)

Gregor Lingl’s session at Europython wasn’t the only one delivered using software developed by the presenter. What would be the opposite of eating your own dogfood, I wondered? Abusing someone else’s software, perhaps.

After one too many bad presentations at a meeting in January 2000, I decided to see if I could do something about it. — Peter Norvig

I’m fairly sure Peter Norvig had no part in PowerPoint’s development. In a hilarious satire he skewers the popular presentation tool with its own Autocontent Wizard.

Back on the subject of overhead projectors, I saw one put to good use by another eminent old-skooler, Donald Knuth, at the recent Mathematics and Fiction workshop in Oxford. Asked by passport control at London Heathrow if he’d be visiting Oxford on a business trip or a pleasure trip, Knuth had answered: no, he’d come on a ego trip.

Knuth was in Oxford to talk to his fans about about Surreal Numbers, a book he wrote in just a couple of weeks in 1973 while taking a break from working on The Art of Computer Programming in a hotel in Oslo, and which may well be the only example of a mathematical theory first published in fictional form.

For the workshop Knuth had gone back to his files and found his working notes, the original hotel brochure, photos, hand-written reviews by Pólya and others, though he couldn’t locate the paper napkin on which John Horton Conway had sketched the axioms underpinning the number system a few months before^[1] — Knuth had copied this source material onto acetates which he then sorted and shuffled on the OHP according to the direction his reminiscences and questions from the audience took him.

Unlike Tony Hoare, Donald Knuth wasn’t making a formal presentation, but I was struck by some advantages offered by the OHP. For one, the process of getting slides displayed seemed foolproof — at Europython we had the usual catalogue of computer/screen interface glitches (unwanted dialog boxes popping up, batteries dying, screensavers kicking in, missing Mac display dongles, delays while rebooting Ubuntu, alignment issues). The OHP also facilitated a dynamic presentation style: Knuth accessed his slides at random, composing screens from more than one slide on the fly, and pointing to areas of interest directly using a finger. He didn’t modify his slides during the session by writing on them, but that would also have been possible.

In a supreme example of dogfood consumption, a couple of years after publishing Surreal Numbers Knuth took a rather longer break from TAOCP to work on TeX, a typesetting system whose results match the beauty of his writing.

… You get surreal numbers by playing games. I used to feel guilty in Cambridge that I spent all day playing games, while I was supposed to be doing mathematics. Then, when I discovered surreal numbers, I realized that playing games IS mathematics. — John Horton Conway

[1] In fact, he’d lost the napkin before his stay in the hotel in Oslo, which explains the difference between the axioms used in Surreal Numbers and the ones originally suggested by John Horton Conway.

Tony Hoare’s vision, car crashes, and Alan Turing

tag@wordaligned.org (Thomas Guest) — 2009-07-02

Yesterday afternoon, at Europython 2009, David Jones addressed the subject “What sucks about Python?” Despite this provocative title, David Jones had lots of good things to say about Python, and the two topics which really roused the audience (the global interpreter lock and the over-crowded Python packaging space) had more to do with the Python-the-platform than Python-the-language. He also failed to mention the thing I miss most when working with Python: via Peter Norvig’s Python IAQ, quoting Bjarne Stroustrup:

“If I were to design a language from scratch, I would follow the Algol68 path and make every statement and declaration an expression that yields a value.”

Of course what really matters to an engineer is Python-the-platform rather than Python-the-language. Python famously comes with batteries included, and, stretching the metaphor, it also excels at integrating with the other batteries used in modern software applications. The packaging confusion is a side-effect of Python-the-platform’s success. More on over-stretched batteries later …

The day had started with Bruce Eckel’s keynote on Software Archeology. Bruce Eckel is a relaxed and engaging speaker but I found his presentation rather flimsy. Its substance could (and did!) fit on to a couple of David Jones’ slides and the remainder dwelt a little too long on Bruce Eckel, his Java and C++ books, blogs, and www.mindviewinc.com.

During the rest of the day, I had a choice of 4 or 5 different presentations at any one time, generally on the subject of Python modules or frameworks. The common theme I took away is that people turn to Python to get things done, and they’re reluctant to turn back. As the afternoon drew on everyone regathered in the Adrian Boult Hall to listen to a brilliant series of lightning talks which developed on this same theme. We also heard a wonderful short story about the best way to wreck cars and software systems.

On the subject of car crashes, it seemed a shame to stem the flow of these talks and keep Sir Tony Hoare waiting in the wings in order to pull Guido van Rossum on stage, especially since Guido wasn’t even at the conference. Nonetheless, the the benevolent dictator for life dutifully skyped in, and his face beamed up on the 12m² screen. We could see and hear him. He couldn’t hear us. The connection fizzed and chirped until all protocol broke down. Eventually the skype laptop popped up a message warning its batteries were running low, then promptly and mercifully shut down, ending the experiment.

On walked Sir Tony Hoare, the programmer, software engineer, computer scientist and academic who now works for Microsoft research. His thoughtful keynote analysed the differences between science and engineering, and considered their interplay in the field of software development. His presentation challenged my way of thinking about software specification and program correctness, and the message on his closing slide was both shaming and inspirational:

One Day

Software will be the most reliable component of every product which contains it

Software engineering will be the most dependable of all engineering professions

Because of the successful interplay of research
into the science of programming

and the engineering of software

— Tony Hoare, The Science of Computing and the Engineering of Software, 2009

Sir Tony Hoare is a Turing Award winner. I think he said he’d been working with computers for 50 years — it may well have been longer. Certainly he remembered when ALGOL was the hot new language, poised to supplant FORTRAN. The conference provided an opportunity to go further back, to Turing himself, and to the first ever programmable digital computer. In another memorable keynote session after lunch Simon Greenish and Dr Sue Black spoke passionately about Bletchley Park, the expansive Milton Keynes mansion which was converted into a code-breaking factory during the second World War and which is now a museum struggling to make ends meet. At the end of the presentation they unveiled a real Enigma machine to a huge round of applause.

Colossus, the world’s first ever programmable digital computer, has been painstakingly rebuilt at Bletchley Park. Although it won’t be running Python, it will resume its orginal task of cracking the Lorenz cipher.

There can be no such return for Alan Turing, who would have been 97 last week, but who tragically took his own life 55 years ago. He was a brilliant mathematician and scientist, famously eccentric, yet his papers on machine intelligence and computability remain highly accessible, forming the way we now think about computers. Over 11 thousand people worked at Bletchley Park during the war, and Alan Turing helped direct the decryption effort, a huge task which succeeded in shortening the war by two years and saving an estimated 22 million lives. In 2007 a statue of Alan Turing was erected at Bletchley Park. Dr Sue Black showed us a photo of his coffee mug which remains where he kept it, chained to a radiator.

Partitioning with Python

tag@wordaligned.org (Thomas Guest) — 2009-06-17

Sums and Splits

On the subject of hunting for eodermdromes, here are a couple of semi-related partitioning problems.

for a positive integer, N, find the positive integer sequences which sum to N
for a sequence, S, find the distinct partitions of that sequence

As an example of the first, the 16 distinct integer sequences which sum to 5 are:

5
4 + 1
3 + 1 + 1
3 + 2
2 + 1 + 2
2 + 1 + 1 + 1
2 + 2 + 1
2 + 3
1 + 1 + 3
1 + 1 + 2 + 1
1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 2 + 2
1 + 2 + 1 + 1
1 + 3 + 1
1 + 4

and of the second, the 8 distinct ways of partitioning the sequence ABCD are:

ABCD
A BCD
AB CD
ABC D
A B CD
A BC D
AB C D
A B C D

Note that I’ve counted 2 + 1 + 2, 2 + 2 + 1, and 1 + 2 + 2 as distinct sums totalling 5. That happens to be the formulation of the problem which interested me.

Context

Before discussing a solution to these problems, some context. Recall that an eodermdrome is a sequence which forms an Eulerian circuit through the fully connected graph whose vertices are the set of its elements. Put more simply: when you trace through the letters you get the figure shown, with no edge covered twice. Examples include:

EODERMDROME

ENHANCE ACHE

TAX DEAD TEXT

Eodermdromes turn out to be surprisingly rare. Writing a computer program to find them is a nice exercise in searching and text processing. Clearly, we should start with a collection of words. Then we can generate combinations of words from this collection and filter out the eodermdromes.

(filter eodermdrome? (combinations words))

A large set of words (note: “set” not “collection”, we don’t need duplicates) gives the best chance of success. I started with a file containing more than 35 thousand distinct words. This gives over a billion possible word pairs, and when we consider word triples and quartets the numbers get silly even for a modern computer.

As is so often the case in computing, we have a tension between opposing concerns. We’d like code which separates the task of generating candidates and the task of testing these candidates for eodermdromicity, but in order to run this code in a timely manner we need some of the eodermdrome testing to leak into the candidate generation. For example, we could preprocess the word set removing words which contain double Ls (all, ball, call, ill, Bill, kill …) since these can never appear in an eodermdrome. And we could similarly remove words which end ETE (delete, Pete, effete). As I hope you can see, it’s easy to end up with finickity code and co-dependent functions.

I chose a simple but effective strategy to reduce the search space to something manageable, based on word length. First, then, I loaded my word set into a Python dict collecting lists of words keyed by their length.

>>> from collections import defaultdict
>>> words = defaultdict(list)
>>> for word in open('word-set.txt').read().split():
...     words[len(word)].append(word)

Given this dict, picking out single word eodermdromes is easy.

>>> list(filter(is_eodermdrome, words[11]))
['eodermdrome']

How about eodermdromes composed of a 6 letter word followed by a 5 letter word? We can form the cartesian product of the lists of 6 and 5 letter words and filter out the ones we want.

>>> from itertools import product
>>> eod_6_5 = filter(is_eodermdrome, product(words[6], words[5]))
>>> next(eod_6_5)
('earned', 'andre')
>>> next(eod_6_5)
('yearly', 'relay')

How about all eodermdromes of length 11?

>>> from itertools import chain.from_iterable as seq
>>> word_lens = sum_to_n(11)
>>> candidates = seq(product(*[words[i] for i in s]) for s in word_lens)
>>> eods = filter(is_eodermdrome, candidates)

Note here that I’m using Python 3.0, and that filter is therefore a lazy function. The interactive session shown above hasn’t actually started taking anything from these lazily-evaluated streams.

I certainly don’t claim this is the quickest way to search for eodermdromes. In fact, this little program took several hours to complete. But a back-of-an-envelope calculation showed it would complete in a few hours, and that was good enough.

Note also that we haven’t shown an implementation of sum_to_n() yet, which takes us back to the problems posed at the start of this article.

Sum to N

Finding the positive integer series which sum to a positive integer N is a job for itertools.combinations.

from itertools import combinations, chain

def sum_to_n(n):
    'Generate the series of +ve integer lists which sum to a +ve integer, n.'
    from operator import sub
    b, mid, e = [0], list(range(1, n)), [n]
    splits = (d for i in range(n) for d in combinations(mid, i)) 
    return (list(map(sub, chain(s, e), chain(b, s))) for s in splits)

The idea here is straightforward: there’s a 1-to-1 correspondence between the sums we want and ordered combinations drawn from the series 1, 2, … n-1. For example, if n is 11 one such combination would be:

(1, 5, 7, 10)

we can extend this by pushing 0 in front and n at the end

(0, 1, 5, 7, 10, 11)

This extended tuple can now be seen as partial sums of a series which sums to 11. Taking differences gives the series

(1-0, 5-1, 7-5, 10-7, 11-10)

which is

(1, 4, 2, 3, 1)

which does indeed sum to 11

1 + 4 + 2 + 3 + 1 = 11

The Python code shown uses a clever idea to implement this staggered differencing, an idea I cleverly stole from one of Raymond Hettinger’s brilliant Python recipes.

Partitioning a Sequence

Python Cookbook: Recipe 576795

from itertools import chain, combinations

def partition(iterable, chain=chain, map=map):
    s = iterable if hasattr(iterable, '__getslice__') else tuple(iterable)
    n = len(s)
    first, middle, last = [0], range(1, n), [n]
    getslice = s.__getslice__
    return [map(getslice, chain(first, div), chain(div, last))
            for i in range(n) for div in combinations(middle, i)]

This recipe shows sum-to-n and partitioning to be very similar problems. In fact, we could easily implement sum_to_n() on top of partition():

def sum_to_n(n):
    return ([len(t) for t in p] for p in partition(range(n)))

The posted recipe needs a minor overhaul to get it working with Python 3.0, which does away with __getslice__: getting a slice is simply what __getitem__ does when given a slice object. The 2to3 tool fails to convert the recipe, which must be recast as something like:

from itertools import chain, combinations

def sliceable(xs):
    '''Return a sliceable version of the iterable xs.'''
    try:
        xs[:0]
        return xs
    except TypeError:
        return tuple(xs)

def partition(iterable):
    s = sliceable(iterable)
    n = len(s)
    b, mid, e = [0], list(range(1, n)), [n]
    getslice = s.__getitem__
    splits = (d for i in range(n) for d in combinations(mid, i))
    return [[s[sl] for sl in map(slice, chain(b, d), chain(d, e))]
            for d in splits]

Sum to N, again

Here’s a variant implementation of sum_to_n(). The idea here is to fill N slots with a pattern of 0’s and 1’s. We then reduce this pattern to the lengths of runs of repeated elements, giving a series which sums to N. Itertools.product('01', repeat=n) generates all possible binary patterns of length N, which turns out to be twice as many as we want since (e.g.) 00001111100 and 11110000011 represent the same sum, 4 + 5 + 2; hence the n-1 repeat count and the call to chain in the code below^[1].

from itertools import groupby, chain, product

def ilen(it):
    return sum(1 for _ in it)

def sum_to_n(n):
    return ([ilen(gp) for _, gp in groupby(chain('1', O1))]
            for O1 in product('01', repeat=n-1))

Fun, but the version using combinations is better!

[1] My first thought was to use itertools.islice to limit the stream to the first 2^n-1 values, but I discovered islice has a surprising limitation.

>>> from itertools import islice, count
>>> islice(count(), (1<<31) - 1)
<itertools.islice object at 0x63a0c0>
>>> islice(count(), (1<<31))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: Stop argument for islice() must be a non-negative integer or None.

so reuse ours

Oulipo and the Eodermdrome challenge

tag@wordaligned.org (Thomas Guest) — 2009-06-05

SHOES ON HENS

SAMSON MOANS

DRAB RED BEAD

Oulipo

At the Mathematics and Fiction workshop held last weekend in Oxford I particularly enjoyed David Bellos’ wonderful talk about Oulipo, the world’s longest running literary movement. The Oulipo is a group of writers interested in exploring the application of mathematical structures, patterns and algorithms to writing.

As an example, poet and novelist Raymond Queneau unleashed the exponential power of combinatorics to write a small book of sonnets which he hadn’t finished reading himself!

Constraints

The sonnet is a highly constrained literary form: 14 lines, 10 syllables per line, and a well-defined rhyme pattern. More generally, the Oulipo discovered such mathematical constraints can generate interesting results. Constraints can also provide inspiration — tying things down helps give them shape. Consider two questions:

What are you doing?
What are you doing? (Limit your answer to 140 characters.)

The first sounds plain nosey; but the second has spawned a whole new form of publishing.

The day-in-a-life format is another famous literary constraint. Oulipo-inspired writer Richard Beard explains how he notched this constraint up a level, creating a novel in which the action is formally and tightly bound to a single day.

In “Damascus,” I only use nouns that appeared in The Times of Nov. 1 1993. How does this work? In one paragraph some children are racing to the sea and one of them wants to say — “Last to touch the water’s a donkey.” But there’s no “donkey” in the paper, so they end up saying, “Last to touch the water’s a walrus.” So you end up with some interesting and novel linguistic formulations. — Richard Beard

The Eodermdrome challenge

The simplest Oulipian structure David Bellos presented was the eodermdrome. The word “EODERMDROME” is itself an eodermdrome ^[1]: if you place the letters E, O, D, R, M at the vertices of a pentagon, as shown, when you trace the sequence E→O→D→E→R→M→D→R→O→M→E you end up where you started, covering each line in the resulting figure exactly once. Mathematically speaking, the sequence EODERMDROME forms an Eulerian circuit within the fully connected graph whose vertices are the set of its constituent characters. Eodermdromes make naturally pleasing sequences, perhaps suitable for domain names or memorable phone numbers.

In his talk David Bellos offered three more eodermdromes. The second is credited to Jacques Roubaud. You’ll notice that the elements in the third are words rather than characters: the pattern works at any scale, and a reader needn’t be aware of it to appreciate its beauty.

tears at rest
étoile, ortie
figs, lizards, snakes, heat, light, figs, snakes, light, lizards, heat, figs

Eodermdromes turn out to be surprisingly thin on the ground. I include three of my own discoveries ^[2] at the start of this article. Can you can find any better ones?

[1] The word for such words is “autological”, as opposed to “heterological”. But is “heterological” itself heterological?

[2] OK, so a computer did the hard work. It’s a nice programming exercise.

end code once

Run-length encoding in Python

tag@wordaligned.org (Thomas Guest) — 2009-06-01

Recently I discussed run-length encoding and DEFLATE compression. I never actually showed a Python implementation of a run-length encoder, so here’s one now.

import itertools as its

def ilen(it):
    '''Return the length of an iterable.
    
    >>> ilen(range(7))
    7
    '''
    return sum(1 for _ in it)

def runlength_enc(xs):
    '''Return a run-length encoded version of the stream, xs.
    
    The resulting stream consists of (count, x) pairs.
    
    >>> ys = runlength_enc('AAABBCCC')
    >>> next(ys)
    (3, 'A')
    >>> list(ys)
    [(2, 'B'), (3, 'C')]
    '''
    return ((ilen(gp), x) for x, gp in its.groupby(xs))

The decoder is equally simple. Itertools.repeat expands a (count, value) pair into an iterable which will generate count elements. Itertools.chain flattens these iterables into a single stream.

def runlength_dec(xs):
    '''Expand a run-length encoded stream.
    
    Each element of xs is a pair, (count, x).
    
    >>> ys = runlength_dec(((3, 'A'), (2, 'B')))
    >>> next(ys)
    'A'
    >>> ''.join(ys)
    'AABB'
    '''
    return its.chain.from_iterable(its.repeat(x, n) for n, x in xs)

If you haven’t seen itertools.chain.from_iterable() yet, it was introduced at Python 3.0/2.6. The important feature here is that it lazily works its way through a single iterable argument. If instead we’d written:

def runlength_dec(xs):
    ....
    return its.chain(*(its.repeat(x, n) for n, x in xs))

then our run-length decoder would need to consume all of xs before yielding results (which is why we must interrupt the interpreter’s execution below).

>>> xs = its.cycle((3, 'A'), (2, 'B'))
>>> runlength_dec(xs)
  C-c C-cTraceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 25, in runlength_dec
  File "<string>", line 25, in <genexpr>
KeyboardInterrupt

Named tuples for clarity

Streams of pairs (as shown above) are perfectly Pythonic. If we run-length encode a stream of numbers, clients will just have to read the manual and remember that item[0] is a repeat count and item[1] is a value.

If this seems fragile, a new-ish member of the collections module can give the pair more structure.

>>> from collections import namedtuple
>>> Run = namedtuple('Run', 'count value') 
>>> run1 = Run(count=10, value=2)
>>> run2 = Run(value=2, count=10)
>>> run1
Run(count=10, value=2)
>>> run2
Run(count=10, value=2)
>>> run1.count
10
>>> run1[0]
10

Here’s how we’d change runlength_enc() to use the new type.

def runlength_enc(xs):
    '''Return a run-length encoded version of the stream, xs.
    
    >>> ys = runlength_enc('AAABBCCC')
    >>> next(ys)
    Run(count=3, value='A')
    >>> list(ys)
    [Run(count=2, value='B'), Run(count=3, value='C')]
    '''
    return (Run(ilen(gp), x) for x, gp in its.groupby(xs))

DEFLATE: run-length encoding, but better

tag@wordaligned.org (Thomas Guest) — 2009-05-21

Run-length encoding

Run-length encoding is a simple compression scheme in which runs of equal values are represented by the value and a repeat count. For example, a supermarket cashier might process this line of shopping

4 bananas
3 apples
2 bananas
1 pineapple
3 apples

Unix packs in its very own run length encoder, uniq -c. It works just fine — so long as the values you want to encode are newline separated byte strings, that is.

Let’s use a sequence of coin tosses as an example stream. $RANDOM generates random numbers. We use the least significant bit of these numbers as an index into an array containing the values heads, tails.

$ HT=(heads tails)
$ toss() { echo ${HT[$RANDOM&1]}; }
$ toss; toss; toss
heads
tails
tails
$ tosses() { while [ 1 ]; do toss; done; }
$ tosses | head
tails
tails
tails
heads
tails
heads
heads
heads
tails
tails

Passing a fresh sample from this same stream through our run-length encoder we get:

$ tosses | uniq -c | head
   2 heads
   1 tails
   1 heads
   1 tails
   1 heads
   6 tails
   3 heads
   1 tails
   4 heads
   1 tails

An awk script can be used as a run-length decoder. (There must be a neater way, using sed maybe?)

$ runlendec() { awk '{ while ($1--) print $2 }'; }
$ tosses | head | tee orig.log | uniq -c | runlendec | tee encdec.log
heads
tails
heads
tails
heads
heads
tails
tails
heads
heads
$ diff orig.log encdec.log

Here, we toss a coin 10 times teeing the original sequence to a file. The next two links in the pipeline compress and decompress the sequence, teeing the results to another file. Finally, as a sanity check, we confirm the round trip results are the same.

Run-length encoding in Python

This Unix run-length codec is fun, but of limited practical use. One good feature, though, is the way it operates on streams of data (including infinite streams), leaving clients free to decide how best to slice and buffer these streams.

Python has a fine library of high-level stream transformation tools from which we can build a generic and flexible run-length codec in just a few lines. Since I want to progress from run-length coding to something more advanced, I’ll leave discussing how to implement this codec for now, but if you’d like to write your own version, here’s a description suitable for doctesting.

Import the run-length codec functions and compress a short string.
>>> from runlength import compress, decompress
>>> comp = compress('AABBBACC')

The returned compressor is a stream (an iterable).
>>> next(comp)
(2, 'A')

Pull the rest of the stream into memory.
>>> rest = list(comp)
>>> rest
[(3, 'B'), (1, 'A'), (2, 'C')]

Simple decompress example.
>>> concat = ''.join
>>> concat(decompress(rest))
'BBBACC'

Compress, decompress also work with infinite streams, like the 
a2b3 stream, which repeatedly cycles two pairs. 
>>> from itertools import cycle, islice
>>> a2b3 = cycle([(2, 'a'), (3, 'b')])
>>> dec = decompress(a2b3)

Pull 8 values from the decompressed stream.
>>> concat(islice(dec, 8))
'aabbbaab'

Now compress the decompressed stream, and explore a few items.
>>> comp = compress(dec)
>>> next(comp)
(2, 'b')
>>> list(islice(comp, 2))
[(2, 'a'), (3, 'b')]

DEFLATE

The Wikipedia page on run-length encoding identifies monochrome images as good candidates for run-length compression. The white and black pixels typically group into long runs. Indeed, any simple image using a limited palette should reduce well using this compression scheme.

The chessboard above is 256×256 pixels, each square being 32×32 pixels. We could run-length encode this 64K pixel image as 256×8 = 2K runs of 32 pixels, a decent saving. (Actually, we should do slightly better, noting that there are runs of length 64 at the chessboard rank boundaries, but you get the idea.)

(32,W)(32,B)(32,W)(32,B)(32,W)(32,B)(32,W)(32,B),
(32,W)(32,B)(32,W)(32,B)(32,W)(32,B)(32,W)(32,B),
....
(32,B)(32,W)(32,B)(32,W)(32,B)(32,W)(32,B)(32,W)

Like a paletted image, a block of text — the web page you’re reading now, for example — employs a limited alphabet. Although the characters in this text don’t usually group into long runs there’s plenty of repetition, especially in the raw HTML: all the occurrences of <div>, <span> and class used for CSS styling, for example. The DEFLATE compression algorithm uses a clever twist on run-length encoding to remove this redundancy:

The compressed data consists of a series of elements of two types: literal bytes (of strings that have not been detected as duplicated within the previous 32K input bytes), and pointers to duplicated strings, where a pointer is represented as a pair <length, backward distance>. (RFC-1951)

(In addition, a multiple-level dynamic Huffman encoding scheme reduces the space needed for the strings, distances and lengths themselves.)

There’s more to these pointer elements than first appears: the length can exceed the backward distance. Thus the sequence:

heads
heads
heads
heads
heads

can be deflated as the literal type heads\n followed by the pointer type <24, 6>.

If you’ve spotted the potential for recursion, good! The inflating stream can reference itself, which can reference itself, which can … Confusing?

Zipping pixels

PNG images use DEFLATE compression (as implemented by zlib) to save on pixel storage space. Here’s a binary view of the raw data in the chessboard graphic shown above, all 137 bytes of it. The 64K pixels themselves compress into a 88 byte IDAT chunk, of which the final 8 bytes are a checksum and (I think?) some padding. Maybe the image could be squeezed harder, but I’m impressed!

8950 4e47 0d0a 1a0a 0000 000d 4948 4452  .PNG........IHDR
0000 0100 0000 0100 0100 0000 0074 0995  .............t..
cb00 0000 5049 4441 5468 81ed ceb1 0d00  ....PIDATh......
200c 0341 f65f 1a58 803a 2f74 6e52 e424   ..A._.X.:/tnR.$
7bed 9b75 f3ba cf07 0000 df83 ca0e 0000  {..u............
7a60 ba1f 0080 2ea8 ec00 00a0 07a6 fb01  z`..............
00e8 82ca 0e00 007a 60ba 1f00 802e a8ec  .......z`.......
0000 2007 0e8a 69f0 e2b9 9471 c700 0000  .. ...i....q....
0049 454e 44ae 4260 82                   .IEND.B`.

Here’s a trace of how zlib inflates the compressed pixels in this IDAT chunk. (Source code available via anonymous SVN at http://wordaligned.org/svn/etc/zlib_trace.)

inflate: allocated
inflate: reset
inflate:   zlib header ok
inflate:     dynamic codes block (last)
inflate:       table sizes ok
inflate:       code lengths ok
inflate:       codes ok
inflate:         literal 0x00
inflate:         literal 0xff
inflate:         length 3
inflate:         distance 1
inflate:         literal 0x00
inflate:         length 3
inflate:         distance 1
inflate:         length 24
inflate:         distance 8
inflate:         length 25
inflate:         distance 25
inflate:         length 258
inflate:         distance 33
....

I’ve attempted to show the first few stages of the genesis of the uncompressed stream in the picture below. The way the stream recursively inflates itself is quite beautiful.

put 00
put ff
go back 1 (to ff), put 3
put 00
go back 1 (to 00), put 3
go back 8 (to 00 00 00 00 ff ff ff ff)
put 24

Two elements later, and the repeat length has grown to 258. In fact, the entire chessboard is generated from just 3 literal and 43 pointer elements.

(Not all graphics have such a regular pattern, of course, so we can’t always achieve such dramatic compression.)

Deflated HTML

Web servers can and do save on band-width by transferring gzip compressed HTML to gzip capable clients. (Gzip is a simple wrapper around DEFLATE.) Any PNG images transferred will also have their pixels DEFLATE compressed.

$ curl http://wordaligned.org --head --compress
HTTP/1.1 200 OK
Date: Sun, 17 May 2009 17:41:53 GMT
Server: lighttpd | Word Aligned
Content-Type: text/html; charset=UTF-8
....
Vary: Accept-Encoding
Content-Encoding: gzip
Content-Length: 20

The Word Aligned front page contains about 75Kb of HTML, which gzips to just 16Kb — a decent saving. Relevant lines from the lighttpd configuration file read:

lighttpd mod_compress

server.modules = (
    ....
    "mod_compress"
)
compress.cache-dir = basedir + "lighttpd/cache/compress/"
compress.filetype  = ("text/plain", "text/html", "text/css")

I uphold Gzip (built on zlib, which implements DEFLATE) as a hero of the web. As we’ve seen, it implements a powerful and elegant algorithm, but perhaps the best thing about it is that it’s free to use, a freedom worth fighting for. Check out this battle report from the FAQ.

What about patents?

gzip was developed as a replacement for compress because of the UNISYS and IBM patents covering the LZW algorithm used by compress.

I have probably spent more time studying data compression patents than actually implementing data compression algorithms. I maintain a list of several hundred patents on lossless data compression algorithms, and I made sure that gzip isn’t covered by any of them. In particular, the --fast option of gzip is not as fast it could, precisely to avoid a patented technique. — Jean-Loup Gailly, Gzip FAQ

Word Aligned

Bike charts by Google

When you comment on a comment

Power programming

Contents

Python, Surprise me!

A Simple Function

The Real Surprise

Parentheses Required(?)

Serious about Syntax

Won’t Get Fooled Again

Next permutation: When C++ gets it right

Contents

itertools.permutations(iterable, r=None)

Python on Ice

Contents

Steady on Subversion

My secret shame

Do it the same, but better!

Definitive commentary

Long live Subversion

Favicon

Code Rot

Contents

A useful octal escape sequence

Converting integer literals in C++ and Python

Inner, Outer, Shake it all abouter

Blackmail made easy using Python counters

Contents

Could OCR conquer the calligraphylion?

Undogfooding

Tony Hoare’s vision, car crashes, and Alan Turing

One Day

Partitioning with Python

Sums and Splits

Context

Sum to N

Partitioning a Sequence

Sum to N, again

Oulipo and the Eodermdrome challenge

Oulipo

Constraints

The Eodermdrome challenge

Run-length encoding in Python

Named tuples for clarity

DEFLATE: run-length encoding, but better

Run-length encoding

Run-length encoding in Python

DEFLATE

Zipping pixels

Deflated HTML

What about patents?

`itertools.permutations(iterable, r=None)`