I’ve not written a blog post for ages. Maybe sporadic posts are inevitable. Anyway, here’s one which has been sitting in draft form for a couple of years ago and I’ve just managed to drag it up-to-date.

tl;dr Compute and store high-resolution sampling of the Mandelbrot set, in a way which can be incrementally updated (e.g. to increase maximum iteration count) and is independent of any image which can then be generated from it.

I’ve been somewhat fascinated by fractals for over two decades now (that makes me feel old :-) ), and the Mandelbrot set is both common and relatively easy to understand and program. I’m not going to go into details here - take a look at the Wikipedia page.

The usual thing with Mandelbrot plotters is to evaluate the Mandelbrot set over a given area of the complex plane and render the result as a colourful picture. Depending on the hardware, area selected, and precision, this can take from milliseconds (rough rendering on a GPU) to many hours. But however long it takes, the typical process is to re-evaluate it in real time, each time. I’ve done an example of that in JavaScript here. There are many others in all sorts of programming languages.

brotmap is a bit different - it’s thinking about the question “What if we pre-calculated and stored the Mandelbrot set, to a sensible degree of accuracy, such that we could render images from the pre-calculated version?”

An analogy could be a sampling synthesizer. The work required to produce a tone from a sampler is considerably less than from a complex synth. Back in-the-day (two decades ago) I would pre-generate tables of sines for graphical plasma effects and so-on, because a table lookup was much faster than a sin(x) calculation even on a top-of-the-range 486. Today that would be crazy; memory is the bottleneck today, and table lookups of just about any sort are to be regarded with suspicion.

But that is exactly the point and purpose of brotmap. Its grand but insane idea is this: let’s precalculate the Mandelbrot set. (Well, actually the point and purpose of brotmap is to have a play around and maybe try out some new (or not-so-new) things along the way, but that’s not very profound).

There are a couple of things which needed to be decided before we go off and do such a silly thing. What are the input parameters? What is the end result? Starting with the output format, a coloured image isn’t much use to anyone; we need a something lower level. What we really want is an iteration count at bailout; that is what the colours in funky fractal images are based on anyway. By storing the iteration count, we can apply any colour map we like at a later point, or turn the map into a 3D height map, or anything else which may or may not be interesting.

On the input side, we need to specify the area we are interested in, the resolution, and the maximum iteration count. A square area from –2..+1 on the real axis and –1.5..+1.5 on the imaginary works well as a outer boundary, and the resolution can be as high as we like. For performance and accuracy we want each point to be accurately representable by a floating point number, so brotmap uses a step size of 2^-n for some n.

There is no point having high resolution if we don’t also have a high maximum iteration count. One key ‘feature’ of brotmap is that it allows incremental increases in iteration count. If a map is made with a MAX_ITER count of 1024, then the work generating that map can be reused by using it as a starting point in further iterations. To achieve this, not only is the iteration-count-at-bailout stored for each point, but also (for points which have so far not reached bailout), the current value of the complex number in the iterative calculation. To prevent precision loss, these are stored as a pair of double precision numbers (2x8 bytes per point). But if the point is definitely not in the M-set, then we no longer need that information - just the iteration count.

Anonymous unions to the rescue

These maps clearly get rather large. At a step size of just 2^–10, there are 3*3 (the image area on the complex plane) * 2¹⁰ (the number of points per unit in each row) * 2¹⁰ (the number of rows per unit) = 9.5 million points. And each of these has to store a good few bits of data - at least two double precision floating point values for points which could still be found to be in the M-set, and the bailout iteration count for those that have been excluded from the set.

Since we only care about either the current iteration values of re and im, or the number of iterations at which we exceeded our bailout condition, we can use unions to store both sets of information in the same space. But we also need a way of determining which type of data each point contains. Fortunately, IEEE754 floating point comes to our rescue here, because there are some special bit patterns we can use as sentinels - they will never appear in the course of (our) floating point evaluations, but we can set them and detect them. Amongst these values are the NaNs. Not-a-Number values allow us to use one of the pair of double floats to indicate that the point is outside the M-set, and that the other value should be treated as an integer iteration count.

struct pinfo {
    double x;
    union {
        double y;
        long itercount;
    };
};

One of the great things about C++ is support for anonymous unions. That union in the pinfo struct? No name. Anonymous, you might say. These types allow operations to all members of the union to be transparent - nothing in the code needs to know the structure even is a union.

To make the point clearer, the pinfo struct could have looked like this instead:

struct pinfo {
    double x
    double y;
    long itercount;
};

and nothing else in the code would have to change, except that we would be using 50% more storage (assuming the size of a long is also 8 bytes, typically true on 64 bit machines).

OK, so we have a basic input spec, output spec, and the M-set calculation itself is straightforward. But we’ve still got to write out gigabytes or more of data for anything interesting. We don’t want messy IO code cluttering up the rest of the code, do we?

mmap to the rescue

mmap is awesome. It’s not the easiest API to setup and clean up, but neither is it difficult, and in-between these steps it gets out of your way. Like totally-invisible out of your way. I can imagine that using it with a 32 bit virtual address space would be a pain, as you’d have to continually re-map different sections of a large (multi-gigabyte) file into the limited address space, but with a 64 bit VAS, it feels like magic. That structure of millions of 16 byte points? Wave a wand, and it’s backed by a file. No read operations, write operations, anything else at the user level. No stdio buffering, flushing, seeking. Just the C(++) memory model, and the OS does the rest. It feels like cheating - and maybe it is to use it like this - but remember this is a crazy pointless program, right?

pthreads to the rescue

Mandelbrot calculation is a trivially parallelizable problem. And I have multiple cores in my machine (only two, but…), so it would be nice to get a speedup from them. Sadly I’m more than a little late to this party. The C++11 standard has got threading support, and I’ll use this as an opportunity to learn that later, but for now I’ve learnt a minimum of pthreads coding to get this working. It’s simple enough; use pthread_create to create each thread, and have a mutex lock around shared data.

Rendering the data

Of course, this wouldn’t be much fun without actually being able to have some visual representation of the output, so make_ppm is a separate program which reads the data files and outputs a PPM file rendering the M-set in basic greyscale. Colour maps can wait :-)

Note I’m just using PPM as a lowest-common-denominator file format. It’s trivial for this sort of thing, though it does produce large (uncompressed) files, taking 3 bytes per pixel.

pnmtopng will convert a PPM file to the more useful png. (pnmtopng is part of netbpm - available for most Linux distributions or as part of homebrew for Mac, though ppm2tiff seems to be pre-installed on Mac and will suffice).

Running it

The code for brotmap is available on bitbucket, or github if you prefer that.

The makefile includes a target which will build and display the output (subject to dependencies - tested on Linux & Mac OS X with netpbm installed):

make show

This will compile the two programs (brotmap and make_ppm), and then run things (ignoring directories etc) as follows:

./brotmap mandel.dat 10
./make_ppm mandel.dat out.ppm
pnmtopng out.ppm > image.png
open image.png

This computes a set of data for a 3072x3072 sampling of the Mandelbrot set, then renders a PPM file from it, converts to a more friendly format, and then (hopefully) displays it on-screen.

brotmap takes two arguments: the target filename, and a ‘binary digits’ value, dictating the resolution of the computed filename. Note the output filenames will be large:

bit_size	res (x*y)	points	file size
10	3072	9437184	144 MB
11	6144	37748736	576 MB
12	12288	150994944	2.3 GB
13	24576	603979776	9.2 GB
14	49152	2415919104	36.86 GB
15	98304	9663676416	147.5 GB
16	196608	38654705664	589.8 GB

The default which various Make targets use is a binary size of 10. 12 is fairly quick, and I’ve tried 14 once or twice.

make_ppm takes two arguments; the input file generated by brotmap, and the output file which will be in PPM format (subformat P6).

See an example png (a 12288x12288 resolution greyscale image here - though note it may stress your browser slightly. This is computed to an iteration count of 4096, with binary digits of 12. Note that the 2.3 GB source data for this result in a PNG file of only 4 MB…

A smaller example (binary digits of 10) is here.

What’s next?

• Better command line parsing (e.g. for iteration count, step size…) - there’s some in there, but it’s very crude.

• Incremental spatial updates - incremental updates based on iteration count are nice, but what’s really needed are incremental resolution increases. It should be possible to increase resolution by a factor of two in each direction by keeping the current set of data as one of the four points being evaluated for each of the original points, so doubling the number of points takes the same amount of time as the previous round (assuming that data is available). It might make sense to completely change the structure of the data in memory / on-disk to support this operation.

• C++11 based concurrency - it won’t get much new, though I’ll get round to automatically working out the appropriate number of threads to use.

• Use of mmap-based IO in make_ppm as well as brotmap. Again, won’t get anything new, but will clean things up.

• Improvements to make_ppm - it should be possible to pull out a small section of the data and only render a selected area. Selectable colourmaps (something other than grayscale) would be nice too.

• Distributed parallelism - this is a major step up in terms of complexity, but definitely doable. I like to keep things low-level and primitive (and yet still portable - that’s what POSIX is all about), so I’ll probably do something socket based first, or maybe zeromq…

• Improved performance per core - the M-set calculation per point is very basic, with a single optimisation that it knows that points within the major circle and cardioid are within the M-set. Further optimisations could be to use SIMD parallelism (SSE3).

• Smooth colouring; most mandelbrot plotters don’t just use a simple iteration count - colour mapping, but compute some ‘distance’ factor from which to derive the colour.

I had an awesome time at PyConUK last weekend. I went to my first code dojo where I helped write a text-based adventure game (with a disturbing plot!), played with using Python on a RaspberryPi to access the GPIO, started a new Python module for my own use, and gave my second ever lightning talk, titled ‘Typing to Yourself’. This is 'the blog of the talk'.

What's this about then?

I’d started finding that IM chat logs often gave a lot of information, and often the timestamps were useful. The conversational nature of the chats also often gave subtle and useful clues about things such as confidence levels which a more formal report would lose. I started to think that it would be worth having that even if I wasn’t chatting to someone else. And so the madness started….

Typing to yourself. About stuff. Preferably as it happens, in ‘real time’ (is there another kind?). I suppose some people use Twitter like this, but I (and I'm sure my employer) like it that I keep at least some things to myself.

I've been doing this for a few months now, and got a single file with about 1300 lines of info I've been writing. Originally I cleared it out every few days, but then thought that maybe keeping it all around would be of some benefit.

Why Type to Yourself?

Record snippets of new knowledge

There are hundreds of small things I’ll find out about and then not look at again for 6 months. And chances are, I’ll forget all about them. It’s worth recording that sort of stuff. Things like pv, a new and useful iptables rule, the name of a nice vim colour scheme.

Decouple recording from reporting

Part of a knowledge-based job, where part of the task involves continual learning and researching, is that there is always the risk of going off into some blind alleys, dead-ends, or things more interesting than what you / I should really be working on. Chances are, even if it’s tangential to the work you / I should be doing, it’s still useful in itself, and worth recording. If I’ve just spent half an hour reading about ZeroMQ, I’ll include that. I might not record it in a list of training activities for the week though. It defers disclosure, allowing selection to take place at a later point. And therefore encourages more interesting and accurate reporting. By separating out recording from (for example) time reporting systems, we can post-process and filter that raw data later. Same thing as RAW and JPEG files from a camera; it’s not a bad thing to have the RAW data even if the end result is somewhat different. We are likely to be more honest if we type to ourselves, including feelings, distractions, etc, some of which will be useful at a later point.

Record why decisions were made

We make dozens of design decisions every day, and the vast majority of these seem obvious at the time. But there are some that aren’t ever obvious, and some that won’t be tomorrow even if they are now. Recording why we make the choices we do is important, even if just to force us to make them consciously. And it can be very useful to document dead-end design decisions which we try and ultimately give up on, in the hope of avoiding repeating them in the future.

Overcome creative blocks

Writer’s block affects programmers as well as novelists. Or at least it affects me from time to time. Sometimes I sit there for minutes on end, simply staring at the screen. I’ve found that explaining my dilemma to myself through the medium of typing to myself can often overcome this. Sometimes any activity can be a key to being able to think clearly about a problem again. Not only that, but regularly writing down what you're doing can be a great antidote to distraction and procrastination. This comes back to being able to be honest with ourselves about what we're doing - writing this down makes us think about it, be able to criticise it, and therefore more quickly be able to change direction.

Rubber duck debugging

This is a technique which uses vocalisation of a problem we’re facing to make us think more clearly about the problem; to take a step back, and explain to a toy rubber duck - ideally one with no previous knowledge of the problem we’re facing - what’s going on and how we’re trying to fix it. Just explaining it often helps us realise the problem. But rubber ducks are tricky to find at the crucial moment, and people think programmers are mad enough already without seeing us all talking to little ducks sitting on our desks. No, typing to ourselves, writing down the problem, is clearly much safer. After all, a programmer writing down a problem to themselves looks highly productive, rather than slightly mad.

Searchable history

We version control our code. Why not version our thoughts and activities? Write stuff down. Be able to go back in time and revisit those thoughts at a later date. Use it to store our short-term thoughts just before a meeting or break, so picking up where we left of is easy. That sort of stuff. Or to record surprising errors which we can’t reproduce and just put down to ‘something must have been set up wrong’. But then we start to find that we’ve already recorded it two months earlier…

How should I go about that?

Timestamped

Typing to yourself is an activity best done in real-time. Doing it later may still have some benefit, but the stream of consciousness brain-dump in the background has a lot of value which is lost if we’re just typing a historical report on what happened earlier. The point of typing to yourself is that having a record is useful; trying to remember stuff to record after the fact is lossy and a waste of time. Having things timestamped is a motivation (‘I’ve not written anything for 2 hours!’) and useful for searching history - finding out just when that bug appeared last.

Centralised

For a given context (e.g. work), there should be a single log on which you type to yourself. Perhaps there shouldn’t even be multiple contexts; everything should go in one big fat log. But it should be a single log, and yet available everywhere. Having to merge logs, or wondering where the latest version is, or knowing but not having access to it - all bad things. Dropbox is good.

Low friction

The whole point of ‘typing to yourself’ is that it shouldn’t be a context switch. I tend to keep a tmux pane open with editfile running (as track -t). Switching into it is just a case of Ctrl-A/cursor key. Then type stuff. Then Ctrl-A/cursor the other way. There’s no alt-tabbing, no windows changing focus or popping in front of each other. And importantly, I can see what’s there at all times, so it’s always in my consciousness - I don’t have to ‘swap it back in’ when I switch to it. Another aspect of low-friction is that the data itself should be widely available to programs to use, whether for searching, editing, or anything else. A text file is ideal.

An Implementation

I’m more keen about the ideas here than the implementation, but without an implementation it couldn’t work. I use my editfile program for almost all longer pieces of writing - blog posts, ideas, plans. And my ‘typing to myself’ log, which is just an editfile ‘instance’ used in ‘time track’ mode, which keeps a single file on Dropbox with all the content in a text file. I wrote about editfile in an earlier blog post. editfile started out as a very simple bash script:

#!/bin/bash
$EDITOR "~/Dropbox/editfile/$(basename $0)"

but is now a more complex bash script, including search, a two level hierarchy (I had that before iCloud decided it was a good idea!), command-line completion, and the time track mode I use for typing to myself.

The time-track mode has a couple of useful features - readline & history integration, and prompting and storing a timestamp. It’s not perfect; one of the key things is that the timestamp prompt doesn’t update in real time (although it does store the current time in the text file rather than the potentially out-of-date displayed time). The implementation of the time-track loop is the following:

now=$(date '+%Y/%m/%d %H:%M')
# read history from previous
history -r $HIST_FILE
while read -ep "$now >> " track_input ; do
    now=$(date '+%Y/%m/%d %H:%M')
    if [[ -z $track_input ]] ; then
        # don't store blank lines
        continue
    fi
    # use -- to indicate end to options e.g. if track_input
    # starts with '->' which previously caused errors
    history -s -- "$track_input"
    echo "$now $track_input" >> ${TARGET_PATH}
done
# append current session to history
history -a $HIST_FILE
# ensure bash prompt starts on a new line
echo

I use this every day at work, and it's got to the stage where I want to use it more. I've got plenty of ideas for things to integrate into my implementation, though the real essence of it doesn't need anything clever really.

I’m a great fan of Python; not only do I think the language itself is clean and readable, the community polite and helpful, and the ecosystem diverse and fascinating, but also the Zen of Python resonates with me.

I think there is significant value in that ‘there should be one - and preferably only one - obvious way to do it’, and that ‘namespaces are one honking great idea’. To me, it is sad that this essence of Python philosophy isn’t applied more widely.

Of course there is an element of tension in the Zen - Namespaces are about nesting, but ‘Flat is better than nested’. Nevertheless, flat within namespaces isn’t the same as not having any namespaces at all.

Namespaces don’t exist in a Google world.

I bet that most project name searches on Google are a single word. ‘jquery’ would get me want I want. ‘requests’ gets me what I want. Even one of my own projects - ‘pylibftdi’ gets me where I want to go. Getting to this point is probably part of choosing a good name. But that’s exactly the problem: how do I choose a good name for my new project? It’s one thing already knowing what project I’m interested in and simply using Google to get me there (sometimes a language name qualifier helps, e.g. ‘python flask’), it’s quite another two problems a) searching for a project to meet a given problem, not knowing what might be available b) searching for a project name I can use for my shiny new thing.

Searchable Project Names

One of the technologies I use the most at work is SSH. I tend to use it mostly in a fairly crude way, via it’s normal client and server programs ssh and sshd with many configuration options, but I have used the paramiko library. Which works well, and has a great name - easily remembered, especially after reading about its etymology on the project page. And very easily searchable. Recently, however, it’s development has slowed. I read in some places that it is now ‘deprecated’, but I’m not sure about that - the github project was last updated 11 days ago as of now… Anyhow, recently it has been forked, and its ‘successor’, has the brilliant name of… wait for it… ‘ssh’. Yes, brilliant. No, actually, it isn’t that helpful. Search for ‘ssh’, and it obviously won’t be there, straightaway, on the first page. Search for ‘python ssh’, and it still won’t be there. I guess it might be in a few months or years once it (presumably) takes off as the ‘one way to do it’, but now? It’s not helpful. Maybe it’s only aimed at people who use the PyPI search engine? And even if / when it is ‘obvious’, it’s still going to be a pain to do web searches for problems relating to use of the package. If I want to know which to use, then ‘paramiko vs ssh’ is of no help. Is the new ssh module ‘preferred’ by the community going forward? Or is it just a random fork by the Fabric guys? Other than the download stats on PyPI, it’s difficult to tell, because searching for info about it is... tricky.

As another example, the pbs package has recently changed its name to sh. Now pbs might not be the bestest name, but changing it to sh causes exactly the same kind of problem as ssh. There can be a real feeling of ‘hijacking’ when something so domain specific is used for a general project name. Using such a name is a clear signal: this is the module you should want to use for this task - you’d would be crazy to try anything else! That may or may not be intended or justified, but when it is a trivial thing for anyone to do, we developers have to be very careful and deliberate. Domain-specific project names, with massively overloaded meanings, only make sense in a very defined namespace: in these cases, the set of Python packages on PyPI.

Except, in a Google world, there aren’t namespaces.

Finding a project name (or rather finding the absence of one)

One of the problems with project naming in a flat unified project namespace (because of course there is one namespace) is project name squatting. For a variety of reasons - good and bad - developers decide that ‘release early, release often’ is a good policy. And one of the first things needed for that first visible release - perhaps the only thing needed - is a project name. So names are snapped up in an eager race. Project names have become the new hot-property. So we have lots of great project ideas, which need and find an awesome project name, make that first release, … and then do nothing. Stagnate. Just like the dot-com crazy days, we have project-name squatting, and permanent project-name ‘under construction’ empty shells… And, like defunct satellites cluttering low-earth orbit, the debris of project names now unused is a danger to every other project, trying to find its own space and path through the knowledge-sphere, avoiding the no-man’s land which has been staked out and left barren, taking juicy spectrum in an interference causing blackout. Soon there will be no more names left and [Sorry, I seem to have got carried away. Ahem.]

So…?

The following are some more thoughts and examples. Most of this is subjective. Hurrah for being able to dump half-finished ideas in a well name-spaced environment!

Over-general names:

• ‘node’ - really unhelpful.
• ‘windows’ - key element in GUI programming. WIMP.
• ‘dropbox’ - to a certain extent.
• ‘color’ - remember them? Good thing they didn’t take this word away…
• ‘word’ - a tool for writing words?
• eliminate a name not just from the project namespace, but increasingly from the word namespace.
• makes web searching harder

Unpleasant / generally bad names:

• git
• gimp
• My[anything] ;-)
• Any number of ‘offensive’ or ‘wrong connotation’ names, often leading to name changes, which help no one, except in an ‘any publicity is good publicity’ kind of way:
  • http://github.com/vmg/sundown/issues/36
  • testosterone - an example of deliberately trying to change the perception of a project in a positive way

Duplicate projects with the same name:

• pyro / pyro

Create or recognise our own namespaces:

• blog articles: author + title
• PyPI / CPAN etc
• ‘hungarian notation’ e.g. pyxyz, where the ‘py’ prefix includes some indicator of what namespace it lives in.
• domain name country code extensions - ‘.io’ etc
• ‘file extension’ as part of project name: ‘node.js’ etc
• identification by company or organisation: iOS / iPod / i*, gmail, google maps, etc
• identification by well-known patterns: xUnit, [j/py]Query etc.

Summary

If I were to produce a new vacuum cleaner and call it ‘Vacuum’, then various people might get upset. We (in software development) don’t really want to have to deal with all the legal & trademark clutter - the fact that we can have an idea, create a project and ‘market’ it all in a weekend is awesome, but requires us to act responsibly. Just because we can launch a new project into the orbital (name)space around us, doesn’t mean we must. Though it is awfully tempting… In addition we need to recognise, use, and educate ourselves and others about the namespaces all around us.

So I guess what I’m really saying, is (to quote Tim Peters)...

Namespaces are one honking great idea - let’s do more of those!

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

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

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:

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

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

   to

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

2. 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.
3. 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...!

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.

[edit 2013-11-25: note that recent versions of pylibftdi have deprecated and then removed the ability to use 'Driver' in this way; replace Driver and BitBangDriver with Device and BitBangDevice in the code below]

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

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' :-)

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

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

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

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.

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.

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.