Word Aligned

Angle brackets hurt my eyes

tag@wordaligned.org (Thomas Guest) — 2013-05-01

“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.

It’s not that Clojure/Lisp has a lot of parentheses. Its just that we removed everything else.
— Alex Miller (@puredanger) March 18, 2013

Imagine a parallel universe with angle-bracket Lisp. I wonder if the language would have proved so enduring?

Not so pretty now?

<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>>>>>

Looking more closely at the first code snippet, the section from a build file, we can see the problem isn’t so much the angle brackets as all the others.

<mkdir dir="build" if="${not directory::exists('build')}" />

The braces and parentheses may be embedded in a double quoted string but that only makes things worse. The nested levels hurt my eyes and, if you can bear to look at the code long enough, you’ll realise there’s a simpler message trying to get out: mkdir -p build.

“Solutions”

tag@wordaligned.org (Thomas Guest) — 2013-04-17

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

tag@wordaligned.org (Thomas Guest) — 2013-04-11

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

tag@wordaligned.org (Thomas Guest) — 2013-04-02

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

tag@wordaligned.org (Thomas Guest) — 2013-03-14

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!

tag@wordaligned.org (Thomas Guest) — 2013-03-06

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++

tag@wordaligned.org (Thomas Guest) — 2013-02-21

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”.

At home, I’m downloading compiler and library updates I’m in no position to use at work; and at work, I’ve already been sent on a C++11 training course. I’ve streamed high quality videos starring C++’s big hitters which promote the new C++, explaining its principles, its foundations, and even where it’s going next.

What exactly is it about C++11 that’s roused such a normally phlegmatic audience?

Before I try and answer that, I’ll venture to suggest new C++ isn’t going to win many new recruits. I don’t even think it will persuade those who have abandoned the language to return. C++11 contains all of C++98, a notoriously complex and subtle language, then adds a whole lot more. Yes, it is possible to write new C++ which is more compact and efficient than traditional C++, but you’ll also need to maintain old C++ code and build new expertise. And the language update fails to address some of C++’s worst characteristics: slow compile times and impenetrable compiler diagnostics.

No, C++11 is primarily a win for existing C++ programmers; those of us who already have a fair understanding of the language and its trade-offs, and who can appreciate the rationale behind the changes. For traditionalists and pragmatists, the transition isn’t hard — at least, no harder than any port between compiler revisions. For progressives, there are several immediate wins: the auto keyword has been repurposed, reducing repetition and making code more flexible; lambdas enable functions to be plugged directly into algorithms; smart pointers are standard, allowing accurate memory management; and on the subject of memory, rvalues and move semantics mean you’ll waste less of it on temporaries.

I could go on.

Rather than risk more generalisations, here’s a specific example of C++11 in action. Consider an object with multiple fields, a four part version number, say.

struct version
{
    unsigned major, minor, patch, build;
};

To compare version numbers, or sort them, or put them in a std::set, we’ll need operator<(). This operator must model a strict weak ordering. The canonical form looks something like.

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;
}

It’s not so hard to write this code for the version struct, where we have a clear idea of what it means for one version number to be less than another. It would be rather more tricky if we were dealing with points, for example, struct point { int x, y; };. Ordering points makes little sense but we might well want them as keys in an associative container, and we’d better have a suitable operator<().

No, no, no!

bool operator<(point const & p1, point const & p2)
{
    return p1.x < p2.x && p1.y < p2.y;
}

With C++11 — with the current version of C++ — we can use std::tie() to create a tuple of references, recasting operator<() into a form that’s easy to read and hard to get wrong.

Yes, yes, yes!

bool operator<(version const & v1, version const & v2)
{
    return std::tie(v1.major, v1.minor, v1.patch, v1.build)
         < std::tie(v2.major, v2.minor, v2.patch, v2.build);
}

bool operator<(point const & p1, point const & p2)
{
    return std::tie(p1.x, p1.y) < std::tie(p2.x, p2.y);
}

My thanks to Jonathan Wakely for sharing the std::tie() recipe on the accu-general mailing list and for letting me use it here.

Singly Linked Lists in C++

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

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()?

Remove_if for forward lists

Using pointers-to-pointers to modify linked lists gives this elegant and compact C implementation of remove_if(), which de-lists all nodes which match a supplied predicate.

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;
    }
}

How does the C++ standard library support this algorithm?

Std::remove_if() operates on an iterator range, remove_if(first, last, pred). All it requires is that the iterators are forward iterators so it should just work on a forward_list.

Hang on though: what if pred(*first) is true? How can a node be removed from a linked list without reference to its predecessor? Actually, the node isn’t removed — the value it contains gets overwritten by the value in the first node (if any!) for which the predicate returns false. In fact, remove_if doesn’t remove anything from the container! What it does is return an iterator, call it new_last, such that the range (first, new_last) holds the elements which have been kept, and (new_last, last) holds those which have been “removed”, which is to say they can still be dereferenced but their value is implementation dependent.

Remove_if usually pairs up with erase:

container.erase(remove_if(first, last, pred), last);

There is no std::forward_list::erase(iterator) — remember, we can only erase after — so the usual remove_if algorithm is of little use for forward lists.

Forward_list::remove_if()

As usual, we should prefer member functions to algorithms with the same names. C++’s forward_list has its very own remove_if which manipulates pointers rather than moves values, and which really does remove and destroy items.

Forward_list::remove_if() operates on the list as a whole, not an iterator range — as we’ve seen, an iterator cannot remove itself. I took a look at a couple of implementations of this function to see how it’s done.

Here’s LLVM’s libc++ implementation:

template <class _Tp, class _Alloc>
template <class _Predicate>
void
forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred)
{
    iterator __e = end();
    for (iterator __i = before_begin(); __i.__ptr_->__next_ != nullptr;)
    {
        if (__pred(__i.__ptr_->__next_->__value_))
        {
            iterator __j = _VSTD::next(__i, 2);
            for (; __j != __e && __pred(*__j); ++__j)
                ;
            erase_after(__i, __j);
            if (__j == __e)
                break;
            __i = __j;
        }
        else
            ++__i;
    }
}

There’s no need for any special treatment of the first list node here, since we have its predecessor, the before_begin() node. The function does double back though, figuring out the next range to erase before going back to erase it — and the erase function isn’t pretty.

template <class _Tp, class _Alloc>
typename forward_list<_Tp, _Alloc>::iterator
forward_list<_Tp, _Alloc>::erase_after(const_iterator __f, const_iterator __l)
{
    __node_pointer __e = const_cast<__node_pointer>(__l.__ptr_);
    if (__f != __l)
    {
        __node_pointer __p = const_cast<__node_pointer>(__f.__ptr_);
        __node_pointer __n = __p->__next_;
        if (__n != __e)
        {
            __p->__next_ = __e;
            __node_allocator& __a = base::__alloc();
            do
            {
                __p = __n->__next_;
                __node_traits::destroy(__a, _VSTD::addressof(__n->__value_));
                __node_traits::deallocate(__a, __n, 1);
                __n = __p;
            } while (__n != __e);
        }
    }
    return iterator(__e);
}

For comparison, here’s how GCC’s libstdc++ does the same thing.

template<typename _Tp, typename _Alloc>
    template<typename _Pred>
      void
      forward_list<_Tp, _Alloc>::
      remove_if(_Pred __pred)
      {
	_Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
        while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
          {
            if (__pred(*__tmp->_M_valptr()))
              this->_M_erase_after(__curr);
            else
              __curr = static_cast<_Node*>(__curr->_M_next);
          }
      }

Here, erasing (after a) node reads:

template<typename _Tp, typename _Alloc>
    _Fwd_list_node_base*
    _Fwd_list_base<_Tp, _Alloc>::
    _M_erase_after(_Fwd_list_node_base* __pos)
    {
      _Node* __curr = static_cast<_Node*>(__pos->_M_next);
      __pos->_M_next = __curr->_M_next;
      _Tp_alloc_type __a(_M_get_Node_allocator());
      allocator_traits<_Tp_alloc_type>::destroy(__a, __curr->_M_valptr());
      __curr->~_Node();
      _M_put_node(__curr);
      return __pos->_M_next;
    }

This version walks through the list removing nodes which match the predicate as it finds them. Don’t be confused by &this->_M_impl._M_head: it’s not the node at the head of the list, it’s the one before.

Lessons from C++

Maybe this code wouldn’t persaude Linus Torvalds to rethink his opinion of C++, but if you can see past the angle brackets, underscores and allocators, it’s simple enough.

It’s also:

subtle, so I’m glad someone else has written and checked it
generic, so I can put what I want in a list without casting or indirection
standard, so I know what to expect
supported

The before-begin node idea serves equally well in C, enabling list modifiers which have no need of double indirection or special case code for the list head.

void remove_after(node * prev, remove_fn rm)
{
    while (prev->next != NULL)
    {
        node * curr = prev->next;
        if (rm(curr))
        {
            prev->next = curr->next;
            free(curr);
        }
        else
            prev = curr;
    }
}

Pass this function the before-begin node to remove all items from the list which match the predicate.

Folded files and rainbow code

tag@wordaligned.org (Thomas Guest) — 2013-01-23

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.

The house editor wasn’t mandated but the fold tokens it automatically placed in special comments made it challenging to work with anything else ^[1].

Folding made it easy to work with large files and long, complex functions. Looking back, I’d say it made it too easy — I’ve come to prefer other ways of organising code — but at the time I saw things differently. We all did. What interests me now is the effect an editor has on the shape of your code.

A wide editing pane renders long lines comfortably. Code completion makes forgettable names workable. Smart indentation keeps your code legal even as you type. Cut and paste allows you to replicate an existing function and tweak it for a new use case. Undo, redo and autosave are like version control made simple.

The folding editor failed to seduce everyone. One colleague grumbled it lacked syntax highlighting. Well, it probably came from an age before coloured pixels, and, similarly dated, at the time, I couldn’t see the need.

These days I find it hard to operate without syntax highlighting: code doesn’t even look like code if imports, literals, comments etc. aren’t visually distinct. Yet there are elite programmers who write their own programming languages using their own editors who find syntax highlighting a distraction.

Walking round the office where I work I see a diversity of editors. There are split screens and floating windows, stacked up toolbars, icons piled high. Helicopter views expose the jagged outlines of source code seen from a distance. Lenses zoom in on regions of interest. Tokens glow like plankton in deep sea colour schemes.

It’s good practice to develop code on multiple platforms even if your product targets just one. Different compilers and hardware exercise your software in different ways, making it resilient and portable. I wonder too if multiple editors scrutinize your software from different perspectives, keeping it flexible and clean.

My thanks to Gary Cobb for permission to use his origami dragon snap, and to willapalens for the plankton. The video clip is by Russ Cox, acme fanatic and go developer.

[1]: Programmers relish challenges and one seasoned emacs user had put together an emacs mode to cope with the folds.

C++ Concurrency in Action

tag@wordaligned.org (Thomas Guest) — 2013-01-21

★★★★★

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

tag@wordaligned.org (Thomas Guest) — 2013-01-14

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:

Syntax error!

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

tag@wordaligned.org (Thomas Guest) — 2013-01-08

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 prev entry, and then to delete the entry, doing something like
if (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:

This person doesn’t understand pointers

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.

Two star programming

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

tag@wordaligned.org (Thomas Guest) — 2012-08-31

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

tag@wordaligned.org (Thomas Guest) — 2012-06-29

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

tag@wordaligned.org (Thomas Guest) — 2012-06-27

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.

A 2 dimensional array can naturally be represented on the most basic computer screen — think raster graphics, pixels — and the parallel emergence and development of the personal computer helps explain life’s continuing appeal^[1]. The game of life has become the hello world of graphics frameworks. In 2012 we can use the HTML5 canvas, a 2 dimensional surface for drawing on.

After a little experimentation you’re sure to uncover life’s three main domains: still lives, which remain unchanged; oscillators, which repeat; and spaceships, which move across the board. Then there are methuselahs, puffers, guns …

Here’s a pulsar, an oscillator with period 3.

And here’s a glider, classed as a diagonal spaceship, a pattern chosen by Eric S Raymond as a hackers’ emblem.

Here’s another 5 cell pattern — the R-pentomino. Clear the canvas, pick out an R-pentomino cluster of cells with the mouse, click play, and watch what evolves!

Turtle, garden, unicycle: animal, vegetable, mineral. The kingdom of life is inclusive and extensive, a delight for naturalists and taxonomists alike. It’s seduced logophiles and lexicographers too: reading through Stephen A. Silver’s comprehensive Life Lexicon, I learned that an anteater consumes ants, a caterpillar works by laying tracks at its front end, a baker’s dozen is a loaf hassled by two blocks and two caterers, and an AK47 reaction occurs when a honey farm predecessor, catalysed by an eater and a block, reappears at another location 47 generations later, having produced a glider and a traffic light. I could go on…

[1]: I’m glossing over details here. The true game of life is played out on an infinite grid, and patterns such as Gosper’s glider gun show that it really does have to be infinite. Computers have trouble with such an unconstrained requirement, and a computer animation might try and adapt the screen as the pattern grows, or limit the region of interest. Another approach is to wrap the canvas, left to right, top to bottom, so the game of life is played out on what’s topologically a toriodal surface. That’s what the canvas shown here does.

The icons used on this page were downloaded from http://glyphicons.com and are licensed under the CC BY 3.0 terms. The animated gifs were placed in the public domain by their authors.

Desktop preferences

tag@wordaligned.org (Thomas Guest) — 2012-06-21

Paul grumbled about the lack of new content on wordaligned.org and since he’d just bought me lunch I thought I’d better do something about it. He also said he didn’t like the stuff about algorithms and maths. Well, that makes my life easier too.

I’m moving jobs — the lunch he paid for was a leaving do — and my employers kindly allowed me to buy this macbook pro at a reasonable price. Of course I had to wipe and reinstall it. It took an hour and a half to fill the hard drive with zeros and a similar amount of time to load a few ones back on^[1].

Installation done, I set about customisation. The official term is preferences but annoyances would be more accurate: you fix things which irk you before they cause real pain or, worse, you become immune to them. Typing hurt until I set key repeat to the max. Thomas Guest’s macbook pro is a lousy name. I’ve used Itchy before and I like it so I’m using it again. I booted Safari off the dock and stood Chrome in its place. I undocked some other things which I didn’t recognise by their icons and were obviously of no use to me. By now I’d seen the galactic login backdrop too many times. I’ve never found a customisable preference for it but google told me what to do.

$ sudo cp Downloads/matt-burns-pylon.jpg \
          /System/Library/CoreServices/DefaultDesktop.jpg

Actually, that’s pretty much all I needed to fix. Now it really was about preferences I prefer. Aquamacs. Skype. I chose two pictures for my desktop backgrounds. What you want on a desktop — no, what I want on my desktop — is something gorgeous but not distracting, something personal but not too personal, something which works in widescreen, something of a high enough resolution, something which doesn’t get spoiled when application windows are slathered over it. I went with a couple more Burnsy’s.

I remember the second Severn crossing being built. I’d just moved to Bristol, joining a company which did virtual reality. The hardware was too expensive and the software too slow but we were a good team. Summer lunchtimes, we would play frisbee on the grassy hill by the Almondsbury garden centre. You could see the estuary, the new concrete pylons stepping into it, and, rising to the East, the towers of the original suspension bridge. Anyone who cycles around Bristol knows this view well. Interval training with Owen, we spin out along Passage Road and catch our breath before turning back.

More recently I’ve moved to Swansea but kept my job in Bristol, crossing from and to Wales under the river twice a week, Tuesdays and Thursdays, working from home on Mondays and Fridays. Now that too has come to an end. We were a good team but … anyway. My new job will be home-based. Next I’ll be partitioning the hard drive and booting into Linux.

My thanks, again, to Matt Burns for allowing me to use his superb photos.

[1] Which reminds me, I should write about a cunning data structure which lazily initialises a sparse vector. Wordaligned.org is a programming blog, honest.

Knuth visited, Brains Limited

tag@wordaligned.org (Thomas Guest) — 2011-02-03

Lucky me, I did get a ticket to see Professor Donald Knuth deliver the 2011 Turing Lecture at Cardiff University. He started out by saying he’d been wanting to come here ever since seeing Yellow Submarine in the 60s because of some dialogue which goes something like:

“What do you call a big school of whales?”

“A University of Wales.”

What a fine country Wales is for a computer scientist, he continued, you have a place called Login. A village in Pembrokeshire, someone in the audience chipped in, it’s very beautiful. Wonderful, all the more reason to visit!

Openings over, the lecture turned into a question and answer session. If I’m honest, I’d have preferred something more formal, but having just completed TAOCP4A, all 900 pages of it, and Volume 8 of his collected papers, the “dessert” edition of the series on fun and games, Professor Knuth was in a holiday mood, and it was a delight to hear him field questions on the future of computer science, P = NP, literate programming, analog computers, brute force vs. elegance, and whether the increase in computing power diminishes the art of programming.

Yes, computers grow exponentially more powerful — but human appetites grow yet more quickly. And even if you have all of that power, can you be sure the computers are getting the right answers? This afternoon, Professor Knuth said, while strolling through Cardiff, he’d seen the famous brewery Brains & Co. Ltd. and thought, yes, that’s about right. Brains limited.

My thanks to Arkadyevna for permission to use her wonderful photo.

Set.insert or set.add?

tag@wordaligned.org (Thomas Guest) — 2010-11-17

Get set, go!

Suppose you have an element e to put in a set S.

Should you:

S.add(e)

or:

S.insert(e)

It depends on which language you’re using. I use C++ and Python and I usually get it wrong.

>>> S.insert(e)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'set' object has no attribute 'insert'

Try again!

error: 'class std::set<int, std::less<int>, std::allocator<int> >' 
has no member named 'add'

Maybe my IDE should auto-complete the correct member function but it doesn’t, or at least I haven’t configured it to, so instead I’ve worked out how to remember.

Now, neither C++ nor Python pins down how a set should be implemented — read the language standard and reference manual respectively and all you’ll get is an interface and some hints. Read between the lines of these references, though, or study the implementations, and you’ll soon realise a Python set is an unordered container designed for fast membership, union, intersection, and differencing operations — much like the mathematical sets I learned about at school — whereas a C++ set is an ordered container, featuring logarithmic access times and persistent iterators.

Think: C++ set ≈ binary tree; Python set ≈ hashed array.

It’s apparent which method is correct for which language now. To put something into a binary tree you must recurse down the tree and find where to insert it. Hence std::set::insert() is correct C++. To put something into a hashed array you hash it and add it right there. Hence set.add() is proper Python.

How long is a string?

I’m suggesting programmers should know at least some of what goes on in their standard language library implementations. Appreciating an API isn’t always enough. You insert into trees and add to hashes: so if your set is a tree, call S.insert(), and if it’s a hash, S.add().

Such logical arguments don’t always deliver.

Question: Suppose now that S is a string and you’re after its length. Should you use S.length() or S.size()?

Answer: Neither or both.

In Python a string is a standard sequence and as for all other sequences len(S) does the trick. In C++ a string is a standard container and as for all other containers S.size() returns the number of elements; but, being std::string, S.length() does too.

Oh, and the next revision of C++ features an unordered_set (available now as std::tr1::unordered_set) which is a hashed container. I think unordered_set is a poor name for something which models a set better than std::set does but that’s the price it pays for coming late to the party. And you don’t std::unordered_set::add elements to it, you std::unordered_set::insert them.

My thanks to the|G|™ for permission to use his string.

Define pedantic

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

My dictionary defines a pedant as:

pedant n. 1. A person who relies too much on academic learning or who is concerned chiefly with academic detail.

Apparently the word derives from the Italian, pedante, meaning teacher. During my career as a computer programmer a number of my colleagues have been surprisingly pedantic about the proper use of English.

“I refuse to join a supermarket queue marked 10 items or less.”

“I do wish people would stop using target as a verb. You aim at a target, you don’t target it.”

“I am an exceptionally skilled grammarian in English … Take that rule and shove it!”

Some of this fussiness may well be a reaction against corporate double-speak. Still, I wouldn’t have expected programmers to be 1) so particular and 2) so certain they’re right. Maybe this attitude comes from all those years of writing code. Programming languages are strict about what they’ll accept: after all, they have standards!

Some programming languages are more pedantic than others. Paul Graham memorably characterises C++ as a pernickety aunt^[1]. By contrast, Perl won’t pick nits. Designed by Larry Wall to be his software butler, Perl interprets your ill-expressed wishes with discretion and assurance. Hence you can end up with a Perl program which gets on with its job but which no-one fully understands.

Pedants, by definition, take things too far, but pedantry in programming isn’t all bad. GCC has a useful -pedantic flag. It helps you write portable programs. Perl has a use strict pragma which recasts the butler as a personal trainer.

When it comes to correctness, attention to detail matters. What if this input parameter goes negative? Will that file be closed when an exception is thrown? Can your algorithm handle an empty container?

I recently fixed a defect in some (of my own) code which assumed conformant input. When faced with garbage-in this code failed even to generate garbage-out, instead getting caught in an infinite loop. Should a pedantic program insist on correct inputs or should it consider how to handle all possible inputs? Define pedantic.

[1]: It turns out my memory is at fault here. When I checked the reference I discovered Paul Graham makes no explicit mention of C++.

We need a language that lets us scribble and smudge and smear, not a language where you have to sit with a teacup of types balanced on your knee and make polite conversation with a strict old aunt of a compiler. — Paul Graham, Hackers and Painters

You might have guessed which language he’s promoting for scribbling but there’s no mention of Lisp either in this particular essay. In fact only one programming language earns a name-check. I’ll let you find out which one for yourselves.

Hiding iterator boilerplate behind a Boost facade

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

Filling in missing methods. Python

Here’s another wholesome recipe served up by Raymond Hettinger.

Total ordering class decorator

def total_ordering(cls):
    'Class decorator that fills-in missing ordering methods'    
    convert = {
        '__lt__': [('__gt__', lambda self, other: other < self),
                   ('__le__', lambda self, other: not other < self),
                   ('__ge__', lambda self, other: not self < other)],
        '__le__': [('__ge__', lambda self, other: other <= self),
                   ('__lt__', lambda self, other: not other <= self),
                   ('__gt__', lambda self, other: not self <= other)],
        '__gt__': [('__lt__', lambda self, other: other > self),
                   ('__ge__', lambda self, other: not other > self),
                   ('__le__', lambda self, other: not self > other)],
        '__ge__': [('__le__', lambda self, other: other >= self),
                   ('__gt__', lambda self, other: not other >= self),
                   ('__lt__', lambda self, other: not self >= other)]
    }
    roots = set(dir(cls)) & set(convert)
    assert roots, 'must define at least one ordering operation: < > <= >='
    root = max(roots)       # prefer __lt__ to __le__ to __gt__ to __ge__
    for opname, opfunc in convert[root]:
        if opname not in roots:
            opfunc.__name__ = opname
            opfunc.__doc__ = getattr(int, opname).__doc__
            setattr(cls, opname, opfunc)
    return cls

If you have a class, X, which implements one or more of the ordering operators, <, <=, >, >= then total_ordering(X) adapts and returns the class with the missing operators filled-in. Alternatively, use standard decorator syntax to adapt a class. If we apply @total_ordering to a Point class

@total_ordering
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __lt__(self, other):
        return (self.x, self.y) < (other.x, other.y)

then we can compare points however we like

>>> p = Point(1,2)
>>> q = Point(1,3)
>>> p < q, p > q, p >= q, p <= q
(True, False, False, True)

Here’s a nice touch: the freshly-baked methods even have documentation!

>>> help(Point)
Help on class Point in module __main__:

class Point
 |  Methods defined here:
 |  
 |  __ge__(self, other)
 |      x.__ge__(y) <==> x>=y
 |  
 |  __gt__(self, other)
 |      x.__gt__(y) <==> x>y
 |  
 |  __init__(self, x, y)
 |  
 |  __le__(self, other)
 |      x.__le__(y) <==> x<=y
 |  
 |  __lt__(self, other)

Writing class decorators may not be the first thing a new Python programmer attempts, but once you’ve discovered the relationship between Python’s special method names and the more familiar operator symbols, I think this recipe is remarkably straightforward.

convert = {
    '__lt__': [('__gt__', lambda self, other: other < self),
               ('__le__', lambda self, other: not other < self),
               ('__ge__', lambda self, other: not self < other)],
    '__le__': [('__ge__', lambda self, other: other <= self),
               ('__lt__', lambda self, other: not other <= self),
               ('__gt__', lambda self, other: not self <= other)],
    '__gt__': [('__lt__', lambda self, other: other > self),
               ('__ge__', lambda self, other: not other > self),
               ('__le__', lambda self, other: not self > other)],
    '__ge__': [('__le__', lambda self, other: other >= self),
               ('__gt__', lambda self, other: not other >= self),
               ('__lt__', lambda self, other: not self >= other)]
}

Before moving on to something more challenging, look again at one of the recipe’s key ingredients, the convert dict, which helps create the missing ordering functions from existing ones. As you can see, there’s much repetition here, and plenty of opportunities for cut-and-paste errors.

This block of code is an example of what programmers term boilerplate. By using the total ordering decorator, we can avoid boilerplating our own code.^[1]

Filling in missing methods. C++

Python is dynamic and self-aware, happy to expose its internals for this kind of tinkering. It takes real wizardry to achieve similar results with a less flexible language, such as C++ — but it can be done.

In a previous article we developed a random access file iterator in C++. At its heart, this iterator simply repositioned itself using file-seeks and dereferenced itself using file-reads. There wasn’t much to it.

Unfortunately we had to fill-out the iterator with the various members required to make it comply with the standard random access iterator requirements (which was the whole point, since we wanted something we could use with standard binary search algorithms).

We had to expose standard typedefs:

typedef std::random_access_iterator_tag iterator_category;
typedef item value_type;
typedef std::streamoff difference_type;
typedef item * pointer;
typedef item & reference;

Worse, we had to implement a full set of comparison, iteration, step and access functions. Please, page down past the following code block! I only include it here so you can see how long it goes on for.

Iterator boilerplate

public: // Comparison
    bool operator<(iter const & other) const
    {
        return pos < other.pos;
    }
    
    bool operator>(iter const & other) const
    {
        return pos > other.pos;
    }
    
    bool operator==(iter const & other) const
    {
        return pos == other.pos;
    }
    
    bool operator!=(iter const & other) const
    {
        return pos != other.pos;
    }
    
public: // Iteration
    iter & operator++()
    {
        return *this += 1;
    }
    
    iter & operator--()
    {
        return *this -= 1;
    }
    
    iter operator++(int)
    {
        iter tmp(*this);
        ++(*this);
        return tmp;
    }
    
    iter operator--(int)
    {
        iter tmp(*this);
        --(*this);
        return tmp;
    }
    
public: // Step
    iter & operator+=(difference_type n)
    {
        advance(n);
        return *this;
    }
    
    iter & operator-=(difference_type n)
    {
        advance(-n);
        return *this;
    }
    
    iter operator+(difference_type n)
    {
        iter result(*this);
        return result += n;
    }
    
    iter operator-(difference_type n)
    {
        iter result(*this);
        return result -= n;
    }
    
public: // Distance
    difference_type operator-(iter & other)
    {
        return pos - other.pos;
    }
    
public: // Access
    value_type operator*()
    {
        return (*this)[0];
    }

value_type operator[](difference_type n)
    {
        std::streampos restore = getpos();
        advance(n);
        value_type const result = read();
        setpos(restore);
        return result;
    }
    ....

How tiresome! Most of these member functions are directly and unsurprisingly implemented in a standard way. It would be nice if we could write (and test!) what we actually needed to and have a decorator fill in the rest.

Enter Boost iterators

Actually, we can! I’m grateful to proggitor dzorz for telling me how.

A nicer solution would use boost::iterator_facade and just implement dereference, equal, increment, decrement, advance and distance_to.

Like many programmers I have mixed feelings about C++ — when it’s good it’s very very good, but when it’s bad it’s horrid — and these feelings are only amplified by the Boost library. Boost is superb, so long as you stick to the good parts.

So which parts are good? It depends. On you, who you work with, and the platforms you’re working on.

In my previous article I used an ingenious iterator adaptor from the Boost.Spirit parser library to disastrous effect. If only I’d looked a little more carefully I’d have discovered something more useful in a more obvious place. Boost.Iterator could have helped.

As dzorz points out, boost::iterator_facade can work with any C++ iterable. Implement whatever subset of

dereference
equal
increment
decrement
advance
distance_to

is appropriate and iterator_facade will fill in the boilerplate required to standardise your iterator.

In our case, we’ll need the full set. That’s because we’re after a random access iterator. Other iterators need rather less. Here’s a table showing the relationship between core operations and iterator concepts.

Using boost::iterator_facade

The Boost.Iterator documentation is well-written but daunting. Read it from top-to bottom and you’ll get:

rationale and theory
plans for standardisation (which don’t seem correct ^[2])
usage notes
some subtle points on the implementation and its predecessor
a namecheck for the curiously recurring template pattern
a fat reference section detailing the boilerplate which this library allows you to forget
a tutorial

If you’re tempted to skip to the end of the page, you’ll see this code block.

#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>
  
  ....
  
private:
  struct enabler {};
  
public:
  template <class OtherValue>
  node_iter(
      node_iter<OtherValue> const& other
    , typename boost::enable_if<
          boost::is_convertible<OtherValue*,Value*>
        , enabler
      >::type = enabler()
  )
    : m_node(other.m_node) {}

According to the surrounding documentation this is “magic”. I find it scary.

Luckily it turns out the library is straightforward to use. What you really want, as a newcomer, are the usage notes and the tutorial example.

The tutorial walks through the process of skinning a singly-linked list with a forwards iterator facade. This is a different use case to ours: the tutorial shows a basic class which implements what it should, and the facade allows it to be treated as a forwards iterator. In our case we’ve already created a full-blown random access iterator. We can retrospectively apply iterator_facade to strip our class back to basics.

Templates and Traits

Where we had:

template <typename item>
class text_file_iter
{
public: // Traits typedefs, which make this class usable with
        // algorithms which need a random access iterator.
    typedef std::random_access_iterator_tag iterator_category;
    typedef item value_type;
    typedef std::streamoff difference_type;
    typedef item * pointer;
    typedef item & reference;
....
};

We now need (my thanks here to Giuseppe for correcting the code I originally posted here):

template <typename value>
class text_file_iter
    : public boost::iterator_facade<
      text_file_iter<value>
    , value
    , std::random_access_iterator_tag
    , value
    , std::streamoff
    >
....
};

(Yes, the class accepts itself as a template parameter. That’s the curious recursion.)

Constructors, destructors and operators

We still need iterator constructors and destructors — these are unchanged — but we can eliminate every single operator shown in the “Iterator boilerplate” code block above.

Here’s what we need instead, to ensure iterator_facade can do its job. The read() member function we had before doesn’t need changing.

    ....
private: // Everything Boost's iterator facade needs
    friend class boost::iterator_core_access;
    
    value dereference() const
    {
        return read();
    }
    
    bool equal(iter const & other) const
    {
        return pos == other.pos;
    }
    
    void increment()
    {
        advance(1);
    }
    
    void decrement()
    {
        advance(-1);
    }
    
    void advance(std::streamoff n)
    {
        in.seekg(n, std::ios_base::cur);
        pos = in.tellg();
    }
    
    std::streamoff distance_to(iter const & other) const
    {
        return other.pos - pos;
    }

And that really is all there is to it. I’m impressed.

Notice, by the way, that friend is used to expose the primitive, private member functions for use by the boost::iterator_core_access class. This follows the example set by the tutorial. I’ve written enough C and Python to question C++’s sophisticated access rules — you have public, protected and private, but that’s still not enough, so you need friend declaration to cut through it all — which tempts me to simply make dereference(), equal() etc. public, but then the facade wouldn’t be a proper facade. Users should treat the final class exactly as they would any other random access iterator, and designating these members as private means they’ll have to.

Wrinkles

You’ll notice the dereference() member function has a const signature. However, the read() member function is non-const.

    // Return the item at the current position
    value_type read()
    {
        value_type n = 0;
        
        // Reverse till we hit whitespace or the start of the file
        while (in && !isspace(in.peek()))
        {
            in.unget();
        }
        in.clear();
        
        in >> n;
        return n;
    }

Here, in is a data member of type std::ifstream, and clearly the read call modifies it. That’s what this alarming compiler error is trying to tell us.

boost_binary_search_text_file.cpp: In member function 'value text_file_iter<value>::read() const [with value = long long int]':
boost_binary_search_text_file.cpp:90:   instantiated from 'value text_file_iter<value>::dereference() const [with value = long long int]'
/opt/local/include/boost/iterator/iterator_facade.hpp:516:   instantiated from 'static typename Facade::reference boost::iterator_core_access::dereference(const Facade&) [with Facade = text_file_iter<long long int>]'
/opt/local/include/boost/iterator/iterator_facade.hpp:634:   instantiated from 'Reference boost::iterator_facade<I, V, TC, R, D>::operator*() const [with Derived = text_file_iter<long long int>, Value = long long int, CategoryOrTraversal = boost::random_access_traversal_tag, Reference = long long int, Difference = long long int]'
/usr/include/c++/4.2.1/bits/stl_algo.h:4240:   instantiated from 'bool std::binary_search(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = text_file_iter<long long int>, _Tp = main::number]'
boost_binary_search_text_file.cpp:203:   instantiated from here
boost_binary_search_text_file.cpp:174: error: passing 'const std::basic_ifstream<char, std::char_traits<char> >' as 'this' argument of 'typename std::basic_istream<_CharT, _Traits>::int_type std::basic_istream<_CharT, _Traits>::peek() [with _CharT = char, _Traits = std::char_traits<char>]' discards qualifiers
boost_binary_search_text_file.cpp:176: error: passing 'const std::basic_ifstream<char, std::char_traits<char> >' as 'this' argument of 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::unget() [with _CharT = char, _Traits = std::char_traits<char>]' discards qualifiers
boost_binary_search_text_file.cpp:178: error: passing 'const std::basic_ifstream<char, std::char_traits<char> >' as 'this' argument of 'void std::basic_ios<_CharT, _Traits>::clear(std::_Ios_Iostate) [with _CharT = char, _Traits = std::char_traits<char>]' discards qualifiers
boost_binary_search_text_file.cpp:180: error: passing 'const std::basic_ifstream<char, std::char_traits<char> >' as 'this' argument of 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(long long int&) [with _CharT = char, _Traits = std::char_traits<char>]' discards qualifiers

Related to this, the Reference template parameter (shown in bold in the listing below) is actually a value, rather than the (default) value &. As we originally implemented it, our file iterator reads values lazily, only when clients request them. We have no reference to return.

template <typename value>
class text_file_iter
    : public boost::iterator_facade<
      text_file_iter<value>
    , value
    , std::random_access_iterator_tag
    , value
    , std::streamoff
    >
};

I faced a dilemma here. Either I could modify my original file iterator, including a current value data member, which I would take care to update every time we repositioned the file read position. Then our references could be real references and read() would naturally be const, simply returning a reference to this member. Or, I could make the in input stream data member mutable.

Mutable makes me uneasy for the same reason that friend does — if you can shake off the rigours of const-correctness so easily, then why bother with it? — and for this reason the first option appealed. However, a read-only file is an unusual container: we do not change it, but we cannot supply const references to its elements without reading them in, and that will mean changes to the file input stream. The easier option, involving the smallest code change, was to make in mutable. So that’s what I did.

Less code, more software

By employing two of my least favourite C++ keywords I now had a class which provided the functions it should, and, thanks to the magic worked by Boost’s iterator facade, I also had a class which I could use as a standard random access iterator. Most of the code changes were the deletion of boilerplate — very satisfying. I added code too, since I decided to invest a little more effort in tests. I didn’t have any doubts about the Boost library’s correctness but I thought I might not have been using it correctly. Happily these tests all passed.

Performance

Let’s not forget why we originally wanted a random access file iterator: we had a large sorted file, too large to read into memory, and we wanted to test for the presence of the number in this file.

For test purposes I created a file just over 4GB in size. A simple linear search through this file took around 180 seconds on my (aging laptop) computer, and was light on memory use. By creating a random access file iterator, boilerplate and all, we took advantage of the standard binary search algorithm and reduced the time to around 4 milliseconds.

How would our version using Boost iterator facade do? I wasn’t expecting it to be faster than the original, but I wouldn’t have been surprised if it gave it a close run: using Boost doesn’t usually involve compromise. In fact, over repeated runs of my performance tests there was no significant difference between the two iterator versions — or at least there wasn’t once a helpful reader had discovered and fixed a bug in my program, which was causing it to run correctly but slowly.

To trust a facade I guess you need some knowledge of what lies behind it.

Note: During my original performance tests, reported in the first version of this article, the Boost iterator performed woefully, far slower even than a linear search. By this time I’d lost patience, and it was left up to a reader, Giuseppe, to point out my mistake. I’d been using a boost::random_access_traversal_tag template parameter, with the result that std::distance() was using repeated increments rather than calling distance_to() to get an immediate result, and consequently ran very slowly. I should have used std::random_access_iterator_tag. I modified my code accordingly and confirmed that the Boost version does indeed perform on a par with the original version.

My thanks to Chris P for permission to use his photograph of the Library of Celsus at Ephesus, or at rather its beautiful facade. Ephesus is famous for the Temple of Artemis, one of the seven wonders of the ancient world, of which only fragments remain. Thanks too to Dave Hamster for the boilerplate photo — actually a detail from the hull of the SS Great Britain.

If you’d like to continue this experiment the code and the tests I used are available via anonymous SVN access from http://svn.wordaligned.org/svn/etc/search_text_file.

[1]: As of Python 2.7 and 3.2, the standard library will include a version of this recipe. It’s in the functools module. For some reason, your class “should supply an __eq__()” method.

[2]: According to the Boost.Iterator documentation:

Both iterator_facade and iterator_adaptor as well as many of the specialized adaptors mentioned below have been proposed for standardization, and accepted into the first C++ technical report; see our [Standard Proposal For Iterator Facade and Adaptor (PDF)][tr1proposal] for more details.

I assumed this meant there’d be tr1::iterator_(facade|adaptor) classes, but I don’t think that’s the case. Unlike other (good) bits of Boost, the Iterator library doesn’t seem likely to be part of the next C++ release.

Word Aligned

Angle brackets hurt my eyes

“Solutions”

ACCU 2013

An Exploration of the Phenomenology of Software Development

Patience Sorted

Hosting for Life? TextDrive revived!

More adventures in C++

Singly Linked Lists in C++

C++ introduces … the linked list!

Remove_if for forward lists

Forward_list::remove_if()

Lessons from C++

Folded files and rainbow code

C++ Concurrency in Action

Python’s lesser known loop control

Two star programming

ACCU Bristol and Bath

Life goes on

Life on Canvas

Desktop preferences

Knuth visited, Brains Limited

Set.insert or set.add?

Get set, go!

How long is a string?

Define pedantic

Hiding iterator boilerplate behind a Boost facade

Contents