Go! Steady. Ready?

2016-04-18, , Comments

I’m looking forward to talking about Go at the ACCU 2016 Conference this Friday. If you’d like to find out what connects an Easter egg with flying horses and the runner in the green vest, then come along. Expect live coding, concurrent functions and answers.

>>> import antigravity

muybridge-horse

Tyntesfield 10k 2014

8 Queens Puzzle++

2016-04-05, Comments

Yesterday I wrote about a Python solution to the 8 Queens puzzle.

n = 8
sqs = range(n)

Qs = (Q for Q in itertools.permutations(sqs)
      if n == len({Q[i]+i for i in sqs})
           == len({Q[i]-i for i in sqs}))

It’s possible to reproduce this strategy in C++:

The std::next_permutation algorithm stands alone in the C++ standard library. Used here, it pairs well with the similarly uncommon do ... while loop. The solution depends on the vector sqs starting off in sorted order, and by the end of the loop the vector will have been returned to this state.

8 Queens Puzzle

2016-04-04, Comments

♛♛♛♛♛♛♛♛

Here’s one of my favourite recipes, by Raymond Hettinger, lightly adapted for Python 3.

from itertools import permutations

n = width_of_chessboard = 8
sqs = range(n)

Qs = (Q for Q in permutations(sqs)
      if n == len({Q[i]+i for i in sqs})
           == len({Q[i]-i for i in sqs}))

We start by assigning sqs to the range 0 through 7.

>>> sqs = range(8)
>>> list(sqs)
[0, 1, 2, 3, 4, 5, 6, 7]

The range has 8 indices. If each index represents a column on a standard 8x8 chessboard and the value at that index represents a row on the same chessboard, then our range represents 8 positions on the board. Using the built-in enumerate function to generate these (index, value) pairs we see that sqs encodes the diagonal (0, 0) to (7, 7):

>>> list(enumerate(sqs))
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7)]

Next, permute the values — the rows.

>>> from itertools import permutations
>>> rooks = permutations(sqs)
>>> next(rooks)
(0, 1, 2, 3, 4, 5, 6, 7)
>>> next(rooks)
(0, 1, 2, 3, 4, 5, 7, 6)
>>> next(rooks)
(0, 1, 2, 3, 4, 6, 5, 7)
>>> list(rooks)[34567]
(6, 7, 0, 1, 3, 4, 5, 2)

Itertools.permutations generates values lazily. The snippet above shows the first two results, then skips forward 34568 places. Permutations(sqs) generates all possible arrangements of 8 pieces on a chessboard such that each row has exactly one piece on it and so does each column. That is, it generates all possible ways of placing 8 rooks on a chessboard so that no pair attacks each other.

In the final program, we filter these rook positions to generate solutions to the more challenging — and more interesting — eight Queens puzzle.

Consider our starting point, the diagonal (0, 0) to (7, 7)

>>> diagonal = range(8)
>>> {r-c for c,r in enumerate(diagonal)}
{0}
>>> {r+c for c,r in enumerate(diagonal)}
{0, 2, 4, 6, 8, 10, 12, 14}

Here, a set comprehension collects the distinct values taken by the difference between the row and column along this diagonal, which in this case gives {0}. That is, if we placed 8 bishops along this ↗ diagonal they would all attack each other along this diagonal. The sum of the row and column takes 8 distinct values, however, meaning no pair attacks along a ↖ diagonal.

Comparison operators chain in Python, so the expression:

n == len({Q[i]+i for i in sqs}) == len({Q[i]-i for i in sqs})

is True if both sets have 8 elements, that is, if the squares in Q are on distinct ↖ and ↗ diagonals; or, equivalently no pair of bishops placed on the squares in Q would attack each other. Since we already know Q positions 8 rooks so that no pair attacks each other, and a chess Queen combines the moves of a rook and a bishop, we can see that Qs generates every possible way of placing 8 Queens on a chessboard so that no pair attacks each other: which is to say, we’ve solved the 8 Queens puzzle.

Qs = (Q for Q in permutations(sqs)
      if n == len({Q[i]+i for i in sqs})
           == len({Q[i]-i for i in sqs}))

This is beautiful code and there’s one final twist.

Qs is a generator expression primed to permute squares into neighbourly rooks filtered by amicable bishops yielding unthreatening Queens. Until asked, however, it does nothing.

♕♕♕♕♕♕♕♕

Easy as Py

2016-03-23, , Comments

What makes Python Simple?

I consider Python a simple language. Here’s why.

Easy to Read

I can read and understand Python code (unless it’s wilfully perverse). Syntactic whitespace and the associated removal of punctuation results in a regular, open layout. The combination of built in containers, extensive standard libraries and high level constructs allow for clear, compact code: code which fits in your head.

Easy to Write

I can write Python code which is free of syntax errors and which does what I want. Of course it helps that I’ve been actively using the language for 15 years, but I’ve been using C++ for longer and still make mistakes with it: ask me to declare a pointer to a member function, for example, or to knock up a variadic template function, and I’ll need a moment or two.

Transparent

I also consider C a simple language. C offers a transparent abstraction of a register machine, with a stack, a heap, and addressable memory. If you can imagine the operation of such a machine, you can figure out C. Python is less transparent but reveals its workings if pressed. Dicts form a part of the language seen by users, and under the hood they provide the dynamic context which supports a running program. The read-eval-print loop makes it easy to poke and reshape your program. You can disassemble code to see what the virtual machine sees.

Consistent improvement

The language has got better since I first started using it. It has also got bigger, and this growth would, at first, seem at odds with simplicity. However, consider — as an example — the point when list comprehensions were introduced. Language support for building a list from an iterable results in compact declarative code. Simple code. What’s more, the square brackets which now delimit list comprehensions are the same square brackets that were previously used to delimit lists. The syntax may have been new but it didn’t surprise. Now consider the introduction of set and dict comprehensions, which follow logically and naturally from list comprehensions, almost as if they were discovered rather than invented.

There are many other examples where additions to the language have unified and simplified.

Vision

I’m not a Python insider and cannot comment on the exact balance of benevolence and dictatorship which goes into the language enhancement process. I would say Python doesn’t suffer from being designed by a committee. It sticks to its strengths and its direction, to its vision.

Sausages, sausages, sausages - slice, slice, slice

2016-03-21, Comments

A friend asked for help reaching the next level of a puzzle game. The test which stalled her involves machine placement in a sausage factory.

… each sausage was branded with a letter for quality control purposes, thus: ypbtkizfgxptclcoirdsuhjwulqkoszrabfc

The string was then drawn through seven machines which rearranged the sausages in flavour enhancing ways.

Machine A: The Reversifier

Reverses the order of the sausages, so they get tastier as you go along.

Machine G: Secondhalffirstifier

move the second half of the string to the beginning, as the earlier sausages are too spicy to eat early in the morning.

He attached these machines in a certain sequence, though one of them was out for repair so only six were used. He then fed a string of sausages through and was surprised to discover the string that came out at the other end said lickyourlips. What order were the machines in?

It’s nicely phrased, but what’s really wanted is the sequence of simple transformations that takes input “ypbtkizfgxptclcoirdsuhjwulqkoszrabfc” and produces output “lickyourlips”.

It’s no doubt possible to work backwards and figure out a solution using no more than logic, pencil and paper. For example, only two of the machines change the length of the string, and — looking at the before and after lengths — these must both be used. It’s rather easier to write a short program to find a solution.

First we must simulate the seven sausage machines, A-G, which perform the following sequence operations.

  1. reverse the order of a sequence
  2. remove every other element of a sequence
  3. remove every third element of a sequence
  4. pairwise reverse elements of a sequence
  5. move even numbered elements to the front of a sequence
  6. move the last element of a sequence to the front
  7. swap the front and back half of a sequence

None of these is difficult, especially in a high-level language which builds in support for sequence operations. What I found noteworthy is that a solution can be found without any loops or if statements. What’s more, every operation can handled using nothing more than slice operations.

Here’s my solution. The machines consist of slice operations, helped by a couple of conditional expressions and recursive calls. The solution can then be brute-forced: there are only 5040 ways of permuting 6 out of 7 machines.

I’ve used reduce to apply a chain of functions to a string of sausages — an explicit loop might be clearer, but I want a loop-free solution. For this same reason I use recursion in the pairwise swapper and the element dropper. Generally in Python, recursion is a poor choice. In this case I know I’m starting with a string of just 36 elements which cannot get any longer; there’s no risk of exceeding the system recursion limit.

The sequence reversal s[::-1] is idiomatic but alarming to the uninitiated. Slices have [start:stop:stride] fields, any of which may be defaulted. Usually start and stop default to the start and end of the sequence, but in this case the negative stride reverses them.

To rotate the last element of a sequence to the front, prefer:

return s[-1:] + s[:-1]

to:

return [s[-1]] + s[:-1]

because the latter raises an IndexError for an empty sequence.

Slicing is a formidable tool for sequence manipulation, especially when combined with the option of using negative indices to count back from the end. Slices allow you to reverse, rotate and partition sequences, to pairwise swap elements, and to drop every nth element.

The miniature recipes presented here don’t even use slice assignment, which gives me an excuse to reproduce this elegant prime sieve function, which does.

Gofmt knows best

2016-03-07Comments

Everyone’s favourite

Gofmt’s style is no one’s favorite, yet gofmt is everyone’s favorite. — Rob Pike

Code formatting tools are nothing new but Go notches them up a level. Your Go installation comes with an automated formatter, gofmt, and this tool has been used to layout the entire code base. As a result, Go code looks uniform and familiar. The recommendation is to gofmt your own code, ideally on save and certainly before submitting for review.

(add-hook 'before-save-hook 'gofmt-before-save)

Formatting tools for other languages require configuration. You must instruct the tool about your preferences for spaces and braces. Gofmt is inflexible and this is a strength.

The language designers did Go a favour by supplying and promoting gofmt early on, before alternative style guides had been developed and adopted. There can be no more arguments about tabs vs spaces, for example. Code reviews must focus on content rather than layout.

There are also more subtle benefits. Certain kinds of manual layout are fragile: the insertion of space to vertically align assignment statements, for example. A code formatter gets it right every time.

Go knows best

As writers — and programmers are, fundamentally, writers — maybe we don’t want our work to look uniform or familiar. Maybe we prefer more control over what we produce. Maybe sometimes, we’d like to surprise or provoke.

Does the regularity gofmt imposes render our code bland, even boring?

I’ve heard this point extended to be a criticism of Go in general: that the language restricts what you can do because the language designers know best, and that it’s for your own good.

Well, if I’ve ever submitted extravagently formatted code for review, it’s been slapped back. Substantial programs are developed by teams who adopt idiom and share style rules for good reason. It’s how we work together. Imagine how much easier it would be if the third party code in your code base was also written to your preferred style. Go gives you that, so long as you prefer its native style.

Gofmt does not completely over-ride a programmer’s choices. Two programs which are semantically identical but laid out differently will probably still be laid out differently after a pass through gofmt.

When formatters fail

Formatting sometimes fails. Some examples follow.

Decluttered Java

Here’s some creatively formatted Java. Of course it’s a joke, and a funny one, but a language like Python, and indeed go, gets the last laugh. It is possible to get rid of braces and semicolons and your code will look better for it.

Tetrominoes

Here’s an equally witty but perfectly sensible use of non-standard layout.

Mathias is referring to some tetrominoes — tetris shapes — coded in elm by Joseph Collard.

-- A Tetromino is a list of Locations. By definition, a valid tetromino
-- should contain exactly 4 different locations
type Tetromino = [Location]

line : Tetromino
line = [(0,0), (1,0), (2,0), (3,0)]

square : Tetromino
square = [(0,0), (1,0),
          (0,1), (1,1)]

spiece : Tetromino
spiece = [       (1,0), (2,0),
          (0,1), (1,1)]

jpiece : Tetromino
jpiece = [       (1,0),
                 (1,1),
          (0,2), (1,2)]

For brevity, I’ve left out the Z and L pieces. I’ve also omitted comments from the original, which I would suggest are redundant since the code has been painstakingly formatted to indicate the shape of the pieces.

The same tetrominoes in hand-formatted Go read:

package tetris

type Tetronimo [4][2]int

var (
    Line   = Tetronimo   {{0, 0}, {1, 0}, {2, 0}, {3, 0}}
    
    Square = Tetronimo   {{0, 0}, {1, 0}, 
                          {0, 1}, {1, 1}}
    
    Spiece = Tetronimo   {        {1, 0}, {2, 0}, 
                          {0, 1}, {1, 1}}
    
    Jpiece = Tetronimo   {        {1, 0}, 
                                  {1, 1}, 
                          {0, 2}, {1, 2}}
)

Gofmt spoils them:

package tetris

type Tetronimo [4][2]int

var (
	Line = Tetronimo{{0, 0}, {1, 0}, {2, 0}, {3, 0}}
    
	Square = Tetronimo{{0, 0}, {1, 0},
		{0, 1}, {1, 1}}
    
	Spiece = Tetronimo{{1, 0}, {2, 0},
		{0, 1}, {1, 1}}
    
	Jpiece = Tetronimo{{1, 0},
		{1, 1},
		{0, 2}, {1, 2}}
)

Obfuscation

Here’s a tiny rectangular program submitted by Thaddaeus Frogley to the International Obfuscated C Code Contest in 2001. It’s meant to be hard to read and the compact layout helps, by hindering.

/*(c) 2001 Thad */
#include<string.h>
#include <stdio.h>
#define abc stdout
int main(int a,ch\
ar*b){char*c="??="
"??(??/??/??)??'{"
"??!??>??-";while(
!((a=fgetc(stdin))
==EOF))fputc((b=s\
trchr(c,a))?fputc(
fputc(077,abc),abc
),"=(/)'<!>""-"??(
b-c??):a, abc);??>

In the author’s own words:

I wanted to create a piece of code that could be considered to be “art” on multiple levels.

He’s succeeded. It’s impossible to translate this program into Go so I cannot gofmt it. If, instead, I try clang-format, the resulting code no longer compiles! Obfuscation has bamboozled the formatter.

/*(c) 2001 Thad */
#include <stdio.h>
#include <string.h>
#define abc stdout
int main(int a, ch\
ar *b) {
  char *c = "??="
            "??(??/??/??)??'{"
            "??!??>??-";
  while (!((a = fgetc(stdin)) == EOF))fputc((b=s\
trchr(c,a))?fputc(
fputc(077,abc),abc
),"=(/)'<!>""-"??(
b-c??):a, abc);
? ? >

Depth First Search

Finally, here’s a recursive depth first search from the boost graph library

template <class IncidenceGraph, class DFSVisitor, class ColorMap,
          class TerminatorFunc>
void depth_first_visit_impl
  (const IncidenceGraph& g,
   typename graph_traits<IncidenceGraph>::vertex_descriptor u,
   DFSVisitor& vis,  // pass-by-reference here, important!
   ColorMap color, TerminatorFunc func)
{
  typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
  typedef typename property_traits<ColorMap>::value_type ColorValue;
  typedef color_traits<ColorValue> Color;
  typename graph_traits<IncidenceGraph>::out_edge_iterator ei, ei_end;
  
  put(color, u, Color::gray());          vis.discover_vertex(u, g);
  
  if (!func(u, g))
    for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
      Vertex v = target(*ei, g);           vis.examine_edge(*ei, g);
      ColorValue v_color = get(color, v);
      if (v_color == Color::white()) {     vis.tree_edge(*ei, g);
      depth_first_visit_impl(g, v, vis, color, func);
      } else if (v_color == Color::gray()) vis.back_edge(*ei, g);
      else                                 vis.forward_or_cross_edge(*ei, g);
      call_finish_edge(vis, *ei, g);
    }
  put(color, u, Color::black());         vis.finish_vertex(u, g);
}

Clients of the function supply a visitor, vis, which is called back as vertices and edges are discovered and classified. These callbacks are carefully placed on the right hand side, visually distinguishing the core traversal from associated events. Note too the alignment, with edge events indented to the right of vertex events. Again, a code formatter tramples over this elegantly shaped code:

template <class IncidenceGraph, class DFSVisitor, class ColorMap,
          class TerminatorFunc>
void depth_first_visit_impl(
    const IncidenceGraph &g,
    typename graph_traits<IncidenceGraph>::vertex_descriptor u,
    DFSVisitor &vis, // pass-by-reference here, important!
    ColorMap color, TerminatorFunc func) {
  typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
  typedef typename property_traits<ColorMap>::value_type ColorValue;
  typedef color_traits<ColorValue> Color;
  typename graph_traits<IncidenceGraph>::out_edge_iterator ei, ei_end;
  
  put(color, u, Color::gray());
  vis.discover_vertex(u, g);
  
  if (!func(u, g))
    for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
      Vertex v = target(*ei, g);
      vis.examine_edge(*ei, g);
      ColorValue v_color = get(color, v);
      if (v_color == Color::white()) {
        vis.tree_edge(*ei, g);
        depth_first_visit_impl(g, v, vis, color, func);
      } else if (v_color == Color::gray())
        vis.back_edge(*ei, g);
      else
        vis.forward_or_cross_edge(*ei, g);
      call_finish_edge(vis, *ei, g);
    }
  put(color, u, Color::black());
  vis.finish_vertex(u, g);
}

Conclusion

Creative code formatting does have a place. Generally, though, gofmt gets it right: an automated tool can and should take care of formatting our code base, and the benefits are amplified if the tool is inflexible. With formatting solved we can focus our creative energy where it counts.

Sledgehammers vs Nut Crackers

2016-02-23, Comments

Awk

I get awk and can read awk programs but find the language of little use. Its focus is narrow and its syntax can be surprising. Python matches it at home and smashes it away. Nonetheless, a number of the advent of code puzzles fit the awk processing model — line based instructions, the interpretation of which builds state contributing to the final result — and I enjoyed writing awk solutions. There’s satisfaction in using a tool which is up to the job, no more and no less: in using a nutcracker, rather than a sledgehammer, to crack a nut.

Puzzle

For example, the puzzle set on day 6 consists of a list of instructions for switching and toggling a 1000 x 1000 grid of lights. The instructions read:

turn on 296,50 through 729,664
turn on 212,957 through 490,987
toggle 171,31 through 688,88
turn off 991,989 through 994,998
....

and the question is, after following these instructions, how many lights are lit?

Each instruction is a single line; the actions — turn on, turn off, toggle — can be matched by patterns; and to follow these actions requires no more than an array and arithmetic: awk fits nicely.

Code

Comments

Here, the BEGIN action sets the field separator FS to the regular expression [ ,] which picks out the textual and numeric fields from each instruction. Awk is highly dynamic: use a variable as a number and it becomes a number, in this case the coordinates of a lighting grid; and similarly, the fields “on”, “off” and “toggle” are matched and treated as strings.

The grid of lights appears to be represented as a two dimensional array, accessed lights[x,y] rather than lights[x][y]. In fact, the array — like all arrays in awk — is an associative container, which maps from strings — not numbers — to values. The key x,y becomes a string which joins the values of x and y with a separator defaulted to "\034".

Niggles

The escape character at the end of line 5 is needed to continue the long line. I’d prefer to use parentheses to wrap the expression over more than one line, as I would in Python, but this trick doesn’t seem to work. I was somewhat surprised there was no built in sum() function to count up the number of lights turned on by the END. It would have been cute to pass on(), off() and toggle() as functions into switch(), separating traversal from action, but I couldn’t find a way to do this in awk.

My awk script solved the puzzle in 45 seconds. A Python solution took 17 seconds. I didn’t try optimising either.

Don’t use a sledgehammer to crack a nut!

This advice, commonly given to programmers, demands explanation. If it’s intended to imply a sledgehammer is more likely to pulverise the nut than open it, then fine, that’s true — but the analogy fails in this case: a solution written in Python would have been equally correct.

Alternatively, if we mean you shouldn’t use a powerful language when a less powerful one would do, then the question becomes: why not? Python is a general purpose programming language. It can crack nuts, peel bananas, serve web pages and so much more. If you know Python why bother with Awk?

At the outset of this post I admitted I don’t generally bother with awk. Sometimes, though, I encounter the language and need to read and possibly adapt an existing script. So that’s one reason to bother. Another reason is that it’s elegant and compact. Studying its operation and motivation may help us compose and factor our own programs — programs far more substantial than the scripts presented here, and in which there will surely be places for mini-languages of our own.

Advent of Code

2016-02-22, , Comments

I enjoyed solving Eric Wastl’s excellent Advent of Code programming puzzles over Christmas last year. The puzzles are nicely themed and the site itself is a delight: lighting up an ascii art Christmas tree, row by row, became an addiction.

Advent of Code is a series of small programming puzzles for a variety of skill levels. They are self-contained and are just as appropriate for an expert who wants to stay sharp as they are for a beginner who is just learning to code.

First time through, I blasted through all the puzzles using Python, leaning on its standard containers, algorithms and text munging capabilities: “an expert who wants to stay sharp”, if you like. Now I’m tackling the problems again using languages and techniques I’m less comfortable with: “a beginner who is just learning to code”, which I like.

Second time round is fun, slow and instructive. I’m posting solutions on github.

ascii xmas tree

Code Reviews - the rules

2015-08-05, , , Comments

The rule is: no code gets checked in without a review.

It’s not always easy to get a reviewer to sign off a changelist. Does the code build? In all configurations and on all platforms? Do the tests pass? Are all new code paths covered? Does the commit message describe the change? Does the formatting match the style guide? Does the code match its surroundings? How about documentation, compiler warnings, license requirements?

Is the change really necessary? Could it have been realised more simply?

Certainly the reviewer’s task is easier if the task has been paired on. Small and self-contained changelists are more straightforward. Removing code, too, should be less contentious.

Depending on infrastructure, some checklist items can be automated. Ideally the changelist has already been though CI, for example, ticking the builds-cleanly and passes-its-tests boxes.

So far, so what? (So obvious!)

Here’s another rule, and one I’ve not seen written down before.

When I review code I might well consider how I would have made the change. That doesn’t mean I’ll insist the submitter does things my way. In the absence of automated formatters there will be more than one acceptable way to lay out the code. Sometimes there’s little reason to prefer an explicit loop over an algorithm + lambda combination, or vice-versa. Short names work for me but not for everyone. It’s hard to argue against test coverage, but is more always better?

In such cases I won’t try to impose my own style on the changelist. Instead, the question becomes: does the code match the standards we, as a team, have set? Or, do these changes merit a place in our codebase?

It’s a simple principle but not an obvious one. It helps me review fairly and also to learn from others on my team.

There is more than one way to do it!

Programming Paired and Shared

2015-05-27, , Comments

We pair program where I work. Two people, one desk. It can get intense.

Floor cleaner Emacs

Editor wars claim few casualties — until an emacs and a vim user are forced to share a keyboard and screen, that is. Anyone for notepad?

Sharing the typing isn’t why we pair. Where I work we also do code reviews. Whilst pair programming is encouraged, code reviews are mandated: code cannot be checked in until approved by a reviewer. That reviewer could be the person you paired with, and it soon becomes apparent that reviews conducted with a pair go more smoothly than ones where the reviewer is new to the task. It’s hard for someone to review a tricky changeset without the context of its development.

The context of its development turns out to be paramount for understanding a codebase, not just a changeset. Pair programming helps provide that context.

The term pairing serves better than pair programming. The former suggests sharing; the latter, typing. The benefits come from sharing all aspects of the work: decisions and responsibility; research, design, development; how to test; where to cut corners and where to go beyond the immediate requirement; when to take a break. Anyone for table football?

Edd and Bridget vs Bridget and Edd

Jokey Code?

2015-05-11, Comments

Choose Talks

I usually leave it as late as possible before deciding which sessions to attend at the ACCU conference. There’s ample time to study the schedule when you’re there and anyway, it’s subject to change.

This year I stuck with this policy with a couple of notable exceptions. First, there was my own talk, where I noted that computer programmers are writers who impose formal constraints on their texts, and who can learn from other writers who practice the same discipline. Second, there was Peter Hilton’s talk, “How to name things — the hardest problem in programming”, in which he argued more generally that programmers had much to learn from writers.

I had to see Peter Hilton’s talk and it did not disappoint. It engaged me at the time, in discussions afterwards, and it continues to make me think. I won’t post a full response here but I do want to consider one aspect: humour.

Tell Jokes

Peter Hilton argued we should pay attention to tips from the likes of George Orwell and Stephen King because their advice is better written and also because it’s funnier. Why does this humourous aspect matter? Well, perhaps we’re more likely to listen to someone who makes us laugh. Witty advice sounds less pompous.

It goes deeper than this, though. Another point from the talk:

Improve your general vocabulary. Read books, especially funny novels.

Why funny novels? At this point in the talk Peter Hilton disingenously suggested such books were easier to read. A point he made later goes deeper:

Tell jokes … Puns are important for naming, because they rely on double-meanings. Spotting double-meanings is the essential skill for avoiding ambiguous names.

Interesting! I agree that word play and word power are linked: but do you need to be a punster to avoid ambiguity? I’m not sure. In the words of Chris Oldwood:

I’ve been writing more functional code lately. I recently tried a few numerical recipes with currying functions, but all I got was a NaN.

all I got was a NaN

Laughable Code

Is there a place for humour in code? Rarely, I’d say. Code is read, re-read and then read again: most jokes become tired and then irritating under such scrutiny. Peter Hilton, though, described his amusement on discovering this function, which configures and starts Apache Camel:

/** Configure and start Apache Camel */
def mountCamel() {
    Logger.info("Starting Camel...")
    val context = new DefaultCamelContext()
    configuredRoutes foreach { route =>
        context.addRoutes(route)
    }
    context.start()
}

The obvious alternative, startCamel(), just isn’t funny enough, apparently. I’m glad the author resisted the temptation to call it humpCamel().

I’m reminded of a colleague with a fondness for franglais who would, for example, check in a graphics routine called do_le_render(). Mildly amusing first time round, maybe, but less so each time it got revisited to fix les bugs.

Ark of Desert - Camel

I don’t see many jokes in the code I read and I don’t think it’s because the authors lack a sense of humour. Just as good documentation should inform rather than entertain, good code should express complex ideas as plainly as possible: humour doesn’t get a look in.

There are exceptions. We’ve already seen the name “camel” used for something which isn’t a camel: libraries, products and projects can benefit from short, memorable and quirky names. In unit tests, too, code is less complex, which can leave space for quips and in-jokes. When an integer is expected it often turns out to be 42. Binary input data is laid out to form strange messages when viewed as hexadecimal. If some text — any old text — is needed, lorem ipsum would indicate a lack of imagination. Even so, well-chosen names and values from the domain under test would probably be more helpful when a failing test needs fixing.

Charming code

I’m down on jokes in code but I do think code can be a pleasure to read and that well written programs can delight. Whilst I agree with Peter Hilton’s recommendation to read widely and well, I was surprised he didn’t recommend reading code, and when I discussed this with him afterwards he asked, where is it? Where is it! That will be the subject of another article, but off the top of my head, freetype, ffmpeg, llvm, the Go and Python standard libraries. If you read through any of these you’ll enjoy their clarity and internal consistency — their style; and should you code against them, these same attributes show through their interfaces.

I haven’t found any jokes in the SQLite source but if you decide to integrate it in your application, when you check the license you’ll find, instead, a blessing. This may seem funny — unusual, certainly — but it’s actually quite serious.

May you do good and not evil
May you find forgiveness for yourself and forgive others
May you share freely, never taking more than you give.

We may not issue blessings with our own code but maybe we can find other ways to surprise and delight.

Election Manifesto - a timely activity for agile retrospectives

2015-04-29, Comments

Did I mention that I’ve become scrum master for my team? I have now. It’s a new thing for me (and for this blog) but I enjoy it, especially running the retrospective meetings. You have to keep these fresh and one way of doing this is to connect them with what’s going on in the world outside: the Oscars, the eclipse, the general election

With a week to go, my vote has been posted. So, here’s an activity I devised for a recent retrospective. We were focusing on infrastructure issues and trying to come with improvements. For this, it worked well.

Ask the team to split into three or four “political” parties. Each party must come up with a manifesto for change. What isn’t working? How would they improve things, given the chance? After 20 minutes of discussion, reconvene and ask the party leaders to present their manifesto to the electorate. Be prepared for tough questions and heckling!

Now it’s time to plan a brighter future. Summarise the key points of each manifesto and write them up on sticky notes, using different colours for the different parties. What do the parties agree on? Which promises are unrealistic and which can be delivered?

For more retrospective ideas, I recommend Retromat by Corinna Baldauf. You can find another suggestion of mine, #tweetmysprint, on the Retromat and I’ve submitted this one too.

Speaking at the ACCU Conference 2015

2015-04-28, , Comments

This time last week I was on my way to the ACCU 2015 conference in Bristol. The past couple of years I’ve been, but for one day only. This year, as a presenter of a full length (90 minute!) session I got to go to the whole thing.

Being a speaker made all the difference. Having the chance to attend plenty of sessions meant I was more relaxed about choosing which ones to pick — each slot during the day offered 5 options — and less upset if I thought, 10 minutes into a presentation, that I could have picked something else. Perhaps as a consequence of this, I was happy with all my choices. That said, I’d love the whole thing to run again so I could take a second route through the schedule.

I’d run a couple of practice versions of my talk at ACCU local groups in Bristol and then in Oxford, which meant I was comfortable with the material and convinced it would hold an audience’s interest.

Some things to consider for next year:

  • I’m going to submit another talk proposal, and if it’s accepted
  • I’ll practise it twice, at least and
  • I’ll get a remote control.
  • My laptop is too bulky for comfort. Dirk Haun ran his talk from a tablet. Could a phone be used?

My lightning talk ☞ Life A User’s Manual.

Slides for my main talk ☞ Lessons from the OuLiPo.

I would like to thank all the organisers of the conference, everyone who presented, and everyone who attended. Especial mention to Jon Jagger who announced that this would be his last year as conference chair. Let’s hope that in future years the mail bag continues to be inundated with letters! Pete Goodliffe too deserves a special mention for setting up three excellent lightning talk sessions. Controlled anarchy — he’s good at it!

2147483647

2015-02-12, Comments

Magic!

When software developers refer to “magic numbers” they mean those numeric literals which appear in a program without explanation — as if by magic. Consider the mysterious figures in this incantation:

int cigarettes()
{
    return 365 * 20 * 10 + 2 * 20 + 17;
}

Why is the 20 repeated? Does the first 20 mean the same as the second one? Could 365 be the number of days in a year? Named constants would make the code easier to read and maintain.

Some numbers truly are magical though.

2147483647

The number 2147483647 is special and terrible.

It’s a substantial number, far greater than the number of goals Lionel Messi has scored or the number of hot dinners I’ve eaten, and comparable with the number of heart beats in a lifetime or the number of instructions a processor executes in a second; but it’s not that large. You’ll need more than 2147483647 bytes to install a modern operating system, let alone store your video collection. And shuffling a pack of just 52 cards has 80658175170943878571660636856403766975289505440883277824000000000000 possible outcomes.

If 2147483647 isn’t remarkable for its size it certainly has a noteworthy history. In 1772 the Swiss mathematician Leonhard Euler proved it a prime. I’m guessing it was the largest known prime at the time. Euler didn’t have a computer to hunt for primes so he narrowed the field by focusing on Mersenne numbers — numbers one less than a power of two — a strategy which remains a winner even today, when computers are networked to search.

Actually, 2147483647 is a double Mersenne prime, which is to say it takes the form 2m - 1, where m itself takes the form 2n - 1.

>>> 2**(2**5 - 1) - 1
2147483647

Magic!

Dragons!

2147483647 has a special significance for C programmers, who know it by the name INT_MAX, and for C++ programmers, who demystify the digits as std::numeric_limits<int>::max().

Remember, 2147483647 is Mersenne(Mersenne(5)), which is Mersenne(31), or 2 to the power 31 minus 1. In binary arithmetic you add a zero on the right to multiply by 2 so 2 to the 31 is 1 followed by 31 zeros; and subtracting 1 leaves 31 1’s. It’s the largest signed value you can fit in a 32 bit register.

>>> mersenne31 = 2**31-1
>>> bin(mersenne31)
'0b1111111111111111111111111111111'
>>> hex(mersenne31)
'0x7fffffffL'
>>> mersenne31
2147483647L

It’s quite possible to inadvertantly increment an int which has reached INT_MAX. The result is undefined behaviour: anything could happen.

Gangnam Style

We never thought a video would be watched in numbers greater than a 32-bit integer (=2,147,483,647 views), but that was before we met PSY. Gangnam Style has been viewed so many times we had to upgrade to a 64-bit integer (9,223,372,036,854,775,808)!

youtube developers

Psy

Exactly what undefined behaviour was provoked when PSY’s popularity broke the magic limit isn’t disclosed. Maybe a server leaked account details to North Korean hackers. Or maybe the video’s viewing figures were wrong for a while.

Note that the new limit of 9,223,372,036,854,775,808 is an unsigned value, which is exempt from this flavour of undefined behaviour and wraps to zero when you bump it up.

Bugwards compatibility

There’s another reason for preferring INT_MAX to the magical 2147483647: the two values might be different. 2147483647 is 2147483647 but INT_MAX depends on the implementation.

A modern computer probably has 64 bit registers making a 64 bit int a more natural choice. However, for compatibility reasons, ints may intentionally be limited to 32 bits!

Lessons from the OuLiPo

2015-01-12, , , Comments

I’m delighted to announce that my talk, Lessons from the OuLiPo, has been accepted for the ACCU 2015 conference.

Slide 1

The talk follows up on a lightning talk I gave at my employer’s last year about Georges Perec’s masterpiece, Life A User’s Manual. Click the graphic below to play the animation and read the transcript.

Knights tour

I’ll be giving a preview of the full version here in Bristol in a couple of weeks. I hope you can come along. More details on Meetup.

In the meanwhile, the next section of this page introduces the ideas I’ll be exploring in my talk.

§

As software developers we often ponder what it is we do: are we architects, engineers, or scientists? Are we — gasp! — rock stars or ninjas? Which metaphors best fit? Tending a code base is like gardening. Through the seasons we encourage new growth, whilst pruning back dead code and squashing bugs. Programming is like carpentry, maybe. Select the right tool from a set kept sharp and ready for action. Programming is like cooking. Source the finest ingredients and follow the recipe.

I think there’s a more obvious metaphor. Actually there’s nothing meta- about it. It is what we do.

We’re writers.

We write to communicate and to instruct. We write for fun and profit. We edit and adapt. We rewrite. We borrow text from other writers. The languages we think we write in — C++, Python, Javascript — are actually just highly stylised dialects of our native tongue. Like poets we’re particular about punctuation and space. We have strange ideas about spelling. The texts we write, programs, are subject to formal constraints.

We’re writers bound by mathematical rules.

November, 1960. Paris. The poet Raymond Queneau organises the first meeting of a group which will become known as OuLiPo. A dozen turn up: writers, mathematicians, pataphysicians and surrealists. Their mission: to explore the literary potential of applying mathematical constraints to texts.

Of course constrained writing is nothing new — consider the haiku: 17 syllables, arranged as 3 phrases of 5, 7 and 5 syllables, a Japanese form many centuries old — and one strand of the OuLiPo’s efforts is devoted to researching past experiments and structures; but I claim it’s no coincidence the OuLiPo emerged at much the same time as our own novel form of constrained writing: computer programming.

In this talk I’ll discuss the OuLiPo in more depth, investigating the parallels between their work and ours. We’ll focus on Georges Perec, whose book Life A User’s Manual is an Oulipian tour de force. There will be some code, as well as quines, easter eggs and — as you’d expect — bugs.