Coded Structure

Linux Laziness (or: editing text files made twice as easy)

2012-01-29T00:37:00.000Z

It's been far too long since I wrote anything on this blog, so I'm easing myself back into it with what I've found to be a nice shortcut over the last few months. It uses one of my favourite POSIX tricks - symlinks to executables, together with behaviour based on the original symlink's name - the 'zeroth' argument to the executable.

As someone who identifies fully - and then some - with this xkcd comic: The General Problem, I would really rather not have to type commands which require options. I like aliases, preferably one or two characters long, and I would prefer to write one long word than a short word with an option or two. The mental effort of typing a single word to do a specific action is exactly what I want.

Which leads me to the problem. Text files are great. I am (or was) regularly opening editors, making notes, and saving them somewhere random. The problem is that, like standards, there quickly become too many of them. Which one to use? How to keep track of them? The problem is that the action 'edit my notes file' has to be split into two: a 'verb' (edit), and an 'object' (that particular file). Now you might think I'm irredeemably lazy, but that's twice as many things to remember - or type - as I'd like. I could just add an alias to .bash_aliases, but that's no fun, and while I could have a bunch of them, if I wanted to do anything more complex, I'd be repeating myself too much. Laziness, remember? Got to solve 'The General Problem', and then never have to worry about the specifics ever again :-)

One of my fun projects many moons ago was about adding '--xml' options to ordinary posix commands (xmlcmd - because XML may have serious backing in the enterprise, but needs all the help it can get to make this 'the year of XML on the Linux desktop'), and in it I create symlinks from ~/bin/name-of-posix-command to a Python script which then looks up and runs the original command (using the Python which package), before encoding that command's output into XML to be returned to the user. So basically:

Symlinks in a path early in $PATH to a common script
Use of argv[0] / $0 in that script to know from which command it was called, and act accordingly.

(And which ls on all my computers still shows $HOME/bin/ls, even though I hardly ever use the --xml option - isn't transparency nice?)

Applying these techniques to the rather simpler - yet more useful - task of editing files, and jumping to the punchline, I have this in ~/bin/editfile:

#!/bin/bash
EDITFILE_DIR=~/Dropbox/editfile
mkdir -p $EDITFILE_DIR  # ensure this exists
TARGET_PATH=$EDITFILE_DIR/$(basename $0).txt

case $1 in
    '-a')
        # append command arguments to file and exit
        shift  # don't include the '-a'
        echo "$*" >> $TARGET_PATH
        ;;
    '-l')
        # list file and exit
        cat $TARGET_PATH
        ;;
    *)
        # Determine editor to use
        if [[ -n "${EDITOR}" ]] ; then
            EDIT=$EDITOR
        elif $(which gedit) ; then
            EDIT="gedit -b"  # default fallback if present
        else
            EDIT="vim"       # fallback if no gedit there
        fi

        # Edit it...
        $EDIT $TARGET_PATH
        ;;
esac

And this:


$ ls -l ~/bin
-rwxr-xr-x  1 ben  staff    714 28 Jan 23:55 editfile
lrwxr-xr-x  1 ben  staff      8 19 Dec 22:13 notes -> editfile
lrwxr-xr-x  1 ben  staff      8 19 Dec 22:50 report -> editfile
lrwxr-xr-x  1 ben  staff      8 19 Dec 22:50 todo -> editfile
lrwxr-xr-x  1 ben  staff      8 19 Dec 22:50 track -> editfile

This has been developed from the much simpler starting point which looked something like this:


#!/bin/bash
gedit ~/$(basename $0)

The result of this is that I can type 'notes' from anywhere on my system, and up will pop my editor with the notes file, which happens to be something on Dropbox, and therefore available on all my computers. I can add as many extra files for different purposes as I like, and they all act in the same way. The files themselves aren't tied into any particular system, and even have helpful '.txt' extensions on the 'actual' files. And since there's a single script behind all of these, they all inherit the 'extras', such as '-l' to list the file, and '-a' to add a line, and I can add extra features and commands, and only have to do it once.

But the main point of all of this is that I've turned a verb + object into a more specific verb, and as long as the first verb is something like 'edit this text file', then I've solved The General Problem too. It might have taken a while longer than 'alias notes="vim ~/Dropbox/editfile/notes.txt"', but that wouldn't have been half as fun. And if you haven't looked at the xkcd comic I linked to earlier, you should now... :-)

I feel the need for a 'today' action, and while I'm at it I should add a todo:


$ (cd ~/bin; ln -s editfile today)
$ todo -a blog post about recently released pylibftdi 0.9

HTTP or it doesn't exist.

2011-07-18T23:35:00.002+01:00

This is my 'or it doesn't exist' blog post[1][2][3]. I think everyone should have one ;-)

A big chunk of my life is processing electronic information. Since I would like it to be a (slightly) smaller chunk of my life, I want to automate as much as possible. Now ideally, I don't want a massive disconnect between what I have to do as a human processor of information and what I need to tell a computer to do to do that job done without my help. Because it's easier that way.

So when I hear that the information I need to process is in some spreadsheet or other on a Windows share, it makes me a little sad. When I hear that it is available via a sensible REST interface in a sensible format, my heart leaps for joy just a little.

With something like Python's standard library (and third-party package) support for HTTP (requests), XML (ElementTree) and JSON, I should be able to get my computer to do most of the manual data processing tasks which involve 'documents' of some form or other.

In a previous job I worked at convincing anyone who would listen that 'XML over HTTP' was the best thing since sliced bread. With appropriate XSLT and CSS links, the same data source (i.e. URI) could be happily consumed by both man and machine. Admittedly most of the information was highly structured data - wire protocols and the like, but it still needed to be understandable by real people and real programs.

I'm not an XML expert, but I think I 'get' it. I never understood why it needed so much baggage though, and can't say I'm sad that the whole web services thing seems to be quietly drifting into the background - though maybe it was always trying to.

A lot changes in web technology in a short time, and XML is no longer 'cool', so I won't be quite as passionate about 'XML over HTTP' as I once was. For short fragments it is far more verbose than JSON, though I'd argue that for longer documents, XML's added expressiveness makes the verbosity worth it. Maybe it was ever thus, but whenever two technologies have even the slightest overlap, there seems to be a territorial defensiveness which makes the thought of using both in one project seem somewhat radical. So while I've used JSON much more than XML in the last couple of years, I've not turned against it. If done right (Apple, what were you thinking with plist files!?) - it is great. Compared to JSON-like representations, the ability to have attributes for every node in the tree is a whole new dimension in making a data source more awesome or usable (or terribly broken and rubbish). I've seen too many XML documents where either everything is an attribute or nothing is, but it's not exactly rocket science.

Things I liked about XML:

Simplicity: I like to think I could write a parser for XML 1.0 without too much effort. If it's not well formed, stop. Except for trivial whitespace normalisation etc, there is a one-to-one mapping of structure to serialisation. Compare that with the mess of HTML parsers. While HTML5 might now specify how errored documents should be parsed (i.e. what the resulting DOM should be), I suspect that a HTML5 -> DOM parser is a far more complex beast.
Names! Sensible Names!: Because HTML is limited in its domain, it has a fixed (though growing thanks to the living standard[4] which is HTML) set of tags. When another domain is imposed on top of that, the class attribute tends to get pressed into service in a ugly and overloaded way. By allowing top-level tags to be domain-specific, we can make the document abstraction more 'square'[5].
Attributes: Attributes allow metadata to be attached to document nodes. Just as a lower-level language is fully capable of creating a solution to any given problem, having 'zero mental cost' abstractions (such as the data structures provided by high-level languages) enables new ways of thinking about problems. In the same way, having attributes on data nodes doesn't give us anything we couldn't implement without them, but it provides another abstraction which I've found invaluable and missed when using or creating JSON data sources.

What does make me slightly(!) sad though is the practical demise of XHTML and any priority that browsers might give to processing XML. There is now a many-to-one mapping of markup to DOM, and pre HTML5 (and still in practice for the foreseeable future considering browser idiosyncrasies and bugs) - a many-to-many mapping. It wouldn't surprise me if XSLT transform support eventually disappeared from browsers.

Maybe there's a bit of elitism here - if you can't code well-formed markup and some decent XSLT (preferably with lots of convoluted functional programming thrown in) - then frankly 'get of my lawn!'. I love the new features in HTML(5), but part of me wishes that there was an implied background 'X' unquestionably preceding that, for all things. The success of the web is that it broke out of that mould. But in doing that it has compromised the formalisms which machines demand and require. Is the dream of the machine-readable semantic web getting further away - even as cool and accessible (and standards compliant - at last) web content finally looks like it might possibly start to achieve its goal? Is it too much (and too late) to dream of 'data' (rather than ramblings like this one) being available in the same form for both the human viewer and the computer automaton?

I'm prepared to be realistic and accept where we've come to. It's not all bad, and the speed with which technology is changing has never been faster. It's an exciting time to wield electronic information, and we've got the tools to move forward from inaccessible files stored on closed, disconnected systems. So where I used to say 'XML over HTTP', my new mantra shall now be 'HTTP or it doesn't exist'. At least for a while.

Bugs: they hide where you're not looking

2011-06-05T22:51:00.000+01:00

I bought a new Pogoplug over the weekend (only £50 new at PC World), and after being genuinely impressed by the Pogoplug software, decided it was far too easy and put PlugApps Linux on it. These 'plug' type devices are fairly amazing - cheap, very low power (measured mine at just under 4 watts, with only a single USB flash stick), but with a decent 1.2GHz ARM processor. I'm already thinking my next computer might be another 'plug.

After hacking for I while (why won't my printer work?), I decided to check whether my pylibftdi package worked on it. To my shock, a quick 'pacman -S libftdi; pip install pylibftdi', installed fine, and I could open a device connection to a FTDI device! But then things got worse. Trying to run examples/lcd.py failed with an exception in BitBangDevice, and I quickly realised that the API changes I'd done in 0.8 to make device access more 'file-like' had broken things in BitBangDriver. I was slightly sad that I'd released something where the examples didn't even work, and part of the whole reason the package might be useful to people (the abstraction over bit-bang device operation) was broken.

pylibftdi is fairly simple, and basically consists of Driver, Device, and BitBangDevice classes. Most of the interesting is in the Device class - so this is where I started when I finally got round to adding some tests for the 0.8 release. Having achieved reasonable coverage (though shamefully less than the 100% Uncle Bob demands), I considered my initial testing 'done'. I knew there was more to add later, and had (and still have) full intentions to 'get around to it'.

What I failed to anticipate has the unintended side-effect of writing tests. In the same way teachers might teach how to pass an exam rather than the depth and breadth of a subject, once tests exist, the purpose can simply be to pass them. Old manual acceptance tests get ignored as the 'old way' of doing things. Ideally of course this isn't a problem, because full test cases exist for every feature and code-path in the system, but that was very far from the case here. So somehow, my standard acceptance test (do the example programs still work) got omitted, in preference for 'there are tests now, so it must be better! And the tests pass!'

So beware - a little testing can be a dangerous thing. The bugs hide where you're not looking for them. This is great motivation for achieving full test coverage, for automating acceptance testing (as well as unit / component level testing) so far as possible, and for being humble when it comes to writing tests. My motivations for writing them in the first place were two-fold: the feeling it was 'what I should do', and the idea that at some future point when I added or refactored things later I could be confident I hadn't broken things. I had no thought that the software was already broken; that I needed tests.

Anyway, pylibftdi 0.8.1 is now out, with trivial but important fixes and lots more tests.

pylibftdi 0.8 released; testing, coverage, and mocking

2011-05-07T22:57:00.001+01:00

pylibftdi is a file-like wrapper to FTDI USB devices such as the UB232R (a USB<->serial converter) and the UM245R (8 bit parallel I/O).

No big changes for the 0.8 release, but a couple of new things:

ability to specify the device identifier in the Device([device_id]) constructor as either a serial number (as previously), or a device description. So can now specify Device('UB232R'), and the first attached UB232R device will be opened. The code initially tries to open by serial number, and if that fails will try to open by description, which I'm fairly confident will be useful rather than annoying :-)
more file-like API functions (flush, readline()/readlines()/writelines(), iterating over lines). These probably only make sense for text over serial lines, but that's a use-case worth supporting, considering pylibftdi already has unicode support.

As well as that, I finally got round to adding some tests, and discovered something wonderful: checking test coverage isn't just practical icing on the cake to make sure things are tested well, but is a powerful and effective motivation for writing tests. I'm using coverage, and have to say it's one of those things I wish I had got round to sooner.

Speaking of which, at some point I'll probably end up saying the same about Mock, which I've read around and know I should probably start using, but it's just so easy in Python to knock up something like this:


fn_log = []
class SimpleMock(object):
    """
    This is a simple mock plugin for fdll which logs any calls
    made through it to fn_log, which is currently rather ugly
    global state.
    """
    def __init__(self, name="<base>"):
        self.__name = name

    def __getattr__(self, key):
        # This makes me smile :)
        return self.__dict__.get(key, SimpleMock(key))

    def __call__(self, *o, **k):
        fn_log.append(self.__name)
        # most fdll calls return 0 for success
        return 0

def get_calls(fn):
    "return the called function names which the fdll mock object made"
    del fn_log[:]
    fn()
    return fn_log

Sometimes I think Python makes 'clever' things like that too easy, and is perhaps the reason that although in the Python language there is only-one-way-to-do-it, in the Python ecosystem there is perhaps a tendency to reinvent the wheel over and over again. Because it's easy - and it's fun.

As always code is at bitbucket. For the next release (0.9) I'm planning to add more tests and docs (which are rather scarce), as well as one or two of the other things I've got planned (possible D2XX support, or at least some notes on libftdi on Windows, more examples & protocol adapters, maybe even a web interface for 8 bit IO...)

piefull - a simple javascript & canvas visualisation tool

2011-04-18T22:56:00.001+01:00

OK, so calling piefull a visualisation tool is going a bit over the top, but it is a tool, and it does help with visualisation. It does one thing and one thing only - plot pie-charts indicating a single value. And it's even more restricted than that - the value it plots needs to be a percentage value.

The main use cases for this are things like task completion status (project and outliner applications, test coverage, etc) or resource allocation (disk space, CPU usage).

By choosing contrasting colours (these are configurable in piefull), the the overall outlook can be ascertained by a glance from a distance. By default the charts it generates are fairly small - 24px - which allows them to be used in-line in text, or as entries in tables. The general approach is derived from the sparklines example given in David Flanagan's Canvas Pocket Reference - replacing some textual data with a pictorial equivalent in the hope(!) it will be more quickly understandable. Of course this approach also lends itself well to graceful degradation, as the data is already there in the document itself.

There are plenty of other pie-chart generators - after all it's a fairly trivial thing to write with HTML5 canvas elements. But most of these tend to be fairly complex, with lots of options. I needed something where a fixed size display could represent a single value clearly, and piefull is the result.

Basically piefull turns this:

10%	20%	33%	20%	10%
18%	55%	33%	23%	12%
14%	35%	40%	21%	11%
12%	29%	14%	11%	5%
12%	17%	10%	9%	5%

(which looks like this in code:)


<table class="piefull">
    <tr>
       <td><div>10%</div></td>
       ...
       <td><div>5%</div></td>
    </tr>
</table>

into this:

10%	20%	33%	20%	10%
18%	55%	33%	23%	12%
14%	35%	40%	21%	11%
12%	29%	14%	11%	5%
12%	17%	10%	9%	5%

by doing this:


<script>
  window.onload = (function() { piefull.main("table.piefull td div"); });
</script>

where 'table.piefull td div' is a selector passed to querySelectorAll() to locate elements which will be replaced by little canvas piecharts. The contents of the selected elements are matched against a regular expression looking for a percentage value to extract (generally speaking, the first number), and the element is replaced with a canvas element displaying that value. The classes and id of the original element are preserved in the new element, allowing sensible CSS styling, and the canvas title takes on the text which it has replaced. As well as the selector, there are a (small) number of other parameters - size, 'yes' and 'no' colours. A value of e.g. 10 will display a 10% pie-segment in the 'yes' colour - the remainder will be the 'no' colour. (Like this: 10%.) These are all optional - even the selector defaults to '.piefull', which works great for a small number of spans or divs in some prose:

In other news, at least 66% of statistics are made up. No, wait - it should be a little higher now.

Note: If you're viewing this on IE8 or below, this probably makes no sense, as I've not included excanvas here. It is supported for IE8 with excanvas (but not less than IE8). One gotcha with IE is that block-level elements such as canvas don't work inside <p> elements. But you know you want to get a better browser... And why not get one with webgl support while you're at it?

The code for piefull can be found here

xmlcmd: adding an --xml option, one command at a time

2011-04-06T23:37:00.001+01:00

In my last post, I wrote some thoughts on how using the text based meta-language[1] of regular expressions to filter and manipulate structured data from UNIX commands was not fully exploiting the jigsaw-puzzle approach of 'the unix philosophy'[2], and that XPath (and by implication XML) provided an alternative where structured data on the command line was concerned.[3]

I also mentioned how great things could be if, like subversion, every POSIX command line tool had an --xml switch which could output XML. (There are many programs with XML output, but the main POSIX ones[4] don't have this as an option)

Here's one I made earlier

I was always aware of the danger of overstating the case, but sometimes that can be helpful. Or at least fun. And I'd already started prototyping something which looked fun, dangerous, and potentially useful. This is intended to be illustrative rather than a serious suggestion, but there might be many other cases where the concepts can be used more seriously.

1. Add a path

There isn't any magic to what we're doing in adding --xml options, and we're not touching the original programs. We're just using the fact that the PATH in POSIX operating systems contains an ordered list of entries, and we're simply inserting a 'hook' early on in the path which can catch and redirect certain formats of command, while transparently forwarding others.

I tend to have a ~/bin directory on my path anyway (keeping good care that it is only writable by myself) - so I'm already set, but if not, you'll need a directory which appears first on the PATH.


ben$ mkdir -p ~/bin

add that path to the start of your login path (e.g. in .bashrc or .bash_profile):


export PATH=$HOME/bin:$PATH

Once that is done, anything in that directory will be run in preference to anything else. Put an 'ls' file in there something like the following:


#!/usr/bin/env python
print("These are not the files you're looking for")

make it executable (chmod +x ~/bin/ls) and you won't be able to run 'ls' anymore. Except you are running it, it's just a different ls, and not doing anything particularly helpful. You can always run the original ls with a fully specified path (or try using $(whereis ls)).

Two more things make this potentially useful:

Finding the next program on the PATH, which would have been run if something else hadn't sneaked in first
Selectively running either this 'original' program or some different code based on relevant criteria (e.g. existence of --xml in the command line options)

and the following makes things practical:

Making the two things above easily reusable for any command.

2. The magic of args[0]

Most of the time most programs ignore args[0] - the program's own name. But what if args[0] could be treated as a command line option, just like all the others? What makes this possible is having multiple symbolic links to a single program. args[0] is then the name of the original symlink by which the process was called, so although the same program is ultimately running, it can determine in what way it was called. It can therefore change its own operation. This technique is used in the busybox project to implement a generous number of commands in a single executable.

3. Introducing xmlcmd

xmlcmd is a Python package which supports this terrible corruption of POSIX as it should always be. The main xmlcmd module code is fairly straightforward, and is shown below. This finds the original program (which would have been run if we weren't first on the path), and then either execs that (if no --xml option is provided), or runs some Python code in an dynamically imported Python module (_xyz from the xmlcmd package, where xyz is the 'original' command name) if --xml is present.


#!/usr/bin/python
"""
xmlcmd.py - support for adding an --xml option to various commands

Ben Bass 2011. (Public Domain)
"""

import sys
import os
import which  # from PyPI 'which' package

def process_cmd(cmd_name, args, orig_cmd_path):
    """
    import and call the main() function from the module
    xmlcmd._{cmd}
    """
    module = __import__('xmlcmd._%s' % cmd_name,
                        fromlist=['_%s' % cmd_name])
    raise SystemExit(module.main(args, orig_cmd_path))

def main(args=None):
    """
    run system command from sys.argv[:], where sys.argv[0]
    implies the real command to run (e.g. via symlinks to us)
    """
    if args is None:
        args = sys.argv

    # args[0] will be a full path - we only want the command name
    cmd_name = os.path.basename(args[0])
    if cmd_name.startswith('xmlcmd'):
        raise SystemExit('xmlcmd should not be called directly')

    # get the command which would have run if we hadn't sneaked
    # ahead of it in the $PATH
    cmd_path_gen = which.whichgen(cmd_name)
    cmd_path_gen.next()   # skip first match (us)
    orig_cmd_path = cmd_path_gen.next()

    if '--xml' in args:
        args.remove('--xml')
        # forward to our xmlized version...
        process_cmd(cmd_name, args, orig_cmd_path)
    else:
        # execv *replaces* this process, so it has no idea it
        # wasn't called directly. Total transparency.
        os.execv(orig_cmd_path, args)

if __name__ == '__main__':
    main()

4. The implementations

The real work is all handled in the _{cmd} modules of course, so admittedly we've really only moved the problem around a bit. But the point of this exercise is about the ease with which we can add these new entry points into existing systems. Nothing slows down in any noticeable way, and it would be easy to extend an entire class of commands, one at a time, by nothing more than adding a Python module and creating a symlink.

For reference, the main() function from _ls.py looks something like this:


def main(args=None, orig_cmd_path=None):
    """very basic xml directory listing"""
    if len(args) > 1:
        target_dir = args[-1]
        if not os.path.isdir(target_dir):
            raise SystemExit('%s is not a directory' % (target_dir,))
    else:
        target_dir = os.getcwd()

    root = ET.Element('directory', name=target_dir)
    for fn in os.listdir(target_dir):
        stat = os.stat(os.path.join(target_dir, fn))
        f_el = ET.SubElement(root, 'file', mtime=str(stat.st_mtime))
        ET.SubElement(f_el, 'name').text = fn
        ET.SubElement(f_el, 'size').text = str(stat.st_size)
    ET.ElementTree(root).write(sys.stdout, 'utf-8')
    sys.stdout.write('\n')

5. Example


ben$ sudo pip install which xmlcmd

(yup, it's on PyPI) will install the xmlcmd Python package (and the 'which' dependency), and an xmlcmd wrapper script which should end up on the path. With that done, you can now create the magic symlinks:


ben$ ln -sf $(which xmlcmd) ~/bin/ls
ben$ ln -sf $(which xmlcmd) ~/bin/ps

And now, assuming things are working properly (a quick hash -r/rehash can't hurt), you should now be able to do wonderful things like this:


ben$ ps --xml aux | xpath '//process/command/text()[../../cpu > 2.5]'

which in this case displays the command name of all processes currently taking more than 2.5% of the CPU. Sure the XPath isn't exactly elegant. But the point is that patterns of this micro-language would be shared between tasks, and manipulating structured data on the UNIX command line would become as easy as text manipulation is now.

Here's some they made earlier...

Having said and done all that, a few searches later (for 'posix commands' in this case) brought up xmlsh.org, which seems to do some very similar things.

I also found (via [2]) xmltk, which at first glance seems to have beaten me to these ideas by about 9 years... :-)

Notes

[1]: 'Regular expressions are notations for describing patterns of text and, in effect, make up a special-purpose language for pattern matching.' Brian Kerninghan, Beautiful Code (ed. Andy Oram & Greg Wilson, O'Reilly Media Inc).
[2]: The Art of Unix Programming, Eric S. Raymond. Especially the 'Rule of Composition'; see Chapter 1. (Note this book also praises text of course...)
[3]: What a pointlessly long sentence.
[4]: POSIX 2 (Commands and Utilities) covers these, e.g. see reference here

XPath is to XML as regex is to text

2011-03-21T21:29:00.001Z

Anyone who has been a developer for a while gets familiar with regular expressions. They eat text for breakfast, and spit out desired answers. For all their cryptic terseness, they are at least in part reusable, and are based on only a handful (or two...) of rules. 'regexes' are a domain-specific micro-language for searching and filtering text.

But once we get outside of text, what is there?

With XML, we have XPath. I had one of those light-bulb realisations recently that what regexes are to text, XPath is to XML. And it made me think:

Why would I want to use a data substrate which doesn't have such a tool?

What I mean is this; text has regex. XML has XPath. RDBMS have SQL. Markup language of the day has... oh, it doesn't. Not really, in the sense of a standardised domain-specific micro-language. Regular expressions, XPath and SQL have history and mindshare. They 'work' specifically because they are DSLs, rather than high-level code. (OK, SQL is pushing it further than I'd like here, but it's still a DSL. Just not a micro-sized one.) To me, this is a problem which many 'NoSQL' tools have. I want the features of them, but CouchDB wants me to write map-reduce functions in JavaScript. MongoDB wants me to use a JSON-based query language. There is no commonality; no reuse; no lingua franca which will let me abstract the processing concepts away from the tools. Perhaps that will come in time for more data-representations (this seems to be an attempt for JSON, for example), but there is a significant barrier before such a tool gains widespread acceptance as a common abstraction across an entire data layer.

Pipelines and Data Processing

The 'UNIX philosophy' of connecting together a number of single-purpose programs to accomplish larger tasks is one of the keys to its power. These tools can be plugged together in ways which the original creators may never have thought of. Tools such as sed and awk are often employed as regex-based filters to command pipelines. I wish more tools had XML output options, because the tools we use in our pipelines often output structured data in textual format, often in tabular form. Tables are great for human consumption (provided they are modest in size), but when we start getting empty columns, cells flowing onto multiple lines, and other inconsistencies, it becomes a pain to parse. How great things could be if every tool following subversion's lead and had an --xml option:

svn diff -r $(svn log --stop-on-copy --xml | xpath -q -e '//log/logentry[last()]/@revision' | cut -d '"' -f 2):HEAD

(This command does a diff from a branch base to the most recent revision. It still does some basic text processing, because the end result of XPath expressions are still text nodes).

Just imagine if POSIX defined an XML schema for each relevant command, and mandated an --xml option. Life would be so much easier. In many environments, data is structured but we still represent it as text. The pipeline philosophy might be nice, but it isn't exploited to the full when we need to write convoluted awk scripts and inscrutable regular expressions (or worse, Perl ;) ) to try and untangle the structure from the text. Consider something straightforward like the output of 'mount' on a *nix box. On my Mac it looks like this:


ben$ mount
/dev/disk0s2 on / (hfs, local, journaled)
devfs on /dev (devfs, local, nobrowse)
map -hosts on /net (autofs, nosuid, automounted, nobrowse)
map auto_home on /home (autofs, automounted, nobrowse)
/dev/disk1s1 on /Volumes/My Book (msdos, local, nodev, nosuid, noowners)

This is structured data, but getting the information out of that text blob would not be trivial, and would probably take many minutes of trial and error with regexes to get something reasonable. And the crucial thing is that you couldn't be sure it would always work. Plug a new device in which gets mounted in some new and interesting way, and who is to say that the new output of mount won't suddenly break your hand-crafted regex? That's where XML shines. Adding new information doesn't change anything in the old information. The way to access it doesn't change. Nothing breaks in the face of extension. Compare this to something like CSV, where the insertion of an extra column means all the indices from that column onwards need to change in every producer and consumer of the data.

XML and the Web

I'm somewhat saddened that XHTML didn't win outright in the last decade, and that XML on the web never really took off. I spent months at a previous job trying to convince everyone that 'XML-over-HTTP' was the best thing since sliced bread. A single source of data, which could be consumed by man (via XSLT & CSS in the browser) and machine alike. Just think how much energy the likes of Google could save if our web content didn't focus almost entirely on human consumption and discriminate against machines ;-)

One interesting thing which has happened as XML-on-the-web has declined is the increase in use of CSS selectors, first via frameworks such as Sizzle (used in jQuery), and later in the standard querySelectorAll DOM method. There is clearly a need for these DSL micro-languages, and as the 'CSS selector' DSL shows, they can quickly establish themselves if there is a clear need and sufficient backing from the community. Also apparent is that existing solutions can be usurped - users could do virtually everything CSS selectors could do (and far more besides) with XPath, but that didn't happen. Simplicity won here. But just because XPath was (arguably) wrong for Web development, doesn't mean it is wrong everywhere, and I contend that there are places where we have over-simplified, forcing regular expressions and text manipulation to (and beyond) breaking point, when XML processing would make things simpler everywhere.

Conclusion

In terms of practicalities, if I had ever spent too long in the world of Java, I would probably see XML as an unwelcome and persistent pest. But living in the happier climes of Python-ville, I have access to the wonderful ElementTree API, via both ElementTree itself (included in the standard library) and lxml.

Both of these support XPath as well as high-level abstractions of XML documents to and from lists and dictionaries. With ElementTree, XML access from Python is (almost) as easy as JSON access from JavaScript. And with technologies like XPath and XSLT available, I think it's worth it.

As a final thought, I've just had a quick glance through Greg Wilson's excellent Data Crunching, which contains chapters on Text, Regular Expressions, Binary data (rather a short ad-hoc chapter), XML, and Relational Databases. Perhaps the 'binary data' chapter is short because there simply aren't many patterns available. There is no language to describe unabstracted data. And perhaps when we consider the data layer we should be using, we should think not only of features and performance, but also the power, expressiveness, and concision of the languages available to reason about the information. Perhaps too often we settle for a lowest common denominator solution (text) when a higher level one might be more powerful, especially if we don't have to give up on the concepts of fine-grained interoperability which micro-DSLs such as XPath give us.

To be continued...

Concurrent Queue.get() with timeouts eats CPU

2011-02-20T00:16:00.000Z

...or how adding a timeout can make your program suffer

Call me lazy, but I like threads. Or at least I like the programming model they provide. I very rarely use explicit locks, and find the combination of threads and queues a great mental abstraction of parallel processing. Often though, the abstraction is so leaky that it gets me annoyed. Here is a case in point...

I noticed this problem in a Python process which sits in a loop doing readline() on a file object and dispatching the incoming lines to different worker threads to do some various asynchronous actions. With no input on the source file, the process was still taking 5% CPU. I would have expected next-to-nothing, since everything should have been blocking.

strace -fc -p $PID showed that the process was anything but idle though, and after further investigation, I found the culprit.

Concurrent Queue.get() with timeouts eats CPU.

A test case for this is the following Python (2 & 3) code. It intentionally doesn't do anything, simply starting WORKER threads, each of which performs a blocking Queue.get. The main thread simply waits for a newline on stdin. I wouldn't expect this to take any significant CPU time - in theory all the threads are blocked - either waiting on stdin input, or on something to be available in the various worker queues (which nothing ever gets sent to).


import threading, sys, time
try: import queue
except ImportError: import Queue as queue

WORKERS = 100

class Worker(threading.Thread):
    def __init__(self):
        self.queue = queue.Queue()
        threading.Thread.__init__(self)
        self.daemon = True

    def run(self):
        while True:
            next_item = self.queue.get()
            print(next_item)

def test():
    w_set = set()
    for i in range(WORKERS):
        new_w = Worker()
        new_w.start()
        w_set.add(new_w)

    print('Running: Press Enter to finish')
    sys.stdin.readline()

if __name__ == '__main__':
    test()

Sure enough, running and monitoring this shows 0% CPU usage, but WORKER+1 threads in use (I'm using OS X's Activity Monitor at the moment).

But let's suppose we want to change the worker threads to wake up occasionally to do some background activity. No problem: provide a timeout on the Queue.get():


class TimeoutWorker(Worker):
    def run(self):
        while True:
            try:
                next_item = self.queue.get(timeout=1)
            except queue.Empty:
                # do whatever background check needs doing
                pass
            else:
                print(next_item)

OK, so now the threads can wake up occasionally and perform whatever activity they want.

Except...

CPU usage just went up from ~0% to 10%. Increasing WORKERS shows that the CPU load of this program which still does nothing (the queues never get anything put in them) is proportional to the number of threads (95% at 1000 worker threads). I'm not inclined to look further than assuming this is some artifact of the GIL (pthread activity seems to be the culprit).

This is fairly independent of the length of the timeout. For very short timeouts, I'd expect CPU usage to go up, as the worker thread is spending more time doing work rather than being blocked. But there is no noticeable difference between timeout=10 and timeout=sys.maxint. In the latter case, the get() is never plausibly going to timeout, but the same high-CPU behaviour still occurs.

Fixing the code

I'm not inclined to delve deep into CPython to look at what Queue.get() is doing under the hood. It's clearly something very different depending on whether it has a timeout or not. For now I'm content to fix the code to eliminate the situations where these problems can occur. Hopefully the fact that I've written this will keep me aware of this potential issue and I'll manage to avoid it in future :)

The code where I found this issue was using a 1 second timeout to continually check the while condition and exit if required. This was easily fixed with sending a poison-pill of None into the queue rather than setting a flag on the thread instance, and checking for this once we've got a next_item. This is cleaner anyway, allowing immediate thread termination and the use of timeout-less get(). For more complex cases where some background activity is required in the worker threads, it might make more sense to keep all threads using timeout-less Queue.get()s and have a separate thread sending sentinel values into each queue according to some schedule, which cause the background activity to be run.

Conclusion

It seems fairly unintuitive that simply adding a timeout to a Queue.get() can totally change the CPU characteristics of a multi-threaded program. Perhaps this could be documented and explained. But then in CPython it seems many threading issues are entirely unintuitive. The scientific part of my brain won't stop thinking threads are wonderful, but the engineering part is becoming increasingly sceptical about threads and enamoured with coroutines, especially with PEP 380 on the horizon.

pylibftdi 0.7 - multiple device support

2011-02-09T22:42:00.000Z

pylibftdi has always been about minimalism, which means that if you wanted to do something it didn't support, things got tricky. One of it's glaring deficiencies until now was that it only supported a single FTDI device - if you had multiple devices plugged in, it would pick one - seemingly - at random.

With pylibftdi 0.7, that has finally changed, and devices can now be opened by name. Or at least by serial number, which is nearly as good. A new example script (which I've just remembered is hideously raw and lacks any tidying up at all) examples/list_devices.py in the source distribution will enumerate the attached devices, displaying the manufacturer (which should be FTDI in all cases), description, and serial number.

The API has changed slightly to cope with this; whereas previously there was just a single Driver class, now the primary interface is the Device class. Driver still exists, and holds the CDLL reference, as well as supporting device enumeration and providing backwards compatibility.

(As an aside, using ftdi_usb_find_all was (not) fun - it sets a pointer to pointer which is then used to traverse a linked list. Trivial in C, an hour of frustration in ctypes. Anyway, I got there in the end).


>>> from pylibftdi import Device
>>> import time
>>> 
>>> # make some noise
>>> with Device('FTE4FFVQ', mode='b') as midi_dev:
...     midi_dev.baudrate = 31250
...     for count in range(3):
...         midi_dev.write(b'\x90\x3f\x7f')
...         time.sleep(0.5)
...         midi_dev.write(b'\x90\x3f\x00')
...         time.sleep(0.25)
...

Both Device() and BitBangDevice take device_id as the (optional) first parameter to select the target device. If porting from an earlier version, one of the first changes is probably to use named parameters for options when instantiating these classes. My intention is that device_id will always be the first parameter, but the order and number of subsequent parameters could change.

Another change is that Devices are now opened implicitly on instantiation unless told not to (see the docstrings). Previously the Driver class only opened automatically when used as a context manager. There is no harm in opening devices multiple times though - subsequent open()s have no effect.

I've also finally figured out that I need to set long_description in setup.py to get documentation to appear on the PyPI front page. After all, without docs, it doesn't exist.

It's only been a few days since 0.6, but I wanted to get this release out - I think it is a big improvement since 0.5, and It'll probably be a while till the next release. In the mean time, I'll try and get a vaguely useful example going - which will probably involve MIDI and an LCD...

pylibftdi 0.6 released: now with Python 3 goodness

2011-02-06T20:09:00.000Z

pylibftdi 0.6 has been out the door and onto PyPI for the last few days, but I'm only just getting round to blogging about it. It's basically some minor work for Python 3 compatibility - the same code now works on both Python 2 (2.6/2.7) and Python 3. This means support for Python 2.5 has been dropped (due to use of bytearray/bytes types). I can always add it back in if people shout.

Other than trivially fixing a print statement to be a function call, the main change required was the expected bytes/string issue. The driver also gains a couple of parameters; mode = 't' ('t':text, 'b':binary) and encoding = 'latin1'.

In binary mode (the default - so no user code changes are required for this release), read() and write() take and return instances of type bytes. For text mode, write() will take either bytes/bytearray, or a string which it will encode with the given driver encoding, and read() will return a string. I've set the default to be latin1 rather than using utf-8 as it is an equivalence mapping over the first 256 code points.

Coming soon...

I've started work on 0.7 - the main feature of which is support for multiple devices. I had a few problems getting the right ctypes incantations to follow the linked-list which ftdi_usb_find_all sets, but that's sorted now. The bigger issue is that it really needs a split between driver and device, which could cause the API to change. I'm thinking of various ways to keep existing code working, and will probably go for something like:

0.7 - set pylibftdi.SUPPORT_MULTIPLE to True to use new API / support multiple devices
0.8 - set pylibftdi.SUPPORT_MULTIPLE to False to use old API / only support a single device / get a deprecation warning
0.9 - SUPPORT_MULTIPLE no longer used; old API disappears.

So 0.7 is all about multiple device support, 0.8 will probably be support for Windows (supporting D2XX, for example), and 0.9 (or maybe just 1.0) will be a tidy-up / bug-fix / improve docs release. In parallel with all of this I'm writing some test code which will gradually bring this side of things up-to-standard. I'm not allowing myself to do a 1.0 release without decent testing & docs. All that will probably take a two months; I only get a couple of hours a week looking at this. But it could be sooner - or later.

pylibftdi 0.7 should be out in within a week or so, and I'll elaborate more then, hence the lack of any examples here. I'm on the case!

HTTP 'streaming' from Python generators

2010-12-31T17:28:00.000Z

One of the more annoying things about HTTP is that it wants to send things in complete chunks: you ask for an object with a particular URL, and some point later you get that object. There isn't a lot you can do (at least from JavaScript) until the complete resource has loaded.For more fine grained control, it's a bit annoying.

Of course web sockets will solve all of this (maybe) once the spec has gone through the mill a few more times. But in the mean-time there is often an impedance mismatch between how we'd like to be able to do things on the server-side and how we are forced to do them because of the way HTTP works.

The following is an example of one way to manage splitting things up. It allows Python generators to be used on the server side and sends an update to the client on every yield, with the client doing long-polling to get the data. This shouldn't be confused with CherryPy's support for yield streaming single responses back to the server (which is discouraged) - the yield functionality is hijacked for other purposes if the method decorator is applied. Also note that this is only of any help for clients which can use AJAX to repeatedly poll the generator.

Example

Let's suppose that we want to generate a large (or infinite) volume of data and send it to a web client. It could be a long text document served line-by-line. But let's use the sequence of prime numbers (because that's good enough for aliens). We want to send it to the client, and have it processed as it arrives. The principle is to use a generator on the server side rather than a basic request function, but wrap that in something which translates the generator into a sequence of responses, each serving one chunk of the response.

Server implementation using CherryPy - note the json_yield decorator.


import cherrypy

class PrimeGen(object):
    @cherrypy.expose
    def index(self):
        return INDEX_HTML # see below

    @cherrypy.expose
    @json_yield   # see below
    def prime(self):
        # this isn't supposed to be efficient.
        probe = 1
        while True:
           for i in range(2, probe):
               if probe % i == 0:
                   break
           else:
               yield probe
           probe += 2

cherrypy.quickstart(PrimeGen)

The thing which turns this generator into something usable with long-polling is the following 'json_yield' decorator.

Because we might want more than one such generator on the server (not to mention generator instances from multiple clients), we need a key - passed in from the client - which associates a particular client with the generator instance. This isn't really handled in this example, see the source file download at the end of the post for that.

The major win is that the client doesn't have to store a 'next-index' or anything else. State is stored implicitly in the Python generator on the server side. Both client and server code should be simpler. Of course this goes against REST principles, where one of the fundamental tenets is that state should be stored only on the Client. But there is a place for everything.


import functools
import json

def json_yield(fn):
    # each application of this decorator has its own id
    json_yield._fn_id += 1

    # put it into the local scope so our internal function
    # can use it properly
    fn_id = json_yield._fn_id

    @functools.wraps(fn)
    def _(self, key, *o, **k):
        """
        key should be unique to a session.
        Multiple overlapping calls with the same 
        key should not happen (will result in
        ValueError: generator already executing)
        """

        # create generator if it hasn't already been
        if (fn_id,key) not in json_yield._gen_dict:
            new_gen = fn(self, *o, **k)
            json_yield._gen_dict[(fn_id,key)] = new_gen

        # get next result from generator
        try:
           # get, assuming there is more.
           gen = json_yield._gen_dict[(fn_id, key)]
           content = gen.next()
           # send it
           return json.dumps({'state': 'ready',
                              'content':content})
        except StopIteration:
           # remove the generator object
           del json_yield._gen_dict[(fn_id,key)]
           # signal we are finished.
           return json.dumps({'state': 'done',
                              'content': None})
    return _
# some function data...
json_yield._gen_dict = {}
json_yield._fn_id = 0

The HTML to go with this is basic long-polling, and separating out the state from the content. Here I'm using jQuery:


INDEX_HTML = """
<html>
<head>
<script src="http://code.jquery.com/jquery-1.4.4.min.js">
</script>
<script>
$(function() {

  function update() {
    $.getJSON('/prime?key=1', {}, function(data) {
      if (data.state != 'done') {
        $('#status').text(data.content);
        //// alternative for appending:
        // $('#status').append($(''+data.content+'
'));
        setTimeout(update, 0);
      }
    });
  }

  update();
});
</script>
</head>
<body>
<div id="status"></div>
</body>
</html>
"""

Uses

The example above is contrived, but there are plenty of possibilities if the json_yield decorator is extended in a number of ways. Long running server side processes can send status information back to the client with minimal hassle. Client-side processing of large text documents can begin before they have finished downloading. One issue is that a chunk of the data should be semantically understandable. Using things like this on binary files or XML (where it is only valid once the root element is closed) won't have sensible results.

There are plenty of possibilities in extending this; the decorator could accumulate the content (rather than the client) and send the entire results up-to-now back, or (given finite memory) some portion of it using a length-limited deque. Additional meta-data (e.g. count of messages so far, or the session key) could be added to the JSON information sent to the client each poll.

Disclaimer: I've not done any research into how others do this, because coding is more fun than research. There are undoubtedly better ways of accomplishing similar goals. In particular there are issues with memory usage and timeouts which aren't handled with json_yield. Also note that the example is obviously silly - it would be much faster to compute the primes on the client.

Download Files

Compiling "Essential Mathematics for Games" sample code on Mac OSX 10.6 Snow Leopard

2010-12-16T22:27:00.000Z

Before getting into a spot of games programming I thought I would buy a book which covered a few of the relevant topics. Wanting something a bit deeper and not likely to be outdated in the too-near future, I plumped for Van Verth and Bishop's Essential Mathematics for Games and Interactive Applications: A Programmer's Guide[Amazon Associates link]. Seems fairly good so far, mainly because it establishes why a certain approach is most applicable, rather than just telling you 'the' way to do things.

Anyway, the point of this blog post is to share some minor modifications required to the code included on the CD (which seems not available on-line) to get it building on Mac OS X 10.6 (Snow Leopard). From the documentation it seems the code was tested against OS X 10.4 and 10.5. It fails to build out-of-the-CD on 10.6, and I didn't find any updates on the website (www.essentialmath.com), but perhaps in time that will get updated.

Required changes are:

in common/MakefileCommon, change lines 15-17 from:


ifeq ($(PLATFORM), OSX)
  CFLAGS_EXT = -fvisibility-inlines-hidden
endif


ifeq ($(PLATFORM), OSX)
  CFLAGS_EXT = -fvisibility-inlines-hidden -ffriend-injection
endif

change the equivalent line 12 CFLAGS_EXT setting in Examples/MakefileExamples in the same way, i.e. adding -ffriend-injection. Presumably this is a requirement of a more recent version of GCC in Snow Leopard.
In common/Graphics/OGL/IvRendererOGL.cpp line 204, remove the GLvoid in the InitGL definition, i.e. change from
```
int 
IvRendererOGL::InitGL(GLvoid)
```
to
```
int 
IvRendererOGL::InitGL()
```

To build it (this is all in the relevant README files, as is the basic requirement of having the Mac Developer tools - i.e. XCode - installed):


cd <root of directory structure>
chmod -R +w *  # only required once, files/directories copied from CD are read-only
pushd common
make PLATFORM=OSX
popd
pushd Examples
make PLATFORM=OSX
popd

And then the example executables are available under the relevant chapter/section directory as ./Example, e.g. Examples/Ch13-Simulation/Simulation-02-Integration/Example. Note some of the examples seem to segfault if not started from the working directory...

Anyway, hope this helps someone. Now, on to developing some games...!

pylibftdi updated to 0.5

2010-11-25T23:16:00.000Z

I've done some tidying up of pylibftdi, fixing a few bugs, refactored the pylibftdi package to contain several modules instead of everything dumped in a __init__.py file, and generally made it a bit cleaner. It even has docstrings for most things now, and a test or two!

pylibftdi is a simple interface to libftdi, which in turn allows accessing FTDI's range of USB parallel and serial chips. See here for more details, but very briefly, serial access is provided by a file-like (read/write) interface with a baudrate property, and parallel access is provided by a pair of properties - direction (data direction register) and port (data IO register).

I haven't yet added any more examples, hopefully I'll get round to that in the next week or so. I have been using it as a MIDI interface though, which is fun - I'll get an appropriate example of that out in the next version, together with some diagrams / photos etc.

BlogPress, iPod, website

2010-11-09T23:38:00.001Z

So this is the obligatory 'testing' post from BlogPress on my new-ish iPod touch 4th gen.

I wish the battery life was better, but the retina display is awesome for reading tiny text, making ebooks surprisingly practical. It's also far too easy to spend lots of money on the app store. One nice thing is that three fingered touch typing is just about doable in landscape mode - not a skill I anticipated learning!

I've been spending lots of time recently on my website codedstructure.net, and especially on a project for playing with / learning GLSL in the context of WebGL: WebGL Shader Lab, which I'll write more about next time.

If only iOS Safari supported WebGL...

- Posted using BlogPress from my iPod

dsPIC33 (and PIC18) programming on my EEEPC at last

2010-10-04T22:27:00.000+01:00

I've got an EEEPC 701, and although it is annoying in some ways (small screen, limited SSD space), it's great for portability. One of my goals when I got it was to be able to use it to help developing various microcontroller projects I've got on the go, and I especially like that it doesn't take up lots of space on my (tiny) desk when I'm hacking around. It works great with Arduino, but I prefer PICs to be honest. The issue with this is that Microchip (producers of PIC microcontrollers) want everyone to use MPLAB, which only works on Windows. And even if it worked on my Linux-based EEEPC, it probably wouldn't be too great on a 7 inch screen. Anyway, being born before 1980 (but not by much!) I still prefer command lines to IDEs anyway. My first development environment was debug.com on MS-DOS, and it's never been bettered :-)

At some point I'll get round to changing the OS (Linux Mint looks like the front runner at the mo...), but for now it's still got the Xandros stock install (though I've removed unionfs).

Rather than mess around with getting the (GCC based) Microchip tools compiled on the machine, I'm using wine - both C18 and C30 install and work without any problems.

For actually burning the image onto the controller, I use and the perfectly-working-without-lots-of-hassle pk2cmd and the brilliant PicKit2, (which was so successful Microchip went and broke it).

The following gives the commands I use to build and download the target .hex file - I've only got a single .c file (this one) for input at the moment, and haven't even got a makefile together yet. But getting this working took a couple of hours, so this is as much for reference as anything else...

#!/bin/bash

# exit on errors
set -e

C30_BASE=/home/user/.wine/drive_c/Program\ Files/Microchip/MPLAB\ C30/

echo "Building..."
wine "${C30_BASE}/bin/bin/pic30-coff-gcc.exe" -o dac_music.coff -mcpu=33fj64gp802 -Wl,--script "${C30_BASE}/support/dsPIC33F/gld/p33FJ64GP802.gld" DacMusic.c

echo "bin2hex..."
wine "${C30_BASE}/bin/bin/pic30-coff-bin2hex.exe" dac_music.coff

echo "burning..."
pk2cmd -Pdspic33fj64GP802 -Fdac_music.hex -Q -M -R -T

For reference, I've also got a similar setup for something on the PIC18. I've had this running from fairly soon after I got my EEEPC, and didn't have problems getting it up and running:

#!/bin/bash

# exit on errors
set -e

C18_BASE=/home/user/.wine/drive_c/MCC18

echo "Compiling..."
wine ${C18_BASE}/bin/mcc18-traditional.exe -ml -p=18f252 -k -Oi+ music.c

echo "Linking..."
wine ${C18_BASE}/bin/mplink.exe \\MCC18\\lkr\\18f252i.lkr /l\\MCC18\\lib /aINHX32 music.o

echo "burning..."
pk2cmd -P18f252 -Fa.hex -M -R -T

At some point I'll turn them into makefiles, but for now - I can program tiny microcontrollers with my almost-as-tiny EEEPC. Which is nice and cosy.

Some time soon I'll actually write a blog post or two about the projects I'm using this with - mostly synthesizers and other various things to do with MIDI.

Non-evil SEO?

2010-09-26T20:46:00.000+01:00

I've always thought SEO was evil (in the non-theological sense!), but this effort (via @rem) seems well worth supporting. According to my Facebook page my favourite quote is 'It is amazing what you can accomplish if you do not care who gets the credit' - so said Harry Truman. Perhaps amazing is overstating the goal, but maybe it could be paraphrased 'It is amazing what you can make Google do if it is actually helpful and not (directly) self-serving'. I guess we'll find out...

Announcing pylibftdi - a minimal Pythonic wrapper for libftdi

2010-09-19T22:45:00.000+01:00

The playing-around I've done with FTDI devices seemed like a good opportunity to actually release something as open source, and so I present 'pylibftdi'. Undoubtedly not the greatest, but right now most likely the latest FTDI-Python bridge in the rather large open source field.There are a few features I know I want to add to it (primarily support for multiple devices), but for a flavour of things:

Toggling an LED or other device from pin D0

from pylibftdi import BitBangDriver
import time

with BitBangDriver() as bb:
    while True:
        bb.port ^= 1
        time.sleep(0.5)

Sending a string to a serial terminal

from pylibftdi import Driver

with Driver() as drv:
    drv.baudrate = 19200
    drv.write('Hello World!')

It's been tested on Linux (Ubuntu 10.10) and Mac OS X (10.6), with libftdi 0.17 and 0.18, but doesn't have any intended platform specific requirements other than having the libftdi library installed.The following goals for this project differentiate it from similar projects:

Fully supported on Linux and Mac OS X, using Intra2net's open source libftdi driver.
Simple things are very simple, as the example above shows. The basic functionality is made as simple as possible to use, with properties and context managers used where it makes sense. Most other FTDI Python wrappers are 'just' low level bindings of the underlying API.
There will be an increasing library of examples showing interaction with various protocols and devices - note this is a goal, not yet an accomplishment, though there is an LCD example there.

pylibftdi is easy_installable (or equivalent) from PyPI, and the code is developed on bitbucket, where you can also raise tickets for problems and feature requests.

For reference, other similar projects include PyUSB, pyftdi, python-ftdi, and ftd2xx. There are probably others...

libftdi on Mac OS X

2010-08-30T20:10:00.003+01:00

Update 2011/02/02: In trying to port pylibftdi to Python3, I found that the libraries which get built following the instructions below are 64-bit. All well and good, but the Python3.1 installation on Mac OS X 10.6 is 32-bit only (unlike the Python2.6 install).

While it's possible to get both 32-bit and 64-bit universal libraries, I haven't tried that yet. The solution to built 32-bit libraries was to use the following:

CFLAGS="-arch i386" ./configure && make && sudo make install

(Note I omitted libusb and sudo (for make install) in previous instructions - I've updated below). I also found I needed to do:

export PKG_CONFIG_PATH=/usr/local/lib/pkgconfig/

prior to building libusb-compat - I can't remember if this was a problem or not the first time round. Anyway, hopefully I'll have pylibftdi working with Python3 soon.
End of Update

I've not written much about my ftdi projects recently, so here's an update.I've played around with reading values from an encoder and outputting to a RGB LED with PWM, but both of these require a fairly high constant poll rate (or in the case of reading the encoder, ideally interrupt-on-change). The jitter is quite annoying, and decent PWM seems tricky, even when following FTDI's instructions (pdf link) for maxmising the buffer size. There's always going to be a gap when one buffer has finished and the next starts.

On a different note, I'm now mostly using my new Mac mini, so I've spent a few moments getting things to work there. Prerequisites:

libusb (tested with version 1.0.8)
pkg-config (tested with version 0.25)
libusb-compat (test with version 0.1.3)
libftdi (tested with version 0.18)

These should be installed in the order listed; for each file, download it, untar it (tar -xf filename), then run './configure && make && sudo make install' in the new directory which tar has created.

On the Python side, there were a couple of issues when I tried to run the old code. First was that the library could not be found at all. This was due to the library extension (.so) being hardcoded. For a cross-platform solution, it seems the best way is to use the following:


from ctypes import *
from ctypes.util import find_library

dll = CDLL(find_library('ftdi'))

Rather than specifying 'libftdi.so', we have stripped off the 'lib' prefix and the .so extension. The simple 'ftdi' string would be used if we were linking this library with gcc using the -l flag. Try 'gcc -lftdi' and it should report only that it can't find _main, not that the library is missing (try gcc -lmadeupname and it should complain about being unable to find 'madeupname')

Once this was done, the program would some times run (especially under pdb, which lead me up the garden path of thinking it was a timing issue...), but other times would cause a segfault. This was tracked down to another hard-coded value - the size of the context structure.The following will report the size of the ftdi_context structure:


echo -e '#include \nint main(){return sizeof(struct ftdi_context);}' | gcc -xc - && (./a.out; echo $?)

This is somewhat fragile, as it will fail if the structure ever gets larger than 255 bytes, but this seems unlikely for the time being. On this Mac this gives 112 bytes; on my Linux boxes it gives 84 - though they are running on the previous (0.17) version of libftdi. There is also the issue that the Mac library is x86_64 (i.e. 64-bit), while the Linux libraries are 32-bit.

One solution, though not exactly a purist's, is to allocate far more memory than will be needed. It won't slow anything down, as only a pointer to the start of the block is passed around, and probably won't make a difference to the memory consumption as applications will always use whole numbers of pages (4KB minimum) anyway. So for now, an allocation of 1KB seems a good solution.

The result of this is that the changes needed to the earlier code for compatibility with both Mac OS X and Linux are as follows:


...

from ctypes.util import find_library

def ftdi_start():
    global ctx, fdll  # frown... :P
    fdll = CDLL(find_library('libftdi'))
    # size of ftdi_context varies
    # seen 112 (x86_64, v0.18). 84 (i386, v0.17)
    # over-allocate to 1KB.
    ctx = create_string_buffer(1024)
    fdll.ftdi_init(byref(ctx))
    fdll.ftdi_usb_open(byref(ctx), 0x0403, 0x6001)
    fdll.ftdi_set_bitmode(byref(ctx), 0xFF, 0x01)

...

Me loves os.name == 'posix' :-)

New website - codedstructure.net

2010-08-17T23:00:00.000+01:00

I've not got round to putting much on here for a while, but I have been busy, honest! I've finally got my own website after far too many years of not bothering: codedstructure.net.

I'm probably not the first to use scrolling like that, but I wasn't copying anyone and I think it's quite funky, especially the nice text shadows. Me likes the way web development is going, after years of shunning it...

Oh, and while I'm at it, I've got a twitter account, and hope to be churning out iPhone apps in the near future - though Objective C looks horribly like some terrible collision of Java and Smalltalk - in a bad way. Hope I can grow to like it.

A Python LCD status display

2010-06-16T22:44:00.000+01:00

This is the third in my series of blog posts about doing IO with FTDI's Async BitBang mode on the UM245R / UM232R eval boards, and this time we're actually going to do something useful - have an LCD update with interesting system information. The LCD in question is based on the ubiquitous HD44780 controller, which is interfaced to microcontrollers throughout the world...

Anyway, with only 8 IO lines on the UM2xxR boards, we need to use the 4bit interface mode (two extra IO lines are needed beyond the 'data' path - one to act as a 'data-ready' strobe, and the other to select between 'data' and 'commands'). The wiring up is basically DB0-DB3 on the FTDI device going to D4-D7 on the LCD, with DB6 on the FTDI going to the 'RS' (register select) line on the LCD, and DB7 to the 'E' strobe. If that makes no sense, then hopefully the photo makes things slightly clearer...

I've also got an LED backlight for my display, which makes it look a whole lot cooler :-)

I'll present the code in chunks and try to explain it as I go along. First the initialisation and shutdown code, which are fundamentally unchanged from the previous examples, though they are now in functions to make them just a little tidier. (Note there is still no error checking here...)

"""
Write a string (argv[1] if run from command line) to a HD44780
LCD module connected via a FTDI UM232R/245R module

example usage:

# while true;
>   do python lcd.py $( awk '{print $1}' /proc/loadavg);
>   sleep 5;
> done
"""

from ctypes import *
import time, sys

def ftdi_start():
    global ctx, fdll  # frown... :P
    fdll = CDLL('libftdi.so')
    ctx = create_string_buffer(84)
    fdll.ftdi_init(byref(ctx))
    fdll.ftdi_usb_open(byref(ctx), 0x0403, 0x6001)
    fdll.ftdi_set_bitmode(byref(ctx), 0xFF, 0x01)

def ftdi_end():
    fdll.ftdi_usb_close(byref(ctx))
    fdll.ftdi_deinit(byref(ctx))

The following class is an abstraction of a bus - a collection of one (probably two, technically...) or more electrical lines which should be treated as a single unit. The aim here is to be able to program in a similar style to the embedded programming on a microcontroller, where registers are typically memory mapped and writing to a bus is simply writing into a bitfield. The parameters of this abstraction are the width of the bus (in bits), and the offset from the LSB of the entire port being accessed. It also needs a reference to a driver which allows it to do the reading and writing to the port. By using this as a descriptor, we can define buses within classes representing the various devices we are using; in this case the LCD.

class Bus(object):
    """
    This class is a descriptor for a bus of a given width starting
    at a given offset (0 = LSB).  It needs a driver which does the
    actual reading and writing - see FtdiDriver below
    """
    def __init__(self, driver, offset, width=1):
        self.offset = offset
        self.width = width
        self._mask = ((1<<width)-1)
        self.driver = driver

    def __get__(self):
        val = self.driver.read()
        return (val >> offset) & self._mask

    def __set__(self, obj, value):
        value = value & self._mask
        # in a multi-threaded environment, would
        # want to ensure following was locked, eg
        # by acquiring a driver lock
        val = self.driver.latch()
        val &= ~(self._mask << self.offset)
        val |= value << self.offset
        self.driver.write(val)

The following is the driver which will be used to do the actual data access. Note the use of the latch to store the last value written to the port, which cannot generally be read from the device after having been written (Latch registers for the IO ports was a big advance for the PIC18F series over the earlier 16F series, which needed the application to store this separately in order to do read-modify-write operations properly on the IO ports).

class FtdiDriver(object):
    def __init__(self):
        self._latch = 0

    def read(self):
        z = c_byte()
        fdll.ftdi_read(byref(ctx), byref(z), 1)
        return z.value

    def latch(self):
        return self._latch

    def write(self, val):
        self._latch = val
        z = c_byte(val)
        fdll.ftdi_write_data(byref(ctx), byref(z), 1)
        # the following is a hack specifically to allow
        # me to ignore all the timing constraints of the
        # LCD.  For more advanced LCD usage, this wouldn't
        # be acceptable...
        time.sleep(0.005)

Now we've got a Bus class and a driver to use with it, we can define the LCD module interface. I'm not going to cover the details of the interface, but the wikipedia HD44780 page has some pointers.

# need to instantiate this in global context so LCD
# class can be defined. Could tidy this up...
ftdi_driver = FtdiDriver()

class LCD(object):
    """
    The UM232R/245R is wired to the LCD as follows:
       DB0..3 to LCD D4..D7 (pin 11..pin 14)
       DB6 to LCD 'RS' (pin 4)
       DB7 to LCD 'E' (pin 6)
    """
    data = Bus(ftdi_driver, 0, 4)
    rs = Bus(ftdi_driver, 6)
    e = Bus(ftdi_driver, 7)

    def init_four_bit(self):
        """
        set the LCD's 4 bit mode, since we only have
        8 data lines and need at least 2 to strobe
        data into the module and select between data
        and commands.
        """
        self.rs = 0
        self.data = 3
        self.e = 1; self.e = 0
        self.e = 1; self.e = 0
        self.e = 1; self.e = 0
        self.data = 2
        self.e = 1; self.e = 0

    def _write_raw(self, rs, x):
        # rs determines whether this is a command
        # or a data byte. Write the data as two
        # nibbles. Ahhh... nibbles. QBasic anyone?
        self.rs = rs
        self.data = x >> 4
        self.e = 1; self.e = 0
        self.data = x & 0x0F
        self.e = 1; self.e = 0

    def write_cmd(self, x):
        self._write_raw(0, x)

    def write_data(self, x):
        self._write_raw(1, x)

All that remains is to initialise the FTDI device, initialise the LCD module, and write some data to it.

def display(string):
    ftdi_start()

    lcd = LCD()
    lcd.init_four_bit()

    # 001xxxxx - function set
    lcd.write_cmd(0x20)
    # 00000001 - clear display
    lcd.write_cmd(0x01)
    # 000001xx - entry mode set
    # bit 1: inc(1)/dec(0)
    # bit 0: shift display
    lcd.write_cmd(0x06)
    # 00001xxx - display config
    # bit 2: display on
    # bit 1: display cursor
    # bit 0: blinking cursor
    lcd.write_cmd(0x0C)

    for i in string:
        lcd.write_data(ord(i))

    ftdi_end()


if __name__ == '__main__':
    # note blatant lack of error checking...
    display(sys.argv[1])

and there we have it; a slightly cumbersome but also slightly cool and slightly useful little display utility. In the spirit of UNIX programming, this only does one thing - display the command line argument on the LCD. Obviously it needs major error handling if robustness is required...

while true; do python lcd.py $( awk '{print $1}' /proc/loadavg); sleep 5; done

Mandelbrot Canvas...

2010-06-08T21:39:00.000+01:00

This Mandelbrot Plotter is something I worked on a little while ago. One of the things I want to do in any language I'm learning is know how to get a pixel on a page. A long time ago it was function 0Ch of INT 10h, then memory mapped displays, and now the wonderful ImageData object underlying HTML5's Canvas element. It's so much more fun displaying a picture than 'Hello World' in text...

I'm also fascinated by fractals, and the Mandelbrot set in particular (since I sort-of understand the maths behind it). It makes me wonder whether it is an invention or a discovery, and just why it is what it is - and whether other inscrutable patterns are just waiting to have some new visual representation cast a whole new light on them...

Of course with it being hosted (albeit slightly oddly on Blogger), I can now claim to have written a 'web app', for better or worse. Anyway, it's nice to be able to put random JavaScript up within Blogger...

Let there be LEDs

2010-05-27T21:29:00.000+01:00

"In the beginning, [...] God said 'let there be light'".

Some time later, Man discovered Gallium Arsenide, and eye-piercing LEDs have blighted us ever-since. (Although they used to be quite dim, actually). Nevertheless, the 'hello world' of the embedded world is to make an LED flash.

In part 1 I 'covered' installation and test of the libftdi module, but the program didn't actually do anything. The UM232R module is primarily a UART module (unlike the DLP USB245M, which is a FIFO), but as with most recent FTDI devices it supports a 'BitBang' mode. BitBang is embedded jargon for running a protocol at the digital bit level, specifying in firmware at what point each of the (potentially many) IO lines goes high or low.

To put these devices in to this mode, an API call is needed to the FTDI driver to establish this mode. The ftdi_set_bitmode function takes three parameters; the FTDI control context (by reference), a direction bitmap, and a mode indicator (which should be 1 for async bitbang mode). The interesting is the direction bitmap. For each of the 8 IO lines, the corresponding bit in this mask can be a '1' to indicate an output, or a '0' for an input. I'm starting with output, so...

if ((ret = ftdi_set_bitmode(&ftdic, 0xFF, 0x01)) < 0) {
        fprintf(stderr, "unable to set bitmode\n");
        return EXIT_FAILURE;
    }

(this fits into the 'DO STUFF HERE' part of the code from last time)

Once this is done, we can start writing things out to the data port.

unsigned char x = 0;
    while (1) {
        ftdi_write_data(&ftdic, &x, 1);
        x ^= 0xFF;      /* toggle all lines */
        usleep(100000)  /* pause for 100ms  */
    }

This is hackish - it never exits for a start - but it should enable an LED to flash!

In terms of wiring things up, the 'GND' pin needs to go to the shorter leg of the LED (the cathode), and a data line (it doesn't matter which in this example, use DB0 to be safe) goes to the longer lead (anode). A 1K resistor needs to be in either line to limit the current and prevent burning out the LED. As supplied, the jumpers on the UM232R/UM245R module configure it to be self powered. Anyway, it should look something like this, and the LED should be flashing at approx 5Hz.

To do anything more interesting, let's move to Python. This is where the fun begins - with ctypes. I remember the first time I used ctypes, using puts from the C standard library on a Solaris machine, and the fact that it just worked. Occasionally there is a need to write the equivalent of a function prototype, but most of the time things are incredibly easy.

First up: loading the shared library. Lets guess its name - libftdi.so?

[GCC 4.1.2 20061115 (prerelease) (Debian 4.1.1-20)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>>
>>> from ctypes import *
>>>
>>> fdll = CDLL('libftdi.so')
>>>
>>> fdll
<CDLL 'libftdi.so', handle 81da028 at b7cfd4ac>
>>>

So far so good :) Next thing is this ftdi_context struct which is referenced by each function in the C code. It starts as an unpopulated structure, and presumably the first functions (init and usb_open) set it up as required. While the D2XX interface just gives an integer handle, in libftdi we have to pass pointers to this structure around. So, how do we define this in ctypes?
First we need its size:

#include "ftdi.h"
#include "stdio.h"
int main()
{
    printf ("%d\n", sizeof(struct ftdi_context));
}

Now compile and run...

/home/user/ftdi> gcc get_size.c
/home/user/ftdi> ./a.out
84

So, we need 84 bytes of storage for this context. ctypes will do that for us:

>>> ftdic = create_string_buffer(84)

Done that. Now we can rattle it off: only two other things: first, where in C you give &var to give the address of a variable (e.g. as a parameter to a function taking *var), in Python with ctypes, it's byref(var). Second, to create a something which has existence in the C world, (e.g. so can have its address taken), there are a whole bunch of c_XXX functions - we'll use c_byte, which is equivalent to an unsigned char.

from ctypes import *

fdll = CDLL('libftdi.so')

ftdic = create_string_buffer(84)

fdll.ftdi_init(byref(ftdic))

fdll.ftdi_usb_open(byref(ftdic), 0x0403, 0x6001)

fdll.ftdi_set_bitmode(byref(ftdic), 0xFF, 0x01)

import time
x = c_byte(0)
try:
    while True:
        fdll.ftdi_write_data(byref(ftdic), byref(x), 1)
        time.sleep(0.1)
        x.value ^= 0xFF # toggle all bits
except KeyboardInterrupt:
    pass

fdll.ftdi_usb_close(byref(ftdic))

fdll.ftdi_deinit(byref(ftdic))

And we're done! It's surprising how easy it is to translate basic C code using libraries into Python using ctypes - normally it just works.

Next time we'll look at interfacing to an LCD module...

Should I teach my children machine code?

2010-05-20T08:11:00.000+01:00

I waited till primary school to read this book, but it seems that 'modern' kids can understand these things sooner - or at least Amazon thinks so...

The outside world...

2010-05-18T21:05:00.000+01:00

I'm going to do a series of blog posts on using FTDI devices to access the outside world. There are probably a dozen other similar series out there, so I hope I can introduce enough novelty to make it interesting

I've been interested in low-level programming for as long as I've been programming (anyone else remember this book? - yes, a "children's" book on Machine Code...)

In terms of 'physical computing', things like Arduino are really taking off at the moment, but I'm going to take a step back to the simplicity of simple digital IO based on the BitBang mode of FTDI's latest devices. There are two reasons for this: firstly it came seem laborious writing two sets of software (for both the host computer and the target micro-controller), and secondly that even if the eventual application is going to be a standalone micro based system, it is still generally quicker to prototype things using only the host computer, avoiding the cross-compile and firmware upload cycle.

Hardware-wise, I'm using a FTDI UM232R (Farnell link) device. (I've also used one of these, and this either will be usable) This is a DIL module which plugs nicely into a breadboard which can be used to interface with stuff. If you want to follow along, get a breadboard to plug it into, some LEDs, 1Kohm resistors, and some connecting wire (I like these, but they are waaay over priced). In a couple of posts I'll be using one of these (N26AZ), too...

On the software side, I'm using Linux on a EEEPC 701 (stock Xandros) with the libftdi drivers, compiled from source found here. The FTDI supplied drivers are similar and might be a better choice on Windows (not sure if libftdi works on Windows), but some of the function names and interfaces differ somewhat.

First step is getting the simple.c program compiled and working. The program outline - slightly edited for length - looks something like this.

/* see http://www.intra2net.com/en/developer/libftdi/documentation/ */ 
#include "stdio.h"
#include "ftdi.h"

int main(void)
{
    int ret;
    struct ftdi_context ftdic;
    if (ftdi_init(&ftdic) < 0) {
        return EXIT_FAILURE;
    }

    if ((ret = ftdi_usb_open(&ftdic, 0x0403, 0x6001)) < 0) {
        return EXIT_FAILURE;
    }

    /* DO STUFF HERE */

    if ((ret = ftdi_usb_close(&ftdic)) < 0) {
        return EXIT_FAILURE;
    }

    ftdi_deinit(&ftdic);

    return EXIT_SUCCESS;
}

Compiling this (gcc -o simple simple.c -lftdi) and running the resulting executable should not cause any errors, and should return a successful error code if a FTDI device is attached.

This post is getting long enough for now, so I'll leave it at that. Next time will be configuring bitbang mode, where we can use the device as a configurable 8-bit IO port, blinking lights, and the wonders of Python's ctypes module...

The keyboard and the pen

2010-01-18T22:14:00.000Z

When I was a teenager, I discovered something amazing. A pen that made writing fun, desirable, and (almost) exciting. A Pilot V5. They never lasted long, but maybe that was because I'd actually write stuff with them. Time moved on, and I grew a penchant for nice Parker pens (Frontier rollerball please...), except that I'd get one for Christmas and have lost it by my birthday only a month later, and need another one. Anyways... Moving on more than a few years, I've come to realise that having something which makes writing attractive is more than just a nice incidental thing, but an important consideration.

At least for me, writing is a major way of organising and clarifying my thoughts, and I quite enjoy writing random streams of consciousness on a subject and later reviewing it to see if any interesting things are in there. If writing is fun, I'll do more of it, and having a decent writing instrument does make it fun.

Nowadays, I don't use a pen much (and my handwriting seems to be getting worse from lack of practice), but I still use a writing instrument - my keyboard. And just as there is a great difference between a free biro and a decent pen, so there is with keyboards, if not more so. A decent keyboard makes 'writing' fun, and that is a good thing. My current choice is a small Apple keyboard which is nice and portable, so I can plug it into whichever computer I happen to be using (it's even worth the annoyance of not having a delete key on a PC), and enjoy fine typing, perhaps even leading to some fine thoughts...

killing Python processes...

2009-11-24T22:19:00.000Z

I'm playing with some midi based Python stuff at the moment, doing raw file access to /dev/midi1 (midisport uno), and most of the time it's just sitting on a file.read(1). In Windows, the user can break into this with Ctrl-Break (Ctrl-C doesn't work on Windows or Linux), but there doesn't seem to be an equivalent to Ctrl-Break in the Linux world. So it's Ctrl-Z to put it in the background, ps -a, find the program, then terminate it hastily with sudo kill -9. All of which is a bit excessive. Rather than put something proper in there to terminate it (is select() the way to do these things on Linux?), I decided to get the wrong way a little less wrong.
I now have a half-way house to getting it a bit simpler:

alias killpy="sudo kill -9 \`ps -a | grep python | head -c 6\`"

And it's then just Ctrl-Z, killpy. I'm sure this isn't the best way of doing things, but I like the fact that it does things the same way I do, but using pipes to communicate, instead of the eye-brain-hand-keyboard loop. And it's the first time I've used the -c option on head (number of bytes to copy to stdout), so I've learnt something!

Of course it doesn't work if there is more than one Python process, or whatever, and yes I do need the sudo and -9.

Python lists aren't

2009-11-16T14:59:00.000Z

Names are important, and doubly so in programming. So when a programmer sees 'list', they think they know what that means, and similarly when they see 'array'.
The fundamental difference would be something like this:

array performance:
random access - O(1)
insertion / deletion of known element - O(n)

list performance:
random access - O(n)
insertion / deletion of known element - O(1)

The performance guarantees of a programming languages' data structures form part of the functional specification of that type, not just some incidental extra information.

I bumped into this when using streams of bytes (represented as lists of integers each < 256) with the following codec-like code:

def process(packet):
    itemlen = work_out_length(packet)
    item, packet = packet[:itemlen], packet[itemlen:]
    # do something with item
    return packet

packet = some data
while packet:
    packet = process(packet)

which is equivalent to this...

a = some data
while a:
    head, a = a[0], a[1:]
    process(head)

(The actual problem wasn't as easy to solve as the above case, as this assumes that the 'head' item is always a single byte; in reality it could be any number of bytes, and the packet would have to be streamed using multiple recursive loops like the above to process it. But the fundamentals are the same.)

Anyway, it all works fine until a large packet arrives. And then the interactive program suddenly stops; what took on the order of a millisecond suddenly takes half-an-hour, which to any user looks like the program has crashed.

This is a functional programming idiom, but it just doesn't work with Python lists in the general case of large lists. It didn't just slow it down, it completely broke it.

Solutions in this specific case are deques (collections.deque) or using iterators. But that's for another time...

In the C++ STL, part of the specification is a performance guarantee for each algorithm on each container type (http://www.sgi.com/tech/stl/complexity.html). In anything other than toy programs this information is critical, and they give the C++ developer an additional criteria in selecting the appropriate collection types. It changes 'worse/better' into 'wrong/right'. 'If [these specifications] are ignored [in an STL implementation], the performance of the resulting program will often render it useless.' - from previous link. The very separation of algorithms and data structures which the C++ STL enables (see the Elements of Programming book for a up-to-date discussion of the underlying paradigm of the STL - without STL-specific code), makes possible the enumeration of performance guarantees (other than specifying it for every function in every types' API). So while the Python documentation for lists warns that inserts and deletes at the beginning are O(n), this information isn't part of a coherent bigger picture which guides me to the right methods and data structures.

James Bond, Parenting, Refactoring

2009-11-12T06:11:00.000Z

So it is 1:00 in the morning, and our youngest son wakes up screaming. At 18 months it isn't always clear what the problem is, but with a bit of attention he soon settles. Except the same thing happened an hour ago, though my wife got up then. And, almost exactly an hour later, he wakes again, and does his 'muuuuu-meeeeee' type noises in-between crying. Except I've woken up first, which sort of means it's my job to go to him, again... And at this point I remember that vital software principle: don't repeat youself (DRY). The tempting thing is to give him back his dummy, give him a cuddle, and within 2 minutes he could be back asleep - and in 3 so could I. This is the bet I am making: there's a small chance he'll sleep through the rest of the night. It's always possible. But far more likely is that he'll wake again, and I won't get much sleep at all tonight. Because if he woke 3 hours on the trot when he normally sleeps through without problem, there's probably a reason - maybe even a reason I could fix (bets on a dirty nappy?) But I'm tired, and tiredness makes me even more lazy than usual, and... I hope he settles and I go back to bed.

As in many areas of life, software developers continually have to make the choice between short-term ease against the risk of long-term disaster. If the disaster was certain, the choice would be clear, if not easy. But there is always the chance that it will never happen, and if the cost of averting that potential disaster is significant (e.g. lost business due to competition in time-to-market), it is no longer clear-cut. But each time the risk is seen and ignored, the likelihood of getting it done right decreases. If I get up at each hour from 1am till 5am to settle my son, am I really going to bother doing anything different at 6am?

So what are we to do? Recognise the need early, when the cost is least and the confidence of knowing that the potential disaster has already been averted can have the longest effect. Make the commitment early, not counting the short-term effort as a cost, but as a decision well-made.

I leave the quantitative analysis to Ian Fleming:
'Once is happenstance, Twice is coincidence, The third time is enemy action'
- Ian Fleming, Goldfinger

Enemy action must be countered with force of will, or we shall be defeated.

Square Abstractions

2009-11-12T05:57:00.000Z

Managing complexity is at the heart of Software Engineering, and abstraction is the tool by which we accomplish this. But what do our abstractions look like, and how should we judge them?

Abstractions should be square.

Or cubic. Possibly n-dimensional hypercubes. But not rectangles. And lines are right out. G.A. Miller wrote a classic psychology paper in 1956 with the far-reaching conclusion that in uni-dimensional data-sets, humans have a typical classification capacity of between 2 and 3 bits - between 4 and 8 items. His paper is titled 'The Magical Number Seven, Plus or Minus Two: Some Limits on our Capacity for Processing Information'. How does this apply to software abstraction? It gives us a quantitive key to determining whether an abstraction (which implies a reduction in complexity) is of sufficient quality. It also gives us a clue to resolving the issue of abstractions still retaining too much complexity: add another dimension.

By square abstractions, I mean that a good set of abstractions in the software domain, from an arbitrarily complex starting point to the most understandable abstraction of that idea, should have approximately equal complexity in each dimension. If the result is that each (and all, since we have decreed equality) dimension of abstraction is still too complex, we must re-dimension, refactor, and re-abstract.

Soap bubbles form perfect spheres not just because they find it aesthetically pleasing, but because they are most comfortable like that. It takes the least effort. In software we should similarly strive to find the solution which satisfies the constraints with the least energy. Spheres might be nature's solution, but in software we tend to seek orthogonal abstractions - leading to squares, cubes, hypercubes, and so-on.

Getting practical for a moment, remember that every program, library, and API is an abstraction. An application containing a single 100,000 file (yes, really...) might be perfectly good internally, but is missing out on a key abstraction in terms of translation units, modules, whatever else maps to files. So split it into one-hundred 1000 line files - we've added a dimension and reduced the maximum unidimensional complexity. But we should continue - 100 is more than an order of magnitude greater than our magic 7 plus or minus 2. Directories, packages, folders: another level of abstraction. And because we are being square, we aim to have approximately 10 directories with 10 files in each. This stretches 7 +/- 2, but not sufficiently that any more abstraction would necessarily be helpful - adding a dimension has a cost too.
Why 100 files of 1000 lines, and not 316 files of 316 lines? Because not all abstractions have the same cost, and we can apply additional abstractions within those files. Like, um, classes, methods and functions.

So next time you (or I) think about adding that 100th method to our widget API, think about adding a new dimension instead. And if it isn't obvious what that new dimension might be, then get creative and invent something new.

10%	20%	33%	20%	10%
18%	55%	33%	23%	12%
14%	35%	40%	21%	11%
12%	29%	14%	11%	5%
12%	17%	10%	9%	5%

10%	20%	33%	20%	10%
18%	55%	33%	23%	12%
14%	35%	40%	21%	11%
12%	29%	14%	11%	5%
12%	17%	10%	9%	5%

10%	20%	33%	20%	10%
18%	55%	33%	23%	12%
14%	35%	40%	21%	11%
12%	29%	14%	11%	5%
12%	17%	10%	9%	5%

10%	20%	33%	20%	10%
18%	55%	33%	23%	12%
14%	35%	40%	21%	11%
12%	29%	14%	11%	5%
12%	17%	10%	9%	5%

10%	20%	33%	20%	10%
18%	55%	33%	23%	12%
14%	35%	40%	21%	11%
12%	29%	14%	11%	5%
12%	17%	10%	9%	5%

10%	20%	33%	20%	10%
18%	55%	33%	23%	12%
14%	35%	40%	21%	11%
12%	29%	14%	11%	5%
12%	17%	10%	9%	5%