Angle brackets hurt my eyes
“All these angle brackets, they’re hurting my eyes.”
I’m quoting a colleague who sits next to me and I sympathise. Perhaps a section from a build file was causing him pain?
<target name="all" description="Build product.">
<mkdir dir="build" if="${not directory::exists('build')}" />
....
</target>
Or maybe it was some XSL to generate XML by applying XML to XML?
<xsl:if test="$index-make or @index!='false'">
<xsl:if test="//index">
<fo:block text-align-last="justify" space-before="5pt">
<fo:basic-link internal-destination="index-page">
<xsl:choose>
<xsl:when test="(/doc/@lang = 'ja') or (/doc/@lang = '')</xsl:when>
<xsl:otherwise>INDEX</xsl:otherwise>
</xsl:choose>
</fo:basic-link>
<fo:page-number-citation ref-id="index-page"/>
</fo:block>
</xsl:if>
</xsl:if>
Or perhaps he was wrestling with a C++ compile error.
print.cpp: In function 'void print(const std::map<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, int, std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::allocator<std::pair<const std::basic_string<char, std::char_traits<char>, std::allocator<char> >, int> > >&)': print.cpp:7: error: no match for 'operator<<' in 'std::cout << details' /usr/include/c++/4.2.1/ostream:112: note: candidates are: std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(std::basic_ostream<_CharT, _Traits>& (*)(std::basic_ostream<_CharT, _Traits>&)) [with _CharT = char, _Traits = std::char_traits<char>]
What makes angle brackets so vexatious. Could it be their sharp corners?
Lisp is as elegant as XML is prickly, yet it too is famous for brackets, albeit round ones — and lots of them.
Imagine a parallel universe with angle-bracket Lisp. I wonder if the language would have proved so enduring?It’s not that Clojure/Lisp has a lot of parentheses. Its just that we removed everything else.
— Alex Miller (@puredanger) March 18, 2013
<define <euler-transform s>
<let <<s0 <stream-ref s 0>>
<s1 <stream-ref s 1>>
<s2 <stream-ref s 2>>>
<cons-stream <- s2 </ <square <- s2 s1>>
<+ s0 <* -2 s1> s2>>>
<euler-transform <stream-cdr s>>>>>
<mkdir dir="build" if="${not directory::exists('build')}" />
“Solutions”
I like working around enthusiasts and optimists but that doesn’t mean I want to use chirpy or bombastic software.
These days I build programs using visual studio. Sure, it’s a decent tool but part of me cringes every time I’m asked to open a “Solution” especially when what I get seems more like a “Muddle”. A progress bar slides into action after my program links: “Updating Intellisense …”
Who coined that galumphing portmanteau? It means auto-completion and I don’t want to know it’s going on — especially since I edit code using Emacs.
Perforce is new to me and I lean on a graphical client so heavily I sometimes trip over it. So when I’m trying to dance round client workspaces and their half-baked integration with microsoft muddles solutions, the last thing I want is to be asked to “Choose a Favorite Connection”. When it comes to Perforce Servers I don’t have favourites let alone favorites. Sorry.
ACCU 2013
Brian Marick opened the second day of ACCU 2013 with a keynote presentation entitled: “Cheating Decline: Acting now to let you program well for a really long time”. He drew a distinction between effortful and automatic thinking. For example, we can drive a car along a clear road automatically but it requires considerable concentration to parallel park that same car. By tuning out unwanted signals crickets can locate their mates using minimal brainpower, and cricket players have no need of Newtonian dynamics to track the trajectory of a ball — they apply a simple visual self-calibrating algorithm to catch out batsmen. Tango dancers disturb and re-establish invariants. A robot can walk for hours without thinking about what it’s doing. Actually, if it’s your job to park cars, you can probably do that without thinking; and this was Brian Marick’s main cheat — find the work practices which allow you to lean on your perceptions and so avoid effortful thinking.
Anthony Williams’ talk on C++11 Features and Real World code did require effortful thinking but that was what I’d hoped for. He provided a concise and expert summary of the new language features in action, focusing on the biggest early winners. Leading with auto, lambda, range-for, he went on to talk about concurrency and move semantics. I learned that lambda functions can have a mutable qualifier. Ha!
I couldn’t resist Olve Maudal’s C++11 pub quiz, appropriately held in the Marriot Hotel bar, for which we formed teams and mentally compiled and executed dodgy code, capturing standard output on an answer sheet. Some of the answers may well have have been implementation dependent but Olve specified an implementation: our answers should match this laptop running this software. I was simultaneously appalled by the limits of my knowledge on fundamental subjects such as integral promotion and initialisation order, and surprised by my ability to correctly predict the behaviour of some esoteric and perverse code. I’m chastened and will be studying the answers in the cold light of day. Brian Marick may have advocated programming after a beer or two in his morning session, but the afternoon pub quiz proved that coffee works better for me!
A programmer’s dozen (13, which is 12 counting from zero!) lightning talks kept the day crackling with energy. Ewan Milne chaired the session expertly, adeptly dispatching a birthday cake as proceedings commenced. I wish I could describe all the talks but you really had to be there. Phil Nash’s use of the little known left arrow operator ← got a well deserved response from the audience. Sander Hoogendoorn stuck the boot into “Agile Fluffiness”. James Grenning’s talk on embedded development was a lightning keynote: hilarious, moving and, ultimately, tragic.
An Exploration of the Phenomenology of Software Development
I was lucky to be in the audience last week, when Charles Tolman visited Accu Bristol to preview his Accu 2013 conference talk: “An Exploration of the Phenomenology of Software Development”.
The talk precis is entirely accurate — but maybe not so helpful. What this talk actually delivers is a highly original and thoughtful examination of what the software development revolution is and how we can make sense of it.
Charles Tolman’s central insight is that we have crossed a boundary. New tools and technologies have extended our powers. Just as machinery developed in the industrial revolution extended our physical abilities, so software developed in the information technology revolution extends our capacity for thought.
Essentially, software development is thinking, so to analyse it we need to think about thought. With this realisation we can view our industry as a continuation of the efforts of earlier thought workers — philosophers such as Descartes and Goethe.
If this all sounds a bit heavy, Charles made space for anecdotes, humourous insights and pictures of gliders. I look forward to future episodes.
Patience Sorted
I gave a lightning talk today about patience sorting and its application to the longest increasing subsequence problem. It’s a subject I’ve written about before. My computer has been put through several million simulations. I’ve even coded up a javascript demo which deals out virtual playing cards and sorts them at the click of a button.
Today I used real playing cards; a linen-finished standard deck. For any talk it’s nice to have a prop.
Now, I thought I understood the patience sort algorithm but until yesterday I’d never actually played it with real cards. I’ve been surprised by how much this physical dimension has developed my understanding.
I’ll be testing my new cards on some other sorting algorithms; I have high hopes. It would be good to find a similarly simple prop for linked data structures so I can balance trees, flip lists and walk graphs.
Hosting for Life? TextDrive revived!
Towards the end of last year I was emailed by Jason Hoffman from Joyent. Joyent owned TextDrive, the company which, 6 years ago, offered web hosting for life in return for a single up-front payment. Jason’s email said this lifetime hosting — legacy service, he called it — was nearing End of Life (!) and would be sunsetted (!!) at the end of October 2012.
As a TextDrive customer I reckon I’d had good value from the original deal, but while six years may seem like forever on the internet it’s surely not a lifetime. Happily TextDrive’s original founder, Dean Allen, felt the same way: he emailed me to say he’d be relaunching TextDrive on a new, modern, infrastructure.
Quite how this pans out remains to be seen but I’m sticking it out. If you’re reading this page, great: it’s been served up by the new, modern infrastructure which Dean mentioned. Whilst migrating wordaligned.org I’ve had to fiddle with rewrite rules and tinker with DNS records and file permissions. Any glitches or oddities, please let me know.
More adventures in C++
bool operator<(version const & v1, version const & v2)
{
if (v1.major != v2.major)
return v1.major < v2.major;
if (v1.minor != v2.minor)
return v1.minor < v2.minor;
if (v1.patch != v2.patch)
return v1.patch < v2.patch;
return v1.build < v2.build;
}
C++ programmers are sticklers for tradition and unlikely to be swayed by what’s in fashion. C++ suits those who want to control the machine, and who respect the rigour and discipline this imposes. C++ programmers are generally a conservative bunch.
Some history: C++ was standardized in 1998. The next major revision of the language was developed under the working title of C++0x, where the “0x” stood for the year the job would be finished. The X gave the standardizers some slack, but not enough. C++0x became C++11 which is now, thankfully, simply C++.
Although the language’s development has been painstakingly slow the developments themselves have been extensive and radical. What’s more, users are rushing to use the new features — even before they have access to compilers which support them! I’ve seen answers to C++ topics on Q&A sites which use aspects of the language the contributors cheerfully admit they have no access to. I’ve worked on a project which used elaborate shims to hide the fact that GCC 4.6 couldn’t compile C++ as well as GCC 4.7 does, and this despite the fact that GCC’s C++11 support remains, officially, “experimental”.
Singly Linked Lists in C++
In a recent post I wrote about removing items from a singly linked list. I presented a couple of alternative implementations, and in the comments section readers suggested yet more versions.
My implementations were written in C: the post was inspired by something Linus Torvalds had said about low-level programming skills, and I’m guessing he meant C programming skills. The fact is, C programmers are condemned to reimplement these basic functions on this basic structure because the C standard library has nothing to say about singly linked lists. Until recently the C++ standard library was similarly silent on the subject, only offering a doubly linked list.
C++ introduces … the linked list!
That’s all changed now with the introduction of std::forward_list. The class interface doesn’t mention links or pointers but a quick glance through its contents makes it clear that if you imagine the container to be a templated version of a classic singly-linked list, you won’t go far wrong.
This gives forward_list some members you won’t find elsewhere in the std:: namespace. For example, std::forward_list::before_begin(), which returns an iterator just before the beginning of the list — much as the more familiar end() is just past the end.
Why is before_begin() necessary? You can’t dereference it and you can’t reverse through a forward list till you get to it. Well, since forward list iterators can only go forwards, instead of the familiar sequence insert(), erase() and emplace() methods we have insert_after(), erase_after() and emplace_after(), not to mention splice_after(). The before-the-beginning iterator allows you to use these operations to modify the node at the head of the list.
Quick question: what’s the complexity of std::list::size()?
Trick question: and how about std::forward_list::size()?
Folded files and rainbow code
In one of my first programming jobs I worked at a software house which grew its own tools. We had a home made version control system, build system, test harness and programming language. We even had our own editor!
The language was C, lightly extended to support the primitive types of our particular problem domain. The editor was more esoteric. You drove it using the numeric keypad and it modeled source code as nested blocks:
- files contained blocks of:
- includes
- documentation
- data
- functions
- functions contained groups of:
- parameters:
- in parameters
- out parameters
- initialisation blocks
- assertions
- code blocks
- loops
- machine dependent sections
- returns
The editor facilitated navigation of this nested structure, with keypresses to fold and unfold.
You don’t need to write your own editor to get the benefits of code folding: most editors support it to some degree. With this particular editor, however, folding reached its apotheosis. You could crimp and tuck and pleat, nesting layer upon layer within a single source file.
C++ Concurrency in Action
★★★★★
C++ Concurrency in Action is an excellent book. You should buy it if you want to use the support for concurrency added by the new C++ standard, C++11; and if you’re using C++11 you’ll deepen your understanding of the various language enhancements and how they work together.
Who’s the author? What makes him qualified to write this book?
Anthony Williams is a UK-based developer and consultant with many years experience in C++. He has been an active member of the BSI C++ Standards Panel since 2001, and is author or coauthor of many of the C++ Standards Committee papers that led up to the inclusion of the thread library in the new C++ Standard, known as C++11 or C++0x. He has been the maintainer of the Boost Thread library since 2006, and is the developer of the just::thread implementation of the C++11 thread library from Just Software Solutions Ltd. Anthony lives in the far west of Cornwall, England. — About the Author, Manning website
It’s clear the experience of writing papers for the standards committee has paid off. The book is well organised and clearly written. Accurate and thorough, it’s also a pleasure to read. The examples are practical, and range from launching threads through to lock-free message queues. The largest case study — a message passing framework and an ATM application built on this framework — shows the expert use of modern C++ to write elegant and compact code.
The clarity of the text is matched by the book’s clean and functional design. It looks good. I bought the dead-tree version which gave me free access to the ebook and I’ve made use of both formats.
I’m new to C++11 and compilers are still catching up with the standard. This book is steeped in C++11. Reading through it, I came to realise that a close look at the standard thread library helps explain the evolution of the language as a whole: so that’s why variadic templates are needed, and move semantics work there, and — I get it! — lambda functions fit nicely with condition variables.
Recommended++
Python’s lesser known loop control
I’ll break out of a loop if I have to but generally prefer to recast code so no break is needed. It’s not about avoiding the keyword; but rather that the loop control expression should tell readers when and why the loop exits.
In C and C++ such recasting is rarely a problem. Python separates statements and expressions which makes things more difficult. You can’t assign to a variable in a loop control expression, for example. Consider a function which processes a file one chunk at a time, until the file is exhausted.
while True:
data = fp.read(4096)
if not data:
break
...
The control expression, while True, suggests an infinite loop, which isn’t what actually happens, but readers must poke around in the loop body to find the actual termination condition.
As already mentioned, an assignment statement isn’t an expression, so we can’t write this:
while data = fp.read(4096):
...
You could implement a file reader generator function which yields chunks of data, allowing clients to write:
for data in chunked_file_reader(fp):
...
This at least localises the problem to chunked_file_reader().
Another solution is to use the two argument flavour of iter, iter(object, sentinel). Here, object is a callable and sentinel is a terminal value. Object is called with no arguments: use functools.partial to set the chunk size passed to file.read; and stop when this function returns the empty string.
import functools
chunked_file_reader = functools.partial(fp.read, 4096)
for data in iter(chunked_file_reader, ''):
...
Two star programming
A few weeks ago Linus Torvalds answered some questions on slashdot. All his responses make good reading but one in particular caught my eye. Asked to describe his favourite kernel hack, Torvalds grumbles he rarely looks at code these days — unless it’s to sort out someone else’s mess. He then pauses to admit he’s proud of the kernel’s fiendishly cunning filename lookup cache before continuing to moan about incompetence.
At the opposite end of the spectrum, I actually wish more people understood the really core low-level kind of coding. Not big, complex stuff like the lockless name lookup, but simply good use of pointers-to-pointers etc. For example, I’ve seen too many people who delete a singly-linked list entry by keeping track of the
preventry, and then to delete the entry, doing something likeif (prev) prev->next = entry->next; else list_head = entry->next;and whenever I see code like that, I just go “This person doesn’t understand pointers”. And it’s sadly quite common.
People who understand pointers just use a “pointer to the entry pointer”, and initialize that with the address of the list_head. And then as they traverse the list, they can remove the entry without using any conditionals, by just doing a
*pp = entry->next.
Well I thought I understood pointers but, sad to say, if asked to implement a list removal function I too would have kept track of the previous list node. Here’s a sketch of the code:
typedef struct node
{
struct node * next;
....
} node;
typedef bool (* remove_fn)(node const * v);
// Remove all nodes from the supplied list for which the
// supplied remove function returns true.
// Returns the new head of the list.
node * remove_if(node * head, remove_fn rm)
{
for (node * prev = NULL, * curr = head; curr != NULL; )
{
node * const next = curr->next;
if (rm(curr))
{
if (prev)
prev->next = next;
else
head = next;
free(curr);
}
else
prev = curr;
curr = next;
}
return head;
}
The linked list is a simple but perfectly-formed structure built from nothing more than a pointer-per-node and a sentinel value, but the code to modify such lists can be subtle. No wonder linked lists feature in so many interview questions!
The subtlety in the implementation shown above is the conditional required to handle any nodes removed from the head of the list.
Now let’s look at the implementation Linus Torvalds had in mind. In this case we pass in a pointer to the list head, and the list traversal and modification is done using a pointer to the next pointers.
void remove_if(node ** head, remove_fn rm)
{
for (node** curr = head; *curr; )
{
node * entry = *curr;
if (rm(entry))
{
*curr = entry->next;
free(entry);
}
else
curr = &entry->next;
}
}
Much better! The key insight is that the links in a linked list are pointers and so pointers to pointers are the prime candidates for modifying such a list.
§
The improved version of remove_if() is an example of two star programming: the doubled-up asterisks indicate two levels of indirection. A third star would be one too many.
ACCU Bristol and Bath
Lightning talks. In a pub. Me first! I hadn’t actually practised but I knew what I wanted to say and had picked a subject so trivial I couldn’t possibly overrun.
Yes, it was time, at last, for the first ACCU Bristol & Bath meeting, to be held in an upstairs room at the Cornubia. We’d reconnoitred the venue a few weeks earlier. Although the room was dingy and we couldn’t work out where to put a screen, and despite disturbance from the increasingly raucous CAMRA meeting next door, the location was ideal and the beer superb. I looked forward to returning.
Plans change. In an agile last minute switch the meeting relocated to the Marriot — which, coincidentally, had just been announced as the host of next year’s ACCU conference. I shuffled through revolving doors into the hotel’s vacant lobby rehearsing my talk in my head. Where was everyone? It took some backtracking and interrogation to locate the subterranean room but fortunately they hadn’t started without me.
Now this was a proper meeting room. Panelled walls, no windows. A blank TV screen; green apples; red glasses; bottled water.
Ewan welcomed me. “Have you got a macbook display adapter?”
No. I didn’t even have the slides to my own presentation — I’d emailed them ahead to be merged into a single deck.
The screen flicked to life. Nine talks, five minutes each. We’d be done in an hour. After a brief welcome my slides were on screen and I was off.
Unfortunately I ran out of time, laughing too long at my own lightning anecdote which framed a talk about ellipses, the triple-dots … which mean different things in different places in different programming languages. Next up was Dan Towner who walked us through the algorithm used by compilers for allocating registers. It’s a greedy colouring of a planar map, he said, wrapped in a bail-and-retry loop. Dan Tallis spoke about the single committer model which works so well on open source projects. Developers don’t have write access to the repository and must submit patches to the committer for review, a protocol which encourages incremental and considered changes to a codebase. Kevlin Henney needed just a single slide to clear up some misconceptions in exactly five minutes. Chris Simons didn’t need any slides to describe where designs come from. Pacing the floor and waving his fingers, he explained that computer systems are punchlines; design is a matter of figuring out the joke. Attack the solution space with ants! No ACCU meeting would be complete without a discourse on C++ test frameworks and Malcolm Noyes duly dazzled us developing a C++ mocking library before our very eyes. Jim Thomson compared before and after binaries to prove his source code rearrangements hadn’t caused any damage. Ewan Milne, who’d not only organised and chaired the meeting, also contributed a talk on (guess what?) planning, subtitled how agile can Kanban be (say it!)
Jon Jagger postponed his closing talk. Macs just work if you’ve got the right connectors. We hadn’t. The audience wanted more but that’s no bad thing. We regathered in the hotel bar to crunch apples and chew over the evening. The ACCU Bristol & Bath launch had been a success! The price of a pint and anodyne surroundings discouraged lingering. We drank up and headed off towards trains, homes, and, for a select few, the Cornubia.
Life goes on
In my previous post I described John Conway’s Game of Life as a hello world for computer graphics. Actually, it goes beyond that. Hello world is a complete program, a proof the toolchain works, but it’s not a particularly interesting program. An implementation of the game of life does more than demonstrate you can put pixels on screens: the evolution of those pixel colonies turns out to be a subject worth studying in itself.
That said, I’m primarily interested in Life as an exercise in learning new things. I’ve continued to develop my canvas implementation, adding some jQuery UI effects. The code is on Github — yes, it’s high time I learned about that too — though note there are dependencies on jQuery, jQuery UI, Imagemagick, and on pattern files downloaded from conwaylife.com.
A working version can be found at wordaligned.org/life. Click the graphic below to give it a go. Your web client does support HTML5 Canvas, right?
Thanks, anachrocomputer, for the delightful hello world photo
Life on Canvas
I was lucky enough to be taught maths by John Horton Conway, if only for an hour a week for a single term. He was lucky enough to be teaching number theory: a subject packed with treasures picked from the full history of mathematics.
I remember him as animated and unkempt. He bustled into that first lecture with a carrier bag and started pulling out groceries one by one. How many items were in the bag, he wondered? Could he count them all — it was a very large bag — and what exactly did infinity mean? Later I would see him pacing along Kings Parade dragging a shopping tolley, lost in thought.
Number theory may be as old as mathematics but it remains very much alive. Some 40 years ago Professor Conway discovered a primitive and novel mathematical life form: the Game of Life.
The rules are simple. A colony of cells inhabits a two dimensional grid. At any one time each cell is either alive or dead, and as time advances the fate of a cell is determined entirely by its immediate 8 neighbours:
- reproduction: a dead cell with exactly 3 live neighbours becomes alive
- survival: a live cell with 2 or 3 live neighbours lives on
- overcrowding or loneliness: in all other cases the cell dies or stays dead
In code, we might represent the colony as a two dimensional array filled with 1’s and 0’s for live and dead cells and code up the rules like this:
// Determine the fate of cell i, j in the next generation.
// Return 1 for "lives", 0 for "dies"
function fate(cells, i, j) {
var neighbours = [[-1,-1],[-1,0],[-1,1],
[0,-1], [0,1],
[1,-1], [1,0], [1,1]];
live_neighbours = 0;
neighbours.forEach(function(n) {
live_neighbours += cells[i + n[0]][j + n[1]];
});
return (live_neighbours == 3 ||
cells[i][j] == 1 && live_neighbours == 2) ? 1 : 0;
}
It turns out these simple rules generate an astonishing ecosystem. Simple patterns flourish, evolving into complex patterns which, many generations later may decay into stable forms and repeating patterns, or, occasionally, become extinct.
Can a finite pattern grow indefinitely? Conway originally conjectured no, this was impossible, offering $50 to the first person who could prove or disprove the his conjecture before the end of 1970. In November of that year a team from MIT led by Bill Gosper claimed the prize, disproving the conjecture with a glider gun pattern which spits out a new spaceship every 30 generations.
Articles